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