From 91e912f8d40284c74d4a997c8c95961eebb35d91 Mon Sep 17 00:00:00 2001 From: dundargoc <33953936+dundargoc@users.noreply.github.com> Date: Sun, 25 Sep 2022 15:26:37 +0200 Subject: refactor: move klib out of src/nvim/ #20341 It's confusing to mix vendored dependencies with neovim source code. A clean separation is simpler to keep track of and simpler to document. --- src/klib/kbtree.h | 477 ++++++++++++++++++++++++ src/klib/khash.h | 730 +++++++++++++++++++++++++++++++++++++ src/klib/klist.h | 144 ++++++++ src/klib/kvec.h | 236 ++++++++++++ src/nvim/CMakeLists.txt | 4 +- src/nvim/api/private/defs.h | 2 +- src/nvim/api/private/helpers.c | 2 +- src/nvim/api/private/helpers.h | 2 +- src/nvim/buffer_defs.h | 2 +- src/nvim/context.h | 2 +- src/nvim/decoration_provider.c | 2 +- src/nvim/eval/decode.c | 2 +- src/nvim/eval/encode.c | 2 +- src/nvim/eval/typval_encode.c.h | 2 +- src/nvim/eval/typval_encode.h | 2 +- src/nvim/event/loop.h | 2 +- src/nvim/ex_getln.c | 2 +- src/nvim/extmark.c | 2 +- src/nvim/extmark_defs.h | 2 +- src/nvim/lib/kbtree.h | 477 ------------------------ src/nvim/lib/khash.h | 730 ------------------------------------- src/nvim/lib/klist.h | 144 -------- src/nvim/lib/kvec.h | 236 ------------ src/nvim/lua/converter.c | 2 +- src/nvim/lua/treesitter.c | 2 +- src/nvim/map.c | 2 +- src/nvim/map_defs.h | 2 +- src/nvim/marktree.c | 2 +- src/nvim/message.h | 2 +- src/nvim/msgpack_rpc/channel.c | 2 +- src/nvim/msgpack_rpc/helpers.c | 2 +- src/nvim/ops.c | 2 +- src/nvim/os/pty_conpty_win.h | 2 +- src/nvim/os/pty_process_unix.c | 2 +- src/nvim/os/shell.c | 2 +- src/nvim/shada.c | 4 +- src/nvim/state.c | 2 +- src/nvim/strings.h | 2 +- src/nvim/tui/tui.c | 2 +- src/nvim/ui_compositor.c | 2 +- src/nvim/undo.c | 2 +- src/nvim/viml/parser/expressions.c | 2 +- src/nvim/viml/parser/parser.h | 2 +- 43 files changed, 1624 insertions(+), 1624 deletions(-) create mode 100644 src/klib/kbtree.h create mode 100644 src/klib/khash.h create mode 100644 src/klib/klist.h create mode 100644 src/klib/kvec.h delete mode 100644 src/nvim/lib/kbtree.h delete mode 100644 src/nvim/lib/khash.h delete mode 100644 src/nvim/lib/klist.h delete mode 100644 src/nvim/lib/kvec.h (limited to 'src') diff --git a/src/klib/kbtree.h b/src/klib/kbtree.h new file mode 100644 index 0000000000..99f79952d7 --- /dev/null +++ b/src/klib/kbtree.h @@ -0,0 +1,477 @@ +/*- + * 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. + */ + +// Gotchas +// ------- +// +// if you delete from a kbtree while iterating over it you must use +// kb_del_itr and not kb_del otherwise the iterator might point to freed memory. + +#ifndef NVIM_LIB_KBTREE_H +#define NVIM_LIB_KBTREE_H + +#include +#include +#include +#include + +#include "nvim/memory.h" + +#define KB_MAX_DEPTH 64 + +#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[]; \ + }; \ + typedef struct { \ + 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_destroy(kbnode_t, b) do { \ + int i; \ + unsigned int max = 8; \ + kbnode_t *x, **top, **stack = 0; \ + if (b->root) { \ + top = stack = (kbnode_t **)xcalloc(max, sizeof(kbnode_t *)); \ + *top++ = (b)->root; \ + while (top != stack) { \ + x = *--top; \ + if (x->is_internal == 0) { XFREE_CLEAR(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 **)xrealloc(stack, max * sizeof(kbnode_t *)); \ + top = stack + (max>>1); \ + } \ + *top++ = __KB_PTR(b, x)[i]; \ + } \ + XFREE_CLEAR(x); \ + } \ + } \ + XFREE_CLEAR(stack); \ +} while (0) + +#define __KB_GET_AUX1(name, key_t, kbnode_t, __cmp) \ + 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; \ + 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, kbnode_t) \ + static key_t *kb_getp_##name(kbtree_##name##_t *b, key_t * __restrict k) \ + { \ + if (!b->root) { \ + return 0; \ + } \ + 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, key_t k) \ + { \ + return kb_getp_##name(b, &k); \ + } + +#define __KB_INTERVAL(name, key_t, kbnode_t) \ + static inline void kb_intervalp_##name(kbtree_##name##_t *b, 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; \ + 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, 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 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)); \ + ++b->n_nodes; \ + z->is_internal = y->is_internal; \ + 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)[T - 1]; \ + ++x->n; \ + } \ + 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; \ + 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 * 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 inline key_t *kb_putp_##name(kbtree_##name##_t *b, 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; \ + if (r->n == 2 * T - 1) { \ + ++b->n_nodes; \ + 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); \ + r = s; \ + } \ + return __kb_putp_aux_##name(b, r, 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 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; \ + 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) >= 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) >= 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 == 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 *)); \ + 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; \ + XFREE_CLEAR(z); \ + return __kb_delp_aux_##name(b, y, k, s); \ + } \ + } \ + ++i; \ + 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 >= 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 == 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; \ + XFREE_CLEAR(xp); \ + xp = y; \ + } 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 *)); \ + 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; \ + XFREE_CLEAR(y); \ + } \ + } \ + return __kb_delp_aux_##name(b, xp, k, s); \ + } \ + static inline key_t kb_delp_##name(kbtree_##name##_t *b, 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]; \ + XFREE_CLEAR(x); \ + } \ + return ret; \ + } \ + static inline key_t kb_del_##name(kbtree_##name##_t *b, key_t k) \ + { \ + return kb_delp_##name(b, &k); \ + } + +#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 = NULL; \ + 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_##name##_t *itr) \ + { \ + if (itr->p == NULL) return 0; \ + for (;;) { \ + ++itr->p->i; \ + assert(itr->p->i <= 21); \ + 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; \ + } \ + if (itr->p == itr->stack) { \ + itr->p = NULL; \ + return 0; \ + } \ + --itr->p; \ + 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_##name##_t *itr) \ + { \ + if (itr->p == NULL) 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; \ + } \ + if (itr->p == itr->stack) { \ + itr->p = NULL; \ + return 0; \ + } \ + --itr->p; \ + --itr->p->i; \ + if (itr->p->x && itr->p->i >= 0) return 1; \ + } \ + } \ + static inline int kb_itr_getp_##name(kbtree_##name##_t *b, key_t * __restrict k, \ + kbitr_##name##_t *itr) \ + { \ + if (b->n_keys == 0) { \ + itr->p = NULL; \ + return 0; \ + } \ + 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; \ + assert(itr->p->i <= 21); \ + itr->p[1].x = itr->p->x->is_internal? __KB_PTR(b, itr->p->x)[i + 1] : 0; \ + ++itr->p; \ + } \ + itr->p->i = 0; \ + return 0; \ + } \ + 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) \ + { \ + 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_IMPL(name, key_t, kbnode_t, __cmp, T, ILEN) \ + __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) + +#define KB_DEFAULT_SIZE 512 + +#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) +#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_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(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) + +#define kb_generic_cmp(a, b) (((b) < (a)) - ((a) < (b))) +#define kb_str_cmp(a, b) strcmp(a, b) + +#endif // NVIM_LIB_KBTREE_H diff --git a/src/klib/khash.h b/src/klib/khash.h new file mode 100644 index 0000000000..57a41f9c13 --- /dev/null +++ b/src/klib/khash.h @@ -0,0 +1,730 @@ +/* The MIT License + + Copyright (c) 2008, 2009, 2011 by Attractive Chaos + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE. + */ + +/* + Example: + + #include "nvim/khash.h" + KHASH_MAP_INIT_INT(32, char) + int main() { + int ret, is_missing; + khiter_t k; + khash_t(32) *h = kh_init(32); + k = kh_put(32, h, 5, &ret); + kh_value(h, k) = 10; + k = kh_get(32, h, 10); + is_missing = (k == kh_end(h)); + k = kh_get(32, h, 5); + kh_del(32, h, k); + for (k = kh_begin(h); k != kh_end(h); ++k) + if (kh_exist(h, k)) kh_value(h, k) = 1; + kh_destroy(32, h); + return 0; + } + */ + +/* + 2013-05-02 (0.2.8): + + * Use quadratic probing. When the capacity is power of 2, stepping function + i*(i+1)/2 guarantees to traverse each bucket. It is better than double + hashing on cache performance and is more robust than linear probing. + + In theory, double hashing should be more robust than quadratic probing. + However, my implementation is probably not for large hash tables, because + the second hash function is closely tied to the first hash function, + which reduce the effectiveness of double hashing. + + Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php + + 2011-12-29 (0.2.7): + + * Minor code clean up; no actual effect. + + 2011-09-16 (0.2.6): + + * The capacity is a power of 2. This seems to dramatically improve the + speed for simple keys. Thank Zilong Tan for the suggestion. Reference: + + - http://code.google.com/p/ulib/ + - http://nothings.org/computer/judy/ + + * Allow to optionally use linear probing which usually has better + performance for random input. Double hashing is still the default as it + is more robust to certain non-random input. + + * Added Wang's integer hash function (not used by default). This hash + function is more robust to certain non-random input. + + 2011-02-14 (0.2.5): + + * Allow to declare global functions. + + 2009-09-26 (0.2.4): + + * Improve portability + + 2008-09-19 (0.2.3): + + * Corrected the example + * Improved interfaces + + 2008-09-11 (0.2.2): + + * Improved speed a little in kh_put() + + 2008-09-10 (0.2.1): + + * Added kh_clear() + * Fixed a compiling error + + 2008-09-02 (0.2.0): + + * Changed to token concatenation which increases flexibility. + + 2008-08-31 (0.1.2): + + * Fixed a bug in kh_get(), which has not been tested previously. + + 2008-08-31 (0.1.1): + + * Added destructor + */ + +#ifndef NVIM_LIB_KHASH_H +#define NVIM_LIB_KHASH_H + +/*! + @header + + Generic hash table library. + */ + +#define AC_VERSION_KHASH_H "0.2.8" + +#include +#include +#include +#include + +#include "nvim/func_attr.h" +#include "nvim/memory.h" + +// compiler specific configuration + +#if UINT_MAX == 0xffffffffu +typedef unsigned int khint32_t; +#elif ULONG_MAX == 0xffffffffu +typedef unsigned long khint32_t; +#endif + +#if ULONG_MAX == ULLONG_MAX +typedef unsigned long khint64_t; +#else +typedef unsigned long long khint64_t; +#endif + +#ifdef _MSC_VER +# define kh_inline __inline +#else +# define kh_inline inline +#endif + +typedef khint32_t khint_t; +typedef khint_t khiter_t; + +#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2) +#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1) +#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3) +#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(khint_t)(1ul<<((i&0xfU)<<1))) +#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(khint_t)(2ul<<((i&0xfU)<<1))) +#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(khint_t)(3ul<<((i&0xfU)<<1))) +#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=(khint_t)1ul<<((i&0xfU)<<1)) + +#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4) + +#ifndef kroundup32 +# define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, \ + ++(x)) +#endif + +#ifndef kcalloc +# define kcalloc(N, Z) xcalloc(N, Z) +#endif +#ifndef kmalloc +# define kmalloc(Z) xmalloc(Z) +#endif +#ifndef krealloc +# define krealloc(P, Z) xrealloc(P, Z) +#endif +#ifndef kfree +# define kfree(P) XFREE_CLEAR(P) +#endif + +#define __ac_HASH_UPPER 0.77 + +#define __KHASH_TYPE(name, khkey_t, khval_t) \ + typedef struct { \ + khint_t n_buckets, size, n_occupied, upper_bound; \ + khint32_t *flags; \ + khkey_t *keys; \ + khval_t *vals; \ + } kh_##name##_t; + +#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ + extern kh_##name##_t *kh_init_##name(void); \ + extern void kh_dealloc_##name(kh_##name##_t *h); \ + extern void kh_destroy_##name(kh_##name##_t *h); \ + extern void kh_clear_##name(kh_##name##_t *h); \ + extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \ + extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \ + extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \ + extern void kh_del_##name(kh_##name##_t *h, khint_t x); + +#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, \ + __hash_equal) \ + SCOPE kh_##name##_t *kh_init_##name(void) \ + REAL_FATTR_UNUSED; \ + SCOPE kh_##name##_t *kh_init_##name(void) { \ + return (kh_##name##_t *)kcalloc(1, sizeof(kh_##name##_t)); \ + } \ + SCOPE void kh_dealloc_##name(kh_##name##_t *h) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_dealloc_##name(kh_##name##_t *h) \ + { \ + kfree(h->keys); \ + kfree(h->flags); \ + kfree(h->vals); \ + } \ + SCOPE void kh_destroy_##name(kh_##name##_t *h) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_destroy_##name(kh_##name##_t *h) \ + { \ + if (h) { \ + kh_dealloc_##name(h); \ + kfree(h); \ + } \ + } \ + SCOPE void kh_clear_##name(kh_##name##_t *h) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_clear_##name(kh_##name##_t *h) \ + { \ + if (h && h->flags) { \ + memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \ + h->size = h->n_occupied = 0; \ + } \ + } \ + SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ + REAL_FATTR_UNUSED; \ + SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ + { \ + if (h->n_buckets) { \ + khint_t k, i, last, mask, step = 0; \ + mask = h->n_buckets - 1; \ + k = __hash_func(key); i = k & mask; \ + last = i; \ + while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || \ + !__hash_equal(h->keys[i], key))) { \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + return h->n_buckets; \ + } \ + } \ + return __ac_iseither(h->flags, i) ? h->n_buckets : i; \ + } else { \ + return 0; \ + } \ + } \ + SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ + { /* This function uses 0.25*n_buckets bytes of working space instead of */ \ + /* [sizeof(key_t+val_t)+.25]*n_buckets. */ \ + khint32_t *new_flags = 0; \ + khint_t j = 1; \ + { \ + kroundup32(new_n_buckets); \ + if (new_n_buckets < 4) { \ + new_n_buckets = 4; \ + } \ + /* requested size is too small */ \ + if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) { \ + j = 0; \ + } else { /* hash table size to be changed (shrink or expand); rehash */ \ + new_flags = (khint32_t *)kmalloc(__ac_fsize(new_n_buckets) \ + * sizeof(khint32_t)); \ + memset(new_flags, 0xaa, \ + __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ + if (h->n_buckets < new_n_buckets) { /* expand */ \ + khkey_t *new_keys = (khkey_t *)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ + h->keys = new_keys; \ + if (kh_is_map) { \ + khval_t *new_vals = \ + (khval_t *)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ + h->vals = new_vals; \ + } \ + } /* otherwise shrink */ \ + } \ + } \ + if (j) { /* rehashing is needed */ \ + for (j = 0; j != h->n_buckets; ++j) { \ + if (__ac_iseither(h->flags, j) == 0) { \ + khkey_t key = h->keys[j]; \ + khval_t val; \ + khint_t new_mask; \ + new_mask = new_n_buckets - 1; \ + if (kh_is_map) { \ + val = h->vals[j]; \ + } \ + __ac_set_isdel_true(h->flags, j); \ + /* kick-out process; sort of like in Cuckoo hashing */ \ + while (1) { \ + khint_t k, i, step = 0; \ + k = __hash_func(key); \ + i = k & new_mask; \ + while (!__ac_isempty(new_flags, i)) { \ + i = (i + (++step)) & new_mask; \ + } \ + __ac_set_isempty_false(new_flags, i); \ + /* kick out the existing element */ \ + if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \ + { \ + khkey_t tmp = h->keys[i]; \ + h->keys[i] = key; \ + key = tmp; \ + } \ + if (kh_is_map) { \ + khval_t tmp = h->vals[i]; \ + h->vals[i] = val; \ + val = tmp; \ + } \ + /* mark it as deleted in the old hash table */ \ + __ac_set_isdel_true(h->flags, i); \ + } else { /* write the element and jump out of the loop */ \ + h->keys[i] = key; \ + if (kh_is_map) { \ + h->vals[i] = val; \ + } \ + break; \ + } \ + } \ + } \ + } \ + if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ + h->keys = (khkey_t *)krealloc((void *)h->keys, \ + new_n_buckets * sizeof(khkey_t)); \ + if (kh_is_map) { \ + h->vals = (khval_t *)krealloc((void *)h->vals, \ + new_n_buckets * sizeof(khval_t)); \ + } \ + } \ + kfree(h->flags); /* free the working space */ \ + h->flags = new_flags; \ + h->n_buckets = new_n_buckets; \ + h->n_occupied = h->size; \ + h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + } \ + SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ + REAL_FATTR_UNUSED; \ + SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ + { \ + khint_t x; \ + if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ + if (h->n_buckets > (h->size << 1)) { \ + kh_resize_##name(h, h->n_buckets - 1); /* clear "deleted" elements */ \ + } else { \ + kh_resize_##name(h, h->n_buckets + 1); /* expand the hash table */ \ + } \ + } /* TODO: implement automatically shrinking; */ \ + /* resize() already support shrinking */ \ + { \ + khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ + x = site = h->n_buckets; \ + k = __hash_func(key); \ + i = k & mask; \ + if (__ac_isempty(h->flags, i)) { \ + x = i; /* for speed up */ \ + } else { \ + last = i; \ + while (!__ac_isempty(h->flags, i) \ + && (__ac_isdel(h->flags, i) \ + || !__hash_equal(h->keys[i], key))) { \ + if (__ac_isdel(h->flags, i)) { \ + site = i; \ + } \ + i = (i + (++step)) & mask; \ + if (i == last) { \ + x = site; \ + break; \ + } \ + } \ + if (x == h->n_buckets) { \ + if (__ac_isempty(h->flags, i) && site != h->n_buckets) { \ + x = site; \ + } else { \ + x = i; \ + } \ + } \ + } \ + } \ + if (__ac_isempty(h->flags, x)) { /* not present at all */ \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + h->size++; \ + h->n_occupied++; \ + *ret = 1; \ + } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + h->size++; \ + *ret = 2; \ + } else { \ + *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ + } \ + return x; \ + } \ + SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ + REAL_FATTR_UNUSED; \ + SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ + { \ + if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ + __ac_set_isdel_true(h->flags, x); \ + --h->size; \ + } \ + } + +#define KHASH_DECLARE(name, khkey_t, khval_t) \ + __KHASH_TYPE(name, khkey_t, khval_t) \ + __KHASH_PROTOTYPES(name, khkey_t, khval_t) + +#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + __KHASH_TYPE(name, khkey_t, khval_t) \ + __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) + +#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + KHASH_INIT2(name, static kh_inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) + +// --- BEGIN OF HASH FUNCTIONS --- + +/*! @function + @abstract Integer hash function + @param key The integer [khint32_t] + @return The hash value [khint_t] + */ +#define kh_int_hash_func(key) (khint32_t)(key) +/*! @function + @abstract Integer comparison function + */ +#define kh_int_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract 64-bit integer hash function + @param key The integer [khint64_t] + @return The hash value [khint_t] + */ +#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11) +/*! @function + @abstract 64-bit integer comparison function + */ +#define kh_int64_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract const char* hash function + @param s Pointer to a null terminated string + @return The hash value + */ +static kh_inline khint_t __ac_X31_hash_string(const char *s) +{ + khint_t h = (khint_t)*s; + if (h) { + for (++s; *s; ++s) { h = (h << 5) - h + (uint8_t)*s; } + } + return h; +} +/*! @function + @abstract Another interface to const char* hash function + @param key Pointer to a null terminated string [const char*] + @return The hash value [khint_t] + */ +#define kh_str_hash_func(key) __ac_X31_hash_string(key) +/*! @function + @abstract Const char* comparison function + */ +#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0) + +static kh_inline khint_t __ac_Wang_hash(khint_t key) +{ + key += ~(key << 15); + key ^= (key >> 10); + key += (key << 3); + key ^= (key >> 6); + key += ~(key << 11); + key ^= (key >> 16); + return key; +} +#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key) + +// --- END OF HASH FUNCTIONS --- + +// Other convenient macros... + +/*! + @abstract Type of the hash table. + @param name Name of the hash table [symbol] + */ +#define khash_t(name) kh_##name##_t + +/*! @function + @abstract Initiate a hash table. + @param name Name of the hash table [symbol] + @return Pointer to the hash table [khash_t(name)*] + */ +#define kh_init(name) kh_init_##name() + +/*! @function + @abstract Destroy a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_destroy(name, h) kh_destroy_##name(h) + +/*! @function + @abstract Free memory referenced directly inside a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_dealloc(name, h) kh_dealloc_##name(h) + +/*! @function + @abstract Reset a hash table without deallocating memory. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_clear(name, h) kh_clear_##name(h) + +/*! @function + @abstract Resize a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param s New size [khint_t] + */ +#define kh_resize(name, h, s) kh_resize_##name(h, s) + +/*! @function + @abstract Insert a key to the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @param r Extra return code: -1 if the operation failed; + 0 if the key is present in the hash table; + 1 if the bucket is empty (never used); 2 if the element in + the bucket has been deleted [int*] + @return Iterator to the inserted element [khint_t] + */ +#define kh_put(name, h, k, r) kh_put_##name(h, k, r) + +/*! @function + @abstract Retrieve a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @return Iterator to the found element, or kh_end(h) if the element is absent [khint_t] + */ +#define kh_get(name, h, k) kh_get_##name(h, k) + +/*! @function + @abstract Remove a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Iterator to the element to be deleted [khint_t] + */ +#define kh_del(name, h, k) kh_del_##name(h, k) + +/*! @function + @abstract Test whether a bucket contains data. + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return 1 if containing data; 0 otherwise [int] + */ +#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x))) + +/*! @function + @abstract Get key given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Key [type of keys] + */ +#define kh_key(h, x) ((h)->keys[x]) + +/*! @function + @abstract Get value given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Value [type of values] + @discussion For hash sets, calling this results in segfault. + */ +#define kh_val(h, x) ((h)->vals[x]) + +/*! @function + @abstract Alias of kh_val() + */ +#define kh_value(h, x) ((h)->vals[x]) + +/*! @function + @abstract Get the start iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The start iterator [khint_t] + */ +#define kh_begin(h) (khint_t)(0) + +/*! @function + @abstract Get the end iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The end iterator [khint_t] + */ +#define kh_end(h) ((h)->n_buckets) + +/*! @function + @abstract Get the number of elements in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of elements in the hash table [khint_t] + */ +#define kh_size(h) ((h)->size) + +/*! @function + @abstract Get the number of buckets in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of buckets in the hash table [khint_t] + */ +#define kh_n_buckets(h) ((h)->n_buckets) + +/*! @function + @abstract Iterate over the entries in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param kvar Variable to which key will be assigned + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach(h, kvar, vvar, code) { khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ + if (!kh_exist(h, __i)) continue; \ + (kvar) = kh_key(h, __i); \ + (vvar) = kh_val(h, __i); \ + code; \ + } } + +/*! @function + @abstract Iterate over the values in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach_value(h, vvar, code) { khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ + if (!kh_exist(h, __i)) continue; \ + (vvar) = kh_val(h, __i); \ + code; \ + } } + +/*! @function + @abstract Iterate over the keys in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param kvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach_key(h, kvar, code) \ + { \ + khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); __i++) { \ + if (!kh_exist(h, __i)) { \ + continue; \ + } \ + (kvar) = kh_key(h, __i); \ + code; \ + } \ + } + +// More convenient interfaces + +/*! @function + @abstract Instantiate a hash set containing integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT(name) \ + KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT(name, khval_t) \ + KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing 64-bit integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT64(name) \ + KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing 64-bit integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT64(name, khval_t) \ + KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal) + +typedef const char *kh_cstr_t; +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_STR(name) \ + KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_STR(name, khval_t) \ + KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) + +/*! @function + @abstract Return a literal for an empty hash table. + @param name Name of the hash table [symbol] + */ +#define KHASH_EMPTY_TABLE(name) \ + ((kh_##name##_t) { \ + .n_buckets = 0, \ + .size = 0, \ + .n_occupied = 0, \ + .upper_bound = 0, \ + .flags = NULL, \ + .keys = NULL, \ + .vals = NULL, \ + }) +#endif // NVIM_LIB_KHASH_H diff --git a/src/klib/klist.h b/src/klib/klist.h new file mode 100644 index 0000000000..a9abbc6dc2 --- /dev/null +++ b/src/klib/klist.h @@ -0,0 +1,144 @@ +/* The MIT License + + Copyright (c) 2008-2009, by Attractive Chaos + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE. + */ + +#ifndef _AC_KLIST_H +#define _AC_KLIST_H + +#include +#include + +#include "nvim/func_attr.h" +#include "nvim/memory.h" + +#define KMEMPOOL_INIT(name, kmptype_t, kmpfree_f) \ + typedef struct { \ + size_t cnt, n, max; \ + kmptype_t **buf; \ + } kmp_##name##_t; \ + static inline kmp_##name##_t *kmp_init_##name(void) { \ + return xcalloc(1, sizeof(kmp_##name##_t)); \ + } \ + static inline void kmp_destroy_##name(kmp_##name##_t *mp) \ + REAL_FATTR_UNUSED; \ + static inline void kmp_destroy_##name(kmp_##name##_t *mp) { \ + size_t k; \ + for (k = 0; k < mp->n; k++) { \ + kmpfree_f(mp->buf[k]); XFREE_CLEAR(mp->buf[k]); \ + } \ + XFREE_CLEAR(mp->buf); XFREE_CLEAR(mp); \ + } \ + static inline kmptype_t *kmp_alloc_##name(kmp_##name##_t *mp) { \ + mp->cnt++; \ + if (mp->n == 0) { \ + return xcalloc(1, sizeof(kmptype_t)); \ + } \ + return mp->buf[--mp->n]; \ + } \ + static inline void kmp_free_##name(kmp_##name##_t *mp, kmptype_t *p) { \ + mp->cnt--; \ + if (mp->n == mp->max) { \ + mp->max = mp->max ? (mp->max << 1) : 16; \ + mp->buf = xrealloc(mp->buf, sizeof(kmptype_t *) * mp->max); \ + } \ + mp->buf[mp->n++] = p; \ + } + +#define kmempool_t(name) kmp_##name##_t +#define kmp_init(name) kmp_init_##name() +#define kmp_destroy(name, mp) kmp_destroy_##name(mp) +#define kmp_alloc(name, mp) kmp_alloc_##name(mp) +#define kmp_free(name, mp, p) kmp_free_##name(mp, p) + +#define KLIST_INIT(name, kltype_t, kmpfree_t) \ + struct __kl1_##name { \ + kltype_t data; \ + struct __kl1_##name *next; \ + }; \ + typedef struct __kl1_##name kl1_##name; \ + KMEMPOOL_INIT(name, kl1_##name, kmpfree_t) \ + typedef struct { \ + kl1_##name *head, *tail; \ + kmp_##name##_t *mp; \ + size_t size; \ + } kl_##name##_t; \ + static inline kl_##name##_t *kl_init_##name(void) { \ + kl_##name##_t *kl = xcalloc(1, sizeof(kl_##name##_t)); \ + kl->mp = kmp_init(name); \ + kl->head = kl->tail = kmp_alloc(name, kl->mp); \ + kl->head->next = 0; \ + return kl; \ + } \ + static inline void kl_destroy_##name(kl_##name##_t *kl) \ + REAL_FATTR_UNUSED; \ + static inline void kl_destroy_##name(kl_##name##_t *kl) { \ + kl1_##name *p; \ + for (p = kl->head; p != kl->tail; p = p->next) { \ + kmp_free(name, kl->mp, p); \ + } \ + kmp_free(name, kl->mp, p); \ + kmp_destroy(name, kl->mp); \ + XFREE_CLEAR(kl); \ + } \ + static inline void kl_push_##name(kl_##name##_t *kl, kltype_t d) { \ + kl1_##name *q, *p = kmp_alloc(name, kl->mp); \ + q = kl->tail; p->next = 0; kl->tail->next = p; kl->tail = p; \ + kl->size++; \ + q->data = d; \ + } \ + static inline kltype_t kl_shift_at_##name(kl_##name##_t *kl, \ + kl1_##name **n) { \ + assert((*n)->next); \ + kl1_##name *p; \ + kl->size--; \ + p = *n; \ + *n = (*n)->next; \ + if (p == kl->head) { \ + kl->head = *n; \ + } \ + kltype_t d = p->data; \ + kmp_free(name, kl->mp, p); \ + return d; \ + } + +#define kliter_t(name) kl1_##name +#define klist_t(name) kl_##name##_t +#define kl_val(iter) ((iter)->data) +#define kl_next(iter) ((iter)->next) +#define kl_begin(kl) ((kl)->head) +#define kl_end(kl) ((kl)->tail) + +#define kl_init(name) kl_init_##name() +#define kl_destroy(name, kl) kl_destroy_##name(kl) +#define kl_push(name, kl, d) kl_push_##name(kl, d) +#define kl_shift_at(name, kl, node) kl_shift_at_##name(kl, node) +#define kl_shift(name, kl) kl_shift_at(name, kl, &kl->head) +#define kl_empty(kl) ((kl)->size == 0) +// Iteration macros. It's ok to modify the list while iterating as long as a +// `break` statement is executed before the next iteration. +#define kl_iter(name, kl, p) kl_iter_at(name, kl, p, NULL) +#define kl_iter_at(name, kl, p, h) \ + for (kl1_##name **p = h ? h : &kl->head; *p != kl->tail; p = &(*p)->next) + +#endif diff --git a/src/klib/kvec.h b/src/klib/kvec.h new file mode 100644 index 0000000000..b5b3adf7d2 --- /dev/null +++ b/src/klib/kvec.h @@ -0,0 +1,236 @@ +// The MIT License +// +// Copyright (c) 2008, by Attractive Chaos +// +// Permission is hereby granted, free of charge, to any person obtaining +// a copy of this software and associated documentation files (the +// "Software"), to deal in the Software without restriction, including +// without limitation the rights to use, copy, modify, merge, publish, +// distribute, sublicense, and/or sell copies of the Software, and to +// permit persons to whom the Software is furnished to do so, subject to +// the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS +// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN +// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN +// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +// SOFTWARE. + +// An example: +// +// #include "kvec.h" +// int main() { +// kvec_t(int) array = KV_INITIAL_VALUE; +// kv_push(array, 10); // append +// kv_a(array, 20) = 5; // dynamic +// kv_A(array, 20) = 4; // static +// kv_destroy(array); +// return 0; +// } + +#ifndef NVIM_LIB_KVEC_H +#define NVIM_LIB_KVEC_H + +#include +#include + +#include "nvim/memory.h" +#include "nvim/os/os_defs.h" + +#define kv_roundup32(x) \ + ((--(x)), \ + ((x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16), \ + (++(x))) + +#define KV_INITIAL_VALUE { .size = 0, .capacity = 0, .items = NULL } + +#define kvec_t(type) \ + struct { \ + size_t size; \ + size_t capacity; \ + type *items; \ + } + +#define kv_init(v) ((v).size = (v).capacity = 0, (v).items = 0) +#define kv_destroy(v) \ + do { \ + xfree((v).items); \ + kv_init(v); \ + } while (0) +#define kv_A(v, i) ((v).items[(i)]) +#define kv_pop(v) ((v).items[--(v).size]) +#define kv_size(v) ((v).size) +#define kv_max(v) ((v).capacity) +#define kv_Z(v, i) kv_A(v, kv_size(v) - (i) - 1) +#define kv_last(v) kv_Z(v, 0) + +/// Drop last n items from kvec without resizing +/// +/// Previously spelled as `(void)kv_pop(v)`, repeated n times. +/// +/// @param[out] v Kvec to drop items from. +/// @param[in] n Number of elements to drop. +#define kv_drop(v, n) ((v).size -= (n)) + +#define kv_resize(v, s) \ + ((v).capacity = (s), \ + (v).items = xrealloc((v).items, sizeof((v).items[0]) * (v).capacity)) + +#define kv_resize_full(v) \ + kv_resize(v, (v).capacity ? (v).capacity << 1 : 8) + +#define kv_copy(v1, v0) \ + do { \ + if ((v1).capacity < (v0).size) { \ + kv_resize(v1, (v0).size); \ + } \ + (v1).size = (v0).size; \ + memcpy((v1).items, (v0).items, sizeof((v1).items[0]) * (v0).size); \ + } while (0) + +/// fit at least "len" more items +#define kv_ensure_space(v, len) \ + do { \ + if ((v).capacity < (v).size + len) { \ + (v).capacity = (v).size + len; \ + kv_roundup32((v).capacity); \ + kv_resize((v), (v).capacity); \ + } \ + } while (0) + +#define kv_concat_len(v, data, len) \ + do { \ + kv_ensure_space(v, len); \ + memcpy((v).items + (v).size, data, sizeof((v).items[0]) * len); \ + (v).size = (v).size + len; \ + } while (0) + +#define kv_concat(v, str) kv_concat_len(v, str, STRLEN(str)) +#define kv_splice(v1, v0) kv_concat_len(v1, (v0).items, (v0).size) + +#define kv_pushp(v) \ + ((((v).size == (v).capacity) ? (kv_resize_full(v), 0) : 0), \ + ((v).items + ((v).size++))) + +#define kv_push(v, x) \ + (*kv_pushp(v) = (x)) + +#define kv_pushp_c(v) ((v).items + ((v).size++)) +#define kv_push_c(v, x) (*kv_pushp_c(v) = (x)) + +#define kv_a(v, i) \ + (*(((v).capacity <= (size_t)(i) \ + ? ((v).capacity = (v).size = (i) + 1, \ + kv_roundup32((v).capacity), \ + kv_resize((v), (v).capacity), 0UL) \ + : ((v).size <= (size_t)(i) \ + ? (v).size = (i) + 1 \ + : 0UL)), \ + &(v).items[(i)])) + +#define kv_printf(v, ...) kv_do_printf(&(v), __VA_ARGS__) + +/// Type of a vector with a few first members allocated on stack +/// +/// Is compatible with #kv_A, #kv_pop, #kv_size, #kv_max, #kv_last. +/// Is not compatible with #kv_resize, #kv_resize_full, #kv_copy, #kv_push, +/// #kv_pushp, #kv_a, #kv_destroy. +/// +/// @param[in] type Type of vector elements. +/// @param[in] init_size Number of the elements in the initial array. +#define kvec_withinit_t(type, INIT_SIZE) \ + struct { \ + size_t size; \ + size_t capacity; \ + type *items; \ + type init_array[INIT_SIZE]; \ + } + +/// Initialize vector with preallocated array +/// +/// @param[out] v Vector to initialize. +#define kvi_init(v) \ + ((v).capacity = ARRAY_SIZE((v).init_array), \ + (v).size = 0, \ + (v).items = (v).init_array) + +/// Move data to a new destination and free source +static inline void *_memcpy_free(void *const restrict dest, void *const restrict src, + const size_t size) + FUNC_ATTR_NONNULL_ALL FUNC_ATTR_NONNULL_RET FUNC_ATTR_ALWAYS_INLINE +{ + memcpy(dest, src, size); + XFREE_CLEAR(src); + return dest; +} + +// -V:kvi_push:512 + +/// Resize vector with preallocated array +/// +/// @note May not resize to an array smaller then init_array: if requested, +/// init_array will be used. +/// +/// @param[out] v Vector to resize. +/// @param[in] s New size. +#define kvi_resize(v, s) \ + ((v).capacity = ((s) > ARRAY_SIZE((v).init_array) \ + ? (s) \ + : ARRAY_SIZE((v).init_array)), \ + (v).items = ((v).capacity == ARRAY_SIZE((v).init_array) \ + ? ((v).items == (v).init_array \ + ? (v).items \ + : _memcpy_free((v).init_array, (v).items, \ + (v).size * sizeof((v).items[0]))) \ + : ((v).items == (v).init_array \ + ? memcpy(xmalloc((v).capacity * sizeof((v).items[0])), \ + (v).items, \ + (v).size * sizeof((v).items[0])) \ + : xrealloc((v).items, \ + (v).capacity * sizeof((v).items[0]))))) + +/// Resize vector with preallocated array when it is full +/// +/// @param[out] v Vector to resize. +#define kvi_resize_full(v) \ + /* ARRAY_SIZE((v).init_array) is the minimal capacity of this vector. */ \ + /* Thus when vector is full capacity may not be zero and it is safe */ \ + /* not to bother with checking whether (v).capacity is 0. But now */ \ + /* capacity is not guaranteed to have size that is a power of 2, it is */ \ + /* hard to fix this here and is not very necessary if users will use */ \ + /* 2^x initial array size. */ \ + kvi_resize(v, (v).capacity << 1) + +/// Get location where to store new element to a vector with preallocated array +/// +/// @param[in,out] v Vector to push to. +/// +/// @return Pointer to the place where new value should be stored. +#define kvi_pushp(v) \ + ((((v).size == (v).capacity) ? (kvi_resize_full(v), 0) : 0), \ + ((v).items + ((v).size++))) + +/// Push value to a vector with preallocated array +/// +/// @param[out] v Vector to push to. +/// @param[in] x Value to push. +#define kvi_push(v, x) \ + (*kvi_pushp(v) = (x)) + +/// Free array of elements of a vector with preallocated array if needed +/// +/// @param[out] v Vector to free. +#define kvi_destroy(v) \ + do { \ + if ((v).items != (v).init_array) { \ + XFREE_CLEAR((v).items); \ + } \ + } while (0) + +#endif // NVIM_LIB_KVEC_H diff --git a/src/nvim/CMakeLists.txt b/src/nvim/CMakeLists.txt index a1b57f927e..f28b7a7e28 100755 --- a/src/nvim/CMakeLists.txt +++ b/src/nvim/CMakeLists.txt @@ -96,8 +96,8 @@ file(MAKE_DIRECTORY ${LINT_SUPPRESSES_ROOT}/src) glob_wrapper(NVIM_SOURCES *.c) glob_wrapper(NVIM_HEADERS *.h) -glob_wrapper(EXTERNAL_SOURCES ../xdiff/*.c ../mpack/*.c ../cjson/*.c) -glob_wrapper(EXTERNAL_HEADERS ../xdiff/*.h ../mpack/*.h ../cjson/*.h) +glob_wrapper(EXTERNAL_SOURCES ../xdiff/*.c ../mpack/*.c ../cjson/*.c ../klib/*.c) +glob_wrapper(EXTERNAL_HEADERS ../xdiff/*.h ../mpack/*.h ../cjson/*.h ../klib/*.h) foreach(subdir os diff --git a/src/nvim/api/private/defs.h b/src/nvim/api/private/defs.h index 9c7e59e4b3..2ae3ee6c7c 100644 --- a/src/nvim/api/private/defs.h +++ b/src/nvim/api/private/defs.h @@ -5,8 +5,8 @@ #include #include +#include "klib/kvec.h" #include "nvim/func_attr.h" -#include "nvim/lib/kvec.h" #include "nvim/types.h" #define ARRAY_DICT_INIT KV_INITIAL_VALUE diff --git a/src/nvim/api/private/helpers.c b/src/nvim/api/private/helpers.c index 22d2ffbaf1..b888d09343 100644 --- a/src/nvim/api/private/helpers.c +++ b/src/nvim/api/private/helpers.c @@ -8,6 +8,7 @@ #include #include +#include "klib/kvec.h" #include "nvim/api/private/converter.h" #include "nvim/api/private/defs.h" #include "nvim/api/private/helpers.h" @@ -22,7 +23,6 @@ #include "nvim/ex_eval.h" #include "nvim/extmark.h" #include "nvim/highlight_group.h" -#include "nvim/lib/kvec.h" #include "nvim/lua/executor.h" #include "nvim/map.h" #include "nvim/map_defs.h" diff --git a/src/nvim/api/private/helpers.h b/src/nvim/api/private/helpers.h index 2157ad0ec2..65215fa8c8 100644 --- a/src/nvim/api/private/helpers.h +++ b/src/nvim/api/private/helpers.h @@ -1,11 +1,11 @@ #ifndef NVIM_API_PRIVATE_HELPERS_H #define NVIM_API_PRIVATE_HELPERS_H +#include "klib/kvec.h" #include "nvim/api/private/defs.h" #include "nvim/decoration.h" #include "nvim/ex_eval_defs.h" #include "nvim/getchar.h" -#include "nvim/lib/kvec.h" #include "nvim/memory.h" #include "nvim/vim.h" diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h index 3019a1323c..c18a8209cf 100644 --- a/src/nvim/buffer_defs.h +++ b/src/nvim/buffer_defs.h @@ -41,7 +41,7 @@ typedef struct { // for Map(K, V) #include "nvim/map.h" // for kvec -#include "nvim/lib/kvec.h" +#include "klib/kvec.h" // for marktree #include "nvim/marktree.h" diff --git a/src/nvim/context.h b/src/nvim/context.h index c2deca12c9..ae77e66516 100644 --- a/src/nvim/context.h +++ b/src/nvim/context.h @@ -3,8 +3,8 @@ #include +#include "klib/kvec.h" #include "nvim/api/private/defs.h" -#include "nvim/lib/kvec.h" typedef struct { msgpack_sbuffer regs; ///< Registers. diff --git a/src/nvim/decoration_provider.c b/src/nvim/decoration_provider.c index a11a4d2b04..48664421a3 100644 --- a/src/nvim/decoration_provider.c +++ b/src/nvim/decoration_provider.c @@ -1,13 +1,13 @@ // 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 +#include "klib/kvec.h" #include "nvim/api/extmark.h" #include "nvim/api/private/helpers.h" #include "nvim/buffer.h" #include "nvim/decoration.h" #include "nvim/decoration_provider.h" #include "nvim/highlight.h" -#include "nvim/lib/kvec.h" #include "nvim/lua/executor.h" static kvec_t(DecorProvider) decor_providers = KV_INITIAL_VALUE; diff --git a/src/nvim/eval/decode.c b/src/nvim/eval/decode.c index d585509df4..94ef419bed 100644 --- a/src/nvim/eval/decode.c +++ b/src/nvim/eval/decode.c @@ -4,6 +4,7 @@ #include #include +#include "klib/kvec.h" #include "nvim/ascii.h" #include "nvim/charset.h" // vim_str2nr #include "nvim/eval.h" @@ -11,7 +12,6 @@ #include "nvim/eval/encode.h" #include "nvim/eval/typval.h" #include "nvim/globals.h" -#include "nvim/lib/kvec.h" #include "nvim/macros.h" #include "nvim/message.h" #include "nvim/vim.h" // OK, FAIL diff --git a/src/nvim/eval/encode.c b/src/nvim/eval/encode.c index 599bbae0f5..27d35ea24f 100644 --- a/src/nvim/eval/encode.c +++ b/src/nvim/eval/encode.c @@ -13,6 +13,7 @@ #include #include +#include "klib/kvec.h" #include "nvim/ascii.h" #include "nvim/buffer_defs.h" #include "nvim/charset.h" // vim_isprintc() @@ -21,7 +22,6 @@ #include "nvim/eval/typval.h" #include "nvim/eval/typval_encode.h" #include "nvim/garray.h" -#include "nvim/lib/kvec.h" #include "nvim/macros.h" #include "nvim/math.h" #include "nvim/mbyte.h" diff --git a/src/nvim/eval/typval_encode.c.h b/src/nvim/eval/typval_encode.c.h index 73b36b8611..ff4f92e40b 100644 --- a/src/nvim/eval/typval_encode.c.h +++ b/src/nvim/eval/typval_encode.c.h @@ -250,7 +250,7 @@ #include "nvim/eval/typval.h" #include "nvim/eval/typval_encode.h" #include "nvim/func_attr.h" -#include "nvim/lib/kvec.h" +#include "klib/kvec.h" // -V::1063 diff --git a/src/nvim/eval/typval_encode.h b/src/nvim/eval/typval_encode.h index ed70ba87ec..33e19c531c 100644 --- a/src/nvim/eval/typval_encode.h +++ b/src/nvim/eval/typval_encode.h @@ -10,9 +10,9 @@ #include #include +#include "klib/kvec.h" #include "nvim/eval/typval.h" #include "nvim/func_attr.h" -#include "nvim/lib/kvec.h" /// Type of the stack entry typedef enum { diff --git a/src/nvim/event/loop.h b/src/nvim/event/loop.h index 65980c6c05..c0bcda40ce 100644 --- a/src/nvim/event/loop.h +++ b/src/nvim/event/loop.h @@ -4,8 +4,8 @@ #include #include +#include "klib/klist.h" #include "nvim/event/multiqueue.h" -#include "nvim/lib/klist.h" #include "nvim/os/time.h" typedef void *WatcherPtr; diff --git a/src/nvim/ex_getln.c b/src/nvim/ex_getln.c index 2a91e9c672..2d39ced582 100644 --- a/src/nvim/ex_getln.c +++ b/src/nvim/ex_getln.c @@ -9,6 +9,7 @@ #include #include +#include "klib/kvec.h" #include "nvim/api/extmark.h" #include "nvim/api/vim.h" #include "nvim/arabic.h" @@ -40,7 +41,6 @@ #include "nvim/highlight_group.h" #include "nvim/indent.h" #include "nvim/keycodes.h" -#include "nvim/lib/kvec.h" #include "nvim/log.h" #include "nvim/main.h" #include "nvim/mapping.h" diff --git a/src/nvim/extmark.c b/src/nvim/extmark.c index 290d20b749..176ad0d5c8 100644 --- a/src/nvim/extmark.c +++ b/src/nvim/extmark.c @@ -30,6 +30,7 @@ #include +#include "klib/kbtree.h" #include "nvim/api/extmark.h" #include "nvim/buffer.h" #include "nvim/buffer_updates.h" @@ -37,7 +38,6 @@ #include "nvim/decoration.h" #include "nvim/extmark.h" #include "nvim/globals.h" -#include "nvim/lib/kbtree.h" #include "nvim/map.h" #include "nvim/memline.h" #include "nvim/pos.h" diff --git a/src/nvim/extmark_defs.h b/src/nvim/extmark_defs.h index 5570b5c71e..9ef4ec23e5 100644 --- a/src/nvim/extmark_defs.h +++ b/src/nvim/extmark_defs.h @@ -1,7 +1,7 @@ #ifndef NVIM_EXTMARK_DEFS_H #define NVIM_EXTMARK_DEFS_H -#include "nvim/lib/kvec.h" +#include "klib/kvec.h" #include "nvim/types.h" typedef struct { diff --git a/src/nvim/lib/kbtree.h b/src/nvim/lib/kbtree.h deleted file mode 100644 index 99f79952d7..0000000000 --- a/src/nvim/lib/kbtree.h +++ /dev/null @@ -1,477 +0,0 @@ -/*- - * 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. - */ - -// Gotchas -// ------- -// -// if you delete from a kbtree while iterating over it you must use -// kb_del_itr and not kb_del otherwise the iterator might point to freed memory. - -#ifndef NVIM_LIB_KBTREE_H -#define NVIM_LIB_KBTREE_H - -#include -#include -#include -#include - -#include "nvim/memory.h" - -#define KB_MAX_DEPTH 64 - -#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[]; \ - }; \ - typedef struct { \ - 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_destroy(kbnode_t, b) do { \ - int i; \ - unsigned int max = 8; \ - kbnode_t *x, **top, **stack = 0; \ - if (b->root) { \ - top = stack = (kbnode_t **)xcalloc(max, sizeof(kbnode_t *)); \ - *top++ = (b)->root; \ - while (top != stack) { \ - x = *--top; \ - if (x->is_internal == 0) { XFREE_CLEAR(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 **)xrealloc(stack, max * sizeof(kbnode_t *)); \ - top = stack + (max>>1); \ - } \ - *top++ = __KB_PTR(b, x)[i]; \ - } \ - XFREE_CLEAR(x); \ - } \ - } \ - XFREE_CLEAR(stack); \ -} while (0) - -#define __KB_GET_AUX1(name, key_t, kbnode_t, __cmp) \ - 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; \ - 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, kbnode_t) \ - static key_t *kb_getp_##name(kbtree_##name##_t *b, key_t * __restrict k) \ - { \ - if (!b->root) { \ - return 0; \ - } \ - 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, key_t k) \ - { \ - return kb_getp_##name(b, &k); \ - } - -#define __KB_INTERVAL(name, key_t, kbnode_t) \ - static inline void kb_intervalp_##name(kbtree_##name##_t *b, 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; \ - 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, 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 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)); \ - ++b->n_nodes; \ - z->is_internal = y->is_internal; \ - 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)[T - 1]; \ - ++x->n; \ - } \ - 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; \ - 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 * 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 inline key_t *kb_putp_##name(kbtree_##name##_t *b, 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; \ - if (r->n == 2 * T - 1) { \ - ++b->n_nodes; \ - 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); \ - r = s; \ - } \ - return __kb_putp_aux_##name(b, r, 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 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; \ - 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) >= 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) >= 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 == 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 *)); \ - 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; \ - XFREE_CLEAR(z); \ - return __kb_delp_aux_##name(b, y, k, s); \ - } \ - } \ - ++i; \ - 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 >= 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 == 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; \ - XFREE_CLEAR(xp); \ - xp = y; \ - } 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 *)); \ - 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; \ - XFREE_CLEAR(y); \ - } \ - } \ - return __kb_delp_aux_##name(b, xp, k, s); \ - } \ - static inline key_t kb_delp_##name(kbtree_##name##_t *b, 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]; \ - XFREE_CLEAR(x); \ - } \ - return ret; \ - } \ - static inline key_t kb_del_##name(kbtree_##name##_t *b, key_t k) \ - { \ - return kb_delp_##name(b, &k); \ - } - -#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 = NULL; \ - 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_##name##_t *itr) \ - { \ - if (itr->p == NULL) return 0; \ - for (;;) { \ - ++itr->p->i; \ - assert(itr->p->i <= 21); \ - 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; \ - } \ - if (itr->p == itr->stack) { \ - itr->p = NULL; \ - return 0; \ - } \ - --itr->p; \ - 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_##name##_t *itr) \ - { \ - if (itr->p == NULL) 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; \ - } \ - if (itr->p == itr->stack) { \ - itr->p = NULL; \ - return 0; \ - } \ - --itr->p; \ - --itr->p->i; \ - if (itr->p->x && itr->p->i >= 0) return 1; \ - } \ - } \ - static inline int kb_itr_getp_##name(kbtree_##name##_t *b, key_t * __restrict k, \ - kbitr_##name##_t *itr) \ - { \ - if (b->n_keys == 0) { \ - itr->p = NULL; \ - return 0; \ - } \ - 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; \ - assert(itr->p->i <= 21); \ - itr->p[1].x = itr->p->x->is_internal? __KB_PTR(b, itr->p->x)[i + 1] : 0; \ - ++itr->p; \ - } \ - itr->p->i = 0; \ - return 0; \ - } \ - 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) \ - { \ - 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_IMPL(name, key_t, kbnode_t, __cmp, T, ILEN) \ - __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) - -#define KB_DEFAULT_SIZE 512 - -#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) -#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_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(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) - -#define kb_generic_cmp(a, b) (((b) < (a)) - ((a) < (b))) -#define kb_str_cmp(a, b) strcmp(a, b) - -#endif // NVIM_LIB_KBTREE_H diff --git a/src/nvim/lib/khash.h b/src/nvim/lib/khash.h deleted file mode 100644 index 57a41f9c13..0000000000 --- a/src/nvim/lib/khash.h +++ /dev/null @@ -1,730 +0,0 @@ -/* The MIT License - - Copyright (c) 2008, 2009, 2011 by Attractive Chaos - - Permission is hereby granted, free of charge, to any person obtaining - a copy of this software and associated documentation files (the - "Software"), to deal in the Software without restriction, including - without limitation the rights to use, copy, modify, merge, publish, - distribute, sublicense, and/or sell copies of the Software, and to - permit persons to whom the Software is furnished to do so, subject to - the following conditions: - - The above copyright notice and this permission notice shall be - included in all copies or substantial portions of the Software. - - THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS - BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN - ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN - CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - SOFTWARE. - */ - -/* - Example: - - #include "nvim/khash.h" - KHASH_MAP_INIT_INT(32, char) - int main() { - int ret, is_missing; - khiter_t k; - khash_t(32) *h = kh_init(32); - k = kh_put(32, h, 5, &ret); - kh_value(h, k) = 10; - k = kh_get(32, h, 10); - is_missing = (k == kh_end(h)); - k = kh_get(32, h, 5); - kh_del(32, h, k); - for (k = kh_begin(h); k != kh_end(h); ++k) - if (kh_exist(h, k)) kh_value(h, k) = 1; - kh_destroy(32, h); - return 0; - } - */ - -/* - 2013-05-02 (0.2.8): - - * Use quadratic probing. When the capacity is power of 2, stepping function - i*(i+1)/2 guarantees to traverse each bucket. It is better than double - hashing on cache performance and is more robust than linear probing. - - In theory, double hashing should be more robust than quadratic probing. - However, my implementation is probably not for large hash tables, because - the second hash function is closely tied to the first hash function, - which reduce the effectiveness of double hashing. - - Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php - - 2011-12-29 (0.2.7): - - * Minor code clean up; no actual effect. - - 2011-09-16 (0.2.6): - - * The capacity is a power of 2. This seems to dramatically improve the - speed for simple keys. Thank Zilong Tan for the suggestion. Reference: - - - http://code.google.com/p/ulib/ - - http://nothings.org/computer/judy/ - - * Allow to optionally use linear probing which usually has better - performance for random input. Double hashing is still the default as it - is more robust to certain non-random input. - - * Added Wang's integer hash function (not used by default). This hash - function is more robust to certain non-random input. - - 2011-02-14 (0.2.5): - - * Allow to declare global functions. - - 2009-09-26 (0.2.4): - - * Improve portability - - 2008-09-19 (0.2.3): - - * Corrected the example - * Improved interfaces - - 2008-09-11 (0.2.2): - - * Improved speed a little in kh_put() - - 2008-09-10 (0.2.1): - - * Added kh_clear() - * Fixed a compiling error - - 2008-09-02 (0.2.0): - - * Changed to token concatenation which increases flexibility. - - 2008-08-31 (0.1.2): - - * Fixed a bug in kh_get(), which has not been tested previously. - - 2008-08-31 (0.1.1): - - * Added destructor - */ - -#ifndef NVIM_LIB_KHASH_H -#define NVIM_LIB_KHASH_H - -/*! - @header - - Generic hash table library. - */ - -#define AC_VERSION_KHASH_H "0.2.8" - -#include -#include -#include -#include - -#include "nvim/func_attr.h" -#include "nvim/memory.h" - -// compiler specific configuration - -#if UINT_MAX == 0xffffffffu -typedef unsigned int khint32_t; -#elif ULONG_MAX == 0xffffffffu -typedef unsigned long khint32_t; -#endif - -#if ULONG_MAX == ULLONG_MAX -typedef unsigned long khint64_t; -#else -typedef unsigned long long khint64_t; -#endif - -#ifdef _MSC_VER -# define kh_inline __inline -#else -# define kh_inline inline -#endif - -typedef khint32_t khint_t; -typedef khint_t khiter_t; - -#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2) -#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1) -#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3) -#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(khint_t)(1ul<<((i&0xfU)<<1))) -#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(khint_t)(2ul<<((i&0xfU)<<1))) -#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(khint_t)(3ul<<((i&0xfU)<<1))) -#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=(khint_t)1ul<<((i&0xfU)<<1)) - -#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4) - -#ifndef kroundup32 -# define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, \ - ++(x)) -#endif - -#ifndef kcalloc -# define kcalloc(N, Z) xcalloc(N, Z) -#endif -#ifndef kmalloc -# define kmalloc(Z) xmalloc(Z) -#endif -#ifndef krealloc -# define krealloc(P, Z) xrealloc(P, Z) -#endif -#ifndef kfree -# define kfree(P) XFREE_CLEAR(P) -#endif - -#define __ac_HASH_UPPER 0.77 - -#define __KHASH_TYPE(name, khkey_t, khval_t) \ - typedef struct { \ - khint_t n_buckets, size, n_occupied, upper_bound; \ - khint32_t *flags; \ - khkey_t *keys; \ - khval_t *vals; \ - } kh_##name##_t; - -#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ - extern kh_##name##_t *kh_init_##name(void); \ - extern void kh_dealloc_##name(kh_##name##_t *h); \ - extern void kh_destroy_##name(kh_##name##_t *h); \ - extern void kh_clear_##name(kh_##name##_t *h); \ - extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \ - extern void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \ - extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \ - extern void kh_del_##name(kh_##name##_t *h, khint_t x); - -#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, \ - __hash_equal) \ - SCOPE kh_##name##_t *kh_init_##name(void) \ - REAL_FATTR_UNUSED; \ - SCOPE kh_##name##_t *kh_init_##name(void) { \ - return (kh_##name##_t *)kcalloc(1, sizeof(kh_##name##_t)); \ - } \ - SCOPE void kh_dealloc_##name(kh_##name##_t *h) \ - REAL_FATTR_UNUSED; \ - SCOPE void kh_dealloc_##name(kh_##name##_t *h) \ - { \ - kfree(h->keys); \ - kfree(h->flags); \ - kfree(h->vals); \ - } \ - SCOPE void kh_destroy_##name(kh_##name##_t *h) \ - REAL_FATTR_UNUSED; \ - SCOPE void kh_destroy_##name(kh_##name##_t *h) \ - { \ - if (h) { \ - kh_dealloc_##name(h); \ - kfree(h); \ - } \ - } \ - SCOPE void kh_clear_##name(kh_##name##_t *h) \ - REAL_FATTR_UNUSED; \ - SCOPE void kh_clear_##name(kh_##name##_t *h) \ - { \ - if (h && h->flags) { \ - memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \ - h->size = h->n_occupied = 0; \ - } \ - } \ - SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ - REAL_FATTR_UNUSED; \ - SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ - { \ - if (h->n_buckets) { \ - khint_t k, i, last, mask, step = 0; \ - mask = h->n_buckets - 1; \ - k = __hash_func(key); i = k & mask; \ - last = i; \ - while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || \ - !__hash_equal(h->keys[i], key))) { \ - i = (i + (++step)) & mask; \ - if (i == last) { \ - return h->n_buckets; \ - } \ - } \ - return __ac_iseither(h->flags, i) ? h->n_buckets : i; \ - } else { \ - return 0; \ - } \ - } \ - SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ - REAL_FATTR_UNUSED; \ - SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ - { /* This function uses 0.25*n_buckets bytes of working space instead of */ \ - /* [sizeof(key_t+val_t)+.25]*n_buckets. */ \ - khint32_t *new_flags = 0; \ - khint_t j = 1; \ - { \ - kroundup32(new_n_buckets); \ - if (new_n_buckets < 4) { \ - new_n_buckets = 4; \ - } \ - /* requested size is too small */ \ - if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) { \ - j = 0; \ - } else { /* hash table size to be changed (shrink or expand); rehash */ \ - new_flags = (khint32_t *)kmalloc(__ac_fsize(new_n_buckets) \ - * sizeof(khint32_t)); \ - memset(new_flags, 0xaa, \ - __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ - if (h->n_buckets < new_n_buckets) { /* expand */ \ - khkey_t *new_keys = (khkey_t *)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ - h->keys = new_keys; \ - if (kh_is_map) { \ - khval_t *new_vals = \ - (khval_t *)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ - h->vals = new_vals; \ - } \ - } /* otherwise shrink */ \ - } \ - } \ - if (j) { /* rehashing is needed */ \ - for (j = 0; j != h->n_buckets; ++j) { \ - if (__ac_iseither(h->flags, j) == 0) { \ - khkey_t key = h->keys[j]; \ - khval_t val; \ - khint_t new_mask; \ - new_mask = new_n_buckets - 1; \ - if (kh_is_map) { \ - val = h->vals[j]; \ - } \ - __ac_set_isdel_true(h->flags, j); \ - /* kick-out process; sort of like in Cuckoo hashing */ \ - while (1) { \ - khint_t k, i, step = 0; \ - k = __hash_func(key); \ - i = k & new_mask; \ - while (!__ac_isempty(new_flags, i)) { \ - i = (i + (++step)) & new_mask; \ - } \ - __ac_set_isempty_false(new_flags, i); \ - /* kick out the existing element */ \ - if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { \ - { \ - khkey_t tmp = h->keys[i]; \ - h->keys[i] = key; \ - key = tmp; \ - } \ - if (kh_is_map) { \ - khval_t tmp = h->vals[i]; \ - h->vals[i] = val; \ - val = tmp; \ - } \ - /* mark it as deleted in the old hash table */ \ - __ac_set_isdel_true(h->flags, i); \ - } else { /* write the element and jump out of the loop */ \ - h->keys[i] = key; \ - if (kh_is_map) { \ - h->vals[i] = val; \ - } \ - break; \ - } \ - } \ - } \ - } \ - if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ - h->keys = (khkey_t *)krealloc((void *)h->keys, \ - new_n_buckets * sizeof(khkey_t)); \ - if (kh_is_map) { \ - h->vals = (khval_t *)krealloc((void *)h->vals, \ - new_n_buckets * sizeof(khval_t)); \ - } \ - } \ - kfree(h->flags); /* free the working space */ \ - h->flags = new_flags; \ - h->n_buckets = new_n_buckets; \ - h->n_occupied = h->size; \ - h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ - } \ - } \ - SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ - REAL_FATTR_UNUSED; \ - SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ - { \ - khint_t x; \ - if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ - if (h->n_buckets > (h->size << 1)) { \ - kh_resize_##name(h, h->n_buckets - 1); /* clear "deleted" elements */ \ - } else { \ - kh_resize_##name(h, h->n_buckets + 1); /* expand the hash table */ \ - } \ - } /* TODO: implement automatically shrinking; */ \ - /* resize() already support shrinking */ \ - { \ - khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ - x = site = h->n_buckets; \ - k = __hash_func(key); \ - i = k & mask; \ - if (__ac_isempty(h->flags, i)) { \ - x = i; /* for speed up */ \ - } else { \ - last = i; \ - while (!__ac_isempty(h->flags, i) \ - && (__ac_isdel(h->flags, i) \ - || !__hash_equal(h->keys[i], key))) { \ - if (__ac_isdel(h->flags, i)) { \ - site = i; \ - } \ - i = (i + (++step)) & mask; \ - if (i == last) { \ - x = site; \ - break; \ - } \ - } \ - if (x == h->n_buckets) { \ - if (__ac_isempty(h->flags, i) && site != h->n_buckets) { \ - x = site; \ - } else { \ - x = i; \ - } \ - } \ - } \ - } \ - if (__ac_isempty(h->flags, x)) { /* not present at all */ \ - h->keys[x] = key; \ - __ac_set_isboth_false(h->flags, x); \ - h->size++; \ - h->n_occupied++; \ - *ret = 1; \ - } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ - h->keys[x] = key; \ - __ac_set_isboth_false(h->flags, x); \ - h->size++; \ - *ret = 2; \ - } else { \ - *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ - } \ - return x; \ - } \ - SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ - REAL_FATTR_UNUSED; \ - SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ - { \ - if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ - __ac_set_isdel_true(h->flags, x); \ - --h->size; \ - } \ - } - -#define KHASH_DECLARE(name, khkey_t, khval_t) \ - __KHASH_TYPE(name, khkey_t, khval_t) \ - __KHASH_PROTOTYPES(name, khkey_t, khval_t) - -#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ - __KHASH_TYPE(name, khkey_t, khval_t) \ - __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) - -#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ - KHASH_INIT2(name, static kh_inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) - -// --- BEGIN OF HASH FUNCTIONS --- - -/*! @function - @abstract Integer hash function - @param key The integer [khint32_t] - @return The hash value [khint_t] - */ -#define kh_int_hash_func(key) (khint32_t)(key) -/*! @function - @abstract Integer comparison function - */ -#define kh_int_hash_equal(a, b) ((a) == (b)) -/*! @function - @abstract 64-bit integer hash function - @param key The integer [khint64_t] - @return The hash value [khint_t] - */ -#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11) -/*! @function - @abstract 64-bit integer comparison function - */ -#define kh_int64_hash_equal(a, b) ((a) == (b)) -/*! @function - @abstract const char* hash function - @param s Pointer to a null terminated string - @return The hash value - */ -static kh_inline khint_t __ac_X31_hash_string(const char *s) -{ - khint_t h = (khint_t)*s; - if (h) { - for (++s; *s; ++s) { h = (h << 5) - h + (uint8_t)*s; } - } - return h; -} -/*! @function - @abstract Another interface to const char* hash function - @param key Pointer to a null terminated string [const char*] - @return The hash value [khint_t] - */ -#define kh_str_hash_func(key) __ac_X31_hash_string(key) -/*! @function - @abstract Const char* comparison function - */ -#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0) - -static kh_inline khint_t __ac_Wang_hash(khint_t key) -{ - key += ~(key << 15); - key ^= (key >> 10); - key += (key << 3); - key ^= (key >> 6); - key += ~(key << 11); - key ^= (key >> 16); - return key; -} -#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key) - -// --- END OF HASH FUNCTIONS --- - -// Other convenient macros... - -/*! - @abstract Type of the hash table. - @param name Name of the hash table [symbol] - */ -#define khash_t(name) kh_##name##_t - -/*! @function - @abstract Initiate a hash table. - @param name Name of the hash table [symbol] - @return Pointer to the hash table [khash_t(name)*] - */ -#define kh_init(name) kh_init_##name() - -/*! @function - @abstract Destroy a hash table. - @param name Name of the hash table [symbol] - @param h Pointer to the hash table [khash_t(name)*] - */ -#define kh_destroy(name, h) kh_destroy_##name(h) - -/*! @function - @abstract Free memory referenced directly inside a hash table. - @param name Name of the hash table [symbol] - @param h Pointer to the hash table [khash_t(name)*] - */ -#define kh_dealloc(name, h) kh_dealloc_##name(h) - -/*! @function - @abstract Reset a hash table without deallocating memory. - @param name Name of the hash table [symbol] - @param h Pointer to the hash table [khash_t(name)*] - */ -#define kh_clear(name, h) kh_clear_##name(h) - -/*! @function - @abstract Resize a hash table. - @param name Name of the hash table [symbol] - @param h Pointer to the hash table [khash_t(name)*] - @param s New size [khint_t] - */ -#define kh_resize(name, h, s) kh_resize_##name(h, s) - -/*! @function - @abstract Insert a key to the hash table. - @param name Name of the hash table [symbol] - @param h Pointer to the hash table [khash_t(name)*] - @param k Key [type of keys] - @param r Extra return code: -1 if the operation failed; - 0 if the key is present in the hash table; - 1 if the bucket is empty (never used); 2 if the element in - the bucket has been deleted [int*] - @return Iterator to the inserted element [khint_t] - */ -#define kh_put(name, h, k, r) kh_put_##name(h, k, r) - -/*! @function - @abstract Retrieve a key from the hash table. - @param name Name of the hash table [symbol] - @param h Pointer to the hash table [khash_t(name)*] - @param k Key [type of keys] - @return Iterator to the found element, or kh_end(h) if the element is absent [khint_t] - */ -#define kh_get(name, h, k) kh_get_##name(h, k) - -/*! @function - @abstract Remove a key from the hash table. - @param name Name of the hash table [symbol] - @param h Pointer to the hash table [khash_t(name)*] - @param k Iterator to the element to be deleted [khint_t] - */ -#define kh_del(name, h, k) kh_del_##name(h, k) - -/*! @function - @abstract Test whether a bucket contains data. - @param h Pointer to the hash table [khash_t(name)*] - @param x Iterator to the bucket [khint_t] - @return 1 if containing data; 0 otherwise [int] - */ -#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x))) - -/*! @function - @abstract Get key given an iterator - @param h Pointer to the hash table [khash_t(name)*] - @param x Iterator to the bucket [khint_t] - @return Key [type of keys] - */ -#define kh_key(h, x) ((h)->keys[x]) - -/*! @function - @abstract Get value given an iterator - @param h Pointer to the hash table [khash_t(name)*] - @param x Iterator to the bucket [khint_t] - @return Value [type of values] - @discussion For hash sets, calling this results in segfault. - */ -#define kh_val(h, x) ((h)->vals[x]) - -/*! @function - @abstract Alias of kh_val() - */ -#define kh_value(h, x) ((h)->vals[x]) - -/*! @function - @abstract Get the start iterator - @param h Pointer to the hash table [khash_t(name)*] - @return The start iterator [khint_t] - */ -#define kh_begin(h) (khint_t)(0) - -/*! @function - @abstract Get the end iterator - @param h Pointer to the hash table [khash_t(name)*] - @return The end iterator [khint_t] - */ -#define kh_end(h) ((h)->n_buckets) - -/*! @function - @abstract Get the number of elements in the hash table - @param h Pointer to the hash table [khash_t(name)*] - @return Number of elements in the hash table [khint_t] - */ -#define kh_size(h) ((h)->size) - -/*! @function - @abstract Get the number of buckets in the hash table - @param h Pointer to the hash table [khash_t(name)*] - @return Number of buckets in the hash table [khint_t] - */ -#define kh_n_buckets(h) ((h)->n_buckets) - -/*! @function - @abstract Iterate over the entries in the hash table - @param h Pointer to the hash table [khash_t(name)*] - @param kvar Variable to which key will be assigned - @param vvar Variable to which value will be assigned - @param code Block of code to execute - */ -#define kh_foreach(h, kvar, vvar, code) { khint_t __i; \ - for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ - if (!kh_exist(h, __i)) continue; \ - (kvar) = kh_key(h, __i); \ - (vvar) = kh_val(h, __i); \ - code; \ - } } - -/*! @function - @abstract Iterate over the values in the hash table - @param h Pointer to the hash table [khash_t(name)*] - @param vvar Variable to which value will be assigned - @param code Block of code to execute - */ -#define kh_foreach_value(h, vvar, code) { khint_t __i; \ - for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ - if (!kh_exist(h, __i)) continue; \ - (vvar) = kh_val(h, __i); \ - code; \ - } } - -/*! @function - @abstract Iterate over the keys in the hash table - @param h Pointer to the hash table [khash_t(name)*] - @param kvar Variable to which value will be assigned - @param code Block of code to execute - */ -#define kh_foreach_key(h, kvar, code) \ - { \ - khint_t __i; \ - for (__i = kh_begin(h); __i != kh_end(h); __i++) { \ - if (!kh_exist(h, __i)) { \ - continue; \ - } \ - (kvar) = kh_key(h, __i); \ - code; \ - } \ - } - -// More convenient interfaces - -/*! @function - @abstract Instantiate a hash set containing integer keys - @param name Name of the hash table [symbol] - */ -#define KHASH_SET_INIT_INT(name) \ - KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal) - -/*! @function - @abstract Instantiate a hash map containing integer keys - @param name Name of the hash table [symbol] - @param khval_t Type of values [type] - */ -#define KHASH_MAP_INIT_INT(name, khval_t) \ - KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal) - -/*! @function - @abstract Instantiate a hash map containing 64-bit integer keys - @param name Name of the hash table [symbol] - */ -#define KHASH_SET_INIT_INT64(name) \ - KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal) - -/*! @function - @abstract Instantiate a hash map containing 64-bit integer keys - @param name Name of the hash table [symbol] - @param khval_t Type of values [type] - */ -#define KHASH_MAP_INIT_INT64(name, khval_t) \ - KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal) - -typedef const char *kh_cstr_t; -/*! @function - @abstract Instantiate a hash map containing const char* keys - @param name Name of the hash table [symbol] - */ -#define KHASH_SET_INIT_STR(name) \ - KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal) - -/*! @function - @abstract Instantiate a hash map containing const char* keys - @param name Name of the hash table [symbol] - @param khval_t Type of values [type] - */ -#define KHASH_MAP_INIT_STR(name, khval_t) \ - KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) - -/*! @function - @abstract Return a literal for an empty hash table. - @param name Name of the hash table [symbol] - */ -#define KHASH_EMPTY_TABLE(name) \ - ((kh_##name##_t) { \ - .n_buckets = 0, \ - .size = 0, \ - .n_occupied = 0, \ - .upper_bound = 0, \ - .flags = NULL, \ - .keys = NULL, \ - .vals = NULL, \ - }) -#endif // NVIM_LIB_KHASH_H diff --git a/src/nvim/lib/klist.h b/src/nvim/lib/klist.h deleted file mode 100644 index a9abbc6dc2..0000000000 --- a/src/nvim/lib/klist.h +++ /dev/null @@ -1,144 +0,0 @@ -/* The MIT License - - Copyright (c) 2008-2009, by Attractive Chaos - - Permission is hereby granted, free of charge, to any person obtaining - a copy of this software and associated documentation files (the - "Software"), to deal in the Software without restriction, including - without limitation the rights to use, copy, modify, merge, publish, - distribute, sublicense, and/or sell copies of the Software, and to - permit persons to whom the Software is furnished to do so, subject to - the following conditions: - - The above copyright notice and this permission notice shall be - included in all copies or substantial portions of the Software. - - THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS - BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN - ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN - CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - SOFTWARE. - */ - -#ifndef _AC_KLIST_H -#define _AC_KLIST_H - -#include -#include - -#include "nvim/func_attr.h" -#include "nvim/memory.h" - -#define KMEMPOOL_INIT(name, kmptype_t, kmpfree_f) \ - typedef struct { \ - size_t cnt, n, max; \ - kmptype_t **buf; \ - } kmp_##name##_t; \ - static inline kmp_##name##_t *kmp_init_##name(void) { \ - return xcalloc(1, sizeof(kmp_##name##_t)); \ - } \ - static inline void kmp_destroy_##name(kmp_##name##_t *mp) \ - REAL_FATTR_UNUSED; \ - static inline void kmp_destroy_##name(kmp_##name##_t *mp) { \ - size_t k; \ - for (k = 0; k < mp->n; k++) { \ - kmpfree_f(mp->buf[k]); XFREE_CLEAR(mp->buf[k]); \ - } \ - XFREE_CLEAR(mp->buf); XFREE_CLEAR(mp); \ - } \ - static inline kmptype_t *kmp_alloc_##name(kmp_##name##_t *mp) { \ - mp->cnt++; \ - if (mp->n == 0) { \ - return xcalloc(1, sizeof(kmptype_t)); \ - } \ - return mp->buf[--mp->n]; \ - } \ - static inline void kmp_free_##name(kmp_##name##_t *mp, kmptype_t *p) { \ - mp->cnt--; \ - if (mp->n == mp->max) { \ - mp->max = mp->max ? (mp->max << 1) : 16; \ - mp->buf = xrealloc(mp->buf, sizeof(kmptype_t *) * mp->max); \ - } \ - mp->buf[mp->n++] = p; \ - } - -#define kmempool_t(name) kmp_##name##_t -#define kmp_init(name) kmp_init_##name() -#define kmp_destroy(name, mp) kmp_destroy_##name(mp) -#define kmp_alloc(name, mp) kmp_alloc_##name(mp) -#define kmp_free(name, mp, p) kmp_free_##name(mp, p) - -#define KLIST_INIT(name, kltype_t, kmpfree_t) \ - struct __kl1_##name { \ - kltype_t data; \ - struct __kl1_##name *next; \ - }; \ - typedef struct __kl1_##name kl1_##name; \ - KMEMPOOL_INIT(name, kl1_##name, kmpfree_t) \ - typedef struct { \ - kl1_##name *head, *tail; \ - kmp_##name##_t *mp; \ - size_t size; \ - } kl_##name##_t; \ - static inline kl_##name##_t *kl_init_##name(void) { \ - kl_##name##_t *kl = xcalloc(1, sizeof(kl_##name##_t)); \ - kl->mp = kmp_init(name); \ - kl->head = kl->tail = kmp_alloc(name, kl->mp); \ - kl->head->next = 0; \ - return kl; \ - } \ - static inline void kl_destroy_##name(kl_##name##_t *kl) \ - REAL_FATTR_UNUSED; \ - static inline void kl_destroy_##name(kl_##name##_t *kl) { \ - kl1_##name *p; \ - for (p = kl->head; p != kl->tail; p = p->next) { \ - kmp_free(name, kl->mp, p); \ - } \ - kmp_free(name, kl->mp, p); \ - kmp_destroy(name, kl->mp); \ - XFREE_CLEAR(kl); \ - } \ - static inline void kl_push_##name(kl_##name##_t *kl, kltype_t d) { \ - kl1_##name *q, *p = kmp_alloc(name, kl->mp); \ - q = kl->tail; p->next = 0; kl->tail->next = p; kl->tail = p; \ - kl->size++; \ - q->data = d; \ - } \ - static inline kltype_t kl_shift_at_##name(kl_##name##_t *kl, \ - kl1_##name **n) { \ - assert((*n)->next); \ - kl1_##name *p; \ - kl->size--; \ - p = *n; \ - *n = (*n)->next; \ - if (p == kl->head) { \ - kl->head = *n; \ - } \ - kltype_t d = p->data; \ - kmp_free(name, kl->mp, p); \ - return d; \ - } - -#define kliter_t(name) kl1_##name -#define klist_t(name) kl_##name##_t -#define kl_val(iter) ((iter)->data) -#define kl_next(iter) ((iter)->next) -#define kl_begin(kl) ((kl)->head) -#define kl_end(kl) ((kl)->tail) - -#define kl_init(name) kl_init_##name() -#define kl_destroy(name, kl) kl_destroy_##name(kl) -#define kl_push(name, kl, d) kl_push_##name(kl, d) -#define kl_shift_at(name, kl, node) kl_shift_at_##name(kl, node) -#define kl_shift(name, kl) kl_shift_at(name, kl, &kl->head) -#define kl_empty(kl) ((kl)->size == 0) -// Iteration macros. It's ok to modify the list while iterating as long as a -// `break` statement is executed before the next iteration. -#define kl_iter(name, kl, p) kl_iter_at(name, kl, p, NULL) -#define kl_iter_at(name, kl, p, h) \ - for (kl1_##name **p = h ? h : &kl->head; *p != kl->tail; p = &(*p)->next) - -#endif diff --git a/src/nvim/lib/kvec.h b/src/nvim/lib/kvec.h deleted file mode 100644 index b5b3adf7d2..0000000000 --- a/src/nvim/lib/kvec.h +++ /dev/null @@ -1,236 +0,0 @@ -// The MIT License -// -// Copyright (c) 2008, by Attractive Chaos -// -// Permission is hereby granted, free of charge, to any person obtaining -// a copy of this software and associated documentation files (the -// "Software"), to deal in the Software without restriction, including -// without limitation the rights to use, copy, modify, merge, publish, -// distribute, sublicense, and/or sell copies of the Software, and to -// permit persons to whom the Software is furnished to do so, subject to -// the following conditions: -// -// The above copyright notice and this permission notice shall be -// included in all copies or substantial portions of the Software. -// -// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, -// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF -// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS -// BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN -// ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN -// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -// SOFTWARE. - -// An example: -// -// #include "kvec.h" -// int main() { -// kvec_t(int) array = KV_INITIAL_VALUE; -// kv_push(array, 10); // append -// kv_a(array, 20) = 5; // dynamic -// kv_A(array, 20) = 4; // static -// kv_destroy(array); -// return 0; -// } - -#ifndef NVIM_LIB_KVEC_H -#define NVIM_LIB_KVEC_H - -#include -#include - -#include "nvim/memory.h" -#include "nvim/os/os_defs.h" - -#define kv_roundup32(x) \ - ((--(x)), \ - ((x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16), \ - (++(x))) - -#define KV_INITIAL_VALUE { .size = 0, .capacity = 0, .items = NULL } - -#define kvec_t(type) \ - struct { \ - size_t size; \ - size_t capacity; \ - type *items; \ - } - -#define kv_init(v) ((v).size = (v).capacity = 0, (v).items = 0) -#define kv_destroy(v) \ - do { \ - xfree((v).items); \ - kv_init(v); \ - } while (0) -#define kv_A(v, i) ((v).items[(i)]) -#define kv_pop(v) ((v).items[--(v).size]) -#define kv_size(v) ((v).size) -#define kv_max(v) ((v).capacity) -#define kv_Z(v, i) kv_A(v, kv_size(v) - (i) - 1) -#define kv_last(v) kv_Z(v, 0) - -/// Drop last n items from kvec without resizing -/// -/// Previously spelled as `(void)kv_pop(v)`, repeated n times. -/// -/// @param[out] v Kvec to drop items from. -/// @param[in] n Number of elements to drop. -#define kv_drop(v, n) ((v).size -= (n)) - -#define kv_resize(v, s) \ - ((v).capacity = (s), \ - (v).items = xrealloc((v).items, sizeof((v).items[0]) * (v).capacity)) - -#define kv_resize_full(v) \ - kv_resize(v, (v).capacity ? (v).capacity << 1 : 8) - -#define kv_copy(v1, v0) \ - do { \ - if ((v1).capacity < (v0).size) { \ - kv_resize(v1, (v0).size); \ - } \ - (v1).size = (v0).size; \ - memcpy((v1).items, (v0).items, sizeof((v1).items[0]) * (v0).size); \ - } while (0) - -/// fit at least "len" more items -#define kv_ensure_space(v, len) \ - do { \ - if ((v).capacity < (v).size + len) { \ - (v).capacity = (v).size + len; \ - kv_roundup32((v).capacity); \ - kv_resize((v), (v).capacity); \ - } \ - } while (0) - -#define kv_concat_len(v, data, len) \ - do { \ - kv_ensure_space(v, len); \ - memcpy((v).items + (v).size, data, sizeof((v).items[0]) * len); \ - (v).size = (v).size + len; \ - } while (0) - -#define kv_concat(v, str) kv_concat_len(v, str, STRLEN(str)) -#define kv_splice(v1, v0) kv_concat_len(v1, (v0).items, (v0).size) - -#define kv_pushp(v) \ - ((((v).size == (v).capacity) ? (kv_resize_full(v), 0) : 0), \ - ((v).items + ((v).size++))) - -#define kv_push(v, x) \ - (*kv_pushp(v) = (x)) - -#define kv_pushp_c(v) ((v).items + ((v).size++)) -#define kv_push_c(v, x) (*kv_pushp_c(v) = (x)) - -#define kv_a(v, i) \ - (*(((v).capacity <= (size_t)(i) \ - ? ((v).capacity = (v).size = (i) + 1, \ - kv_roundup32((v).capacity), \ - kv_resize((v), (v).capacity), 0UL) \ - : ((v).size <= (size_t)(i) \ - ? (v).size = (i) + 1 \ - : 0UL)), \ - &(v).items[(i)])) - -#define kv_printf(v, ...) kv_do_printf(&(v), __VA_ARGS__) - -/// Type of a vector with a few first members allocated on stack -/// -/// Is compatible with #kv_A, #kv_pop, #kv_size, #kv_max, #kv_last. -/// Is not compatible with #kv_resize, #kv_resize_full, #kv_copy, #kv_push, -/// #kv_pushp, #kv_a, #kv_destroy. -/// -/// @param[in] type Type of vector elements. -/// @param[in] init_size Number of the elements in the initial array. -#define kvec_withinit_t(type, INIT_SIZE) \ - struct { \ - size_t size; \ - size_t capacity; \ - type *items; \ - type init_array[INIT_SIZE]; \ - } - -/// Initialize vector with preallocated array -/// -/// @param[out] v Vector to initialize. -#define kvi_init(v) \ - ((v).capacity = ARRAY_SIZE((v).init_array), \ - (v).size = 0, \ - (v).items = (v).init_array) - -/// Move data to a new destination and free source -static inline void *_memcpy_free(void *const restrict dest, void *const restrict src, - const size_t size) - FUNC_ATTR_NONNULL_ALL FUNC_ATTR_NONNULL_RET FUNC_ATTR_ALWAYS_INLINE -{ - memcpy(dest, src, size); - XFREE_CLEAR(src); - return dest; -} - -// -V:kvi_push:512 - -/// Resize vector with preallocated array -/// -/// @note May not resize to an array smaller then init_array: if requested, -/// init_array will be used. -/// -/// @param[out] v Vector to resize. -/// @param[in] s New size. -#define kvi_resize(v, s) \ - ((v).capacity = ((s) > ARRAY_SIZE((v).init_array) \ - ? (s) \ - : ARRAY_SIZE((v).init_array)), \ - (v).items = ((v).capacity == ARRAY_SIZE((v).init_array) \ - ? ((v).items == (v).init_array \ - ? (v).items \ - : _memcpy_free((v).init_array, (v).items, \ - (v).size * sizeof((v).items[0]))) \ - : ((v).items == (v).init_array \ - ? memcpy(xmalloc((v).capacity * sizeof((v).items[0])), \ - (v).items, \ - (v).size * sizeof((v).items[0])) \ - : xrealloc((v).items, \ - (v).capacity * sizeof((v).items[0]))))) - -/// Resize vector with preallocated array when it is full -/// -/// @param[out] v Vector to resize. -#define kvi_resize_full(v) \ - /* ARRAY_SIZE((v).init_array) is the minimal capacity of this vector. */ \ - /* Thus when vector is full capacity may not be zero and it is safe */ \ - /* not to bother with checking whether (v).capacity is 0. But now */ \ - /* capacity is not guaranteed to have size that is a power of 2, it is */ \ - /* hard to fix this here and is not very necessary if users will use */ \ - /* 2^x initial array size. */ \ - kvi_resize(v, (v).capacity << 1) - -/// Get location where to store new element to a vector with preallocated array -/// -/// @param[in,out] v Vector to push to. -/// -/// @return Pointer to the place where new value should be stored. -#define kvi_pushp(v) \ - ((((v).size == (v).capacity) ? (kvi_resize_full(v), 0) : 0), \ - ((v).items + ((v).size++))) - -/// Push value to a vector with preallocated array -/// -/// @param[out] v Vector to push to. -/// @param[in] x Value to push. -#define kvi_push(v, x) \ - (*kvi_pushp(v) = (x)) - -/// Free array of elements of a vector with preallocated array if needed -/// -/// @param[out] v Vector to free. -#define kvi_destroy(v) \ - do { \ - if ((v).items != (v).init_array) { \ - XFREE_CLEAR((v).items); \ - } \ - } while (0) - -#endif // NVIM_LIB_KVEC_H diff --git a/src/nvim/lua/converter.c b/src/nvim/lua/converter.c index 735a75a6f1..bdb0719809 100644 --- a/src/nvim/lua/converter.c +++ b/src/nvim/lua/converter.c @@ -15,12 +15,12 @@ #include "nvim/memory.h" // FIXME: vim.h is not actually needed, but otherwise it states MAXPATHL is // redefined +#include "klib/kvec.h" #include "nvim/ascii.h" #include "nvim/eval/decode.h" #include "nvim/eval/typval.h" #include "nvim/eval/userfunc.h" #include "nvim/globals.h" -#include "nvim/lib/kvec.h" #include "nvim/lua/converter.h" #include "nvim/lua/executor.h" #include "nvim/macros.h" diff --git a/src/nvim/lua/treesitter.c b/src/nvim/lua/treesitter.c index f3c67e265f..64cace9ab4 100644 --- a/src/nvim/lua/treesitter.c +++ b/src/nvim/lua/treesitter.c @@ -16,9 +16,9 @@ #include #include +#include "klib/kvec.h" #include "nvim/api/private/helpers.h" #include "nvim/buffer.h" -#include "nvim/lib/kvec.h" #include "nvim/log.h" #include "nvim/lua/treesitter.h" #include "nvim/map.h" diff --git a/src/nvim/map.c b/src/nvim/map.c index 1561b089a7..24478c6091 100644 --- a/src/nvim/map.c +++ b/src/nvim/map.c @@ -14,7 +14,7 @@ #include #include -#include "nvim/lib/khash.h" +#include "klib/khash.h" #include "nvim/map.h" #include "nvim/map_defs.h" #include "nvim/memory.h" diff --git a/src/nvim/map_defs.h b/src/nvim/map_defs.h index 7b4596ce2e..61afedbe50 100644 --- a/src/nvim/map_defs.h +++ b/src/nvim/map_defs.h @@ -1,7 +1,7 @@ #ifndef NVIM_MAP_DEFS_H #define NVIM_MAP_DEFS_H -#include "nvim/lib/khash.h" +#include "klib/khash.h" typedef const char *cstr_t; typedef void *ptr_t; diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 03340a99d6..ad1680322c 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -49,8 +49,8 @@ #include +#include "klib/kvec.h" #include "nvim/garray.h" -#include "nvim/lib/kvec.h" #include "nvim/marktree.h" #define T MT_BRANCH_FACTOR diff --git a/src/nvim/message.h b/src/nvim/message.h index 811e621c11..31cd54f18c 100644 --- a/src/nvim/message.h +++ b/src/nvim/message.h @@ -5,9 +5,9 @@ #include #include +#include "klib/kvec.h" #include "nvim/api/private/defs.h" #include "nvim/grid_defs.h" -#include "nvim/lib/kvec.h" #include "nvim/macros.h" #include "nvim/types.h" diff --git a/src/nvim/msgpack_rpc/channel.c b/src/nvim/msgpack_rpc/channel.c index d22bcb29d5..71ed5ccf81 100644 --- a/src/nvim/msgpack_rpc/channel.c +++ b/src/nvim/msgpack_rpc/channel.c @@ -7,6 +7,7 @@ #include #include +#include "klib/kvec.h" #include "nvim/api/private/helpers.h" #include "nvim/api/ui.h" #include "nvim/api/vim.h" @@ -18,7 +19,6 @@ #include "nvim/event/rstream.h" #include "nvim/event/socket.h" #include "nvim/event/wstream.h" -#include "nvim/lib/kvec.h" #include "nvim/log.h" #include "nvim/main.h" #include "nvim/map.h" diff --git a/src/nvim/msgpack_rpc/helpers.c b/src/nvim/msgpack_rpc/helpers.c index 488321be42..ddca9afad0 100644 --- a/src/nvim/msgpack_rpc/helpers.c +++ b/src/nvim/msgpack_rpc/helpers.c @@ -5,10 +5,10 @@ #include #include +#include "klib/kvec.h" #include "nvim/api/private/dispatch.h" #include "nvim/api/private/helpers.h" #include "nvim/assert.h" -#include "nvim/lib/kvec.h" #include "nvim/log.h" #include "nvim/memory.h" #include "nvim/msgpack_rpc/helpers.h" diff --git a/src/nvim/ops.c b/src/nvim/ops.c index 6391644f83..dee23e9193 100644 --- a/src/nvim/ops.c +++ b/src/nvim/ops.c @@ -9,6 +9,7 @@ #include #include +#include "klib/kvec.h" #include "nvim/ascii.h" #include "nvim/assert.h" #include "nvim/buffer.h" @@ -28,7 +29,6 @@ #include "nvim/globals.h" #include "nvim/indent.h" #include "nvim/indent_c.h" -#include "nvim/lib/kvec.h" #include "nvim/log.h" #include "nvim/macros.h" #include "nvim/mark.h" diff --git a/src/nvim/os/pty_conpty_win.h b/src/nvim/os/pty_conpty_win.h index 15e7c3da0c..0c25a5970e 100644 --- a/src/nvim/os/pty_conpty_win.h +++ b/src/nvim/os/pty_conpty_win.h @@ -1,7 +1,7 @@ #ifndef NVIM_OS_PTY_CONPTY_WIN_H #define NVIM_OS_PTY_CONPTY_WIN_H -#include "nvim/lib/kvec.h" +#include "klib/kvec.h" #include "nvim/os/input.h" #ifndef HPCON diff --git a/src/nvim/os/pty_process_unix.c b/src/nvim/os/pty_process_unix.c index c5d6af0ff6..0b7af87267 100644 --- a/src/nvim/os/pty_process_unix.c +++ b/src/nvim/os/pty_process_unix.c @@ -31,11 +31,11 @@ #include +#include "klib/klist.h" #include "nvim/event/loop.h" #include "nvim/event/process.h" #include "nvim/event/rstream.h" #include "nvim/event/wstream.h" -#include "nvim/lib/klist.h" #include "nvim/log.h" #include "nvim/os/os.h" #include "nvim/os/pty_process_unix.h" diff --git a/src/nvim/os/shell.c b/src/nvim/os/shell.c index ca3e32e871..9766c8f3d9 100644 --- a/src/nvim/os/shell.c +++ b/src/nvim/os/shell.c @@ -7,6 +7,7 @@ #include #include +#include "klib/kvec.h" #include "nvim/ascii.h" #include "nvim/charset.h" #include "nvim/eval.h" @@ -15,7 +16,6 @@ #include "nvim/event/rstream.h" #include "nvim/ex_cmds.h" #include "nvim/fileio.h" -#include "nvim/lib/kvec.h" #include "nvim/log.h" #include "nvim/main.h" #include "nvim/memline.h" diff --git a/src/nvim/shada.c b/src/nvim/shada.c index f735829030..7580cc8897 100644 --- a/src/nvim/shada.c +++ b/src/nvim/shada.c @@ -11,6 +11,8 @@ #include #include +#include "klib/khash.h" +#include "klib/kvec.h" #include "nvim/api/private/defs.h" #include "nvim/api/private/helpers.h" #include "nvim/ascii.h" @@ -25,8 +27,6 @@ #include "nvim/fileio.h" #include "nvim/garray.h" #include "nvim/globals.h" -#include "nvim/lib/khash.h" -#include "nvim/lib/kvec.h" #include "nvim/macros.h" #include "nvim/mark.h" #include "nvim/memory.h" diff --git a/src/nvim/state.c b/src/nvim/state.c index 8b07c484e6..0353e61742 100644 --- a/src/nvim/state.c +++ b/src/nvim/state.c @@ -3,6 +3,7 @@ #include +#include "klib/kvec.h" #include "nvim/ascii.h" #include "nvim/autocmd.h" #include "nvim/drawscreen.h" @@ -10,7 +11,6 @@ #include "nvim/ex_docmd.h" #include "nvim/getchar.h" #include "nvim/insexpand.h" -#include "nvim/lib/kvec.h" #include "nvim/log.h" #include "nvim/main.h" #include "nvim/option.h" diff --git a/src/nvim/strings.h b/src/nvim/strings.h index 9ef1eb5816..6ad9daf5bf 100644 --- a/src/nvim/strings.h +++ b/src/nvim/strings.h @@ -5,8 +5,8 @@ #include #include +#include "klib/kvec.h" #include "nvim/eval/typval.h" -#include "nvim/lib/kvec.h" #include "nvim/types.h" /// Append string to string and return pointer to the next byte diff --git a/src/nvim/tui/tui.c b/src/nvim/tui/tui.c index 5a331463e3..4eabecb74a 100644 --- a/src/nvim/tui/tui.c +++ b/src/nvim/tui/tui.c @@ -13,13 +13,13 @@ # include #endif +#include "klib/kvec.h" #include "nvim/api/private/helpers.h" #include "nvim/api/vim.h" #include "nvim/ascii.h" #include "nvim/event/loop.h" #include "nvim/event/signal.h" #include "nvim/highlight.h" -#include "nvim/lib/kvec.h" #include "nvim/log.h" #include "nvim/main.h" #include "nvim/map.h" diff --git a/src/nvim/ui_compositor.c b/src/nvim/ui_compositor.c index f23615180e..8ef24b484e 100644 --- a/src/nvim/ui_compositor.c +++ b/src/nvim/ui_compositor.c @@ -11,12 +11,12 @@ #include #include +#include "klib/kvec.h" #include "nvim/api/private/helpers.h" #include "nvim/ascii.h" #include "nvim/grid.h" #include "nvim/highlight.h" #include "nvim/highlight_group.h" -#include "nvim/lib/kvec.h" #include "nvim/log.h" #include "nvim/lua/executor.h" #include "nvim/main.h" diff --git a/src/nvim/undo.c b/src/nvim/undo.c index 0a5a3133df..d67863f84f 100644 --- a/src/nvim/undo.c +++ b/src/nvim/undo.c @@ -81,6 +81,7 @@ #include #include "auto/config.h" +#include "klib/kvec.h" #include "nvim/ascii.h" #include "nvim/buffer.h" #include "nvim/buffer_updates.h" @@ -94,7 +95,6 @@ #include "nvim/fold.h" #include "nvim/garray.h" #include "nvim/getchar.h" -#include "nvim/lib/kvec.h" #include "nvim/mark.h" #include "nvim/memline.h" #include "nvim/memory.h" diff --git a/src/nvim/viml/parser/expressions.c b/src/nvim/viml/parser/expressions.c index d12a690b83..4564831824 100644 --- a/src/nvim/viml/parser/expressions.c +++ b/src/nvim/viml/parser/expressions.c @@ -55,11 +55,11 @@ #include #include +#include "klib/kvec.h" #include "nvim/ascii.h" #include "nvim/assert.h" #include "nvim/charset.h" #include "nvim/eval/typval.h" -#include "nvim/lib/kvec.h" #include "nvim/memory.h" #include "nvim/types.h" #include "nvim/vim.h" diff --git a/src/nvim/viml/parser/parser.h b/src/nvim/viml/parser/parser.h index 55f54cedbe..404dc5a0d1 100644 --- a/src/nvim/viml/parser/parser.h +++ b/src/nvim/viml/parser/parser.h @@ -5,8 +5,8 @@ #include #include +#include "klib/kvec.h" #include "nvim/func_attr.h" -#include "nvim/lib/kvec.h" #include "nvim/mbyte.h" #include "nvim/memory.h" -- cgit