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 (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 fItemCount = 0; 260 261 return result; 262 } 263 264 /*! If the table needs resizing, the number of bytes for the required 265 allocation is returned. If no resizing is needed, 0 is returned. 266 */ 267 size_t ResizeNeeded() const 268 { 269 size_t size = fTableSize; 270 if (size == 0 || fItemCount >= (size * 200 / 256)) { 271 // grow table 272 if (size == 0) 273 size = kMinimumSize; 274 while (fItemCount >= size * 200 / 256) 275 size <<= 1; 276 } else if (size > kMinimumSize && fItemCount < size * 50 / 256) { 277 // shrink table 278 while (fItemCount < size * 50 / 256) 279 size >>= 1; 280 if (size < kMinimumSize) 281 size = kMinimumSize; 282 } 283 284 if (size == fTableSize) 285 return 0; 286 287 return size * sizeof(ValueType*); 288 } 289 290 /*! Resizes the table using the given allocation. The allocation must not 291 be \c NULL. It must be of size \a size, which must a value returned 292 earlier by ResizeNeeded(). If the size requirements have changed in the 293 meantime, the method free()s the given allocation and returns \c false, 294 unless \a force is \c true, in which case the supplied allocation is 295 used in any event. 296 Otherwise \c true is returned. 297 If \a oldTable is non-null and resizing is successful, the old table 298 will not be freed, but will be returned via this parameter instead. 299 */ 300 bool Resize(void* allocation, size_t size, bool force = false, 301 void** oldTable = NULL) 302 { 303 if (!force && size != ResizeNeeded()) { 304 fAllocator.Free(allocation); 305 return false; 306 } 307 308 _Resize((ValueType**)allocation, size / sizeof(ValueType*), oldTable); 309 return true; 310 } 311 312 class Iterator { 313 public: 314 Iterator(const HashTable* table) 315 : fTable(table) 316 { 317 Rewind(); 318 } 319 320 Iterator(const HashTable* table, size_t index, ValueType* value) 321 : fTable(table), fIndex(index), fNext(value) {} 322 323 bool HasNext() const { return fNext != NULL; } 324 325 ValueType* Next() 326 { 327 ValueType* current = fNext; 328 _GetNext(); 329 return current; 330 } 331 332 void Rewind() 333 { 334 // get the first one 335 fIndex = 0; 336 fNext = NULL; 337 _GetNext(); 338 } 339 340 protected: 341 Iterator() {} 342 343 void _GetNext() 344 { 345 if (fNext) 346 fNext = fTable->_Link(fNext); 347 348 while (fNext == NULL && fIndex < fTable->fTableSize) 349 fNext = fTable->fTable[fIndex++]; 350 } 351 352 const HashTable* fTable; 353 size_t fIndex; 354 ValueType* fNext; 355 }; 356 357 Iterator GetIterator() const 358 { 359 return Iterator(this); 360 } 361 362 Iterator GetIterator(const KeyType& key) const 363 { 364 if (fTableSize == 0) 365 return Iterator(this, fTableSize, NULL); 366 367 size_t index = fDefinition.HashKey(key) & (fTableSize - 1); 368 ValueType* slot = fTable[index]; 369 370 while (slot) { 371 if (fDefinition.Compare(key, slot)) 372 break; 373 slot = _Link(slot); 374 } 375 376 if (slot == NULL) 377 return Iterator(this, fTableSize, NULL); 378 379 return Iterator(this, index + 1, slot); 380 } 381 382 protected: 383 // for g++ 2.95 384 friend class Iterator; 385 386 void _Insert(ValueType** table, size_t tableSize, ValueType* value) 387 { 388 size_t index = fDefinition.Hash(value) & (tableSize - 1); 389 390 _Link(value) = table[index]; 391 table[index] = value; 392 } 393 394 bool _Resize(size_t newSize) 395 { 396 ValueType** newTable 397 = (ValueType**)fAllocator.Allocate(sizeof(ValueType*) * newSize); 398 if (newTable == NULL) 399 return false; 400 401 _Resize(newTable, newSize); 402 return true; 403 } 404 405 void _Resize(ValueType** newTable, size_t newSize, void** _oldTable = NULL) 406 { 407 for (size_t i = 0; i < newSize; i++) 408 newTable[i] = NULL; 409 410 if (fTable) { 411 for (size_t i = 0; i < fTableSize; i++) { 412 ValueType* bucket = fTable[i]; 413 while (bucket) { 414 ValueType* next = _Link(bucket); 415 _Insert(newTable, newSize, bucket); 416 bucket = next; 417 } 418 } 419 420 if (_oldTable != NULL) 421 *_oldTable = fTable; 422 else 423 fAllocator.Free(fTable); 424 } else if (_oldTable != NULL) 425 *_oldTable = NULL; 426 427 fTableSize = newSize; 428 fTable = newTable; 429 } 430 431 ValueType*& _Link(ValueType* bucket) const 432 { 433 return fDefinition.GetLink(bucket); 434 } 435 436 bool _ExhaustiveSearch(ValueType* value) const 437 { 438 for (size_t i = 0; i < fTableSize; i++) { 439 ValueType* bucket = fTable[i]; 440 while (bucket) { 441 if (bucket == value) 442 return true; 443 bucket = _Link(bucket); 444 } 445 } 446 447 return false; 448 } 449 450 Definition fDefinition; 451 Allocator fAllocator; 452 size_t fTableSize; 453 size_t fItemCount; 454 ValueType** fTable; 455 }; 456 457 #endif // _KERNEL_UTIL_OPEN_HASH_TABLE_H 458