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			if (table->deinitializer) {
191				table->deinitializer(lookupResult->value);
192			}
193			lookupResult->value = value;
194		}
195		return;
196	} TABLE_LOOKUP_END;
197	list = _resizeAsNeeded(table, list, hash);
198	list->list[list->nEntries].key = hash;
199	list->list[list->nEntries].stringKey = strdup(key);
200	list->list[list->nEntries].keylen = strlen(key);
201	list->list[list->nEntries].value = value;
202	++list->nEntries;
203	++table->size;
204}
205
206void HashTableRemove(struct Table* table, const char* key) {
207	uint32_t hash = hash32(key, strlen(key), 0);
208	struct TableList* list;
209	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
210		_removeItemFromList(table, list, i); // TODO: Move i out of the macro
211	} TABLE_LOOKUP_END;
212}
213
214void HashTableClear(struct Table* table) {
215	size_t i;
216	for (i = 0; i < table->tableSize; ++i) {
217		struct TableList* list = &table->table[i];
218		size_t j;
219		for (j = 0; j < list->nEntries; ++j) {
220			if (table->deinitializer) {
221				table->deinitializer(list->list[j].value);
222			}
223			free(list->list[j].stringKey);
224		}
225		free(list->list);
226		list->listSize = LIST_INITIAL_SIZE;
227		list->nEntries = 0;
228		list->list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
229	}
230}
231
232void HashTableEnumerate(const struct Table* table, void (handler(const char* key, void* value, void* user)), void* user) {
233	size_t i;
234	for (i = 0; i < table->tableSize; ++i) {
235		const struct TableList* list = &table->table[i];
236		size_t j;
237		for (j = 0; j < list->nEntries; ++j) {
238			handler(list->list[j].stringKey, list->list[j].value, user);
239		}
240	}
241}
242
243size_t HashTableSize(const struct Table* table) {
244	return table->size;
245}