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 "AutoLocker.h" 32#include "Locker.h" 33#include "OpenHashTable.h" 34 35// HashSetElement 36template<typename Key> 37class HashSetElement : public OpenHashElement { 38private: 39 typedef HashSetElement<Key> Element; 40public: 41 42 HashSetElement() : OpenHashElement(), fKey() 43 { 44 fNext = -1; 45 } 46 47 inline uint32 Hash() const 48 { 49 return fKey.GetHashCode(); 50 } 51 52 inline bool operator==(const OpenHashElement &_element) const 53 { 54 const Element &element = static_cast<const Element&>(_element); 55 return (fKey == element.fKey); 56 } 57 58 inline void Adopt(Element &element) 59 { 60 fKey = element.fKey; 61 } 62 63 Key fKey; 64}; 65 66// HashSet 67template<typename Key> 68class HashSet { 69public: 70 class Iterator { 71 private: 72 typedef HashSetElement<Key> Element; 73 public: 74 Iterator(const Iterator& other) 75 : fSet(other.fSet), 76 fIndex(other.fIndex), 77 fElement(other.fElement), 78 fLastElement(other.fElement) 79 { 80 } 81 82 bool HasNext() const 83 { 84 return fElement; 85 } 86 87 Key Next() 88 { 89 if (!fElement) 90 return Key(); 91 Key result(fElement->fKey); 92 _FindNext(); 93 return result; 94 } 95 96 bool Remove() 97 { 98 if (!fLastElement) 99 return false; 100 fSet->fTable.Remove(fLastElement); 101 fLastElement = NULL; 102 return true; 103 } 104 105 Iterator& operator=(const Iterator& other) 106 { 107 fSet = other.fSet; 108 fIndex = other.fIndex; 109 fElement = other.fElement; 110 fLastElement = other.fLastElement; 111 return *this; 112 } 113 114 private: 115 Iterator(HashSet<Key>* map) 116 : fSet(map), 117 fIndex(0), 118 fElement(NULL), 119 fLastElement(NULL) 120 { 121 // find first 122 _FindNext(); 123 } 124 125 void _FindNext() 126 { 127 fLastElement = fElement; 128 if (fElement && fElement->fNext >= 0) { 129 fElement = fSet->fTable.ElementAt(fElement->fNext); 130 return; 131 } 132 fElement = NULL; 133 int32 arraySize = fSet->fTable.ArraySize(); 134 for (; !fElement && fIndex < arraySize; fIndex++) 135 fElement = fSet->fTable.FindFirst(fIndex); 136 } 137 138 private: 139 friend class HashSet<Key>; 140 141 HashSet<Key>* fSet; 142 int32 fIndex; 143 Element* fElement; 144 Element* fLastElement; 145 }; 146 147 HashSet(); 148 ~HashSet(); 149 150 status_t InitCheck() const; 151 152 status_t Add(const Key& key); 153 bool Remove(const Key& key); 154 bool Contains(const Key& key) const; 155 156 int32 Size() const; 157 158 Iterator GetIterator(); 159 160protected: 161 typedef HashSetElement<Key> Element; 162 friend class Iterator; 163 164private: 165 Element *_FindElement(const Key& key) const; 166 167protected: 168 OpenHashElementArray<Element> fElementArray; 169 OpenHashTable<Element, OpenHashElementArray<Element> > fTable; 170}; 171 172// SynchronizedHashSet 173template<typename Key> 174class SynchronizedHashSet : public Locker { 175public: 176 typedef HashSet<Key>::Iterator Iterator; 177 178 SynchronizedHashSet() : Locker("synchronized hash map") {} 179 ~SynchronizedHashSet() { Lock(); } 180 181 status_t InitCheck() const 182 { 183 return fSet.InitCheck(); 184 } 185 186 status_t Add(const Key& key) 187 { 188 MapLocker locker(this); 189 if (!locker.IsLocked()) 190 return B_ERROR; 191 return fSet.Add(key); 192 } 193 194 bool Remove(const Key& key) 195 { 196 MapLocker locker(this); 197 if (!locker.IsLocked()) 198 return false; 199 return fSet.Remove(key); 200 } 201 202 bool Contains(const Key& key) const 203 { 204 const Locker* lock = this; 205 MapLocker locker(const_cast<Locker*>(lock)); 206 if (!locker.IsLocked()) 207 return false; 208 return fSet.Contains(key); 209 } 210 211 int32 Size() const 212 { 213 const Locker* lock = this; 214 MapLocker locker(const_cast<Locker*>(lock)); 215 return fSet.Size(); 216 } 217 218 Iterator GetIterator() 219 { 220 return fSet.GetIterator(); 221 } 222 223 // for debugging only 224 const HashSet<Key>& GetUnsynchronizedSet() const { return fSet; } 225 HashSet<Key>& GetUnsynchronizedSet() { return fSet; } 226 227protected: 228 typedef AutoLocker<Locker> MapLocker; 229 230 HashSet<Key> fSet; 231}; 232 233// HashSet 234 235// constructor 236template<typename Key> 237HashSet<Key>::HashSet() 238 : fElementArray(1000), 239 fTable(1000, &fElementArray) 240{ 241} 242 243// destructor 244template<typename Key> 245HashSet<Key>::~HashSet() 246{ 247} 248 249// InitCheck 250template<typename Key> 251status_t 252HashSet<Key>::InitCheck() const 253{ 254 return (fTable.InitCheck() && fElementArray.InitCheck() 255 ? B_OK : B_NO_MEMORY); 256} 257 258// Add 259template<typename Key> 260status_t 261HashSet<Key>::Add(const Key& key) 262{ 263 if (Contains(key)) 264 return B_OK; 265 Element* element = fTable.Add(key.GetHashCode()); 266 if (!element) 267 return B_NO_MEMORY; 268 element->fKey = key; 269 return B_OK; 270} 271 272// Remove 273template<typename Key> 274bool 275HashSet<Key>::Remove(const Key& key) 276{ 277 if (Element* element = _FindElement(key)) { 278 fTable.Remove(element); 279 return true; 280 } 281 return false; 282} 283 284// Contains 285template<typename Key> 286bool 287HashSet<Key>::Contains(const Key& key) const 288{ 289 return _FindElement(key); 290} 291 292// Size 293template<typename Key> 294int32 295HashSet<Key>::Size() const 296{ 297 return fTable.CountElements(); 298} 299 300// GetIterator 301template<typename Key> 302HashSet<Key>::Iterator 303HashSet<Key>::GetIterator() 304{ 305 return Iterator(this); 306} 307 308// _FindElement 309template<typename Key> 310HashSet<Key>::Element * 311HashSet<Key>::_FindElement(const Key& key) const 312{ 313 Element* element = fTable.FindFirst(key.GetHashCode()); 314 while (element && element->fKey != key) { 315 if (element->fNext >= 0) 316 element = fTable.ElementAt(element->fNext); 317 else 318 element = NULL; 319 } 320 return element; 321} 322 323#endif // HASH_SET_H 324