1// HashMap.h
2//
3// Copyright (c) 2004-2007, Ingo Weinhold (bonefish@cs.tu-berlin.de)
4//
5// Permission is hereby granted, free of charge, to any person obtaining a
6// copy of this software and associated documentation files (the "Software"),
7// to deal in the Software without restriction, including without limitation
8// the rights to use, copy, modify, merge, publish, distribute, sublicense,
9// and/or sell copies of the Software, and to permit persons to whom the
10// Software is furnished to do so, subject to the following conditions:
11//
12// The above copyright notice and this permission notice shall be included in
13// all copies or substantial portions of the Software.
14//
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21// DEALINGS IN THE SOFTWARE.
22//
23// Except as contained in this notice, the name of a copyright holder shall
24// not be used in advertising or otherwise to promote the sale, use or other
25// dealings in this Software without prior written authorization of the
26// copyright holder.
27
28#ifndef HASH_MAP_H
29#define HASH_MAP_H
30
31
32#include <Locker.h>
33
34#include "AutoLocker.h"
35#include "OpenHashTable.h"
36
37
38namespace BPrivate {
39
40// HashMapElement
41template<typename Key, typename Value>
42class HashMapElement : public OpenHashElement {
43private:
44	typedef HashMapElement<Key, Value> Element;
45public:
46
47	HashMapElement() : OpenHashElement(), fKey(), fValue()
48	{
49		fNext = -1;
50	}
51
52	inline uint32 Hash() const
53	{
54		return fKey.GetHashCode();
55	}
56
57	inline bool operator==(const OpenHashElement &_element) const
58	{
59		const Element &element = static_cast<const Element&>(_element);
60		return (fKey == element.fKey);
61	}
62
63	inline void Adopt(Element &element)
64	{
65		fKey = element.fKey;
66		fValue = element.fValue;
67	}
68
69	Key		fKey;
70	Value	fValue;
71};
72
73// HashMap
74template<typename Key, typename Value>
75class HashMap {
76public:
77	class Entry {
78	public:
79		Entry() {}
80		Entry(const Key& key, Value value) : key(key), value(value) {}
81
82		Key		key;
83		Value	value;
84	};
85
86	class Iterator {
87	private:
88		typedef HashMapElement<Key, Value>	Element;
89	public:
90		Iterator(const Iterator& other)
91			:
92			fMap(other.fMap),
93			fIndex(other.fIndex),
94			fElement(other.fElement),
95			fLastElement(other.fElement)
96		{
97		}
98
99		bool HasNext() const
100		{
101			return fElement;
102		}
103
104		Entry Next()
105		{
106			if (!fElement)
107				return Entry();
108			Entry result(fElement->fKey, fElement->fValue);
109			_FindNext();
110			return result;
111		}
112
113		Value* NextValue()
114		{
115			if (fElement == NULL)
116				return NULL;
117
118			Value* value = &fElement->fValue;
119			_FindNext();
120			return value;
121		}
122
123		Entry Remove()
124		{
125			if (!fLastElement)
126				return Entry();
127			Entry result(fLastElement->fKey, fLastElement->fValue);
128			fMap->fTable.Remove(fLastElement, true);
129			fLastElement = NULL;
130			return result;
131		}
132
133		Iterator& operator=(const Iterator& other)
134		{
135			fMap = other.fMap;
136			fIndex = other.fIndex;
137			fElement = other.fElement;
138			fLastElement = other.fLastElement;
139			return *this;
140		}
141
142	private:
143		Iterator(const HashMap<Key, Value>* map)
144			:
145			fMap(const_cast<HashMap<Key, Value>*>(map)),
146			fIndex(0),
147			fElement(NULL),
148			fLastElement(NULL)
149		{
150			// find first
151			_FindNext();
152		}
153
154		void _FindNext()
155		{
156			fLastElement = fElement;
157			if (fElement && fElement->fNext >= 0) {
158				fElement = fMap->fTable.ElementAt(fElement->fNext);
159				return;
160			}
161			fElement = NULL;
162			int32 arraySize = fMap->fTable.ArraySize();
163			for (; !fElement && fIndex < arraySize; fIndex++)
164				fElement = fMap->fTable.FindFirst(fIndex);
165		}
166
167	private:
168		friend class HashMap<Key, Value>;
169
170		HashMap<Key, Value>*	fMap;
171		int32					fIndex;
172		Element*				fElement;
173		Element*				fLastElement;
174	};
175
176	HashMap();
177	~HashMap();
178
179	status_t InitCheck() const;
180
181	status_t Put(const Key& key, Value value);
182	Value Remove(const Key& key);
183	void Clear();
184	Value Get(const Key& key) const;
185	bool Get(const Key& key, Value*& _value) const;
186
187	bool ContainsKey(const Key& key) const;
188
189	int32 Size() const;
190
191	Iterator GetIterator() const;
192
193protected:
194	typedef HashMapElement<Key, Value>	Element;
195	friend class Iterator;
196
197private:
198	Element *_FindElement(const Key& key) const;
199
200protected:
201	OpenHashElementArray<Element>							fElementArray;
202	OpenHashTable<Element, OpenHashElementArray<Element> >	fTable;
203};
204
205// SynchronizedHashMap
206template<typename Key, typename Value>
207class SynchronizedHashMap : public BLocker {
208public:
209	typedef struct HashMap<Key, Value>::Entry Entry;
210	typedef struct HashMap<Key, Value>::Iterator Iterator;
211
212	SynchronizedHashMap() : BLocker("synchronized hash map")	{}
213	~SynchronizedHashMap()	{ Lock(); }
214
215	status_t InitCheck() const
216	{
217		return fMap.InitCheck();
218	}
219
220	status_t Put(const Key& key, Value value)
221	{
222		MapLocker locker(this);
223		if (!locker.IsLocked())
224			return B_ERROR;
225		return fMap.Put(key, value);
226	}
227
228	Value Remove(const Key& key)
229	{
230		MapLocker locker(this);
231		if (!locker.IsLocked())
232			return Value();
233		return fMap.Remove(key);
234	}
235
236	void Clear()
237	{
238		MapLocker locker(this);
239		fMap.Clear();
240	}
241
242	Value Get(const Key& key) const
243	{
244		const BLocker* lock = this;
245		MapLocker locker(const_cast<BLocker*>(lock));
246		if (!locker.IsLocked())
247			return Value();
248		return fMap.Get(key);
249	}
250
251	bool ContainsKey(const Key& key) const
252	{
253		const BLocker* lock = this;
254		MapLocker locker(const_cast<BLocker*>(lock));
255		if (!locker.IsLocked())
256			return false;
257		return fMap.ContainsKey(key);
258	}
259
260	int32 Size() const
261	{
262		const BLocker* lock = this;
263		MapLocker locker(const_cast<BLocker*>(lock));
264		return fMap.Size();
265	}
266
267	Iterator GetIterator()
268	{
269		return fMap.GetIterator();
270	}
271
272	// for debugging only
273	const HashMap<Key, Value>& GetUnsynchronizedMap() const	{ return fMap; }
274	HashMap<Key, Value>& GetUnsynchronizedMap()				{ return fMap; }
275
276protected:
277	typedef AutoLocker<BLocker> MapLocker;
278
279	HashMap<Key, Value>	fMap;
280};
281
282// HashKey32
283template<typename Value>
284struct HashKey32 {
285	HashKey32() {}
286	HashKey32(const Value& value) : value(value) {}
287
288	uint32 GetHashCode() const
289	{
290		return (uint32)value;
291	}
292
293	HashKey32<Value> operator=(const HashKey32<Value>& other)
294	{
295		value = other.value;
296		return *this;
297	}
298
299	bool operator==(const HashKey32<Value>& other) const
300	{
301		return (value == other.value);
302	}
303
304	bool operator!=(const HashKey32<Value>& other) const
305	{
306		return (value != other.value);
307	}
308
309	Value	value;
310};
311
312
313// HashKey64
314template<typename Value>
315struct HashKey64 {
316	HashKey64() {}
317	HashKey64(const Value& value) : value(value) {}
318
319	uint32 GetHashCode() const
320	{
321		uint64 v = (uint64)value;
322		return (uint32)(v >> 32) ^ (uint32)v;
323	}
324
325	HashKey64<Value> operator=(const HashKey64<Value>& other)
326	{
327		value = other.value;
328		return *this;
329	}
330
331	bool operator==(const HashKey64<Value>& other) const
332	{
333		return (value == other.value);
334	}
335
336	bool operator!=(const HashKey64<Value>& other) const
337	{
338		return (value != other.value);
339	}
340
341	Value	value;
342};
343
344
345// HashMap
346
347// constructor
348template<typename Key, typename Value>
349HashMap<Key, Value>::HashMap()
350	:
351	fElementArray(1000),
352	fTable(1000, &fElementArray)
353{
354}
355
356// destructor
357template<typename Key, typename Value>
358HashMap<Key, Value>::~HashMap()
359{
360}
361
362// InitCheck
363template<typename Key, typename Value>
364status_t
365HashMap<Key, Value>::InitCheck() const
366{
367	return (fTable.InitCheck() && fElementArray.InitCheck()
368			? B_OK : B_NO_MEMORY);
369}
370
371// Put
372template<typename Key, typename Value>
373status_t
374HashMap<Key, Value>::Put(const Key& key, Value value)
375{
376	Element* element = _FindElement(key);
377	if (element) {
378		// already contains the key: just set the new value
379		element->fValue = value;
380		return B_OK;
381	}
382	// does not contain the key yet: add an element
383	element = fTable.Add(key.GetHashCode());
384	if (!element)
385		return B_NO_MEMORY;
386	element->fKey = key;
387	element->fValue = value;
388	return B_OK;
389}
390
391// Remove
392template<typename Key, typename Value>
393Value
394HashMap<Key, Value>::Remove(const Key& key)
395{
396	Value value = Value();
397	if (Element* element = _FindElement(key)) {
398		value = element->fValue;
399		fTable.Remove(element);
400	}
401	return value;
402}
403
404// Clear
405template<typename Key, typename Value>
406void
407HashMap<Key, Value>::Clear()
408{
409	fTable.RemoveAll();
410}
411
412// Get
413template<typename Key, typename Value>
414Value
415HashMap<Key, Value>::Get(const Key& key) const
416{
417	if (Element* element = _FindElement(key))
418		return element->fValue;
419	return Value();
420}
421
422// Get
423template<typename Key, typename Value>
424bool
425HashMap<Key, Value>::Get(const Key& key, Value*& _value) const
426{
427	if (Element* element = _FindElement(key)) {
428		_value = &element->fValue;
429		return true;
430	}
431
432	return false;
433}
434
435// ContainsKey
436template<typename Key, typename Value>
437bool
438HashMap<Key, Value>::ContainsKey(const Key& key) const
439{
440	return _FindElement(key);
441}
442
443// Size
444template<typename Key, typename Value>
445int32
446HashMap<Key, Value>::Size() const
447{
448	return fTable.CountElements();
449}
450
451// GetIterator
452template<typename Key, typename Value>
453struct HashMap<Key, Value>::Iterator
454HashMap<Key, Value>::GetIterator() const
455{
456	return Iterator(this);
457}
458
459// _FindElement
460template<typename Key, typename Value>
461typename HashMap<Key, Value>::Element *
462HashMap<Key, Value>::_FindElement(const Key& key) const
463{
464	Element* element = fTable.FindFirst(key.GetHashCode());
465	while (element && element->fKey != key) {
466		if (element->fNext >= 0)
467			element = fTable.ElementAt(element->fNext);
468		else
469			element = NULL;
470	}
471	return element;
472}
473
474}	// namespace BPrivate
475
476using BPrivate::HashMap;
477using BPrivate::HashKey32;
478using BPrivate::HashKey64;
479using BPrivate::SynchronizedHashMap;
480
481#endif	// HASH_MAP_H
482