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