1// HashMap.h
2//
3// Copyright (c) 2004, 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//#include <Debug.h>
32
33#include "AutoLocker.h"
34#include "Locker.h"
35#include "OpenHashTable.h"
36
37// HashMapElement
38template<typename Key, typename Value>
39class HashMapElement : public OpenHashElement {
40private:
41	typedef HashMapElement<Key, Value> Element;
42public:
43
44	HashMapElement() : OpenHashElement(), fKey(), fValue()
45	{
46		fNext = -1;
47	}
48
49	inline uint32 Hash() const
50	{
51		return fKey.GetHashCode();
52	}
53
54	inline bool operator==(const OpenHashElement &_element) const
55	{
56		const Element &element = static_cast<const Element&>(_element);
57		return (fKey == element.fKey);
58	}
59
60	inline void Adopt(Element &element)
61	{
62		fKey = element.fKey;
63		fValue = element.fValue;
64	}
65
66	Key		fKey;
67	Value	fValue;
68};
69
70// HashMap
71template<typename Key, typename Value>
72class HashMap {
73public:
74	class Entry {
75	public:
76		Entry() {}
77		Entry(const Key& key, Value value) : key(key), value(value) {}
78
79		Key		key;
80		Value	value;
81	};
82
83	class Iterator {
84	private:
85		typedef HashMapElement<Key, Value>	Element;
86	public:
87		Iterator(const Iterator& other)
88			: fMap(other.fMap),
89			  fIndex(other.fIndex),
90			  fElement(other.fElement),
91			  fLastElement(other.fElement)
92		{
93		}
94
95		bool HasNext() const
96		{
97			return fElement;
98		}
99
100		Entry Next()
101		{
102			if (!fElement)
103				return Entry();
104			Entry result(fElement->fKey, fElement->fValue);
105			_FindNext();
106			return result;
107		}
108
109		Entry Remove()
110		{
111			if (!fLastElement)
112				return Entry();
113			Entry result(fLastElement->fKey, fLastElement->fValue);
114			fMap->fTable.Remove(fLastElement, true);
115			fLastElement = NULL;
116			return result;
117		}
118
119		Iterator& operator=(const Iterator& other)
120		{
121			fMap = other.fMap;
122			fIndex = other.fIndex;
123			fElement = other.fElement;
124			fLastElement = other.fLastElement;
125			return *this;
126		}
127
128	private:
129		Iterator(HashMap<Key, Value>* map)
130			: fMap(map),
131			  fIndex(0),
132			  fElement(NULL),
133			  fLastElement(NULL)
134		{
135			// find first
136			_FindNext();
137		}
138
139		void _FindNext()
140		{
141			fLastElement = fElement;
142			if (fElement && fElement->fNext >= 0) {
143				fElement = fMap->fTable.ElementAt(fElement->fNext);
144				return;
145			}
146			fElement = NULL;
147			int32 arraySize = fMap->fTable.ArraySize();
148			for (; !fElement && fIndex < arraySize; fIndex++)
149				fElement = fMap->fTable.FindFirst(fIndex);
150		}
151
152	private:
153		friend class HashMap<Key, Value>;
154
155		HashMap<Key, Value>*	fMap;
156		int32					fIndex;
157		Element*				fElement;
158		Element*				fLastElement;
159	};
160
161	HashMap();
162	~HashMap();
163
164	status_t InitCheck() const;
165
166	status_t Put(const Key& key, Value value);
167	Value Remove(const Key& key);
168	void Clear();
169	Value Get(const Key& key) const;
170
171	bool ContainsKey(const Key& key) const;
172
173	int32 Size() const;
174
175	Iterator GetIterator();
176
177protected:
178	typedef HashMapElement<Key, Value>	Element;
179	friend class Iterator;
180
181private:
182	Element *_FindElement(const Key& key) const;
183
184protected:
185	OpenHashElementArray<Element>							fElementArray;
186	OpenHashTable<Element, OpenHashElementArray<Element> >	fTable;
187};
188
189// SynchronizedHashMap
190template<typename Key, typename Value>
191class SynchronizedHashMap : public Locker {
192public:
193	typedef HashMap<Key, Value>::Entry Entry;
194	typedef HashMap<Key, Value>::Iterator Iterator;
195
196	SynchronizedHashMap() : Locker("synchronized hash map")	{}
197	~SynchronizedHashMap()	{ Lock(); }
198
199	status_t InitCheck() const
200	{
201		return fMap.InitCheck();
202	}
203
204	status_t Put(const Key& key, Value value)
205	{
206		MapLocker locker(this);
207		if (!locker.IsLocked())
208			return B_ERROR;
209		return fMap.Put(key, value);
210	}
211
212	Value Remove(const Key& key)
213	{
214		MapLocker locker(this);
215		if (!locker.IsLocked())
216			return Value();
217		return fMap.Remove(key);
218	}
219
220	void Clear()
221	{
222		MapLocker locker(this);
223		return fMap.Clear();
224	}
225
226	Value Get(const Key& key) const
227	{
228		const Locker* lock = this;
229		MapLocker locker(const_cast<Locker*>(lock));
230		if (!locker.IsLocked())
231			return Value();
232		return fMap.Get(key);
233	}
234
235	bool ContainsKey(const Key& key) const
236	{
237		const Locker* lock = this;
238		MapLocker locker(const_cast<Locker*>(lock));
239		if (!locker.IsLocked())
240			return false;
241		return fMap.ContainsKey(key);
242	}
243
244	int32 Size() const
245	{
246		const Locker* lock = this;
247		MapLocker locker(const_cast<Locker*>(lock));
248		return fMap.Size();
249	}
250
251	Iterator GetIterator()
252	{
253		return fMap.GetIterator();
254	}
255
256	// for debugging only
257	const HashMap<Key, Value>& GetUnsynchronizedMap() const	{ return fMap; }
258	HashMap<Key, Value>& GetUnsynchronizedMap()				{ return fMap; }
259
260protected:
261	typedef AutoLocker<Locker> MapLocker;
262
263	HashMap<Key, Value>	fMap;
264};
265
266// HashKey32
267template<typename Value>
268struct HashKey32 {
269	HashKey32() {}
270	HashKey32(const Value& value) : value(value) {}
271
272	uint32 GetHashCode() const
273	{
274		return (uint32)value;
275	}
276
277	HashKey32<Value> operator=(const HashKey32<Value>& other)
278	{
279		value = other.value;
280		return *this;
281	}
282
283	bool operator==(const HashKey32<Value>& other) const
284	{
285		return (value == other.value);
286	}
287
288	bool operator!=(const HashKey32<Value>& other) const
289	{
290		return (value != other.value);
291	}
292
293	Value	value;
294};
295
296
297// HashKey64
298template<typename Value>
299struct HashKey64 {
300	HashKey64() {}
301	HashKey64(const Value& value) : value(value) {}
302
303	uint32 GetHashCode() const
304	{
305		uint64 v = (uint64)value;
306		return (uint32)(v >> 32) ^ (uint32)v;
307	}
308
309	HashKey64<Value> operator=(const HashKey64<Value>& other)
310	{
311		value = other.value;
312		return *this;
313	}
314
315	bool operator==(const HashKey64<Value>& other) const
316	{
317		return (value == other.value);
318	}
319
320	bool operator!=(const HashKey64<Value>& other) const
321	{
322		return (value != other.value);
323	}
324
325	Value	value;
326};
327
328
329// HashMap
330
331// constructor
332template<typename Key, typename Value>
333HashMap<Key, Value>::HashMap()
334	: fElementArray(1000),
335	  fTable(1000, &fElementArray)
336{
337}
338
339// destructor
340template<typename Key, typename Value>
341HashMap<Key, Value>::~HashMap()
342{
343}
344
345// InitCheck
346template<typename Key, typename Value>
347status_t
348HashMap<Key, Value>::InitCheck() const
349{
350	return (fTable.InitCheck() && fElementArray.InitCheck()
351			? B_OK : B_NO_MEMORY);
352}
353
354// Put
355template<typename Key, typename Value>
356status_t
357HashMap<Key, Value>::Put(const Key& key, Value value)
358{
359	Element* element = _FindElement(key);
360	if (element) {
361		// already contains the key: just set the new value
362		element->fValue = value;
363		return B_OK;
364	}
365	// does not contain the key yet: add an element
366	element = fTable.Add(key.GetHashCode());
367	if (!element)
368		return B_NO_MEMORY;
369	element->fKey = key;
370	element->fValue = value;
371	return B_OK;
372}
373
374// Remove
375template<typename Key, typename Value>
376Value
377HashMap<Key, Value>::Remove(const Key& key)
378{
379	Value value = Value();
380	if (Element* element = _FindElement(key)) {
381		value = element->fValue;
382		fTable.Remove(element);
383	}
384	return value;
385}
386
387// Clear
388template<typename Key, typename Value>
389void
390HashMap<Key, Value>::Clear()
391{
392	fTable.RemoveAll();
393}
394
395// Get
396template<typename Key, typename Value>
397Value
398HashMap<Key, Value>::Get(const Key& key) const
399{
400	if (Element* element = _FindElement(key))
401		return element->fValue;
402	return Value();
403}
404
405// ContainsKey
406template<typename Key, typename Value>
407bool
408HashMap<Key, Value>::ContainsKey(const Key& key) const
409{
410	return _FindElement(key);
411}
412
413// Size
414template<typename Key, typename Value>
415int32
416HashMap<Key, Value>::Size() const
417{
418	return fTable.CountElements();
419}
420
421// GetIterator
422template<typename Key, typename Value>
423HashMap<Key, Value>::Iterator
424HashMap<Key, Value>::GetIterator()
425{
426	return Iterator(this);
427}
428
429// _FindElement
430template<typename Key, typename Value>
431HashMap<Key, Value>::Element *
432HashMap<Key, Value>::_FindElement(const Key& key) const
433{
434	Element* element = fTable.FindFirst(key.GetHashCode());
435	while (element && element->fKey != key) {
436		if (element->fNext >= 0)
437			element = fTable.ElementAt(element->fNext);
438		else
439			element = NULL;
440	}
441	return element;
442}
443
444#endif	// HASH_MAP_H
445