1 /* 2 * Copyright 2007, Hugo Santos. All Rights Reserved. 3 * Distributed under the terms of the MIT License. 4 */ 5 #ifndef _KERNEL_UTIL_OPEN_HASH_TABLE_H 6 #define _KERNEL_UTIL_OPEN_HASH_TABLE_H 7 8 9 #include <OS.h> 10 #include <stdlib.h> 11 #include <string.h> 12 13 #ifdef _KERNEL_MODE 14 # include <KernelExport.h> 15 # include <util/kernel_cpp.h> 16 #endif 17 18 19 /*! 20 The Definition template must have four methods: `HashKey', `Hash', 21 `Compare' and `GetLink;. It must also define several types as shown in the 22 following example: 23 24 struct Foo { 25 int bar; 26 27 Foo* fNext; 28 }; 29 30 struct HashTableDefinition { 31 typedef int KeyType; 32 typedef Foo ValueType; 33 34 size_t HashKey(int key) const 35 { 36 return key >> 1; 37 } 38 39 size_t Hash(Foo* value) const 40 { 41 return HashKey(value->bar); 42 } 43 44 bool Compare(int key, Foo* value) const 45 { 46 return value->bar == key; 47 } 48 49 Foo*& GetLink(Foo* value) const 50 { 51 return value->fNext; 52 } 53 }; 54 */ 55 56 57 struct MallocAllocator { 58 void* Allocate(size_t size) const 59 { 60 return malloc(size); 61 } 62 63 void Free(void* memory) const 64 { 65 free(memory); 66 } 67 }; 68 69 70 template<typename Definition, bool AutoExpand = true, 71 bool CheckDuplicates = false, typename Allocator = MallocAllocator> 72 class BOpenHashTable { 73 public: 74 typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable; 75 typedef typename Definition::KeyType KeyType; 76 typedef typename Definition::ValueType ValueType; 77 78 static const size_t kMinimumSize = 8; 79 80 // All allocations are of power of 2 lengths. 81 82 // regrowth factor: 200 / 256 = 78.125% 83 // 50 / 256 = 19.53125% 84 85 BOpenHashTable() 86 : 87 fTableSize(0), 88 fItemCount(0), 89 fTable(NULL) 90 { 91 } 92 93 BOpenHashTable(const Definition& definition) 94 : 95 fDefinition(definition), 96 fTableSize(0), 97 fItemCount(0), 98 fTable(NULL) 99 { 100 } 101 102 BOpenHashTable(const Definition& definition, const Allocator& allocator) 103 : 104 fDefinition(definition), 105 fAllocator(allocator), 106 fTableSize(0), 107 fItemCount(0), 108 fTable(NULL) 109 { 110 } 111 112 ~BOpenHashTable() 113 { 114 fAllocator.Free(fTable); 115 } 116 117 status_t Init(size_t initialSize = kMinimumSize) 118 { 119 if (initialSize > 0 && !_Resize(initialSize)) 120 return B_NO_MEMORY; 121 return B_OK; 122 } 123 124 size_t TableSize() const 125 { 126 return fTableSize; 127 } 128 129 size_t CountElements() const 130 { 131 return fItemCount; 132 } 133 134 ValueType* Lookup(const KeyType& key) const 135 { 136 if (fTableSize == 0) 137 return NULL; 138 139 size_t index = fDefinition.HashKey(key) & (fTableSize - 1); 140 ValueType* slot = fTable[index]; 141 142 while (slot) { 143 if (fDefinition.Compare(key, slot)) 144 break; 145 slot = _Link(slot); 146 } 147 148 return slot; 149 } 150 151 status_t Insert(ValueType* value) 152 { 153 if (fTableSize == 0) { 154 if (!_Resize(kMinimumSize)) 155 return B_NO_MEMORY; 156 } else if (AutoExpand && fItemCount >= (fTableSize * 200 / 256)) 157 _Resize(fTableSize * 2); 158 159 InsertUnchecked(value); 160 return B_OK; 161 } 162 163 void InsertUnchecked(ValueType* value) 164 { 165 if (CheckDuplicates && _ExhaustiveSearch(value)) { 166 #ifdef _KERNEL_MODE 167 panic("Hash Table: value already in table."); 168 #else 169 debugger("Hash Table: value already in table."); 170 #endif 171 } 172 173 _Insert(fTable, fTableSize, value); 174 fItemCount++; 175 } 176 177 // TODO: a ValueType* Remove(const KeyType& key) method is missing 178 179 bool Remove(ValueType* value) 180 { 181 if (!RemoveUnchecked(value)) 182 return false; 183 184 if (AutoExpand && fTableSize > kMinimumSize 185 && fItemCount < (fTableSize * 50 / 256)) 186 _Resize(fTableSize / 2); 187 188 return true; 189 } 190 191 bool RemoveUnchecked(ValueType* value) 192 { 193 size_t index = fDefinition.Hash(value) & (fTableSize - 1); 194 ValueType* previous = NULL; 195 ValueType* slot = fTable[index]; 196 197 while (slot) { 198 ValueType* next = _Link(slot); 199 200 if (value == slot) { 201 if (previous) 202 _Link(previous) = next; 203 else 204 fTable[index] = next; 205 break; 206 } 207 208 previous = slot; 209 slot = next; 210 } 211 212 if (slot == NULL) 213 return false; 214 215 if (CheckDuplicates && _ExhaustiveSearch(value)) { 216 #ifdef _KERNEL_MODE 217 panic("Hash Table: duplicate detected."); 218 #else 219 debugger("Hash Table: duplicate detected."); 220 #endif 221 } 222 223 fItemCount--; 224 return true; 225 } 226 227 /*! Removes all elements from the hash table. No resizing happens. The 228 elements are not deleted. If \a returnElements is \c true, the method 229 returns all elements chained via their hash table link. 230 */ 231 ValueType* Clear(bool returnElements = false) 232 { 233 if (this->fItemCount == 0) 234 return NULL; 235 236 ValueType* result = NULL; 237 238 if (returnElements) { 239 ValueType** nextPointer = &result; 240 241 // iterate through all buckets 242 for (size_t i = 0; i < fTableSize; i++) { 243 ValueType* element = fTable[i]; 244 if (element != NULL) { 245 // add the bucket to the list 246 *nextPointer = element; 247 248 // update nextPointer to point to the fNext of the last 249 // element in the bucket 250 while (element != NULL) { 251 nextPointer = &_Link(element); 252 element = *nextPointer; 253 } 254 } 255 } 256 } 257 258 memset(this->fTable, 0, sizeof(ValueType*) * this->fTableSize); 259 260 return result; 261 } 262 263 /*! If the table needs resizing, the number of bytes for the required 264 allocation is returned. If no resizing is needed, 0 is returned. 265 */ 266 size_t ResizeNeeded() const 267 { 268 size_t size = fTableSize; 269 if (size == 0 || fItemCount >= (size * 200 / 256)) { 270 // grow table 271 if (size == 0) 272 size = kMinimumSize; 273 while (fItemCount >= size * 200 / 256) 274 size <<= 1; 275 } else if (size > kMinimumSize && fItemCount < size * 50 / 256) { 276 // shrink table 277 while (fItemCount < size * 50 / 256) 278 size >>= 1; 279 if (size < kMinimumSize) 280 size = kMinimumSize; 281 } 282 283 if (size == fTableSize) 284 return 0; 285 286 return size * sizeof(ValueType*); 287 } 288 289 /*! Resizes the table using the given allocation. The allocation must not 290 be \c NULL. It must be of size \a size, which must a value returned 291 earlier by ResizeNeeded(). If the size requirements have changed in the 292 meantime, the method free()s the given allocation and returns \c false, 293 unless \a force is \c true, in which case the supplied allocation is 294 used in any event. 295 Otherwise \c true is returned. 296 If \a oldTable is non-null and resizing is successful, the old table 297 will not be freed, but will be returned via this parameter instead. 298 */ 299 bool Resize(void* allocation, size_t size, bool force = false, 300 void** oldTable = NULL) 301 { 302 if (!force && size != ResizeNeeded()) { 303 fAllocator.Free(allocation); 304 return false; 305 } 306 307 _Resize((ValueType**)allocation, size / sizeof(ValueType*), oldTable); 308 return true; 309 } 310 311 class Iterator { 312 public: 313 Iterator(const HashTable* table) 314 : fTable(table) 315 { 316 Rewind(); 317 } 318 319 Iterator(const HashTable* table, size_t index, ValueType* value) 320 : fTable(table), fIndex(index), fNext(value) {} 321 322 bool HasNext() const { return fNext != NULL; } 323 324 ValueType* Next() 325 { 326 ValueType* current = fNext; 327 _GetNext(); 328 return current; 329 } 330 331 void Rewind() 332 { 333 // get the first one 334 fIndex = 0; 335 fNext = NULL; 336 _GetNext(); 337 } 338 339 protected: 340 Iterator() {} 341 342 void _GetNext() 343 { 344 if (fNext) 345 fNext = fTable->_Link(fNext); 346 347 while (fNext == NULL && fIndex < fTable->fTableSize) 348 fNext = fTable->fTable[fIndex++]; 349 } 350 351 const HashTable* fTable; 352 size_t fIndex; 353 ValueType* fNext; 354 }; 355 356 Iterator GetIterator() const 357 { 358 return Iterator(this); 359 } 360 361 Iterator GetIterator(const KeyType& key) const 362 { 363 if (fTableSize == 0) 364 return Iterator(this, fTableSize, NULL); 365 366 size_t index = fDefinition.HashKey(key) & (fTableSize - 1); 367 ValueType* slot = fTable[index]; 368 369 while (slot) { 370 if (fDefinition.Compare(key, slot)) 371 break; 372 slot = _Link(slot); 373 } 374 375 if (slot == NULL) 376 return Iterator(this, fTableSize, NULL); 377 378 return Iterator(this, index + 1, slot); 379 } 380 381 protected: 382 // for g++ 2.95 383 friend class Iterator; 384 385 void _Insert(ValueType** table, size_t tableSize, ValueType* value) 386 { 387 size_t index = fDefinition.Hash(value) & (tableSize - 1); 388 389 _Link(value) = table[index]; 390 table[index] = value; 391 } 392 393 bool _Resize(size_t newSize) 394 { 395 ValueType** newTable 396 = (ValueType**)fAllocator.Allocate(sizeof(ValueType*) * newSize); 397 if (newTable == NULL) 398 return false; 399 400 _Resize(newTable, newSize); 401 return true; 402 } 403 404 void _Resize(ValueType** newTable, size_t newSize, void** _oldTable = NULL) 405 { 406 for (size_t i = 0; i < newSize; i++) 407 newTable[i] = NULL; 408 409 if (fTable) { 410 for (size_t i = 0; i < fTableSize; i++) { 411 ValueType* bucket = fTable[i]; 412 while (bucket) { 413 ValueType* next = _Link(bucket); 414 _Insert(newTable, newSize, bucket); 415 bucket = next; 416 } 417 } 418 419 if (_oldTable != NULL) 420 *_oldTable = fTable; 421 else 422 fAllocator.Free(fTable); 423 } else if (_oldTable != NULL) 424 *_oldTable = NULL; 425 426 fTableSize = newSize; 427 fTable = newTable; 428 } 429 430 ValueType*& _Link(ValueType* bucket) const 431 { 432 return fDefinition.GetLink(bucket); 433 } 434 435 bool _ExhaustiveSearch(ValueType* value) const 436 { 437 for (size_t i = 0; i < fTableSize; i++) { 438 ValueType* bucket = fTable[i]; 439 while (bucket) { 440 if (bucket == value) 441 return true; 442 bucket = _Link(bucket); 443 } 444 } 445 446 return false; 447 } 448 449 Definition fDefinition; 450 Allocator fAllocator; 451 size_t fTableSize; 452 size_t fItemCount; 453 ValueType** fTable; 454 }; 455 456 #endif // _KERNEL_UTIL_OPEN_HASH_TABLE_H 457