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