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