Merge pull request #24985 from bfredl/hash2

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

1 files changed, 125 insertions, 52 deletions

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