src/bin/bfs_tools/lib/Hashtable.cpp

   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