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 OpenHashTable<Definition, 25 AutoExpand, CheckDuplicates> { 26 public: 27 typedef OpenHashTable<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(size_t initialSize = HashTable::kMinimumSize) 35 : HashTable(initialSize) {} 36 37 MultiHashTable(const Definition& definition, 38 size_t initialSize = HashTable::kMinimumSize) 39 : HashTable(definition, initialSize) {} 40 41 status_t InitCheck() const { return HashTable::InitCheck(); } 42 43 void Insert(ValueType *value) 44 { 45 if (AutoExpand 46 && HashTable::fItemCount >= (HashTable::fTableSize * 200 / 256)) 47 _Resize(HashTable::fTableSize * 2); 48 49 InsertUnchecked(value); 50 } 51 52 void InsertUnchecked(ValueType *value) 53 { 54 _Insert(HashTable::fTable, HashTable::fTableSize, value); 55 HashTable::fItemCount++; 56 } 57 58 bool Remove(ValueType *value) 59 { 60 if (!HashTable::RemoveUnchecked(value)) 61 return false; 62 63 if (AutoExpand && HashTable::fTableSize > HashTable::kMinimumSize 64 && HashTable::fItemCount < (HashTable::fTableSize * 50 / 256)) 65 _Resize(HashTable::fTableSize / 2); 66 67 return true; 68 } 69 70 Iterator GetIterator() const { return HashTable::GetIterator(); } 71 72 class ValueIterator : protected Iterator { 73 public: 74 ValueIterator(const HashTable *table, size_t index, ValueType *value) 75 : fOriginalIndex(index), fOriginalValue(value) 76 { 77 Iterator::fTable = table; 78 Rewind(); 79 } 80 81 bool HasNext() const 82 { 83 if (Iterator::fNext == NULL) 84 return false; 85 if (Iterator::fNext == fOriginalValue) 86 return true; 87 return ((const MultiTable *)Iterator::fTable)->_Definition().CompareValues( 88 fOriginalValue, Iterator::fNext); 89 } 90 91 void Rewind() 92 { 93 Iterator::fIndex = fOriginalIndex + 1; 94 Iterator::fNext = fOriginalValue; 95 } 96 97 ValueType *Next() { return Iterator::Next(); } 98 99 private: 100 size_t fOriginalIndex; 101 ValueType *fOriginalValue; 102 }; 103 104 ValueIterator Lookup(const KeyType &key) const 105 { 106 size_t index = HashTable::fDefinition.HashKey(key) 107 & (HashTable::fTableSize - 1); 108 ValueType *slot = HashTable::fTable[index]; 109 110 while (slot) { 111 if (HashTable::fDefinition.Compare(key, slot)) 112 break; 113 slot = HashTable::_Link(slot)->fNext; 114 } 115 116 if (slot == NULL) 117 return ValueIterator(this, HashTable::fTableSize, NULL); 118 119 return ValueIterator(this, index, slot); 120 } 121 122 private: 123 // for g++ 2.95 124 friend class ValueIterator; 125 126 const Definition &_Definition() const { return HashTable::fDefinition; } 127 128 void _Insert(ValueType **table, size_t tableSize, ValueType *value) 129 { 130 size_t index = HashTable::fDefinition.Hash(value) & (tableSize - 1); 131 132 ValueType *previous; 133 134 // group values with the same key 135 for (previous = table[index]; previous 136 && !HashTable::fDefinition.CompareValues(previous, value); 137 previous = HashTable::_Link(previous)->fNext); 138 139 if (previous) { 140 _Link(value)->fNext = _Link(previous)->fNext; 141 _Link(previous)->fNext = value; 142 } else { 143 _Link(value)->fNext = table[index]; 144 table[index] = value; 145 } 146 } 147 148 // TODO use OpenHashTable's _Resize 149 bool _Resize(size_t newSize) 150 { 151 ValueType **newTable = new ValueType *[newSize]; 152 if (newTable == NULL) 153 return false; 154 155 for (size_t i = 0; i < newSize; i++) 156 newTable[i] = NULL; 157 158 if (HashTable::fTable) { 159 for (size_t i = 0; i < HashTable::fTableSize; i++) { 160 ValueType *bucket = HashTable::fTable[i]; 161 while (bucket) { 162 ValueType *next = _Link(bucket)->fNext; 163 _Insert(newTable, newSize, bucket); 164 bucket = next; 165 } 166 } 167 168 delete [] HashTable::fTable; 169 } 170 171 HashTable::fTableSize = newSize; 172 HashTable::fTable = newTable; 173 return true; 174 } 175 }; 176 177 #endif // _KERNEL_UTIL_MULTI_HASH_TABLE_H 178