src/util/table.c (view raw)
1/* Copyright (c) 2013-2020 Jeffrey Pfau
2 *
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6#include <mgba-util/table.h>
7
8#include <mgba-util/hash.h>
9#include <mgba-util/math.h>
10#include <mgba-util/string.h>
11
12#define LIST_INITIAL_SIZE 4
13#define TABLE_INITIAL_SIZE 8
14#define REBALANCE_THRESHOLD 4
15
16#define TABLE_COMPARATOR(LIST, INDEX) LIST->list[(INDEX)].key == key
17#define HASH_TABLE_STRNCMP_COMPARATOR(LIST, INDEX) LIST->list[(INDEX)].key == hash && strncmp(LIST->list[(INDEX)].stringKey, key, LIST->list[(INDEX)].keylen) == 0
18#define HASH_TABLE_MEMCMP_COMPARATOR(LIST, INDEX) LIST->list[(INDEX)].key == hash && LIST->list[(INDEX)].keylen == keylen && memcmp(LIST->list[(INDEX)].stringKey, key, LIST->list[(INDEX)].keylen) == 0
19
20#define TABLE_LOOKUP_START(COMPARATOR, LIST) \
21 size_t i; \
22 for (i = 0; i < LIST->nEntries; ++i) { \
23 if (COMPARATOR(LIST, i)) { \
24 struct TableTuple* lookupResult = &LIST->list[i]; \
25 UNUSED(lookupResult);
26
27#define TABLE_LOOKUP_END \
28 break; \
29 } \
30 }
31
32struct TableTuple {
33 uint32_t key;
34 char* stringKey;
35 size_t keylen;
36 void* value;
37};
38
39struct TableList {
40 struct TableTuple* list;
41 size_t nEntries;
42 size_t listSize;
43};
44
45void HashTableInsertBinaryMoveKey(struct Table* table, void* key, size_t keylen, void* value);
46
47static inline const struct TableList* _getConstList(const struct Table* table, uint32_t key) {
48 uint32_t entry = key & (table->tableSize - 1);
49 return &table->table[entry];
50}
51
52static inline struct TableList* _getList(struct Table* table, uint32_t key) {
53 uint32_t entry = key & (table->tableSize - 1);
54 return &table->table[entry];
55}
56
57static struct TableList* _resizeAsNeeded(struct Table* table, struct TableList* list, uint32_t key) {
58 UNUSED(table);
59 UNUSED(key);
60 // TODO: Expand table if needed
61 if (list->nEntries + 1 == list->listSize) {
62 list->listSize *= 2;
63 list->list = realloc(list->list, list->listSize * sizeof(struct TableTuple));
64 }
65 return list;
66}
67
68static void _removeItemFromList(struct Table* table, struct TableList* list, size_t item) {
69 --list->nEntries;
70 --table->size;
71 free(list->list[item].stringKey);
72 if (table->deinitializer) {
73 table->deinitializer(list->list[item].value);
74 }
75 if (item != list->nEntries) {
76 list->list[item] = list->list[list->nEntries];
77 }
78}
79
80static void _rebalance(struct Table* table) {
81 struct Table newTable;
82 TableInit(&newTable, table->tableSize * REBALANCE_THRESHOLD, NULL);
83 newTable.seed = table->seed * 134775813 + 1;
84 size_t i;
85 for (i = 0; i < table->tableSize; ++i) {
86 const struct TableList* list = &table->table[i];
87 size_t j;
88 for (j = 0; j < list->nEntries; ++j) {
89 HashTableInsertBinaryMoveKey(&newTable, list->list[j].stringKey, list->list[j].keylen, list->list[j].value);
90 }
91 free(list->list);
92 }
93 free(table->table);
94 table->tableSize = newTable.tableSize;
95 table->table = newTable.table;
96 table->seed = newTable.seed;
97}
98
99void TableInit(struct Table* table, size_t initialSize, void (*deinitializer)(void*)) {
100 if (initialSize < 2) {
101 initialSize = TABLE_INITIAL_SIZE;
102 } else if (initialSize & (initialSize - 1)) {
103 initialSize = toPow2(initialSize);
104 }
105 table->tableSize = initialSize;
106 table->table = calloc(table->tableSize, sizeof(struct TableList));
107 table->size = 0;
108 table->deinitializer = deinitializer;
109 table->seed = 0;
110
111 size_t i;
112 for (i = 0; i < table->tableSize; ++i) {
113 table->table[i].listSize = LIST_INITIAL_SIZE;
114 table->table[i].nEntries = 0;
115 table->table[i].list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
116 }
117}
118
119void TableDeinit(struct Table* table) {
120 size_t i;
121 for (i = 0; i < table->tableSize; ++i) {
122 struct TableList* list = &table->table[i];
123 size_t j;
124 for (j = 0; j < list->nEntries; ++j) {
125 free(list->list[j].stringKey);
126 if (table->deinitializer) {
127 table->deinitializer(list->list[j].value);
128 }
129 }
130 free(list->list);
131 }
132 free(table->table);
133 table->table = 0;
134 table->tableSize = 0;
135}
136
137void* TableLookup(const struct Table* table, uint32_t key) {
138 const struct TableList* list = _getConstList(table, key);
139 TABLE_LOOKUP_START(TABLE_COMPARATOR, list) {
140 return lookupResult->value;
141 } TABLE_LOOKUP_END;
142 return 0;
143}
144
145void TableInsert(struct Table* table, uint32_t key, void* value) {
146 struct TableList* list = _getList(table, key);
147 TABLE_LOOKUP_START(TABLE_COMPARATOR, list) {
148 if (value != lookupResult->value) {
149 if (table->deinitializer) {
150 table->deinitializer(lookupResult->value);
151 }
152 lookupResult->value = value;
153 }
154 return;
155 } TABLE_LOOKUP_END;
156 list = _resizeAsNeeded(table, list, key);
157 list->list[list->nEntries].key = key;
158 list->list[list->nEntries].stringKey = 0;
159 list->list[list->nEntries].value = value;
160 ++list->nEntries;
161 ++table->size;
162}
163
164void TableRemove(struct Table* table, uint32_t key) {
165 struct TableList* list = _getList(table, key);
166 TABLE_LOOKUP_START(TABLE_COMPARATOR, list) {
167 _removeItemFromList(table, list, i); // TODO: Move i out of the macro
168 } TABLE_LOOKUP_END;
169}
170
171void TableClear(struct Table* table) {
172 size_t i;
173 for (i = 0; i < table->tableSize; ++i) {
174 struct TableList* list = &table->table[i];
175 if (table->deinitializer) {
176 size_t j;
177 for (j = 0; j < list->nEntries; ++j) {
178 table->deinitializer(list->list[j].value);
179 }
180 }
181 free(list->list);
182 list->listSize = LIST_INITIAL_SIZE;
183 list->nEntries = 0;
184 list->list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
185 }
186}
187
188void TableEnumerate(const struct Table* table, void (*handler)(uint32_t key, void* value, void* user), void* user) {
189 size_t i;
190 for (i = 0; i < table->tableSize; ++i) {
191 const struct TableList* list = &table->table[i];
192 size_t j;
193 for (j = 0; j < list->nEntries; ++j) {
194 handler(list->list[j].key, list->list[j].value, user);
195 }
196 }
197}
198
199size_t TableSize(const struct Table* table) {
200 return table->size;
201}
202
203void HashTableInit(struct Table* table, size_t initialSize, void (*deinitializer)(void*)) {
204 TableInit(table, initialSize, deinitializer);
205 table->seed = 1;
206}
207
208void HashTableDeinit(struct Table* table) {
209 TableDeinit(table);
210}
211
212void* HashTableLookup(const struct Table* table, const char* key) {
213 uint32_t hash = hash32(key, strlen(key), table->seed);
214 const struct TableList* list = _getConstList(table, hash);
215 TABLE_LOOKUP_START(HASH_TABLE_STRNCMP_COMPARATOR, list) {
216 return lookupResult->value;
217 } TABLE_LOOKUP_END;
218 return 0;
219}
220
221void* HashTableLookupBinary(const struct Table* table, const void* key, size_t keylen) {
222 uint32_t hash = hash32(key, keylen, table->seed);
223 const struct TableList* list = _getConstList(table, hash);
224 TABLE_LOOKUP_START(HASH_TABLE_MEMCMP_COMPARATOR, list) {
225 return lookupResult->value;
226 } TABLE_LOOKUP_END;
227 return 0;
228}
229
230void HashTableInsert(struct Table* table, const char* key, void* value) {
231 uint32_t hash = hash32(key, strlen(key), table->seed);
232 struct TableList* list = _getList(table, hash);
233 if (table->size >= table->tableSize * REBALANCE_THRESHOLD) {
234 _rebalance(table);
235 hash = hash32(key, strlen(key), table->seed);
236 list = _getList(table, hash);
237 }
238 TABLE_LOOKUP_START(HASH_TABLE_STRNCMP_COMPARATOR, list) {
239 if (value != lookupResult->value) {
240 if (table->deinitializer) {
241 table->deinitializer(lookupResult->value);
242 }
243 lookupResult->value = value;
244 }
245 return;
246 } TABLE_LOOKUP_END;
247 list = _resizeAsNeeded(table, list, hash);
248 list->list[list->nEntries].key = hash;
249 list->list[list->nEntries].stringKey = strdup(key);
250 list->list[list->nEntries].keylen = strlen(key);
251 list->list[list->nEntries].value = value;
252 ++list->nEntries;
253 ++table->size;
254}
255
256void HashTableInsertBinary(struct Table* table, const void* key, size_t keylen, void* value) {
257 uint32_t hash = hash32(key, keylen, table->seed);
258 struct TableList* list = _getList(table, hash);
259 if (table->size >= table->tableSize * REBALANCE_THRESHOLD) {
260 _rebalance(table);
261 hash = hash32(key, keylen, table->seed);
262 list = _getList(table, hash);
263 }
264 TABLE_LOOKUP_START(HASH_TABLE_MEMCMP_COMPARATOR, list) {
265 if (value != lookupResult->value) {
266 if (table->deinitializer) {
267 table->deinitializer(lookupResult->value);
268 }
269 lookupResult->value = value;
270 }
271 return;
272 } TABLE_LOOKUP_END;
273 list = _resizeAsNeeded(table, list, hash);
274 list->list[list->nEntries].key = hash;
275 list->list[list->nEntries].stringKey = malloc(keylen);
276 memcpy(list->list[list->nEntries].stringKey, key, keylen);
277 list->list[list->nEntries].keylen = keylen;
278 list->list[list->nEntries].value = value;
279 ++list->nEntries;
280 ++table->size;
281}
282
283void HashTableInsertBinaryMoveKey(struct Table* table, void* key, size_t keylen, void* value) {
284 uint32_t hash = hash32(key, keylen, table->seed);
285 struct TableList* list = _getList(table, hash);
286 if (table->size >= table->tableSize * REBALANCE_THRESHOLD) {
287 _rebalance(table);
288 hash = hash32(key, keylen, table->seed);
289 list = _getList(table, hash);
290 }
291 TABLE_LOOKUP_START(HASH_TABLE_MEMCMP_COMPARATOR, list) {
292 if (value != lookupResult->value) {
293 if (table->deinitializer) {
294 table->deinitializer(lookupResult->value);
295 }
296 lookupResult->value = value;
297 }
298 return;
299 } TABLE_LOOKUP_END;
300 list = _resizeAsNeeded(table, list, hash);
301 list->list[list->nEntries].key = hash;
302 list->list[list->nEntries].stringKey = key;
303 list->list[list->nEntries].keylen = keylen;
304 list->list[list->nEntries].value = value;
305 ++list->nEntries;
306 ++table->size;
307}
308
309void HashTableRemove(struct Table* table, const char* key) {
310 uint32_t hash = hash32(key, strlen(key), table->seed);
311 struct TableList* list = _getList(table, hash);
312 TABLE_LOOKUP_START(HASH_TABLE_STRNCMP_COMPARATOR, list) {
313 _removeItemFromList(table, list, i); // TODO: Move i out of the macro
314 } TABLE_LOOKUP_END;
315}
316
317void HashTableRemoveBinary(struct Table* table, const void* key, size_t keylen) {
318 uint32_t hash = hash32(key, keylen, table->seed);
319 struct TableList* list = _getList(table, hash);
320 TABLE_LOOKUP_START(HASH_TABLE_MEMCMP_COMPARATOR, list) {
321 _removeItemFromList(table, list, i); // TODO: Move i out of the macro
322 } TABLE_LOOKUP_END;
323}
324
325void HashTableClear(struct Table* table) {
326 size_t i;
327 for (i = 0; i < table->tableSize; ++i) {
328 struct TableList* list = &table->table[i];
329 size_t j;
330 for (j = 0; j < list->nEntries; ++j) {
331 if (table->deinitializer) {
332 table->deinitializer(list->list[j].value);
333 }
334 free(list->list[j].stringKey);
335 }
336 free(list->list);
337 list->listSize = LIST_INITIAL_SIZE;
338 list->nEntries = 0;
339 list->list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
340 }
341}
342
343void HashTableEnumerate(const struct Table* table, void (*handler)(const char* key, void* value, void* user), void* user) {
344 size_t i;
345 for (i = 0; i < table->tableSize; ++i) {
346 const struct TableList* list = &table->table[i];
347 size_t j;
348 for (j = 0; j < list->nEntries; ++j) {
349 handler(list->list[j].stringKey, list->list[j].value, user);
350 }
351 }
352}
353
354void HashTableEnumerateBinary(const struct Table* table, void (*handler)(const char* key, size_t keylen, void* value, void* user), void* user) {
355 size_t i;
356 for (i = 0; i < table->tableSize; ++i) {
357 const struct TableList* list = &table->table[i];
358 size_t j;
359 for (j = 0; j < list->nEntries; ++j) {
360 handler(list->list[j].stringKey, list->list[j].keylen, list->list[j].value, user);
361 }
362 }
363}
364
365const char* HashTableSearch(const struct Table* table, bool (*predicate)(const char* key, const void* value, const void* user), const void* user) {
366 size_t i;
367 const char* result = NULL;
368 for (i = 0; i < table->tableSize; ++i) {
369 const struct TableList* list = &table->table[i];
370 size_t j;
371 for (j = 0; j < list->nEntries; ++j) {
372 if (predicate(list->list[j].stringKey, list->list[j].value, user)) {
373 return list->list[j].stringKey;
374 }
375 }
376 }
377 return result;
378}
379
380static bool HashTableRefEqual(const char* key, const void* value, const void* user) {
381 UNUSED(key);
382 return value == user;
383}
384
385const char* HashTableSearchPointer(const struct Table* table, const void* value) {
386 return HashTableSearch(table, HashTableRefEqual, value);
387}
388
389struct HashTableSearchParam {
390 const void* value;
391 size_t bytes;
392};
393
394static bool HashTableMemcmp(const char* key, const void* value, const void* user) {
395 UNUSED(key);
396 const struct HashTableSearchParam* ref = user;
397 return memcmp(value, ref->value, ref->bytes) == 0;
398}
399
400const char* HashTableSearchData(const struct Table* table, const void* value, const size_t bytes) {
401 struct HashTableSearchParam ref = { value, bytes };
402 return HashTableSearch(table, HashTableMemcmp, &ref);
403}
404
405static bool HashTableStrcmp(const char* key, const void* value, const void* user) {
406 UNUSED(key);
407 return strcmp(value, user) == 0;
408}
409
410const char* HashTableSearchString(const struct Table* table, const char* value) {
411 return HashTableSearch(table, HashTableStrcmp, value);
412}
413
414size_t HashTableSize(const struct Table* table) {
415 return table->size;
416}