OpenHashTable.h revision 955d5259
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
73template<typename Definition, bool AutoExpand = true,
74	bool CheckDuplicates = false, typename Allocator = MallocAllocator>
75class BOpenHashTable {
76public:
77	typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
78	typedef typename Definition::KeyType	KeyType;
79	typedef typename Definition::ValueType	ValueType;
80
81	static const size_t kMinimumSize = 8;
82
83	// All allocations are of power of 2 lengths.
84
85	// regrowth factor: 200 / 256 = 78.125%
86	//                   50 / 256 = 19.53125%
87
88	BOpenHashTable()
89		:
90		fTableSize(0),
91		fItemCount(0),
92		fTable(NULL)
93	{
94	}
95
96	BOpenHashTable(const Definition& definition)
97		:
98		fDefinition(definition),
99		fTableSize(0),
100		fItemCount(0),
101		fTable(NULL)
102	{
103	}
104
105	BOpenHashTable(const Definition& definition, const Allocator& allocator)
106		:
107		fDefinition(definition),
108		fAllocator(allocator),
109		fTableSize(0),
110		fItemCount(0),
111		fTable(NULL)
112	{
113	}
114
115	~BOpenHashTable()
116	{
117		fAllocator.Free(fTable);
118	}
119
120	status_t Init(size_t initialSize = kMinimumSize)
121	{
122		if (initialSize > 0 && !_Resize(initialSize))
123			return B_NO_MEMORY;
124		return B_OK;
125	}
126
127	size_t TableSize() const
128	{
129		return fTableSize;
130	}
131
132	bool IsEmpty() const
133	{
134		return fItemCount == 0;
135	}
136
137	size_t CountElements() const
138	{
139		return fItemCount;
140	}
141
142	ValueType* Lookup(typename TypeOperation<KeyType>::ConstRefT key) const
143	{
144		if (fTableSize == 0)
145			return NULL;
146
147		size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
148		ValueType* slot = fTable[index];
149
150		while (slot) {
151			if (fDefinition.Compare(key, slot))
152				break;
153			slot = _Link(slot);
154		}
155
156		return slot;
157	}
158
159	status_t Insert(ValueType* value)
160	{
161		if (fTableSize == 0) {
162			if (!_Resize(kMinimumSize))
163				return B_NO_MEMORY;
164		} else if (AutoExpand && fItemCount >= (fTableSize * 200 / 256))
165			_Resize(fTableSize * 2);
166
167		InsertUnchecked(value);
168		return B_OK;
169	}
170
171	void InsertUnchecked(ValueType* value)
172	{
173		if (CheckDuplicates && _ExhaustiveSearch(value)) {
174#ifdef _KERNEL_MODE
175			panic("Hash Table: value already in table.");
176#else
177			debugger("Hash Table: value already in table.");
178#endif
179		}
180
181		_Insert(fTable, fTableSize, value);
182		fItemCount++;
183	}
184
185	// TODO: a ValueType* Remove(const KeyType& key) method is missing
186
187	bool Remove(ValueType* value)
188	{
189		if (!RemoveUnchecked(value))
190			return false;
191
192		if (AutoExpand && fTableSize > kMinimumSize
193			&& fItemCount < (fTableSize * 50 / 256))
194			_Resize(fTableSize / 2);
195
196		return true;
197	}
198
199	bool RemoveUnchecked(ValueType* value)
200	{
201		size_t index = fDefinition.Hash(value) & (fTableSize - 1);
202		ValueType* previous = NULL;
203		ValueType* slot = fTable[index];
204
205		while (slot) {
206			ValueType* next = _Link(slot);
207
208			if (value == slot) {
209				if (previous)
210					_Link(previous) = next;
211				else
212					fTable[index] = next;
213				break;
214			}
215
216			previous = slot;
217			slot = next;
218		}
219
220		if (slot == NULL)
221			return false;
222
223		if (CheckDuplicates && _ExhaustiveSearch(value)) {
224#ifdef _KERNEL_MODE
225			panic("Hash Table: duplicate detected.");
226#else
227			debugger("Hash Table: duplicate detected.");
228#endif
229		}
230
231		fItemCount--;
232		return true;
233	}
234
235	/*!	Removes all elements from the hash table. No resizing happens. The
236		elements are not deleted. If \a returnElements is \c true, the method
237		returns all elements chained via their hash table link.
238	*/
239	ValueType* Clear(bool returnElements = false)
240	{
241		if (fItemCount == 0)
242			return NULL;
243
244		ValueType* result = NULL;
245
246		if (returnElements) {
247			ValueType** nextPointer = &result;
248
249			// iterate through all buckets
250			for (size_t i = 0; i < fTableSize; i++) {
251				ValueType* element = fTable[i];
252				if (element != NULL) {
253					// add the bucket to the list
254					*nextPointer = element;
255
256					// update nextPointer to point to the fNext of the last
257					// element in the bucket
258					while (element != NULL) {
259						nextPointer = &_Link(element);
260						element = *nextPointer;
261					}
262				}
263			}
264		}
265
266		memset(this->fTable, 0, sizeof(ValueType*) * this->fTableSize);
267		fItemCount = 0;
268
269		return result;
270	}
271
272	/*!	If the table needs resizing, the number of bytes for the required
273		allocation is returned. If no resizing is needed, 0 is returned.
274	*/
275	size_t ResizeNeeded() const
276	{
277		size_t size = fTableSize;
278		if (size == 0 || fItemCount >= (size * 200 / 256)) {
279			// grow table
280			if (size == 0)
281				size = kMinimumSize;
282			while (fItemCount >= size * 200 / 256)
283				size <<= 1;
284		} else if (size > kMinimumSize && fItemCount < size * 50 / 256) {
285			// shrink table
286			while (fItemCount < size * 50 / 256)
287				size >>= 1;
288			if (size < kMinimumSize)
289				size = kMinimumSize;
290		}
291
292		if (size == fTableSize)
293			return 0;
294
295		return size * sizeof(ValueType*);
296	}
297
298	/*!	Resizes the table using the given allocation. The allocation must not
299		be \c NULL. It must be of size \a size, which must a value returned
300		earlier by ResizeNeeded(). If the size requirements have changed in the
301		meantime, the method free()s the given allocation and returns \c false,
302		unless \a force is \c true, in which case the supplied allocation is
303		used in any event.
304		Otherwise \c true is returned.
305		If \a oldTable is non-null and resizing is successful, the old table
306		will not be freed, but will be returned via this parameter instead.
307	*/
308	bool Resize(void* allocation, size_t size, bool force = false,
309		void** oldTable = NULL)
310	{
311		if (!force && size != ResizeNeeded()) {
312			fAllocator.Free(allocation);
313			return false;
314		}
315
316		_Resize((ValueType**)allocation, size / sizeof(ValueType*), oldTable);
317		return true;
318	}
319
320	class Iterator {
321	public:
322		Iterator(const HashTable* table)
323			: fTable(table)
324		{
325			Rewind();
326		}
327
328		Iterator(const HashTable* table, size_t index, ValueType* value)
329			: fTable(table), fIndex(index), fNext(value) {}
330
331		bool HasNext() const { return fNext != NULL; }
332
333		ValueType* Next()
334		{
335			ValueType* current = fNext;
336			_GetNext();
337			return current;
338		}
339
340		void Rewind()
341		{
342			// get the first one
343			fIndex = 0;
344			fNext = NULL;
345			_GetNext();
346		}
347
348	protected:
349		Iterator() {}
350
351		void _GetNext()
352		{
353			if (fNext)
354				fNext = fTable->_Link(fNext);
355
356			while (fNext == NULL && fIndex < fTable->fTableSize)
357				fNext = fTable->fTable[fIndex++];
358		}
359
360		const HashTable* fTable;
361		size_t fIndex;
362		ValueType* fNext;
363	};
364
365	Iterator GetIterator() const
366	{
367		return Iterator(this);
368	}
369
370	Iterator GetIterator(typename TypeOperation<KeyType>::ConstRefT key) const
371	{
372		if (fTableSize == 0)
373			return Iterator(this, fTableSize, NULL);
374
375		size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
376		ValueType* slot = fTable[index];
377
378		while (slot) {
379			if (fDefinition.Compare(key, slot))
380				break;
381			slot = _Link(slot);
382		}
383
384		if (slot == NULL)
385			return Iterator(this, fTableSize, NULL);
386
387		return Iterator(this, index + 1, slot);
388	}
389
390protected:
391	// for g++ 2.95
392	friend class Iterator;
393
394	void _Insert(ValueType** table, size_t tableSize, ValueType* value)
395	{
396		size_t index = fDefinition.Hash(value) & (tableSize - 1);
397
398		_Link(value) = table[index];
399		table[index] = value;
400	}
401
402	bool _Resize(size_t newSize)
403	{
404		ValueType** newTable
405			= (ValueType**)fAllocator.Allocate(sizeof(ValueType*) * newSize);
406		if (newTable == NULL)
407			return false;
408
409		_Resize(newTable, newSize);
410		return true;
411	}
412
413	void _Resize(ValueType** newTable, size_t newSize, void** _oldTable = NULL)
414	{
415		for (size_t i = 0; i < newSize; i++)
416			newTable[i] = NULL;
417
418		if (fTable) {
419			for (size_t i = 0; i < fTableSize; i++) {
420				ValueType* bucket = fTable[i];
421				while (bucket) {
422					ValueType* next = _Link(bucket);
423					_Insert(newTable, newSize, bucket);
424					bucket = next;
425				}
426			}
427
428			if (_oldTable != NULL)
429				*_oldTable = fTable;
430			else
431				fAllocator.Free(fTable);
432		} else if (_oldTable != NULL)
433			*_oldTable = NULL;
434
435		fTableSize = newSize;
436		fTable = newTable;
437	}
438
439	ValueType*& _Link(ValueType* bucket) const
440	{
441		return fDefinition.GetLink(bucket);
442	}
443
444	bool _ExhaustiveSearch(ValueType* value) const
445	{
446		for (size_t i = 0; i < fTableSize; i++) {
447			ValueType* bucket = fTable[i];
448			while (bucket) {
449				if (bucket == value)
450					return true;
451				bucket = _Link(bucket);
452			}
453		}
454
455		return false;
456	}
457
458	Definition		fDefinition;
459	Allocator		fAllocator;
460	size_t			fTableSize;
461	size_t			fItemCount;
462	ValueType**		fTable;
463};
464
465#endif	// _KERNEL_UTIL_OPEN_HASH_TABLE_H
466