1 /* 2 * Copyright 2004-2009, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * Copyright 2019, Haiku, Inc. All rights reserved. 4 * Distributed under the terms of the MIT License. 5 */ 6 #ifndef HASH_MAP_H 7 #define HASH_MAP_H 8 9 #include <OpenHashTable.h> 10 #include <Locker.h> 11 12 #include "AutoLocker.h" 13 14 15 namespace BPrivate { 16 17 18 // HashMapElement 19 template<typename Key, typename Value> 20 class HashMapElement { 21 private: 22 typedef HashMapElement<Key, Value> Element; 23 24 public: 25 HashMapElement() 26 : 27 fKey(), 28 fValue(), 29 fNext(NULL) 30 { 31 } 32 33 HashMapElement(const Key& key, const Value& value) 34 : 35 fKey(key), 36 fValue(value), 37 fNext(NULL) 38 { 39 } 40 41 Key fKey; 42 Value fValue; 43 HashMapElement* fNext; 44 }; 45 46 47 // HashMapTableDefinition 48 template<typename Key, typename Value> 49 struct HashMapTableDefinition { 50 typedef Key KeyType; 51 typedef HashMapElement<Key, Value> ValueType; 52 53 size_t HashKey(const KeyType& key) const 54 { return key.GetHashCode(); } 55 size_t Hash(const ValueType* value) const 56 { return HashKey(value->fKey); } 57 bool Compare(const KeyType& key, const ValueType* value) const 58 { return value->fKey == key; } 59 ValueType*& GetLink(ValueType* value) const 60 { return value->fNext; } 61 }; 62 63 64 // HashMap 65 template<typename Key, typename Value> 66 class HashMap { 67 public: 68 class Entry { 69 public: 70 Entry() {} 71 Entry(const Key& key, Value value) : key(key), value(value) {} 72 73 Key key; 74 Value value; 75 }; 76 77 class Iterator { 78 private: 79 typedef HashMapElement<Key, Value> Element; 80 public: 81 Iterator(const Iterator& other) 82 : 83 fMap(other.fMap), 84 fIterator(other.fIterator), 85 fElement(other.fElement) 86 { 87 } 88 89 bool HasNext() const 90 { 91 return fIterator.HasNext(); 92 } 93 94 Entry Next() 95 { 96 fElement = fIterator.Next(); 97 if (fElement == NULL) 98 return Entry(); 99 100 return Entry(fElement->fKey, fElement->fValue); 101 } 102 103 Iterator& operator=(const Iterator& other) 104 { 105 fMap = other.fMap; 106 fIterator = other.fIterator; 107 fElement = other.fElement; 108 return *this; 109 } 110 111 private: 112 Iterator(const HashMap<Key, Value>* map) 113 : 114 fMap(map), 115 fIterator(map->fTable.GetIterator()), 116 fElement(NULL) 117 { 118 } 119 120 private: 121 friend class HashMap<Key, Value>; 122 typedef BOpenHashTable<HashMapTableDefinition<Key, Value> > 123 ElementTable; 124 125 const HashMap<Key, Value>* fMap; 126 typename ElementTable::Iterator fIterator; 127 Element* fElement; 128 }; 129 130 HashMap(); 131 ~HashMap(); 132 133 status_t InitCheck() const; 134 135 status_t Put(const Key& key, const Value& value); 136 Value Remove(const Key& key); 137 Value Remove(Iterator& it); 138 void Clear(); 139 Value Get(const Key& key) const; 140 bool Get(const Key& key, Value*& _value) const; 141 142 bool ContainsKey(const Key& key) const; 143 144 int32 Size() const; 145 146 Iterator GetIterator() const; 147 148 protected: 149 typedef BOpenHashTable<HashMapTableDefinition<Key, Value> > ElementTable; 150 typedef HashMapElement<Key, Value> Element; 151 friend class Iterator; 152 153 protected: 154 ElementTable fTable; 155 }; 156 157 158 // SynchronizedHashMap 159 template<typename Key, typename Value, typename Locker = BLocker> 160 class SynchronizedHashMap : public Locker { 161 public: 162 typedef typename HashMap<Key, Value>::Entry Entry; 163 typedef typename HashMap<Key, Value>::Iterator Iterator; 164 165 SynchronizedHashMap() : Locker("synchronized hash map") {} 166 ~SynchronizedHashMap() { Locker::Lock(); } 167 168 status_t InitCheck() const 169 { 170 return fMap.InitCheck(); 171 } 172 173 status_t Put(const Key& key, const Value& value) 174 { 175 MapLocker locker(this); 176 if (!locker.IsLocked()) 177 return B_ERROR; 178 return fMap.Put(key, value); 179 } 180 181 Value Remove(const Key& key) 182 { 183 MapLocker locker(this); 184 if (!locker.IsLocked()) 185 return Value(); 186 return fMap.Remove(key); 187 } 188 189 Value Remove(Iterator& it) 190 { 191 MapLocker locker(this); 192 if (!locker.IsLocked()) 193 return Value(); 194 return fMap.Remove(it); 195 } 196 197 void Clear() 198 { 199 MapLocker locker(this); 200 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 // Remove 416 template<typename Key, typename Value> 417 Value 418 HashMap<Key, Value>::Remove(Iterator& it) 419 { 420 Element* element = it.fElement; 421 if (element == NULL) 422 return Value(); 423 424 Value value = element->fValue; 425 426 fTable.RemoveUnchecked(element); 427 delete element; 428 it.fElement = NULL; 429 430 return value; 431 } 432 433 434 // Clear 435 template<typename Key, typename Value> 436 void 437 HashMap<Key, Value>::Clear() 438 { 439 // clear the table and delete the elements 440 Element* element = fTable.Clear(true); 441 while (element != NULL) { 442 Element* next = element->fNext; 443 delete element; 444 element = next; 445 } 446 } 447 448 449 // Get 450 template<typename Key, typename Value> 451 Value 452 HashMap<Key, Value>::Get(const Key& key) const 453 { 454 if (Element* element = fTable.Lookup(key)) 455 return element->fValue; 456 return Value(); 457 } 458 459 460 // Get 461 template<typename Key, typename Value> 462 bool 463 HashMap<Key, Value>::Get(const Key& key, Value*& _value) const 464 { 465 if (Element* element = fTable.Lookup(key)) { 466 _value = &element->fValue; 467 return true; 468 } 469 return false; 470 } 471 472 473 // ContainsKey 474 template<typename Key, typename Value> 475 bool 476 HashMap<Key, Value>::ContainsKey(const Key& key) const 477 { 478 return fTable.Lookup(key) != NULL; 479 } 480 481 482 // Size 483 template<typename Key, typename Value> 484 int32 485 HashMap<Key, Value>::Size() const 486 { 487 return fTable.CountElements(); 488 } 489 490 491 // GetIterator 492 template<typename Key, typename Value> 493 typename HashMap<Key, Value>::Iterator 494 HashMap<Key, Value>::GetIterator() const 495 { 496 return Iterator(this); 497 } 498 499 } // namespace BPrivate 500 501 using BPrivate::HashMap; 502 using BPrivate::HashKey32; 503 using BPrivate::HashKey64; 504 using BPrivate::HashKeyPointer; 505 using BPrivate::SynchronizedHashMap; 506 507 #endif // HASH_MAP_H 508