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_COMPARATOR(LIST, INDEX) LIST->list[(INDEX)].key == hash && strncmp(LIST->list[(INDEX)].stringKey, key, LIST->list[(INDEX)].keylen) == 0
 16
 17#define TABLE_LOOKUP_START(COMPARATOR, LIST, KEY) \
 18	uint32_t entry = (KEY) & (table->tableSize - 1); \
 19	LIST = &table->table[entry]; \
 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 struct TableList* _resizeAsNeeded(struct Table* table, struct TableList* list, uint32_t key) {
 45	UNUSED(table);
 46	UNUSED(key);
 47	// TODO: Expand table if needed
 48	if (list->nEntries + 1 == list->listSize) {
 49		list->listSize *= 2;
 50		list->list = realloc(list->list, list->listSize * sizeof(struct TableTuple));
 51	}
 52	return list;
 53}
 54
 55static void _removeItemFromList(struct Table* table, struct TableList* list, size_t item) {
 56	--list->nEntries;
 57	--table->size;
 58	free(list->list[item].stringKey);
 59	if (table->deinitializer) {
 60		table->deinitializer(list->list[item].value);
 61	}
 62	if (item != list->nEntries) {
 63		list->list[item] = list->list[list->nEntries];
 64	}
 65}
 66
 67void TableInit(struct Table* table, size_t initialSize, void (deinitializer(void*))) {
 68	if (initialSize < 2 || (initialSize & (initialSize - 1))) {
 69		initialSize = TABLE_INITIAL_SIZE;
 70	}
 71	table->tableSize = initialSize;
 72	table->table = calloc(table->tableSize, sizeof(struct TableList));
 73	table->size = 0;
 74	table->deinitializer = deinitializer;
 75
 76	size_t i;
 77	for (i = 0; i < table->tableSize; ++i) {
 78		table->table[i].listSize = LIST_INITIAL_SIZE;
 79		table->table[i].nEntries = 0;
 80		table->table[i].list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
 81	}
 82}
 83
 84void TableDeinit(struct Table* table) {
 85	size_t i;
 86	for (i = 0; i < table->tableSize; ++i) {
 87		struct TableList* list = &table->table[i];
 88		size_t j;
 89		for (j = 0; j < list->nEntries; ++j) {
 90			free(list->list[j].stringKey);
 91			if (table->deinitializer) {
 92				table->deinitializer(list->list[j].value);
 93			}
 94		}
 95		free(list->list);
 96	}
 97	free(table->table);
 98	table->table = 0;
 99	table->tableSize = 0;
100}
101
102void* TableLookup(const struct Table* table, uint32_t key) {
103	const struct TableList* list;
104	TABLE_LOOKUP_START(TABLE_COMPARATOR, list, key) {
105		return lookupResult->value;
106	} TABLE_LOOKUP_END;
107	return 0;
108}
109
110void TableInsert(struct Table* table, uint32_t key, void* value) {
111	struct TableList* list;
112	TABLE_LOOKUP_START(TABLE_COMPARATOR, list, key) {
113		if (value != lookupResult->value) {
114			if (table->deinitializer) {
115				table->deinitializer(lookupResult->value);
116			}
117			lookupResult->value = value;
118		}
119		return;
120	} TABLE_LOOKUP_END;
121	list = _resizeAsNeeded(table, list, key);
122	list->list[list->nEntries].key = key;
123	list->list[list->nEntries].stringKey = 0;
124	list->list[list->nEntries].value = value;
125	++list->nEntries;
126	++table->size;
127}
128
129void TableRemove(struct Table* table, uint32_t key) {
130	struct TableList* list;
131	TABLE_LOOKUP_START(TABLE_COMPARATOR, list, key) {
132		_removeItemFromList(table, list, i); // TODO: Move i out of the macro
133	} TABLE_LOOKUP_END;
134}
135
136void TableClear(struct Table* table) {
137	size_t i;
138	for (i = 0; i < table->tableSize; ++i) {
139		struct TableList* list = &table->table[i];
140		if (table->deinitializer) {
141			size_t j;
142			for (j = 0; j < list->nEntries; ++j) {
143				table->deinitializer(list->list[j].value);
144			}
145		}
146		free(list->list);
147		list->listSize = LIST_INITIAL_SIZE;
148		list->nEntries = 0;
149		list->list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
150	}
151}
152
153void TableEnumerate(const struct Table* table, void (handler(uint32_t key, void* value, void* user)), void* user) {
154	size_t i;
155	for (i = 0; i < table->tableSize; ++i) {
156		const struct TableList* list = &table->table[i];
157		size_t j;
158		for (j = 0; j < list->nEntries; ++j) {
159			handler(list->list[j].key, list->list[j].value, user);
160		}
161	}
162}
163
164size_t TableSize(const struct Table* table) {
165	return table->size;
166}
167
168void HashTableInit(struct Table* table, size_t initialSize, void (deinitializer(void*))) {
169	TableInit(table, initialSize, deinitializer);
170}
171
172void HashTableDeinit(struct Table* table) {
173	TableDeinit(table);
174}
175
176void* HashTableLookup(const struct Table* table, const char* key) {
177	uint32_t hash = hash32(key, strlen(key), 0);
178	const struct TableList* list;
179	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
180		return lookupResult->value;
181	} TABLE_LOOKUP_END;
182	return 0;
183}
184
185void HashTableInsert(struct Table* table, const char* key, void* value) {
186	uint32_t hash = hash32(key, strlen(key), 0);
187	struct TableList* list;
188	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
189		if (value != lookupResult->value) {
190			table->deinitializer(lookupResult->value);
191			lookupResult->value = value;
192		}
193		return;
194	} TABLE_LOOKUP_END;
195	list = _resizeAsNeeded(table, list, hash);
196	list->list[list->nEntries].key = hash;
197	list->list[list->nEntries].stringKey = strdup(key);
198	list->list[list->nEntries].keylen = strlen(key);
199	list->list[list->nEntries].value = value;
200	++list->nEntries;
201	++table->size;
202}
203
204void HashTableRemove(struct Table* table, const char* key) {
205	uint32_t hash = hash32(key, strlen(key), 0);
206	struct TableList* list;
207	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
208		_removeItemFromList(table, list, i); // TODO: Move i out of the macro
209	} TABLE_LOOKUP_END;
210}
211
212void HashTableClear(struct Table* table) {
213	size_t i;
214	for (i = 0; i < table->tableSize; ++i) {
215		struct TableList* list = &table->table[i];
216		size_t j;
217		for (j = 0; j < list->nEntries; ++j) {
218			if (table->deinitializer) {
219				table->deinitializer(list->list[j].value);
220			}
221			free(list->list[j].stringKey);
222		}
223		free(list->list);
224		list->listSize = LIST_INITIAL_SIZE;
225		list->nEntries = 0;
226		list->list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
227	}
228}
229
230void HashTableEnumerate(const struct Table* table, void (handler(const char* key, void* value, void* user)), void* user) {
231	size_t i;
232	for (i = 0; i < table->tableSize; ++i) {
233		const struct TableList* list = &table->table[i];
234		size_t j;
235		for (j = 0; j < list->nEntries; ++j) {
236			handler(list->list[j].stringKey, list->list[j].value, user);
237		}
238	}
239}
240
241size_t HashTableSize(const struct Table* table) {
242	return table->size;
243}