marktree.h
Go to the documentation of this file.
1 #ifndef NVIM_MARKTREE_H
2 #define NVIM_MARKTREE_H
3 
4 #include <assert.h>
5 #include <stdint.h>
6 
7 #include "nvim/assert.h"
8 #include "nvim/garray.h"
9 #include "nvim/map.h"
10 #include "nvim/pos.h"
11 #include "nvim/types.h"
12 
13 #define MT_MAX_DEPTH 20
14 #define MT_BRANCH_FACTOR 10
15 
16 typedef struct {
17  int32_t row;
18  int32_t col;
19 } mtpos_t;
20 
21 typedef struct mtnode_s mtnode_t;
22 typedef struct {
23  int oldcol;
24  int i;
25 } iterstate_t;
26 
27 typedef struct {
29  int lvl;
31  int i;
33 } MarkTreeIter;
34 
35 
36 // Internal storage
37 //
38 // NB: actual marks have flags > 0, so we can use (row,col,0) pseudo-key for
39 // "space before (row,col)"
40 typedef struct {
42  uint32_t ns;
43  uint32_t id;
44  int32_t hl_id;
45  uint16_t flags;
46  uint16_t priority;
48 } mtkey_t;
49 #define MT_INVALID_KEY (mtkey_t) { { -1, -1 }, 0, 0, 0, 0, 0, NULL }
50 
51 #define MT_FLAG_REAL (((uint16_t)1) << 0)
52 #define MT_FLAG_END (((uint16_t)1) << 1)
53 #define MT_FLAG_PAIRED (((uint16_t)1) << 2)
54 #define MT_FLAG_HL_EOL (((uint16_t)1) << 3)
55 
56 #define DECOR_LEVELS 4
57 #define MT_FLAG_DECOR_OFFSET 4
58 #define MT_FLAG_DECOR_MASK (((uint16_t)(DECOR_LEVELS - 1)) << MT_FLAG_DECOR_OFFSET)
59 
60 // next flag is (((uint16_t)1) << 6)
61 
62 // These _must_ be last to preserve ordering of marks
63 #define MT_FLAG_RIGHT_GRAVITY (((uint16_t)1) << 14)
64 #define MT_FLAG_LAST (((uint16_t)1) << 15)
65 
66 #define MT_FLAG_EXTERNAL_MASK (MT_FLAG_DECOR_MASK | MT_FLAG_RIGHT_GRAVITY | MT_FLAG_HL_EOL)
67 
68 #define MARKTREE_END_FLAG (((uint64_t)1) << 63)
69 static inline uint64_t mt_lookup_id(uint32_t ns, uint32_t id, bool enda)
70 {
71  return (uint64_t)ns << 32 | id | (enda?MARKTREE_END_FLAG:0);
72 }
73 #undef MARKTREE_END_FLAG
74 
75 static inline uint64_t mt_lookup_key(mtkey_t key)
76 {
77  return mt_lookup_id(key.ns, key.id, key.flags & MT_FLAG_END);
78 }
79 
80 static inline bool mt_paired(mtkey_t key)
81 {
82  return key.flags & MT_FLAG_PAIRED;
83 }
84 
85 static inline bool mt_end(mtkey_t key)
86 {
87  return key.flags & MT_FLAG_END;
88 }
89 
90 static inline bool mt_start(mtkey_t key)
91 {
92  return mt_paired(key) && !mt_end(key);
93 }
94 
95 static inline bool mt_right(mtkey_t key)
96 {
97  return key.flags & MT_FLAG_RIGHT_GRAVITY;
98 }
99 
100 static inline uint8_t marktree_decor_level(mtkey_t key)
101 {
102  return (uint8_t)((key.flags&MT_FLAG_DECOR_MASK) >> MT_FLAG_DECOR_OFFSET);
103 }
104 
105 static inline uint16_t mt_flags(bool right_gravity, uint8_t decor_level)
106 {
107  assert(decor_level < DECOR_LEVELS);
108  return (uint16_t)((right_gravity ? MT_FLAG_RIGHT_GRAVITY : 0)
109  | (decor_level << MT_FLAG_DECOR_OFFSET));
110 }
111 
112 
113 struct mtnode_s {
114  int32_t n;
115  int32_t level;
116  // TODO(bfredl): we could consider having a only-sometimes-valid
117  // index into parent for faster "cached" lookup.
121 };
122 
123 // TODO(bfredl): the iterator is pretty much everpresent, make it part of the
124 // tree struct itself?
125 typedef struct {
127  size_t n_keys, n_nodes;
128  // TODO(bfredl): the pointer to node could be part of the larger
129  // Map(uint64_t, ExtmarkItem) essentially;
130  PMap(uint64_t) id2node[1];
131 } MarkTree;
132 
133 
134 #ifdef INCLUDE_GENERATED_DECLARATIONS
135 # include "marktree.h.generated.h"
136 #endif
137 
138 #endif // NVIM_MARKTREE_H
MarkTreeIter::i
int i
Definition: marktree.h:31
mtkey_t::decor_full
Decoration * decor_full
Definition: marktree.h:47
mtpos_t::col
int32_t col
Definition: marktree.h:18
iterstate_t::i
int i
Definition: marktree.h:24
MarkTreeIter::pos
mtpos_t pos
Definition: marktree.h:28
MT_FLAG_DECOR_MASK
#define MT_FLAG_DECOR_MASK
Definition: marktree.h:58
types.h
iterstate_t
Definition: marktree.h:22
mtpos_t::row
int32_t row
Definition: marktree.h:17
MT_FLAG_RIGHT_GRAVITY
#define MT_FLAG_RIGHT_GRAVITY
Definition: marktree.h:63
assert.h
mtkey_t::hl_id
int32_t hl_id
Definition: marktree.h:44
DECOR_LEVELS
#define DECOR_LEVELS
Definition: marktree.h:56
key
int key
Definition: keycodes.c:571
mtnode_s::level
int32_t level
Definition: marktree.h:115
MT_FLAG_PAIRED
#define MT_FLAG_PAIRED
Definition: marktree.h:53
mtkey_t::pos
mtpos_t pos
Definition: marktree.h:41
MarkTree::n_nodes
size_t n_nodes
Definition: marktree.h:127
mtpos_t
Definition: marktree.h:16
mtnode_s
Definition: marktree.h:113
mtkey_t
Definition: marktree.h:40
MarkTreeIter
Definition: marktree.h:27
mtkey_t::ns
uint32_t ns
Definition: marktree.h:42
mtnode_s::n
int32_t n
Definition: marktree.h:114
MARKTREE_END_FLAG
#define MARKTREE_END_FLAG
Definition: marktree.h:68
MarkTree::root
mtnode_t * root
Definition: marktree.h:126
mtkey_t::priority
uint16_t priority
Definition: marktree.h:46
map.h
assert
assert(len >=0)
MT_FLAG_DECOR_OFFSET
#define MT_FLAG_DECOR_OFFSET
Definition: marktree.h:57
s
char * s
Definition: eval.c:797
MarkTreeIter::node
mtnode_t * node
Definition: marktree.h:30
mtnode_s::key
mtkey_t key[2 *MT_BRANCH_FACTOR - 1]
Definition: marktree.h:119
mtnode_s::ptr
mtnode_t * ptr[]
Definition: marktree.h:120
MarkTreeIter::lvl
int lvl
Definition: marktree.h:29
mtkey_t::id
uint32_t id
Definition: marktree.h:43
MarkTree
Definition: marktree.h:125
garray.h
iterstate_t::oldcol
int oldcol
Definition: marktree.h:23
MT_MAX_DEPTH
#define MT_MAX_DEPTH
Definition: marktree.h:13
MT_FLAG_END
#define MT_FLAG_END
Definition: marktree.h:52
PMap
#define PMap(T)
Definition: map_defs.h:10
MT_BRANCH_FACTOR
#define MT_BRANCH_FACTOR
Definition: marktree.h:14
Decoration
Definition: decoration.h:38
pos.h
mtnode_s::parent
mtnode_t * parent
Definition: marktree.h:118
mtkey_t::flags
uint16_t flags
Definition: marktree.h:45