1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
|
#pragma once
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#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);
|
