OpenHashTable.h revision 9d053f59
1/*
2 * Copyright 2007, Hugo Santos. All Rights Reserved.
3 * Distributed under the terms of the MIT License.
4 */
5#ifndef _KERNEL_UTIL_OPEN_HASH_TABLE_H
6#define _KERNEL_UTIL_OPEN_HASH_TABLE_H
7
8
9#include <OS.h>
10#include <stdlib.h>
11#include <string.h>
12
13#ifdef _KERNEL_MODE
14#	include <KernelExport.h>
15#	include <util/kernel_cpp.h>
16#	include <util/TypeOperation.h>
17#else
18#	include <TypeOperation.h>
19#endif
20
21
22/*!
23	The Definition template must have four methods: `HashKey', `Hash',
24	`Compare' and `GetLink;. It must also define several types as shown in the
25	following example:
26
27	struct Foo {
28		int bar;
29
30		Foo* fNext;
31	};
32
33	struct HashTableDefinition {
34		typedef int		KeyType;
35		typedef	Foo		ValueType;
36
37		size_t HashKey(KeyType key) const
38		{
39			return key >> 1;
40		}
41
42		size_t Hash(ValueType* value) const
43		{
44			return HashKey(value->bar);
45		}
46
47		bool Compare(KeyType key, ValueType* value) const
48		{
49			return value->bar == key;
50		}
51
52		ValueType*& GetLink(ValueType* value) const
53		{
54			return value->fNext;
55		}
56	};
57*/
58
59
60struct MallocAllocator {
61	void* Allocate(size_t size) const
62	{
63		return malloc(size);
64	}
65
66	void Free(void* memory) const
67	{
68		free(memory);
69	}
70};
71
72
73/** Implements an hash table with open hashing, that is, colliding entries are
74 * stored in a linked list. The table may be made to adjust its number of slots
75 * depending on the load factor (this should be enabled unless the object is to
76 * be used at times where memory allocations aren't possible, such as code
77 * called byt he memory allocator).
78 *
79 * The link between entries is part of the ValueType stored items, which makes
80 * sure the table can always accept new items and will never fail because it is
81 * out of memory (except at Init time).
82 */
83template<typename Definition, bool AutoExpand = true,
84	bool CheckDuplicates = false, typename Allocator = MallocAllocator>
85class BOpenHashTable {
86public:
87	typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
88	typedef typename Definition::KeyType	KeyType;
89	typedef typename Definition::ValueType	ValueType;
90
91	static const size_t kMinimumSize = 8;
92
93	// All allocations are of power of 2 lengths.
94
95	// regrowth factor: 200 / 256 = 78.125%
96	//                   50 / 256 = 19.53125%
97
98	BOpenHashTable()
99		:
100		fTableSize(0),
101		fItemCount(0),
102		fTable(NULL)
103	{
104	}
105
106	BOpenHashTable(const Definition& definition)
107		:
108		fDefinition(definition),
109		fTableSize(0),
110		fItemCount(0),
111		fTable(NULL)
112	{
113	}
114
115	BOpenHashTable(const Definition& definition, const Allocator& allocator)
116		:
117		fDefinition(definition),
118		fAllocator(allocator),
119		fTableSize(0),
120		fItemCount(0),
121		fTable(NULL)
122	{
123	}
124
125	~BOpenHashTable()
126	{
127		fAllocator.Free(fTable);
128	}
129
130	status_t Init(size_t initialSize = kMinimumSize)
131	{
132		if (initialSize > 0 && !_Resize(initialSize))
133			return B_NO_MEMORY;
134		return B_OK;
135	}
136
137	size_t TableSize() const
138	{
139		return fTableSize;
140	}
141
142	bool IsEmpty() const
143	{
144		return fItemCount == 0;
145	}
146
147	size_t CountElements() const
148	{
149		return fItemCount;
150	}
151
152	ValueType* Lookup(typename TypeOperation<KeyType>::ConstRefT key) const
153	{
154		if (fTableSize == 0)
155			return NULL;
156
157		size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
158		ValueType* slot = fTable[index];
159
160		while (slot) {
161			if (fDefinition.Compare(key, slot))
162				break;
163			slot = _Link(slot);
164		}
165
166		return slot;
167	}
168
169	status_t Insert(ValueType* value)
170	{
171		if (fTableSize == 0) {
172			if (!_Resize(kMinimumSize))
173				return B_NO_MEMORY;
174		} else if (AutoExpand && fItemCount >= (fTableSize * 200 / 256))
175			_Resize(fTableSize * 2);
176
177		InsertUnchecked(value);
178		return B_OK;
179	}
180
181	/*! \brief Inserts a value without resizing the table.
182
183		Use this method if you need to insert a value into the table while
184		iterating it, as regular insertion can invalidate iterators.
185	*/
186	void InsertUnchecked(ValueType* value)
187	{
188		if (CheckDuplicates && _ExhaustiveSearch(value)) {
189#ifdef _KERNEL_MODE
190			panic("Hash Table: value already in table.");
191#else
192			debugger("Hash Table: value already in table.");
193#endif
194		}
195
196		_Insert(fTable, fTableSize, value);
197		fItemCount++;
198	}
199
200	// TODO: a ValueType* Remove(const KeyType& key) method is missing
201
202	bool Remove(ValueType* value)
203	{
204		if (!RemoveUnchecked(value))
205			return false;
206
207		if (AutoExpand && fTableSize > kMinimumSize
208			&& fItemCount < (fTableSize * 50 / 256))
209			_Resize(fTableSize / 2);
210
211		return true;
212	}
213
214	/*! \brief Removes a value without resizing the table.
215
216		Use this method if you need to remove a value from the table while
217		iterating it, as Remove can invalidate iterators.
218
219		Also use this method if you know you are going to reinsert the item soon
220		(possibly with a different hash) to avoid shrinking then growing the
221		table again.
222	*/
223	bool RemoveUnchecked(ValueType* value)
224	{
225		size_t index = fDefinition.Hash(value) & (fTableSize - 1);
226		ValueType* previous = NULL;
227		ValueType* slot = fTable[index];
228
229		while (slot) {
230			ValueType* next = _Link(slot);
231
232			if (value == slot) {
233				if (previous)
234					_Link(previous) = next;
235				else
236					fTable[index] = next;
237				break;
238			}
239
240			previous = slot;
241			slot = next;
242		}
243
244		if (slot == NULL)
245			return false;
246
247		if (CheckDuplicates && _ExhaustiveSearch(value)) {
248#ifdef _KERNEL_MODE
249			panic("Hash Table: duplicate detected.");
250#else
251			debugger("Hash Table: duplicate detected.");
252#endif
253		}
254
255		fItemCount--;
256		return true;
257	}
258
259	/*!	\brief Removes all elements from the hash table.
260
261		No resizing happens. The elements are not deleted. If \a returnElements
262		is \c true, the method returns all elements chained via their hash table
263		link.
264	*/
265	ValueType* Clear(bool returnElements = false)
266	{
267		if (fItemCount == 0)
268			return NULL;
269
270		ValueType* result = NULL;
271
272		if (returnElements) {
273			ValueType** nextPointer = &result;
274
275			// iterate through all buckets
276			for (size_t i = 0; i < fTableSize; i++) {
277				ValueType* element = fTable[i];
278				if (element != NULL) {
279					// add the bucket to the list
280					*nextPointer = element;
281
282					// update nextPointer to point to the fNext of the last
283					// element in the bucket
284					while (element != NULL) {
285						nextPointer = &_Link(element);
286						element = *nextPointer;
287					}
288				}
289			}
290		}
291
292		memset(this->fTable, 0, sizeof(ValueType*) * this->fTableSize);
293		fItemCount = 0;
294
295		return result;
296	}
297
298	/*!	If the table needs resizing, the number of bytes for the required
299		allocation is returned. If no resizing is needed, 0 is returned.
300	*/
301	size_t ResizeNeeded() const
302	{
303		size_t size = fTableSize;
304		if (size == 0 || fItemCount >= (size * 200 / 256)) {
305			// grow table
306			if (size == 0)
307				size = kMinimumSize;
308			while (fItemCount >= size * 200 / 256)
309				size <<= 1;
310		} else if (size > kMinimumSize && fItemCount < size * 50 / 256) {
311			// shrink table
312			while (fItemCount < size * 50 / 256)
313				size >>= 1;
314			if (size < kMinimumSize)
315				size = kMinimumSize;
316		}
317
318		if (size == fTableSize)
319			return 0;
320
321		return size * sizeof(ValueType*);
322	}
323
324	/*!	Resizes the table using the given allocation. The allocation must not
325		be \c NULL. It must be of size \a size, which must be a value returned
326		earlier by ResizeNeeded(). If the size requirements have changed in the
327		meantime, the method free()s the given allocation and returns \c false,
328		unless \a force is \c true, in which case the supplied allocation is
329		used in any event.
330		Otherwise \c true is returned.
331		If \a oldTable is non-null and resizing is successful, the old table
332		will not be freed, but will be returned via this parameter instead.
333	*/
334	bool Resize(void* allocation, size_t size, bool force = false,
335		void** oldTable = NULL)
336	{
337		if (!force && size != ResizeNeeded()) {
338			fAllocator.Free(allocation);
339			return false;
340		}
341
342		_Resize((ValueType**)allocation, size / sizeof(ValueType*), oldTable);
343		return true;
344	}
345
346	/*! \brief Iterator for BOpenHashMap
347
348		The iterator is not invalidated when removing the current element from
349		the table, unless the removal triggers a resize.
350	*/
351	class Iterator {
352	public:
353		Iterator(const HashTable* table)
354			: fTable(table)
355		{
356			Rewind();
357		}
358
359		Iterator(const HashTable* table, size_t index, ValueType* value)
360			: fTable(table), fIndex(index), fNext(value) {}
361
362		bool HasNext() const { return fNext != NULL; }
363
364		ValueType* Next()
365		{
366			ValueType* current = fNext;
367			_GetNext();
368			return current;
369		}
370
371		void Rewind()
372		{
373			// get the first one
374			fIndex = 0;
375			fNext = NULL;
376			_GetNext();
377		}
378
379	protected:
380		Iterator() {}
381
382		void _GetNext()
383		{
384			if (fNext)
385				fNext = fTable->_Link(fNext);
386
387			while (fNext == NULL && fIndex < fTable->fTableSize)
388				fNext = fTable->fTable[fIndex++];
389		}
390
391		const HashTable* fTable;
392		size_t fIndex;
393		ValueType* fNext;
394	};
395
396	Iterator GetIterator() const
397	{
398		return Iterator(this);
399	}
400
401	Iterator GetIterator(typename TypeOperation<KeyType>::ConstRefT key) const
402	{
403		if (fTableSize == 0)
404			return Iterator(this, fTableSize, NULL);
405
406		size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
407		ValueType* slot = fTable[index];
408
409		while (slot) {
410			if (fDefinition.Compare(key, slot))
411				break;
412			slot = _Link(slot);
413		}
414
415		if (slot == NULL)
416			return Iterator(this, fTableSize, NULL);
417
418		return Iterator(this, index + 1, slot);
419	}
420
421protected:
422	// for g++ 2.95
423	friend class Iterator;
424
425	void _Insert(ValueType** table, size_t tableSize, ValueType* value)
426	{
427		size_t index = fDefinition.Hash(value) & (tableSize - 1);
428
429		_Link(value) = table[index];
430		table[index] = value;
431	}
432
433	bool _Resize(size_t newSize)
434	{
435		ValueType** newTable
436			= (ValueType**)fAllocator.Allocate(sizeof(ValueType*) * newSize);
437		if (newTable == NULL)
438			return false;
439
440		_Resize(newTable, newSize);
441		return true;
442	}
443
444	void _Resize(ValueType** newTable, size_t newSize, void** _oldTable = NULL)
445	{
446		for (size_t i = 0; i < newSize; i++)
447			newTable[i] = NULL;
448
449		if (fTable) {
450			for (size_t i = 0; i < fTableSize; i++) {
451				ValueType* bucket = fTable[i];
452				while (bucket) {
453					ValueType* next = _Link(bucket);
454					_Insert(newTable, newSize, bucket);
455					bucket = next;
456				}
457			}
458
459			if (_oldTable != NULL)
460				*_oldTable = fTable;
461			else
462				fAllocator.Free(fTable);
463		} else if (_oldTable != NULL)
464			*_oldTable = NULL;
465
466		fTableSize = newSize;
467		fTable = newTable;
468	}
469
470	ValueType*& _Link(ValueType* bucket) const
471	{
472		return fDefinition.GetLink(bucket);
473	}
474
475	bool _ExhaustiveSearch(ValueType* value) const
476	{
477		for (size_t i = 0; i < fTableSize; i++) {
478			ValueType* bucket = fTable[i];
479			while (bucket) {
480				if (bucket == value)
481					return true;
482				bucket = _Link(bucket);
483			}
484		}
485
486		return false;
487	}
488
489	Definition		fDefinition;
490	Allocator		fAllocator;
491	size_t			fTableSize;
492	size_t			fItemCount;
493	ValueType**		fTable;
494};
495
496#endif	// _KERNEL_UTIL_OPEN_HASH_TABLE_H
497