1/* Generic hash table
2**
3** Copyright 2001, Travis Geiselbrecht. All rights reserved.
4** Distributed under the terms of the NewOS License.
5*/
6
7#include "hash.h"
8
9#include <stdlib.h>
10
11#include "fssh_errors.h"
12#include "fssh_kernel_export.h"
13
14
15#undef TRACE
16#define TRACE_HASH 0
17#if TRACE_HASH
18#	define TRACE(x) fssh_dprintf x
19#else
20#	define TRACE(x) ;
21#endif
22
23#undef ASSERT
24#define ASSERT(x)
25
26
27namespace FSShell {
28
29
30// TODO: the hashtable is not expanded when necessary (no load factor, nothing)
31//		resizing should be optional, though, in case the hash is used at times
32//		that forbid resizing.
33
34struct hash_table {
35	struct		hash_element **table;
36	int			next_ptr_offset;
37	uint32_t	table_size;
38	int			num_elements;
39	int			flags;
40	int			(*compare_func)(void *e, const void *key);
41	uint32_t	(*hash_func)(void *e, const void *key, uint32_t range);
42};
43
44// XXX gross hack
45#define NEXT_ADDR(t, e) ((void *)(((unsigned long)(e)) + (t)->next_ptr_offset))
46#define NEXT(t, e) ((void *)(*(unsigned long *)NEXT_ADDR(t, e)))
47#define PUT_IN_NEXT(t, e, val) (*(unsigned long *)NEXT_ADDR(t, e) = (long)(val))
48
49
50static inline void *
51next_element(hash_table *table, void *element)
52{
53	// ToDo: should we use this instead of the NEXT() macro?
54	return (void *)(*(unsigned long *)NEXT_ADDR(table, element));
55}
56
57
58struct hash_table *
59hash_init(uint32_t table_size, int next_ptr_offset,
60	int compare_func(void *e, const void *key),
61	uint32_t hash_func(void *e, const void *key, uint32_t range))
62{
63	struct hash_table *t;
64	unsigned int i;
65
66	if (compare_func == NULL || hash_func == NULL) {
67		fssh_dprintf("hash_init() called with NULL function pointer\n");
68		return NULL;
69	}
70
71	t = (struct hash_table *)malloc(sizeof(struct hash_table));
72	if (t == NULL)
73		return NULL;
74
75	t->table = (struct hash_element **)malloc(sizeof(void *) * table_size);
76	if (t->table == NULL) {
77		free(t);
78		return NULL;
79	}
80
81	for (i = 0; i < table_size; i++)
82		t->table[i] = NULL;
83
84	t->table_size = table_size;
85	t->next_ptr_offset = next_ptr_offset;
86	t->flags = 0;
87	t->num_elements = 0;
88	t->compare_func = compare_func;
89	t->hash_func = hash_func;
90
91	TRACE(("hash_init: created table %p, next_ptr_offset %d, compare_func %p, hash_func %p\n",
92		t, next_ptr_offset, compare_func, hash_func));
93
94	return t;
95}
96
97
98int
99hash_uninit(struct hash_table *table)
100{
101	ASSERT(table->num_elements == 0);
102
103	free(table->table);
104	free(table);
105
106	return 0;
107}
108
109
110fssh_status_t
111hash_insert(struct hash_table *table, void *element)
112{
113	uint32_t hash;
114
115	ASSERT(table != NULL && element != NULL);
116	TRACE(("hash_insert: table 0x%x, element 0x%x\n", table, element));
117
118	hash = table->hash_func(element, NULL, table->table_size);
119	PUT_IN_NEXT(table, element, table->table[hash]);
120	table->table[hash] = (struct hash_element *)element;
121	table->num_elements++;
122
123	// ToDo: resize hash table if it's grown too much!
124
125	return FSSH_B_OK;
126}
127
128
129fssh_status_t
130hash_remove(struct hash_table *table, void *_element)
131{
132	uint32_t hash = table->hash_func(_element, NULL, table->table_size);
133	void *element, *lastElement = NULL;
134
135	for (element = table->table[hash]; element != NULL;
136			lastElement = element, element = NEXT(table, element)) {
137		if (element == _element) {
138			if (lastElement != NULL) {
139				// connect the previous entry with the next one
140				PUT_IN_NEXT(table, lastElement, NEXT(table, element));
141			} else
142				table->table[hash] = (struct hash_element *)NEXT(table, element);
143			table->num_elements--;
144
145			return FSSH_B_OK;
146		}
147	}
148
149	return FSSH_B_ERROR;
150}
151
152
153void
154hash_remove_current(struct hash_table *table, struct hash_iterator *iterator)
155{
156	uint32_t index = iterator->bucket;
157	void *element;
158
159	if (iterator->current == NULL)
160		fssh_panic("hash_remove_current() called too early.");
161
162	for (element = table->table[index]; index < table->table_size; index++) {
163		void *lastElement = NULL;
164
165		while (element != NULL) {
166			if (element == iterator->current) {
167				iterator->current = lastElement;
168
169				if (lastElement != NULL) {
170					// connect the previous entry with the next one
171					PUT_IN_NEXT(table, lastElement, NEXT(table, element));
172				} else {
173					table->table[index] = (struct hash_element *)NEXT(table,
174						element);
175				}
176
177				table->num_elements--;
178				return;
179			}
180
181			element = NEXT(table, element);
182		}
183	}
184}
185
186
187void *
188hash_remove_first(struct hash_table *table, uint32_t *_cookie)
189{
190	uint32_t index;
191
192	for (index = _cookie ? *_cookie : 0; index < table->table_size; index++) {
193		void *element = table->table[index];
194		if (element != NULL) {
195			// remove the first element we find
196			table->table[index] = (struct hash_element *)NEXT(table, element);
197			table->num_elements--;
198			if (_cookie)
199				*_cookie = index;
200			return element;
201		}
202	}
203
204	return NULL;
205}
206
207
208void *
209hash_find(struct hash_table *table, void *searchedElement)
210{
211	uint32_t hash = table->hash_func(searchedElement, NULL, table->table_size);
212	void *element;
213
214	for (element = table->table[hash]; element != NULL; element = NEXT(table, element)) {
215		if (element == searchedElement)
216			return element;
217	}
218
219	return NULL;
220}
221
222
223void *
224hash_lookup(struct hash_table *table, const void *key)
225{
226	uint32_t hash = table->hash_func(NULL, key, table->table_size);
227	void *element;
228
229	for (element = table->table[hash]; element != NULL; element = NEXT(table, element)) {
230		if (table->compare_func(element, key) == 0)
231			return element;
232	}
233
234	return NULL;
235}
236
237
238struct hash_iterator *
239hash_open(struct hash_table *table, struct hash_iterator *iterator)
240{
241	if (iterator == NULL) {
242		iterator = (struct hash_iterator *)malloc(sizeof(struct hash_iterator));
243		if (iterator == NULL)
244			return NULL;
245	}
246
247	hash_rewind(table, iterator);
248
249	return iterator;
250}
251
252
253void
254hash_close(struct hash_table *table, struct hash_iterator *iterator, bool freeIterator)
255{
256	if (freeIterator)
257		free(iterator);
258}
259
260
261void
262hash_rewind(struct hash_table *table, struct hash_iterator *iterator)
263{
264	iterator->current = NULL;
265	iterator->bucket = -1;
266}
267
268
269void *
270hash_next(struct hash_table *table, struct hash_iterator *iterator)
271{
272	uint32_t index;
273
274restart:
275	if (iterator->current == NULL) {
276		// get next bucket
277		for (index = (uint32_t)(iterator->bucket + 1); index < table->table_size; index++) {
278			if (table->table[index]) {
279				iterator->bucket = index;
280				iterator->current = table->table[index];
281				break;
282			}
283		}
284	} else {
285		iterator->current = NEXT(table, iterator->current);
286		if (!iterator->current)
287			goto restart;
288	}
289
290	return iterator->current;
291}
292
293
294uint32_t
295hash_hash_string(const char *string)
296{
297	uint32_t hash = 0;
298	char c;
299
300	// we assume hash to be at least 32 bits
301	while ((c = *string++) != 0) {
302		hash ^= hash >> 28;
303		hash <<= 4;
304		hash ^= c;
305	}
306
307	return hash;
308}
309
310}	// namespace FSShell
311