aboutsummaryrefslogtreecommitdiff
path: root/src/nvim/marktree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/nvim/marktree.c')
-rw-r--r--src/nvim/marktree.c196
1 files changed, 110 insertions, 86 deletions
diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c
index 38014ab375..8ae138b2eb 100644
--- a/src/nvim/marktree.c
+++ b/src/nvim/marktree.c
@@ -56,12 +56,6 @@
#define T MT_BRANCH_FACTOR
#define ILEN (sizeof(mtnode_t)+(2 * T) * sizeof(void *))
-#define RIGHT_GRAVITY (((uint64_t)1) << 63)
-#define ANTIGRAVITY(id) ((id)&(RIGHT_GRAVITY-1))
-#define IS_RIGHT(id) ((id)&RIGHT_GRAVITY)
-
-#define PAIRED MARKTREE_PAIRED_FLAG
-#define END_FLAG MARKTREE_END_FLAG
#define ID_INCR (((uint64_t)1) << 2)
#define rawkey(itr) (itr->node->key[itr->i])
@@ -119,7 +113,7 @@ static int key_cmp(mtkey_t a, mtkey_t b)
}
// NB: keeping the events at the same pos sorted by id is actually not
// necessary only make sure that START is before END etc.
- return mt_generic_cmp(a.id, b.id);
+ return mt_generic_cmp(a.flags, b.flags);
}
static inline int marktree_getp_aux(const mtnode_t *x, mtkey_t k, int *r)
@@ -148,7 +142,7 @@ static inline int marktree_getp_aux(const mtnode_t *x, mtkey_t k, int *r)
static inline void refkey(MarkTree *b, mtnode_t *x, int i)
{
- pmap_put(uint64_t)(b->id2node, ANTIGRAVITY(x->key[i].id), x);
+ pmap_put(uint64_t)(b->id2node, mt_lookup_key(x->key[i]), x);
}
// put functions
@@ -221,38 +215,28 @@ static inline void marktree_putp_aux(MarkTree *b, mtnode_t *x, mtkey_t k)
}
}
-uint64_t marktree_put(MarkTree *b, int row, int col, bool right_gravity, uint8_t decor_level)
+void marktree_put(MarkTree *b, mtkey_t key, int end_row, int end_col, bool end_right)
{
- uint64_t id = (b->next_id+=ID_INCR);
- assert(decor_level < DECOR_LEVELS);
- id = id | ((uint64_t)decor_level << DECOR_OFFSET);
- uint64_t keyid = id;
- if (right_gravity) {
- // order all right gravity keys after the left ones, for effortless
- // insertion (but not deletion!)
- keyid |= RIGHT_GRAVITY;
- }
- marktree_put_key(b, row, col, keyid);
- return id;
-}
+ assert(!(key.flags & ~MT_FLAG_EXTERNAL_MASK));
+ if (end_row >= 0) {
+ key.flags |= MT_FLAG_PAIRED;
+ }
-uint64_t marktree_put_pair(MarkTree *b, int start_row, int start_col, bool start_right, int end_row,
- int end_col, bool end_right, uint8_t decor_level)
-{
- uint64_t id = (b->next_id+=ID_INCR)|PAIRED;
- assert(decor_level < DECOR_LEVELS);
- id = id | ((uint64_t)decor_level << DECOR_OFFSET);
- uint64_t start_id = id|(start_right?RIGHT_GRAVITY:0);
- uint64_t end_id = id|END_FLAG|(end_right?RIGHT_GRAVITY:0);
- marktree_put_key(b, start_row, start_col, start_id);
- marktree_put_key(b, end_row, end_col, end_id);
- return id;
+ marktree_put_key(b, key);
+
+ if (end_row >= 0) {
+ mtkey_t end_key = key;
+ end_key.flags = (uint16_t)((uint16_t)(key.flags & ~MT_FLAG_RIGHT_GRAVITY)
+ |(uint16_t)MT_FLAG_END
+ |(uint16_t)(end_right ? MT_FLAG_RIGHT_GRAVITY : 0));
+ end_key.pos = (mtpos_t){ end_row, end_col };
+ marktree_put_key(b, end_key);
+ }
}
-void marktree_put_key(MarkTree *b, int row, int col, uint64_t id)
+void marktree_put_key(MarkTree *b, mtkey_t k)
{
- mtkey_t k = { .pos = { .row = row, .col = col }, .id = id };
-
+ k.flags |= MT_FLAG_REAL; // let's be real.
if (!b->root) {
b->root = (mtnode_t *)xcalloc(1, ILEN);
b->n_nodes++;
@@ -302,7 +286,7 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
mtnode_t *cur = itr->node;
int curi = itr->i;
- uint64_t id = cur->key[curi].id;
+ uint64_t id = mt_lookup_key(cur->key[curi]);
// fprintf(stderr, "\nDELET %lu\n", id);
if (itr->node->level) {
@@ -364,7 +348,7 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
}
b->n_keys--;
- pmap_del(uint64_t)(b->id2node, ANTIGRAVITY(id));
+ pmap_del(uint64_t)(b->id2node, id);
// 5.
bool itr_dirty = false;
@@ -570,23 +554,29 @@ void marktree_free_node(mtnode_t *x)
}
/// NB: caller must check not pair!
-uint64_t marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level)
+void marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level, mtkey_t key)
{
- uint64_t old_id = rawkey(itr).id;
- pmap_del(uint64_t)(b->id2node, ANTIGRAVITY(old_id));
- uint64_t new_id = (b->next_id += ID_INCR) + ((uint64_t)decor_level << DECOR_OFFSET);
- rawkey(itr).id = new_id + (RIGHT_GRAVITY&old_id);
- refkey(b, itr->node, itr->i);
- return new_id;
+ // TODO(bfredl): clean up this mess and re-instantiate &= and |= forms
+ // once we upgrade to a non-broken version of gcc in functionaltest-lua CI
+ rawkey(itr).flags = (uint16_t)((uint16_t)rawkey(itr).flags & (uint16_t)~MT_FLAG_DECOR_MASK);
+ rawkey(itr).flags = (uint16_t)((uint16_t)rawkey(itr).flags
+ | (uint16_t)(decor_level << MT_FLAG_DECOR_OFFSET)
+ | (uint16_t)(key.flags & MT_FLAG_DECOR_MASK));
+ rawkey(itr).decor_full = key.decor_full;
+ rawkey(itr).hl_id = key.hl_id;
+ rawkey(itr).priority = key.priority;
}
void marktree_move(MarkTree *b, MarkTreeIter *itr, int row, int col)
{
- uint64_t old_id = rawkey(itr).id;
+ mtkey_t key = rawkey(itr);
// TODO(bfredl): optimize when moving a mark within a leaf without moving it
// across neighbours!
marktree_del_itr(b, itr, false);
- marktree_put_key(b, row, col, old_id);
+ key.pos = (mtpos_t){ row, col };
+
+
+ marktree_put_key(b, key);
itr->node = NULL; // itr might become invalid by put
}
@@ -602,14 +592,15 @@ bool marktree_itr_get(MarkTree *b, int row, int col, MarkTreeIter *itr)
bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last, bool gravity,
mtpos_t *oldbase)
{
- mtkey_t k = { .pos = p, .id = gravity ? RIGHT_GRAVITY : 0 };
- if (last && !gravity) {
- k.id = UINT64_MAX;
- }
if (b->n_keys == 0) {
itr->node = NULL;
return false;
}
+
+ mtkey_t k = { .pos = p, .flags = gravity ? MT_FLAG_RIGHT_GRAVITY : 0 };
+ if (last && !gravity) {
+ k.flags = MT_FLAG_LAST;
+ }
itr->pos = (mtpos_t){ 0, 0 };
itr->node = b->root;
itr->lvl = 0;
@@ -816,25 +807,29 @@ mtpos_t marktree_itr_pos(MarkTreeIter *itr)
return pos;
}
-mtmark_t marktree_itr_current(MarkTreeIter *itr)
+mtkey_t marktree_itr_current(MarkTreeIter *itr)
{
if (itr->node) {
- uint64_t keyid = rawkey(itr).id;
- mtpos_t pos = marktree_itr_pos(itr);
- mtmark_t mark = { .row = pos.row,
- .col = pos.col,
- .id = ANTIGRAVITY(keyid),
- .right_gravity = keyid & RIGHT_GRAVITY };
- return mark;
- }
- return (mtmark_t){ -1, -1, 0, false };
+ mtkey_t key = rawkey(itr);
+ key.pos = marktree_itr_pos(itr);
+ return key;
+ }
+ return MT_INVALID_KEY;
}
-static void swap_id(uint64_t *id1, uint64_t *id2)
+static bool itr_eq(MarkTreeIter *itr1, MarkTreeIter *itr2)
{
- uint64_t temp = *id1;
- *id1 = *id2;
- *id2 = temp;
+ return (&rawkey(itr1) == &rawkey(itr2));
+}
+
+static void itr_swap(MarkTreeIter *itr1, MarkTreeIter *itr2)
+{
+ mtkey_t key1 = rawkey(itr1);
+ mtkey_t key2 = rawkey(itr2);
+ rawkey(itr1) = key2;
+ rawkey(itr1).pos = key1.pos;
+ rawkey(itr2) = key1;
+ rawkey(itr2).pos = key2.pos;
}
bool marktree_splice(MarkTree *b, int start_line, int start_col, int old_extent_line,
@@ -865,7 +860,7 @@ bool marktree_splice(MarkTree *b, int start_line, int start_col, int old_extent_
mtpos_t ipos = marktree_itr_pos(itr);
if (!pos_leq(old_extent, ipos)
|| (old_extent.row == ipos.row && old_extent.col == ipos.col
- && !IS_RIGHT(rawkey(itr).id))) {
+ && !mt_right(rawkey(itr)))) {
marktree_itr_get_ext(b, old_extent, enditr, true, true, NULL);
assert(enditr->node);
// "assert" (itr <= enditr)
@@ -895,13 +890,13 @@ continue_same_node:
break;
}
- if (IS_RIGHT(rawkey(itr).id)) {
- while (rawkey(itr).id != rawkey(enditr).id
- && IS_RIGHT(rawkey(enditr).id)) {
+ if (mt_right(rawkey(itr))) {
+ while (!itr_eq(itr, enditr)
+ && mt_right(rawkey(enditr))) {
marktree_itr_prev(b, enditr);
}
- if (!IS_RIGHT(rawkey(enditr).id)) {
- swap_id(&rawkey(itr).id, &rawkey(enditr).id);
+ if (!mt_right(rawkey(enditr))) {
+ itr_swap(itr, enditr);
refkey(b, itr->node, itr->i);
refkey(b, enditr->node, enditr->i);
} else {
@@ -911,7 +906,7 @@ continue_same_node:
}
}
- if (rawkey(itr).id == rawkey(enditr).id) {
+ if (itr_eq(itr, enditr)) {
// actually, will be past_right after this key
past_right = true;
}
@@ -1006,13 +1001,13 @@ void marktree_move_region(MarkTree *b, int start_row, colnr_T start_col, int ext
marktree_itr_get_ext(b, start, itr, false, true, NULL);
kvec_t(mtkey_t) saved = KV_INITIAL_VALUE;
while (itr->node) {
- mtpos_t pos = marktree_itr_pos(itr);
- if (!pos_leq(pos, end) || (pos.row == end.row && pos.col == end.col
- && rawkey(itr).id & RIGHT_GRAVITY)) {
+ mtkey_t k = marktree_itr_current(itr);
+ if (!pos_leq(k.pos, end) || (k.pos.row == end.row && k.pos.col == end.col
+ && mt_right(k))) {
break;
}
- relative(start, &pos);
- kv_push(saved, ((mtkey_t){ .pos = pos, .id = rawkey(itr).id }));
+ relative(start, &k.pos);
+ kv_push(saved, k);
marktree_del_itr(b, itr, false);
}
@@ -1024,30 +1019,36 @@ void marktree_move_region(MarkTree *b, int start_row, colnr_T start_col, int ext
for (size_t i = 0; i < kv_size(saved); i++) {
mtkey_t item = kv_A(saved, i);
unrelative(new, &item.pos);
- marktree_put_key(b, item.pos.row, item.pos.col, item.id);
+ marktree_put_key(b, item);
}
kv_destroy(saved);
}
/// @param itr OPTIONAL. set itr to pos.
-mtpos_t marktree_lookup(MarkTree *b, uint64_t id, MarkTreeIter *itr)
+mtkey_t marktree_lookup_ns(MarkTree *b, uint32_t ns, uint32_t id, bool end, MarkTreeIter *itr)
+{
+ return marktree_lookup(b, mt_lookup_id(ns, id, end), itr);
+}
+
+/// @param itr OPTIONAL. set itr to pos.
+mtkey_t marktree_lookup(MarkTree *b, uint64_t id, MarkTreeIter *itr)
{
mtnode_t *n = pmap_get(uint64_t)(b->id2node, id);
if (n == NULL) {
if (itr) {
itr->node = NULL;
}
- return (mtpos_t){ -1, -1 };
+ return MT_INVALID_KEY;
}
int i = 0;
for (i = 0; i < n->n; i++) {
- if (ANTIGRAVITY(n->key[i].id) == id) {
+ if (mt_lookup_key(n->key[i]) == id) {
goto found;
}
}
abort();
found: {}
- mtpos_t pos = n->key[i].pos;
+ mtkey_t key = n->key[i];
if (itr) {
itr->i = i;
itr->node = n;
@@ -1066,14 +1067,23 @@ found_node:
itr->s[b->root->level-p->level].i = i;
}
if (i > 0) {
- unrelative(p->key[i-1].pos, &pos);
+ unrelative(p->key[i-1].pos, &key.pos);
}
n = p;
}
if (itr) {
marktree_itr_fix_pos(b, itr);
}
- return pos;
+ return key;
+}
+
+mtpos_t marktree_get_altpos(MarkTree *b, mtkey_t mark, MarkTreeIter *itr)
+{
+ mtkey_t end = MT_INVALID_KEY;
+ if (mt_paired(mark)) {
+ end = marktree_lookup_ns(b, mark.ns, mark.id, !mt_end(mark), itr);
+ }
+ return end.pos;
}
static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr)
@@ -1092,6 +1102,20 @@ static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr)
assert(x == itr->node);
}
+// for unit test
+void marktree_put_test(MarkTree *b, uint32_t id, int row, int col, bool right_gravity)
+{
+ mtkey_t key = { { row, col }, UINT32_MAX, id, 0,
+ mt_flags(right_gravity, 0), 0, NULL };
+ marktree_put(b, key, -1, -1, false);
+}
+
+// for unit test
+bool mt_right_test(mtkey_t key)
+{
+ return mt_right(key);
+}
+
void marktree_check(MarkTree *b)
{
#ifndef NDEBUG
@@ -1134,11 +1158,11 @@ static size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_rig
}
assert(pos_leq(*last, x->key[i].pos));
if (last->row == x->key[i].pos.row && last->col == x->key[i].pos.col) {
- assert(!*last_right || IS_RIGHT(x->key[i].id));
+ assert(!*last_right || mt_right(x->key[i]));
}
- *last_right = IS_RIGHT(x->key[i].id);
+ *last_right = mt_right(x->key[i]);
assert(x->key[i].pos.col >= 0);
- assert(pmap_get(uint64_t)(b->id2node, ANTIGRAVITY(x->key[i].id)) == x);
+ assert(pmap_get(uint64_t)(b->id2node, mt_lookup_key(x->key[i])) == x);
}
if (x->level) {
generated by cgit (git 2.34.1) at 2025-05-22 20:19:56 +0000