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