aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/klib/khash.h733
-rw-r--r--src/nvim/CMakeLists.txt2
-rw-r--r--src/nvim/api/extmark.c8
-rw-r--r--src/nvim/api/extmark.h2
-rw-r--r--src/nvim/api/ui.c18
-rw-r--r--src/nvim/autocmd.c4
-rw-r--r--src/nvim/channel.c26
-rw-r--r--src/nvim/eval.c8
-rw-r--r--src/nvim/extmark.c2
-rw-r--r--src/nvim/highlight.c2
-rw-r--r--src/nvim/lua/treesitter.c6
-rw-r--r--src/nvim/map.c258
-rw-r--r--src/nvim/map.h177
-rw-r--r--src/nvim/map_key_impl.c.h159
-rw-r--r--src/nvim/map_value_impl.c.h64
-rw-r--r--src/nvim/marktree.c6
-rw-r--r--src/nvim/msgpack_rpc/channel.c2
-rw-r--r--src/nvim/os/env.c2
-rw-r--r--src/nvim/runtime.c8
-rw-r--r--src/nvim/shada.c22
-rw-r--r--src/nvim/tui/input.c11
-rw-r--r--src/nvim/ui.c8
-rw-r--r--test/client/session.lua6
-rw-r--r--test/functional/helpers.lua7
-rw-r--r--test/unit/helpers.lua1
25 files changed, 574 insertions, 968 deletions
diff --git a/src/klib/khash.h b/src/klib/khash.h
deleted file mode 100644
index eb1714c471..0000000000
--- a/src/klib/khash.h
+++ /dev/null
@@ -1,733 +0,0 @@
-/* The MIT License
-
- Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk>
-
- 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 <limits.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-
-#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
-
-// This is only used for stack temporaries. Heap allocation is done with precise sizes.
-#define KHASH_MAX_VAL_SIZE 32
-
-#define __KHASH_TYPE(name, khkey_t) \
- typedef struct { \
- khint_t n_buckets, size, n_occupied, upper_bound; \
- khint32_t *flags; \
- khkey_t *keys; \
- char *vals_buf; \
- } kh_##name##_t;
-
-#define __KHASH_PROTOTYPES(name, khkey_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, size_t val_size); \
- extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret, size_t val_size); \
- extern void kh_del_##name(kh_##name##_t *h, khint_t x);
-
-#define kh_bval(h, x) (&(h)->vals_buf[val_size*(x)])
-#define kh_copyval(to, from) memcpy(to, from, val_size)
-
-#define __KHASH_IMPL(name, SCOPE, khkey_t, __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_buf); \
- } \
- 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, size_t val_size) \
- REAL_FATTR_UNUSED; \
- SCOPE void kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets, size_t val_size) \
- { /* 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 (val_size) { \
- char *new_vals = krealloc( h->vals_buf, new_n_buckets * val_size); \
- h->vals_buf = new_vals; \
- } \
- } /* otherwise shrink */ \
- } \
- } \
- char cval[KHASH_MAX_VAL_SIZE]; \
- char ctmp[KHASH_MAX_VAL_SIZE]; \
- 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]; \
- khint_t new_mask; \
- new_mask = new_n_buckets - 1; \
- if (val_size) { \
- kh_copyval(cval, kh_bval(h, 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 (val_size) { \
- kh_copyval(ctmp, kh_bval(h, i)); \
- kh_copyval(kh_bval(h, i), cval); \
- kh_copyval(cval, ctmp); \
- } \
- /* 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 (val_size) { \
- kh_copyval(kh_bval(h, i), cval); \
- } \
- 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 (val_size) { \
- h->vals_buf = krealloc((void *)h->vals_buf, new_n_buckets * val_size); \
- } \
- } \
- 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, size_t val_size) \
- REAL_FATTR_UNUSED; \
- SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret, size_t val_size) \
- { \
- 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, val_size); /* clear "deleted" elements */ \
- } else { \
- kh_resize_##name(h, h->n_buckets + 1, val_size); /* 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(khkey_t) \
- __KHASH_TYPE(khkey_t, khkey_t) \
- __KHASH_PROTOTYPES(khkey_t, khkey_t)
-
-#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, __hash_func, __hash_equal) \
- __KHASH_TYPE(name, khkey_t, khval_t) \
- __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, __hash_func, __hash_equal)
-
-#define KHASH_INIT(name, khkey_t, khval_t, __hash_func, __hash_equal) \
- KHASH_INIT2(name, static kh_inline, khkey_t, khval_t, __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, vs) kh_put_##name(h, k, r, vs)
-
-/*! @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(type, h, x) (*(type *)(&(h)->vals_buf[(x)*(sizeof (type))]))
-
-/*! @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(type, 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(type, 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(type, 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(type, 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_buf = NULL, \
- })
-#endif // NVIM_LIB_KHASH_H
diff --git a/src/nvim/CMakeLists.txt b/src/nvim/CMakeLists.txt
index 535058bd7d..82a88c6774 100644
--- a/src/nvim/CMakeLists.txt
+++ b/src/nvim/CMakeLists.txt
@@ -90,7 +90,7 @@ if(MSVC)
target_compile_options(main_lib INTERFACE -W3)
# Disable warnings that give too many false positives.
- target_compile_options(main_lib INTERFACE -wd4311 -wd4146)
+ target_compile_options(main_lib INTERFACE -wd4311 -wd4146 -wd4003)
target_compile_definitions(main_lib INTERFACE _CRT_SECURE_NO_WARNINGS _CRT_NONSTDC_NO_DEPRECATE)
target_sources(main_lib INTERFACE ${CMAKE_CURRENT_LIST_DIR}/os/nvim.manifest)
diff --git a/src/nvim/api/extmark.c b/src/nvim/api/extmark.c
index 30e39cd7aa..6ec1fc4ee0 100644
--- a/src/nvim/api/extmark.c
+++ b/src/nvim/api/extmark.c
@@ -54,14 +54,14 @@ void api_extmark_free_all_mem(void)
Integer nvim_create_namespace(String name)
FUNC_API_SINCE(5)
{
- handle_T id = map_get(String, handle_T)(&namespace_ids, name);
+ handle_T id = map_get(String, int)(&namespace_ids, name);
if (id > 0) {
return id;
}
id = next_namespace_id++;
if (name.size > 0) {
String name_alloc = copy_string(name, NULL);
- map_put(String, handle_T)(&namespace_ids, name_alloc, id);
+ map_put(String, int)(&namespace_ids, name_alloc, id);
}
return (Integer)id;
}
@@ -76,7 +76,7 @@ Dictionary nvim_get_namespaces(void)
String name;
handle_T id;
- map_foreach(handle_T, &namespace_ids, name, id, {
+ map_foreach(&namespace_ids, name, id, {
PUT(retval, name.data, INTEGER_OBJ(id));
})
@@ -87,7 +87,7 @@ const char *describe_ns(NS ns_id)
{
String name;
handle_T id;
- map_foreach(handle_T, &namespace_ids, name, id, {
+ map_foreach(&namespace_ids, name, id, {
if ((NS)id == ns_id && name.size) {
return name.data;
}
diff --git a/src/nvim/api/extmark.h b/src/nvim/api/extmark.h
index 3c979fa4f6..a7baad496f 100644
--- a/src/nvim/api/extmark.h
+++ b/src/nvim/api/extmark.h
@@ -8,7 +8,7 @@
#include "nvim/map.h"
#include "nvim/types.h"
-EXTERN Map(String, handle_T) namespace_ids INIT(= MAP_INIT);
+EXTERN Map(String, int) namespace_ids INIT(= MAP_INIT);
EXTERN handle_T next_namespace_id INIT(= 1);
#ifdef INCLUDE_GENERATED_DECLARATIONS
diff --git a/src/nvim/api/ui.c b/src/nvim/api/ui.c
index 891c81d470..70c97be984 100644
--- a/src/nvim/api/ui.c
+++ b/src/nvim/api/ui.c
@@ -136,7 +136,7 @@ void remote_ui_wait_for_attach(void)
}
LOOP_PROCESS_EVENTS_UNTIL(&main_loop, channel->events, -1,
- pmap_has(uint64_t)(&connected_uis, CHAN_STDIO));
+ map_has(uint64_t, &connected_uis, CHAN_STDIO));
}
/// Activates UI events on the channel.
@@ -158,7 +158,7 @@ void nvim_ui_attach(uint64_t channel_id, Integer width, Integer height, Dictiona
Error *err)
FUNC_API_SINCE(1) FUNC_API_REMOTE_ONLY
{
- if (pmap_has(uint64_t)(&connected_uis, channel_id)) {
+ if (map_has(uint64_t, &connected_uis, channel_id)) {
api_set_error(err, kErrorTypeException,
"UI already attached to channel: %" PRId64, channel_id);
return;
@@ -233,7 +233,7 @@ void ui_attach(uint64_t channel_id, Integer width, Integer height, Boolean enabl
void nvim_ui_set_focus(uint64_t channel_id, Boolean gained, Error *error)
FUNC_API_SINCE(11) FUNC_API_REMOTE_ONLY
{
- if (!pmap_has(uint64_t)(&connected_uis, channel_id)) {
+ if (!map_has(uint64_t, &connected_uis, channel_id)) {
api_set_error(error, kErrorTypeException,
"UI not attached to channel: %" PRId64, channel_id);
return;
@@ -255,7 +255,7 @@ void nvim_ui_set_focus(uint64_t channel_id, Boolean gained, Error *error)
void nvim_ui_detach(uint64_t channel_id, Error *err)
FUNC_API_SINCE(1) FUNC_API_REMOTE_ONLY
{
- if (!pmap_has(uint64_t)(&connected_uis, channel_id)) {
+ if (!map_has(uint64_t, &connected_uis, channel_id)) {
api_set_error(err, kErrorTypeException,
"UI not attached to channel: %" PRId64, channel_id);
return;
@@ -271,7 +271,7 @@ void remote_ui_stop(UI *ui)
void nvim_ui_try_resize(uint64_t channel_id, Integer width, Integer height, Error *err)
FUNC_API_SINCE(1) FUNC_API_REMOTE_ONLY
{
- if (!pmap_has(uint64_t)(&connected_uis, channel_id)) {
+ if (!map_has(uint64_t, &connected_uis, channel_id)) {
api_set_error(err, kErrorTypeException,
"UI not attached to channel: %" PRId64, channel_id);
return;
@@ -292,7 +292,7 @@ void nvim_ui_try_resize(uint64_t channel_id, Integer width, Integer height, Erro
void nvim_ui_set_option(uint64_t channel_id, String name, Object value, Error *error)
FUNC_API_SINCE(1) FUNC_API_REMOTE_ONLY
{
- if (!pmap_has(uint64_t)(&connected_uis, channel_id)) {
+ if (!map_has(uint64_t, &connected_uis, channel_id)) {
api_set_error(error, kErrorTypeException,
"UI not attached to channel: %" PRId64, channel_id);
return;
@@ -426,7 +426,7 @@ void nvim_ui_try_resize_grid(uint64_t channel_id, Integer grid, Integer width, I
Error *err)
FUNC_API_SINCE(6) FUNC_API_REMOTE_ONLY
{
- if (!pmap_has(uint64_t)(&connected_uis, channel_id)) {
+ if (!map_has(uint64_t, &connected_uis, channel_id)) {
api_set_error(err, kErrorTypeException,
"UI not attached to channel: %" PRId64, channel_id);
return;
@@ -448,7 +448,7 @@ void nvim_ui_try_resize_grid(uint64_t channel_id, Integer grid, Integer width, I
void nvim_ui_pum_set_height(uint64_t channel_id, Integer height, Error *err)
FUNC_API_SINCE(6) FUNC_API_REMOTE_ONLY
{
- if (!pmap_has(uint64_t)(&connected_uis, channel_id)) {
+ if (!map_has(uint64_t, &connected_uis, channel_id)) {
api_set_error(err, kErrorTypeException,
"UI not attached to channel: %" PRId64, channel_id);
return;
@@ -489,7 +489,7 @@ void nvim_ui_pum_set_bounds(uint64_t channel_id, Float width, Float height, Floa
Error *err)
FUNC_API_SINCE(7) FUNC_API_REMOTE_ONLY
{
- if (!pmap_has(uint64_t)(&connected_uis, channel_id)) {
+ if (!map_has(uint64_t, &connected_uis, channel_id)) {
api_set_error(err, kErrorTypeException,
"UI not attached to channel: %" PRId64, channel_id);
return;
diff --git a/src/nvim/autocmd.c b/src/nvim/autocmd.c
index c43a59cbb3..5f94fbb014 100644
--- a/src/nvim/autocmd.c
+++ b/src/nvim/autocmd.c
@@ -543,7 +543,7 @@ void do_augroup(char *arg, int del_group)
String name;
int value;
- map_foreach(int, &map_augroup_name_to_id, name, value, {
+ map_foreach(&map_augroup_name_to_id, name, value, {
if (value > 0) {
msg_puts(name.data);
} else {
@@ -577,7 +577,7 @@ void free_all_autocmds(void)
})
map_destroy(String, &map_augroup_name_to_id);
- map_foreach_value(String, &map_augroup_id_to_name, name, {
+ map_foreach_value(&map_augroup_id_to_name, name, {
api_free_string(name);
})
map_destroy(int, &map_augroup_id_to_name);
diff --git a/src/nvim/channel.c b/src/nvim/channel.c
index f9ce62dbd2..165e5e0cac 100644
--- a/src/nvim/channel.c
+++ b/src/nvim/channel.c
@@ -57,7 +57,7 @@ void channel_teardown(void)
{
Channel *channel;
- pmap_foreach_value(&channels, channel, {
+ map_foreach_value(&channels, channel, {
channel_close(channel->id, kChannelPartAll, NULL);
});
}
@@ -937,12 +937,28 @@ Dictionary channel_info(uint64_t id)
return info;
}
+/// Simple int64_t comparison function for use with qsort()
+static int int64_t_cmp(const void *a, const void *b)
+{
+ int64_t diff = *(int64_t *)a - *(int64_t *)b;
+ return (diff < 0) ? -1 : (diff > 0);
+}
+
Array channel_all_info(void)
{
- Channel *channel;
- Array ret = ARRAY_DICT_INIT;
- pmap_foreach_value(&channels, channel, {
- ADD(ret, DICTIONARY_OBJ(channel_info(channel->id)));
+ // order the items in the array by channel number, for Determinism™
+ kvec_t(int64_t) ids = KV_INITIAL_VALUE;
+ kv_resize(ids, map_size(&channels));
+ uint64_t id;
+ map_foreach_key(&channels, id, {
+ kv_push(ids, (int64_t)id);
});
+ qsort(ids.items, ids.size, sizeof ids.items[0], int64_t_cmp);
+
+ Array ret = ARRAY_DICT_INIT;
+ for (size_t i = 0; i < ids.size; i++) {
+ ADD(ret, DICTIONARY_OBJ(channel_info((uint64_t)ids.items[i])));
+ }
+ kv_destroy(ids);
return ret;
}
diff --git a/src/nvim/eval.c b/src/nvim/eval.c
index e7a28cfe67..9be4cea059 100644
--- a/src/nvim/eval.c
+++ b/src/nvim/eval.c
@@ -4470,7 +4470,7 @@ bool garbage_collect(bool testing)
// Channels
{
Channel *data;
- pmap_foreach_value(&channels, data, {
+ map_foreach_value(&channels, data, {
set_ref_in_callback_reader(&data->on_data, copyID, NULL, NULL);
set_ref_in_callback_reader(&data->on_stderr, copyID, NULL, NULL);
set_ref_in_callback(&data->on_exit, copyID, NULL, NULL);
@@ -4480,7 +4480,7 @@ bool garbage_collect(bool testing)
// Timers
{
timer_T *timer;
- pmap_foreach_value(&timers, timer, {
+ map_foreach_value(&timers, timer, {
set_ref_in_callback(&timer->callback, copyID, NULL, NULL);
})
}
@@ -6123,7 +6123,7 @@ void add_timer_info_all(typval_T *rettv)
{
tv_list_alloc_ret(rettv, map_size(&timers));
timer_T *timer;
- pmap_foreach_value(&timers, timer, {
+ map_foreach_value(&timers, timer, {
if (!timer->stopped || timer->refcount > 1) {
add_timer_info(rettv, timer);
}
@@ -6235,7 +6235,7 @@ static void timer_decref(timer_T *timer)
void timer_stop_all(void)
{
timer_T *timer;
- pmap_foreach_value(&timers, timer, {
+ map_foreach_value(&timers, timer, {
timer_stop(timer);
})
}
diff --git a/src/nvim/extmark.c b/src/nvim/extmark.c
index f4a6a02682..77e41cb5cf 100644
--- a/src/nvim/extmark.c
+++ b/src/nvim/extmark.c
@@ -291,7 +291,7 @@ bool extmark_clear(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_col, int u_r
}
uint64_t id;
ssize_t decor_id;
- map_foreach(ssize_t, &delete_set, id, decor_id, {
+ map_foreach(&delete_set, id, decor_id, {
mtkey_t mark = marktree_lookup(buf->b_marktree, id, itr);
assert(marktree_itr_valid(itr));
marktree_del_itr(buf->b_marktree, itr, false);
diff --git a/src/nvim/highlight.c b/src/nvim/highlight.c
index 3755b7ae05..29e5db7a96 100644
--- a/src/nvim/highlight.c
+++ b/src/nvim/highlight.c
@@ -167,7 +167,7 @@ void ns_hl_def(NS ns_id, int hl_id, HlAttrs attrs, int link_id, Dict(highlight)
return;
}
if ((attrs.rgb_ae_attr & HL_DEFAULT)
- && map_has(ColorKey, ColorItem)(&ns_hls, ColorKey(ns_id, hl_id))) {
+ && map_has(ColorKey, &ns_hls, (ColorKey(ns_id, hl_id)))) {
return;
}
DecorProvider *p = get_decor_provider(ns_id, true);
diff --git a/src/nvim/lua/treesitter.c b/src/nvim/lua/treesitter.c
index 45fe7f6129..d255dd56e5 100644
--- a/src/nvim/lua/treesitter.c
+++ b/src/nvim/lua/treesitter.c
@@ -173,7 +173,7 @@ void tslua_init(lua_State *L)
int tslua_has_language(lua_State *L)
{
const char *lang_name = luaL_checkstring(L, 1);
- lua_pushboolean(L, pmap_has(cstr_t)(&langs, lang_name));
+ lua_pushboolean(L, map_has(cstr_t, &langs, lang_name));
return 1;
}
@@ -190,7 +190,7 @@ int tslua_add_language(lua_State *L)
symbol_name = luaL_checkstring(L, 3);
}
- if (pmap_has(cstr_t)(&langs, lang_name)) {
+ if (map_has(cstr_t, &langs, lang_name)) {
lua_pushboolean(L, true);
return 1;
}
@@ -243,7 +243,7 @@ int tslua_add_language(lua_State *L)
int tslua_remove_lang(lua_State *L)
{
const char *lang_name = luaL_checkstring(L, 1);
- bool present = pmap_has(cstr_t)(&langs, lang_name);
+ bool present = map_has(cstr_t, &langs, lang_name);
if (present) {
cstr_t key;
pmap_del(cstr_t)(&langs, lang_name, &key);
diff --git a/src/nvim/map.c b/src/nvim/map.c
index 4c8506f468..e2c6443245 100644
--- a/src/nvim/map.c
+++ b/src/nvim/map.c
@@ -1,122 +1,62 @@
// 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
+// map.c: Hash maps and sets
//
-// map.c: khash.h wrapper
+// parts of the implementation derived from khash.h as part of klib (MIT license)
//
// NOTE: Callers must manage memory (allocate) for keys and values.
-// khash.h does not make its own copy of the key or value.
-//
+// Map and Set does not make its own copy of the key or value.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "auto/config.h"
-#include "klib/khash.h"
#include "nvim/gettext.h"
#include "nvim/map.h"
#include "nvim/memory.h"
-#define cstr_t_hash kh_str_hash_func
-#define cstr_t_eq kh_str_hash_equal
-#define uint64_t_hash kh_int64_hash_func
-#define uint64_t_eq kh_int64_hash_equal
-#define uint32_t_hash kh_int_hash_func
-#define uint32_t_eq kh_int_hash_equal
-#define int_hash kh_int_hash_func
-#define int_eq kh_int_hash_equal
-#define handle_T_hash kh_int_hash_func
-#define handle_T_eq kh_int_hash_equal
+#define equal_simple(x, y) ((x) == (y))
+
+#define hash_uint64_t(key) (uint32_t)((key) >> 33^(key)^(key) << 11)
+#define equal_uint64_t equal_simple
+#define hash_uint32_t(x) (x)
+#define equal_uint32_t equal_simple
+#define hash_int(x) hash_uint32_t((uint32_t)(x))
+#define equal_int equal_simple
#if defined(ARCH_64)
-# define ptr_t_hash(key) uint64_t_hash((uint64_t)(key))
-# define ptr_t_eq(a, b) uint64_t_eq((uint64_t)(a), (uint64_t)(b))
+# define hash_ptr_t(key) hash_uint64_t((uint64_t)(key))
+# define equal_ptr_t(a, b) equal_uint64_t((uint64_t)(a), (uint64_t)(b))
#elif defined(ARCH_32)
-# define ptr_t_hash(key) uint32_t_hash((uint32_t)(key))
-# define ptr_t_eq(a, b) uint32_t_eq((uint32_t)(a), (uint32_t)(b))
+# define hash_ptr_t(key) hash_uint32_t((uint32_t)(key))
+# define equal_ptr_t(a, b) equal_uint32_t((uint32_t)(a), (uint32_t)(b))
#endif
-#define INITIALIZER(T, U) T##_##U##_initializer
-#define INITIALIZER_DECLARE(T, U, ...) const U INITIALIZER(T, U) = __VA_ARGS__
-#define DEFAULT_INITIALIZER { 0 }
-#define SSIZE_INITIALIZER { -1 }
-
-#define KEY_IMPL(T) \
- __KHASH_IMPL(T, , T, T##_hash, T##_eq) \
-
-#define MAP_IMPL(T, U, ...) \
- INITIALIZER_DECLARE(T, U, __VA_ARGS__); \
- U map_##T##_##U##_get(Map(T, U) *map, T key) \
- { \
- khiter_t k; \
- if ((k = kh_get(T, &map->table, key)) == kh_end(&map->table)) { \
- return INITIALIZER(T, U); \
- } \
- return kh_val(U, &map->table, k); \
- } \
- U map_##T##_##U##_put(Map(T, U) *map, T key, U value) \
- { \
- STATIC_ASSERT(sizeof(U) <= KHASH_MAX_VAL_SIZE, "increase KHASH_MAX_VAL_SIZE"); \
- int ret; \
- U rv = INITIALIZER(T, U); \
- khiter_t k = kh_put(T, &map->table, key, &ret, sizeof(U)); \
- if (!ret) { \
- rv = kh_val(U, &map->table, k); \
- } \
- kh_val(U, &map->table, k) = value; \
- return rv; \
- } \
- U *map_##T##_##U##_ref(Map(T, U) *map, T key, T **key_alloc) \
- { \
- khiter_t k = kh_get(T, &map->table, key); \
- if (k == kh_end(&map->table)) { \
- return NULL; \
- } \
- if (key_alloc) { \
- *key_alloc = &kh_key(&map->table, k); \
- } \
- return &kh_val(U, &map->table, k); \
- } \
- U *map_##T##_##U##_put_ref(Map(T, U) *map, T key, T **key_alloc, bool *new_item) \
- { \
- int ret; \
- khiter_t k = kh_put(T, &map->table, key, &ret, sizeof(U)); \
- if (ret) { \
- kh_val(U, &map->table, k) = INITIALIZER(T, U); \
- } \
- if (new_item) { \
- *new_item = (bool)ret; \
- } \
- if (key_alloc) { \
- *key_alloc = &kh_key(&map->table, k); \
- } \
- return &kh_val(U, &map->table, k); \
- } \
- U map_##T##_##U##_del(Map(T, U) *map, T key, T *key_alloc) \
- { \
- U rv = INITIALIZER(T, U); \
- khiter_t k; \
- if ((k = kh_get(T, &map->table, key)) != kh_end(&map->table)) { \
- rv = kh_val(U, &map->table, k); \
- if (key_alloc) { \
- *key_alloc = kh_key(&map->table, k); \
- } \
- kh_del(T, &map->table, k); \
- } \
- return rv; \
+static inline uint32_t hash_cstr_t(const char *s)
+{
+ uint32_t h = 0;
+ for (size_t i = 0; s[i]; i++) {
+ h = (h << 5) - h + (uint8_t)s[i];
}
+ return h;
+}
+
+#define equal_cstr_t strequal
-static inline khint_t String_hash(String s)
+// when used as a key, String doesn't need to be NUL terminated,
+// and can also contain embedded NUL:s as part of the data.
+static inline uint32_t hash_String(String s)
{
- khint_t h = 0;
- for (size_t i = 0; i < s.size && s.data[i]; i++) {
+ uint32_t h = 0;
+ for (size_t i = 0; i < s.size; i++) {
h = (h << 5) - h + (uint8_t)s.data[i];
}
return h;
}
-static inline bool String_eq(String a, String b)
+static inline bool equal_String(String a, String b)
{
if (a.size != b.size) {
return false;
@@ -124,61 +64,137 @@ static inline bool String_eq(String a, String b)
return memcmp(a.data, b.data, a.size) == 0;
}
-static inline khint_t HlEntry_hash(HlEntry ae)
+static inline uint32_t hash_HlEntry(HlEntry ae)
{
const uint8_t *data = (const uint8_t *)&ae;
- khint_t h = 0;
+ uint32_t h = 0;
for (size_t i = 0; i < sizeof(ae); i++) {
h = (h << 5) - h + data[i];
}
return h;
}
-static inline bool HlEntry_eq(HlEntry ae1, HlEntry ae2)
+static inline bool equal_HlEntry(HlEntry ae1, HlEntry ae2)
{
return memcmp(&ae1, &ae2, sizeof(ae1)) == 0;
}
-static inline khint_t ColorKey_hash(ColorKey ae)
+static inline uint32_t hash_ColorKey(ColorKey ae)
{
const uint8_t *data = (const uint8_t *)&ae;
- khint_t h = 0;
+ uint32_t h = 0;
for (size_t i = 0; i < sizeof(ae); i++) {
h = (h << 5) - h + data[i];
}
return h;
}
-static inline bool ColorKey_eq(ColorKey ae1, ColorKey ae2)
+static inline bool equal_ColorKey(ColorKey ae1, ColorKey ae2)
{
return memcmp(&ae1, &ae2, sizeof(ae1)) == 0;
}
-KEY_IMPL(int)
-KEY_IMPL(cstr_t)
-KEY_IMPL(ptr_t)
-KEY_IMPL(uint64_t)
-KEY_IMPL(uint32_t)
-KEY_IMPL(String)
-KEY_IMPL(HlEntry)
-KEY_IMPL(ColorKey)
-
-MAP_IMPL(int, int, DEFAULT_INITIALIZER)
-MAP_IMPL(int, ptr_t, DEFAULT_INITIALIZER)
-MAP_IMPL(int, cstr_t, DEFAULT_INITIALIZER)
-MAP_IMPL(cstr_t, ptr_t, DEFAULT_INITIALIZER)
-MAP_IMPL(cstr_t, int, DEFAULT_INITIALIZER)
-MAP_IMPL(ptr_t, ptr_t, DEFAULT_INITIALIZER)
-MAP_IMPL(uint32_t, ptr_t, DEFAULT_INITIALIZER)
-MAP_IMPL(uint64_t, ptr_t, DEFAULT_INITIALIZER)
-MAP_IMPL(uint64_t, ssize_t, SSIZE_INITIALIZER)
-MAP_IMPL(uint64_t, uint64_t, DEFAULT_INITIALIZER)
-MAP_IMPL(uint32_t, uint32_t, DEFAULT_INITIALIZER)
-MAP_IMPL(HlEntry, int, DEFAULT_INITIALIZER)
-MAP_IMPL(String, handle_T, 0)
-MAP_IMPL(String, int, DEFAULT_INITIALIZER)
-MAP_IMPL(int, String, DEFAULT_INITIALIZER)
-MAP_IMPL(ColorKey, ColorItem, COLOR_ITEM_INITIALIZER)
+// TODO(bfredl): this could be _less_ for the h->hash part as this is now small (4 bytes per value)
+#define UPPER_FILL 0.77
+
+#define roundup32(x) (--(x), (x)|= (x)>>1, (x)|= (x)>>2, (x)|= (x)>>4, (x)|= (x)>>8, \
+ (x)|= (x)>>16, ++(x))
+
+// h->hash must either be NULL or an already valid pointer
+void mh_realloc(MapHash *h, uint32_t n_min_buckets)
+{
+ xfree(h->hash);
+ uint32_t n_buckets = n_min_buckets < 16 ? 16 : n_min_buckets;
+ roundup32(n_buckets);
+ // sets all buckets to EMPTY
+ h->hash = xcalloc(n_buckets, sizeof *h->hash);
+ h->n_occupied = h->size = 0;
+ h->n_buckets = n_buckets;
+ h->upper_bound = (uint32_t)(h->n_buckets * UPPER_FILL + 0.5);
+}
+
+void mh_clear(MapHash *h)
+{
+ if (h->hash) {
+ memset(h->hash, 0, h->n_buckets * sizeof(*h->hash));
+ h->size = h->n_occupied = 0;
+ h->n_keys = 0;
+ }
+}
+
+#define KEY_NAME(x) x##int
+#include "nvim/map_key_impl.c.h"
+#define VAL_NAME(x) quasiquote(x, int)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#define VAL_NAME(x) quasiquote(x, ptr_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#define VAL_NAME(x) quasiquote(x, String)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#undef KEY_NAME
+
+#define KEY_NAME(x) x##ptr_t
+#include "nvim/map_key_impl.c.h"
+#define VAL_NAME(x) quasiquote(x, ptr_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#undef KEY_NAME
+
+#define KEY_NAME(x) x##cstr_t
+#include "nvim/map_key_impl.c.h"
+#define VAL_NAME(x) quasiquote(x, ptr_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#define VAL_NAME(x) quasiquote(x, int)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#undef KEY_NAME
+
+#define KEY_NAME(x) x##String
+#include "nvim/map_key_impl.c.h"
+#define VAL_NAME(x) quasiquote(x, int)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#undef KEY_NAME
+
+#define KEY_NAME(x) x##uint32_t
+#include "nvim/map_key_impl.c.h"
+#define VAL_NAME(x) quasiquote(x, ptr_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#define VAL_NAME(x) quasiquote(x, uint32_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#undef KEY_NAME
+
+#define KEY_NAME(x) x##uint64_t
+#include "nvim/map_key_impl.c.h"
+#define VAL_NAME(x) quasiquote(x, ptr_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#define VAL_NAME(x) quasiquote(x, ssize_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#define VAL_NAME(x) quasiquote(x, uint64_t)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#undef KEY_NAME
+
+#define KEY_NAME(x) x##HlEntry
+#include "nvim/map_key_impl.c.h"
+#define VAL_NAME(x) quasiquote(x, int)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#undef KEY_NAME
+
+#define KEY_NAME(x) x##ColorKey
+#include "nvim/map_key_impl.c.h"
+#define VAL_NAME(x) quasiquote(x, ColorItem)
+#include "nvim/map_value_impl.c.h"
+#undef VAL_NAME
+#undef KEY_NAME
/// Deletes a key:value pair from a string:pointer map, and frees the
/// storage of both key and value.
diff --git a/src/nvim/map.h b/src/nvim/map.h
index cc32a20740..a84d533262 100644
--- a/src/nvim/map.h
+++ b/src/nvim/map.h
@@ -5,7 +5,6 @@
#include <stdint.h>
#include <stdio.h>
-#include "klib/khash.h"
#include "nvim/api/private/defs.h"
#include "nvim/assert.h"
#include "nvim/highlight_defs.h"
@@ -19,47 +18,106 @@
typedef const char *cstr_t;
typedef void *ptr_t;
-#define Map(T, U) Map_##T##_##U
+#define Set(type) Set_##type
+#define Map(T, U) Map_##T##U
#define PMap(T) Map(T, ptr_t)
+static const int value_init_int = 0;
+static const ptr_t value_init_ptr_t = NULL;
+static const ssize_t value_init_ssize_t = -1;
+static const uint32_t value_init_uint32_t = 0;
+static const uint64_t value_init_uint64_t = 0;
+static const String value_init_String = STRING_INIT;
+static const ColorItem value_init_ColorItem = COLOR_ITEM_INITIALIZER;
+
+// layer 0: type non-specific code
+
+typedef struct {
+ uint32_t n_buckets;
+ uint32_t size;
+ uint32_t n_occupied;
+ uint32_t upper_bound;
+ uint32_t n_keys; // this is almost always "size", but keys[] could contain ded items..
+ uint32_t keys_capacity;
+ uint32_t *hash;
+} MapHash;
+
+#define MAPHASH_INIT { 0, 0, 0, 0, 0, 0, NULL }
+#define SET_INIT { MAPHASH_INIT, NULL }
+#define MAP_INIT { SET_INIT, NULL }
+
+#define MH_TOMBSTONE UINT32_MAX
+
+#define mh_is_empty(h, i) ((h)->hash[i] == 0)
+#define mh_is_del(h, i) ((h)->hash[i] == MH_TOMBSTONE)
+#define mh_is_either(h, i) ((uint32_t)((h)->hash[i] + 1U) <= 1U)
+
+typedef enum {
+ kMHExisting = 0,
+ kMHNewKeyDidFit,
+ kMHNewKeyRealloc,
+} MhPutStatus;
+
+void mh_clear(MapHash *h);
+void mh_realloc(MapHash *h, uint32_t n_min_buckets);
+
+// layer 1: key type specific defs
+// This is all need for sets.
+
#define KEY_DECLS(T) \
- KHASH_DECLARE(T) \
+ typedef struct { \
+ MapHash h; \
+ T *keys; \
+ } Set(T); \
+ \
+ uint32_t mh_find_bucket_##T(Set(T) *set, T key, bool put); \
+ uint32_t mh_get_##T(Set(T) *set, T key); \
+ void mh_rehash_##T(Set(T) *set); \
+ uint32_t mh_put_##T(Set(T) *set, T key, MhPutStatus *new); \
+ uint32_t mh_delete_##T(Set(T) *set, T *key); \
+ \
static inline bool set_put_##T(Set(T) *set, T key, T **key_alloc) { \
- int kh_ret; \
- khiter_t k = kh_put(T, set, key, &kh_ret, 0); \
+ MhPutStatus status; \
+ uint32_t k = mh_put_##T(set, key, &status); \
if (key_alloc) { \
- *key_alloc = &kh_key(set, k); \
+ *key_alloc = &set->keys[k]; \
} \
- return kh_ret; \
+ return status != kMHExisting; \
} \
- static inline void set_del_##T(Set(T) *set, T key) \
+ static inline T set_del_##T(Set(T) *set, T key) \
{ \
- khiter_t k; \
- if ((k = kh_get(T, set, key)) != kh_end(set)) { \
- kh_del(T, set, k); \
- } \
+ mh_delete_##T(set, &key); \
+ return key; \
} \
static inline bool set_has_##T(Set(T) *set, T key) { \
- return (kh_get(T, set, key) != kh_end(set)); \
+ return mh_get_##T(set, key) != MH_TOMBSTONE; \
} \
+// layer 2: key+value specific defs
+// now we finally get Maps
+
#define MAP_DECLS(T, U) \
typedef struct { \
- khash_t(T) table; \
+ Set(T) set; \
+ U *values; \
} Map(T, U); \
- U map_##T##_##U##_get(Map(T, U) *map, T key); \
- static inline bool map_##T##_##U##_has(Map(T, U) *map, T key) \
+ static inline U map_get_##T##U(Map(T, U) *map, T key) \
{ \
- return kh_get(T, &map->table, key) != kh_end(&map->table); \
+ uint32_t k = mh_get_##T(&map->set, key); \
+ return k == MH_TOMBSTONE ? value_init_##U : map->values[k]; \
} \
- U map_##T##_##U##_put(Map(T, U) *map, T key, U value); \
- U *map_##T##_##U##_ref(Map(T, U) *map, T key, T **key_alloc); \
- U *map_##T##_##U##_put_ref(Map(T, U) *map, T key, T **key_alloc, bool *new_item); \
- U map_##T##_##U##_del(Map(T, U) *map, T key, T *key_alloc); \
+ U *map_ref_##T##U(Map(T, U) *map, T key, T **key_alloc); \
+ U *map_put_ref_##T##U(Map(T, U) *map, T key, T **key_alloc, bool *new_item); \
+ static inline void map_put_##T##U(Map(T, U) *map, T key, U value) \
+ { \
+ U *val = map_put_ref_##T##U(map, key, NULL, NULL); \
+ *val = value; \
+ } \
+ U map_del_##T##U(Map(T, U) *map, T key, T *key_alloc); \
-// NOTE: Keys AND values must be allocated! khash.h does not make a copy.
+// NOTE: Keys AND values must be allocated! Map and Set does not make a copy.
-#define Set(type) khash_t(type)
+#define quasiquote(x, y) x##y
KEY_DECLS(int)
KEY_DECLS(cstr_t)
@@ -72,7 +130,6 @@ KEY_DECLS(ColorKey)
MAP_DECLS(int, int)
MAP_DECLS(int, ptr_t)
-MAP_DECLS(int, cstr_t)
MAP_DECLS(cstr_t, ptr_t)
MAP_DECLS(cstr_t, int)
MAP_DECLS(ptr_t, ptr_t)
@@ -82,49 +139,65 @@ MAP_DECLS(uint64_t, ssize_t)
MAP_DECLS(uint64_t, uint64_t)
MAP_DECLS(uint32_t, uint32_t)
MAP_DECLS(HlEntry, int)
-MAP_DECLS(String, handle_T)
MAP_DECLS(String, int)
MAP_DECLS(int, String)
MAP_DECLS(ColorKey, ColorItem)
-#define SET_INIT { 0, 0, 0, 0, NULL, NULL, NULL }
-#define MAP_INIT { SET_INIT }
-
-#define map_get(T, U) map_##T##_##U##_get
-#define map_has(T, U) map_##T##_##U##_has
-#define map_put(T, U) map_##T##_##U##_put
-#define map_ref(T, U) map_##T##_##U##_ref
-#define map_put_ref(T, U) map_##T##_##U##_put_ref
-#define map_del(T, U) map_##T##_##U##_del
-#define map_destroy(T, map) kh_dealloc(T, &(map)->table)
-#define map_clear(T, map) kh_clear(T, &(map)->table)
-
-#define map_size(map) ((map)->table.size)
+#define set_has(T, set, key) set_has_##T(set, key)
+#define set_put(T, set, key) set_put_##T(set, key, NULL)
+#define set_put_ref(T, set, key, key_alloc) set_put_##T(set, key, key_alloc)
+#define set_del(T, set, key) set_del_##T(set, key)
+#define set_destroy(T, set) (xfree((set)->keys), xfree((set)->h.hash))
+#define set_clear(T, set) mh_clear(&(set)->h)
+#define set_size(set) ((set)->h.size)
+
+#define map_get(T, U) map_get_##T##U
+#define map_has(T, map, key) set_has(T, &(map)->set, key)
+#define map_put(T, U) map_put_##T##U
+#define map_ref(T, U) map_ref_##T##U
+#define map_put_ref(T, U) map_put_ref_##T##U
+#define map_del(T, U) map_del_##T##U
+#define map_destroy(T, map) (set_destroy(T, &(map)->set), xfree((map)->values))
+#define map_clear(T, map) set_clear(T, &(map)->set)
+#define map_size(map) set_size(&(map)->set)
#define pmap_get(T) map_get(T, ptr_t)
-#define pmap_has(T) map_has(T, ptr_t)
#define pmap_put(T) map_put(T, ptr_t)
#define pmap_ref(T) map_ref(T, ptr_t)
#define pmap_put_ref(T) map_put_ref(T, ptr_t)
/// @see pmap_del2
#define pmap_del(T) map_del(T, ptr_t)
-#define map_foreach(U, map, key, value, block) kh_foreach(U, &(map)->table, key, value, block)
+#define set_foreach(set, key, block) \
+ { \
+ uint32_t __i; \
+ for (__i = 0; __i < (set)->h.n_keys; __i++) { \
+ (key) = (set)->keys[__i]; \
+ block; \
+ } \
+ }
-#define map_foreach_value(U, map, value, block) kh_foreach_value(U, &(map)->table, value, block)
-#define map_foreach_key(map, key, block) kh_foreach_key(&(map)->table, key, block)
-#define set_foreach(set, key, block) kh_foreach_key(set, key, block)
+#define map_foreach_key(map, key, block) set_foreach(&(map)->set, key, block)
+
+#define map_foreach(map, key, value, code) \
+ { \
+ uint32_t __i; \
+ for (__i = 0; __i < (map)->set.h.n_keys; __i++) { \
+ (key) = (map)->set.keys[__i]; \
+ (value) = (map)->values[__i]; \
+ code; \
+ } \
+ }
-#define pmap_foreach_value(map, value, block) map_foreach_value(ptr_t, map, value, block)
-#define pmap_foreach(map, key, value, block) map_foreach(ptr_t, map, key, value, block)
+#define map_foreach_value(map, value, code) \
+ { \
+ uint32_t __i; \
+ for (__i = 0; __i < (map)->set.h.n_keys; __i++) { \
+ (value) = (map)->values[__i]; \
+ code; \
+ } \
+ }
void pmap_del2(PMap(cstr_t) *map, const char *key);
-#define set_has(T, set, key) set_has_##T(set, key)
-#define set_put(T, set, key) set_put_##T(set, key, NULL)
-#define set_put_ref(T, set, key, key_alloc) set_put_##T(set, key, key_alloc)
-#define set_del(T, set, key) set_del_##T(set, key)
-#define set_destroy(T, set) kh_dealloc(T, set)
-#define set_clear(T, set) kh_clear(T, set)
-
#endif // NVIM_MAP_H
diff --git a/src/nvim/map_key_impl.c.h b/src/nvim/map_key_impl.c.h
new file mode 100644
index 0000000000..7e7b2f74fe
--- /dev/null
+++ b/src/nvim/map_key_impl.c.h
@@ -0,0 +1,159 @@
+#include "nvim/map.h"
+#include "nvim/memory.h"
+
+#ifndef KEY_NAME
+// Don't error out. it is nice to type-check the file in isolation, in clangd or otherwise
+# define KEY_NAME(x) x##int
+# define hash_int(x) ((uint32_t)x)
+# define equal_int(x, y) ((x) == (y))
+#endif
+
+#define SET_TYPE KEY_NAME(Set_)
+#define KEY_TYPE KEY_NAME()
+
+/// find bucket to get or put "key"
+///
+/// set->h.hash assumed already allocated!
+///
+/// @return bucket index, or MH_TOMBSTONE if not found and `put` was false
+/// mh_is_either(hash[rv]) : not found, but this is the place to put
+/// otherwise: hash[rv]-1 is index into key/value arrays
+uint32_t KEY_NAME(mh_find_bucket_)(SET_TYPE *set, KEY_TYPE key, bool put)
+{
+ MapHash *h = &set->h;
+ uint32_t step = 0;
+ uint32_t mask = h->n_buckets - 1;
+ uint32_t k = KEY_NAME(hash_)(key);
+ uint32_t i = k & mask;
+ uint32_t last = i;
+ uint32_t site = put ? last : MH_TOMBSTONE;
+ while (!mh_is_empty(h, i)) {
+ if (mh_is_del(h, i)) {
+ if (site == last) {
+ site = i;
+ }
+ } else if (KEY_NAME(equal_)(set->keys[h->hash[i] - 1], key)) {
+ return i;
+ }
+ i = (i + (++step)) & mask;
+ if (i == last) {
+ abort();
+ }
+ }
+ if (site == last) {
+ site = i;
+ }
+ return site;
+}
+
+/// @return index into set->keys if found, MH_TOMBSTONE otherwise
+uint32_t KEY_NAME(mh_get_)(SET_TYPE *set, KEY_TYPE key)
+{
+ if (set->h.n_buckets == 0) {
+ return MH_TOMBSTONE;
+ }
+ uint32_t idx = KEY_NAME(mh_find_bucket_)(set, key, false);
+ return (idx != MH_TOMBSTONE) ? set->h.hash[idx] - 1 : MH_TOMBSTONE;
+}
+
+/// Rebuild hash from keys[] array
+///
+/// set->h.hash must be allocated and empty before&alling!
+void KEY_NAME(mh_rehash_)(SET_TYPE *set)
+{
+ for (uint32_t k = 0; k < set->h.n_keys; k++) {
+ uint32_t idx = KEY_NAME(mh_find_bucket_)(set, set->keys[k], true);
+ // there must be tombstones when we do a rehash
+ if (!mh_is_empty((&set->h), idx)) {
+ abort();
+ }
+ set->h.hash[idx] = k + 1;
+ }
+ set->h.n_occupied = set->h.size = set->h.n_keys;
+}
+
+/// Put a key. Return the existing item if found
+///
+/// Allocates/resizes the hash table and/or keys[] table if needed.
+///
+/// @param[out] new mandatory. Reveals if an existing key was found. In addition,
+/// if new item, indicates if keys[] was resized.
+///
+/// @return keys index
+uint32_t KEY_NAME(mh_put_)(SET_TYPE *set, KEY_TYPE key, MhPutStatus *new)
+{
+ MapHash *h = &set->h;
+ // Might rehash ahead of time if "key" already existed. But it was
+ // going to happen soon anyway.
+ if (h->n_occupied >= h->upper_bound) {
+ // If we likely were to resize soon, do it now to avoid extra rehash
+ // TODO(bfredl): we never shrink. but maybe that's fine
+ if (h->size >= h->upper_bound * 0.9) {
+ mh_realloc(h, h->n_buckets + 1);
+ } else {
+ // Just a lot of tombstones from deleted items, start all over again
+ memset(h->hash, 0, h->n_buckets * sizeof(*h->hash));
+ h->size = h->n_occupied = 0;
+ }
+ KEY_NAME(mh_rehash_)(set);
+ }
+
+ uint32_t idx = KEY_NAME(mh_find_bucket_)(set, key, true);
+
+ if (mh_is_either(h, idx)) {
+ h->size++;
+ if (mh_is_empty(h, idx)) {
+ h->n_occupied++;
+ }
+
+ uint32_t pos = h->n_keys++;
+ if (pos >= h->keys_capacity) {
+ h->keys_capacity = MAX(h->keys_capacity * 2, 8);
+ set->keys = xrealloc(set->keys, h->keys_capacity * sizeof(KEY_TYPE));
+ *new = kMHNewKeyRealloc;
+ } else {
+ *new = kMHNewKeyDidFit;
+ }
+ set->keys[pos] = key;
+ h->hash[idx] = pos + 1;
+ return pos;
+ } else {
+ *new = kMHExisting;
+ uint32_t pos = h->hash[idx] - 1;
+ if (!KEY_NAME(equal_)(set->keys[pos], key)) {
+ abort();
+ }
+ return pos;
+ }
+}
+
+/// Deletes `*key` if found, do nothing otherwise
+///
+/// @param[in, out] key modified to the value contained in the set
+/// @return the index the item used to have in keys[]
+/// MH_TOMBSTONE if key was not found
+uint32_t KEY_NAME(mh_delete_)(SET_TYPE *set, KEY_TYPE *key)
+{
+ if (set->h.size == 0) {
+ return MH_TOMBSTONE;
+ }
+ uint32_t idx = KEY_NAME(mh_find_bucket_)(set, *key, false);
+ if (idx != MH_TOMBSTONE) {
+ uint32_t k = set->h.hash[idx] - 1;
+ set->h.hash[idx] = MH_TOMBSTONE;
+
+ uint32_t last = --set->h.n_keys;
+ *key = set->keys[k];
+ set->h.size--;
+ if (last != k) {
+ uint32_t idx2 = KEY_NAME(mh_find_bucket_)(set, set->keys[last], false);
+ if (set->h.hash[idx2] != last + 1) {
+ abort();
+ }
+ set->h.hash[idx2] = k + 1;
+ set->keys[k] = set->keys[last];
+ }
+ return k;
+ }
+ return MH_TOMBSTONE;
+}
diff --git a/src/nvim/map_value_impl.c.h b/src/nvim/map_value_impl.c.h
new file mode 100644
index 0000000000..fffda280f0
--- /dev/null
+++ b/src/nvim/map_value_impl.c.h
@@ -0,0 +1,64 @@
+#include "nvim/assert.h"
+#include "nvim/map.h"
+
+#if !defined(KEY_NAME) || !defined(VAL_NAME)
+// Don't error out. it is nice to type-check the file in isolation, in clangd or otherwise
+# define KEY_NAME(x) x##int
+# define VAL_NAME(x) quasiquote(x, ptr_t)
+#endif
+
+#define MAP_NAME(x) VAL_NAME(KEY_NAME(x))
+#define MAP_TYPE MAP_NAME(Map_)
+#define KEY_TYPE KEY_NAME()
+#define VALUE_TYPE VAL_NAME()
+#define INITIALIZER VAL_NAME(value_init_)
+
+VALUE_TYPE *MAP_NAME(map_ref_)(MAP_TYPE *map, KEY_TYPE key, KEY_TYPE **key_alloc)
+{
+ uint32_t k = KEY_NAME(mh_get_)(&map->set, key);
+ if (k == MH_TOMBSTONE) {
+ return NULL;
+ }
+ if (key_alloc) {
+ *key_alloc = &map->set.keys[k];
+ }
+ return &map->values[k];
+}
+
+VALUE_TYPE *MAP_NAME(map_put_ref_)(MAP_TYPE *map, KEY_TYPE key, KEY_TYPE **key_alloc,
+ bool *new_item)
+{
+ MhPutStatus status;
+ uint32_t k = KEY_NAME(mh_put_)(&map->set, key, &status);
+ if (status != kMHExisting) {
+ if (status == kMHNewKeyRealloc) {
+ map->values = xrealloc(map->values, map->set.h.keys_capacity * sizeof(VALUE_TYPE));
+ }
+ map->values[k] = INITIALIZER;
+ }
+ if (new_item) {
+ *new_item = (status != kMHExisting);
+ }
+ if (key_alloc) {
+ *key_alloc = &map->set.keys[k];
+ }
+ return &map->values[k];
+}
+
+VALUE_TYPE MAP_NAME(map_del_)(MAP_TYPE *map, KEY_TYPE key, KEY_TYPE *key_alloc)
+{
+ VALUE_TYPE rv = INITIALIZER;
+ uint32_t k = KEY_NAME(mh_delete_)(&map->set, &key);
+ if (k == MH_TOMBSTONE) {
+ return rv;
+ }
+
+ if (key_alloc) {
+ *key_alloc = key;
+ }
+ rv = map->values[k];
+ if (k != map->set.h.n_keys) {
+ map->values[k] = map->values[map->set.h.n_keys];
+ }
+ return rv;
+}
diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c
index 840b6b646e..d07d176b6d 100644
--- a/src/nvim/marktree.c
+++ b/src/nvim/marktree.c
@@ -548,10 +548,8 @@ void marktree_clear(MarkTree *b)
marktree_free_node(b->root);
b->root = NULL;
}
- if (b->id2node->table.keys) {
- map_destroy(uint64_t, b->id2node);
- *b->id2node = (PMap(uint64_t)) MAP_INIT;
- }
+ map_destroy(uint64_t, b->id2node);
+ *b->id2node = (PMap(uint64_t)) MAP_INIT;
b->n_keys = 0;
b->n_nodes = 0;
}
diff --git a/src/nvim/msgpack_rpc/channel.c b/src/nvim/msgpack_rpc/channel.c
index 095e392092..3a9b36a914 100644
--- a/src/nvim/msgpack_rpc/channel.c
+++ b/src/nvim/msgpack_rpc/channel.c
@@ -564,7 +564,7 @@ static void broadcast_event(const char *name, Array args)
kvec_t(Channel *) subscribed = KV_INITIAL_VALUE;
Channel *channel;
- pmap_foreach_value(&channels, channel, {
+ map_foreach_value(&channels, channel, {
if (channel->is_rpc
&& set_has(cstr_t, channel->rpc.subscribed_events, name)) {
kv_push(subscribed, channel);
diff --git a/src/nvim/os/env.c b/src/nvim/os/env.c
index f931e00916..10fe3cb114 100644
--- a/src/nvim/os/env.c
+++ b/src/nvim/os/env.c
@@ -64,7 +64,7 @@ const char *os_getenv(const char *name)
return NULL;
}
int r = 0;
- if (pmap_has(cstr_t)(&envmap, name)
+ if (map_has(cstr_t, &envmap, name)
&& !!(e = (char *)pmap_get(cstr_t)(&envmap, name))) {
if (e[0] != '\0') {
// Found non-empty cached env var.
diff --git a/src/nvim/runtime.c b/src/nvim/runtime.c
index 992566b0fe..269c3805a1 100644
--- a/src/nvim/runtime.c
+++ b/src/nvim/runtime.c
@@ -731,7 +731,7 @@ static bool path_is_after(char *buf, size_t buflen)
RuntimeSearchPath runtime_search_path_build(void)
{
kvec_t(String) pack_entries = KV_INITIAL_VALUE;
- Map(String, handle_T) pack_used = MAP_INIT;
+ Map(String, int) pack_used = MAP_INIT;
Set(String) rtp_used = SET_INIT;
RuntimeSearchPath search_path = KV_INITIAL_VALUE;
CharVec after_path = KV_INITIAL_VALUE;
@@ -744,7 +744,7 @@ RuntimeSearchPath runtime_search_path_build(void)
String the_entry = { .data = cur_entry, .size = strlen(buf) };
kv_push(pack_entries, the_entry);
- map_put(String, handle_T)(&pack_used, the_entry, 0);
+ map_put(String, int)(&pack_used, the_entry, 0);
}
char *rtp_entry;
@@ -761,7 +761,7 @@ RuntimeSearchPath runtime_search_path_build(void)
// fact: &rtp entries can contain wild chars
expand_rtp_entry(&search_path, &rtp_used, buf, false);
- handle_T *h = map_ref(String, handle_T)(&pack_used, cstr_as_string(buf), NULL);
+ handle_T *h = map_ref(String, int)(&pack_used, cstr_as_string(buf), NULL);
if (h) {
(*h)++;
expand_pack_entry(&search_path, &rtp_used, &after_path, buf, buflen);
@@ -770,7 +770,7 @@ RuntimeSearchPath runtime_search_path_build(void)
for (size_t i = 0; i < kv_size(pack_entries); i++) {
String item = kv_A(pack_entries, i);
- handle_T h = map_get(String, handle_T)(&pack_used, item);
+ handle_T h = map_get(String, int)(&pack_used, item);
if (h == 0) {
expand_pack_entry(&search_path, &rtp_used, &after_path, item.data, item.size);
}
diff --git a/src/nvim/shada.c b/src/nvim/shada.c
index 49136402ac..e302c05b1c 100644
--- a/src/nvim/shada.c
+++ b/src/nvim/shada.c
@@ -1396,7 +1396,7 @@ shada_read_main_cycle_end:
hms_dealloc(&hms[i]);
}
}
- if (cl_bufs.n_occupied) {
+ if (cl_bufs.h.n_occupied) {
FOR_ALL_TAB_WINDOWS(tp, wp) {
(void)tp;
if (set_has(ptr_t, &cl_bufs, wp->w_buffer)) {
@@ -1600,7 +1600,7 @@ static ShaDaWriteResult shada_pack_entry(msgpack_packer *const packer, ShadaEntr
break;
}
case kSDItemSearchPattern: {
- const size_t map_size = (
+ size_t entry_map_size = (
1 // Search pattern is always present
+ ONE_IF_NOT_DEFAULT(entry, search_pattern.magic)
+ ONE_IF_NOT_DEFAULT(entry, search_pattern.is_last_used)
@@ -1617,7 +1617,7 @@ static ShaDaWriteResult shada_pack_entry(msgpack_packer *const packer, ShadaEntr
entry.data.search_pattern.additional_data
? entry.data.search_pattern.additional_data->dv_hashtab.ht_used
: 0));
- msgpack_pack_map(spacker, map_size);
+ msgpack_pack_map(spacker, entry_map_size);
PACK_STATIC_STR(SEARCH_KEY_PAT);
PACK_BIN(cstr_as_string(entry.data.search_pattern.pat));
PACK_BOOL(entry, SEARCH_KEY_MAGIC, magic);
@@ -1641,7 +1641,7 @@ static ShaDaWriteResult shada_pack_entry(msgpack_packer *const packer, ShadaEntr
case kSDItemGlobalMark:
case kSDItemLocalMark:
case kSDItemJump: {
- const size_t map_size = (
+ size_t entry_map_size = (
1 // File name
+ ONE_IF_NOT_DEFAULT(entry, filemark.mark.lnum)
+ ONE_IF_NOT_DEFAULT(entry, filemark.mark.col)
@@ -1651,7 +1651,7 @@ static ShaDaWriteResult shada_pack_entry(msgpack_packer *const packer, ShadaEntr
entry.data.filemark.additional_data == NULL
? 0
: entry.data.filemark.additional_data->dv_hashtab.ht_used));
- msgpack_pack_map(spacker, map_size);
+ msgpack_pack_map(spacker, entry_map_size);
PACK_STATIC_STR(KEY_FILE);
PACK_BIN(cstr_as_string(entry.data.filemark.fname));
if (!CHECK_DEFAULT(entry, filemark.mark.lnum)) {
@@ -1674,7 +1674,7 @@ static ShaDaWriteResult shada_pack_entry(msgpack_packer *const packer, ShadaEntr
break;
}
case kSDItemRegister: {
- const size_t map_size = (2 // Register contents and name
+ size_t entry_map_size = (2 // Register contents and name
+ ONE_IF_NOT_DEFAULT(entry, reg.type)
+ ONE_IF_NOT_DEFAULT(entry, reg.width)
+ ONE_IF_NOT_DEFAULT(entry, reg.is_unnamed)
@@ -1682,7 +1682,7 @@ static ShaDaWriteResult shada_pack_entry(msgpack_packer *const packer, ShadaEntr
+ (entry.data.reg.additional_data == NULL
? 0
: entry.data.reg.additional_data->dv_hashtab.ht_used));
- msgpack_pack_map(spacker, map_size);
+ msgpack_pack_map(spacker, entry_map_size);
PACK_STATIC_STR(REG_KEY_CONTENTS);
msgpack_pack_array(spacker, entry.data.reg.contents_size);
for (size_t i = 0; i < entry.data.reg.contents_size; i++) {
@@ -1712,7 +1712,7 @@ static ShaDaWriteResult shada_pack_entry(msgpack_packer *const packer, ShadaEntr
case kSDItemBufferList:
msgpack_pack_array(spacker, entry.data.buffer_list.size);
for (size_t i = 0; i < entry.data.buffer_list.size; i++) {
- const size_t map_size = (
+ size_t entry_map_size = (
1 // Buffer name
+ (size_t)(entry.data.buffer_list.buffers[i].pos.lnum
!= default_pos.lnum)
@@ -1725,7 +1725,7 @@ static ShaDaWriteResult shada_pack_entry(msgpack_packer *const packer, ShadaEntr
? 0
: (entry.data.buffer_list.buffers[i].additional_data
->dv_hashtab.ht_used)));
- msgpack_pack_map(spacker, map_size);
+ msgpack_pack_map(spacker, entry_map_size);
PACK_STATIC_STR(KEY_FILE);
PACK_BIN(cstr_as_string(entry.data.buffer_list.buffers[i].fname));
if (entry.data.buffer_list.buffers[i].pos.lnum != 1) {
@@ -2867,7 +2867,7 @@ static ShaDaWriteResult shada_write(ShaDaWriteDef *const sd_writer, ShaDaReadDef
xmalloc(file_markss_size * sizeof(*all_file_markss));
FileMarks **cur_file_marks = all_file_markss;
ptr_t val;
- map_foreach_value(ptr_t, &wms->file_marks, val, {
+ map_foreach_value(&wms->file_marks, val, {
*cur_file_marks++ = val;
})
qsort((void *)all_file_markss, file_markss_size, sizeof(*all_file_markss),
@@ -2922,7 +2922,7 @@ shada_write_exit:
hms_dealloc(&wms->hms[i]);
}
}
- map_foreach_value(ptr_t, &wms->file_marks, val, {
+ map_foreach_value(&wms->file_marks, val, {
xfree(val);
})
map_destroy(cstr_t, &wms->file_marks);
diff --git a/src/nvim/tui/input.c b/src/nvim/tui/input.c
index c55cb44560..edf8cbe237 100644
--- a/src/nvim/tui/input.c
+++ b/src/nvim/tui/input.c
@@ -115,7 +115,7 @@ static const struct kitty_key_map_entry {
{ KITTY_KEY_KP_BEGIN, "kOrigin" },
};
-static Map(int, cstr_t) kitty_key_map = MAP_INIT;
+static PMap(int) kitty_key_map = MAP_INIT;
#ifdef INCLUDE_GENERATED_DECLARATIONS
# include "tui/input.c.generated.h"
@@ -133,8 +133,7 @@ void tinput_init(TermInput *input, Loop *loop)
input->key_buffer = rbuffer_new(KEY_BUFFER_SIZE);
for (size_t i = 0; i < ARRAY_SIZE(kitty_key_map_entry); i++) {
- map_put(int, cstr_t)(&kitty_key_map, kitty_key_map_entry[i].key,
- kitty_key_map_entry[i].name);
+ pmap_put(int)(&kitty_key_map, kitty_key_map_entry[i].key, (ptr_t)kitty_key_map_entry[i].name);
}
input->in_fd = STDIN_FILENO;
@@ -267,7 +266,7 @@ static size_t handle_more_modifiers(TermKeyKey *key, char *buf, size_t buflen)
static void handle_kitty_key_protocol(TermInput *input, TermKeyKey *key)
{
- const char *name = map_get(int, cstr_t)(&kitty_key_map, (int)key->code.codepoint);
+ const char *name = pmap_get(int)(&kitty_key_map, (int)key->code.codepoint);
if (name) {
char buf[64];
size_t len = 0;
@@ -287,7 +286,7 @@ static void forward_simple_utf8(TermInput *input, TermKeyKey *key)
char *ptr = key->utf8;
if (key->code.codepoint >= 0xE000 && key->code.codepoint <= 0xF8FF
- && map_has(int, cstr_t)(&kitty_key_map, (int)key->code.codepoint)) {
+ && map_has(int, &kitty_key_map, (int)key->code.codepoint)) {
handle_kitty_key_protocol(input, key);
return;
}
@@ -317,7 +316,7 @@ static void forward_modified_utf8(TermInput *input, TermKeyKey *key)
} else {
assert(key->modifiers);
if (key->code.codepoint >= 0xE000 && key->code.codepoint <= 0xF8FF
- && map_has(int, cstr_t)(&kitty_key_map, (int)key->code.codepoint)) {
+ && map_has(int, &kitty_key_map, (int)key->code.codepoint)) {
handle_kitty_key_protocol(input, key);
return;
}
diff --git a/src/nvim/ui.c b/src/nvim/ui.c
index 7d8328d913..ba16ba545f 100644
--- a/src/nvim/ui.c
+++ b/src/nvim/ui.c
@@ -127,7 +127,7 @@ void ui_free_all_mem(void)
kv_destroy(call_buf);
UIEventCallback *event_cb;
- pmap_foreach_value(&ui_event_cbs, event_cb, {
+ map_foreach_value(&ui_event_cbs, event_cb, {
free_ui_event_callback(event_cb);
})
map_destroy(uint32_t, &ui_event_cbs);
@@ -661,7 +661,7 @@ void ui_call_event(char *name, Array args)
{
UIEventCallback *event_cb;
bool handled = false;
- pmap_foreach_value(&ui_event_cbs, event_cb, {
+ map_foreach_value(&ui_event_cbs, event_cb, {
Error err = ERROR_INIT;
Object res = nlua_call_ref(event_cb->cb, name, args, false, &err);
if (res.type == kObjectTypeBoolean && res.data.boolean == true) {
@@ -687,7 +687,7 @@ void ui_cb_update_ext(void)
for (size_t i = 0; i < kUIGlobalCount; i++) {
UIEventCallback *event_cb;
- pmap_foreach_value(&ui_event_cbs, event_cb, {
+ map_foreach_value(&ui_event_cbs, event_cb, {
if (event_cb->ext_widgets[i]) {
ui_cb_ext[i] = true;
break;
@@ -723,7 +723,7 @@ void ui_add_cb(uint32_t ns_id, LuaRef cb, bool *ext_widgets)
void ui_remove_cb(uint32_t ns_id)
{
- if (pmap_has(uint32_t)(&ui_event_cbs, ns_id)) {
+ if (map_has(uint32_t, &ui_event_cbs, ns_id)) {
UIEventCallback *item = pmap_del(uint32_t)(&ui_event_cbs, ns_id, NULL);
free_ui_event_callback(item);
}
diff --git a/test/client/session.lua b/test/client/session.lua
index 0509fa88be..b1bf5ea75e 100644
--- a/test/client/session.lua
+++ b/test/client/session.lua
@@ -73,6 +73,11 @@ function Session:next_message(timeout)
return table.remove(self._pending_messages, 1)
end
+ -- if closed, only return pending messages
+ if self.closed then
+ return nil
+ end
+
self:_run(on_request, on_notification, timeout)
return table.remove(self._pending_messages, 1)
end
@@ -139,6 +144,7 @@ function Session:close(signal)
if not self._timer:is_closing() then self._timer:close() end
if not self._prepare:is_closing() then self._prepare:close() end
self._msgpack_rpc_stream:close(signal)
+ self.closed = true
end
function Session:_yielding_request(method, args)
diff --git a/test/functional/helpers.lua b/test/functional/helpers.lua
index 67275b12a4..b98cf97e7e 100644
--- a/test/functional/helpers.lua
+++ b/test/functional/helpers.lua
@@ -83,6 +83,13 @@ end
local session, loop_running, last_error, method_error
+if not is_os('win') then
+ local sigpipe_handler = luv.new_signal()
+ luv.signal_start(sigpipe_handler, "sigpipe", function()
+ print("warning: got SIGPIPE signal. Likely related to a crash in nvim")
+ end)
+end
+
function module.get_session()
return session
end
diff --git a/test/unit/helpers.lua b/test/unit/helpers.lua
index 52769cd9e9..e9b97266d0 100644
--- a/test/unit/helpers.lua
+++ b/test/unit/helpers.lua
@@ -139,6 +139,7 @@ local function filter_complex_blocks(body)
or string.find(line, "_Float")
or string.find(line, "msgpack_zone_push_finalizer")
or string.find(line, "msgpack_unpacker_reserve_buffer")
+ or string.find(line, "value_init_")
or string.find(line, "UUID_NULL") -- static const uuid_t UUID_NULL = {...}
or string.find(line, "inline _Bool")) then
result[#result + 1] = line
generated by cgit (git 2.34.1) at 2025-04-29 06:56:23 +0000