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