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