1 /* 2 * Copyright 2007, Hugo Santos. All Rights Reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Hugo Santos, hugosantos@gmail.com 7 */ 8 #ifndef _KERNEL_UTIL_MULTI_HASH_TABLE_H 9 #define _KERNEL_UTIL_MULTI_HASH_TABLE_H 10 11 12 #include <KernelExport.h> 13 #include <util/kernel_cpp.h> 14 #include <util/OpenHashTable.h> 15 16 17 // MultiHashTable is a container which acts a bit like multimap<> 18 // but with hash table semantics. 19 20 // refer to OpenHashTable.h for how to use this container. 21 22 template<typename Definition, bool AutoExpand = true, 23 bool CheckDuplicates = false> 24 class MultiHashTable : private BOpenHashTable<Definition, 25 AutoExpand, CheckDuplicates> { 26 public: 27 typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable; 28 typedef MultiHashTable<Definition, AutoExpand, CheckDuplicates> MultiTable; 29 30 typedef typename HashTable::Iterator Iterator; 31 typedef typename Definition::KeyType KeyType; 32 typedef typename Definition::ValueType ValueType; 33 34 MultiHashTable() 35 : HashTable() {} 36 37 MultiHashTable(const Definition& definition) 38 : HashTable(definition) {} 39 40 status_t Init(size_t initialSize = HashTable::kMinimumSize) 41 { 42 return HashTable::Init(initialSize); 43 } 44 45 void Insert(ValueType *value) 46 { 47 if (AutoExpand 48 && HashTable::fItemCount >= (HashTable::fTableSize * 200 / 256)) 49 _Resize(HashTable::fTableSize * 2); 50 51 InsertUnchecked(value); 52 } 53 54 void InsertUnchecked(ValueType *value) 55 { 56 _Insert(HashTable::fTable, HashTable::fTableSize, value); 57 HashTable::fItemCount++; 58 } 59 60 bool Remove(ValueType *value) 61 { 62 if (!HashTable::RemoveUnchecked(value)) 63 return false; 64 65 if (AutoExpand && HashTable::fTableSize > HashTable::kMinimumSize 66 && HashTable::fItemCount < (HashTable::fTableSize * 50 / 256)) 67 _Resize(HashTable::fTableSize / 2); 68 69 return true; 70 } 71 72 Iterator GetIterator() const { return HashTable::GetIterator(); } 73 74 class ValueIterator : protected Iterator { 75 public: 76 ValueIterator(const HashTable *table, size_t index, ValueType *value) 77 : fOriginalIndex(index), fOriginalValue(value) 78 { 79 Iterator::fTable = table; 80 Rewind(); 81 } 82 83 bool HasNext() const 84 { 85 if (Iterator::fNext == NULL) 86 return false; 87 if (Iterator::fNext == fOriginalValue) 88 return true; 89 return ((const MultiTable *)Iterator::fTable)->_Definition().CompareValues( 90 fOriginalValue, Iterator::fNext); 91 } 92 93 void Rewind() 94 { 95 Iterator::fIndex = fOriginalIndex + 1; 96 Iterator::fNext = fOriginalValue; 97 } 98 99 ValueType *Next() { return Iterator::Next(); } 100 101 private: 102 size_t fOriginalIndex; 103 ValueType *fOriginalValue; 104 }; 105 106 ValueIterator Lookup(const KeyType &key) const 107 { 108 size_t index = 0; 109 ValueType *slot = NULL; 110 if (HashTable::fTableSize > 0) { 111 index = HashTable::fDefinition.HashKey(key) 112 & (HashTable::fTableSize - 1); 113 slot = HashTable::fTable[index]; 114 } 115 116 while (slot) { 117 if (HashTable::fDefinition.Compare(key, slot)) 118 break; 119 slot = HashTable::_Link(slot); 120 } 121 122 if (slot == NULL) 123 return ValueIterator(this, HashTable::fTableSize, NULL); 124 125 return ValueIterator(this, index, slot); 126 } 127 128 private: 129 // for g++ 2.95 130 friend class ValueIterator; 131 132 const Definition &_Definition() const { return HashTable::fDefinition; } 133 134 void _Insert(ValueType **table, size_t tableSize, ValueType *value) 135 { 136 size_t index = HashTable::fDefinition.Hash(value) & (tableSize - 1); 137 138 ValueType *previous; 139 140 // group values with the same key 141 for (previous = table[index]; previous 142 && !HashTable::fDefinition.CompareValues(previous, value); 143 previous = HashTable::_Link(previous)); 144 145 if (previous) { 146 HashTable::_Link(value) = HashTable::_Link(previous); 147 HashTable::_Link(previous) = value; 148 } else { 149 HashTable::_Link(value) = table[index]; 150 table[index] = value; 151 } 152 } 153 154 // TODO use BOpenHashTable's _Resize 155 bool _Resize(size_t newSize) 156 { 157 ValueType **newTable = new ValueType *[newSize]; 158 if (newTable == NULL) 159 return false; 160 161 for (size_t i = 0; i < newSize; i++) 162 newTable[i] = NULL; 163 164 if (HashTable::fTable) { 165 for (size_t i = 0; i < HashTable::fTableSize; i++) { 166 ValueType *bucket = HashTable::fTable[i]; 167 while (bucket) { 168 ValueType *next = HashTable::_Link(bucket); 169 _Insert(newTable, newSize, bucket); 170 bucket = next; 171 } 172 } 173 174 delete [] HashTable::fTable; 175 } 176 177 HashTable::fTableSize = newSize; 178 HashTable::fTable = newTable; 179 return true; 180 } 181 }; 182 183 #endif // _KERNEL_UTIL_MULTI_HASH_TABLE_H 184