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