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