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