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