diff options
Diffstat (limited to 'src/nvim/marktree.c')
| -rw-r--r-- | src/nvim/marktree.c | 1638 |
1 files changed, 1356 insertions, 282 deletions
diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 2036ddd21d..b555b3b4ae 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -1,6 +1,3 @@ -// This is an open source non-commercial project. Dear PVS-Studio, please check -// it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com - // Tree data structure for storing marks at (row, col) positions and updating // them to arbitrary text changes. Derivative work of kbtree in klib, whose // copyright notice is reproduced below. Also inspired by the design of the @@ -14,8 +11,6 @@ // Use marktree_itr_current and marktree_itr_next/prev to read marks in a loop. // marktree_del_itr deletes the current mark of the iterator and implicitly // moves the iterator to the next mark. -// -// Work is ongoing to fully support ranges (mark pairs). // Copyright notice for kbtree (included in heavily modified form): // @@ -48,29 +43,41 @@ // at the repo root. #include <assert.h> +#include <inttypes.h> #include <stdio.h> #include <stdlib.h> #include <string.h> +#include <sys/types.h> #include "klib/kvec.h" #include "nvim/garray.h" #include "nvim/marktree.h" #include "nvim/memory.h" -#include "nvim/pos.h" +#include "nvim/pos_defs.h" +// only for debug functions +#include "nvim/api/private/defs.h" +#include "nvim/api/private/helpers.h" +#include "nvim/garray_defs.h" +#include "nvim/macros_defs.h" #define T MT_BRANCH_FACTOR -#define ILEN (sizeof(mtnode_t) + (2 * T) * sizeof(void *)) +#define ILEN (sizeof(MTNode) + (2 * T) * sizeof(void *)) #define ID_INCR (((uint64_t)1) << 2) -#define rawkey(itr) ((itr)->node->key[(itr)->i]) +#define rawkey(itr) ((itr)->x->key[(itr)->i]) -static bool pos_leq(mtpos_t a, mtpos_t b) +static bool pos_leq(MTPos a, MTPos b) { return a.row < b.row || (a.row == b.row && a.col <= b.col); } -static void relative(mtpos_t base, mtpos_t *val) +static bool pos_less(MTPos a, MTPos b) +{ + return !pos_leq(b, a); +} + +static void relative(MTPos base, MTPos *val) { assert(pos_leq(base, *val)); if (val->row == base.row) { @@ -81,7 +88,7 @@ static void relative(mtpos_t base, mtpos_t *val) } } -static void unrelative(mtpos_t base, mtpos_t *val) +static void unrelative(MTPos base, MTPos *val) { if (val->row == 0) { val->row = base.row; @@ -91,7 +98,7 @@ static void unrelative(mtpos_t base, mtpos_t *val) } } -static void compose(mtpos_t *base, mtpos_t val) +static void compose(MTPos *base, MTPos val) { if (val.row == 0) { base->col += val.col; @@ -101,12 +108,21 @@ static void compose(mtpos_t *base, mtpos_t val) } } +// Used by `marktree_splice`. Need to keep track of marks which moved +// in order to repair intersections. +typedef struct { + uint64_t id; + MTNode *old, *new; + int old_i, new_i; +} Damage; +typedef kvec_withinit_t(Damage, 8) DamageList; + #ifdef INCLUDE_GENERATED_DECLARATIONS # include "marktree.c.generated.h" #endif #define mt_generic_cmp(a, b) (((b) < (a)) - ((a) < (b))) -static int key_cmp(mtkey_t a, mtkey_t b) +static int key_cmp(MTKey a, MTKey b) { int cmp = mt_generic_cmp(a.pos.row, b.pos.row); if (cmp != 0) { @@ -116,18 +132,25 @@ static int key_cmp(mtkey_t a, mtkey_t b) if (cmp != 0) { return cmp; } - // 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.flags, b.flags); + + // TODO(bfredl): MT_FLAG_REAL could go away if we fix marktree_getp_aux for real + const uint16_t cmp_mask = MT_FLAG_RIGHT_GRAVITY | MT_FLAG_END | MT_FLAG_REAL | MT_FLAG_LAST; + return mt_generic_cmp(a.flags & cmp_mask, b.flags & cmp_mask); } -static inline int marktree_getp_aux(const mtnode_t *x, mtkey_t k, int *r) +/// @return position of k if it exists in the node, otherwise the position +/// it should be inserted, which ranges from 0 to x->n _inclusively_ +/// @param match (optional) set to TRUE if match (pos, gravity) was found +static inline int marktree_getp_aux(const MTNode *x, MTKey k, bool *match) { - int tr, *rr, begin = 0, end = x->n; + bool dummy_match; + bool *m = match ? match : &dummy_match; + + int begin = 0, end = x->n; if (x->n == 0) { + *m = false; return -1; } - rr = r? r : &tr; while (begin < end) { int mid = (begin + end) >> 1; if (key_cmp(x->key[mid], k) < 0) { @@ -137,47 +160,84 @@ static inline int marktree_getp_aux(const mtnode_t *x, mtkey_t k, int *r) } } if (begin == x->n) { - *rr = 1; return x->n - 1; + *m = false; + return x->n - 1; } - if ((*rr = key_cmp(k, x->key[begin])) < 0) { + if (!(*m = (key_cmp(k, x->key[begin]) == 0))) { begin--; } return begin; } -static inline void refkey(MarkTree *b, mtnode_t *x, int i) +static inline void refkey(MarkTree *b, MTNode *x, int i) { pmap_put(uint64_t)(b->id2node, mt_lookup_key(x->key[i]), x); } +static MTNode *id2node(MarkTree *b, uint64_t id) +{ + return pmap_get(uint64_t)(b->id2node, id); +} + // put functions // x must be an internal node, which is not full // x->ptr[i] should be a full node, i e x->ptr[i]->n == 2*T-1 -static inline void split_node(MarkTree *b, mtnode_t *x, const int i) +static inline void split_node(MarkTree *b, MTNode *x, const int i, MTKey next) { - mtnode_t *y = x->ptr[i]; - mtnode_t *z; - z = (mtnode_t *)xcalloc(1, y->level ? ILEN : sizeof(mtnode_t)); - b->n_nodes++; + MTNode *y = x->ptr[i]; + MTNode *z = marktree_alloc_node(b, y->level); z->level = y->level; z->n = T - 1; - memcpy(z->key, &y->key[T], sizeof(mtkey_t) * (T - 1)); + + // tricky: we might split a node in between inserting the start node and the end + // node of the same pair. Then we must not intersect this id yet (done later + // in marktree_intersect_pair). + uint64_t last_start = mt_end(next) ? mt_lookup_id(next.ns, next.id, false) : MARKTREE_END_FLAG; + + // no alloc in the common case (less than 4 intersects) + kvi_copy(z->intersect, y->intersect); + + if (!y->level) { + uint64_t pi = pseudo_index(y, 0); // note: sloppy pseudo-index + for (int j = 0; j < T; j++) { + MTKey k = y->key[j]; + uint64_t pi_end = pseudo_index_for_id(b, mt_lookup_id(k.ns, k.id, true), true); + if (mt_start(k) && pi_end > pi && mt_lookup_key(k) != last_start) { + intersect_node(b, z, mt_lookup_id(k.ns, k.id, false)); + } + } + + // note: y->key[T-1] is moved up and thus checked for both + for (int j = T - 1; j < (T * 2) - 1; j++) { + MTKey k = y->key[j]; + uint64_t pi_start = pseudo_index_for_id(b, mt_lookup_id(k.ns, k.id, false), true); + if (mt_end(k) && pi_start > 0 && pi_start < pi) { + intersect_node(b, y, mt_lookup_id(k.ns, k.id, false)); + } + } + } + + memcpy(z->key, &y->key[T], sizeof(MTKey) * (T - 1)); for (int j = 0; j < T - 1; j++) { refkey(b, z, j); } if (y->level) { - memcpy(z->ptr, &y->ptr[T], sizeof(mtnode_t *) * T); + memcpy(z->ptr, &y->ptr[T], sizeof(MTNode *) * T); for (int j = 0; j < T; j++) { z->ptr[j]->parent = z; + z->ptr[j]->p_idx = (int16_t)j; } } y->n = T - 1; memmove(&x->ptr[i + 2], &x->ptr[i + 1], - sizeof(mtnode_t *) * (size_t)(x->n - i)); + sizeof(MTNode *) * (size_t)(x->n - i)); x->ptr[i + 1] = z; z->parent = x; // == y->parent - memmove(&x->key[i + 1], &x->key[i], sizeof(mtkey_t) * (size_t)(x->n - i)); + for (int j = i + 1; j < x->n + 2; j++) { + x->ptr[j]->p_idx = (int16_t)j; + } + memmove(&x->key[i + 1], &x->key[i], sizeof(MTKey) * (size_t)(x->n - i)); // move key to internal layer: x->key[i] = y->key[T - 1]; @@ -190,25 +250,32 @@ static inline void split_node(MarkTree *b, mtnode_t *x, const int i) if (i > 0) { unrelative(x->key[i - 1].pos, &x->key[i].pos); } + + if (y->level) { + bubble_up(y); + bubble_up(z); + } else { + // code above goose here + } } // x must not be a full node (even if there might be internal space) -static inline void marktree_putp_aux(MarkTree *b, mtnode_t *x, mtkey_t k) +static inline void marktree_putp_aux(MarkTree *b, MTNode *x, MTKey k) { - int i; + // TODO(bfredl): ugh, make sure this is the _last_ valid (pos, gravity) position, + // to minimize movement + int i = marktree_getp_aux(x, k, NULL) + 1; if (x->level == 0) { - i = marktree_getp_aux(x, k, 0); - if (i != x->n - 1) { - memmove(&x->key[i + 2], &x->key[i + 1], - (size_t)(x->n - i - 1) * sizeof(mtkey_t)); + if (i != x->n) { + memmove(&x->key[i + 1], &x->key[i], + (size_t)(x->n - i) * sizeof(MTKey)); } - x->key[i + 1] = k; - refkey(b, x, i + 1); + x->key[i] = k; + refkey(b, x, i); x->n++; } else { - i = marktree_getp_aux(x, k, 0) + 1; if (x->ptr[i]->n == 2 * T - 1) { - split_node(b, x, i); + split_node(b, x, i, k); if (key_cmp(k, x->key[i]) > 0) { i++; } @@ -220,9 +287,9 @@ static inline void marktree_putp_aux(MarkTree *b, mtnode_t *x, mtkey_t k) } } -void marktree_put(MarkTree *b, mtkey_t key, int end_row, int end_col, bool end_right) +void marktree_put(MarkTree *b, MTKey key, int end_row, int end_col, bool end_right) { - assert(!(key.flags & ~MT_FLAG_EXTERNAL_MASK)); + assert(!(key.flags & ~(MT_FLAG_EXTERNAL_MASK | MT_FLAG_RIGHT_GRAVITY))); if (end_row >= 0) { key.flags |= MT_FLAG_PAIRED; } @@ -230,32 +297,150 @@ void marktree_put(MarkTree *b, mtkey_t key, int end_row, int end_col, bool end_r marktree_put_key(b, key); if (end_row >= 0) { - mtkey_t end_key = key; + MTKey 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 }; + end_key.pos = (MTPos){ end_row, end_col }; marktree_put_key(b, end_key); + MarkTreeIter itr[1] = { 0 }, end_itr[1] = { 0 }; + marktree_lookup(b, mt_lookup_key(key), itr); + marktree_lookup(b, mt_lookup_key(end_key), end_itr); + + marktree_intersect_pair(b, mt_lookup_key(key), itr, end_itr, false); + } +} + +// this is currently not used very often, but if it was it should use binary search +static bool intersection_has(Intersection *x, uint64_t id) +{ + for (size_t i = 0; i < kv_size(*x); i++) { + if (kv_A(*x, i) == id) { + return true; + } else if (kv_A(*x, i) >= id) { + return false; + } } + return false; } -void marktree_put_key(MarkTree *b, mtkey_t k) +static void intersect_node(MarkTree *b, MTNode *x, uint64_t id) +{ + assert(!(id & MARKTREE_END_FLAG)); + kvi_pushp(x->intersect); + // optimized for the common case: new key is always in the end + for (ssize_t i = (ssize_t)kv_size(x->intersect) - 1; i >= 0; i--) { + if (i > 0 && kv_A(x->intersect, i - 1) > id) { + kv_A(x->intersect, i) = kv_A(x->intersect, i - 1); + } else { + kv_A(x->intersect, i) = id; + break; + } + } +} + +static void unintersect_node(MarkTree *b, MTNode *x, uint64_t id, bool strict) +{ + assert(!(id & MARKTREE_END_FLAG)); + bool seen = false; + size_t i; + for (i = 0; i < kv_size(x->intersect); i++) { + if (kv_A(x->intersect, i) < id) { + continue; + } else if (kv_A(x->intersect, i) == id) { + seen = true; + break; + } else { // (kv_A(x->intersect, i) > id) + break; + } + } + if (strict) { + assert(seen); + } + + if (seen) { + if (i < kv_size(x->intersect) - 1) { + memmove(&kv_A(x->intersect, i), &kv_A(x->intersect, i + 1), (kv_size(x->intersect) - i - 1) * + sizeof(kv_A(x->intersect, i))); + } + kv_size(x->intersect)--; + } +} + +/// @param itr mutated +/// @param end_itr not mutated +void marktree_intersect_pair(MarkTree *b, uint64_t id, MarkTreeIter *itr, MarkTreeIter *end_itr, + bool delete) +{ + int lvl = 0, maxlvl = MIN(itr->lvl, end_itr->lvl); +#define iat(itr, l, q) ((l == itr->lvl) ? itr->i + q : itr->s[l].i) + for (; lvl < maxlvl; lvl++) { + if (itr->s[lvl].i > end_itr->s[lvl].i) { + return; // empty range + } else if (itr->s[lvl].i < end_itr->s[lvl].i) { + break; // work to do + } + } + if (lvl == maxlvl && iat(itr, lvl, 1) > iat(end_itr, lvl, 0)) { + return; // empty range + } + + while (itr->x) { + bool skip = false; + if (itr->x == end_itr->x) { + if (itr->x->level == 0 || itr->i >= end_itr->i) { + break; + } else { + skip = true; + } + } else if (itr->lvl > lvl) { + skip = true; + } else { + if (iat(itr, lvl, 1) < iat(end_itr, lvl, 1)) { + skip = true; + } else { + lvl++; + } + } + + if (skip) { + if (itr->x->level) { + MTNode *x = itr->x->ptr[itr->i + 1]; + if (delete) { + unintersect_node(b, x, id, true); + } else { + intersect_node(b, x, id); + } + } + } + marktree_itr_next_skip(b, itr, skip, true, NULL); + } +#undef iat +} + +static MTNode *marktree_alloc_node(MarkTree *b, bool internal) +{ + MTNode *x = xcalloc(1, internal ? ILEN : sizeof(MTNode)); + kvi_init(x->intersect); + b->n_nodes++; + return x; +} + +void marktree_put_key(MarkTree *b, MTKey k) { k.flags |= MT_FLAG_REAL; // let's be real. if (!b->root) { - b->root = (mtnode_t *)xcalloc(1, ILEN); - b->n_nodes++; + b->root = marktree_alloc_node(b, true); } - mtnode_t *r, *s; b->n_keys++; - r = b->root; + MTNode *r = b->root; if (r->n == 2 * T - 1) { - b->n_nodes++; - s = (mtnode_t *)xcalloc(1, ILEN); + MTNode *s = marktree_alloc_node(b, true); b->root = s; s->level = r->level + 1; s->n = 0; s->ptr[0] = r; r->parent = s; - split_node(b, s, 0); + r->p_idx = 0; + split_node(b, s, 0, k); r = s; } marktree_putp_aux(b, r, k); @@ -279,26 +464,41 @@ void marktree_put_key(MarkTree *b, mtkey_t k) /// 6. If 4 went all the way to the root node. The root node /// might have ended up with size 0. Delete it then. /// -/// NB: ideally keeps the iterator valid. Like point to the key after this -/// if present. +/// The iterator remains valid, and now points at the key _after_ the deleted +/// one. /// /// @param rev should be true if we plan to iterate _backwards_ and delete /// stuff before this key. Most of the time this is false (the /// recommended strategy is to always iterate forward) -void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev) +uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev) { int adjustment = 0; - mtnode_t *cur = itr->node; + MTNode *cur = itr->x; int curi = itr->i; uint64_t id = mt_lookup_key(cur->key[curi]); - // fprintf(stderr, "\nDELET %lu\n", id); - if (itr->node->level) { + MTKey raw = rawkey(itr); + uint64_t other = 0; + if (mt_paired(raw) && !(raw.flags & MT_FLAG_ORPHANED)) { + other = mt_lookup_key_side(raw, !mt_end(raw)); + + MarkTreeIter other_itr[1]; + marktree_lookup(b, other, other_itr); + rawkey(other_itr).flags |= MT_FLAG_ORPHANED; + // Remove intersect markers. NB: must match exactly! + if (mt_start(raw)) { + MarkTreeIter this_itr[1] = { *itr }; // mutated copy + marktree_intersect_pair(b, id, this_itr, other_itr, true); + } else { + marktree_intersect_pair(b, other, other_itr, itr, true); + } + } + + if (itr->x->level) { if (rev) { abort(); } else { - // fprintf(stderr, "INTERNAL %d\n", cur->level); // steal previous node marktree_itr_prev(b, itr); adjustment = -1; @@ -306,41 +506,72 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev) } // 3. - mtnode_t *x = itr->node; + MTNode *x = itr->x; assert(x->level == 0); - mtkey_t intkey = x->key[itr->i]; + MTKey intkey = x->key[itr->i]; if (x->n > itr->i + 1) { memmove(&x->key[itr->i], &x->key[itr->i + 1], - sizeof(mtkey_t) * (size_t)(x->n - itr->i - 1)); + sizeof(MTKey) * (size_t)(x->n - itr->i - 1)); } x->n--; + b->n_keys--; + pmap_del(uint64_t)(b->id2node, id, NULL); + // 4. // if (adjustment == 1) { // abort(); // } if (adjustment == -1) { int ilvl = itr->lvl - 1; - const mtnode_t *lnode = x; + MTNode *lnode = x; + uint64_t start_id = 0; + bool did_bubble = false; + if (mt_end(intkey)) { + start_id = mt_lookup_key_side(intkey, false); + } do { - const mtnode_t *const p = lnode->parent; + MTNode *p = lnode->parent; if (ilvl < 0) { abort(); } - const int i = itr->s[ilvl].i; + int i = itr->s[ilvl].i; assert(p->ptr[i] == lnode); if (i > 0) { unrelative(p->key[i - 1].pos, &intkey.pos); } + + if (p != cur && start_id) { + if (intersection_has(&p->ptr[0]->intersect, start_id)) { + // if not the first time, we need to undo the addition in the + // previous step (`intersect_node` just below) + int last = (lnode != x) ? 1 : 0; + for (int k = 0; k < p->n + last; k++) { // one less as p->ptr[n] is the last + unintersect_node(b, p->ptr[k], start_id, true); + } + intersect_node(b, p, start_id); + did_bubble = true; + } + } + lnode = p; ilvl--; } while (lnode != cur); - mtkey_t deleted = cur->key[curi]; + MTKey deleted = cur->key[curi]; cur->key[curi] = intkey; refkey(b, cur, curi); + // if `did_bubble` then we already added `start_id` to some parent + if (mt_end(cur->key[curi]) && !did_bubble) { + uint64_t pi = pseudo_index(x, 0); // note: sloppy pseudo-index + uint64_t pi_start = pseudo_index_for_id(b, start_id, true); + if (pi_start > 0 && pi_start < pi) { + intersect_node(b, x, start_id); + } + } + relative(intkey.pos, &deleted.pos); - mtnode_t *y = cur->ptr[curi + 1]; + MTNode *y = cur->ptr[curi + 1]; if (deleted.pos.row || deleted.pos.col) { while (y) { for (int k = 0; k < y->n; k++) { @@ -352,46 +583,48 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev) itr->i--; } - b->n_keys--; - pmap_del(uint64_t)(b->id2node, id); - // 5. bool itr_dirty = false; int rlvl = itr->lvl - 1; int *lasti = &itr->i; + MTPos ppos = itr->pos; while (x != b->root) { assert(rlvl >= 0); - mtnode_t *p = x->parent; + MTNode *p = x->parent; if (x->n >= T - 1) { // we are done, if this node is fine the rest of the tree will be break; } int pi = itr->s[rlvl].i; assert(p->ptr[pi] == x); + if (pi > 0) { + ppos.row -= p->key[pi - 1].pos.row; + ppos.col = itr->s[rlvl].oldcol; + } + // ppos is now the pos of p + if (pi > 0 && p->ptr[pi - 1]->n > T - 1) { *lasti += 1; itr_dirty = true; // steal one key from the left neighbour - pivot_right(b, p, pi - 1); + pivot_right(b, ppos, p, pi - 1); break; } else if (pi < p->n && p->ptr[pi + 1]->n > T - 1) { // steal one key from right neighbour - pivot_left(b, p, pi); + pivot_left(b, ppos, p, pi); break; } else if (pi > 0) { - // fprintf(stderr, "LEFT "); assert(p->ptr[pi - 1]->n == T - 1); // merge with left neighbour *lasti += T; x = merge_node(b, p, pi - 1); if (lasti == &itr->i) { // TRICKY: we merged the node the iterator was on - itr->node = x; + itr->x = x; } itr->s[rlvl].i--; itr_dirty = true; } else { - // fprintf(stderr, "RIGHT "); assert(pi < p->n && p->ptr[pi + 1]->n == T - 1); merge_node(b, p, pi); // no iter adjustment needed @@ -408,18 +641,18 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev) itr->lvl--; } if (b->root->level) { - mtnode_t *oldroot = b->root; + MTNode *oldroot = b->root; b->root = b->root->ptr[0]; b->root->parent = NULL; - xfree(oldroot); + marktree_free_node(b, oldroot); } else { // no items, nothing for iterator to point to // not strictly needed, should handle delete right-most mark anyway - itr->node = NULL; + itr->x = NULL; } } - if (itr->node && itr_dirty) { + if (itr->x && itr_dirty) { marktree_itr_fix_pos(b, itr); } @@ -435,18 +668,241 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev) marktree_itr_next(b, itr); marktree_itr_next(b, itr); } else { - if (itr->node && itr->i >= itr->node->n) { + if (itr->x && itr->i >= itr->x->n) { // we deleted the last key of a leaf node // go to the inner key after that. - assert(itr->node->level == 0); + assert(itr->x->level == 0); marktree_itr_next(b, itr); } } + + return other; } -static mtnode_t *merge_node(MarkTree *b, mtnode_t *p, int i) +/// similar to intersect_common but modify x and y in place to retain +/// only the items which are NOT in common +static void intersect_merge(Intersection *restrict m, Intersection *restrict x, + Intersection *restrict y) { - mtnode_t *x = p->ptr[i], *y = p->ptr[i + 1]; + size_t xi = 0, yi = 0; + size_t xn = 0, yn = 0; + while (xi < kv_size(*x) && yi < kv_size(*y)) { + if (kv_A(*x, xi) == kv_A(*y, yi)) { + // TODO(bfredl): kvi_pushp is actually quite complex, break out kvi_resize() to a function? + kvi_push(*m, kv_A(*x, xi)); + xi++; + yi++; + } else if (kv_A(*x, xi) < kv_A(*y, yi)) { + kv_A(*x, xn++) = kv_A(*x, xi++); + } else { + kv_A(*y, yn++) = kv_A(*y, yi++); + } + } + + if (xi < kv_size(*x)) { + memmove(&kv_A(*x, xn), &kv_A(*x, xi), sizeof(kv_A(*x, xn)) * (kv_size(*x) - xi)); + xn += kv_size(*x) - xi; + } + if (yi < kv_size(*y)) { + memmove(&kv_A(*y, yn), &kv_A(*y, yi), sizeof(kv_A(*y, yn)) * (kv_size(*y) - yi)); + yn += kv_size(*y) - yi; + } + + kv_size(*x) = xn; + kv_size(*y) = yn; +} + +// w used to be a child of x but it is now a child of y, adjust intersections accordingly +// @param[out] d are intersections which should be added to the old children of y +static void intersect_mov(Intersection *restrict x, Intersection *restrict y, + Intersection *restrict w, Intersection *restrict d) +{ + size_t wi = 0, yi = 0; + size_t wn = 0, yn = 0; + size_t xi = 0; + while (wi < kv_size(*w) || xi < kv_size(*x)) { + if (wi < kv_size(*w) && (xi >= kv_size(*x) || kv_A(*x, xi) >= kv_A(*w, wi))) { + if (xi < kv_size(*x) && kv_A(*x, xi) == kv_A(*w, wi)) { + xi++; + } + // now w < x strictly + while (yi < kv_size(*y) && kv_A(*y, yi) < kv_A(*w, wi)) { + kvi_push(*d, kv_A(*y, yi)); + yi++; + } + if (yi < kv_size(*y) && kv_A(*y, yi) == kv_A(*w, wi)) { + kv_A(*y, yn++) = kv_A(*y, yi++); + wi++; + } else { + kv_A(*w, wn++) = kv_A(*w, wi++); + } + } else { + // x < w strictly + while (yi < kv_size(*y) && kv_A(*y, yi) < kv_A(*x, xi)) { + kvi_push(*d, kv_A(*y, yi)); + yi++; + } + if (yi < kv_size(*y) && kv_A(*y, yi) == kv_A(*x, xi)) { + kv_A(*y, yn++) = kv_A(*y, yi++); + xi++; + } else { + // add kv_A(x, xi) at kv_A(w, wn), pushing up wi if wi == wn + if (wi == wn) { + size_t n = kv_size(*w) - wn; + kvi_pushp(*w); + if (n > 0) { + memmove(&kv_A(*w, wn + 1), &kv_A(*w, wn), n * sizeof(kv_A(*w, 0))); + } + kv_A(*w, wi) = kv_A(*x, xi); + wn++; + wi++; // no need to consider the added element again + } else { + assert(wn < wi); + kv_A(*w, wn++) = kv_A(*x, xi); + } + xi++; + } + } + } + if (yi < kv_size(*y)) { + // move remaining items to d + size_t n = kv_size(*y) - yi; // at least one + kvi_ensure_more_space(*d, n); + memcpy(&kv_A(*d, kv_size(*d)), &kv_A(*y, yi), n * sizeof(kv_A(*d, 0))); + kv_size(*d) += n; + } + kv_size(*w) = wn; + kv_size(*y) = yn; +} + +bool intersect_mov_test(const uint64_t *x, size_t nx, const uint64_t *y, size_t ny, + const uint64_t *win, size_t nwin, uint64_t *wout, size_t *nwout, + uint64_t *dout, size_t *ndout) +{ + // x is immutable in the context of intersect_mov. y might shrink, but we + // don't care about it (we get it the deleted ones in d) + Intersection xi = { .items = (uint64_t *)x, .size = nx }; + Intersection yi = { .items = (uint64_t *)y, .size = ny }; + + Intersection w; + kvi_init(w); + for (size_t i = 0; i < nwin; i++) { + kvi_push(w, win[i]); + } + Intersection d; + kvi_init(d); + + intersect_mov(&xi, &yi, &w, &d); + + if (w.size > *nwout || d.size > *ndout) { + return false; + } + + memcpy(wout, w.items, sizeof(w.items[0]) * w.size); + *nwout = w.size; + + memcpy(dout, d.items, sizeof(d.items[0]) * d.size); + *ndout = d.size; + + return true; +} + +/// intersection: i = x & y +static void intersect_common(Intersection *i, Intersection *x, Intersection *y) +{ + size_t xi = 0, yi = 0; + while (xi < kv_size(*x) && yi < kv_size(*y)) { + if (kv_A(*x, xi) == kv_A(*y, yi)) { + kvi_push(*i, kv_A(*x, xi)); + xi++; + yi++; + } else if (kv_A(*x, xi) < kv_A(*y, yi)) { + xi++; + } else { + yi++; + } + } +} + +// inplace union: x |= y +static void intersect_add(Intersection *x, Intersection *y) +{ + size_t xi = 0, yi = 0; + while (xi < kv_size(*x) && yi < kv_size(*y)) { + if (kv_A(*x, xi) == kv_A(*y, yi)) { + xi++; + yi++; + } else if (kv_A(*y, yi) < kv_A(*x, xi)) { + size_t n = kv_size(*x) - xi; // at least one + kvi_pushp(*x); + memmove(&kv_A(*x, xi + 1), &kv_A(*x, xi), n * sizeof(kv_A(*x, 0))); + kv_A(*x, xi) = kv_A(*y, yi); + xi++; // newly added element + yi++; + } else { + xi++; + } + } + if (yi < kv_size(*y)) { + size_t n = kv_size(*y) - yi; // at least one + kvi_ensure_more_space(*x, n); + memcpy(&kv_A(*x, kv_size(*x)), &kv_A(*y, yi), n * sizeof(kv_A(*x, 0))); + kv_size(*x) += n; + } +} + +// inplace asymmetric difference: x &= ~y +static void intersect_sub(Intersection *restrict x, Intersection *restrict y) +{ + size_t xi = 0, yi = 0; + size_t xn = 0; + while (xi < kv_size(*x) && yi < kv_size(*y)) { + if (kv_A(*x, xi) == kv_A(*y, yi)) { + xi++; + yi++; + } else if (kv_A(*x, xi) < kv_A(*y, yi)) { + kv_A(*x, xn++) = kv_A(*x, xi++); + } else { + yi++; + } + } + if (xi < kv_size(*x)) { + size_t n = kv_size(*x) - xi; + if (xn < xi) { // otherwise xn == xi + memmove(&kv_A(*x, xn), &kv_A(*x, xi), n * sizeof(kv_A(*x, 0))); + } + xn += n; + } + kv_size(*x) = xn; +} + +/// x is a node which shrunk, or the half of a split +/// +/// this means that intervals which previously intersected all the (current) +/// child nodes, now instead intersects `x` itself. +static void bubble_up(MTNode *x) +{ + Intersection xi; + kvi_init(xi); + // due to invariants, the largest subset of _all_ subnodes is the intersection + // between the first and the last + intersect_common(&xi, &x->ptr[0]->intersect, &x->ptr[x->n]->intersect); + if (kv_size(xi)) { + for (int i = 0; i < x->n + 1; i++) { + intersect_sub(&x->ptr[i]->intersect, &xi); + } + intersect_add(&x->intersect, &xi); + } + kvi_destroy(xi); +} + +static MTNode *merge_node(MarkTree *b, MTNode *p, int i) +{ + MTNode *x = p->ptr[i], *y = p->ptr[i + 1]; + Intersection m; + kvi_init(m); + + intersect_merge(&m, &x->intersect, &y->intersect); x->key[x->n] = p->key[i]; refkey(b, x, x->n); @@ -454,35 +910,78 @@ static mtnode_t *merge_node(MarkTree *b, mtnode_t *p, int i) relative(p->key[i - 1].pos, &x->key[x->n].pos); } - memmove(&x->key[x->n + 1], y->key, (size_t)y->n * sizeof(mtkey_t)); + memmove(&x->key[x->n + 1], y->key, (size_t)y->n * sizeof(MTKey)); for (int k = 0; k < y->n; k++) { refkey(b, x, x->n + 1 + k); unrelative(x->key[x->n].pos, &x->key[x->n + 1 + k].pos); } if (x->level) { - memmove(&x->ptr[x->n + 1], y->ptr, ((size_t)y->n + 1) * sizeof(mtnode_t *)); - for (int k = 0; k < y->n + 1; k++) { - x->ptr[x->n + k + 1]->parent = x; + // bubble down: ranges that intersected old-x but not old-y or vice versa + // must be moved to their respective children + memmove(&x->ptr[x->n + 1], y->ptr, ((size_t)y->n + 1) * sizeof(MTNode *)); + for (int k = 0; k < x->n + 1; k++) { + // TODO(bfredl): dedicated impl for "Z |= Y" + for (size_t idx = 0; idx < kv_size(x->intersect); idx++) { + intersect_node(b, x->ptr[k], kv_A(x->intersect, idx)); + } + } + for (int ky = 0; ky < y->n + 1; ky++) { + int k = x->n + ky + 1; + // nodes that used to be in y, now the second half of x + x->ptr[k]->parent = x; + x->ptr[k]->p_idx = (int16_t)k; + // TODO(bfredl): dedicated impl for "Z |= X" + for (size_t idx = 0; idx < kv_size(y->intersect); idx++) { + intersect_node(b, x->ptr[k], kv_A(y->intersect, idx)); + } } } x->n += y->n + 1; - memmove(&p->key[i], &p->key[i + 1], (size_t)(p->n - i - 1) * sizeof(mtkey_t)); + memmove(&p->key[i], &p->key[i + 1], (size_t)(p->n - i - 1) * sizeof(MTKey)); memmove(&p->ptr[i + 1], &p->ptr[i + 2], - (size_t)(p->n - i - 1) * sizeof(mtkey_t *)); + (size_t)(p->n - i - 1) * sizeof(MTKey *)); + for (int j = i + 1; j < p->n; j++) { // note: one has been deleted + p->ptr[j]->p_idx = (int16_t)j; + } p->n--; - xfree(y); - b->n_nodes--; + marktree_free_node(b, y); + + kvi_destroy(x->intersect); + + // move of a kvec_withinit_t, messy! + // TODO(bfredl): special case version of intersect_merge(x_out, x_in_m_out, y) to avoid this + kvi_move(&x->intersect, &m); + return x; } +/// @param dest is overwritten (assumed to already been freed/moved) +/// @param src consumed (don't free or use) +void kvi_move(Intersection *dest, Intersection *src) +{ + dest->size = src->size; + dest->capacity = src->capacity; + if (src->items == src->init_array) { + memcpy(dest->init_array, src->init_array, src->size * sizeof(*src->init_array)); + dest->items = dest->init_array; + } else { + dest->items = src->items; + } +} + // TODO(bfredl): as a potential "micro" optimization, pivoting should balance // the two nodes instead of stealing just one key -static void pivot_right(MarkTree *b, mtnode_t *p, int i) +// x_pos is the absolute position of the key just before x (or a dummy key strictly less than any +// key inside x, if x is the first leaf) +static void pivot_right(MarkTree *b, MTPos p_pos, MTNode *p, const int i) { - mtnode_t *x = p->ptr[i], *y = p->ptr[i + 1]; - memmove(&y->key[1], y->key, (size_t)y->n * sizeof(mtkey_t)); + MTNode *x = p->ptr[i], *y = p->ptr[i + 1]; + memmove(&y->key[1], y->key, (size_t)y->n * sizeof(MTKey)); if (y->level) { - memmove(&y->ptr[1], y->ptr, ((size_t)y->n + 1) * sizeof(mtnode_t *)); + memmove(&y->ptr[1], y->ptr, ((size_t)y->n + 1) * sizeof(MTNode *)); + for (int j = 1; j < y->n + 2; j++) { + y->ptr[j]->p_idx = (int16_t)j; + } } y->key[0] = p->key[i]; refkey(b, y, 0); @@ -491,6 +990,7 @@ static void pivot_right(MarkTree *b, mtnode_t *p, int i) if (x->level) { y->ptr[0] = x->ptr[x->n]; y->ptr[0]->parent = y; + y->ptr[0]->p_idx = 0; } x->n--; y->n++; @@ -501,11 +1001,46 @@ static void pivot_right(MarkTree *b, mtnode_t *p, int i) for (int k = 1; k < y->n; k++) { unrelative(y->key[0].pos, &y->key[k].pos); } + + // repair intersections of x + if (x->level) { + // handle y and first new y->ptr[0] + Intersection d; + kvi_init(d); + // y->ptr[0] was moved from x to y + // adjust y->ptr[0] for a difference between the parents + // in addition, this might cause some intersection of the old y + // to bubble down to the old children of y (if y->ptr[0] wasn't intersected) + intersect_mov(&x->intersect, &y->intersect, &y->ptr[0]->intersect, &d); + if (kv_size(d)) { + for (int yi = 1; yi < y->n + 1; yi++) { + intersect_add(&y->ptr[yi]->intersect, &d); + } + } + kvi_destroy(d); + + bubble_up(x); + } else { + // if the last element of x used to be an end node, check if it now covers all of x + if (mt_end(p->key[i])) { + uint64_t pi = pseudo_index(x, 0); // note: sloppy pseudo-index + uint64_t start_id = mt_lookup_key_side(p->key[i], false); + uint64_t pi_start = pseudo_index_for_id(b, start_id, true); + if (pi_start > 0 && pi_start < pi) { + intersect_node(b, x, start_id); + } + } + + if (mt_start(y->key[0])) { + // no need for a check, just delet it if it was there + unintersect_node(b, y, mt_lookup_key(y->key[0]), false); + } + } } -static void pivot_left(MarkTree *b, mtnode_t *p, int i) +static void pivot_left(MarkTree *b, MTPos p_pos, MTNode *p, int i) { - mtnode_t *x = p->ptr[i], *y = p->ptr[i + 1]; + MTNode *x = p->ptr[i], *y = p->ptr[i + 1]; // reverse from how we "always" do it. but pivot_left // is just the inverse of pivot_right, so reverse it literally. @@ -524,97 +1059,191 @@ static void pivot_left(MarkTree *b, mtnode_t *p, int i) if (x->level) { x->ptr[x->n + 1] = y->ptr[0]; x->ptr[x->n + 1]->parent = x; + x->ptr[x->n + 1]->p_idx = (int16_t)(x->n + 1); } - memmove(y->key, &y->key[1], (size_t)(y->n - 1) * sizeof(mtkey_t)); + memmove(y->key, &y->key[1], (size_t)(y->n - 1) * sizeof(MTKey)); if (y->level) { - memmove(y->ptr, &y->ptr[1], (size_t)y->n * sizeof(mtnode_t *)); + memmove(y->ptr, &y->ptr[1], (size_t)y->n * sizeof(MTNode *)); + for (int j = 0; j < y->n; j++) { // note: last item deleted + y->ptr[j]->p_idx = (int16_t)j; + } } x->n++; y->n--; + + // repair intersections of x,y + if (x->level) { + // handle y and first new y->ptr[0] + Intersection d; + kvi_init(d); + // x->ptr[x->n] was moved from y to x + // adjust x->ptr[x->n] for a difference between the parents + // in addition, this might cause some intersection of the old x + // to bubble down to the old children of x (if x->ptr[n] wasn't intersected) + intersect_mov(&y->intersect, &x->intersect, &x->ptr[x->n]->intersect, &d); + if (kv_size(d)) { + for (int xi = 0; xi < x->n; xi++) { // ptr[x->n| deliberately skipped + intersect_add(&x->ptr[xi]->intersect, &d); + } + } + kvi_destroy(d); + + bubble_up(y); + } else { + // if the first element of y used to be an start node, check if it now covers all of y + if (mt_start(p->key[i])) { + uint64_t pi = pseudo_index(y, 0); // note: sloppy pseudo-index + + uint64_t end_id = mt_lookup_key_side(p->key[i], true); + uint64_t pi_end = pseudo_index_for_id(b, end_id, true); + + if (pi_end > pi) { + intersect_node(b, y, mt_lookup_key(p->key[i])); + } + } + + if (mt_end(x->key[x->n - 1])) { + // no need for a check, just delet it if it was there + unintersect_node(b, x, mt_lookup_key_side(x->key[x->n - 1], false), false); + } + } } /// frees all mem, resets tree to valid empty state void marktree_clear(MarkTree *b) { if (b->root) { - marktree_free_node(b->root); + marktree_free_subtree(b, b->root); b->root = NULL; } - if (b->id2node->table.keys) { - pmap_destroy(uint64_t)(b->id2node); - pmap_init(uint64_t, b->id2node); - } + map_destroy(uint64_t, b->id2node); + *b->id2node = (PMap(uint64_t)) MAP_INIT; b->n_keys = 0; - b->n_nodes = 0; + assert(b->n_nodes == 0); } -void marktree_free_node(mtnode_t *x) +void marktree_free_subtree(MarkTree *b, MTNode *x) { if (x->level) { for (int i = 0; i < x->n + 1; i++) { - marktree_free_node(x->ptr[i]); + marktree_free_subtree(b, x->ptr[i]); } } - xfree(x); + marktree_free_node(b, x); } -/// NB: caller must check not pair! -void marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level, mtkey_t key) +static void marktree_free_node(MarkTree *b, MTNode *x) { - // 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)(rawkey(itr).flags & (uint16_t) ~MT_FLAG_DECOR_MASK); - rawkey(itr).flags = (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; + kvi_destroy(x->intersect); + xfree(x); + b->n_nodes--; } +/// @param itr iterator is invalid after call void marktree_move(MarkTree *b, MarkTreeIter *itr, int row, int col) { - 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); - key.pos = (mtpos_t){ row, col }; + MTKey key = rawkey(itr); + MTNode *x = itr->x; + if (!x->level) { + bool internal = false; + MTPos newpos = MTPos(row, col); + if (x->parent != NULL) { + // strictly _after_ key before `x` + // (not optimal when x is very first leaf of the entire tree, but that's fine) + if (pos_less(itr->pos, newpos)) { + relative(itr->pos, &newpos); + + // strictly before the end of x. (this could be made sharper by + // finding the internal key just after x, but meh) + if (pos_less(newpos, x->key[x->n - 1].pos)) { + internal = true; + } + } + } else { + // tree is one node. newpos thus is already "relative" itr->pos + internal = true; + } + + if (internal) { + if (key.pos.row == newpos.row && key.pos.col == newpos.col) { + return; + } + key.pos = newpos; + bool match; + // tricky: could minimize movement in either direction better + int new_i = marktree_getp_aux(x, key, &match); + if (!match) { + new_i++; + } + if (new_i == itr->i) { + x->key[itr->i].pos = newpos; + } else if (new_i < itr->i) { + memmove(&x->key[new_i + 1], &x->key[new_i], sizeof(MTKey) * (size_t)(itr->i - new_i)); + x->key[new_i] = key; + } else if (new_i > itr->i) { + memmove(&x->key[itr->i], &x->key[itr->i + 1], sizeof(MTKey) * (size_t)(new_i - itr->i - 1)); + x->key[new_i - 1] = key; + } + return; + } + } + uint64_t other = marktree_del_itr(b, itr, false); + key.pos = (MTPos){ row, col }; marktree_put_key(b, key); - itr->node = NULL; // itr might become invalid by put + + if (other) { + marktree_restore_pair(b, key); + } + itr->x = NULL; // itr might become invalid by put +} + +void marktree_restore_pair(MarkTree *b, MTKey key) +{ + MarkTreeIter itr[1]; + MarkTreeIter end_itr[1]; + marktree_lookup(b, mt_lookup_key_side(key, false), itr); + marktree_lookup(b, mt_lookup_key_side(key, true), end_itr); + if (!itr->x || !end_itr->x) { + // this could happen if the other end is waiting to be restored later + // this function will be called again for the other end. + return; + } + rawkey(itr).flags &= (uint16_t) ~MT_FLAG_ORPHANED; + rawkey(end_itr).flags &= (uint16_t) ~MT_FLAG_ORPHANED; + + marktree_intersect_pair(b, mt_lookup_key_side(key, false), itr, end_itr, false); } // itr functions -// TODO(bfredl): static inline? bool marktree_itr_get(MarkTree *b, int32_t row, int col, MarkTreeIter *itr) { - return marktree_itr_get_ext(b, (mtpos_t){ row, col }, - itr, false, false, NULL); + return marktree_itr_get_ext(b, MTPos(row, col), itr, false, false, NULL); } -bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last, bool gravity, - mtpos_t *oldbase) +bool marktree_itr_get_ext(MarkTree *b, MTPos p, MarkTreeIter *itr, bool last, bool gravity, + MTPos *oldbase) { if (b->n_keys == 0) { - itr->node = NULL; + itr->x = NULL; return false; } - mtkey_t k = { .pos = p, .flags = gravity ? MT_FLAG_RIGHT_GRAVITY : 0 }; + MTKey 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->pos = (MTPos){ 0, 0 }; + itr->x = b->root; itr->lvl = 0; if (oldbase) { oldbase[itr->lvl] = itr->pos; } while (true) { - itr->i = marktree_getp_aux(itr->node, k, 0) + 1; + itr->i = marktree_getp_aux(itr->x, k, 0) + 1; - if (itr->node->level == 0) { + if (itr->x->level == 0) { break; } @@ -622,10 +1251,10 @@ bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last, itr->s[itr->lvl].oldcol = itr->pos.col; if (itr->i > 0) { - compose(&itr->pos, itr->node->key[itr->i - 1].pos); - relative(itr->node->key[itr->i - 1].pos, &k.pos); + compose(&itr->pos, itr->x->key[itr->i - 1].pos); + relative(itr->x->key[itr->i - 1].pos, &k.pos); } - itr->node = itr->node->ptr[itr->i]; + itr->x = itr->x->ptr[itr->i]; itr->lvl++; if (oldbase) { oldbase[itr->lvl] = itr->pos; @@ -634,7 +1263,7 @@ bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last, if (last) { return marktree_itr_prev(b, itr); - } else if (itr->i >= itr->node->n) { + } else if (itr->i >= itr->x->n) { return marktree_itr_next(b, itr); } return true; @@ -642,19 +1271,20 @@ bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last, bool marktree_itr_first(MarkTree *b, MarkTreeIter *itr) { - itr->node = b->root; if (b->n_keys == 0) { + itr->x = NULL; return false; } + itr->x = b->root; itr->i = 0; itr->lvl = 0; - itr->pos = (mtpos_t){ 0, 0 }; - while (itr->node->level > 0) { + itr->pos = MTPos(0, 0); + while (itr->x->level > 0) { itr->s[itr->lvl].i = 0; itr->s[itr->lvl].oldcol = 0; itr->lvl++; - itr->node = itr->node->ptr[0]; + itr->x = itr->x->ptr[0]; } return true; } @@ -663,16 +1293,16 @@ bool marktree_itr_first(MarkTree *b, MarkTreeIter *itr) int marktree_itr_last(MarkTree *b, MarkTreeIter *itr) { if (b->n_keys == 0) { - itr->node = NULL; + itr->x = NULL; return false; } - itr->pos = (mtpos_t){ 0, 0 }; - itr->node = b->root; + itr->pos = MTPos(0, 0); + itr->x = b->root; itr->lvl = 0; while (true) { - itr->i = itr->node->n; + itr->i = itr->x->n; - if (itr->node->level == 0) { + if (itr->x->level == 0) { break; } @@ -680,63 +1310,71 @@ int marktree_itr_last(MarkTree *b, MarkTreeIter *itr) itr->s[itr->lvl].oldcol = itr->pos.col; assert(itr->i > 0); - compose(&itr->pos, itr->node->key[itr->i - 1].pos); + compose(&itr->pos, itr->x->key[itr->i - 1].pos); - itr->node = itr->node->ptr[itr->i]; + itr->x = itr->x->ptr[itr->i]; itr->lvl++; } itr->i--; return true; } -// TODO(bfredl): static inline bool marktree_itr_next(MarkTree *b, MarkTreeIter *itr) { - return marktree_itr_next_skip(b, itr, false, NULL); + return marktree_itr_next_skip(b, itr, false, false, NULL); } -static bool marktree_itr_next_skip(MarkTree *b, MarkTreeIter *itr, bool skip, mtpos_t oldbase[]) +static bool marktree_itr_next_skip(MarkTree *b, MarkTreeIter *itr, bool skip, bool preload, + MTPos oldbase[]) { - if (!itr->node) { + if (!itr->x) { return false; } itr->i++; - if (itr->node->level == 0 || skip) { - if (itr->i < itr->node->n) { + if (itr->x->level == 0 || skip) { + if (preload && itr->x->level == 0 && skip) { + // skip rest of this leaf node + itr->i = itr->x->n; + } else if (itr->i < itr->x->n) { // TODO(bfredl): this is the common case, // and could be handled by inline wrapper return true; } // we ran out of non-internal keys. Go up until we find an internal key - while (itr->i >= itr->node->n) { - itr->node = itr->node->parent; - if (itr->node == NULL) { + while (itr->i >= itr->x->n) { + itr->x = itr->x->parent; + if (itr->x == NULL) { return false; } itr->lvl--; itr->i = itr->s[itr->lvl].i; if (itr->i > 0) { - itr->pos.row -= itr->node->key[itr->i - 1].pos.row; + itr->pos.row -= itr->x->key[itr->i - 1].pos.row; itr->pos.col = itr->s[itr->lvl].oldcol; } } } else { // we stood at an "internal" key. Go down to the first non-internal // key after it. - while (itr->node->level > 0) { + while (itr->x->level > 0) { // internal key, there is always a child after if (itr->i > 0) { itr->s[itr->lvl].oldcol = itr->pos.col; - compose(&itr->pos, itr->node->key[itr->i - 1].pos); + compose(&itr->pos, itr->x->key[itr->i - 1].pos); } if (oldbase && itr->i == 0) { oldbase[itr->lvl + 1] = oldbase[itr->lvl]; } itr->s[itr->lvl].i = itr->i; - assert(itr->node->ptr[itr->i]->parent == itr->node); - itr->node = itr->node->ptr[itr->i]; - itr->i = 0; + assert(itr->x->ptr[itr->i]->parent == itr->x); itr->lvl++; + itr->x = itr->x->ptr[itr->i]; + if (preload && itr->x->level) { + itr->i = -1; + break; + } else { + itr->i = 0; + } } } return true; @@ -744,10 +1382,10 @@ static bool marktree_itr_next_skip(MarkTree *b, MarkTreeIter *itr, bool skip, mt bool marktree_itr_prev(MarkTree *b, MarkTreeIter *itr) { - if (!itr->node) { + if (!itr->x) { return false; } - if (itr->node->level == 0) { + if (itr->x->level == 0) { itr->i--; if (itr->i >= 0) { // TODO(bfredl): this is the common case, @@ -756,30 +1394,30 @@ bool marktree_itr_prev(MarkTree *b, MarkTreeIter *itr) } // we ran out of non-internal keys. Go up until we find a non-internal key while (itr->i < 0) { - itr->node = itr->node->parent; - if (itr->node == NULL) { + itr->x = itr->x->parent; + if (itr->x == NULL) { return false; } itr->lvl--; itr->i = itr->s[itr->lvl].i - 1; if (itr->i >= 0) { - itr->pos.row -= itr->node->key[itr->i].pos.row; + itr->pos.row -= itr->x->key[itr->i].pos.row; itr->pos.col = itr->s[itr->lvl].oldcol; } } } else { // we stood at an "internal" key. Go down to the last non-internal // key before it. - while (itr->node->level > 0) { + while (itr->x->level > 0) { // internal key, there is always a child before if (itr->i > 0) { itr->s[itr->lvl].oldcol = itr->pos.col; - compose(&itr->pos, itr->node->key[itr->i - 1].pos); + compose(&itr->pos, itr->x->key[itr->i - 1].pos); } itr->s[itr->lvl].i = itr->i; - assert(itr->node->ptr[itr->i]->parent == itr->node); - itr->node = itr->node->ptr[itr->i]; - itr->i = itr->node->n; + assert(itr->x->ptr[itr->i]->parent == itr->x); + itr->x = itr->x->ptr[itr->i]; + itr->i = itr->x->n; itr->lvl++; } itr->i--; @@ -787,33 +1425,22 @@ bool marktree_itr_prev(MarkTree *b, MarkTreeIter *itr) return true; } -void marktree_itr_rewind(MarkTree *b, MarkTreeIter *itr) -{ - if (!itr->node) { - return; - } - if (itr->node->level) { - marktree_itr_prev(b, itr); - } - itr->i = 0; -} - bool marktree_itr_node_done(MarkTreeIter *itr) { - return !itr->node || itr->i == itr->node->n - 1; + return !itr->x || itr->i == itr->x->n - 1; } -mtpos_t marktree_itr_pos(MarkTreeIter *itr) +MTPos marktree_itr_pos(MarkTreeIter *itr) { - mtpos_t pos = rawkey(itr).pos; + MTPos pos = rawkey(itr).pos; unrelative(itr->pos, &pos); return pos; } -mtkey_t marktree_itr_current(MarkTreeIter *itr) +MTKey marktree_itr_current(MarkTreeIter *itr) { - if (itr->node) { - mtkey_t key = rawkey(itr); + if (itr->x) { + MTKey key = rawkey(itr); key.pos = marktree_itr_pos(itr); return key; } @@ -825,47 +1452,193 @@ static bool itr_eq(MarkTreeIter *itr1, MarkTreeIter *itr2) return (&rawkey(itr1) == &rawkey(itr2)); } -static void itr_swap(MarkTreeIter *itr1, MarkTreeIter *itr2) +/// Get all marks which overlaps the position (row,col) +/// +/// After calling this function, use marktree_itr_step_overlap to step through +/// one overlapping mark at a time, until it returns false +/// +/// NOTE: It's possible to get all marks which overlaps a region (row,col) to (row_end,col_end) +/// To do this, first call marktree_itr_get_overlap with the start position and +/// keep calling marktree_itr_step_overlap until it returns false. +/// After this, as a second loop, keep calling the marktree_itr_next() until +/// the iterator is invalid or reaches past (row_end, col_end). In this loop, +/// consider all "start" marks (and unpaired marks if relevant), but skip over +/// all "end" marks, using mt_end(mark). +/// +/// @return false if we already know no marks can be found +/// even if "true" the first call to marktree_itr_step_overlap +/// could return false +bool marktree_itr_get_overlap(MarkTree *b, int row, int col, MarkTreeIter *itr) +{ + if (b->n_keys == 0) { + itr->x = NULL; + return false; + } + + itr->x = b->root; + itr->i = -1; + itr->lvl = 0; + itr->pos = MTPos(0, 0); + itr->intersect_pos = MTPos(row, col); + // intersect_pos but will be adjusted relative itr->x + itr->intersect_pos_x = MTPos(row, col); + itr->intersect_idx = 0; + return true; +} + +/// Step through all overlapping pairs at a position. +/// +/// This function must only be used with an iterator from |marktree_itr_step_overlap| +/// +/// @return true if a valid pair was found (returned as `pair`) +/// When all overlapping mark pairs have been found, false will be returned. `itr` +/// is then valid as an ordinary iterator at the (row, col) position specified in +/// marktree_itr_step_overlap +bool marktree_itr_step_overlap(MarkTree *b, MarkTreeIter *itr, MTPair *pair) +{ + // phase one: we start at the root node and step inwards towards itr->intersect_pos + // (the position queried in marktree_itr_get_overlap) + // + // For each node (ancestor node to the node containing the sought position) + // we return all intersecting intervals, one at a time + while (itr->i == -1) { + if (itr->intersect_idx < kv_size(itr->x->intersect)) { + uint64_t id = kv_A(itr->x->intersect, itr->intersect_idx++); + *pair = mtpair_from(marktree_lookup(b, id, NULL), + marktree_lookup(b, id|MARKTREE_END_FLAG, NULL)); + return true; + } + + if (itr->x->level == 0) { + itr->s[itr->lvl].i = itr->i = 0; + break; + } + + MTKey k = { .pos = itr->intersect_pos_x, .flags = 0 }; + itr->i = marktree_getp_aux(itr->x, k, 0) + 1; + + itr->s[itr->lvl].i = itr->i; + itr->s[itr->lvl].oldcol = itr->pos.col; + + if (itr->i > 0) { + compose(&itr->pos, itr->x->key[itr->i - 1].pos); + relative(itr->x->key[itr->i - 1].pos, &itr->intersect_pos_x); + } + itr->x = itr->x->ptr[itr->i]; + itr->lvl++; + itr->i = -1; + itr->intersect_idx = 0; + } + + // phase two: we now need to handle the node found at itr->intersect_pos + // first consider all start nodes in the node before this position. + while (itr->i < itr->x->n && pos_less(rawkey(itr).pos, itr->intersect_pos_x)) { + MTKey k = itr->x->key[itr->i++]; + itr->s[itr->lvl].i = itr->i; + if (mt_start(k)) { + MTKey end = marktree_lookup(b, mt_lookup_id(k.ns, k.id, true), NULL); + if (pos_less(end.pos, itr->intersect_pos)) { + continue; + } + + unrelative(itr->pos, &k.pos); + *pair = mtpair_from(k, end); + return true; // it's a start! + } + } + + // phase 2B: We also need to step to the end of this node and consider all end marks, which + // might end an interval overlapping itr->intersect_pos + while (itr->i < itr->x->n) { + MTKey k = itr->x->key[itr->i++]; + if (mt_end(k)) { + uint64_t id = mt_lookup_id(k.ns, k.id, false); + if (id2node(b, id) == itr->x) { + continue; + } + unrelative(itr->pos, &k.pos); + MTKey start = marktree_lookup(b, id, NULL); + if (pos_less(itr->intersect_pos, start.pos)) { + continue; + } + *pair = mtpair_from(start, k); + return true; // end of a range which began before us! + } + } + + // when returning false, get back to the queried position, to ensure the caller + // can keep using it as an ordinary iterator at the queried position. The docstring + // for marktree_itr_get_overlap explains how this is useful. + itr->i = itr->s[itr->lvl].i; + assert(itr->i >= 0); + if (itr->i >= itr->x->n) { + marktree_itr_next(b, itr); + } + + // either on or after the intersected position, bail out + return false; +} + +static void swap_keys(MarkTree *b, MarkTreeIter *itr1, MarkTreeIter *itr2, DamageList *damage) { - mtkey_t key1 = rawkey(itr1); - mtkey_t key2 = rawkey(itr2); + if (itr1->x != itr2->x) { + if (mt_paired(rawkey(itr1))) { + kvi_push(*damage, ((Damage){ mt_lookup_key(rawkey(itr1)), itr1->x, itr2->x, + itr1->i, itr2->i })); + } + if (mt_paired(rawkey(itr2))) { + kvi_push(*damage, ((Damage){ mt_lookup_key(rawkey(itr2)), itr2->x, itr1->x, + itr2->i, itr1->i })); + } + } + + MTKey key1 = rawkey(itr1); + MTKey key2 = rawkey(itr2); rawkey(itr1) = key2; rawkey(itr1).pos = key1.pos; rawkey(itr2) = key1; rawkey(itr2).pos = key2.pos; + refkey(b, itr1->x, itr1->i); + refkey(b, itr2->x, itr2->i); +} + +static int damage_cmp(const void *s1, const void *s2) +{ + Damage *d1 = (Damage *)s1, *d2 = (Damage *)s2; + assert(d1->id != d2->id); + return d1->id > d2->id ? 1 : -1; } bool marktree_splice(MarkTree *b, int32_t start_line, int start_col, int old_extent_line, int old_extent_col, int new_extent_line, int new_extent_col) { - mtpos_t start = { start_line, start_col }; - mtpos_t old_extent = { old_extent_line, old_extent_col }; - mtpos_t new_extent = { new_extent_line, new_extent_col }; + MTPos start = { start_line, start_col }; + MTPos old_extent = { old_extent_line, old_extent_col }; + MTPos new_extent = { new_extent_line, new_extent_col }; bool may_delete = (old_extent.row != 0 || old_extent.col != 0); bool same_line = old_extent.row == 0 && new_extent.row == 0; unrelative(start, &old_extent); unrelative(start, &new_extent); - MarkTreeIter itr[1] = { 0 }; - MarkTreeIter enditr[1] = { 0 }; + MarkTreeIter itr[1] = { 0 }, enditr[1] = { 0 }; - mtpos_t oldbase[MT_MAX_DEPTH] = { 0 }; + MTPos oldbase[MT_MAX_DEPTH] = { 0 }; marktree_itr_get_ext(b, start, itr, false, true, oldbase); - if (!itr->node) { + if (!itr->x) { // den e FÄRDIG return false; } - mtpos_t delta = { new_extent.row - old_extent.row, - new_extent.col - old_extent.col }; + MTPos delta = { new_extent.row - old_extent.row, + new_extent.col - old_extent.col }; if (may_delete) { - mtpos_t ipos = marktree_itr_pos(itr); + MTPos ipos = marktree_itr_pos(itr); if (!pos_leq(old_extent, ipos) || (old_extent.row == ipos.row && old_extent.col == ipos.col && !mt_right(rawkey(itr)))) { marktree_itr_get_ext(b, old_extent, enditr, true, true, NULL); - assert(enditr->node); + assert(enditr->x); // "assert" (itr <= enditr) } else { may_delete = false; @@ -874,14 +1647,16 @@ bool marktree_splice(MarkTree *b, int32_t start_line, int start_col, int old_ext bool past_right = false; bool moved = false; + DamageList damage; + kvi_init(damage); // Follow the general strategy of messing things up and fix them later // "oldbase" carries the information needed to calculate old position of // children. if (may_delete) { - while (itr->node && !past_right) { - mtpos_t loc_start = start; - mtpos_t loc_old = old_extent; + while (itr->x && !past_right) { + MTPos loc_start = start; + MTPos loc_old = old_extent; relative(itr->pos, &loc_start); relative(oldbase[itr->lvl], &loc_old); @@ -899,9 +1674,7 @@ continue_same_node: marktree_itr_prev(b, enditr); } if (!mt_right(rawkey(enditr))) { - itr_swap(itr, enditr); - refkey(b, itr->node, itr->i); - refkey(b, enditr->node, enditr->i); + swap_keys(b, itr, enditr, &damage); } else { past_right = true; // NOLINT (void)past_right; @@ -915,14 +1688,14 @@ continue_same_node: } moved = true; - if (itr->node->level) { + if (itr->x->level) { oldbase[itr->lvl + 1] = rawkey(itr).pos; unrelative(oldbase[itr->lvl], &oldbase[itr->lvl + 1]); rawkey(itr).pos = loc_start; - marktree_itr_next_skip(b, itr, false, oldbase); + marktree_itr_next_skip(b, itr, false, false, oldbase); } else { rawkey(itr).pos = loc_start; - if (itr->i < itr->node->n - 1) { + if (itr->i < itr->x->n - 1) { itr->i++; if (!past_right) { goto continue_same_node; @@ -932,10 +1705,10 @@ continue_same_node: } } } - while (itr->node) { - mtpos_t loc_new = new_extent; + while (itr->x) { + MTPos loc_new = new_extent; relative(itr->pos, &loc_new); - mtpos_t limit = old_extent; + MTPos limit = old_extent; relative(oldbase[itr->lvl], &limit); @@ -945,16 +1718,16 @@ past_continue_same_node: break; } - mtpos_t oldpos = rawkey(itr).pos; + MTPos oldpos = rawkey(itr).pos; rawkey(itr).pos = loc_new; moved = true; - if (itr->node->level) { + if (itr->x->level) { oldbase[itr->lvl + 1] = oldpos; unrelative(oldbase[itr->lvl], &oldbase[itr->lvl + 1]); - marktree_itr_next_skip(b, itr, false, oldbase); + marktree_itr_next_skip(b, itr, false, false, oldbase); } else { - if (itr->i < itr->node->n - 1) { + if (itr->i < itr->x->n - 1) { itr->i++; goto past_continue_same_node; } else { @@ -964,7 +1737,7 @@ past_continue_same_node: } } - while (itr->node) { + while (itr->x) { unrelative(oldbase[itr->lvl], &rawkey(itr).pos); int realrow = rawkey(itr).pos.row; assert(realrow >= old_extent.row); @@ -972,7 +1745,6 @@ past_continue_same_node: if (realrow == old_extent.row) { if (delta.col) { rawkey(itr).pos.col += delta.col; - moved = true; } } else { if (same_line) { @@ -988,22 +1760,79 @@ past_continue_same_node: if (done) { break; } - marktree_itr_next_skip(b, itr, true, NULL); + marktree_itr_next_skip(b, itr, true, false, NULL); + } + + if (kv_size(damage)) { + // TODO(bfredl): a full sort is not really needed. we just need a "start" node to find + // its corresponding "end" node. Set up some dedicated hash for this later (c.f. the + // "grow only" variant of khash_t branch) + qsort((void *)&kv_A(damage, 0), kv_size(damage), sizeof(kv_A(damage, 0)), + damage_cmp); + + for (size_t i = 0; i < kv_size(damage); i++) { + Damage d = kv_A(damage, i); + assert(i == 0 || d.id > kv_A(damage, i - 1).id); + if (!(d.id & MARKTREE_END_FLAG)) { // start + if (i + 1 < kv_size(damage) && kv_A(damage, i + 1).id == (d.id | MARKTREE_END_FLAG)) { + Damage d2 = kv_A(damage, i + 1); + + // pair + marktree_itr_set_node(b, itr, d.old, d.old_i); + marktree_itr_set_node(b, enditr, d2.old, d2.old_i); + marktree_intersect_pair(b, d.id, itr, enditr, true); + marktree_itr_set_node(b, itr, d.new, d.new_i); + marktree_itr_set_node(b, enditr, d2.new, d2.new_i); + marktree_intersect_pair(b, d.id, itr, enditr, false); + + i++; // consume two items + continue; + } + + // d is lone start, end didn't move + MarkTreeIter endpos[1]; + marktree_lookup(b, d.id | MARKTREE_END_FLAG, endpos); + if (endpos->x) { + marktree_itr_set_node(b, itr, d.old, d.old_i); + *enditr = *endpos; + marktree_intersect_pair(b, d.id, itr, enditr, true); + marktree_itr_set_node(b, itr, d.new, d.new_i); + *enditr = *endpos; + marktree_intersect_pair(b, d.id, itr, enditr, false); + } + } else { + // d is lone end, start didn't move + MarkTreeIter startpos[1]; + uint64_t start_id = d.id & ~MARKTREE_END_FLAG; + + marktree_lookup(b, start_id, startpos); + if (startpos->x) { + *itr = *startpos; + marktree_itr_set_node(b, enditr, d.old, d.old_i); + marktree_intersect_pair(b, start_id, itr, enditr, true); + *itr = *startpos; + marktree_itr_set_node(b, enditr, d.new, d.new_i); + marktree_intersect_pair(b, start_id, itr, enditr, false); + } + } + } } + kvi_destroy(damage); + return moved; } void marktree_move_region(MarkTree *b, int start_row, colnr_T start_col, int extent_row, colnr_T extent_col, int new_row, colnr_T new_col) { - mtpos_t start = { start_row, start_col }, size = { extent_row, extent_col }; - mtpos_t end = size; + MTPos start = { start_row, start_col }, size = { extent_row, extent_col }; + MTPos end = size; unrelative(start, &end); MarkTreeIter itr[1] = { 0 }; marktree_itr_get_ext(b, start, itr, false, true, NULL); - kvec_t(mtkey_t) saved = KV_INITIAL_VALUE; - while (itr->node) { - mtkey_t k = marktree_itr_current(itr); + kvec_t(MTKey) saved = KV_INITIAL_VALUE; + while (itr->x) { + MTKey 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; @@ -1014,57 +1843,101 @@ void marktree_move_region(MarkTree *b, int start_row, colnr_T start_col, int ext } marktree_splice(b, start.row, start.col, size.row, size.col, 0, 0); - mtpos_t new = { new_row, new_col }; + MTPos new = { new_row, new_col }; marktree_splice(b, new.row, new.col, 0, 0, size.row, size.col); for (size_t i = 0; i < kv_size(saved); i++) { - mtkey_t item = kv_A(saved, i); + MTKey item = kv_A(saved, i); unrelative(new, &item.pos); marktree_put_key(b, item); + if (mt_paired(item)) { + // other end might be later in `saved`, this will safely bail out then + marktree_restore_pair(b, item); + } } kv_destroy(saved); } /// @param itr OPTIONAL. set itr to pos. -mtkey_t marktree_lookup_ns(MarkTree *b, uint32_t ns, uint32_t id, bool end, MarkTreeIter *itr) +MTKey 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); } +static uint64_t pseudo_index(MTNode *x, int i) +{ + int off = MT_LOG2_BRANCH * x->level; + uint64_t index = 0; + + while (x) { + index |= (uint64_t)(i + 1) << off; + off += MT_LOG2_BRANCH; + i = x->p_idx; + x = x->parent; + } + + return index; +} + +/// @param itr OPTIONAL. set itr to pos. +/// if sloppy, two keys at the same _leaf_ node has the same index +static uint64_t pseudo_index_for_id(MarkTree *b, uint64_t id, bool sloppy) +{ + MTNode *n = id2node(b, id); + if (n == NULL) { + return 0; // a valid pseudo-index is never zero! + } + + int i = 0; + if (n->level || !sloppy) { + for (i = 0; i < n->n; i++) { + if (mt_lookup_key(n->key[i]) == id) { + break; + } + } + assert(i < n->n); + if (n->level) { + i += 1; // internal key i comes after ptr[i] + } + } + + return pseudo_index(n, i); +} + /// @param itr OPTIONAL. set itr to pos. -mtkey_t marktree_lookup(MarkTree *b, uint64_t id, MarkTreeIter *itr) +MTKey marktree_lookup(MarkTree *b, uint64_t id, MarkTreeIter *itr) { - mtnode_t *n = pmap_get(uint64_t)(b->id2node, id); + MTNode *n = id2node(b, id); if (n == NULL) { if (itr) { - itr->node = NULL; + itr->x = NULL; } return MT_INVALID_KEY; } int i = 0; for (i = 0; i < n->n; i++) { if (mt_lookup_key(n->key[i]) == id) { - goto found; + return marktree_itr_set_node(b, itr, n, i); } } + abort(); -found: {} - mtkey_t key = n->key[i]; +} + +MTKey marktree_itr_set_node(MarkTree *b, MarkTreeIter *itr, MTNode *n, int i) +{ + MTKey key = n->key[i]; if (itr) { itr->i = i; - itr->node = n; + itr->x = n; itr->lvl = b->root->level - n->level; } while (n->parent != NULL) { - mtnode_t *p = n->parent; - for (i = 0; i < p->n + 1; i++) { - if (p->ptr[i] == n) { - goto found_node; - } - } - abort(); -found_node: + MTNode *p = n->parent; + i = n->p_idx; + assert(p->ptr[i] == n); + if (itr) { itr->s[b->root->level - p->level].i = i; } @@ -1079,14 +1952,14 @@ found_node: return key; } -mtpos_t marktree_get_altpos(MarkTree *b, mtkey_t mark, MarkTreeIter *itr) +MTPos marktree_get_altpos(MarkTree *b, MTKey mark, MarkTreeIter *itr) { return marktree_get_alt(b, mark, itr).pos; } -mtkey_t marktree_get_alt(MarkTree *b, mtkey_t mark, MarkTreeIter *itr) +MTKey marktree_get_alt(MarkTree *b, MTKey mark, MarkTreeIter *itr) { - mtkey_t end = MT_INVALID_KEY; + MTKey end = MT_INVALID_KEY; if (mt_paired(mark)) { end = marktree_lookup_ns(b, mark.ns, mark.id, !mt_end(mark), itr); } @@ -1095,8 +1968,8 @@ mtkey_t marktree_get_alt(MarkTree *b, mtkey_t mark, MarkTreeIter *itr) static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr) { - itr->pos = (mtpos_t){ 0, 0 }; - mtnode_t *x = b->root; + itr->pos = (MTPos){ 0, 0 }; + MTNode *x = b->root; for (int lvl = 0; lvl < itr->lvl; lvl++) { itr->s[lvl].oldcol = itr->pos.col; int i = itr->s[lvl].i; @@ -1106,23 +1979,36 @@ static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr) assert(x->level); x = x->ptr[i]; } - assert(x == itr->node); + assert(x == itr->x); } // for unit test -void marktree_put_test(MarkTree *b, uint32_t id, int row, int col, bool right_gravity) +void marktree_put_test(MarkTree *b, uint32_t ns, uint32_t id, int row, int col, bool right_gravity, + int end_row, int end_col, bool end_right) { - mtkey_t key = { { row, col }, UINT32_MAX, id, 0, - mt_flags(right_gravity, 0), 0, NULL }; - marktree_put(b, key, -1, -1, false); + uint16_t flags = mt_flags(right_gravity, false, false, false); + MTKey key = { { row, col }, ns, id, flags, { .hl = DECOR_HIGHLIGHT_INLINE_INIT } }; + marktree_put(b, key, end_row, end_col, end_right); } // for unit test -bool mt_right_test(mtkey_t key) +bool mt_right_test(MTKey key) { return mt_right(key); } +// for unit test +void marktree_del_pair_test(MarkTree *b, uint32_t ns, uint32_t id) +{ + MarkTreeIter itr[1]; + marktree_lookup_ns(b, ns, id, false, itr); + + uint64_t other = marktree_del_itr(b, itr, false); + assert(other); + marktree_lookup(b, other, itr); + marktree_del_itr(b, itr, false); +} + void marktree_check(MarkTree *b) { #ifndef NDEBUG @@ -1133,9 +2019,9 @@ void marktree_check(MarkTree *b) return; } - mtpos_t dummy; + MTPos dummy; bool last_right = false; - size_t nkeys = check_node(b, b->root, &dummy, &last_right); + size_t nkeys = marktree_check_node(b, b->root, &dummy, &last_right); assert(b->n_keys == nkeys); assert(b->n_keys == map_size(b->id2node)); #else @@ -1145,7 +2031,7 @@ void marktree_check(MarkTree *b) } #ifndef NDEBUG -static size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_right) +size_t marktree_check_node(MarkTree *b, MTNode *x, MTPos *last, bool *last_right) { assert(x->n <= 2 * T - 1); // TODO(bfredl): too strict if checking "in repair" post-delete tree. @@ -1154,9 +2040,9 @@ static size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_rig for (int i = 0; i < x->n; i++) { if (x->level) { - n_keys += check_node(b, x->ptr[i], last, last_right); + n_keys += marktree_check_node(b, x->ptr[i], last, last_right); } else { - *last = (mtpos_t) { 0, 0 }; + *last = (MTPos) { 0, 0 }; } if (i > 0) { unrelative(x->key[i - 1].pos, last); @@ -1171,50 +2057,238 @@ static size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_rig } if (x->level) { - n_keys += check_node(b, x->ptr[x->n], last, last_right); + n_keys += marktree_check_node(b, x->ptr[x->n], last, last_right); unrelative(x->key[x->n - 1].pos, last); for (int i = 0; i < x->n + 1; i++) { assert(x->ptr[i]->parent == x); + assert(x->ptr[i]->p_idx == i); assert(x->ptr[i]->level == x->level - 1); // PARANOIA: check no double node ref for (int j = 0; j < i; j++) { assert(x->ptr[i] != x->ptr[j]); } } - } else { + } else if (x->n > 0) { *last = x->key[x->n - 1].pos; } return n_keys; } + +bool marktree_check_intersections(MarkTree *b) +{ + if (!b->root) { + return true; + } + PMap(ptr_t) checked = MAP_INIT; + + // 1. move x->intersect to checked[x] and reinit x->intersect + mt_recurse_nodes(b->root, &checked); + + // 2. iterate over all marks. for each START mark of a pair, + // intersect the nodes between the pair + MarkTreeIter itr[1]; + marktree_itr_first(b, itr); + while (true) { + MTKey mark = marktree_itr_current(itr); + if (mark.pos.row < 0) { + break; + } + + if (mt_start(mark)) { + MarkTreeIter start_itr[1]; + MarkTreeIter end_itr[1]; + uint64_t end_id = mt_lookup_id(mark.ns, mark.id, true); + MTKey k = marktree_lookup(b, end_id, end_itr); + if (k.pos.row >= 0) { + *start_itr = *itr; + marktree_intersect_pair(b, mt_lookup_key(mark), start_itr, end_itr, false); + } + } + + marktree_itr_next(b, itr); + } + + // 3. for each node check if the recreated intersection + // matches the old checked[x] intersection. + bool status = mt_recurse_nodes_compare(b->root, &checked); + + uint64_t *val; + map_foreach_value(&checked, val, { + xfree(val); + }); + map_destroy(ptr_t, &checked); + + return status; +} + +void mt_recurse_nodes(MTNode *x, PMap(ptr_t) *checked) +{ + if (kv_size(x->intersect)) { + kvi_push(x->intersect, (uint64_t)-1); // sentinel + uint64_t *val; + if (x->intersect.items == x->intersect.init_array) { + val = xmemdup(x->intersect.items, x->intersect.size * sizeof(*x->intersect.items)); + } else { + val = x->intersect.items; + } + pmap_put(ptr_t)(checked, x, val); + kvi_init(x->intersect); + } + + if (x->level) { + for (int i = 0; i < x->n + 1; i++) { + mt_recurse_nodes(x->ptr[i], checked); + } + } +} + +bool mt_recurse_nodes_compare(MTNode *x, PMap(ptr_t) *checked) +{ + uint64_t *ref = pmap_get(ptr_t)(checked, x); + if (ref != NULL) { + for (size_t i = 0;; i++) { + if (ref[i] == (uint64_t)-1) { + if (i != kv_size(x->intersect)) { + return false; + } + + break; + } else { + if (kv_size(x->intersect) <= i || ref[i] != kv_A(x->intersect, i)) { + return false; + } + } + } + } else { + if (kv_size(x->intersect)) { + return false; + } + } + + if (x->level) { + for (int i = 0; i < x->n + 1; i++) { + if (!mt_recurse_nodes_compare(x->ptr[i], checked)) { + return false; + } + } + } + + return true; +} + #endif -char *mt_inspect_rec(MarkTree *b) +// TODO(bfredl): kv_print +#define GA_PUT(x) ga_concat(ga, (char *)(x)) +#define GA_PRINT(fmt, ...) snprintf(buf, sizeof(buf), fmt, __VA_ARGS__); \ + GA_PUT(buf); + +String mt_inspect(MarkTree *b, bool keys, bool dot) { - garray_T ga; - ga_init(&ga, (int)sizeof(char), 80); - mtpos_t p = { 0, 0 }; - mt_inspect_node(b, &ga, b->root, p); - return ga.ga_data; + garray_T ga[1]; + ga_init(ga, (int)sizeof(char), 80); + MTPos p = { 0, 0 }; + if (b->root) { + if (dot) { + GA_PUT("digraph D {\n\n"); + mt_inspect_dotfile_node(b, ga, b->root, p, NULL); + GA_PUT("\n}"); + } else { + mt_inspect_node(b, ga, keys, b->root, p); + } + } + return ga_take_string(ga); } -void mt_inspect_node(MarkTree *b, garray_T *ga, mtnode_t *n, mtpos_t off) +void mt_inspect_node(MarkTree *b, garray_T *ga, bool keys, MTNode *n, MTPos off) { static char buf[1024]; - ga_concat(ga, "["); + GA_PUT("["); + if (keys && kv_size(n->intersect)) { + for (size_t i = 0; i < kv_size(n->intersect); i++) { + GA_PUT(i == 0 ? "{" : ";"); + // GA_PRINT("%"PRIu64, kv_A(n->intersect, i)); + GA_PRINT("%" PRIu64, mt_dbg_id(kv_A(n->intersect, i))); + } + GA_PUT("},"); + } if (n->level) { - mt_inspect_node(b, ga, n->ptr[0], off); + mt_inspect_node(b, ga, keys, n->ptr[0], off); } for (int i = 0; i < n->n; i++) { - mtpos_t p = n->key[i].pos; + MTPos p = n->key[i].pos; unrelative(off, &p); - snprintf((char *)buf, sizeof(buf), "%d/%d", p.row, p.col); - ga_concat(ga, buf); + GA_PRINT("%d/%d", p.row, p.col); + if (keys) { + MTKey key = n->key[i]; + GA_PUT(":"); + if (mt_start(key)) { + GA_PUT("<"); + } + // GA_PRINT("%"PRIu64, mt_lookup_id(key.ns, key.id, false)); + GA_PRINT("%" PRIu32, key.id); + if (mt_end(key)) { + GA_PUT(">"); + } + } if (n->level) { - mt_inspect_node(b, ga, n->ptr[i + 1], p); + mt_inspect_node(b, ga, keys, n->ptr[i + 1], p); } else { ga_concat(ga, ","); } } ga_concat(ga, "]"); } + +void mt_inspect_dotfile_node(MarkTree *b, garray_T *ga, MTNode *n, MTPos off, char *parent) +{ + static char buf[1024]; + char namebuf[64]; + if (parent != NULL) { + snprintf(namebuf, sizeof namebuf, "%s_%c%d", parent, 'a' + n->level, n->p_idx); + } else { + snprintf(namebuf, sizeof namebuf, "MTNode"); + } + + GA_PRINT(" %s[shape=plaintext, label=<\n", namebuf); + GA_PUT(" <table border='0' cellborder='1' cellspacing='0'>\n"); + if (kv_size(n->intersect)) { + GA_PUT(" <tr><td>"); + for (size_t i = 0; i < kv_size(n->intersect); i++) { + if (i > 0) { + GA_PUT(", "); + } + GA_PRINT("%" PRIu64, mt_dbg_id(kv_A(n->intersect, i))); + } + GA_PUT("</td></tr>\n"); + } + + GA_PUT(" <tr><td>"); + for (int i = 0; i < n->n; i++) { + MTKey k = n->key[i]; + if (i > 0) { + GA_PUT(", "); + } + GA_PRINT("%d", k.id); + if (mt_paired(k)) { + GA_PUT(mt_end(k) ? "e" : "s"); + } + } + GA_PUT("</td></tr>\n"); + GA_PUT(" </table>\n"); + GA_PUT(">];\n"); + if (parent) { + GA_PRINT(" %s -> %s\n", parent, namebuf); + } + if (n->level) { + mt_inspect_dotfile_node(b, ga, n->ptr[0], off, namebuf); + } + for (int i = 0; i < n->n; i++) { + MTPos p = n->key[i].pos; + unrelative(off, &p); + if (n->level) { + mt_inspect_dotfile_node(b, ga, n->ptr[i + 1], p, namebuf); + } + } +} |