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			table->deinitializer(lookupResult->value);
115			lookupResult->value = value;
116		}
117		return;
118	} TABLE_LOOKUP_END;
119	list = _resizeAsNeeded(table, list, key);
120	list->list[list->nEntries].key = key;
121	list->list[list->nEntries].stringKey = 0;
122	list->list[list->nEntries].value = value;
123	++list->nEntries;
124	++table->size;
125}
126
127void TableRemove(struct Table* table, uint32_t key) {
128	struct TableList* list;
129	TABLE_LOOKUP_START(TABLE_COMPARATOR, list, key) {
130		_removeItemFromList(table, list, i); // TODO: Move i out of the macro
131	} TABLE_LOOKUP_END;
132}
133
134void TableClear(struct Table* table) {
135	size_t i;
136	for (i = 0; i < table->tableSize; ++i) {
137		struct TableList* list = &table->table[i];
138		if (table->deinitializer) {
139			size_t j;
140			for (j = 0; j < list->nEntries; ++j) {
141				table->deinitializer(list->list[j].value);
142			}
143		}
144		free(list->list);
145		list->listSize = LIST_INITIAL_SIZE;
146		list->nEntries = 0;
147		list->list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
148	}
149}
150
151void TableEnumerate(const struct Table* table, void (handler(uint32_t key, void* value, void* user)), void* user) {
152	size_t i;
153	for (i = 0; i < table->tableSize; ++i) {
154		const struct TableList* list = &table->table[i];
155		size_t j;
156		for (j = 0; j < list->nEntries; ++j) {
157			handler(list->list[j].key, list->list[j].value, user);
158		}
159	}
160}
161
162size_t TableSize(const struct Table* table) {
163	return table->size;
164}
165
166void HashTableInit(struct Table* table, size_t initialSize, void (deinitializer(void*))) {
167	TableInit(table, initialSize, deinitializer);
168}
169
170void HashTableDeinit(struct Table* table) {
171	TableDeinit(table);
172}
173
174void* HashTableLookup(const struct Table* table, const char* key) {
175	uint32_t hash = hash32(key, strlen(key), 0);
176	const struct TableList* list;
177	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
178		return lookupResult->value;
179	} TABLE_LOOKUP_END;
180	return 0;
181}
182
183void HashTableInsert(struct Table* table, const char* key, void* value) {
184	uint32_t hash = hash32(key, strlen(key), 0);
185	struct TableList* list;
186	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
187		if (value != lookupResult->value) {
188			table->deinitializer(lookupResult->value);
189			lookupResult->value = value;
190		}
191		return;
192	} TABLE_LOOKUP_END;
193	list = _resizeAsNeeded(table, list, hash);
194	list->list[list->nEntries].key = hash;
195	list->list[list->nEntries].stringKey = strdup(key);
196	list->list[list->nEntries].keylen = strlen(key);
197	list->list[list->nEntries].value = value;
198	++list->nEntries;
199	++table->size;
200}
201
202void HashTableRemove(struct Table* table, const char* key) {
203	uint32_t hash = hash32(key, strlen(key), 0);
204	struct TableList* list;
205	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
206		_removeItemFromList(table, list, i); // TODO: Move i out of the macro
207	} TABLE_LOOKUP_END;
208}
209
210void HashTableClear(struct Table* table) {
211	size_t i;
212	for (i = 0; i < table->tableSize; ++i) {
213		struct TableList* list = &table->table[i];
214		size_t j;
215		for (j = 0; j < list->nEntries; ++j) {
216			if (table->deinitializer) {
217				table->deinitializer(list->list[j].value);
218			}
219			free(list->list[j].stringKey);
220		}
221		free(list->list);
222		list->listSize = LIST_INITIAL_SIZE;
223		list->nEntries = 0;
224		list->list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
225	}
226}
227
228void HashTableEnumerate(const struct Table* table, void (handler(const char* key, void* value, void* user)), void* user) {
229	size_t i;
230	for (i = 0; i < table->tableSize; ++i) {
231		const struct TableList* list = &table->table[i];
232		size_t j;
233		for (j = 0; j < list->nEntries; ++j) {
234			handler(list->list[j].stringKey, list->list[j].value, user);
235		}
236	}
237}
238
239size_t HashTableSize(const struct Table* table) {
240	return table->size;
241}