marktree.h
Go to the documentation of this file.
1 #ifndef NVIM_MARKTREE_H
2 #define NVIM_MARKTREE_H
3 
4 #include <stdint.h>
5 
6 #include "nvim/garray.h"
7 #include "nvim/map.h"
8 #include "nvim/pos.h"
9 
10 #define MT_MAX_DEPTH 20
11 #define MT_BRANCH_FACTOR 10
12 
13 typedef struct {
14  int32_t row;
15  int32_t col;
16 } mtpos_t;
17 
18 typedef struct {
19  int32_t row;
20  int32_t col;
21  uint64_t id;
23 } mtmark_t;
24 
25 typedef struct mtnode_s mtnode_t;
26 typedef struct {
27  int oldcol;
28  int i;
29 } iterstate_t;
30 
31 typedef struct {
33  int lvl;
35  int i;
37 } MarkTreeIter;
38 
39 
40 // Internal storage
41 //
42 // NB: actual marks have id > 0, so we can use (row,col,0) pseudo-key for
43 // "space before (row,col)"
44 typedef struct {
46  uint64_t id;
47 } mtkey_t;
48 
49 struct mtnode_s {
50  int32_t n;
51  int32_t level;
52  // TODO(bfredl): we could consider having a only-sometimes-valid
53  // index into parent for faster "cached" lookup.
57 };
58 
59 // TODO(bfredl): the iterator is pretty much everpresent, make it part of the
60 // tree struct itself?
61 typedef struct {
63  size_t n_keys, n_nodes;
64  uint64_t next_id;
65  // TODO(bfredl): the pointer to node could be part of the larger
66  // Map(uint64_t, ExtmarkItem) essentially;
67  PMap(uint64_t) id2node[1];
68 } MarkTree;
69 
70 
71 #ifdef INCLUDE_GENERATED_DECLARATIONS
72 # include "marktree.h.generated.h"
73 #endif
74 
75 #define MARKTREE_PAIRED_FLAG (((uint64_t)1) << 1)
76 #define MARKTREE_END_FLAG (((uint64_t)1) << 0)
77 
78 #define DECOR_LEVELS 4
79 #define DECOR_OFFSET 61
80 #define DECOR_MASK (((uint64_t)(DECOR_LEVELS-1)) << DECOR_OFFSET)
81 
82 static inline uint8_t marktree_decor_level(uint64_t id)
83 {
84  return (uint8_t)((id&DECOR_MASK) >> DECOR_OFFSET);
85 }
86 
87 #endif // NVIM_MARKTREE_H
MarkTreeIter::i
int i
Definition: marktree.h:35
mtmark_t::id
uint64_t id
Definition: marktree.h:21
mtpos_t::col
int32_t col
Definition: marktree.h:15
iterstate_t::i
int i
Definition: marktree.h:28
MarkTreeIter::pos
mtpos_t pos
Definition: marktree.h:32
mtmark_t
Definition: marktree.h:18
iterstate_t
Definition: marktree.h:26
mtpos_t::row
int32_t row
Definition: marktree.h:14
mtkey_t::id
uint64_t id
Definition: marktree.h:46
mtnode_s::level
int32_t level
Definition: marktree.h:51
DECOR_MASK
#define DECOR_MASK
Definition: marktree.h:80
mtkey_t::pos
mtpos_t pos
Definition: marktree.h:45
DECOR_OFFSET
#define DECOR_OFFSET
Definition: marktree.h:79
MarkTree::n_nodes
size_t n_nodes
Definition: marktree.h:63
mtpos_t
Definition: marktree.h:13
mtnode_s
Definition: marktree.h:49
mtmark_t::col
int32_t col
Definition: marktree.h:20
mtkey_t
Definition: marktree.h:44
MarkTreeIter
Definition: marktree.h:31
MarkTree::next_id
uint64_t next_id
Definition: marktree.h:64
mtnode_s::n
int32_t n
Definition: marktree.h:50
MarkTree::root
mtnode_t * root
Definition: marktree.h:62
map.h
s
char_u * s
Definition: eval.c:764
MarkTreeIter::node
mtnode_t * node
Definition: marktree.h:34
mtnode_s::key
mtkey_t key[2 *MT_BRANCH_FACTOR - 1]
Definition: marktree.h:55
mtmark_t::right_gravity
bool right_gravity
Definition: marktree.h:22
mtnode_s::ptr
mtnode_t * ptr[]
Definition: marktree.h:56
MarkTreeIter::lvl
int lvl
Definition: marktree.h:33
mtmark_t::row
int32_t row
Definition: marktree.h:19
MarkTree
Definition: marktree.h:61
garray.h
iterstate_t::oldcol
int oldcol
Definition: marktree.h:27
MT_MAX_DEPTH
#define MT_MAX_DEPTH
Definition: marktree.h:10
PMap
#define PMap(T)
Definition: map_defs.h:10
MT_BRANCH_FACTOR
#define MT_BRANCH_FACTOR
Definition: marktree.h:11
pos.h
mtnode_s::parent
mtnode_t * parent
Definition: marktree.h:54