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