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
508