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
15namespace BPrivate {
16
17
18// HashMapElement
19template<typename Key, typename Value>
20class HashMapElement {
21private:
22 typedef HashMapElement<Key, Value> Element;
23
24public:
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
48template<typename Key, typename Value>
49struct 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
65template<typename Key, typename Value>
66class HashMap {
67public:
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
148protected:
149 typedef BOpenHashTable<HashMapTableDefinition<Key, Value> > ElementTable;
150 typedef HashMapElement<Key, Value> Element;
151 friend class Iterator;
152
153protected:
154 ElementTable fTable;
155};
156
157
158// SynchronizedHashMap
159template<typename Key, typename Value, typename Locker = BLocker>
160class SynchronizedHashMap : public Locker {
161public:
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
237protected:
238 typedef AutoLocker<Locker> MapLocker;
239
240 HashMap<Key, Value> fMap;
241};
242
243// HashKey32
244template<typename Value>
245struct 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
275template<typename Value>
276struct 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
307template<typename Value>
308struct 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
347template<typename Key, typename Value>
348HashMap<Key, Value>::HashMap()
349 :
350 fTable()
351{
352 fTable.Init();
353}
354
355
356// destructor
357template<typename Key, typename Value>
358HashMap<Key, Value>::~HashMap()
359{
360 Clear();
361}
362
363
364// InitCheck
365template<typename Key, typename Value>
366status_t
367HashMap<Key, Value>::InitCheck() const
368{
369 return (fTable.TableSize() > 0 ? B_OK : B_NO_MEMORY);
370}
371
372
373// Put
374template<typename Key, typename Value>
375status_t
376HashMap<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
399template<typename Key, typename Value>
400Value
401HashMap<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
416template<typename Key, typename Value>
417Value
418HashMap<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
435template<typename Key, typename Value>
436void
437HashMap<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
450template<typename Key, typename Value>
451Value
452HashMap<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
461template<typename Key, typename Value>
462bool
463HashMap<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
474template<typename Key, typename Value>
475bool
476HashMap<Key, Value>::ContainsKey(const Key& key) const
477{
478 return fTable.Lookup(key) != NULL;
479}
480
481
482// Size
483template<typename Key, typename Value>
484int32
485HashMap<Key, Value>::Size() const
486{
487 return fTable.CountElements();
488}
489
490
491// GetIterator
492template<typename Key, typename Value>
493typename HashMap<Key, Value>::Iterator
494HashMap<Key, Value>::GetIterator() const
495{
496 return Iterator(this);
497}
498
499} // namespace BPrivate
500
501using BPrivate::HashMap;
502using BPrivate::HashKey32;
503using BPrivate::HashKey64;
504using BPrivate::HashKeyPointer;
505using BPrivate::SynchronizedHashMap;
506
507#endif // HASH_MAP_H
