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