1/* Hashtable - a general purpose hash table
2**
3** Copyright 2001 pinc Software. All Rights Reserved.
4*/
5
6
7#include <stdlib.h>
8#include <stdarg.h>
9#include <string.h>
10
11#include "Hashtable.h"
12
13
14/************************** standard string hash functions **************************/
15
16
17unsigned int stringHash(const char *c)
18{
19	int len = strlen(c);
20
21	return(*(int *)(c + len - 4));  // erstmal zum Testen
22}
23
24
25bool stringCompare(const char *a, const char *b)
26{
27	return(!strcmp(a, b));
28}
29
30
31// #pragma mark - Hashtable
32
33
34Hashtable::Hashtable(int capacity, float loadFactor)
35	:
36	fIteratorIndex(-1)
37{
38	if (capacity < 0 || loadFactor <= 0)
39		return;
40
41	if (!capacity)
42		capacity = 1;
43
44	if (!(fTable = (struct Entry **)malloc(capacity * sizeof(void *))))
45		return;
46	memset(fTable,0,capacity * sizeof(void *));
47
48	fThreshold = (int)(capacity * loadFactor);
49	fModCount = 0;
50	fLoadFactor = loadFactor;
51	fCapacity = capacity;
52
53	fHashFunc = (uint32 (*)(const void *))stringHash;
54	fCompareFunc = (bool (*)(const void *, const void *))stringCompare;
55}
56
57
58Hashtable::~Hashtable()
59{
60	struct Entry **table = fTable;
61
62	for(int32 index = fCapacity;--index >= 0;)
63	{
64		struct Entry *entry,*next;
65
66		for(entry = table[index];entry;entry = next)
67		{
68			next = entry->next;
69			delete entry;
70		}
71	}
72	free(table);
73}
74
75
76void Hashtable::SetHashFunction(uint32 (*func)(const void *))
77{
78	fHashFunc = func;
79}
80
81
82void Hashtable::SetCompareFunction(bool (*func)(const void *, const void *))
83{
84	fCompareFunc = func;
85}
86
87
88bool Hashtable::IsEmpty() const
89{
90	return fCount == 0;
91}
92
93
94bool Hashtable::ContainsKey(const void *key)
95{
96	return GetHashEntry(key) ? true : false;
97}
98
99
100void *Hashtable::GetValue(const void *key)
101{
102	Entry *entry = GetHashEntry(key);
103
104	return entry ? entry->value : NULL;
105}
106
107
108bool Hashtable::Put(const void *key, void *value)
109{
110	Entry *entry = GetHashEntry(key);
111	int hash = fHashFunc(key);
112	int index;
113
114	if (entry)
115		return true;
116
117	fModCount++;
118	if (fCount >= fThreshold)
119		Rehash();
120
121	index = hash % fCapacity;
122
123	fTable[index] = new Entry(fTable[index], key, value);
124	fCount++;
125
126	return true;
127}
128
129
130void *Hashtable::Remove(const void *key)
131{
132	Entry **table,*entry,*prev;
133	uint32 hash,(*func)(const void *);
134	int32 index;
135
136	table = fTable;
137	hash = (func = fHashFunc)(key);
138	index = hash % fCapacity;
139
140	for(entry = table[index],prev = NULL;entry;entry = entry->next)
141	{
142		if ((func(entry->key) == hash) && fCompareFunc(entry->key,key))
143		{
144			void *value;
145
146			fModCount++;
147			if (prev)
148				prev->next = entry->next;
149			else
150				table[index] = entry->next;
151
152			fCount--;
153			value = entry->value;
154			delete entry;
155
156			return value;
157		}
158		prev = entry;
159	}
160	return NULL;
161}
162
163
164status_t Hashtable::GetNextEntry(void **value)
165{
166	if (fIteratorIndex == -1)
167	{
168		fIteratorIndex = 0;
169		fIteratorEntry = fTable[0];
170	}
171	else if (fIteratorEntry)
172		fIteratorEntry = fIteratorEntry->next;
173
174	// get next filled slot
175	while (!fIteratorEntry && fIteratorIndex + 1 < fCapacity)
176		fIteratorEntry = fTable[++fIteratorIndex];
177
178	if (fIteratorEntry)
179	{
180		*value = fIteratorEntry->value;
181		return B_OK;
182	}
183
184	return B_ENTRY_NOT_FOUND;
185}
186
187
188void Hashtable::Rewind()
189{
190	fIteratorIndex = -1;
191}
192
193
194void
195Hashtable::MakeEmpty(int8 keyMode,int8 valueMode)
196{
197	fModCount++;
198
199	for (int32 index = fCapacity; --index >= 0;) {
200		Entry *entry, *next;
201
202		for (entry = fTable[index]; entry; entry = next) {
203			switch (keyMode) {
204				case HASH_EMPTY_DELETE:
205					// TODO: destructors are not called!
206					delete (void*)entry->key;
207					break;
208				case HASH_EMPTY_FREE:
209					free((void*)entry->key);
210					break;
211			}
212			switch (valueMode) {
213				case HASH_EMPTY_DELETE:
214					// TODO: destructors are not called!
215					delete entry->value;
216					break;
217				case HASH_EMPTY_FREE:
218					free(entry->value);
219					break;
220			}
221			next = entry->next;
222			delete entry;
223		}
224		fTable[index] = NULL;
225	}
226	fCount = 0;
227}
228
229
230size_t
231Hashtable::Size() const
232{
233	return fCount;
234}
235
236
237/** The hash table will be doubled in size, and rebuild.
238 *  @return true on success
239 */
240
241bool Hashtable::Rehash()
242{
243	uint32 (*hashCode)(const void *) = fHashFunc;
244	struct Entry **oldTable = fTable,**newtable;
245	int oldCapacity = fCapacity;
246	int newCapacity,i;
247
248	newCapacity = oldCapacity * 2 + 1;
249	if (!(newtable = (struct Entry **)malloc(newCapacity * sizeof(struct Entry *))))
250		return false;
251	memset(newtable,0,newCapacity*sizeof(struct Entry *));
252
253	fModCount++;
254	fThreshold = (int)(newCapacity * fLoadFactor);
255	fTable = newtable;
256	fCapacity = newCapacity;
257
258	for (i = oldCapacity;i-- > 0;) {
259		Entry *oldEntry,*entry = NULL;
260		int index;
261
262		for (oldEntry = oldTable[i];oldEntry;) {
263			entry = oldEntry;  oldEntry = oldEntry->next;
264
265			index = hashCode(entry->key) % newCapacity;
266			entry->next = newtable[index];
267			newtable[index] = entry;
268		}
269	}
270	free(oldTable);
271
272	return true;
273}
274
275
276Hashtable::Entry *Hashtable::GetHashEntry(const void *key)
277{
278	Entry **table,*entry;
279	uint32 hash,(*func)(const void *);
280
281	table = fTable;
282	hash = (func = fHashFunc)(key);
283
284	for(entry = table[hash % fCapacity];entry;entry = entry->next)
285	{
286		if ((func(entry->key) == hash) && fCompareFunc(entry->key,key))
287			return entry;
288	}
289	return NULL;
290}
291
292