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 18using std::nothrow; 19 20struct HashTable::entry { 21 entry* next; 22 Hashable* value; 23}; 24 25 26HashTable::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 43HashTable::~HashTable() 44{ 45 MakeEmpty(fOwning); 46} 47 48 49void 50HashTable::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 72Hashable * 73HashTable::GetValue(Hashable& key) const 74{ 75 struct entry* entry = _GetHashEntry(key); 76 77 return entry != NULL ? entry->value : NULL; 78} 79 80 81bool 82HashTable::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 109Hashable * 110HashTable::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 145bool 146HashTable::_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 189struct HashTable::entry * 190HashTable::_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 206