Merge remote-tracking branch 'upstream/master' into aucmd_textputpostaucmd_textputpost

1 files changed, 140 insertions, 144 deletions

diff --git a/src/nvim/map.c b/src/nvim/map.c
index 191a459863..be6bf58daa 100644
--- a/src/nvim/map.c
+++ b/src/nvim/map.c
@@ -1,197 +1,193 @@
-// 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/map_defs.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 KittyKey_hash kh_int_hash_func
-#define KittyKey_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
+#define hash_int64_t(key) hash_uint64_t((uint64_t)key)
+#define equal_int64_t 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 MAP_IMPL(T, U, ...) \
-  INITIALIZER_DECLARE(T, U, __VA_ARGS__); \
-  __KHASH_IMPL(T##_##U##_map, , T, U, 1, T##_hash, T##_eq) \
-  void map_##T##_##U##_destroy(Map(T, U) *map) \
-  { \
-    kh_dealloc(T##_##U##_map, &map->table); \
-  } \
-  U map_##T##_##U##_get(Map(T, U) *map, T key) \
-  { \
-    khiter_t k; \
-    if ((k = kh_get(T##_##U##_map, &map->table, key)) == kh_end(&map->table)) { \
-      return INITIALIZER(T, U); \
-    } \
-    return kh_val(&map->table, k); \
-  } \
-  bool map_##T##_##U##_has(Map(T, U) *map, T key) \
-  { \
-    return kh_get(T##_##U##_map, &map->table, key) != kh_end(&map->table); \
-  } \
-  T map_##T##_##U##_key(Map(T, U) *map, T key) \
-  { \
-    khiter_t k; \
-    if ((k = kh_get(T##_##U##_map, &map->table, key)) == kh_end(&map->table)) { \
-      abort();  /* Caller must check map_has(). */ \
-    } \
-    return kh_key(&map->table, k); \
-  } \
-  U map_##T##_##U##_put(Map(T, U) *map, T key, U value) \
-  { \
-    int ret; \
-    U rv = INITIALIZER(T, U); \
-    khiter_t k = kh_put(T##_##U##_map, &map->table, key, &ret); \
-    if (!ret) { \
-      rv = kh_val(&map->table, k); \
-    } \
-    kh_val(&map->table, k) = value; \
-    return rv; \
-  } \
-  U *map_##T##_##U##_ref(Map(T, U) *map, T key, bool put) \
-  { \
-    int ret; \
-    khiter_t k; \
-    if (put) { \
-      k = kh_put(T##_##U##_map, &map->table, key, &ret); \
-      if (ret) { \
-        kh_val(&map->table, k) = INITIALIZER(T, U); \
-      } \
-    } else { \
-      k = kh_get(T##_##U##_map, &map->table, key); \
-      if (k == kh_end(&map->table)) { \
-        return NULL; \
-      } \
-    } \
-    return &kh_val(&map->table, k); \
-  } \
-  U map_##T##_##U##_del(Map(T, U) *map, T key) \
-  { \
-    U rv = INITIALIZER(T, U); \
-    khiter_t k; \
-    if ((k = kh_get(T##_##U##_map, &map->table, key)) != kh_end(&map->table)) { \
-      rv = kh_val(&map->table, k); \
-      kh_del(T##_##U##_map, &map->table, k); \
-    } \
-    return rv; \
-  } \
-  void map_##T##_##U##_clear(Map(T, U) *map) \
-  { \
-    kh_clear(T##_##U##_map, &map->table); \
-  }
-
-static inline khint_t String_hash(String s)
+static inline uint32_t hash_cstr_t(const char *s)
 {
-  khint_t h = 0;
-  for (size_t i = 0; i < s.size && s.data[i]; i++) {
-    h = (h << 5) - h + (uint8_t)s.data[i];
+  uint32_t h = 0;
+  for (size_t i = 0; s[i]; i++) {
+    h = (h << 5) - h + (uint8_t)s[i];
   }
   return h;
 }
 
-static inline bool String_eq(String a, String b)
-{
-  if (a.size != b.size) {
-    return false;
-  }
-  return memcmp(a.data, b.data, a.size) == 0;
-}
+#define equal_cstr_t strequal
 
-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;
 }
 
-MAP_IMPL(int, int, 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(handle_T, ptr_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)
-
-MAP_IMPL(KittyKey, cstr_t, DEFAULT_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##int64_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, int64_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"
+#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.
 ///
 void pmap_del2(PMap(cstr_t) *map, const char *key)
 {
-  if (pmap_has(cstr_t)(map, key)) {
-    void *k = (void *)pmap_key(cstr_t)(map, key);
-    void *v = pmap_get(cstr_t)(map, key);
-    pmap_del(cstr_t)(map, key);
-    xfree(k);
-    xfree(v);
-  }
+  cstr_t key_alloc = NULL;
+  ptr_t val = pmap_del(cstr_t)(map, key, &key_alloc);
+  xfree((void *)key_alloc);
+  xfree(val);
 }