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:
HashMapElement()25 HashMapElement()
26 :
27 fKey(),
28 fValue(),
29 fNext(NULL)
30 {
31 }
32
HashMapElement(const Key & key,const Value & value)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
HashKeyHashMapTableDefinition53 size_t HashKey(const KeyType& key) const
54 { return key.GetHashCode(); }
HashHashMapTableDefinition55 size_t Hash(const ValueType* value) const
56 { return HashKey(value->fKey); }
CompareHashMapTableDefinition57 bool Compare(const KeyType& key, const ValueType* value) const
58 { return value->fKey == key; }
GetLinkHashMapTableDefinition59 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:
Entry()70 Entry() {}
Entry(const Key & key,Value value)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:
Iterator(const Iterator & other)81 Iterator(const Iterator& other)
82 :
83 fMap(other.fMap),
84 fIterator(other.fIterator),
85 fElement(other.fElement)
86 {
87 }
88
HasNext()89 bool HasNext() const
90 {
91 return fIterator.HasNext();
92 }
93
Next()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:
Iterator(const HashMap<Key,Value> * map)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
SynchronizedHashMap()165 SynchronizedHashMap() : Locker("synchronized hash map") {}
~SynchronizedHashMap()166 ~SynchronizedHashMap() { Locker::Lock(); }
167
InitCheck()168 status_t InitCheck() const
169 {
170 return fMap.InitCheck();
171 }
172
Put(const Key & key,const Value & value)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
Remove(const Key & key)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
Remove(Iterator & it)189 Value Remove(Iterator& it)
190 {
191 MapLocker locker(this);
192 if (!locker.IsLocked())
193 return Value();
194 return fMap.Remove(it);
195 }
196
Clear()197 void Clear()
198 {
199 MapLocker locker(this);
200 fMap.Clear();
201 }
202
Get(const Key & key)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
ContainsKey(const Key & key)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
Size()221 int32 Size() const
222 {
223 const Locker* lock = this;
224 MapLocker locker(const_cast<Locker*>(lock));
225 return fMap.Size();
226 }
227
GetIterator()228 Iterator GetIterator()
229 {
230 return fMap.GetIterator();
231 }
232
233 // for debugging only
GetUnsynchronizedMap()234 const HashMap<Key, Value>& GetUnsynchronizedMap() const { return fMap; }
GetUnsynchronizedMap()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 {
HashKey32HashKey32246 HashKey32() {}
HashKey32HashKey32247 HashKey32(const Value& value) : value(value) {}
248
GetHashCodeHashKey32249 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 {
HashKey64HashKey64277 HashKey64() {}
HashKey64HashKey64278 HashKey64(const Value& value) : value(value) {}
279
GetHashCodeHashKey64280 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 {
HashKeyPointerHashKeyPointer309 HashKeyPointer() {}
HashKeyPointerHashKeyPointer310 HashKeyPointer(const Value& value) : value(value) {}
311
GetHashCodeHashKeyPointer312 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>
HashMap()348 HashMap<Key, Value>::HashMap()
349 :
350 fTable()
351 {
352 fTable.Init();
353 }
354
355
356 // destructor
357 template<typename Key, typename Value>
~HashMap()358 HashMap<Key, Value>::~HashMap()
359 {
360 Clear();
361 }
362
363
364 // InitCheck
365 template<typename Key, typename Value>
366 status_t
InitCheck()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
Put(const Key & key,const Value & value)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
Remove(const Key & key)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
Remove(Iterator & it)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
Clear()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
Get(const Key & key)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
Get(const Key & key,Value * & _value)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
ContainsKey(const Key & key)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
Size()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
GetIterator()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