From 0b6b03c47211dc45dda03d047c24925edbdbf099 Mon Sep 17 00:00:00 2001 From: timeyyy Date: Thu, 28 Jul 2016 16:30:26 +0200 Subject: kbtree.h --- src/nvim/lib/kbtree.h | 423 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 423 insertions(+) create mode 100644 src/nvim/lib/kbtree.h (limited to 'src') diff --git a/src/nvim/lib/kbtree.h b/src/nvim/lib/kbtree.h new file mode 100644 index 0000000000..b58c3f97a4 --- /dev/null +++ b/src/nvim/lib/kbtree.h @@ -0,0 +1,423 @@ +/*- + * Copyright 1997-1999, 2001, John-Mark Gurney. + * 2008-2009, Attractive Chaos + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef NVIM_LIB_KBTREE_H +#define NVIM_LIB_KBTREE_H + +#include +#include +#include + +#define KB_MAX_DEPTH 64 + +typedef struct { + int32_t is_internal:1, n:31; +} kbnode_t; + + +typedef struct { + kbnode_t *x; + int i; +} kbpos_t; + +typedef struct { + kbpos_t stack[KB_MAX_DEPTH], *p; +} kbitr_t; + +#define __KB_KEY(type, x) ((type*)((char*)x + 4)) +#define __KB_PTR(btr, x) ((kbnode_t**)((char*)x + btr->off_ptr)) + +#define __KB_TREE_T(name) \ + typedef struct { \ + kbnode_t *root; \ + int off_key, off_ptr, ilen, elen; \ + int n, t; \ + int n_keys, n_nodes; \ + } kbtree_##name##_t; + +#define __KB_INIT(name, key_t) \ + static inline kbtree_##name##_t *kb_init_##name(unsigned int size) \ + { \ + kbtree_##name##_t *b; \ + b = (kbtree_##name##_t*)calloc(1, sizeof(kbtree_##name##_t)); \ + b->t = (int)((size - 4 - sizeof(void*)) / (sizeof(void*) + sizeof(key_t)) + 1) >> 1; \ + if (b->t < 2) { \ + free(b); return 0; \ + } \ + b->n = 2 * b->t - 1; \ + b->off_ptr = (int)(4 + (unsigned int)b->n * sizeof(key_t)); \ + b->ilen = (int)(4 + sizeof(void*) + (unsigned int)b->n * (sizeof(void*) + sizeof(key_t)) + 3) >> 2 << 2; \ + b->elen = (b->off_ptr + 3) >> 2 << 2; \ + b->root = (kbnode_t*)calloc(1, (unsigned int)b->ilen); \ + ++b->n_nodes; \ + return b; \ + } + +#define __kb_destroy(b) do { \ + int i; \ + unsigned int max = 8; \ + kbnode_t *x, **top, **stack = 0; \ + if (b) { \ + top = stack = (kbnode_t**)calloc(max, sizeof(kbnode_t*)); \ + *top++ = (b)->root; \ + while (top != stack) { \ + x = *--top; \ + if (x->is_internal == 0) { free(x); continue; } \ + for (i = 0; i <= x->n; ++i) \ + if (__KB_PTR(b, x)[i]) { \ + if (top - stack == (int)max) { \ + max <<= 1; \ + stack = (kbnode_t**)realloc(stack, max * sizeof(kbnode_t*)); \ + top = stack + (max>>1); \ + } \ + *top++ = __KB_PTR(b, x)[i]; \ + } \ + free(x); \ + } \ + } \ + free(b); free(stack); \ + } while (0) + +#define __KB_GET_AUX1(name, key_t, __cmp) \ + static inline int __kb_getp_aux_##name(const kbnode_t * __restrict x, const key_t * __restrict k, int *r) \ + { \ + int tr, *rr, begin = 0, end = x->n; \ + if (x->n == 0) return -1; \ + rr = r? r : &tr; \ + while (begin < end) { \ + int mid = (begin + end) >> 1; \ + if (__cmp(__KB_KEY(key_t, x)[mid], *k) < 0) begin = mid + 1; \ + else end = mid; \ + } \ + if (begin == x->n) { *rr = 1; return x->n - 1; } \ + if ((*rr = __cmp(*k, __KB_KEY(key_t, x)[begin])) < 0) --begin; \ + return begin; \ + } + +#define __KB_GET(name, key_t) \ + static key_t *kb_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ + { \ + int i, r = 0; \ + kbnode_t *x = b->root; \ + while (x) { \ + i = __kb_getp_aux_##name(x, k, &r); \ + if (i >= 0 && r == 0) return &__KB_KEY(key_t, x)[i]; \ + if (x->is_internal == 0) return 0; \ + x = __KB_PTR(b, x)[i + 1]; \ + } \ + return 0; \ + } \ + static inline key_t *kb_get_##name(kbtree_##name##_t *b, const key_t k) \ + { \ + return kb_getp_##name(b, &k); \ + } + +#define __KB_INTERVAL(name, key_t) \ + static void kb_intervalp_##name(kbtree_##name##_t *b, const key_t * __restrict k, key_t **lower, key_t **upper) \ + { \ + int i, r = 0; \ + kbnode_t *x = b->root; \ + *lower = *upper = 0; \ + while (x) { \ + i = __kb_getp_aux_##name(x, k, &r); \ + if (i >= 0 && r == 0) { \ + *lower = *upper = &__KB_KEY(key_t, x)[i]; \ + return; \ + } \ + if (i >= 0) *lower = &__KB_KEY(key_t, x)[i]; \ + if (i < x->n - 1) *upper = &__KB_KEY(key_t, x)[i + 1]; \ + if (x->is_internal == 0) return; \ + x = __KB_PTR(b, x)[i + 1]; \ + } \ + } \ + static inline void kb_interval_##name(kbtree_##name##_t *b, const key_t k, key_t **lower, key_t **upper) \ + { \ + kb_intervalp_##name(b, &k, lower, upper); \ + } + +#define __KB_PUT(name, key_t, __cmp) \ + /* x must be an internal node */ \ + static void __kb_split_##name(kbtree_##name##_t *b, kbnode_t *x, int i, kbnode_t *y) \ + { \ + kbnode_t *z; \ + z = (kbnode_t*)calloc(1, y->is_internal? (unsigned int)b->ilen : (unsigned int)b->elen); \ + ++b->n_nodes; \ + z->is_internal = y->is_internal; \ + z->n = b->t - 1; \ + memcpy(__KB_KEY(key_t, z), __KB_KEY(key_t, y) + b->t, sizeof(key_t) * (unsigned int)(b->t - 1)); \ + if (y->is_internal) memcpy(__KB_PTR(b, z), __KB_PTR(b, y) + (unsigned int)b->t, sizeof(void*) * (unsigned int)b->t); \ + y->n = b->t - 1; \ + memmove(__KB_PTR(b, x) + i + 2, __KB_PTR(b, x) + i + 1, sizeof(void*) * (unsigned int)(x->n - i)); \ + __KB_PTR(b, x)[i + 1] = z; \ + memmove(__KB_KEY(key_t, x) + i + 1, __KB_KEY(key_t, x) + i, sizeof(key_t) * (unsigned int)(x->n - i)); \ + __KB_KEY(key_t, x)[i] = __KB_KEY(key_t, y)[b->t - 1]; \ + ++x->n; \ + } \ + static key_t *__kb_putp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k) \ + { \ + int i = x->n - 1; \ + key_t *ret; \ + if (x->is_internal == 0) { \ + i = __kb_getp_aux_##name(x, k, 0); \ + if (i != x->n - 1) \ + memmove(__KB_KEY(key_t, x) + i + 2, __KB_KEY(key_t, x) + i + 1, (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ + ret = &__KB_KEY(key_t, x)[i + 1]; \ + *ret = *k; \ + ++x->n; \ + } else { \ + i = __kb_getp_aux_##name(x, k, 0) + 1; \ + if (__KB_PTR(b, x)[i]->n == 2 * b->t - 1) { \ + __kb_split_##name(b, x, i, __KB_PTR(b, x)[i]); \ + if (__cmp(*k, __KB_KEY(key_t, x)[i]) > 0) ++i; \ + } \ + ret = __kb_putp_aux_##name(b, __KB_PTR(b, x)[i], k); \ + } \ + return ret; \ + } \ + static key_t *kb_putp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ + { \ + kbnode_t *r, *s; \ + ++b->n_keys; \ + r = b->root; \ + if (r->n == 2 * b->t - 1) { \ + ++b->n_nodes; \ + s = (kbnode_t*)calloc(1, (unsigned int)b->ilen); \ + b->root = s; s->is_internal = 1; s->n = 0; \ + __KB_PTR(b, s)[0] = r; \ + __kb_split_##name(b, s, 0, r); \ + r = s; \ + } \ + return __kb_putp_aux_##name(b, r, k); \ + } \ + static inline void kb_put_##name(kbtree_##name##_t *b, const key_t k) \ + { \ + kb_putp_##name(b, &k); \ + } + + +#define __KB_DEL(name, key_t) \ + static key_t __kb_delp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k, int s) \ + { \ + int yn, zn, i, r = 0; \ + kbnode_t *xp, *y, *z; \ + key_t kp; \ + if (x == 0) return *k; \ + if (s) { /* s can only be 0, 1 or 2 */ \ + r = x->is_internal == 0? 0 : s == 1? 1 : -1; \ + i = s == 1? x->n - 1 : -1; \ + } else i = __kb_getp_aux_##name(x, k, &r); \ + if (x->is_internal == 0) { \ + if (s == 2) ++i; \ + kp = __KB_KEY(key_t, x)[i]; \ + memmove(__KB_KEY(key_t, x) + i, __KB_KEY(key_t, x) + i + 1, (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ + --x->n; \ + return kp; \ + } \ + if (r == 0) { \ + if ((yn = __KB_PTR(b, x)[i]->n) >= b->t) { \ + xp = __KB_PTR(b, x)[i]; \ + kp = __KB_KEY(key_t, x)[i]; \ + __KB_KEY(key_t, x)[i] = __kb_delp_aux_##name(b, xp, 0, 1); \ + return kp; \ + } else if ((zn = __KB_PTR(b, x)[i + 1]->n) >= b->t) { \ + xp = __KB_PTR(b, x)[i + 1]; \ + kp = __KB_KEY(key_t, x)[i]; \ + __KB_KEY(key_t, x)[i] = __kb_delp_aux_##name(b, xp, 0, 2); \ + return kp; \ + } else if (yn == b->t - 1 && zn == b->t - 1) { \ + y = __KB_PTR(b, x)[i]; z = __KB_PTR(b, x)[i + 1]; \ + __KB_KEY(key_t, y)[y->n++] = *k; \ + memmove(__KB_KEY(key_t, y) + y->n, __KB_KEY(key_t, z), (unsigned int)z->n * sizeof(key_t)); \ + if (y->is_internal) memmove(__KB_PTR(b, y) + y->n, __KB_PTR(b, z), (unsigned int)(z->n + 1) * sizeof(void*)); \ + y->n += z->n; \ + memmove(__KB_KEY(key_t, x) + i, __KB_KEY(key_t, x) + i + 1, (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ + memmove(__KB_PTR(b, x) + i + 1, __KB_PTR(b, x) + i + 2, (unsigned int)(x->n - i - 1) * sizeof(void*)); \ + --x->n; \ + free(z); \ + return __kb_delp_aux_##name(b, y, k, s); \ + } \ + } \ + ++i; \ + if ((xp = __KB_PTR(b, x)[i])->n == b->t - 1) { \ + if (i > 0 && (y = __KB_PTR(b, x)[i - 1])->n >= b->t) { \ + memmove(__KB_KEY(key_t, xp) + 1, __KB_KEY(key_t, xp), (unsigned int)xp->n * sizeof(key_t)); \ + if (xp->is_internal) memmove(__KB_PTR(b, xp) + 1, __KB_PTR(b, xp), (unsigned int)(xp->n + 1) * sizeof(void*)); \ + __KB_KEY(key_t, xp)[0] = __KB_KEY(key_t, x)[i - 1]; \ + __KB_KEY(key_t, x)[i - 1] = __KB_KEY(key_t, y)[y->n - 1]; \ + if (xp->is_internal) __KB_PTR(b, xp)[0] = __KB_PTR(b, y)[y->n]; \ + --y->n; ++xp->n; \ + } else if (i < x->n && (y = __KB_PTR(b, x)[i + 1])->n >= b->t) { \ + __KB_KEY(key_t, xp)[xp->n++] = __KB_KEY(key_t, x)[i]; \ + __KB_KEY(key_t, x)[i] = __KB_KEY(key_t, y)[0]; \ + if (xp->is_internal) __KB_PTR(b, xp)[xp->n] = __KB_PTR(b, y)[0]; \ + --y->n; \ + memmove(__KB_KEY(key_t, y), __KB_KEY(key_t, y) + 1, (unsigned int)y->n * sizeof(key_t)); \ + if (y->is_internal) memmove(__KB_PTR(b, y), __KB_PTR(b, y) + 1, (unsigned int)(y->n + 1) * sizeof(void*)); \ + } else if (i > 0 && (y = __KB_PTR(b, x)[i - 1])->n == b->t - 1) { \ + __KB_KEY(key_t, y)[y->n++] = __KB_KEY(key_t, x)[i - 1]; \ + memmove(__KB_KEY(key_t, y) + y->n, __KB_KEY(key_t, xp), (unsigned int)xp->n * sizeof(key_t)); \ + if (y->is_internal) memmove(__KB_PTR(b, y) + y->n, __KB_PTR(b, xp), (unsigned int)(xp->n + 1) * sizeof(void*)); \ + y->n += xp->n; \ + memmove(__KB_KEY(key_t, x) + i - 1, __KB_KEY(key_t, x) + i, (unsigned int)(x->n - i) * sizeof(key_t)); \ + memmove(__KB_PTR(b, x) + i, __KB_PTR(b, x) + i + 1, (unsigned int)(x->n - i) * sizeof(void*)); \ + --x->n; \ + free(xp); \ + xp = y; \ + } else if (i < x->n && (y = __KB_PTR(b, x)[i + 1])->n == b->t - 1) { \ + __KB_KEY(key_t, xp)[xp->n++] = __KB_KEY(key_t, x)[i]; \ + memmove(__KB_KEY(key_t, xp) + xp->n, __KB_KEY(key_t, y), (unsigned int)y->n * sizeof(key_t)); \ + if (xp->is_internal) memmove(__KB_PTR(b, xp) + xp->n, __KB_PTR(b, y), (unsigned int)(y->n + 1) * sizeof(void*)); \ + xp->n += y->n; \ + memmove(__KB_KEY(key_t, x) + i, __KB_KEY(key_t, x) + i + 1, (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ + memmove(__KB_PTR(b, x) + i + 1, __KB_PTR(b, x) + i + 2, (unsigned int)(x->n - i - 1) * sizeof(void*)); \ + --x->n; \ + free(y); \ + } \ + } \ + return __kb_delp_aux_##name(b, xp, k, s); \ + } \ + static key_t kb_delp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ + { \ + kbnode_t *x; \ + key_t ret; \ + ret = __kb_delp_aux_##name(b, b->root, k, 0); \ + --b->n_keys; \ + if (b->root->n == 0 && b->root->is_internal) { \ + --b->n_nodes; \ + x = b->root; \ + b->root = __KB_PTR(b, x)[0]; \ + free(x); \ + } \ + return ret; \ + } \ + static inline key_t kb_del_##name(kbtree_##name##_t *b, const key_t k) \ + { \ + return kb_delp_##name(b, &k); \ + } + +#define __KB_ITR(name, key_t) \ + static inline void kb_itr_first_##name(kbtree_##name##_t *b, kbitr_t *itr) \ + { \ + itr->p = 0; \ + if (b->n_keys == 0) return; \ + itr->p = itr->stack; \ + itr->p->x = b->root; itr->p->i = 0; \ + while (itr->p->x->is_internal && __KB_PTR(b, itr->p->x)[0] != 0) { \ + kbnode_t *x = itr->p->x; \ + ++itr->p; \ + itr->p->x = __KB_PTR(b, x)[0]; itr->p->i = 0; \ + } \ + } \ + static inline int kb_itr_next_##name(kbtree_##name##_t *b, kbitr_t *itr) \ + { \ + if (itr->p < itr->stack) return 0; \ + for (;;) { \ + ++itr->p->i; \ + while (itr->p->x && itr->p->i <= itr->p->x->n) { \ + itr->p[1].i = 0; \ + itr->p[1].x = itr->p->x->is_internal? __KB_PTR(b, itr->p->x)[itr->p->i] : 0; \ + ++itr->p; \ + } \ + --itr->p; \ + if (itr->p < itr->stack) return 0; \ + if (itr->p->x && itr->p->i < itr->p->x->n) return 1; \ + } \ + } + +#define KBTREE_INIT(name, key_t, __cmp) \ + __KB_TREE_T(name) \ + __KB_INIT(name, key_t) \ + __KB_GET_AUX1(name, key_t, __cmp) \ + __KB_GET(name, key_t) \ + __KB_INTERVAL(name, key_t) \ + __KB_PUT(name, key_t, __cmp) \ + __KB_DEL(name, key_t) \ + __KB_ITR(name, key_t) + +#define KB_DEFAULT_SIZE 512 + +#define kbtree_t(name) kbtree_##name##_t +#define kb_init(name, s) kb_init_##name(s) +#define kb_destroy(name, b) __kb_destroy(b) +#define kb_get(name, b, k) kb_get_##name(b, k) +#define kb_put(name, b, k) kb_put_##name(b, k) +#define kb_del(name, b, k) kb_del_##name(b, k) +#define kb_interval(name, b, k, l, u) kb_interval_##name(b, k, l, u) +#define kb_getp(name, b, k) kb_getp_##name(b, k) +#define kb_putp(name, b, k) kb_putp_##name(b, k) +#define kb_delp(name, b, k) kb_delp_##name(b, k) +#define kb_intervalp(name, b, k, l, u) kb_intervalp_##name(b, k, l, u) + +#define kb_itr_first(name, b, i) kb_itr_first_##name(b, i) +#define kb_itr_next(name, b, i) kb_itr_next_##name(b, i) +#define kb_itr_key(type, itr) __KB_KEY(type, (itr)->p->x)[(itr)->p->i] +#define kb_itr_valid(itr) ((itr)->p >= (itr)->stack) + +#define kb_size(b) ((b)->n_keys) + +#define kb_generic_cmp(a, b) (((b) < (a)) - ((a) < (b))) +#define kb_str_cmp(a, b) strcmp(a, b) + +/* The following is *DEPRECATED*!!! Use the iterator interface instead! */ + +typedef struct { + kbnode_t *x; + int i; +} __kbstack_t; + +#define __kb_traverse(key_t, b, __func) do { \ + int __kmax = 8; \ + __kbstack_t *__kstack, *__kp; \ + __kp = __kstack = (__kbstack_t*)calloc(__kmax, sizeof(__kbstack_t)); \ + __kp->x = (b)->root; __kp->i = 0; \ + for (;;) { \ + while (__kp->x && __kp->i <= __kp->x->n) { \ + if (__kp - __kstack == __kmax - 1) { \ + __kmax <<= 1; \ + __kstack = (__kbstack_t*)realloc(__kstack, __kmax * sizeof(__kbstack_t)); \ + __kp = __kstack + (__kmax>>1) - 1; \ + } \ + (__kp+1)->i = 0; (__kp+1)->x = __kp->x->is_internal? __KB_PTR(b, __kp->x)[__kp->i] : 0; \ + ++__kp; \ + } \ + --__kp; \ + if (__kp >= __kstack) { \ + if (__kp->x && __kp->i < __kp->x->n) __func(&__KB_KEY(key_t, __kp->x)[__kp->i]); \ + ++__kp->i; \ + } else break; \ + } \ + free(__kstack); \ + } while (0) + +#define __kb_get_first(key_t, b, ret) do { \ + kbnode_t *__x = (b)->root; \ + while (__KB_PTR(b, __x)[0] != 0) \ + __x = __KB_PTR(b, __x)[0]; \ + (ret) = __KB_KEY(key_t, __x)[0]; \ + } while (0) + +#endif // NVIM_LIB_KBTREE_H -- cgit From 1eff241ec68ebec76ef1e3e5c6d68bfb64602cf5 Mon Sep 17 00:00:00 2001 From: Björn Linse Date: Thu, 28 Jul 2016 22:42:22 +0200 Subject: bufhl: use kbtree for bufhl --- src/nvim/api/vim.c | 1 + src/nvim/buffer.c | 114 ++++++++++++++++++++++++++++++++----------------- src/nvim/buffer_defs.h | 2 - src/nvim/bufhl_defs.h | 9 ++++ src/nvim/map.c | 1 - src/nvim/map.h | 1 - 6 files changed, 84 insertions(+), 44 deletions(-) (limited to 'src') diff --git a/src/nvim/api/vim.c b/src/nvim/api/vim.c index 74e5167635..92985b412a 100644 --- a/src/nvim/api/vim.c +++ b/src/nvim/api/vim.c @@ -13,6 +13,7 @@ #include "nvim/ascii.h" #include "nvim/api/private/helpers.h" #include "nvim/api/private/defs.h" +#include "nvim/api/private/dispatch.h" #include "nvim/api/buffer.h" #include "nvim/msgpack_rpc/channel.h" #include "nvim/lua/executor.h" diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c index 0d7df7ef77..8491e77e73 100644 --- a/src/nvim/buffer.c +++ b/src/nvim/buffer.c @@ -5138,6 +5138,26 @@ void sign_mark_adjust(linenr_T line1, linenr_T line2, long amount, long amount_a // bufhl: plugin highlights associated with a buffer +/// Get reference to line in kbtree_t, allocating it if neccessary. +BufhlLine *bufhl_tree_ref(kbtree_t(bufhl) *b, linenr_T line, bool put) { + BufhlLine t, *p, **pp; + t.line = line; + + // put() only works if key is absent + pp = kb_get(bufhl, b, &t); + if (pp) { + return *pp; + } else if (!put) { + return NULL; + } + + p = xcalloc(sizeof(*p), 1); + p->line = line; + // p->items zero initialized + kb_put(bufhl, b, p); + return p; +} + /// Adds a highlight to buffer. /// /// Unlike matchaddpos() highlights follow changes to line numbering (as lines @@ -5176,12 +5196,12 @@ int bufhl_add_hl(buf_T *buf, return src_id; } if (!buf->b_bufhl_info) { - buf->b_bufhl_info = map_new(linenr_T, bufhl_vec_T)(); + buf->b_bufhl_info = kb_init(bufhl, KB_DEFAULT_SIZE); } - bufhl_vec_T* lineinfo = map_ref(linenr_T, bufhl_vec_T)(buf->b_bufhl_info, - lnum, true); - bufhl_hl_item_T *hlentry = kv_pushp(*lineinfo); + BufhlLine *lineinfo = bufhl_tree_ref(buf->b_bufhl_info, lnum, true); + + bufhl_hl_item_T *hlentry = kv_pushp(lineinfo->items); hlentry->src_id = src_id; hlentry->hl_id = hl_id; hlentry->start = col_start; @@ -5207,14 +5227,20 @@ void bufhl_clear_line_range(buf_T *buf, if (!buf->b_bufhl_info) { return; } - linenr_T line; linenr_T first_changed = MAXLNUM, last_changed = -1; - // In the case line_start - line_end << bufhl_info->size - // it might be better to reverse this, i e loop over the lines - // to clear on. - bufhl_vec_T unused; - map_foreach(buf->b_bufhl_info, line, unused, { - (void)unused; + // TODO: implement kb_itr_interval and jump directly to the first line + kbitr_t itr; + BufhlLine *l; + for (kb_itr_first(bufhl, buf->b_bufhl_info, &itr); + kb_itr_valid(&itr); + kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { + l = kb_itr_key(BufhlLine *, &itr); + linenr_T line = l->line; + if (line < line_start) { + continue; + } else if (line > line_end) { + break; + } if (line_start <= line && line <= line_end) { if (bufhl_clear_line(buf->b_bufhl_info, src_id, line)) { if (line > last_changed) { @@ -5225,7 +5251,7 @@ void bufhl_clear_line_range(buf_T *buf, } } } - }) + } if (last_changed != -1) { changed_lines_buf(buf, first_changed, last_changed+1, 0); @@ -5241,38 +5267,38 @@ void bufhl_clear_line_range(buf_T *buf, static bool bufhl_clear_line(bufhl_info_T *bufhl_info, int src_id, linenr_T lnum) { - bufhl_vec_T *lineinfo = map_ref(linenr_T, bufhl_vec_T)(bufhl_info, - lnum, false); - size_t oldsize = kv_size(*lineinfo); + BufhlLine *lineinfo = bufhl_tree_ref(bufhl_info, lnum, false); + size_t oldsize = kv_size(lineinfo->items); if (src_id < 0) { - kv_size(*lineinfo) = 0; + kv_size(lineinfo->items) = 0; } else { size_t newind = 0; - for (size_t i = 0; i < kv_size(*lineinfo); i++) { - if (kv_A(*lineinfo, i).src_id != src_id) { + for (size_t i = 0; i < kv_size(lineinfo->items); i++) { + if (kv_A(lineinfo->items, i).src_id != src_id) { if (i != newind) { - kv_A(*lineinfo, newind) = kv_A(*lineinfo, i); + kv_A(lineinfo->items, newind) = kv_A(lineinfo->items, i); } newind++; } } - kv_size(*lineinfo) = newind; + kv_size(lineinfo->items) = newind; } - if (kv_size(*lineinfo) == 0) { - kv_destroy(*lineinfo); - map_del(linenr_T, bufhl_vec_T)(bufhl_info, lnum); + if (kv_size(lineinfo->items) == 0) { + kv_destroy(lineinfo->items); + kb_del(bufhl, bufhl_info, lineinfo); } - return kv_size(*lineinfo) != oldsize; + return kv_size(lineinfo->items) != oldsize; } /// Remove all highlights and free the highlight data -void bufhl_clear_all(buf_T* buf) { +void bufhl_clear_all(buf_T *buf) +{ if (!buf->b_bufhl_info) { return; } bufhl_clear_line_range(buf, -1, 1, MAXLNUM); - map_free(linenr_T, bufhl_vec_T)(buf->b_bufhl_info); + kb_destroy(bufhl, buf->b_bufhl_info); buf->b_bufhl_info = NULL; } @@ -5285,25 +5311,29 @@ void bufhl_mark_adjust(buf_T* buf, if (!buf->b_bufhl_info) { return; } + // XXX: does not support move + // we need to detect this case and - bufhl_info_T *newmap = map_new(linenr_T, bufhl_vec_T)(); - linenr_T line; - bufhl_vec_T lineinfo; - map_foreach(buf->b_bufhl_info, line, lineinfo, { - if (line >= line1 && line <= line2) { + kbitr_t itr; + BufhlLine *l; + for (kb_itr_first(bufhl, buf->b_bufhl_info, &itr); + kb_itr_valid(&itr); + kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { + l = kb_itr_key(BufhlLine *, &itr); + if (l->line >= line1 && l->line <= line2) { if (amount == MAXLNUM) { - bufhl_clear_line(buf->b_bufhl_info, -1, line); + bufhl_clear_line(buf->b_bufhl_info, -1, l->line); continue; } else { - line += amount; + l->line += amount; + } + } else if (l->line > line2) { + if (amount_after == 0) { + break; } - } else if (line > line2) { - line += amount_after; + l->line += amount_after; } - map_put(linenr_T, bufhl_vec_T)(newmap, line, lineinfo); - }); - map_free(linenr_T, bufhl_vec_T)(buf->b_bufhl_info); - buf->b_bufhl_info = newmap; + } } @@ -5318,8 +5348,12 @@ bool bufhl_start_line(buf_T *buf, linenr_T lnum, bufhl_lineinfo_T *info) { return false; } + BufhlLine *lineinfo = bufhl_tree_ref(buf->b_bufhl_info, lnum, false); + if (!lineinfo) { + return false; + } info->valid_to = -1; - info->entries = map_get(linenr_T, bufhl_vec_T)(buf->b_bufhl_info, lnum); + info->entries = lineinfo->items; return kv_size(info->entries) > 0; } diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h index af2b50e22d..adced27f58 100644 --- a/src/nvim/buffer_defs.h +++ b/src/nvim/buffer_defs.h @@ -106,8 +106,6 @@ typedef struct frame_S frame_T; // for bufhl_*_T #include "nvim/bufhl_defs.h" -typedef Map(linenr_T, bufhl_vec_T) bufhl_info_T; - #include "nvim/os/fs_defs.h" // for FileID #include "nvim/terminal.h" // for Terminal diff --git a/src/nvim/bufhl_defs.h b/src/nvim/bufhl_defs.h index e47bb2a238..0667a82a62 100644 --- a/src/nvim/bufhl_defs.h +++ b/src/nvim/bufhl_defs.h @@ -3,6 +3,7 @@ #include "nvim/pos.h" #include "nvim/lib/kvec.h" +#include "nvim/lib/kbtree.h" // bufhl: buffer specific highlighting struct bufhl_hl_item @@ -16,10 +17,18 @@ typedef struct bufhl_hl_item bufhl_hl_item_T; typedef kvec_t(struct bufhl_hl_item) bufhl_vec_T; +typedef struct { + linenr_T line; + bufhl_vec_T items; +} BufhlLine; + typedef struct { bufhl_vec_T entries; int current; colnr_T valid_to; } bufhl_lineinfo_T; +#define BUFHL_CMP(a, b) (((b)->line - (a)->line)) +KBTREE_INIT(bufhl, BufhlLine *, BUFHL_CMP) +typedef kbtree_t(bufhl) bufhl_info_T; #endif // NVIM_BUFHL_DEFS_H diff --git a/src/nvim/map.c b/src/nvim/map.c index 366b286d14..537b6751e2 100644 --- a/src/nvim/map.c +++ b/src/nvim/map.c @@ -149,4 +149,3 @@ MAP_IMPL(handle_T, ptr_t, DEFAULT_INITIALIZER) #define MSGPACK_HANDLER_INITIALIZER { .fn = NULL, .async = false } MAP_IMPL(String, MsgpackRpcRequestHandler, MSGPACK_HANDLER_INITIALIZER) #define KVEC_INITIALIZER { .size = 0, .capacity = 0, .items = NULL } -MAP_IMPL(linenr_T, bufhl_vec_T, KVEC_INITIALIZER) diff --git a/src/nvim/map.h b/src/nvim/map.h index a4fccf47f9..047aa163ce 100644 --- a/src/nvim/map.h +++ b/src/nvim/map.h @@ -30,7 +30,6 @@ MAP_DECLS(ptr_t, ptr_t) MAP_DECLS(uint64_t, ptr_t) MAP_DECLS(handle_T, ptr_t) MAP_DECLS(String, MsgpackRpcRequestHandler) -MAP_DECLS(linenr_T, bufhl_vec_T) #define map_new(T, U) map_##T##_##U##_new #define map_free(T, U) map_##T##_##U##_free -- cgit From 6712e08bba2d50899853bf98b786bdf48c3c79be Mon Sep 17 00:00:00 2001 From: Björn Linse Date: Fri, 29 Jul 2016 20:27:50 +0200 Subject: kbtree: allow iterators to start at arbitrary position --- src/nvim/buffer.c | 51 +++++++++++++++++++++++++++++++------------------ src/nvim/bufhl_defs.h | 2 +- src/nvim/lib/kbtree.h | 53 ++++++++++++++++++++++++++++++++++++++++++++++++--- 3 files changed, 83 insertions(+), 23 deletions(-) (limited to 'src') diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c index 8491e77e73..580eb07d6b 100644 --- a/src/nvim/buffer.c +++ b/src/nvim/buffer.c @@ -74,6 +74,12 @@ #include "nvim/os/time.h" #include "nvim/os/input.h" +typedef enum { + kBLSUnchanged = 0, + kBLSChanged = 1, + kBLSDeleted = 2, +} BufhlLineStatus; + #ifdef INCLUDE_GENERATED_DECLARATIONS # include "buffer.c.generated.h" #endif @@ -5228,21 +5234,21 @@ void bufhl_clear_line_range(buf_T *buf, return; } linenr_T first_changed = MAXLNUM, last_changed = -1; - // TODO: implement kb_itr_interval and jump directly to the first line + kbitr_t itr; - BufhlLine *l; - for (kb_itr_first(bufhl, buf->b_bufhl_info, &itr); - kb_itr_valid(&itr); - kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { + BufhlLine *l, t = {line_start}; + if (!kb_itr_get(bufhl, buf->b_bufhl_info, &t, &itr)) { + kb_itr_next(bufhl, buf->b_bufhl_info, &itr); + } + for (; kb_itr_valid(&itr); kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { l = kb_itr_key(BufhlLine *, &itr); linenr_T line = l->line; - if (line < line_start) { - continue; - } else if (line > line_end) { + if (line > line_end) { break; } if (line_start <= line && line <= line_end) { - if (bufhl_clear_line(buf->b_bufhl_info, src_id, line)) { + BufhlLineStatus status = bufhl_clear_line(buf->b_bufhl_info, src_id, line); + if (status != kBLSUnchanged) { if (line > last_changed) { last_changed = line; } @@ -5250,6 +5256,9 @@ void bufhl_clear_line_range(buf_T *buf, first_changed = line; } } + if (status == kBLSDeleted) { + kb_del_itr(bufhl, buf->b_bufhl_info, &itr); + } } } @@ -5264,8 +5273,8 @@ void bufhl_clear_line_range(buf_T *buf, /// @param bufhl_info The highlight info for the buffer /// @param src_id Highlight source group to clear, or -1 to clear all groups. /// @param lnum Linenr where the highlight should be cleared -static bool bufhl_clear_line(bufhl_info_T *bufhl_info, int src_id, - linenr_T lnum) +static BufhlLineStatus bufhl_clear_line(bufhl_info_T *bufhl_info, int src_id, + linenr_T lnum) { BufhlLine *lineinfo = bufhl_tree_ref(bufhl_info, lnum, false); size_t oldsize = kv_size(lineinfo->items); @@ -5286,9 +5295,9 @@ static bool bufhl_clear_line(bufhl_info_T *bufhl_info, int src_id, if (kv_size(lineinfo->items) == 0) { kv_destroy(lineinfo->items); - kb_del(bufhl, bufhl_info, lineinfo); + return kBLSDeleted; } - return kv_size(lineinfo->items) != oldsize; + return kv_size(lineinfo->items) != oldsize ? kBLSChanged : kBLSUnchanged; } /// Remove all highlights and free the highlight data @@ -5315,15 +5324,19 @@ void bufhl_mark_adjust(buf_T* buf, // we need to detect this case and kbitr_t itr; - BufhlLine *l; - for (kb_itr_first(bufhl, buf->b_bufhl_info, &itr); - kb_itr_valid(&itr); - kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { + BufhlLine *l, t = {line1}; + if (!kb_itr_get(bufhl, buf->b_bufhl_info, &t, &itr)) { + kb_itr_next(bufhl, buf->b_bufhl_info, &itr); + } + for (; kb_itr_valid(&itr); kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { l = kb_itr_key(BufhlLine *, &itr); if (l->line >= line1 && l->line <= line2) { if (amount == MAXLNUM) { - bufhl_clear_line(buf->b_bufhl_info, -1, l->line); - continue; + if (bufhl_clear_line(buf->b_bufhl_info, -1, l->line) == kBLSDeleted) { + kb_del_itr(bufhl, buf->b_bufhl_info, &itr); + } else { + assert(false); + } } else { l->line += amount; } diff --git a/src/nvim/bufhl_defs.h b/src/nvim/bufhl_defs.h index 0667a82a62..c8b81e7927 100644 --- a/src/nvim/bufhl_defs.h +++ b/src/nvim/bufhl_defs.h @@ -28,7 +28,7 @@ typedef struct { colnr_T valid_to; } bufhl_lineinfo_T; -#define BUFHL_CMP(a, b) (((b)->line - (a)->line)) +#define BUFHL_CMP(a, b) (((a)->line - (b)->line)) KBTREE_INIT(bufhl, BufhlLine *, BUFHL_CMP) typedef kbtree_t(bufhl) bufhl_info_T; #endif // NVIM_BUFHL_DEFS_H diff --git a/src/nvim/lib/kbtree.h b/src/nvim/lib/kbtree.h index b58c3f97a4..ec83d4d124 100644 --- a/src/nvim/lib/kbtree.h +++ b/src/nvim/lib/kbtree.h @@ -57,7 +57,9 @@ typedef struct { int off_key, off_ptr, ilen, elen; \ int n, t; \ int n_keys, n_nodes; \ - } kbtree_##name##_t; + } kbtree_##name##_t; \ + + #define __KB_INIT(name, key_t) \ static inline kbtree_##name##_t *kb_init_##name(unsigned int size) \ @@ -75,7 +77,7 @@ typedef struct { b->root = (kbnode_t*)calloc(1, (unsigned int)b->ilen); \ ++b->n_nodes; \ return b; \ - } + } \ #define __kb_destroy(b) do { \ int i; \ @@ -346,7 +348,48 @@ typedef struct { if (itr->p < itr->stack) return 0; \ if (itr->p->x && itr->p->i < itr->p->x->n) return 1; \ } \ - } + } \ + static inline int kb_itr_prev_##name(kbtree_##name##_t *b, kbitr_t *itr) \ + { \ + if (itr->p < itr->stack) return 0; \ + for (;;) { \ + while (itr->p->x && itr->p->i >= 0) { \ + itr->p[1].x = itr->p->x->is_internal? __KB_PTR(b, itr->p->x)[itr->p->i] : 0; \ + itr->p[1].i = itr->p[1].x ? itr->p[1].x->n : -1; \ + ++itr->p; \ + } \ + --itr->p; \ + if (itr->p < itr->stack) return 0; \ + --itr->p->i; \ + if (itr->p->x && itr->p->i >= 0) return 1; \ + } \ + } \ + static int kb_itr_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k, kbitr_t *itr) \ + { \ + int i, r = 0; \ + itr->p = itr->stack; \ + itr->p->x = b->root; \ + while (itr->p->x) { \ + i = __kb_getp_aux_##name(itr->p->x, k, &r); \ + itr->p->i = i; \ + if (i >= 0 && r == 0) return 1; \ + ++itr->p->i; \ + itr->p[1].x = itr->p->x->is_internal? __KB_PTR(b, itr->p->x)[i + 1] : 0; \ + ++itr->p; \ + } \ + return 0; \ + } \ + static int kb_itr_get_##name(kbtree_##name##_t *b, const key_t k, kbitr_t *itr) \ + { \ + return kb_itr_getp_##name(b,&k,itr); \ + } \ + static inline void kb_del_itr_##name(kbtree_##name##_t *b, kbitr_t *itr) \ + { \ + key_t k = kb_itr_key(key_t, itr); \ + kb_delp_##name(b, &k); \ + kb_itr_getp_##name(b, &k, itr); \ + } + #define KBTREE_INIT(name, key_t, __cmp) \ __KB_TREE_T(name) \ @@ -373,7 +416,11 @@ typedef struct { #define kb_intervalp(name, b, k, l, u) kb_intervalp_##name(b, k, l, u) #define kb_itr_first(name, b, i) kb_itr_first_##name(b, i) +#define kb_itr_get(name, b, k, i) kb_itr_get_##name(b, k, i) +#define kb_itr_getp(name, b, k, i) kb_itr_getp_##name(b, k, i) #define kb_itr_next(name, b, i) kb_itr_next_##name(b, i) +#define kb_itr_prev(name, b, i) kb_itr_prev_##name(b, i) +#define kb_del_itr(name, b, i) kb_del_itr_##name(b, i) #define kb_itr_key(type, itr) __KB_KEY(type, (itr)->p->x)[(itr)->p->i] #define kb_itr_valid(itr) ((itr)->p >= (itr)->stack) -- cgit From 53cf88c27bcea1099d48a1ca6dc0a4d7c44e0a98 Mon Sep 17 00:00:00 2001 From: Björn Linse Date: Sat, 6 Aug 2016 09:15:43 +0200 Subject: kbtree: use proper structs --- src/nvim/buffer.c | 10 +-- src/nvim/bufhl_defs.h | 2 +- src/nvim/lib/kbtree.h | 212 +++++++++++++++++++++++++------------------------- 3 files changed, 112 insertions(+), 112 deletions(-) (limited to 'src') diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c index 580eb07d6b..26dc07e4bc 100644 --- a/src/nvim/buffer.c +++ b/src/nvim/buffer.c @@ -5202,7 +5202,7 @@ int bufhl_add_hl(buf_T *buf, return src_id; } if (!buf->b_bufhl_info) { - buf->b_bufhl_info = kb_init(bufhl, KB_DEFAULT_SIZE); + buf->b_bufhl_info = kb_init(bufhl); } BufhlLine *lineinfo = bufhl_tree_ref(buf->b_bufhl_info, lnum, true); @@ -5235,13 +5235,13 @@ void bufhl_clear_line_range(buf_T *buf, } linenr_T first_changed = MAXLNUM, last_changed = -1; - kbitr_t itr; + kbitr_t(bufhl) itr; BufhlLine *l, t = {line_start}; if (!kb_itr_get(bufhl, buf->b_bufhl_info, &t, &itr)) { kb_itr_next(bufhl, buf->b_bufhl_info, &itr); } for (; kb_itr_valid(&itr); kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { - l = kb_itr_key(BufhlLine *, &itr); + l = kb_itr_key(&itr); linenr_T line = l->line; if (line > line_end) { break; @@ -5323,13 +5323,13 @@ void bufhl_mark_adjust(buf_T* buf, // XXX: does not support move // we need to detect this case and - kbitr_t itr; + kbitr_t(bufhl) itr; BufhlLine *l, t = {line1}; if (!kb_itr_get(bufhl, buf->b_bufhl_info, &t, &itr)) { kb_itr_next(bufhl, buf->b_bufhl_info, &itr); } for (; kb_itr_valid(&itr); kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { - l = kb_itr_key(BufhlLine *, &itr); + l = kb_itr_key(&itr); if (l->line >= line1 && l->line <= line2) { if (amount == MAXLNUM) { if (bufhl_clear_line(buf->b_bufhl_info, -1, l->line) == kBLSDeleted) { diff --git a/src/nvim/bufhl_defs.h b/src/nvim/bufhl_defs.h index c8b81e7927..0d2f9c90d0 100644 --- a/src/nvim/bufhl_defs.h +++ b/src/nvim/bufhl_defs.h @@ -29,6 +29,6 @@ typedef struct { } bufhl_lineinfo_T; #define BUFHL_CMP(a, b) (((a)->line - (b)->line)) -KBTREE_INIT(bufhl, BufhlLine *, BUFHL_CMP) +KBTREE_INIT(bufhl, BufhlLine *, BUFHL_CMP, 10) typedef kbtree_t(bufhl) bufhl_info_T; #endif // NVIM_BUFHL_DEFS_H diff --git a/src/nvim/lib/kbtree.h b/src/nvim/lib/kbtree.h index ec83d4d124..bfea068206 100644 --- a/src/nvim/lib/kbtree.h +++ b/src/nvim/lib/kbtree.h @@ -32,79 +32,71 @@ #include #include -#define KB_MAX_DEPTH 64 - -typedef struct { - int32_t is_internal:1, n:31; -} kbnode_t; - - -typedef struct { - kbnode_t *x; - int i; -} kbpos_t; +#include "nvim/memory.h" -typedef struct { - kbpos_t stack[KB_MAX_DEPTH], *p; -} kbitr_t; - -#define __KB_KEY(type, x) ((type*)((char*)x + 4)) -#define __KB_PTR(btr, x) ((kbnode_t**)((char*)x + btr->off_ptr)) +#define KB_MAX_DEPTH 64 -#define __KB_TREE_T(name) \ +#define __KB_KEY(type, x) (x->key) +#define __KB_PTR(btr, x) (x->ptr) + +#define __KB_TREE_T(name,key_t,T) \ +typedef struct kbnode_##name##_s kbnode_##name##_t; \ +struct kbnode_##name##_s { \ + int32_t n; \ + bool is_internal; \ + key_t key[2*T-1]; \ + kbnode_##name##_t *ptr[0]; \ +} ; \ + \ typedef struct { \ - kbnode_t *root; \ - int off_key, off_ptr, ilen, elen; \ - int n, t; \ + kbnode_##name##_t *root; \ int n_keys, n_nodes; \ } kbtree_##name##_t; \ + typedef struct { \ + kbnode_##name##_t *x; \ + int i; \ + } kbpos_##name##_t; \ + typedef struct { \ + kbpos_##name##_t stack[KB_MAX_DEPTH], *p; \ + } kbitr_##name##_t; \ - -#define __KB_INIT(name, key_t) \ - static inline kbtree_##name##_t *kb_init_##name(unsigned int size) \ +#define __KB_INIT(name, key_t, kbnode_t, T, ILEN) \ + static inline kbtree_##name##_t *kb_init_##name() \ { \ kbtree_##name##_t *b; \ - b = (kbtree_##name##_t*)calloc(1, sizeof(kbtree_##name##_t)); \ - b->t = (int)((size - 4 - sizeof(void*)) / (sizeof(void*) + sizeof(key_t)) + 1) >> 1; \ - if (b->t < 2) { \ - free(b); return 0; \ - } \ - b->n = 2 * b->t - 1; \ - b->off_ptr = (int)(4 + (unsigned int)b->n * sizeof(key_t)); \ - b->ilen = (int)(4 + sizeof(void*) + (unsigned int)b->n * (sizeof(void*) + sizeof(key_t)) + 3) >> 2 << 2; \ - b->elen = (b->off_ptr + 3) >> 2 << 2; \ - b->root = (kbnode_t*)calloc(1, (unsigned int)b->ilen); \ + b = (kbtree_##name##_t*)xcalloc(1, sizeof(kbtree_##name##_t)); \ + b->root = (kbnode_t*)xcalloc(1, ILEN); \ ++b->n_nodes; \ return b; \ } \ -#define __kb_destroy(b) do { \ +#define __kb_destroy(kbnode_t,b) do { \ int i; \ unsigned int max = 8; \ kbnode_t *x, **top, **stack = 0; \ if (b) { \ - top = stack = (kbnode_t**)calloc(max, sizeof(kbnode_t*)); \ + top = stack = (kbnode_t**)xcalloc(max, sizeof(kbnode_t*)); \ *top++ = (b)->root; \ while (top != stack) { \ x = *--top; \ - if (x->is_internal == 0) { free(x); continue; } \ + if (x->is_internal == 0) { xfree(x); continue; } \ for (i = 0; i <= x->n; ++i) \ if (__KB_PTR(b, x)[i]) { \ if (top - stack == (int)max) { \ max <<= 1; \ - stack = (kbnode_t**)realloc(stack, max * sizeof(kbnode_t*)); \ + stack = (kbnode_t**)xrealloc(stack, max * sizeof(kbnode_t*)); \ top = stack + (max>>1); \ } \ *top++ = __KB_PTR(b, x)[i]; \ } \ - free(x); \ + xfree(x); \ } \ } \ - free(b); free(stack); \ + xfree(b); xfree(stack); \ } while (0) -#define __KB_GET_AUX1(name, key_t, __cmp) \ +#define __KB_GET_AUX1(name, key_t, kbnode_t, __cmp) \ static inline int __kb_getp_aux_##name(const kbnode_t * __restrict x, const key_t * __restrict k, int *r) \ { \ int tr, *rr, begin = 0, end = x->n; \ @@ -120,7 +112,7 @@ typedef struct { return begin; \ } -#define __KB_GET(name, key_t) \ +#define __KB_GET(name, key_t, kbnode_t) \ static key_t *kb_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ { \ int i, r = 0; \ @@ -138,7 +130,7 @@ typedef struct { return kb_getp_##name(b, &k); \ } -#define __KB_INTERVAL(name, key_t) \ +#define __KB_INTERVAL(name, key_t, kbnode_t) \ static void kb_intervalp_##name(kbtree_##name##_t *b, const key_t * __restrict k, key_t **lower, key_t **upper) \ { \ int i, r = 0; \ @@ -161,22 +153,22 @@ typedef struct { kb_intervalp_##name(b, &k, lower, upper); \ } -#define __KB_PUT(name, key_t, __cmp) \ +#define __KB_PUT(name, key_t, kbnode_t, __cmp, T, ILEN) \ /* x must be an internal node */ \ static void __kb_split_##name(kbtree_##name##_t *b, kbnode_t *x, int i, kbnode_t *y) \ { \ kbnode_t *z; \ - z = (kbnode_t*)calloc(1, y->is_internal? (unsigned int)b->ilen : (unsigned int)b->elen); \ + z = (kbnode_t*)xcalloc(1, y->is_internal? ILEN : sizeof(kbnode_##name##_t)); \ ++b->n_nodes; \ z->is_internal = y->is_internal; \ - z->n = b->t - 1; \ - memcpy(__KB_KEY(key_t, z), __KB_KEY(key_t, y) + b->t, sizeof(key_t) * (unsigned int)(b->t - 1)); \ - if (y->is_internal) memcpy(__KB_PTR(b, z), __KB_PTR(b, y) + (unsigned int)b->t, sizeof(void*) * (unsigned int)b->t); \ - y->n = b->t - 1; \ - memmove(__KB_PTR(b, x) + i + 2, __KB_PTR(b, x) + i + 1, sizeof(void*) * (unsigned int)(x->n - i)); \ + z->n = T - 1; \ + memcpy(__KB_KEY(key_t, z), &__KB_KEY(key_t, y)[T], sizeof(key_t) * (T - 1)); \ + if (y->is_internal) memcpy(__KB_PTR(b, z), &__KB_PTR(b, y)[T], sizeof(void*) * T); \ + y->n = T - 1; \ + memmove(&__KB_PTR(b, x)[i + 2], &__KB_PTR(b, x)[i + 1], sizeof(void*) * (unsigned int)(x->n - i)); \ __KB_PTR(b, x)[i + 1] = z; \ - memmove(__KB_KEY(key_t, x) + i + 1, __KB_KEY(key_t, x) + i, sizeof(key_t) * (unsigned int)(x->n - i)); \ - __KB_KEY(key_t, x)[i] = __KB_KEY(key_t, y)[b->t - 1]; \ + memmove(&__KB_KEY(key_t, x)[i + 1], &__KB_KEY(key_t, x)[i], sizeof(key_t) * (unsigned int)(x->n - i)); \ + __KB_KEY(key_t, x)[i] = __KB_KEY(key_t, y)[T - 1]; \ ++x->n; \ } \ static key_t *__kb_putp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k) \ @@ -186,13 +178,13 @@ typedef struct { if (x->is_internal == 0) { \ i = __kb_getp_aux_##name(x, k, 0); \ if (i != x->n - 1) \ - memmove(__KB_KEY(key_t, x) + i + 2, __KB_KEY(key_t, x) + i + 1, (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ + memmove(&__KB_KEY(key_t, x)[i + 2], &__KB_KEY(key_t, x)[i + 1], (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ ret = &__KB_KEY(key_t, x)[i + 1]; \ *ret = *k; \ ++x->n; \ } else { \ i = __kb_getp_aux_##name(x, k, 0) + 1; \ - if (__KB_PTR(b, x)[i]->n == 2 * b->t - 1) { \ + if (__KB_PTR(b, x)[i]->n == 2 * T - 1) { \ __kb_split_##name(b, x, i, __KB_PTR(b, x)[i]); \ if (__cmp(*k, __KB_KEY(key_t, x)[i]) > 0) ++i; \ } \ @@ -205,9 +197,9 @@ typedef struct { kbnode_t *r, *s; \ ++b->n_keys; \ r = b->root; \ - if (r->n == 2 * b->t - 1) { \ + if (r->n == 2 * T - 1) { \ ++b->n_nodes; \ - s = (kbnode_t*)calloc(1, (unsigned int)b->ilen); \ + s = (kbnode_t*)xcalloc(1, ILEN); \ b->root = s; s->is_internal = 1; s->n = 0; \ __KB_PTR(b, s)[0] = r; \ __kb_split_##name(b, s, 0, r); \ @@ -221,7 +213,7 @@ typedef struct { } -#define __KB_DEL(name, key_t) \ +#define __KB_DEL(name, key_t, kbnode_t, T) \ static key_t __kb_delp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k, int s) \ { \ int yn, zn, i, r = 0; \ @@ -235,69 +227,69 @@ typedef struct { if (x->is_internal == 0) { \ if (s == 2) ++i; \ kp = __KB_KEY(key_t, x)[i]; \ - memmove(__KB_KEY(key_t, x) + i, __KB_KEY(key_t, x) + i + 1, (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ + memmove(&__KB_KEY(key_t, x)[i], &__KB_KEY(key_t, x)[i + 1], (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ --x->n; \ return kp; \ } \ if (r == 0) { \ - if ((yn = __KB_PTR(b, x)[i]->n) >= b->t) { \ + if ((yn = __KB_PTR(b, x)[i]->n) >= T) { \ xp = __KB_PTR(b, x)[i]; \ kp = __KB_KEY(key_t, x)[i]; \ __KB_KEY(key_t, x)[i] = __kb_delp_aux_##name(b, xp, 0, 1); \ return kp; \ - } else if ((zn = __KB_PTR(b, x)[i + 1]->n) >= b->t) { \ + } else if ((zn = __KB_PTR(b, x)[i + 1]->n) >= T) { \ xp = __KB_PTR(b, x)[i + 1]; \ kp = __KB_KEY(key_t, x)[i]; \ __KB_KEY(key_t, x)[i] = __kb_delp_aux_##name(b, xp, 0, 2); \ return kp; \ - } else if (yn == b->t - 1 && zn == b->t - 1) { \ + } else if (yn == T - 1 && zn == T - 1) { \ y = __KB_PTR(b, x)[i]; z = __KB_PTR(b, x)[i + 1]; \ __KB_KEY(key_t, y)[y->n++] = *k; \ - memmove(__KB_KEY(key_t, y) + y->n, __KB_KEY(key_t, z), (unsigned int)z->n * sizeof(key_t)); \ - if (y->is_internal) memmove(__KB_PTR(b, y) + y->n, __KB_PTR(b, z), (unsigned int)(z->n + 1) * sizeof(void*)); \ + memmove(&__KB_KEY(key_t, y)[y->n], __KB_KEY(key_t, z), (unsigned int)z->n * sizeof(key_t)); \ + if (y->is_internal) memmove(&__KB_PTR(b, y)[y->n], __KB_PTR(b, z), (unsigned int)(z->n + 1) * sizeof(void*)); \ y->n += z->n; \ - memmove(__KB_KEY(key_t, x) + i, __KB_KEY(key_t, x) + i + 1, (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ - memmove(__KB_PTR(b, x) + i + 1, __KB_PTR(b, x) + i + 2, (unsigned int)(x->n - i - 1) * sizeof(void*)); \ + memmove(&__KB_KEY(key_t, x)[i], &__KB_KEY(key_t, x)[i + 1], (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ + memmove(&__KB_PTR(b, x)[i + 1], &__KB_PTR(b, x)[i + 2], (unsigned int)(x->n - i - 1) * sizeof(void*)); \ --x->n; \ - free(z); \ + xfree(z); \ return __kb_delp_aux_##name(b, y, k, s); \ } \ } \ ++i; \ - if ((xp = __KB_PTR(b, x)[i])->n == b->t - 1) { \ - if (i > 0 && (y = __KB_PTR(b, x)[i - 1])->n >= b->t) { \ - memmove(__KB_KEY(key_t, xp) + 1, __KB_KEY(key_t, xp), (unsigned int)xp->n * sizeof(key_t)); \ - if (xp->is_internal) memmove(__KB_PTR(b, xp) + 1, __KB_PTR(b, xp), (unsigned int)(xp->n + 1) * sizeof(void*)); \ + if ((xp = __KB_PTR(b, x)[i])->n == T - 1) { \ + if (i > 0 && (y = __KB_PTR(b, x)[i - 1])->n >= T) { \ + memmove(&__KB_KEY(key_t, xp)[1], __KB_KEY(key_t, xp), (unsigned int)xp->n * sizeof(key_t)); \ + if (xp->is_internal) memmove(&__KB_PTR(b, xp)[1], __KB_PTR(b, xp), (unsigned int)(xp->n + 1) * sizeof(void*)); \ __KB_KEY(key_t, xp)[0] = __KB_KEY(key_t, x)[i - 1]; \ __KB_KEY(key_t, x)[i - 1] = __KB_KEY(key_t, y)[y->n - 1]; \ if (xp->is_internal) __KB_PTR(b, xp)[0] = __KB_PTR(b, y)[y->n]; \ --y->n; ++xp->n; \ - } else if (i < x->n && (y = __KB_PTR(b, x)[i + 1])->n >= b->t) { \ + } else if (i < x->n && (y = __KB_PTR(b, x)[i + 1])->n >= T) { \ __KB_KEY(key_t, xp)[xp->n++] = __KB_KEY(key_t, x)[i]; \ __KB_KEY(key_t, x)[i] = __KB_KEY(key_t, y)[0]; \ if (xp->is_internal) __KB_PTR(b, xp)[xp->n] = __KB_PTR(b, y)[0]; \ --y->n; \ - memmove(__KB_KEY(key_t, y), __KB_KEY(key_t, y) + 1, (unsigned int)y->n * sizeof(key_t)); \ - if (y->is_internal) memmove(__KB_PTR(b, y), __KB_PTR(b, y) + 1, (unsigned int)(y->n + 1) * sizeof(void*)); \ - } else if (i > 0 && (y = __KB_PTR(b, x)[i - 1])->n == b->t - 1) { \ + memmove(__KB_KEY(key_t, y), &__KB_KEY(key_t, y)[1], (unsigned int)y->n * sizeof(key_t)); \ + if (y->is_internal) memmove(__KB_PTR(b, y), &__KB_PTR(b, y)[1], (unsigned int)(y->n + 1) * sizeof(void*)); \ + } else if (i > 0 && (y = __KB_PTR(b, x)[i - 1])->n == T - 1) { \ __KB_KEY(key_t, y)[y->n++] = __KB_KEY(key_t, x)[i - 1]; \ - memmove(__KB_KEY(key_t, y) + y->n, __KB_KEY(key_t, xp), (unsigned int)xp->n * sizeof(key_t)); \ - if (y->is_internal) memmove(__KB_PTR(b, y) + y->n, __KB_PTR(b, xp), (unsigned int)(xp->n + 1) * sizeof(void*)); \ + memmove(&__KB_KEY(key_t, y)[y->n], __KB_KEY(key_t, xp), (unsigned int)xp->n * sizeof(key_t)); \ + if (y->is_internal) memmove(&__KB_PTR(b, y)[y->n], __KB_PTR(b, xp), (unsigned int)(xp->n + 1) * sizeof(void*)); \ y->n += xp->n; \ - memmove(__KB_KEY(key_t, x) + i - 1, __KB_KEY(key_t, x) + i, (unsigned int)(x->n - i) * sizeof(key_t)); \ - memmove(__KB_PTR(b, x) + i, __KB_PTR(b, x) + i + 1, (unsigned int)(x->n - i) * sizeof(void*)); \ + memmove(&__KB_KEY(key_t, x)[i - 1], &__KB_KEY(key_t, x)[i], (unsigned int)(x->n - i) * sizeof(key_t)); \ + memmove(&__KB_PTR(b, x)[i], &__KB_PTR(b, x)[i + 1], (unsigned int)(x->n - i) * sizeof(void*)); \ --x->n; \ - free(xp); \ + xfree(xp); \ xp = y; \ - } else if (i < x->n && (y = __KB_PTR(b, x)[i + 1])->n == b->t - 1) { \ + } else if (i < x->n && (y = __KB_PTR(b, x)[i + 1])->n == T - 1) { \ __KB_KEY(key_t, xp)[xp->n++] = __KB_KEY(key_t, x)[i]; \ - memmove(__KB_KEY(key_t, xp) + xp->n, __KB_KEY(key_t, y), (unsigned int)y->n * sizeof(key_t)); \ - if (xp->is_internal) memmove(__KB_PTR(b, xp) + xp->n, __KB_PTR(b, y), (unsigned int)(y->n + 1) * sizeof(void*)); \ + memmove(&__KB_KEY(key_t, xp)[xp->n], __KB_KEY(key_t, y), (unsigned int)y->n * sizeof(key_t)); \ + if (xp->is_internal) memmove(&__KB_PTR(b, xp)[xp->n], __KB_PTR(b, y), (unsigned int)(y->n + 1) * sizeof(void*)); \ xp->n += y->n; \ - memmove(__KB_KEY(key_t, x) + i, __KB_KEY(key_t, x) + i + 1, (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ - memmove(__KB_PTR(b, x) + i + 1, __KB_PTR(b, x) + i + 2, (unsigned int)(x->n - i - 1) * sizeof(void*)); \ + memmove(&__KB_KEY(key_t, x)[i], &__KB_KEY(key_t, x)[i + 1], (unsigned int)(x->n - i - 1) * sizeof(key_t)); \ + memmove(&__KB_PTR(b, x)[i + 1], &__KB_PTR(b, x)[i + 2], (unsigned int)(x->n - i - 1) * sizeof(void*)); \ --x->n; \ - free(y); \ + xfree(y); \ } \ } \ return __kb_delp_aux_##name(b, xp, k, s); \ @@ -312,7 +304,7 @@ typedef struct { --b->n_nodes; \ x = b->root; \ b->root = __KB_PTR(b, x)[0]; \ - free(x); \ + xfree(x); \ } \ return ret; \ } \ @@ -321,8 +313,8 @@ typedef struct { return kb_delp_##name(b, &k); \ } -#define __KB_ITR(name, key_t) \ - static inline void kb_itr_first_##name(kbtree_##name##_t *b, kbitr_t *itr) \ +#define __KB_ITR(name, key_t, kbnode_t) \ + static inline void kb_itr_first_##name(kbtree_##name##_t *b, kbitr_##name##_t *itr) \ { \ itr->p = 0; \ if (b->n_keys == 0) return; \ @@ -334,7 +326,7 @@ typedef struct { itr->p->x = __KB_PTR(b, x)[0]; itr->p->i = 0; \ } \ } \ - static inline int kb_itr_next_##name(kbtree_##name##_t *b, kbitr_t *itr) \ + static inline int kb_itr_next_##name(kbtree_##name##_t *b, kbitr_##name##_t *itr) \ { \ if (itr->p < itr->stack) return 0; \ for (;;) { \ @@ -349,7 +341,7 @@ typedef struct { if (itr->p->x && itr->p->i < itr->p->x->n) return 1; \ } \ } \ - static inline int kb_itr_prev_##name(kbtree_##name##_t *b, kbitr_t *itr) \ + static inline int kb_itr_prev_##name(kbtree_##name##_t *b, kbitr_##name##_t *itr) \ { \ if (itr->p < itr->stack) return 0; \ for (;;) { \ @@ -364,7 +356,7 @@ typedef struct { if (itr->p->x && itr->p->i >= 0) return 1; \ } \ } \ - static int kb_itr_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k, kbitr_t *itr) \ + static int kb_itr_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k, kbitr_##name##_t *itr) \ { \ int i, r = 0; \ itr->p = itr->stack; \ @@ -379,33 +371,37 @@ typedef struct { } \ return 0; \ } \ - static int kb_itr_get_##name(kbtree_##name##_t *b, const key_t k, kbitr_t *itr) \ + static int kb_itr_get_##name(kbtree_##name##_t *b, const key_t k, kbitr_##name##_t *itr) \ { \ return kb_itr_getp_##name(b,&k,itr); \ } \ - static inline void kb_del_itr_##name(kbtree_##name##_t *b, kbitr_t *itr) \ + static inline void kb_del_itr_##name(kbtree_##name##_t *b, kbitr_##name##_t *itr) \ { \ - key_t k = kb_itr_key(key_t, itr); \ + const key_t k = kb_itr_key(itr); \ kb_delp_##name(b, &k); \ kb_itr_getp_##name(b, &k, itr); \ } +#define KBTREE_INIT(name, key_t, __cmp, T) \ + KBTREE_INIT_IMPL(name, key_t, kbnode_##name##_t, __cmp, T, (sizeof(kbnode_##name##_t)+(2*T)*sizeof(void *))) + -#define KBTREE_INIT(name, key_t, __cmp) \ - __KB_TREE_T(name) \ - __KB_INIT(name, key_t) \ - __KB_GET_AUX1(name, key_t, __cmp) \ - __KB_GET(name, key_t) \ - __KB_INTERVAL(name, key_t) \ - __KB_PUT(name, key_t, __cmp) \ - __KB_DEL(name, key_t) \ - __KB_ITR(name, key_t) +#define KBTREE_INIT_IMPL(name, key_t, kbnode_t, __cmp, T, ILEN) \ + __KB_TREE_T(name, key_t, T) \ + __KB_INIT(name, key_t, kbnode_t, T, ILEN) \ + __KB_GET_AUX1(name, key_t, kbnode_t, __cmp) \ + __KB_GET(name, key_t, kbnode_t) \ + __KB_INTERVAL(name, key_t, kbnode_t) \ + __KB_PUT(name, key_t, kbnode_t, __cmp, T, ILEN) \ + __KB_DEL(name, key_t, kbnode_t, T) \ + __KB_ITR(name, key_t, kbnode_t) #define KB_DEFAULT_SIZE 512 #define kbtree_t(name) kbtree_##name##_t -#define kb_init(name, s) kb_init_##name(s) -#define kb_destroy(name, b) __kb_destroy(b) +#define kbitr_t(name) kbitr_##name##_t +#define kb_init(name) kb_init_##name() +#define kb_destroy(name, b) __kb_destroy(kbnode_##name##_t, b) #define kb_get(name, b, k) kb_get_##name(b, k) #define kb_put(name, b, k) kb_put_##name(b, k) #define kb_del(name, b, k) kb_del_##name(b, k) @@ -421,7 +417,7 @@ typedef struct { #define kb_itr_next(name, b, i) kb_itr_next_##name(b, i) #define kb_itr_prev(name, b, i) kb_itr_prev_##name(b, i) #define kb_del_itr(name, b, i) kb_del_itr_##name(b, i) -#define kb_itr_key(type, itr) __KB_KEY(type, (itr)->p->x)[(itr)->p->i] +#define kb_itr_key(itr) __KB_KEY(dummy, (itr)->p->x)[(itr)->p->i] #define kb_itr_valid(itr) ((itr)->p >= (itr)->stack) #define kb_size(b) ((b)->n_keys) @@ -431,6 +427,8 @@ typedef struct { /* The following is *DEPRECATED*!!! Use the iterator interface instead! */ +#if 0 + typedef struct { kbnode_t *x; int i; @@ -467,4 +465,6 @@ typedef struct { (ret) = __KB_KEY(key_t, __x)[0]; \ } while (0) +#endif + #endif // NVIM_LIB_KBTREE_H -- cgit From 14e19b8aaf458270ec94deb941be8ee78706851a Mon Sep 17 00:00:00 2001 From: Björn Linse Date: Sun, 28 Aug 2016 13:01:33 +0200 Subject: kbtree: eliminate unneccesary heap allocation --- src/nvim/buffer.c | 57 +++++++++++++++++++------------------------------- src/nvim/buffer_defs.h | 2 +- src/nvim/lib/kbtree.h | 52 ++++++++++++++++++++++----------------------- 3 files changed, 49 insertions(+), 62 deletions(-) (limited to 'src') diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c index 26dc07e4bc..fc28b0de70 100644 --- a/src/nvim/buffer.c +++ b/src/nvim/buffer.c @@ -5201,11 +5201,8 @@ int bufhl_add_hl(buf_T *buf, // no highlight group or invalid line, just return src_id return src_id; } - if (!buf->b_bufhl_info) { - buf->b_bufhl_info = kb_init(bufhl); - } - BufhlLine *lineinfo = bufhl_tree_ref(buf->b_bufhl_info, lnum, true); + BufhlLine *lineinfo = bufhl_tree_ref(&buf->b_bufhl_info, lnum, true); bufhl_hl_item_T *hlentry = kv_pushp(lineinfo->items); hlentry->src_id = src_id; @@ -5229,25 +5226,23 @@ int bufhl_add_hl(buf_T *buf, void bufhl_clear_line_range(buf_T *buf, int src_id, linenr_T line_start, - linenr_T line_end) { - if (!buf->b_bufhl_info) { - return; - } + linenr_T line_end) +{ linenr_T first_changed = MAXLNUM, last_changed = -1; kbitr_t(bufhl) itr; BufhlLine *l, t = {line_start}; - if (!kb_itr_get(bufhl, buf->b_bufhl_info, &t, &itr)) { - kb_itr_next(bufhl, buf->b_bufhl_info, &itr); + if (!kb_itr_get(bufhl, &buf->b_bufhl_info, &t, &itr)) { + kb_itr_next(bufhl, &buf->b_bufhl_info, &itr); } - for (; kb_itr_valid(&itr); kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { + for (; kb_itr_valid(&itr); kb_itr_next(bufhl, &buf->b_bufhl_info, &itr)) { l = kb_itr_key(&itr); linenr_T line = l->line; if (line > line_end) { break; } if (line_start <= line && line <= line_end) { - BufhlLineStatus status = bufhl_clear_line(buf->b_bufhl_info, src_id, line); + BufhlLineStatus status = bufhl_clear_line(l, src_id, line); if (status != kBLSUnchanged) { if (line > last_changed) { last_changed = line; @@ -5257,7 +5252,8 @@ void bufhl_clear_line_range(buf_T *buf, } } if (status == kBLSDeleted) { - kb_del_itr(bufhl, buf->b_bufhl_info, &itr); + kb_del_itr(bufhl, &buf->b_bufhl_info, &itr); + xfree(l); } } } @@ -5273,10 +5269,9 @@ void bufhl_clear_line_range(buf_T *buf, /// @param bufhl_info The highlight info for the buffer /// @param src_id Highlight source group to clear, or -1 to clear all groups. /// @param lnum Linenr where the highlight should be cleared -static BufhlLineStatus bufhl_clear_line(bufhl_info_T *bufhl_info, int src_id, +static BufhlLineStatus bufhl_clear_line(BufhlLine *lineinfo, int src_id, linenr_T lnum) { - BufhlLine *lineinfo = bufhl_tree_ref(bufhl_info, lnum, false); size_t oldsize = kv_size(lineinfo->items); if (src_id < 0) { kv_size(lineinfo->items) = 0; @@ -5303,12 +5298,8 @@ static BufhlLineStatus bufhl_clear_line(bufhl_info_T *bufhl_info, int src_id, /// Remove all highlights and free the highlight data void bufhl_clear_all(buf_T *buf) { - if (!buf->b_bufhl_info) { - return; - } bufhl_clear_line_range(buf, -1, 1, MAXLNUM); - kb_destroy(bufhl, buf->b_bufhl_info); - buf->b_bufhl_info = NULL; + kb_destroy(bufhl, (&buf->b_bufhl_info)); } /// Adjust a placed highlight for inserted/deleted lines. @@ -5316,24 +5307,23 @@ void bufhl_mark_adjust(buf_T* buf, linenr_T line1, linenr_T line2, long amount, - long amount_after) { - if (!buf->b_bufhl_info) { - return; - } + long amount_after) +{ // XXX: does not support move // we need to detect this case and kbitr_t(bufhl) itr; BufhlLine *l, t = {line1}; - if (!kb_itr_get(bufhl, buf->b_bufhl_info, &t, &itr)) { - kb_itr_next(bufhl, buf->b_bufhl_info, &itr); + if (!kb_itr_get(bufhl, &buf->b_bufhl_info, &t, &itr)) { + kb_itr_next(bufhl, &buf->b_bufhl_info, &itr); } - for (; kb_itr_valid(&itr); kb_itr_next(bufhl, buf->b_bufhl_info, &itr)) { + for (; kb_itr_valid(&itr); kb_itr_next(bufhl, &buf->b_bufhl_info, &itr)) { l = kb_itr_key(&itr); if (l->line >= line1 && l->line <= line2) { if (amount == MAXLNUM) { - if (bufhl_clear_line(buf->b_bufhl_info, -1, l->line) == kBLSDeleted) { - kb_del_itr(bufhl, buf->b_bufhl_info, &itr); + if (bufhl_clear_line(l, -1, l->line) == kBLSDeleted) { + kb_del_itr(bufhl, &buf->b_bufhl_info, &itr); + xfree(l); } else { assert(false); } @@ -5356,12 +5346,9 @@ void bufhl_mark_adjust(buf_T* buf, /// @param lnum The line number /// @param[out] info The highligts for the line /// @return true if there was highlights to display -bool bufhl_start_line(buf_T *buf, linenr_T lnum, bufhl_lineinfo_T *info) { - if (!buf->b_bufhl_info) { - return false; - } - - BufhlLine *lineinfo = bufhl_tree_ref(buf->b_bufhl_info, lnum, false); +bool bufhl_start_line(buf_T *buf, linenr_T lnum, bufhl_lineinfo_T *info) +{ + BufhlLine *lineinfo = bufhl_tree_ref(&buf->b_bufhl_info, lnum, false); if (!lineinfo) { return false; } diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h index adced27f58..c027dc4512 100644 --- a/src/nvim/buffer_defs.h +++ b/src/nvim/buffer_defs.h @@ -760,7 +760,7 @@ struct file_buffer { int b_mapped_ctrl_c; // modes where CTRL-C is mapped - bufhl_info_T *b_bufhl_info; // buffer stored highlights + bufhl_info_T b_bufhl_info; // buffer stored highlights }; /* diff --git a/src/nvim/lib/kbtree.h b/src/nvim/lib/kbtree.h index bfea068206..d72c1d5690 100644 --- a/src/nvim/lib/kbtree.h +++ b/src/nvim/lib/kbtree.h @@ -40,18 +40,19 @@ #define __KB_PTR(btr, x) (x->ptr) #define __KB_TREE_T(name,key_t,T) \ -typedef struct kbnode_##name##_s kbnode_##name##_t; \ -struct kbnode_##name##_s { \ - int32_t n; \ - bool is_internal; \ - key_t key[2*T-1]; \ - kbnode_##name##_t *ptr[0]; \ -} ; \ - \ - typedef struct { \ - kbnode_##name##_t *root; \ - int n_keys, n_nodes; \ - } kbtree_##name##_t; \ + typedef struct kbnode_##name##_s kbnode_##name##_t; \ + struct kbnode_##name##_s { \ + int32_t n; \ + bool is_internal; \ + key_t key[2*T-1]; \ + kbnode_##name##_t *ptr[0]; \ + } ; \ + \ + typedef struct { \ + kbnode_##name##_t *root; \ + int n_keys, n_nodes; \ + } kbtree_##name##_t; \ + \ typedef struct { \ kbnode_##name##_t *x; \ int i; \ @@ -61,21 +62,11 @@ struct kbnode_##name##_s { \ } kbitr_##name##_t; \ -#define __KB_INIT(name, key_t, kbnode_t, T, ILEN) \ - static inline kbtree_##name##_t *kb_init_##name() \ - { \ - kbtree_##name##_t *b; \ - b = (kbtree_##name##_t*)xcalloc(1, sizeof(kbtree_##name##_t)); \ - b->root = (kbnode_t*)xcalloc(1, ILEN); \ - ++b->n_nodes; \ - return b; \ - } \ - #define __kb_destroy(kbnode_t,b) do { \ int i; \ unsigned int max = 8; \ kbnode_t *x, **top, **stack = 0; \ - if (b) { \ + if (b->root) { \ top = stack = (kbnode_t**)xcalloc(max, sizeof(kbnode_t*)); \ *top++ = (b)->root; \ while (top != stack) { \ @@ -93,7 +84,7 @@ struct kbnode_##name##_s { \ xfree(x); \ } \ } \ - xfree(b); xfree(stack); \ + xfree(stack); \ } while (0) #define __KB_GET_AUX1(name, key_t, kbnode_t, __cmp) \ @@ -115,6 +106,9 @@ struct kbnode_##name##_s { \ #define __KB_GET(name, key_t, kbnode_t) \ static key_t *kb_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ { \ + if (!b->root) { \ + return 0; \ + } \ int i, r = 0; \ kbnode_t *x = b->root; \ while (x) { \ @@ -133,6 +127,9 @@ struct kbnode_##name##_s { \ #define __KB_INTERVAL(name, key_t, kbnode_t) \ static void kb_intervalp_##name(kbtree_##name##_t *b, const key_t * __restrict k, key_t **lower, key_t **upper) \ { \ + if (!b->root) { \ + return; \ + } \ int i, r = 0; \ kbnode_t *x = b->root; \ *lower = *upper = 0; \ @@ -194,6 +191,10 @@ struct kbnode_##name##_s { \ } \ static key_t *kb_putp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ { \ + if (!b->root) { \ + b->root = (kbnode_t*)xcalloc(1, ILEN); \ + ++b->n_nodes; \ + } \ kbnode_t *r, *s; \ ++b->n_keys; \ r = b->root; \ @@ -358,6 +359,7 @@ struct kbnode_##name##_s { \ } \ static int kb_itr_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k, kbitr_##name##_t *itr) \ { \ + if (b->n_keys == 0) return 0; \ int i, r = 0; \ itr->p = itr->stack; \ itr->p->x = b->root; \ @@ -388,7 +390,6 @@ struct kbnode_##name##_s { \ #define KBTREE_INIT_IMPL(name, key_t, kbnode_t, __cmp, T, ILEN) \ __KB_TREE_T(name, key_t, T) \ - __KB_INIT(name, key_t, kbnode_t, T, ILEN) \ __KB_GET_AUX1(name, key_t, kbnode_t, __cmp) \ __KB_GET(name, key_t, kbnode_t) \ __KB_INTERVAL(name, key_t, kbnode_t) \ @@ -400,7 +401,6 @@ struct kbnode_##name##_s { \ #define kbtree_t(name) kbtree_##name##_t #define kbitr_t(name) kbitr_##name##_t -#define kb_init(name) kb_init_##name() #define kb_destroy(name, b) __kb_destroy(kbnode_##name##_t, b) #define kb_get(name, b, k) kb_get_##name(b, k) #define kb_put(name, b, k) kb_put_##name(b, k) -- cgit From 28a549d597a286330ba87ff4fffe1e2d09e0f611 Mon Sep 17 00:00:00 2001 From: Björn Linse Date: Sun, 28 Aug 2016 13:26:01 +0200 Subject: kbtree: make warning free and delete deprecated macros --- src/clint.py | 2 ++ src/nvim/buffer.c | 23 +++++++------ src/nvim/bufhl_defs.h | 3 +- src/nvim/lib/kbtree.h | 95 +++++++++++++++++++-------------------------------- 4 files changed, 53 insertions(+), 70 deletions(-) (limited to 'src') diff --git a/src/clint.py b/src/clint.py index e6bedd37dc..69a061d2ab 100755 --- a/src/clint.py +++ b/src/clint.py @@ -2529,6 +2529,8 @@ def CheckSpacing(filename, clean_lines, linenum, nesting_state, error): r'(?line = line; - // p->items zero initialized + BufhlLine *p = xmalloc(sizeof(*p)); + *p = (BufhlLine)BUFHLLINE_INIT(line); kb_put(bufhl, b, p); return p; } @@ -5231,7 +5234,7 @@ void bufhl_clear_line_range(buf_T *buf, linenr_T first_changed = MAXLNUM, last_changed = -1; kbitr_t(bufhl) itr; - BufhlLine *l, t = {line_start}; + BufhlLine *l, t = BUFHLLINE_INIT(line_start); if (!kb_itr_get(bufhl, &buf->b_bufhl_info, &t, &itr)) { kb_itr_next(bufhl, &buf->b_bufhl_info, &itr); } @@ -5313,7 +5316,7 @@ void bufhl_mark_adjust(buf_T* buf, // we need to detect this case and kbitr_t(bufhl) itr; - BufhlLine *l, t = {line1}; + BufhlLine *l, t = BUFHLLINE_INIT(line1); if (!kb_itr_get(bufhl, &buf->b_bufhl_info, &t, &itr)) { kb_itr_next(bufhl, &buf->b_bufhl_info, &itr); } diff --git a/src/nvim/bufhl_defs.h b/src/nvim/bufhl_defs.h index 0d2f9c90d0..ddf048dd82 100644 --- a/src/nvim/bufhl_defs.h +++ b/src/nvim/bufhl_defs.h @@ -21,6 +21,7 @@ typedef struct { linenr_T line; bufhl_vec_T items; } BufhlLine; +#define BUFHLLINE_INIT(l) { l, KV_INITIAL_VALUE } typedef struct { bufhl_vec_T entries; @@ -28,7 +29,7 @@ typedef struct { colnr_T valid_to; } bufhl_lineinfo_T; -#define BUFHL_CMP(a, b) (((a)->line - (b)->line)) +#define BUFHL_CMP(a, b) ((int)(((a)->line - (b)->line))) KBTREE_INIT(bufhl, BufhlLine *, BUFHL_CMP, 10) typedef kbtree_t(bufhl) bufhl_info_T; #endif // NVIM_BUFHL_DEFS_H diff --git a/src/nvim/lib/kbtree.h b/src/nvim/lib/kbtree.h index d72c1d5690..f836dec48f 100644 --- a/src/nvim/lib/kbtree.h +++ b/src/nvim/lib/kbtree.h @@ -45,7 +45,7 @@ int32_t n; \ bool is_internal; \ key_t key[2*T-1]; \ - kbnode_##name##_t *ptr[0]; \ + kbnode_##name##_t *ptr[]; \ } ; \ \ typedef struct { \ @@ -88,7 +88,7 @@ } while (0) #define __KB_GET_AUX1(name, key_t, kbnode_t, __cmp) \ - static inline int __kb_getp_aux_##name(const kbnode_t * __restrict x, const key_t * __restrict k, int *r) \ + static inline int __kb_getp_aux_##name(const kbnode_t * __restrict x, key_t * __restrict k, int *r) \ { \ int tr, *rr, begin = 0, end = x->n; \ if (x->n == 0) return -1; \ @@ -104,7 +104,7 @@ } #define __KB_GET(name, key_t, kbnode_t) \ - static key_t *kb_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ + static key_t *kb_getp_##name(kbtree_##name##_t *b, key_t * __restrict k) \ { \ if (!b->root) { \ return 0; \ @@ -119,13 +119,13 @@ } \ return 0; \ } \ - static inline key_t *kb_get_##name(kbtree_##name##_t *b, const key_t k) \ + static inline key_t *kb_get_##name(kbtree_##name##_t *b, key_t k) \ { \ return kb_getp_##name(b, &k); \ } #define __KB_INTERVAL(name, key_t, kbnode_t) \ - static void kb_intervalp_##name(kbtree_##name##_t *b, const key_t * __restrict k, key_t **lower, key_t **upper) \ + static inline void kb_intervalp_##name(kbtree_##name##_t *b, key_t * __restrict k, key_t **lower, key_t **upper) \ { \ if (!b->root) { \ return; \ @@ -145,14 +145,14 @@ x = __KB_PTR(b, x)[i + 1]; \ } \ } \ - static inline void kb_interval_##name(kbtree_##name##_t *b, const key_t k, key_t **lower, key_t **upper) \ + static inline void kb_interval_##name(kbtree_##name##_t *b, key_t k, key_t **lower, key_t **upper) \ { \ kb_intervalp_##name(b, &k, lower, upper); \ } #define __KB_PUT(name, key_t, kbnode_t, __cmp, T, ILEN) \ /* x must be an internal node */ \ - static void __kb_split_##name(kbtree_##name##_t *b, kbnode_t *x, int i, kbnode_t *y) \ + static inline void __kb_split_##name(kbtree_##name##_t *b, kbnode_t *x, int i, kbnode_t *y) \ { \ kbnode_t *z; \ z = (kbnode_t*)xcalloc(1, y->is_internal? ILEN : sizeof(kbnode_##name##_t)); \ @@ -168,7 +168,7 @@ __KB_KEY(key_t, x)[i] = __KB_KEY(key_t, y)[T - 1]; \ ++x->n; \ } \ - static key_t *__kb_putp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k) \ + static inline key_t *__kb_putp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, key_t * __restrict k) \ { \ int i = x->n - 1; \ key_t *ret; \ @@ -189,7 +189,7 @@ } \ return ret; \ } \ - static key_t *kb_putp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ + static inline key_t *kb_putp_##name(kbtree_##name##_t *b, key_t * __restrict k) \ { \ if (!b->root) { \ b->root = (kbnode_t*)xcalloc(1, ILEN); \ @@ -208,14 +208,14 @@ } \ return __kb_putp_aux_##name(b, r, k); \ } \ - static inline void kb_put_##name(kbtree_##name##_t *b, const key_t k) \ + static inline void kb_put_##name(kbtree_##name##_t *b, key_t k) \ { \ kb_putp_##name(b, &k); \ } #define __KB_DEL(name, key_t, kbnode_t, T) \ - static key_t __kb_delp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, const key_t * __restrict k, int s) \ + static inline key_t __kb_delp_aux_##name(kbtree_##name##_t *b, kbnode_t *x, key_t * __restrict k, int s) \ { \ int yn, zn, i, r = 0; \ kbnode_t *xp, *y, *z; \ @@ -295,7 +295,7 @@ } \ return __kb_delp_aux_##name(b, xp, k, s); \ } \ - static key_t kb_delp_##name(kbtree_##name##_t *b, const key_t * __restrict k) \ + static inline key_t kb_delp_##name(kbtree_##name##_t *b, key_t * __restrict k) \ { \ kbnode_t *x; \ key_t ret; \ @@ -309,7 +309,7 @@ } \ return ret; \ } \ - static inline key_t kb_del_##name(kbtree_##name##_t *b, const key_t k) \ + static inline key_t kb_del_##name(kbtree_##name##_t *b, key_t k) \ { \ return kb_delp_##name(b, &k); \ } @@ -357,7 +357,7 @@ if (itr->p->x && itr->p->i >= 0) return 1; \ } \ } \ - static int kb_itr_getp_##name(kbtree_##name##_t *b, const key_t * __restrict k, kbitr_##name##_t *itr) \ + static inline int kb_itr_getp_##name(kbtree_##name##_t *b, key_t * __restrict k, kbitr_##name##_t *itr) \ { \ if (b->n_keys == 0) return 0; \ int i, r = 0; \ @@ -373,13 +373,13 @@ } \ return 0; \ } \ - static int kb_itr_get_##name(kbtree_##name##_t *b, const key_t k, kbitr_##name##_t *itr) \ + static inline int kb_itr_get_##name(kbtree_##name##_t *b, key_t k, kbitr_##name##_t *itr) \ { \ return kb_itr_getp_##name(b,&k,itr); \ } \ static inline void kb_del_itr_##name(kbtree_##name##_t *b, kbitr_##name##_t *itr) \ { \ - const key_t k = kb_itr_key(itr); \ + key_t k = kb_itr_key(itr); \ kb_delp_##name(b, &k); \ kb_itr_getp_##name(b, &k, itr); \ } @@ -387,15 +387,34 @@ #define KBTREE_INIT(name, key_t, __cmp, T) \ KBTREE_INIT_IMPL(name, key_t, kbnode_##name##_t, __cmp, T, (sizeof(kbnode_##name##_t)+(2*T)*sizeof(void *))) +#if (!defined(__clang__) && !defined(__INTEL_COMPILER)) && (__GNUC__ > 4 ) + +// The index trickery shouldn't be UB anymore, +// still it is to much for gcc:s -Werror=array-bounds +# define __KB_PRAGMA_START \ + _Pragma("GCC diagnostic push") \ + _Pragma("GCC diagnostic ignored \"-Warray-bounds\"") + +# define __KB_PRAGMA_END \ + _Pragma("GCC diagnostic pop") \ + +#else + +# define __KB_PRAGMA_START +# define __KB_PRAGMA_END + +#endif #define KBTREE_INIT_IMPL(name, key_t, kbnode_t, __cmp, T, ILEN) \ + __KB_PRAGMA_START \ __KB_TREE_T(name, key_t, T) \ __KB_GET_AUX1(name, key_t, kbnode_t, __cmp) \ __KB_GET(name, key_t, kbnode_t) \ __KB_INTERVAL(name, key_t, kbnode_t) \ __KB_PUT(name, key_t, kbnode_t, __cmp, T, ILEN) \ __KB_DEL(name, key_t, kbnode_t, T) \ - __KB_ITR(name, key_t, kbnode_t) + __KB_ITR(name, key_t, kbnode_t) \ + __KB_PRAGMA_END #define KB_DEFAULT_SIZE 512 @@ -425,46 +444,4 @@ #define kb_generic_cmp(a, b) (((b) < (a)) - ((a) < (b))) #define kb_str_cmp(a, b) strcmp(a, b) -/* The following is *DEPRECATED*!!! Use the iterator interface instead! */ - -#if 0 - -typedef struct { - kbnode_t *x; - int i; -} __kbstack_t; - -#define __kb_traverse(key_t, b, __func) do { \ - int __kmax = 8; \ - __kbstack_t *__kstack, *__kp; \ - __kp = __kstack = (__kbstack_t*)calloc(__kmax, sizeof(__kbstack_t)); \ - __kp->x = (b)->root; __kp->i = 0; \ - for (;;) { \ - while (__kp->x && __kp->i <= __kp->x->n) { \ - if (__kp - __kstack == __kmax - 1) { \ - __kmax <<= 1; \ - __kstack = (__kbstack_t*)realloc(__kstack, __kmax * sizeof(__kbstack_t)); \ - __kp = __kstack + (__kmax>>1) - 1; \ - } \ - (__kp+1)->i = 0; (__kp+1)->x = __kp->x->is_internal? __KB_PTR(b, __kp->x)[__kp->i] : 0; \ - ++__kp; \ - } \ - --__kp; \ - if (__kp >= __kstack) { \ - if (__kp->x && __kp->i < __kp->x->n) __func(&__KB_KEY(key_t, __kp->x)[__kp->i]); \ - ++__kp->i; \ - } else break; \ - } \ - free(__kstack); \ - } while (0) - -#define __kb_get_first(key_t, b, ret) do { \ - kbnode_t *__x = (b)->root; \ - while (__KB_PTR(b, __x)[0] != 0) \ - __x = __KB_PTR(b, __x)[0]; \ - (ret) = __KB_KEY(key_t, __x)[0]; \ - } while (0) - -#endif - #endif // NVIM_LIB_KBTREE_H -- cgit From 7873660e1ebbb6350609f4200296fc2ac4bf3035 Mon Sep 17 00:00:00 2001 From: Björn Linse Date: Sun, 28 Aug 2016 13:32:48 +0200 Subject: bufhl: some style cleanup --- src/nvim/buffer.c | 21 +++++++++++---------- src/nvim/buffer_defs.h | 2 +- src/nvim/bufhl_defs.h | 17 ++++++++--------- src/nvim/screen.c | 2 +- 4 files changed, 21 insertions(+), 21 deletions(-) (limited to 'src') diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c index 39014d903a..ebb38fe709 100644 --- a/src/nvim/buffer.c +++ b/src/nvim/buffer.c @@ -5150,7 +5150,8 @@ void sign_mark_adjust(linenr_T line1, linenr_T line2, long amount, long amount_a /// @param line the linenumber to lookup /// @param put if true, put a new line when not found /// if false, return NULL when not found -BufhlLine *bufhl_tree_ref(kbtree_t(bufhl) *b, linenr_T line, bool put) { +BufhlLine *bufhl_tree_ref(BufhlInfo *b, linenr_T line, bool put) +{ BufhlLine t = BUFHLLINE_INIT(line); // kp_put() only works if key is absent, try get first @@ -5207,7 +5208,7 @@ int bufhl_add_hl(buf_T *buf, BufhlLine *lineinfo = bufhl_tree_ref(&buf->b_bufhl_info, lnum, true); - bufhl_hl_item_T *hlentry = kv_pushp(lineinfo->items); + BufhlItem *hlentry = kv_pushp(lineinfo->items); hlentry->src_id = src_id; hlentry->hl_id = hl_id; hlentry->start = col_start; @@ -5279,16 +5280,16 @@ static BufhlLineStatus bufhl_clear_line(BufhlLine *lineinfo, int src_id, if (src_id < 0) { kv_size(lineinfo->items) = 0; } else { - size_t newind = 0; + size_t newidx = 0; for (size_t i = 0; i < kv_size(lineinfo->items); i++) { if (kv_A(lineinfo->items, i).src_id != src_id) { - if (i != newind) { - kv_A(lineinfo->items, newind) = kv_A(lineinfo->items, i); + if (i != newidx) { + kv_A(lineinfo->items, newidx) = kv_A(lineinfo->items, i); } - newind++; + newidx++; } } - kv_size(lineinfo->items) = newind; + kv_size(lineinfo->items) = newidx; } if (kv_size(lineinfo->items) == 0) { @@ -5349,7 +5350,7 @@ void bufhl_mark_adjust(buf_T* buf, /// @param lnum The line number /// @param[out] info The highligts for the line /// @return true if there was highlights to display -bool bufhl_start_line(buf_T *buf, linenr_T lnum, bufhl_lineinfo_T *info) +bool bufhl_start_line(buf_T *buf, linenr_T lnum, BufhlLineInfo *info) { BufhlLine *lineinfo = bufhl_tree_ref(&buf->b_bufhl_info, lnum, false); if (!lineinfo) { @@ -5370,14 +5371,14 @@ bool bufhl_start_line(buf_T *buf, linenr_T lnum, bufhl_lineinfo_T *info) /// @param info The info returned by bufhl_start_line /// @param col The column to get the attr for /// @return The highilight attr to display at the column -int bufhl_get_attr(bufhl_lineinfo_T *info, colnr_T col) { +int bufhl_get_attr(BufhlLineInfo *info, colnr_T col) { if (col <= info->valid_to) { return info->current; } int attr = 0; info->valid_to = MAXCOL; for (size_t i = 0; i < kv_size(info->entries); i++) { - bufhl_hl_item_T entry = kv_A(info->entries, i); + BufhlItem entry = kv_A(info->entries, i); if (entry.start <= col && col <= entry.stop) { int entry_attr = syn_id2attr(entry.hl_id); attr = hl_combine_attr(attr, entry_attr); diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h index c027dc4512..8e928bce62 100644 --- a/src/nvim/buffer_defs.h +++ b/src/nvim/buffer_defs.h @@ -760,7 +760,7 @@ struct file_buffer { int b_mapped_ctrl_c; // modes where CTRL-C is mapped - bufhl_info_T b_bufhl_info; // buffer stored highlights + BufhlInfo b_bufhl_info; // buffer stored highlights }; /* diff --git a/src/nvim/bufhl_defs.h b/src/nvim/bufhl_defs.h index ddf048dd82..24bd6b7f29 100644 --- a/src/nvim/bufhl_defs.h +++ b/src/nvim/bufhl_defs.h @@ -4,32 +4,31 @@ #include "nvim/pos.h" #include "nvim/lib/kvec.h" #include "nvim/lib/kbtree.h" + // bufhl: buffer specific highlighting -struct bufhl_hl_item -{ +typedef struct { int src_id; int hl_id; // highlight group colnr_T start; // first column to highlight colnr_T stop; // last column to highlight -}; -typedef struct bufhl_hl_item bufhl_hl_item_T; +} BufhlItem; -typedef kvec_t(struct bufhl_hl_item) bufhl_vec_T; +typedef kvec_t(BufhlItem) BufhlItemVec; typedef struct { linenr_T line; - bufhl_vec_T items; + BufhlItemVec items; } BufhlLine; #define BUFHLLINE_INIT(l) { l, KV_INITIAL_VALUE } typedef struct { - bufhl_vec_T entries; + BufhlItemVec entries; int current; colnr_T valid_to; -} bufhl_lineinfo_T; +} BufhlLineInfo; #define BUFHL_CMP(a, b) ((int)(((a)->line - (b)->line))) KBTREE_INIT(bufhl, BufhlLine *, BUFHL_CMP, 10) -typedef kbtree_t(bufhl) bufhl_info_T; +typedef kbtree_t(bufhl) BufhlInfo; #endif // NVIM_BUFHL_DEFS_H diff --git a/src/nvim/screen.c b/src/nvim/screen.c index 3ff2a94a20..2f7fa8724f 100644 --- a/src/nvim/screen.c +++ b/src/nvim/screen.c @@ -2210,7 +2210,7 @@ win_line ( bool search_attr_from_match = false; // if search_attr is from :match bool has_bufhl = false; // this buffer has highlight matches int bufhl_attr = 0; // attributes desired by bufhl - bufhl_lineinfo_T bufhl_info; // bufhl data for this line + BufhlLineInfo bufhl_info; // bufhl data for this line /* draw_state: items that are drawn in sequence: */ #define WL_START 0 /* nothing done yet */ -- cgit From 8b375cf471359ad7632af7fa6a2298c9b7596691 Mon Sep 17 00:00:00 2001 From: Björn Linse Date: Sun, 28 Aug 2016 15:36:18 +0200 Subject: bufhl: fix move --- src/nvim/api/buffer.c | 2 +- src/nvim/buffer.c | 27 ++++++++++++++++++++++----- src/nvim/buffer_defs.h | 2 ++ src/nvim/diff.c | 2 +- src/nvim/ex_cmds.c | 34 +++++++++++++++++----------------- src/nvim/lib/kbtree.h | 6 +++++- src/nvim/mark.c | 19 ++++++++++++------- src/nvim/misc1.c | 6 +++--- src/nvim/ops.c | 2 +- src/nvim/undo.c | 8 +++++--- 10 files changed, 69 insertions(+), 39 deletions(-) (limited to 'src') diff --git a/src/nvim/api/buffer.c b/src/nvim/api/buffer.c index 94554bc4c1..82de8fd4a2 100644 --- a/src/nvim/api/buffer.c +++ b/src/nvim/api/buffer.c @@ -399,7 +399,7 @@ void nvim_buf_set_lines(uint64_t channel_id, // Only adjust marks if we managed to switch to a window that holds // the buffer, otherwise line numbers will be invalid. if (save_curbuf.br_buf == NULL) { - mark_adjust((linenr_T)start, (linenr_T)(end - 1), MAXLNUM, extra); + mark_adjust((linenr_T)start, (linenr_T)(end - 1), MAXLNUM, extra, false); } changed_lines((linenr_T)start, 0, (linenr_T)end, (long)extra); diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c index ebb38fe709..b5ca6543c5 100644 --- a/src/nvim/buffer.c +++ b/src/nvim/buffer.c @@ -5304,6 +5304,9 @@ void bufhl_clear_all(buf_T *buf) { bufhl_clear_line_range(buf, -1, 1, MAXLNUM); kb_destroy(bufhl, (&buf->b_bufhl_info)); + kb_init(&buf->b_bufhl_info); + kv_destroy(buf->b_bufhl_move_space); + kv_init(buf->b_bufhl_move_space); } /// Adjust a placed highlight for inserted/deleted lines. @@ -5311,19 +5314,32 @@ void bufhl_mark_adjust(buf_T* buf, linenr_T line1, linenr_T line2, long amount, - long amount_after) + long amount_after, + bool end_temp) { - // XXX: does not support move - // we need to detect this case and - kbitr_t(bufhl) itr; BufhlLine *l, t = BUFHLLINE_INIT(line1); + if (end_temp && amount < 0) { + // Move all items from b_bufhl_move_space to the btree. + for (size_t i = 0; i < kv_size(buf->b_bufhl_move_space); i++) { + l = kv_A(buf->b_bufhl_move_space, i); + l->line += amount; + kb_put(bufhl, &buf->b_bufhl_info, l); + } + kv_size(buf->b_bufhl_move_space) = 0; + return; + } + if (!kb_itr_get(bufhl, &buf->b_bufhl_info, &t, &itr)) { kb_itr_next(bufhl, &buf->b_bufhl_info, &itr); } for (; kb_itr_valid(&itr); kb_itr_next(bufhl, &buf->b_bufhl_info, &itr)) { l = kb_itr_key(&itr); if (l->line >= line1 && l->line <= line2) { + if (end_temp && amount > 0) { + kb_del_itr(bufhl, &buf->b_bufhl_info, &itr); + kv_push(buf->b_bufhl_move_space, l); + } if (amount == MAXLNUM) { if (bufhl_clear_line(l, -1, l->line) == kBLSDeleted) { kb_del_itr(bufhl, &buf->b_bufhl_info, &itr); @@ -5371,7 +5387,8 @@ bool bufhl_start_line(buf_T *buf, linenr_T lnum, BufhlLineInfo *info) /// @param info The info returned by bufhl_start_line /// @param col The column to get the attr for /// @return The highilight attr to display at the column -int bufhl_get_attr(BufhlLineInfo *info, colnr_T col) { +int bufhl_get_attr(BufhlLineInfo *info, colnr_T col) +{ if (col <= info->valid_to) { return info->current; } diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h index 8e928bce62..559dffb945 100644 --- a/src/nvim/buffer_defs.h +++ b/src/nvim/buffer_defs.h @@ -761,6 +761,8 @@ struct file_buffer { int b_mapped_ctrl_c; // modes where CTRL-C is mapped BufhlInfo b_bufhl_info; // buffer stored highlights + + kvec_t(BufhlLine *) b_bufhl_move_space; // temporary space for highlights }; /* diff --git a/src/nvim/diff.c b/src/nvim/diff.c index 0bd3f59cf2..7da6665cb7 100644 --- a/src/nvim/diff.c +++ b/src/nvim/diff.c @@ -2311,7 +2311,7 @@ void ex_diffgetput(exarg_T *eap) // Adjust marks. This will change the following entries! if (added != 0) { - mark_adjust(lnum, lnum + count - 1, (long)MAXLNUM, (long)added); + mark_adjust(lnum, lnum + count - 1, (long)MAXLNUM, (long)added, false); if (curwin->w_cursor.lnum >= lnum) { // Adjust the cursor position if it's in/after the changed // lines. diff --git a/src/nvim/ex_cmds.c b/src/nvim/ex_cmds.c index 008a44b43b..8dcb3ac449 100644 --- a/src/nvim/ex_cmds.c +++ b/src/nvim/ex_cmds.c @@ -597,9 +597,10 @@ void ex_sort(exarg_T *eap) // Adjust marks for deleted (or added) lines and prepare for displaying. deleted = (long)(count - (lnum - eap->line2)); if (deleted > 0) { - mark_adjust(eap->line2 - deleted, eap->line2, (long)MAXLNUM, -deleted); + mark_adjust(eap->line2 - deleted, eap->line2, (long)MAXLNUM, -deleted, + false); } else if (deleted < 0) { - mark_adjust(eap->line2, MAXLNUM, -deleted, 0L); + mark_adjust(eap->line2, MAXLNUM, -deleted, 0L, false); } changed_lines(eap->line1, 0, eap->line2 + 1, -deleted); @@ -794,9 +795,9 @@ int do_move(linenr_T line1, linenr_T line2, linenr_T dest) * their final destination at the new text position -- webb */ last_line = curbuf->b_ml.ml_line_count; - mark_adjust_nofold(line1, line2, last_line - line2, 0L); + mark_adjust_nofold(line1, line2, last_line - line2, 0L, true); if (dest >= line2) { - mark_adjust_nofold(line2 + 1, dest, -num_lines, 0L); + mark_adjust_nofold(line2 + 1, dest, -num_lines, 0L, false); FOR_ALL_TAB_WINDOWS(tab, win) { if (win->w_buffer == curbuf) { foldMoveRange(&win->w_folds, line1, line2, dest); @@ -805,7 +806,7 @@ int do_move(linenr_T line1, linenr_T line2, linenr_T dest) curbuf->b_op_start.lnum = dest - num_lines + 1; curbuf->b_op_end.lnum = dest; } else { - mark_adjust_nofold(dest + 1, line1 - 1, num_lines, 0L); + mark_adjust_nofold(dest + 1, line1 - 1, num_lines, 0L, false); FOR_ALL_TAB_WINDOWS(tab, win) { if (win->w_buffer == curbuf) { foldMoveRange(&win->w_folds, dest + 1, line1 - 1, line2); @@ -816,7 +817,7 @@ int do_move(linenr_T line1, linenr_T line2, linenr_T dest) } curbuf->b_op_start.col = curbuf->b_op_end.col = 0; mark_adjust_nofold(last_line - num_lines + 1, last_line, - -(last_line - dest - extra), 0L); + -(last_line - dest - extra), 0L, true); /* * Now we delete the original text -- webb @@ -1212,15 +1213,14 @@ static void do_filter( if (do_in) { if (cmdmod.keepmarks || vim_strchr(p_cpo, CPO_REMMARK) == NULL) { - if (read_linecount >= linecount) - /* move all marks from old lines to new lines */ - mark_adjust(line1, line2, linecount, 0L); - else { - /* move marks from old lines to new lines, delete marks - * that are in deleted lines */ - mark_adjust(line1, line1 + read_linecount - 1, - linecount, 0L); - mark_adjust(line1 + read_linecount, line2, MAXLNUM, 0L); + if (read_linecount >= linecount) { + // move all marks from old lines to new lines + mark_adjust(line1, line2, linecount, 0L, false); + } else { + // move marks from old lines to new lines, delete marks + // that are in deleted lines + mark_adjust(line1, line1 + read_linecount - 1, linecount, 0L, false); + mark_adjust(line1 + read_linecount, line2, MAXLNUM, 0L, false); } } @@ -3758,7 +3758,7 @@ static buf_T *do_sub(exarg_T *eap, proftime_T timeout) *p1 = NUL; // truncate up to the CR ml_append(lnum - 1, new_start, (colnr_T)(p1 - new_start + 1), false); - mark_adjust(lnum + 1, (linenr_T)MAXLNUM, 1L, 0L); + mark_adjust(lnum + 1, (linenr_T)MAXLNUM, 1L, 0L, false); if (subflags.do_ask) { appended_lines(lnum - 1, 1L); } else { @@ -3847,7 +3847,7 @@ skip: for (i = 0; i < nmatch_tl; ++i) ml_delete(lnum, (int)FALSE); mark_adjust(lnum, lnum + nmatch_tl - 1, - (long)MAXLNUM, -nmatch_tl); + (long)MAXLNUM, -nmatch_tl, false); if (subflags.do_ask) { deleted_lines(lnum, nmatch_tl); } diff --git a/src/nvim/lib/kbtree.h b/src/nvim/lib/kbtree.h index f836dec48f..a3943054e6 100644 --- a/src/nvim/lib/kbtree.h +++ b/src/nvim/lib/kbtree.h @@ -359,7 +359,10 @@ } \ static inline int kb_itr_getp_##name(kbtree_##name##_t *b, key_t * __restrict k, kbitr_##name##_t *itr) \ { \ - if (b->n_keys == 0) return 0; \ + if (b->n_keys == 0) { \ + itr->p = NULL; \ + return 0; \ + } \ int i, r = 0; \ itr->p = itr->stack; \ itr->p->x = b->root; \ @@ -420,6 +423,7 @@ #define kbtree_t(name) kbtree_##name##_t #define kbitr_t(name) kbitr_##name##_t +#define kb_init(b) ((b)->n_keys = (b)->n_nodes = 0, (b)->root = 0) #define kb_destroy(name, b) __kb_destroy(kbnode_##name##_t, b) #define kb_get(name, b, k) kb_get_##name(b, k) #define kb_put(name, b, k) kb_put_##name(b, k) diff --git a/src/nvim/mark.c b/src/nvim/mark.c index 675fe4d57f..7889fabd45 100644 --- a/src/nvim/mark.c +++ b/src/nvim/mark.c @@ -888,9 +888,13 @@ void ex_changes(exarg_T *eap) * Example: Insert two lines below 55: mark_adjust(56, MAXLNUM, 2, 0); * or: mark_adjust(56, 55, MAXLNUM, 2); */ -void mark_adjust(linenr_T line1, linenr_T line2, long amount, long amount_after) +void mark_adjust(linenr_T line1, + linenr_T line2, + long amount, + long amount_after, + bool end_temp) { - mark_adjust_internal(line1, line2, amount, amount_after, true); + mark_adjust_internal(line1, line2, amount, amount_after, true, end_temp); } // mark_adjust_nofold() does the same as mark_adjust() but without adjusting @@ -899,13 +903,14 @@ void mark_adjust(linenr_T line1, linenr_T line2, long amount, long amount_after) // calling foldMarkAdjust() with arguments line1, line2, amount, amount_after, // for an example of why this may be necessary, see do_move(). void mark_adjust_nofold(linenr_T line1, linenr_T line2, long amount, - long amount_after) + long amount_after, bool end_temp) { - mark_adjust_internal(line1, line2, amount, amount_after, false); + mark_adjust_internal(line1, line2, amount, amount_after, false, end_temp); } -static void mark_adjust_internal(linenr_T line1, linenr_T line2, long amount, - long amount_after, bool adjust_folds) +static void mark_adjust_internal(linenr_T line1, linenr_T line2, + long amount, long amount_after, + bool adjust_folds, bool end_temp) { int i; int fnum = curbuf->b_fnum; @@ -954,7 +959,7 @@ static void mark_adjust_internal(linenr_T line1, linenr_T line2, long amount, } sign_mark_adjust(line1, line2, amount, amount_after); - bufhl_mark_adjust(curbuf, line1, line2, amount, amount_after); + bufhl_mark_adjust(curbuf, line1, line2, amount, amount_after, end_temp); } /* previous context mark */ diff --git a/src/nvim/misc1.c b/src/nvim/misc1.c index 9630656f3f..835b9c7b20 100644 --- a/src/nvim/misc1.c +++ b/src/nvim/misc1.c @@ -751,7 +751,7 @@ open_line ( // Skip mark_adjust when adding a line after the last one, there can't // be marks there. if (curwin->w_cursor.lnum + 1 < curbuf->b_ml.ml_line_count) { - mark_adjust(curwin->w_cursor.lnum + 1, (linenr_T)MAXLNUM, 1L, 0L); + mark_adjust(curwin->w_cursor.lnum + 1, (linenr_T)MAXLNUM, 1L, 0L, false); } did_append = true; } else { @@ -1866,7 +1866,7 @@ void appended_lines_mark(linenr_T lnum, long count) // Skip mark_adjust when adding a line after the last one, there can't // be marks there. if (lnum + count < curbuf->b_ml.ml_line_count) { - mark_adjust(lnum + 1, (linenr_T)MAXLNUM, count, 0L); + mark_adjust(lnum + 1, (linenr_T)MAXLNUM, count, 0L, false); } changed_lines(lnum + 1, 0, lnum + 1, count); } @@ -1888,7 +1888,7 @@ void deleted_lines(linenr_T lnum, long count) */ void deleted_lines_mark(linenr_T lnum, long count) { - mark_adjust(lnum, (linenr_T)(lnum + count - 1), (long)MAXLNUM, -count); + mark_adjust(lnum, (linenr_T)(lnum + count - 1), (long)MAXLNUM, -count, false); changed_lines(lnum, 0, lnum + count, -count); } diff --git a/src/nvim/ops.c b/src/nvim/ops.c index f9153a94a7..5c6f4d0d07 100644 --- a/src/nvim/ops.c +++ b/src/nvim/ops.c @@ -3182,7 +3182,7 @@ error: if (curbuf->b_op_start.lnum + (y_type == kMTCharWise) - 1 + nr_lines < curbuf->b_ml.ml_line_count) { mark_adjust(curbuf->b_op_start.lnum + (y_type == kMTCharWise), - (linenr_T)MAXLNUM, nr_lines, 0L); + (linenr_T)MAXLNUM, nr_lines, 0L, false); } // note changed text for displaying and folding diff --git a/src/nvim/undo.c b/src/nvim/undo.c index 290d5d7553..81af3bfda9 100644 --- a/src/nvim/undo.c +++ b/src/nvim/undo.c @@ -2232,11 +2232,13 @@ static void u_undoredo(int undo) /* adjust marks */ if (oldsize != newsize) { mark_adjust(top + 1, top + oldsize, (long)MAXLNUM, - (long)newsize - (long)oldsize); - if (curbuf->b_op_start.lnum > top + oldsize) + (long)newsize - (long)oldsize, false); + if (curbuf->b_op_start.lnum > top + oldsize) { curbuf->b_op_start.lnum += newsize - oldsize; - if (curbuf->b_op_end.lnum > top + oldsize) + } + if (curbuf->b_op_end.lnum > top + oldsize) { curbuf->b_op_end.lnum += newsize - oldsize; + } } changed_lines(top + 1, 0, bot, newsize - oldsize); -- cgit