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