HashMap.h revision cc54b43e
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()	{ 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	void Clear()
190	{
191		MapLocker locker(this);
192		fMap.Clear();
193	}
194
195	Value Get(const Key& key) const
196	{
197		const Locker* lock = this;
198		MapLocker locker(const_cast<Locker*>(lock));
199		if (!locker.IsLocked())
200			return Value();
201		return fMap.Get(key);
202	}
203
204	bool ContainsKey(const Key& key) const
205	{
206		const Locker* lock = this;
207		MapLocker locker(const_cast<Locker*>(lock));
208		if (!locker.IsLocked())
209			return false;
210		return fMap.ContainsKey(key);
211	}
212
213	int32 Size() const
214	{
215		const Locker* lock = this;
216		MapLocker locker(const_cast<Locker*>(lock));
217		return fMap.Size();
218	}
219
220	Iterator GetIterator()
221	{
222		return fMap.GetIterator();
223	}
224
225	// for debugging only
226	const HashMap<Key, Value>& GetUnsynchronizedMap() const	{ return fMap; }
227	HashMap<Key, Value>& GetUnsynchronizedMap()				{ return fMap; }
228
229protected:
230	typedef AutoLocker<Locker> MapLocker;
231
232	HashMap<Key, Value>	fMap;
233};
234
235// HashKey32
236template<typename Value>
237struct HashKey32 {
238	HashKey32() {}
239	HashKey32(const Value& value) : value(value) {}
240
241	uint32 GetHashCode() const
242	{
243		return (uint32)value;
244	}
245
246	HashKey32<Value> operator=(const HashKey32<Value>& other)
247	{
248		value = other.value;
249		return *this;
250	}
251
252	bool operator==(const HashKey32<Value>& other) const
253	{
254		return (value == other.value);
255	}
256
257	bool operator!=(const HashKey32<Value>& other) const
258	{
259		return (value != other.value);
260	}
261
262	Value	value;
263};
264
265
266// HashKey64
267template<typename Value>
268struct HashKey64 {
269	HashKey64() {}
270	HashKey64(const Value& value) : value(value) {}
271
272	uint32 GetHashCode() const
273	{
274		uint64 v = (uint64)value;
275		return (uint32)(v >> 32) ^ (uint32)v;
276	}
277
278	HashKey64<Value> operator=(const HashKey64<Value>& other)
279	{
280		value = other.value;
281		return *this;
282	}
283
284	bool operator==(const HashKey64<Value>& other) const
285	{
286		return (value == other.value);
287	}
288
289	bool operator!=(const HashKey64<Value>& other) const
290	{
291		return (value != other.value);
292	}
293
294	Value	value;
295};
296
297
298// HashKeyPointer
299template<typename Value>
300struct HashKeyPointer {
301	HashKeyPointer() {}
302	HashKeyPointer(const Value& value) : value(value) {}
303
304	uint32 GetHashCode() const
305	{
306#if __HAIKU_ARCH_BITS == 32
307		return (uint32)(addr_t)value;
308#elif __HAIKU_ARCH_BITS == 64
309		uint64 v = (uint64)(addr_t)value;
310		return (uint32)(v >> 32) ^ (uint32)v;
311#else
312		#error unknown bitness
313#endif
314	}
315
316	HashKeyPointer<Value> operator=(const HashKeyPointer<Value>& other)
317	{
318		value = other.value;
319		return *this;
320	}
321
322	bool operator==(const HashKeyPointer<Value>& other) const
323	{
324		return (value == other.value);
325	}
326
327	bool operator!=(const HashKeyPointer<Value>& other) const
328	{
329		return (value != other.value);
330	}
331
332	Value	value;
333};
334
335
336// HashMap
337
338// constructor
339template<typename Key, typename Value>
340HashMap<Key, Value>::HashMap()
341	:
342	fTable()
343{
344	fTable.Init();
345}
346
347
348// destructor
349template<typename Key, typename Value>
350HashMap<Key, Value>::~HashMap()
351{
352	Clear();
353}
354
355
356// InitCheck
357template<typename Key, typename Value>
358status_t
359HashMap<Key, Value>::InitCheck() const
360{
361	return (fTable.TableSize() > 0 ? B_OK : B_NO_MEMORY);
362}
363
364
365// Put
366template<typename Key, typename Value>
367status_t
368HashMap<Key, Value>::Put(const Key& key, const Value& value)
369{
370	Element* element = fTable.Lookup(key);
371	if (element) {
372		// already contains the key: just set the new value
373		element->fValue = value;
374		return B_OK;
375	}
376
377	// does not contain the key yet: create an element and add it
378	element = new(std::nothrow) Element(key, value);
379	if (!element)
380		return B_NO_MEMORY;
381
382	status_t error = fTable.Insert(element);
383	if (error != B_OK)
384		delete element;
385
386	return error;
387}
388
389
390// Remove
391template<typename Key, typename Value>
392Value
393HashMap<Key, Value>::Remove(const Key& key)
394{
395	Element* element = fTable.Lookup(key);
396	if (element == NULL)
397		return Value();
398
399	fTable.Remove(element);
400	Value value = element->fValue;
401	delete element;
402
403	return value;
404}
405
406
407// Remove
408template<typename Key, typename Value>
409Value
410HashMap<Key, Value>::Remove(Iterator& it)
411{
412	Element* element = it.fElement;
413	if (element == NULL)
414		return Value();
415
416	Value value = element->fValue;
417
418	fTable.RemoveUnchecked(element);
419	delete element;
420	it.fElement = NULL;
421
422	return value;
423}
424
425
426// Clear
427template<typename Key, typename Value>
428void
429HashMap<Key, Value>::Clear()
430{
431	// clear the table and delete the elements
432	Element* element = fTable.Clear(true);
433	while (element != NULL) {
434		Element* next = element->fNext;
435		delete element;
436		element = next;
437	}
438}
439
440
441// Get
442template<typename Key, typename Value>
443Value
444HashMap<Key, Value>::Get(const Key& key) const
445{
446	if (Element* element = fTable.Lookup(key))
447		return element->fValue;
448	return Value();
449}
450
451
452// Get
453template<typename Key, typename Value>
454bool
455HashMap<Key, Value>::Get(const Key& key, Value*& _value) const
456{
457	if (Element* element = fTable.Lookup(key)) {
458		_value = &element->fValue;
459		return true;
460	}
461	return false;
462}
463
464
465// ContainsKey
466template<typename Key, typename Value>
467bool
468HashMap<Key, Value>::ContainsKey(const Key& key) const
469{
470	return fTable.Lookup(key) != NULL;
471}
472
473
474// Size
475template<typename Key, typename Value>
476int32
477HashMap<Key, Value>::Size() const
478{
479	return fTable.CountElements();
480}
481
482
483// GetIterator
484template<typename Key, typename Value>
485typename HashMap<Key, Value>::Iterator
486HashMap<Key, Value>::GetIterator() const
487{
488	return Iterator(this);
489}
490
491} // namespace BPrivate
492
493using BPrivate::HashMap;
494using BPrivate::HashKey32;
495using BPrivate::HashKey64;
496using BPrivate::HashKeyPointer;
497using BPrivate::SynchronizedHashMap;
498
499#endif	// HASH_MAP_H
500