xref: /haiku/headers/private/shared/HashMap.h (revision e688bf23d48bfd1216a0cacbdbda5e35a1bcd779) 
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 
38 namespace BPrivate {
39 
40 // HashMapElement
41 template<typename Key, typename Value>
42 class HashMapElement : public OpenHashElement {
43 private:
44 	typedef HashMapElement<Key, Value> Element;
45 public:
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
74 template<typename Key, typename Value>
75 class HashMap {
76 public:
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 
193 protected:
194 	typedef HashMapElement<Key, Value>	Element;
195 	friend class Iterator;
196 
197 private:
198 	Element *_FindElement(const Key& key) const;
199 
200 protected:
201 	OpenHashElementArray<Element>							fElementArray;
202 	OpenHashTable<Element, OpenHashElementArray<Element> >	fTable;
203 };
204 
205 // SynchronizedHashMap
206 template<typename Key, typename Value>
207 class SynchronizedHashMap : public BLocker {
208 public:
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 
276 protected:
277 	typedef AutoLocker<BLocker> MapLocker;
278 
279 	HashMap<Key, Value>	fMap;
280 };
281 
282 // HashKey32
283 template<typename Value>
284 struct 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
314 template<typename Value>
315 struct 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
348 template<typename Key, typename Value>
349 HashMap<Key, Value>::HashMap()
350 	:
351 	fElementArray(1000),
352 	fTable(1000, &fElementArray)
353 {
354 }
355 
356 // destructor
357 template<typename Key, typename Value>
358 HashMap<Key, Value>::~HashMap()
359 {
360 }
361 
362 // InitCheck
363 template<typename Key, typename Value>
364 status_t
365 HashMap<Key, Value>::InitCheck() const
366 {
367 	return (fTable.InitCheck() && fElementArray.InitCheck()
368 			? B_OK : B_NO_MEMORY);
369 }
370 
371 // Put
372 template<typename Key, typename Value>
373 status_t
374 HashMap<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
392 template<typename Key, typename Value>
393 Value
394 HashMap<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
405 template<typename Key, typename Value>
406 void
407 HashMap<Key, Value>::Clear()
408 {
409 	fTable.RemoveAll();
410 }
411 
412 // Get
413 template<typename Key, typename Value>
414 Value
415 HashMap<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
423 template<typename Key, typename Value>
424 bool
425 HashMap<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
436 template<typename Key, typename Value>
437 bool
438 HashMap<Key, Value>::ContainsKey(const Key& key) const
439 {
440 	return _FindElement(key);
441 }
442 
443 // Size
444 template<typename Key, typename Value>
445 int32
446 HashMap<Key, Value>::Size() const
447 {
448 	return fTable.CountElements();
449 }
450 
451 // GetIterator
452 template<typename Key, typename Value>
453 struct HashMap<Key, Value>::Iterator
454 HashMap<Key, Value>::GetIterator() const
455 {
456 	return Iterator(this);
457 }
458 
459 // _FindElement
460 template<typename Key, typename Value>
461 typename HashMap<Key, Value>::Element *
462 HashMap<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 
476 using BPrivate::HashMap;
477 using BPrivate::HashKey32;
478 using BPrivate::HashKey64;
479 using BPrivate::SynchronizedHashMap;
480 
481 #endif	// HASH_MAP_H
482