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