refactor(map): enhanced implementation, Clean Code™, etc etc

This involves two redesigns of the map.c implementations:

1. Change of macro style and code organization

The old khash.h and map.c implementation used huge #define blocks with a
lot of backslash line continuations.

This instead uses the "implementation file" .c.h pattern. Such a file is
meant to be included multiple times, with different macros set prior to
inclusion as parameters. we already use this pattern e.g. for
eval/typval_encode.c.h to implement different typval encoders reusing a
similar structure.

We can structure this code into two parts. one that only depends on key
type and is enough to implement sets, and one which depends on both key
and value to implement maps (as a wrapper around sets, with an added
value[] array)

2. Separate the main hash buckets from the key / value arrays

Change the hack buckets to only contain an index into separate key /
value arrays
This is a common pattern in modern, state of the art hashmap
implementations. Even though this leads to one more allocated array, it
is this often is a net reduction of memory consumption. Consider
key+value consuming at least 12 bytes per pair. On average, we will have
twice as many buckets per item.
Thus old implementation:

  2*12 = 24 bytes per item

New implementation

  1*12 + 2*4 = 20 bytes per item

And the difference gets bigger with larger items.
One might think we have pulled a fast one here, as wouldn't the average size of
the new key/value arrays be 1.5 slots per items due to amortized grows?
But remember, these arrays are fully dense, and thus the accessed memory,
measured in _cache lines_, the unit which actually matters, will be the
fully used memory but just rounded up to the nearest cache line
boundary.

This has some other interesting properties, such as an insert-only
set/map will be fully ordered by insert only. Preserving this ordering
in face of deletions is more tricky tho. As we currently don't use
ordered maps, the "delete" operation maintains compactness of the item
arrays in the simplest way by breaking the ordering. It would be
possible to implement an order-preserving delete although at some cost,
like allowing the items array to become non-dense until the next rehash.

Finally, in face of these two major changes, all code used in khash.h
has been integrated into map.c and friends. Given the heavy edits it
makes no sense to "layer" the code into a vendored and a wrapper part.
Rather, the layered cake follows the specialization depth: code shared
for all maps, code specialized to a key type (and its equivalence
relation), and finally code specialized to value+key type.

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