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
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
|
#pragma once
#include "misc.h"
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
struct htab_internal {
size_t length;
size_t capacity;
void *base;
char hi_storage[1]; // see vec.h
};
/* Declare the helper functions for a htab key type without static - put this
* in the .h and IMPL_HTAB_KEY in a .c. */
#define DECL_EXTERN_HTAB_KEY( \
name, \
/* The key type. */ \
key_ty \
) \
DO_DECL_HTAB_KEY(name, key_ty, )
/* Declare and implement the helper functions static inline. For the argument
* meanings, see IMPL_HTAB_KEY. */
#define DECL_STATIC_HTAB_KEY( \
name, \
key_ty, \
hash_func, \
eq_func, \
null_func, \
nil_byte \
) \
DO_DECL_HTAB_KEY(name, key_ty, UNUSED_STATIC_INLINE); \
IMPL_HTAB_KEY(name, hash_func, eq_func, null_func, nil_byte)
#define DO_DECL_HTAB_KEY(name, key_ty, func_decl) \
typedef key_ty __htab_key_key_ty_##name; \
DO_DECL_HTAB_KEY_(name, __htab_key_key_ty_##name, func_decl)
#define DO_DECL_HTAB_KEY_(name, key_ty, func_decl) \
func_decl \
void *__htab_key_lookup_##name(struct htab_internal *restrict hi, \
const key_ty *restrict key, \
size_t entry_size, \
bool add, bool resize_if_necessary); \
func_decl \
bool __htab_key_remove_##name(struct htab_internal *restrict hi, \
const key_ty *restrict key, \
size_t entry_size); \
func_decl \
void __htab_key_memset_##name(void *ptr, size_t size); \
func_decl \
bool __htab_key_is_null_##name(const key_ty *bucket); \
func_decl \
void __htab_key_resize_##name(struct htab_internal *restrict hi, \
size_t size, \
size_t entry_size) \
#define IMPL_HTAB_KEY(name, \
/* size_t hash_func(const ty *) - hash. \
* May be a macro. */ \
hash_func, \
/* bool eq_func(const ty *stored, const ty *queried) - check whether the \
* stored key is equal to the requested key (which is assumed to be valid). \
* May be a macro. */ \
eq_func, \
/* bool null_func(const ty *) - check whether the stored key is a \
* special invalid marker. \
* May be a macro. */ \
null_func, \
/* uint8_t nil_byte - which byte to memset to initially. \
* null_func(<all bytes nil_byte>) must be true. */ \
nil_byte \
) \
DO_IMPL_HTAB_KEY(name, __htab_key_key_ty_##name, hash_func, \
eq_func, null_func, nil_byte)
#define DO_IMPL_HTAB_KEY(name, key_ty, hash_func, eq_func, null_func, nil_byte) \
void __htab_key_resize_##name(struct htab_internal *restrict hi, \
size_t capacity, \
size_t entry_size); \
void *__htab_key_lookup_##name(struct htab_internal *restrict hi, \
const key_ty *restrict key, \
size_t entry_size, \
bool add, bool resize_if_necessary) { \
if (resize_if_necessary && \
hi->capacity * 2 <= hi->length * 3) \
__htab_key_resize_##name(hi, hi->capacity * 2, entry_size); \
size_t capacity = hi->capacity; \
size_t hash = (hash_func(key)) % capacity; \
size_t i = hash; \
char *buckets = hi->base; \
do { \
key_ty *bucket = (void *) (buckets + i * entry_size); \
if (null_func(bucket)) { \
if (add) { \
hi->length++; \
return bucket; \
} else { \
return NULL; \
} \
} \
if (eq_func(bucket, key)) \
return bucket; \
} while ((i = (i + 1) % capacity) != hash); \
return NULL; \
} \
\
/* slow but who cares */ \
bool __htab_key_remove_##name(struct htab_internal *restrict hi, \
const key_ty *restrict key, \
size_t entry_size) { \
void *op = __htab_key_lookup_##name(hi, key, entry_size, false, false); \
if (!op) \
return false; \
key_ty *orig = op; \
key_ty *end = (void *) ((char *) hi->base + hi->capacity * entry_size); \
key_ty *cur = orig; \
key_ty *prev; \
do { \
prev = cur; \
cur = (void *) ((char *) cur + entry_size); \
if (cur == end) \
cur = hi->base; \
if (null_func(cur)) \
break; \
memmove(prev, cur, entry_size); \
prev = cur; \
} while (cur != orig); \
memset(cur, 0, entry_size); \
hi->length--; \
return true; \
} \
void __htab_key_memset_##name(void *ptr, size_t size) { \
memset(ptr, (nil_byte), size); \
} \
bool __htab_key_is_null_##name(const key_ty *bucket) { \
return null_func(bucket); \
} \
void __htab_key_resize_##name(struct htab_internal *restrict hi, \
size_t size, \
size_t entry_size) { \
size_t old_size = hi->capacity * entry_size; \
size_t new_size = safe_mul(size, entry_size); \
void *new_buf = malloc(new_size); \
memset(new_buf, (nil_byte), new_size); \
struct htab_internal temp; \
temp.length = 0; \
temp.capacity = size; \
temp.base = new_buf; \
for (size_t i = 0; i < old_size; i += entry_size) { \
key_ty *bucket = (void *) ((char *) hi->base + i); \
if (!null_func(bucket)) { \
memcpy( \
__htab_key_lookup_##name(&temp, bucket, entry_size, \
true, false), \
bucket, \
entry_size); \
} \
} \
hi->capacity = size; \
if (hi->base != hi->hi_storage) \
free(hi->base); \
hi->base = new_buf; \
} \
typedef char __htab_want_semicolon_here_##name
#define DECL_HTAB( \
name, \
/* The name parameter to DECL_HTAB_KEY */ \
key_name, \
value_ty) \
typedef __htab_key_key_ty_##key_name __htab_key_ty_##name; \
typedef value_ty __htab_value_ty_##name; \
\
DO_DECL_HTAB(name, \
__htab_key_ty_##name, \
__htab_value_ty_##name, \
struct htab_bucket_##name, \
struct htab_##name, \
key_name)
#define DO_DECL_HTAB(name, key_ty, value_ty, bucket_ty, htab_ty, key_name) \
bucket_ty { \
key_ty key; \
value_ty value; \
}; \
htab_ty { \
union { \
struct htab_internal hi; \
struct { \
size_t length; \
size_t capacity; \
bucket_ty *base; \
bucket_ty storage[1]; \
}; \
}; \
}; \
UNUSED_STATIC_INLINE \
bucket_ty *htab_getbucket_##name(htab_ty *restrict ht, \
const key_ty *restrict key) { \
return __htab_key_lookup_##key_name(&ht->hi, key, sizeof(bucket_ty), \
false, true); \
} \
UNUSED_STATIC_INLINE \
value_ty *htab_getp_##name(const htab_ty *restrict ht, \
const key_ty *restrict key) { \
bucket_ty *bucket = htab_getbucket_##name((void *) ht, key); \
return bucket ? &bucket->value : NULL; \
} \
UNUSED_STATIC_INLINE \
bucket_ty *htab_setbucket_##name(htab_ty *restrict ht, \
const key_ty *restrict key) { \
return __htab_key_lookup_##key_name(&ht->hi, key, sizeof(bucket_ty), \
true, true); \
} \
UNUSED_STATIC_INLINE \
value_ty *htab_setp_##name(const htab_ty *restrict ht, \
const key_ty *restrict key, \
bool *new_p) { \
bucket_ty *bucket = htab_setbucket_##name((void *) ht, key); \
bool new = false; \
if (__htab_key_is_null_##key_name(&bucket->key)) { \
bucket->key = *key; \
new = true; \
} else { \
new = false; \
} \
if (new_p) \
*new_p = new; \
return &bucket->value; \
} \
UNUSED_STATIC_INLINE \
bool htab_remove_##name(htab_ty *restrict ht, const key_ty *restrict key) { \
return __htab_key_remove_##key_name(&ht->hi, key, sizeof(bucket_ty)); \
} \
UNUSED_STATIC_INLINE \
void __htab_memset_##name(void *ptr, size_t size) { \
return __htab_key_memset_##key_name(ptr, size); \
} \
UNUSED_STATIC_INLINE \
bool __htab_is_null_##name(const key_ty *bucket) { \
return __htab_key_is_null_##key_name(bucket); \
} \
UNUSED_STATIC_INLINE \
void htab_resize_##name(htab_ty *ht, size_t size) { \
return __htab_key_resize_##key_name(&ht->hi, size, sizeof(bucket_ty)); \
} \
UNUSED_STATIC_INLINE \
void htab_free_storage_##name(htab_ty *ht) { \
if (ht->base != ht->storage) \
free(ht->base); \
}
#define HTAB_STORAGE_CAPA(name, n) \
struct { \
struct htab_##name h; \
struct htab_bucket_##name rest[(n)-1]; \
}
#define HTAB_STORAGE(name) \
HTAB_STORAGE_CAPA(name, 5)
#define HTAB_STORAGE_INIT(hs, name) do { \
struct htab_##name *h = &(hs)->h; \
h->length = 0; \
h->capacity = (sizeof((hs)->rest) / sizeof(__htab_key_ty_##name)) + 1; \
h->base = h->storage; \
__htab_memset_##name(h->base, \
h->capacity * sizeof(__htab_key_ty_##name)); \
} while (0)
#define HTAB_FOREACH(ht, key_var, val_var, name) \
LET(struct htab_##name *__htfe_ht = (ht)) \
for (size_t __htfe_bucket = 0; \
__htfe_bucket < __htfe_ht->capacity; \
__htfe_bucket++) \
if(__htab_is_null_##name(&__htfe_ht->base[__htfe_bucket].key)) \
continue; \
else \
LET_LOOP(key_var = &__htfe_ht->base[__htfe_bucket].key) \
LET_LOOP(val_var = &__htfe_ht->base[__htfe_bucket].value)
|
