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 bool IsEmpty() const 130 { 131 return fItemCount == 0; 132 } 133 134 size_t CountElements() const 135 { 136 return fItemCount; 137 } 138 139 ValueType* Lookup(const KeyType& key) const 140 { 141 if (fTableSize == 0) 142 return NULL; 143 144 size_t index = fDefinition.HashKey(key) & (fTableSize - 1); 145 ValueType* slot = fTable[index]; 146 147 while (slot) { 148 if (fDefinition.Compare(key, slot)) 149 break; 150 slot = _Link(slot); 151 } 152 153 return slot; 154 } 155 156 status_t Insert(ValueType* value) 157 { 158 if (fTableSize == 0) { 159 if (!_Resize(kMinimumSize)) 160 return B_NO_MEMORY; 161 } else if (AutoExpand && fItemCount >= (fTableSize * 200 / 256)) 162 _Resize(fTableSize * 2); 163 164 InsertUnchecked(value); 165 return B_OK; 166 } 167 168 void InsertUnchecked(ValueType* value) 169 { 170 if (CheckDuplicates && _ExhaustiveSearch(value)) { 171 #ifdef _KERNEL_MODE 172 panic("Hash Table: value already in table."); 173 #else 174 debugger("Hash Table: value already in table."); 175 #endif 176 } 177 178 _Insert(fTable, fTableSize, value); 179 fItemCount++; 180 } 181 182 // TODO: a ValueType* Remove(const KeyType& key) method is missing 183 184 bool Remove(ValueType* value) 185 { 186 if (!RemoveUnchecked(value)) 187 return false; 188 189 if (AutoExpand && fTableSize > kMinimumSize 190 && fItemCount < (fTableSize * 50 / 256)) 191 _Resize(fTableSize / 2); 192 193 return true; 194 } 195 196 bool RemoveUnchecked(ValueType* value) 197 { 198 size_t index = fDefinition.Hash(value) & (fTableSize - 1); 199 ValueType* previous = NULL; 200 ValueType* slot = fTable[index]; 201 202 while (slot) { 203 ValueType* next = _Link(slot); 204 205 if (value == slot) { 206 if (previous) 207 _Link(previous) = next; 208 else 209 fTable[index] = next; 210 break; 211 } 212 213 previous = slot; 214 slot = next; 215 } 216 217 if (slot == NULL) 218 return false; 219 220 if (CheckDuplicates && _ExhaustiveSearch(value)) { 221 #ifdef _KERNEL_MODE 222 panic("Hash Table: duplicate detected."); 223 #else 224 debugger("Hash Table: duplicate detected."); 225 #endif 226 } 227 228 fItemCount--; 229 return true; 230 } 231 232 /*! Removes all elements from the hash table. No resizing happens. The 233 elements are not deleted. If \a returnElements is \c true, the method 234 returns all elements chained via their hash table link. 235 */ 236 ValueType* Clear(bool returnElements = false) 237 { 238 if (fItemCount == 0) 239 return NULL; 240 241 ValueType* result = NULL; 242 243 if (returnElements) { 244 ValueType** nextPointer = &result; 245 246 // iterate through all buckets 247 for (size_t i = 0; i < fTableSize; i++) { 248 ValueType* element = fTable[i]; 249 if (element != NULL) { 250 // add the bucket to the list 251 *nextPointer = element; 252 253 // update nextPointer to point to the fNext of the last 254 // element in the bucket 255 while (element != NULL) { 256 nextPointer = &_Link(element); 257 element = *nextPointer; 258 } 259 } 260 } 261 } 262 263 memset(this->fTable, 0, sizeof(ValueType*) * this->fTableSize); 264 fItemCount = 0; 265 266 return result; 267 } 268 269 /*! If the table needs resizing, the number of bytes for the required 270 allocation is returned. If no resizing is needed, 0 is returned. 271 */ 272 size_t ResizeNeeded() const 273 { 274 size_t size = fTableSize; 275 if (size == 0 || fItemCount >= (size * 200 / 256)) { 276 // grow table 277 if (size == 0) 278 size = kMinimumSize; 279 while (fItemCount >= size * 200 / 256) 280 size <<= 1; 281 } else if (size > kMinimumSize && fItemCount < size * 50 / 256) { 282 // shrink table 283 while (fItemCount < size * 50 / 256) 284 size >>= 1; 285 if (size < kMinimumSize) 286 size = kMinimumSize; 287 } 288 289 if (size == fTableSize) 290 return 0; 291 292 return size * sizeof(ValueType*); 293 } 294 295 /*! Resizes the table using the given allocation. The allocation must not 296 be \c NULL. It must be of size \a size, which must a value returned 297 earlier by ResizeNeeded(). If the size requirements have changed in the 298 meantime, the method free()s the given allocation and returns \c false, 299 unless \a force is \c true, in which case the supplied allocation is 300 used in any event. 301 Otherwise \c true is returned. 302 If \a oldTable is non-null and resizing is successful, the old table 303 will not be freed, but will be returned via this parameter instead. 304 */ 305 bool Resize(void* allocation, size_t size, bool force = false, 306 void** oldTable = NULL) 307 { 308 if (!force && size != ResizeNeeded()) { 309 fAllocator.Free(allocation); 310 return false; 311 } 312 313 _Resize((ValueType**)allocation, size / sizeof(ValueType*), oldTable); 314 return true; 315 } 316 317 class Iterator { 318 public: 319 Iterator(const HashTable* table) 320 : fTable(table) 321 { 322 Rewind(); 323 } 324 325 Iterator(const HashTable* table, size_t index, ValueType* value) 326 : fTable(table), fIndex(index), fNext(value) {} 327 328 bool HasNext() const { return fNext != NULL; } 329 330 ValueType* Next() 331 { 332 ValueType* current = fNext; 333 _GetNext(); 334 return current; 335 } 336 337 void Rewind() 338 { 339 // get the first one 340 fIndex = 0; 341 fNext = NULL; 342 _GetNext(); 343 } 344 345 protected: 346 Iterator() {} 347 348 void _GetNext() 349 { 350 if (fNext) 351 fNext = fTable->_Link(fNext); 352 353 while (fNext == NULL && fIndex < fTable->fTableSize) 354 fNext = fTable->fTable[fIndex++]; 355 } 356 357 const HashTable* fTable; 358 size_t fIndex; 359 ValueType* fNext; 360 }; 361 362 Iterator GetIterator() const 363 { 364 return Iterator(this); 365 } 366 367 Iterator GetIterator(const KeyType& key) const 368 { 369 if (fTableSize == 0) 370 return Iterator(this, fTableSize, NULL); 371 372 size_t index = fDefinition.HashKey(key) & (fTableSize - 1); 373 ValueType* slot = fTable[index]; 374 375 while (slot) { 376 if (fDefinition.Compare(key, slot)) 377 break; 378 slot = _Link(slot); 379 } 380 381 if (slot == NULL) 382 return Iterator(this, fTableSize, NULL); 383 384 return Iterator(this, index + 1, slot); 385 } 386 387 protected: 388 // for g++ 2.95 389 friend class Iterator; 390 391 void _Insert(ValueType** table, size_t tableSize, ValueType* value) 392 { 393 size_t index = fDefinition.Hash(value) & (tableSize - 1); 394 395 _Link(value) = table[index]; 396 table[index] = value; 397 } 398 399 bool _Resize(size_t newSize) 400 { 401 ValueType** newTable 402 = (ValueType**)fAllocator.Allocate(sizeof(ValueType*) * newSize); 403 if (newTable == NULL) 404 return false; 405 406 _Resize(newTable, newSize); 407 return true; 408 } 409 410 void _Resize(ValueType** newTable, size_t newSize, void** _oldTable = NULL) 411 { 412 for (size_t i = 0; i < newSize; i++) 413 newTable[i] = NULL; 414 415 if (fTable) { 416 for (size_t i = 0; i < fTableSize; i++) { 417 ValueType* bucket = fTable[i]; 418 while (bucket) { 419 ValueType* next = _Link(bucket); 420 _Insert(newTable, newSize, bucket); 421 bucket = next; 422 } 423 } 424 425 if (_oldTable != NULL) 426 *_oldTable = fTable; 427 else 428 fAllocator.Free(fTable); 429 } else if (_oldTable != NULL) 430 *_oldTable = NULL; 431 432 fTableSize = newSize; 433 fTable = newTable; 434 } 435 436 ValueType*& _Link(ValueType* bucket) const 437 { 438 return fDefinition.GetLink(bucket); 439 } 440 441 bool _ExhaustiveSearch(ValueType* value) const 442 { 443 for (size_t i = 0; i < fTableSize; i++) { 444 ValueType* bucket = fTable[i]; 445 while (bucket) { 446 if (bucket == value) 447 return true; 448 bucket = _Link(bucket); 449 } 450 } 451 452 return false; 453 } 454 455 Definition fDefinition; 456 Allocator fAllocator; 457 size_t fTableSize; 458 size_t fItemCount; 459 ValueType** fTable; 460 }; 461 462 #endif // _KERNEL_UTIL_OPEN_HASH_TABLE_H 463