aboutsummaryrefslogtreecommitdiff
path: root/src/nvim/map.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/nvim/map.c')
-rw-r--r--src/nvim/map.c284
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);
}
generated by cgit (git 2.34.1) at 2025-04-28 13:48:35 +0000