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 "table.h"
  7
  8#include "util/hash.h"
  9#include "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	free(list->list[item].stringKey);
 58	if (table->deinitializer) {
 59		table->deinitializer(list->list[item].value);
 60	}
 61	if (item != list->nEntries) {
 62		list->list[item] = list->list[list->nEntries];
 63	}
 64}
 65
 66void TableInit(struct Table* table, size_t initialSize, void (deinitializer(void*))) {
 67	if (initialSize < 2 || (initialSize & (initialSize - 1))) {
 68		initialSize = TABLE_INITIAL_SIZE;
 69	}
 70	table->tableSize = initialSize;
 71	table->table = calloc(table->tableSize, sizeof(struct TableList));
 72	table->deinitializer = deinitializer;
 73
 74	size_t i;
 75	for (i = 0; i < table->tableSize; ++i) {
 76		table->table[i].listSize = LIST_INITIAL_SIZE;
 77		table->table[i].nEntries = 0;
 78		table->table[i].list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
 79	}
 80}
 81
 82void TableDeinit(struct Table* table) {
 83	size_t i;
 84	for (i = 0; i < table->tableSize; ++i) {
 85		struct TableList* list = &table->table[i];
 86		size_t j;
 87		for (j = 0; j < list->nEntries; ++j) {
 88			free(list->list[j].stringKey);
 89			if (table->deinitializer) {
 90				table->deinitializer(list->list[j].value);
 91			}
 92		}
 93		free(list->list);
 94	}
 95	free(table->table);
 96	table->table = 0;
 97	table->tableSize = 0;
 98}
 99
100void* TableLookup(const struct Table* table, uint32_t key) {
101	const struct TableList* list;
102	TABLE_LOOKUP_START(TABLE_COMPARATOR, list, key) {
103		return lookupResult->value;
104	} TABLE_LOOKUP_END;
105	return 0;
106}
107
108void TableInsert(struct Table* table, uint32_t key, void* value) {
109	struct TableList* list;
110	TABLE_LOOKUP_START(TABLE_COMPARATOR, list, key) {
111		if (value != lookupResult->value) {
112			table->deinitializer(lookupResult->value);
113			lookupResult->value = value;
114		}
115		return;
116	} TABLE_LOOKUP_END;
117	list = _resizeAsNeeded(table, list, key);
118	list->list[list->nEntries].key = key;
119	list->list[list->nEntries].stringKey = 0;
120	list->list[list->nEntries].value = value;
121	++list->nEntries;
122}
123
124void TableRemove(struct Table* table, uint32_t key) {
125	struct TableList* list;
126	TABLE_LOOKUP_START(TABLE_COMPARATOR, list, key) {
127		_removeItemFromList(table, list, i); // TODO: Move i out of the macro
128	} TABLE_LOOKUP_END;
129}
130
131void TableClear(struct Table* table) {
132	size_t i;
133	for (i = 0; i < table->tableSize; ++i) {
134		struct TableList* list = &table->table[i];
135		if (table->deinitializer) {
136			size_t j;
137			for (j = 0; j < list->nEntries; ++j) {
138				table->deinitializer(list->list[j].value);
139			}
140		}
141		free(list->list);
142		list->listSize = LIST_INITIAL_SIZE;
143		list->nEntries = 0;
144		list->list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
145	}
146}
147
148void TableEnumerate(const struct Table* table, void (handler(uint32_t key, void* value, void* user)), void* user) {
149	size_t i;
150	for (i = 0; i < table->tableSize; ++i) {
151		const struct TableList* list = &table->table[i];
152		size_t j;
153		for (j = 0; j < list->nEntries; ++j) {
154			handler(list->list[j].key, list->list[j].value, user);
155		}
156	}
157}
158
159void* HashTableLookup(const struct Table* table, const char* key) {
160	uint32_t hash = hash32(key, strlen(key), 0);
161	const struct TableList* list;
162	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
163		return lookupResult->value;
164	} TABLE_LOOKUP_END;
165	return 0;
166}
167
168void HashTableInsert(struct Table* table, const char* key, void* value) {
169	uint32_t hash = hash32(key, strlen(key), 0);
170	struct TableList* list;
171	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
172		if (value != lookupResult->value) {
173			table->deinitializer(lookupResult->value);
174			lookupResult->value = value;
175		}
176		return;
177	} TABLE_LOOKUP_END;
178	list = _resizeAsNeeded(table, list, hash);
179	list->list[list->nEntries].key = hash;
180	list->list[list->nEntries].stringKey = strdup(key);
181	list->list[list->nEntries].keylen = strlen(key);
182	list->list[list->nEntries].value = value;
183	++list->nEntries;
184}
185
186void HashTableRemove(struct Table* table, const char* key) {
187	uint32_t hash = hash32(key, strlen(key), 0);
188	struct TableList* list;
189	TABLE_LOOKUP_START(HASH_TABLE_COMPARATOR, list, hash) {
190		_removeItemFromList(table, list, i); // TODO: Move i out of the macro
191	} TABLE_LOOKUP_END;
192}
193
194void HashTableClear(struct Table* table) {
195	size_t i;
196	for (i = 0; i < table->tableSize; ++i) {
197		struct TableList* list = &table->table[i];
198		size_t j;
199		for (j = 0; j < list->nEntries; ++j) {
200			if (table->deinitializer) {
201				table->deinitializer(list->list[j].value);
202			}
203			free(list->list[j].stringKey);
204		}
205		free(list->list);
206		list->listSize = LIST_INITIAL_SIZE;
207		list->nEntries = 0;
208		list->list = calloc(LIST_INITIAL_SIZE, sizeof(struct TableTuple));
209	}
210}
211
212void HashTableEnumerate(const struct Table* table, void (handler(const char* key, void* value, void* user)), void* user) {
213	size_t i;
214	for (i = 0; i < table->tableSize; ++i) {
215		const struct TableList* list = &table->table[i];
216		size_t j;
217		for (j = 0; j < list->nEntries; ++j) {
218			handler(list->list[j].stringKey, list->list[j].value, user);
219		}
220	}
221}