Merge pull request #24985 from bfredl/hash2

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

21 files changed, 560 insertions, 235 deletions

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);
   }