src/servers/app/HashTable.cpp

   1 /*
   2  * Copyright 2005, Haiku.
   3  * Distributed under the terms of the MIT License.
   4  *
   5  * Authors:
   6  *              Axel Dörfler, axeld@pinc-software.de
   7  */
   8
   9
  10 #include "HashTable.h"
  11
  12 #include <new>
  13
  14 #include <stdlib.h>
  15 //#include <stdarg.h>
  16 #include <string.h>
  17
  18 using std::nothrow;
  19
  20 struct HashTable::entry {
  21         entry*          next;
  22         Hashable*       value;
  23 };
  24
  25
  26 HashTable::HashTable(bool owning, int32 capacity, float loadFactor)
  27         :
  28         fTable(NULL),
  29         fCount(0),
  30         fThreshold(0),
  31         fOwning(owning)
  32 {
  33         if (capacity < 10)
  34                 capacity = 10;
  35         if (loadFactor <= 0.3)
  36                 loadFactor = 0.3;
  37
  38         fLoadFactor = loadFactor;
  39         fCapacity = capacity;
  40 }
  41
  42
  43 HashTable::~HashTable()
  44 {
  45         MakeEmpty(fOwning);
  46 }
  47
  48
  49 void
  50 HashTable::MakeEmpty(bool deleteValues)
  51 {
  52         if (fTable == NULL)
  53                 return;
  54
  55         for (int32 index = fCapacity; --index >= 0;) {
  56                 struct entry *entry, *next;
  57
  58                 for (entry = fTable[index]; entry != NULL; entry = next) {
  59                         next = entry->next;
  60
  61                         if (deleteValues)
  62                                 delete entry->value;
  63                         delete entry;
  64                 }
  65         }
  66
  67         free(fTable);
  68         fTable = NULL;
  69 }
  70
  71
  72 Hashable *
  73 HashTable::GetValue(Hashable& key) const
  74 {
  75         struct entry* entry = _GetHashEntry(key);
  76
  77         return entry != NULL ? entry->value : NULL;
  78 }
  79
  80
  81 bool
  82 HashTable::AddItem(Hashable *value)
  83 {
  84         struct entry *entry = _GetHashEntry(*value);
  85         int32 hash = value->Hash();
  86         int32 index;
  87
  88         // already in hash?
  89         if (entry != NULL)
  90                 return true;
  91
  92         if (fCount >= fThreshold)
  93                 _Rehash();
  94
  95         index = hash % fCapacity;
  96
  97         entry = new (nothrow) HashTable::entry;
  98         if (entry == NULL)
  99                 return false;
 100
 101         entry->value = value;
 102         entry->next = fTable[index];
 103         fTable[index] = entry;
 104         fCount++;
 105         return true;
 106 }
 107
 108
 109 Hashable *
 110 HashTable::RemoveItem(Hashable& key)
 111 {
 112         struct entry* previous = NULL;
 113         struct entry* entry;
 114         uint32 hash;
 115         int32 index;
 116
 117         if (fTable == NULL)
 118                 return NULL;
 119
 120         hash = key.Hash();
 121         index = hash % fCapacity;
 122
 123         for (entry = fTable[index]; entry != NULL; entry = entry->next) {
 124                 if (entry->value->Hash() == hash && entry->value->CompareTo(key)) {
 125                         // found value in array
 126                         Hashable* value;
 127
 128                         if (previous)
 129                                 previous->next = entry->next;
 130                         else
 131                                 fTable[index] = entry->next;
 132
 133                         fCount--;
 134                         value = entry->value;
 135                         delete entry;
 136                         return value;
 137                 }
 138
 139                 previous = entry;
 140         }
 141         return NULL;
 142 }
 143
 144
 145 bool
 146 HashTable::_Rehash()
 147 {
 148         struct entry** newTable;
 149         int32 oldCapacity = fCapacity;
 150         int32 newCapacity, i;
 151
 152         if (fCount != 0)
 153                 newCapacity = oldCapacity * 2 + 1;
 154         else
 155                 newCapacity = fCapacity;
 156
 157         newTable = (struct entry **)malloc(newCapacity * sizeof(struct entry *));
 158         if (newTable == NULL)
 159                 return false;
 160
 161         memset(newTable, 0, newCapacity * sizeof(struct entry *));
 162
 163         if (fTable != NULL) {
 164                 // repopulate the entries into the new array
 165                 for (i = fCapacity; i-- > 0;) {
 166                         struct entry* entry;
 167                         struct entry* next;
 168
 169                         for (entry = fTable[i]; entry != NULL; entry = next) {
 170                                 next = entry->next;
 171
 172                                 int32 index = entry->value->Hash() % newCapacity;
 173                                 entry->next = newTable[index];
 174                                 newTable[index] = entry;
 175                         }
 176                 }
 177
 178                 free(fTable);
 179         }
 180
 181         fTable = newTable;
 182         fCapacity = newCapacity;
 183         fThreshold = int32(newCapacity * fLoadFactor);
 184
 185         return true;
 186 }
 187
 188
 189 struct HashTable::entry *
 190 HashTable::_GetHashEntry(Hashable& key) const
 191 {
 192         struct entry* entry;
 193         uint32 hash = key.Hash();
 194
 195         if (fTable == NULL)
 196                 return NULL;
 197
 198         for (entry = fTable[hash % fCapacity]; entry != NULL; entry = entry->next) {
 199                 if (entry->value->Hash() == hash && entry->value->CompareTo(key))
 200                         return entry;
 201         }
 202
 203         return NULL;
 204 }
 205