From e2fdd53d8c015913e8be4ff708fc3488558c8906 Mon Sep 17 00:00:00 2001 From: bfredl Date: Sun, 14 May 2023 18:45:56 +0200 Subject: refactor(map): avoid duplicated khash_t types for values This reduces the total number of khash_t instantiations from 22 to 8. Make the khash internal functions take the size of values as a runtime parameter. This is abstracted with typesafe Map containers which are still specialized for both key, value type. Introduce `Set(key)` type for when there is no value. Refactor shada.c to use Map/Set instead of khash directly. This requires `map_ref` operation to be more flexible. Return pointers to both key and value, plus an indicator for new_item. As a bonus, `map_key` is now redundant. Instead of Map(cstr_t, FileMarks), use a pointer map as the FileMarks struct is humongous. Make `event_strings` actually work like an intern pool instead of wtf it was doing before. --- src/nvim/map_defs.h | 12 ------------ 1 file changed, 12 deletions(-) delete mode 100644 src/nvim/map_defs.h (limited to 'src/nvim/map_defs.h') diff --git a/src/nvim/map_defs.h b/src/nvim/map_defs.h deleted file mode 100644 index 61afedbe50..0000000000 --- a/src/nvim/map_defs.h +++ /dev/null @@ -1,12 +0,0 @@ -#ifndef NVIM_MAP_DEFS_H -#define NVIM_MAP_DEFS_H - -#include "klib/khash.h" - -typedef const char *cstr_t; -typedef void *ptr_t; - -#define Map(T, U) Map_##T##_##U -#define PMap(T) Map(T, ptr_t) - -#endif // NVIM_MAP_DEFS_H -- cgit From 79b6ff28ad1204fbb4199b9092f5c578d88cb28e Mon Sep 17 00:00:00 2001 From: dundargoc Date: Tue, 28 Nov 2023 20:31:00 +0100 Subject: refactor: fix headers with IWYU --- src/nvim/map_defs.h | 226 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 226 insertions(+) create mode 100644 src/nvim/map_defs.h (limited to 'src/nvim/map_defs.h') diff --git a/src/nvim/map_defs.h b/src/nvim/map_defs.h new file mode 100644 index 0000000000..147c03327a --- /dev/null +++ b/src/nvim/map_defs.h @@ -0,0 +1,226 @@ +#pragma once + +#include +#include +#include + +#include "nvim/api/private/defs.h" +#include "nvim/assert_defs.h" +#include "nvim/highlight_defs.h" +#include "nvim/types_defs.h" + +#if defined(__NetBSD__) +# undef uint64_t +# define uint64_t uint64_t +#endif + +typedef const char *cstr_t; +typedef void *ptr_t; + +// 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) +{ + 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 equal_String(String a, String b) +{ + if (a.size != b.size) { + return false; + } + return memcmp(a.data, b.data, a.size) == 0; +} + +#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 int64_t value_init_int64_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 MH_DECLS(T, K, K_query) \ + typedef struct { \ + MapHash h; \ + K *keys; \ + } Set(T); \ + \ + uint32_t mh_find_bucket_##T(Set(T) *set, K_query key, bool put); \ + uint32_t mh_get_##T(Set(T) *set, K_query key); \ + void mh_rehash_##T(Set(T) *set); \ + uint32_t mh_put_##T(Set(T) *set, K_query key, MHPutStatus *new); \ + +#define KEY_DECLS(T) \ + MH_DECLS(T, T, T) \ + uint32_t mh_delete_##T(Set(T) *set, T *key); \ + static inline bool set_put_##T(Set(T) *set, T key, T **key_alloc) { \ + MHPutStatus status; \ + uint32_t k = mh_put_##T(set, key, &status); \ + if (key_alloc) { \ + *key_alloc = &set->keys[k]; \ + } \ + return status != kMHExisting; \ + } \ + static inline T set_del_##T(Set(T) *set, T key) \ + { \ + mh_delete_##T(set, &key); \ + return key; \ + } \ + static inline bool set_has_##T(Set(T) *set, T key) { \ + 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 { \ + Set(T) set; \ + U *values; \ + } Map(T, U); \ + static inline U map_get_##T##U(Map(T, U) *map, T key) \ + { \ + uint32_t k = mh_get_##T(&map->set, key); \ + return k == MH_TOMBSTONE ? value_init_##U : map->values[k]; \ + } \ + 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! Map and Set does not make a copy. + +#define quasiquote(x, y) x##y + +MH_DECLS(glyph, char, String) +KEY_DECLS(int) +KEY_DECLS(cstr_t) +KEY_DECLS(ptr_t) +KEY_DECLS(uint64_t) +KEY_DECLS(int64_t) +KEY_DECLS(uint32_t) +KEY_DECLS(String) +KEY_DECLS(HlEntry) +KEY_DECLS(ColorKey) + +MAP_DECLS(int, int) +MAP_DECLS(int, ptr_t) +MAP_DECLS(cstr_t, ptr_t) +MAP_DECLS(cstr_t, int) +MAP_DECLS(ptr_t, ptr_t) +MAP_DECLS(uint32_t, ptr_t) +MAP_DECLS(uint64_t, ptr_t) +MAP_DECLS(uint64_t, ssize_t) +MAP_DECLS(uint64_t, uint64_t) +MAP_DECLS(int64_t, int64_t) +MAP_DECLS(int64_t, ptr_t) +MAP_DECLS(uint32_t, uint32_t) +MAP_DECLS(String, int) +MAP_DECLS(int, String) +MAP_DECLS(ColorKey, ColorItem) + +#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_put_idx(T, set, key, status) mh_put_##T(set, key, status) +#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_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 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_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 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); -- cgit