1 // HashSet.h 2 // 3 // Copyright (c) 2004, Ingo Weinhold (bonefish@cs.tu-berlin.de) 4 // 5 // Permission is hereby granted, free of charge, to any person obtaining a 6 // copy of this software and associated documentation files (the "Software"), 7 // to deal in the Software without restriction, including without limitation 8 // the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 // and/or sell copies of the Software, and to permit persons to whom the 10 // Software is furnished to do so, subject to the following conditions: 11 // 12 // The above copyright notice and this permission notice shall be included in 13 // all copies or substantial portions of the Software. 14 // 15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 // DEALINGS IN THE SOFTWARE. 22 // 23 // Except as contained in this notice, the name of a copyright holder shall 24 // not be used in advertising or otherwise to promote the sale, use or other 25 // dealings in this Software without prior written authorization of the 26 // copyright holder. 27 28 #ifndef HASH_SET_H 29 #define HASH_SET_H 30 31 #include <Locker.h> 32 33 #include "AutoLocker.h" 34 #include "OpenHashTable.h" 35 36 37 namespace BPrivate { 38 39 // HashSetElement 40 template<typename Key> 41 class HashSetElement : public OpenHashElement { 42 private: 43 typedef HashSetElement<Key> Element; 44 public: 45 46 HashSetElement() : OpenHashElement(), fKey() 47 { 48 fNext = -1; 49 } 50 51 inline uint32 Hash() const 52 { 53 return fKey.GetHashCode(); 54 } 55 56 inline bool operator==(const OpenHashElement &_element) const 57 { 58 const Element &element = static_cast<const Element&>(_element); 59 return (fKey == element.fKey); 60 } 61 62 inline void Adopt(Element &element) 63 { 64 fKey = element.fKey; 65 } 66 67 Key fKey; 68 }; 69 70 // HashSet 71 template<typename Key> 72 class HashSet { 73 public: 74 class Iterator { 75 private: 76 typedef HashSetElement<Key> Element; 77 public: 78 Iterator(const Iterator& other) 79 : fSet(other.fSet), 80 fIndex(other.fIndex), 81 fElement(other.fElement), 82 fLastElement(other.fElement) 83 { 84 } 85 86 bool HasNext() const 87 { 88 return fElement; 89 } 90 91 Key Next() 92 { 93 if (!fElement) 94 return Key(); 95 Key result(fElement->fKey); 96 _FindNext(); 97 return result; 98 } 99 100 bool Remove() 101 { 102 if (!fLastElement) 103 return false; 104 fSet->fTable.Remove(fLastElement); 105 fLastElement = NULL; 106 return true; 107 } 108 109 Iterator& operator=(const Iterator& other) 110 { 111 fSet = other.fSet; 112 fIndex = other.fIndex; 113 fElement = other.fElement; 114 fLastElement = other.fLastElement; 115 return *this; 116 } 117 118 private: 119 Iterator(HashSet<Key>* map) 120 : fSet(map), 121 fIndex(0), 122 fElement(NULL), 123 fLastElement(NULL) 124 { 125 // find first 126 _FindNext(); 127 } 128 129 void _FindNext() 130 { 131 fLastElement = fElement; 132 if (fElement && fElement->fNext >= 0) { 133 fElement = fSet->fTable.ElementAt(fElement->fNext); 134 return; 135 } 136 fElement = NULL; 137 int32 arraySize = fSet->fTable.ArraySize(); 138 for (; !fElement && fIndex < arraySize; fIndex++) 139 fElement = fSet->fTable.FindFirst(fIndex); 140 } 141 142 private: 143 friend class HashSet<Key>; 144 145 HashSet<Key>* fSet; 146 int32 fIndex; 147 Element* fElement; 148 Element* fLastElement; 149 }; 150 151 HashSet(); 152 ~HashSet(); 153 154 status_t InitCheck() const; 155 156 status_t Add(const Key& key); 157 bool Remove(const Key& key); 158 void Clear(); 159 bool Contains(const Key& key) const; 160 161 int32 Size() const; 162 bool IsEmpty() const { return Size() == 0; } 163 164 Iterator GetIterator(); 165 166 protected: 167 typedef HashSetElement<Key> Element; 168 friend class Iterator; 169 170 private: 171 Element *_FindElement(const Key& key) const; 172 173 protected: 174 OpenHashElementArray<Element> fElementArray; 175 OpenHashTable<Element, OpenHashElementArray<Element> > fTable; 176 }; 177 178 // SynchronizedHashSet 179 template<typename Key> 180 class SynchronizedHashSet : public BLocker { 181 public: 182 typedef typename HashSet<Key>::Iterator Iterator; 183 184 SynchronizedHashSet() : BLocker("synchronized hash set") {} 185 ~SynchronizedHashSet() { Lock(); } 186 187 status_t InitCheck() const 188 { 189 return fSet.InitCheck(); 190 } 191 192 status_t Add(const Key& key) 193 { 194 MapLocker locker(this); 195 if (!locker.IsLocked()) 196 return B_ERROR; 197 return fSet.Add(key); 198 } 199 200 bool Remove(const Key& key) 201 { 202 MapLocker locker(this); 203 if (!locker.IsLocked()) 204 return false; 205 return fSet.Remove(key); 206 } 207 208 bool Contains(const Key& key) const 209 { 210 const BLocker* lock = this; 211 MapLocker locker(const_cast<BLocker*>(lock)); 212 if (!locker.IsLocked()) 213 return false; 214 return fSet.Contains(key); 215 } 216 217 int32 Size() const 218 { 219 const BLocker* lock = this; 220 MapLocker locker(const_cast<BLocker*>(lock)); 221 return fSet.Size(); 222 } 223 224 Iterator GetIterator() 225 { 226 return fSet.GetIterator(); 227 } 228 229 // for debugging only 230 const HashSet<Key>& GetUnsynchronizedSet() const { return fSet; } 231 HashSet<Key>& GetUnsynchronizedSet() { return fSet; } 232 233 protected: 234 typedef AutoLocker<BLocker> MapLocker; 235 236 HashSet<Key> fSet; 237 }; 238 239 // HashSet 240 241 // constructor 242 template<typename Key> 243 HashSet<Key>::HashSet() 244 : fElementArray(1000), 245 fTable(1000, &fElementArray) 246 { 247 } 248 249 // destructor 250 template<typename Key> 251 HashSet<Key>::~HashSet() 252 { 253 } 254 255 // InitCheck 256 template<typename Key> 257 status_t 258 HashSet<Key>::InitCheck() const 259 { 260 return (fTable.InitCheck() && fElementArray.InitCheck() 261 ? B_OK : B_NO_MEMORY); 262 } 263 264 // Add 265 template<typename Key> 266 status_t 267 HashSet<Key>::Add(const Key& key) 268 { 269 if (Contains(key)) 270 return B_OK; 271 Element* element = fTable.Add(key.GetHashCode()); 272 if (!element) 273 return B_NO_MEMORY; 274 element->fKey = key; 275 return B_OK; 276 } 277 278 // Remove 279 template<typename Key> 280 bool 281 HashSet<Key>::Remove(const Key& key) 282 { 283 if (Element* element = _FindElement(key)) { 284 fTable.Remove(element); 285 return true; 286 } 287 return false; 288 } 289 290 // Clear 291 template<typename Key> 292 void 293 HashSet<Key>::Clear() 294 { 295 fTable.RemoveAll(); 296 } 297 298 // Contains 299 template<typename Key> 300 bool 301 HashSet<Key>::Contains(const Key& key) const 302 { 303 return _FindElement(key); 304 } 305 306 // Size 307 template<typename Key> 308 int32 309 HashSet<Key>::Size() const 310 { 311 return fTable.CountElements(); 312 } 313 314 // GetIterator 315 template<typename Key> 316 typename HashSet<Key>::Iterator 317 HashSet<Key>::GetIterator() 318 { 319 return Iterator(this); 320 } 321 322 // _FindElement 323 template<typename Key> 324 HashSetElement<Key> * 325 HashSet<Key>::_FindElement(const Key& key) const 326 { 327 Element* element = fTable.FindFirst(key.GetHashCode()); 328 while (element && element->fKey != key) { 329 if (element->fNext >= 0) 330 element = fTable.ElementAt(element->fNext); 331 else 332 element = NULL; 333 } 334 return element; 335 } 336 337 } // namespace BPrivate 338 339 using BPrivate::HashSet; 340 using BPrivate::SynchronizedHashSet; 341 342 #endif // HASH_SET_H 343