headers/private/userlandfs/shared/HashMap.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_MAP_H
   6 #define HASH_MAP_H
   7
   8 //#include <Debug.h>
   9
  10 #include <util/OpenHashTable.h>
  11
  12 #include "AutoLocker.h"
  13 #include "Locker.h"
  14
  15
  16 // HashMapElement
  17 template<typename Key, typename Value>
  18 class HashMapElement {
  19 private:
  20         typedef HashMapElement<Key, Value> Element;
  21
  22 public:
  23         HashMapElement()
  24                 :
  25                 fKey(),
  26                 fValue()
  27         {
  28         }
  29
  30         HashMapElement(const Key& key, const Value& value)
  31                 :
  32                 fKey(key),
  33                 fValue(value)
  34         {
  35         }
  36
  37         Key                             fKey;
  38         Value                   fValue;
  39         HashMapElement* fNext;
  40 };
  41
  42
  43 // HashMapTableDefinition
  44 template<typename Key, typename Value>
  45 struct HashMapTableDefinition {
  46         typedef Key                                                     KeyType;
  47         typedef HashMapElement<Key, Value>      ValueType;
  48
  49         size_t HashKey(const KeyType& key) const
  50                 { return key.GetHashCode(); }
  51         size_t Hash(const ValueType* value) const
  52                 { return HashKey(value->fKey); }
  53         bool Compare(const KeyType& key, const ValueType* value) const
  54                 { return value->fKey == key; }
  55         ValueType*& GetLink(ValueType* value) const
  56                 { return value->fNext; }
  57 };
  58
  59
  60 // HashMap
  61 template<typename Key, typename Value>
  62 class HashMap {
  63 public:
  64         class Entry {
  65         public:
  66                 Entry() {}
  67                 Entry(const Key& key, Value value) : key(key), value(value) {}
  68
  69                 Key             key;
  70                 Value   value;
  71         };
  72
  73         class Iterator {
  74         private:
  75                 typedef HashMapElement<Key, Value>      Element;
  76         public:
  77                 Iterator(const Iterator& other)
  78                         :
  79                         fMap(other.fMap),
  80                         fIterator(other.fIterator),
  81                         fElement(other.fElement)
  82                 {
  83                 }
  84
  85                 bool HasNext() const
  86                 {
  87                         return fIterator.HasNext();
  88                 }
  89
  90                 Entry Next()
  91                 {
  92                         fElement = fIterator.Next();
  93                         if (fElement == NULL)
  94                                 return Entry();
  95
  96                         return Entry(fElement->fKey, fElement->fValue);
  97                 }
  98
  99                 Entry Remove()
 100                 {
 101                         if (fElement == NULL)
 102                                 return Entry();
 103
 104                         Entry result(fElement->fKey, fElement->fValue);
 105
 106                         fMap->fTable.RemoveUnchecked(fElement);
 107                         delete fElement;
 108                         fElement = NULL;
 109
 110                         return result;
 111                 }
 112
 113                 Iterator& operator=(const Iterator& other)
 114                 {
 115                         fMap = other.fMap;
 116                         fIterator = other.fIterator;
 117                         fElement = other.fElement;
 118                         return *this;
 119                 }
 120
 121         private:
 122                 Iterator(HashMap<Key, Value>* map)
 123                         :
 124                         fMap(map),
 125                         fIterator(map->fTable.GetIterator()),
 126                         fElement(NULL)
 127                 {
 128                 }
 129
 130         private:
 131                 friend class HashMap<Key, Value>;
 132                 typedef BOpenHashTable<HashMapTableDefinition<Key, Value> >
 133                         ElementTable;
 134
 135                 HashMap<Key, Value>*                    fMap;
 136                 typename ElementTable::Iterator fIterator;
 137                 Element*                                                fElement;
 138         };
 139
 140         HashMap();
 141         ~HashMap();
 142
 143         status_t InitCheck() const;
 144
 145         status_t Put(const Key& key, const Value& value);
 146         Value Remove(const Key& key);
 147         void Clear();
 148         Value Get(const Key& key) const;
 149
 150         bool ContainsKey(const Key& key) const;
 151
 152         int32 Size() const;
 153
 154         Iterator GetIterator();
 155
 156 protected:
 157         typedef BOpenHashTable<HashMapTableDefinition<Key, Value> > ElementTable;
 158         typedef HashMapElement<Key, Value>      Element;
 159         friend class Iterator;
 160
 161 protected:
 162         ElementTable    fTable;
 163 };
 164
 165
 166 // SynchronizedHashMap
 167 template<typename Key, typename Value>
 168 class SynchronizedHashMap : public Locker {
 169 public:
 170         typedef typename HashMap<Key, Value>::Entry Entry;
 171         typedef typename HashMap<Key, Value>::Iterator Iterator;
 172
 173         SynchronizedHashMap() : Locker("synchronized hash map") {}
 174         ~SynchronizedHashMap()  { Lock(); }
 175
 176         status_t InitCheck() const
 177         {
 178                 return fMap.InitCheck();
 179         }
 180
 181         status_t Put(const Key& key, const Value& value)
 182         {
 183                 MapLocker locker(this);
 184                 if (!locker.IsLocked())
 185                         return B_ERROR;
 186                 return fMap.Put(key, value);
 187         }
 188
 189         Value Remove(const Key& key)
 190         {
 191                 MapLocker locker(this);
 192                 if (!locker.IsLocked())
 193                         return Value();
 194                 return fMap.Remove(key);
 195         }
 196
 197         void Clear()
 198         {
 199                 MapLocker locker(this);
 200                 return fMap.Clear();
 201         }
 202
 203         Value Get(const Key& key) const
 204         {
 205                 const Locker* lock = this;
 206                 MapLocker locker(const_cast<Locker*>(lock));
 207                 if (!locker.IsLocked())
 208                         return Value();
 209                 return fMap.Get(key);
 210         }
 211
 212         bool ContainsKey(const Key& key) const
 213         {
 214                 const Locker* lock = this;
 215                 MapLocker locker(const_cast<Locker*>(lock));
 216                 if (!locker.IsLocked())
 217                         return false;
 218                 return fMap.ContainsKey(key);
 219         }
 220
 221         int32 Size() const
 222         {
 223                 const Locker* lock = this;
 224                 MapLocker locker(const_cast<Locker*>(lock));
 225                 return fMap.Size();
 226         }
 227
 228         Iterator GetIterator()
 229         {
 230                 return fMap.GetIterator();
 231         }
 232
 233         // for debugging only
 234         const HashMap<Key, Value>& GetUnsynchronizedMap() const { return fMap; }
 235         HashMap<Key, Value>& GetUnsynchronizedMap()                             { return fMap; }
 236
 237 protected:
 238         typedef AutoLocker<Locker> MapLocker;
 239
 240         HashMap<Key, Value>     fMap;
 241 };
 242
 243 // HashKey32
 244 template<typename Value>
 245 struct HashKey32 {
 246         HashKey32() {}
 247         HashKey32(const Value& value) : value(value) {}
 248
 249         uint32 GetHashCode() const
 250         {
 251                 return (uint32)value;
 252         }
 253
 254         HashKey32<Value> operator=(const HashKey32<Value>& other)
 255         {
 256                 value = other.value;
 257                 return *this;
 258         }
 259
 260         bool operator==(const HashKey32<Value>& other) const
 261         {
 262                 return (value == other.value);
 263         }
 264
 265         bool operator!=(const HashKey32<Value>& other) const
 266         {
 267                 return (value != other.value);
 268         }
 269
 270         Value   value;
 271 };
 272
 273
 274 // HashKey64
 275 template<typename Value>
 276 struct HashKey64 {
 277         HashKey64() {}
 278         HashKey64(const Value& value) : value(value) {}
 279
 280         uint32 GetHashCode() const
 281         {
 282                 uint64 v = (uint64)value;
 283                 return (uint32)(v >> 32) ^ (uint32)v;
 284         }
 285
 286         HashKey64<Value> operator=(const HashKey64<Value>& other)
 287         {
 288                 value = other.value;
 289                 return *this;
 290         }
 291
 292         bool operator==(const HashKey64<Value>& other) const
 293         {
 294                 return (value == other.value);
 295         }
 296
 297         bool operator!=(const HashKey64<Value>& other) const
 298         {
 299                 return (value != other.value);
 300         }
 301
 302         Value   value;
 303 };
 304
 305
 306 // HashKeyPointer
 307 template<typename Value>
 308 struct HashKeyPointer {
 309         HashKeyPointer() {}
 310         HashKeyPointer(const Value& value) : value(value) {}
 311
 312         uint32 GetHashCode() const
 313         {
 314 #if __HAIKU_ARCH_BITS == 32
 315                 return (uint32)(addr_t)value;
 316 #elif __HAIKU_ARCH_BITS == 64
 317                 uint64 v = (uint64)(addr_t)value;
 318                 return (uint32)(v >> 32) ^ (uint32)v;
 319 #else
 320                 #error unknown bitness
 321 #endif
 322         }
 323
 324         HashKeyPointer<Value> operator=(const HashKeyPointer<Value>& other)
 325         {
 326                 value = other.value;
 327                 return *this;
 328         }
 329
 330         bool operator==(const HashKeyPointer<Value>& other) const
 331         {
 332                 return (value == other.value);
 333         }
 334
 335         bool operator!=(const HashKeyPointer<Value>& other) const
 336         {
 337                 return (value != other.value);
 338         }
 339
 340         Value   value;
 341 };
 342
 343
 344 // HashMap
 345
 346 // constructor
 347 template<typename Key, typename Value>
 348 HashMap<Key, Value>::HashMap()
 349         :
 350         fTable()
 351 {
 352         fTable.Init();
 353 }
 354
 355
 356 // destructor
 357 template<typename Key, typename Value>
 358 HashMap<Key, Value>::~HashMap()
 359 {
 360         Clear();
 361 }
 362
 363
 364 // InitCheck
 365 template<typename Key, typename Value>
 366 status_t
 367 HashMap<Key, Value>::InitCheck() const
 368 {
 369         return (fTable.TableSize() > 0 ? B_OK : B_NO_MEMORY);
 370 }
 371
 372
 373 // Put
 374 template<typename Key, typename Value>
 375 status_t
 376 HashMap<Key, Value>::Put(const Key& key, const Value& value)
 377 {
 378         Element* element = fTable.Lookup(key);
 379         if (element) {
 380                 // already contains the key: just set the new value
 381                 element->fValue = value;
 382                 return B_OK;
 383         }
 384
 385         // does not contain the key yet: create an element and add it
 386         element = new(std::nothrow) Element(key, value);
 387         if (!element)
 388                 return B_NO_MEMORY;
 389
 390         status_t error = fTable.Insert(element);
 391         if (error != B_OK)
 392                 delete element;
 393
 394         return error;
 395 }
 396
 397
 398 // Remove
 399 template<typename Key, typename Value>
 400 Value
 401 HashMap<Key, Value>::Remove(const Key& key)
 402 {
 403         Element* element = fTable.Lookup(key);
 404         if (element == NULL)
 405                 return Value();
 406
 407         fTable.Remove(element);
 408         Value value = element->fValue;
 409         delete element;
 410
 411         return value;
 412 }
 413
 414
 415 // Clear
 416 template<typename Key, typename Value>
 417 void
 418 HashMap<Key, Value>::Clear()
 419 {
 420         // clear the table and delete the elements
 421         Element* element = fTable.Clear(true);
 422         while (element != NULL) {
 423                 Element* next = element->fNext;
 424                 delete element;
 425                 element = next;
 426         }
 427 }
 428
 429
 430 // Get
 431 template<typename Key, typename Value>
 432 Value
 433 HashMap<Key, Value>::Get(const Key& key) const
 434 {
 435         if (Element* element = fTable.Lookup(key))
 436                 return element->fValue;
 437         return Value();
 438 }
 439
 440
 441 // ContainsKey
 442 template<typename Key, typename Value>
 443 bool
 444 HashMap<Key, Value>::ContainsKey(const Key& key) const
 445 {
 446         return fTable.Lookup(key) != NULL;
 447 }
 448
 449
 450 // Size
 451 template<typename Key, typename Value>
 452 int32
 453 HashMap<Key, Value>::Size() const
 454 {
 455         return fTable.CountElements();
 456 }
 457
 458
 459 // GetIterator
 460 template<typename Key, typename Value>
 461 typename HashMap<Key, Value>::Iterator
 462 HashMap<Key, Value>::GetIterator()
 463 {
 464         return Iterator(this);
 465 }
 466
 467
 468 #endif  // HASH_MAP_H