headers/private/userlandfs/shared/HashSet.h

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