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