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 37namespace BPrivate { 38 39// HashSetElement 40template<typename Key> 41class HashSetElement : public OpenHashElement { 42private: 43 typedef HashSetElement<Key> Element; 44public: 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 71template<typename Key> 72class HashSet { 73public: 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 166protected: 167 typedef HashSetElement<Key> Element; 168 friend class Iterator; 169 170private: 171 Element *_FindElement(const Key& key) const; 172 173protected: 174 OpenHashElementArray<Element> fElementArray; 175 OpenHashTable<Element, OpenHashElementArray<Element> > fTable; 176}; 177 178// SynchronizedHashSet 179template<typename Key> 180class SynchronizedHashSet : public BLocker { 181public: 182 typedef struct 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 233protected: 234 typedef AutoLocker<BLocker> MapLocker; 235 236 HashSet<Key> fSet; 237}; 238 239// HashSet 240 241// constructor 242template<typename Key> 243HashSet<Key>::HashSet() 244 : fElementArray(1000), 245 fTable(1000, &fElementArray) 246{ 247} 248 249// destructor 250template<typename Key> 251HashSet<Key>::~HashSet() 252{ 253} 254 255// InitCheck 256template<typename Key> 257status_t 258HashSet<Key>::InitCheck() const 259{ 260 return (fTable.InitCheck() && fElementArray.InitCheck() 261 ? B_OK : B_NO_MEMORY); 262} 263 264// Add 265template<typename Key> 266status_t 267HashSet<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 279template<typename Key> 280bool 281HashSet<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 291template<typename Key> 292void 293HashSet<Key>::Clear() 294{ 295 fTable.RemoveAll(); 296} 297 298// Contains 299template<typename Key> 300bool 301HashSet<Key>::Contains(const Key& key) const 302{ 303 return _FindElement(key); 304} 305 306// Size 307template<typename Key> 308int32 309HashSet<Key>::Size() const 310{ 311 return fTable.CountElements(); 312} 313 314// GetIterator 315template<typename Key> 316struct HashSet<Key>::Iterator 317HashSet<Key>::GetIterator() 318{ 319 return Iterator(this); 320} 321 322// _FindElement 323template<typename Key> 324struct HashSet<Key>::Element * 325HashSet<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 339using BPrivate::HashSet; 340using BPrivate::SynchronizedHashSet; 341 342#endif // HASH_SET_H 343