1 /* 2 * Copyright 2004-2009, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * Copyright 2019, Haiku, Inc. All rights reserved. 4 * Distributed under the terms of the MIT License. 5 */ 6 #ifndef HASH_SET_H 7 #define HASH_SET_H 8 9 #include <OpenHashTable.h> 10 #include <Locker.h> 11 12 #include "AutoLocker.h" 13 14 15 namespace BPrivate { 16 17 18 // HashSetElement 19 template<typename Key> 20 class HashSetElement { 21 private: 22 typedef HashSetElement<Key> Element; 23 24 public: 25 HashSetElement() 26 : 27 fKey(), 28 fNext(NULL) 29 { 30 } 31 32 HashSetElement(const Key& key) 33 : 34 fKey(key), 35 fNext(NULL) 36 { 37 } 38 39 Key fKey; 40 HashSetElement* fNext; 41 }; 42 43 44 // HashSetTableDefinition 45 template<typename Key> 46 struct HashSetTableDefinition { 47 typedef Key KeyType; 48 typedef HashSetElement<Key> ValueType; 49 50 size_t HashKey(const KeyType& key) const 51 { return key.GetHashCode(); } 52 size_t Hash(const ValueType* value) const 53 { return HashKey(value->fKey); } 54 bool Compare(const KeyType& key, const ValueType* value) const 55 { return value->fKey == key; } 56 ValueType*& GetLink(ValueType* value) const 57 { return value->fNext; } 58 }; 59 60 61 // HashSet 62 template<typename Key> 63 class HashSet { 64 public: 65 class Iterator { 66 private: 67 typedef HashSetElement<Key> Element; 68 public: 69 Iterator(const Iterator& other) 70 : 71 fSet(other.fSet), 72 fIterator(other.fIterator), 73 fElement(other.fElement) 74 { 75 } 76 77 bool HasNext() const 78 { 79 return fIterator.HasNext(); 80 } 81 82 Key Next() 83 { 84 fElement = fIterator.Next(); 85 if (fElement == NULL) 86 return Key(); 87 88 return fElement->fKey; 89 } 90 91 Iterator& operator=(const Iterator& other) 92 { 93 fSet = other.fSet; 94 fIterator = other.fIterator; 95 fElement = other.fElement; 96 return *this; 97 } 98 99 private: 100 Iterator(const HashSet<Key>* set) 101 : 102 fSet(set), 103 fIterator(set->fTable.GetIterator()), 104 fElement(NULL) 105 { 106 } 107 108 private: 109 typedef BOpenHashTable<HashSetTableDefinition<Key> > ElementTable; 110 111 const HashSet<Key>* fSet; 112 typename ElementTable::Iterator fIterator; 113 Element* fElement; 114 115 private: 116 friend class HashSet<Key>; 117 }; 118 119 HashSet(); 120 ~HashSet(); 121 122 status_t InitCheck() const; 123 124 status_t Add(const Key& key); 125 bool Remove(const Key& key); 126 bool Remove(Iterator& it); 127 void Clear(); 128 bool Contains(const Key& key) const; 129 130 int32 Size() const; 131 132 Iterator GetIterator() const; 133 134 protected: 135 typedef BOpenHashTable<HashSetTableDefinition<Key> > ElementTable; 136 typedef HashSetElement<Key> Element; 137 friend class Iterator; 138 139 protected: 140 ElementTable fTable; 141 }; 142 143 144 // SynchronizedHashSet 145 template<typename Key, typename Locker = BLocker> 146 class SynchronizedHashSet : public Locker { 147 public: 148 typedef typename HashSet<Key>::Iterator Iterator; 149 150 SynchronizedHashSet() : Locker("synchronized hash set") {} 151 ~SynchronizedHashSet() { Locker::Lock(); } 152 153 status_t InitCheck() const 154 { 155 return fSet.InitCheck(); 156 } 157 158 status_t Add(const Key& key) 159 { 160 MapLocker locker(this); 161 if (!locker.IsLocked()) 162 return B_ERROR; 163 return fSet.Add(key); 164 } 165 166 bool Remove(const Key& key) 167 { 168 MapLocker locker(this); 169 if (!locker.IsLocked()) 170 return false; 171 return fSet.Remove(key); 172 } 173 174 void Clear() 175 { 176 MapLocker locker(this); 177 fSet.Clear(); 178 } 179 180 bool Contains(const Key& key) const 181 { 182 const Locker* lock = this; 183 MapLocker locker(const_cast<Locker*>(lock)); 184 if (!locker.IsLocked()) 185 return false; 186 return fSet.Contains(key); 187 } 188 189 int32 Size() const 190 { 191 const Locker* lock = this; 192 MapLocker locker(const_cast<Locker*>(lock)); 193 return fSet.Size(); 194 } 195 196 Iterator GetIterator() const 197 { 198 return fSet.GetIterator(); 199 } 200 201 // for debugging only 202 const HashSet<Key>& GetUnsynchronizedSet() const { return fSet; } 203 HashSet<Key>& GetUnsynchronizedSet() { return fSet; } 204 205 protected: 206 typedef AutoLocker<Locker> MapLocker; 207 208 HashSet<Key> fSet; 209 }; 210 211 212 // HashSet 213 214 // constructor 215 template<typename Key> 216 HashSet<Key>::HashSet() 217 : 218 fTable() 219 { 220 fTable.Init(); 221 } 222 223 224 // destructor 225 template<typename Key> 226 HashSet<Key>::~HashSet() 227 { 228 Clear(); 229 } 230 231 232 // InitCheck 233 template<typename Key> 234 status_t 235 HashSet<Key>::InitCheck() const 236 { 237 return (fTable.TableSize() > 0 ? B_OK : B_NO_MEMORY); 238 } 239 240 241 // Add 242 template<typename Key> 243 status_t 244 HashSet<Key>::Add(const Key& key) 245 { 246 Element* element = fTable.Lookup(key); 247 if (element) { 248 // already contains the value 249 return B_OK; 250 } 251 252 // does not contain the key yet: create an element and add it 253 element = new(std::nothrow) Element(key); 254 if (!element) 255 return B_NO_MEMORY; 256 257 status_t error = fTable.Insert(element); 258 if (error != B_OK) 259 delete element; 260 261 return error; 262 } 263 264 265 // Remove 266 template<typename Key> 267 bool 268 HashSet<Key>::Remove(const Key& key) 269 { 270 Element* element = fTable.Lookup(key); 271 if (element == NULL) 272 return false; 273 274 fTable.Remove(element); 275 delete element; 276 277 return true; 278 } 279 280 281 // Remove 282 template<typename Key> 283 bool 284 HashSet<Key>::Remove(Iterator& it) 285 { 286 Element* element = it.fElement; 287 if (element == NULL) 288 return false; 289 290 fTable.RemoveUnchecked(element); 291 delete element; 292 it.fElement = NULL; 293 294 return true; 295 } 296 297 298 // Clear 299 template<typename Key> 300 void 301 HashSet<Key>::Clear() 302 { 303 // clear the table and delete the elements 304 Element* element = fTable.Clear(true); 305 while (element != NULL) { 306 Element* next = element->fNext; 307 delete element; 308 element = next; 309 } 310 } 311 312 313 // Contains 314 template<typename Key> 315 bool 316 HashSet<Key>::Contains(const Key& key) const 317 { 318 return fTable.Lookup(key) != NULL; 319 } 320 321 322 // Size 323 template<typename Key> 324 int32 325 HashSet<Key>::Size() const 326 { 327 return fTable.CountElements(); 328 } 329 330 331 // GetIterator 332 template<typename Key> 333 typename HashSet<Key>::Iterator 334 HashSet<Key>::GetIterator() const 335 { 336 return Iterator(this); 337 } 338 339 } // namespace BPrivate 340 341 using BPrivate::HashSet; 342 343 #endif // HASH_SET_H 344