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 18 unsigned int stringHash(const char *c) 19 { 20 int len = strlen(c); 21 22 return(*(int *)(c + len - 4)); // erstmal zum Testen 23 } 24 25 26 bool stringCompare(const char *a, const char *b) 27 { 28 return(!strcmp(a, b)); 29 } 30 31 32 // #pragma mark - Hashtable 33 34 35 Hashtable::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 59 Hashtable::~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 77 void Hashtable::SetHashFunction(uint32 (*func)(const void *)) 78 { 79 fHashFunc = func; 80 } 81 82 83 void Hashtable::SetCompareFunction(bool (*func)(const void *, const void *)) 84 { 85 fCompareFunc = func; 86 } 87 88 89 bool Hashtable::IsEmpty() const 90 { 91 return fCount == 0; 92 } 93 94 95 bool Hashtable::ContainsKey(const void *key) 96 { 97 return GetHashEntry(key) ? true : false; 98 } 99 100 101 void *Hashtable::GetValue(const void *key) 102 { 103 Entry *entry = GetHashEntry(key); 104 105 return entry ? entry->value : NULL; 106 } 107 108 109 bool 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 131 void *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 165 status_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 189 void Hashtable::Rewind() 190 { 191 fIteratorIndex = -1; 192 } 193 194 195 void 196 Hashtable::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 231 size_t 232 Hashtable::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 242 bool 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 277 Hashtable::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