185dbe747SHugo Santos/*
285dbe747SHugo Santos * Copyright 2007, Hugo Santos. All Rights Reserved.
385dbe747SHugo Santos * Distributed under the terms of the MIT License.
485dbe747SHugo Santos */
584052230SAxel Dörfler#ifndef _KERNEL_UTIL_OPEN_HASH_TABLE_H
684052230SAxel Dörfler#define _KERNEL_UTIL_OPEN_HASH_TABLE_H
785dbe747SHugo Santos
885dbe747SHugo Santos
942ef5213SIngo Weinhold#include <OS.h>
10595d8a3bSFrançois Revol#include <stdlib.h>
1157e7daa5SIngo Weinhold#include <string.h>
1242ef5213SIngo Weinhold
1342ef5213SIngo Weinhold#ifdef _KERNEL_MODE
1442ef5213SIngo Weinhold#	include <KernelExport.h>
1542ef5213SIngo Weinhold#	include <util/kernel_cpp.h>
1694089b90SOliver Tappe#	include <util/TypeOperation.h>
1794089b90SOliver Tappe#else
1858852727SAugustin Cavalier#	include <new>
1994089b90SOliver Tappe#	include <TypeOperation.h>
2042ef5213SIngo Weinhold#endif
2185dbe747SHugo Santos
2284052230SAxel Dörfler
2384052230SAxel Dörfler/*!
2484052230SAxel Dörfler	The Definition template must have four methods: `HashKey', `Hash',
2584052230SAxel Dörfler	`Compare' and `GetLink;. It must also define several types as shown in the
2684052230SAxel Dörfler	following example:
2784052230SAxel Dörfler
285147963dSStephan Aßmus	struct Foo {
2984052230SAxel Dörfler		int bar;
3030e5affaSAxel Dörfler
315147963dSStephan Aßmus		Foo* fNext;
3284052230SAxel Dörfler	};
3384052230SAxel Dörfler
3484052230SAxel Dörfler	struct HashTableDefinition {
3584052230SAxel Dörfler		typedef int		KeyType;
3684052230SAxel Dörfler		typedef	Foo		ValueType;
3784052230SAxel Dörfler
38955d5259SAdrien Destugues		size_t HashKey(KeyType key) const
39b20de45eSIngo Weinhold		{
40b20de45eSIngo Weinhold			return key >> 1;
41b20de45eSIngo Weinhold		}
4284052230SAxel Dörfler
43955d5259SAdrien Destugues		size_t Hash(ValueType* value) const
44b20de45eSIngo Weinhold		{
45b20de45eSIngo Weinhold			return HashKey(value->bar);
46b20de45eSIngo Weinhold		}
47b20de45eSIngo Weinhold
48955d5259SAdrien Destugues		bool Compare(KeyType key, ValueType* value) const
49b20de45eSIngo Weinhold		{
50b20de45eSIngo Weinhold			return value->bar == key;
51b20de45eSIngo Weinhold		}
52b20de45eSIngo Weinhold
53955d5259SAdrien Destugues		ValueType*& GetLink(ValueType* value) const
54b20de45eSIngo Weinhold		{
55b20de45eSIngo Weinhold			return value->fNext;
56b20de45eSIngo Weinhold		}
5784052230SAxel Dörfler	};
5884052230SAxel Dörfler*/
5985dbe747SHugo Santos
602586c25eSHugo Santos
61b20de45eSIngo Weinholdstruct MallocAllocator {
62b20de45eSIngo Weinhold	void* Allocate(size_t size) const
63b20de45eSIngo Weinhold	{
64b20de45eSIngo Weinhold		return malloc(size);
65b20de45eSIngo Weinhold	}
66b20de45eSIngo Weinhold
67b20de45eSIngo Weinhold	void Free(void* memory) const
68b20de45eSIngo Weinhold	{
69b20de45eSIngo Weinhold		free(memory);
70b20de45eSIngo Weinhold	}
71b20de45eSIngo Weinhold};
72b20de45eSIngo Weinhold
73b20de45eSIngo Weinhold
749d053f59SAdrien Destugues/** Implements an hash table with open hashing, that is, colliding entries are
759d053f59SAdrien Destugues * stored in a linked list. The table may be made to adjust its number of slots
769d053f59SAdrien Destugues * depending on the load factor (this should be enabled unless the object is to
779d053f59SAdrien Destugues * be used at times where memory allocations aren't possible, such as code
78f9a8f3e7SMichael Lotz * called by the memory allocator).
799d053f59SAdrien Destugues *
809d053f59SAdrien Destugues * The link between entries is part of the ValueType stored items, which makes
819d053f59SAdrien Destugues * sure the table can always accept new items and will never fail because it is
829d053f59SAdrien Destugues * out of memory (except at Init time).
839d053f59SAdrien Destugues */
842586c25eSHugo Santostemplate<typename Definition, bool AutoExpand = true,
85b20de45eSIngo Weinhold	bool CheckDuplicates = false, typename Allocator = MallocAllocator>
865147963dSStephan Aßmusclass BOpenHashTable {
8785dbe747SHugo Santospublic:
885147963dSStephan Aßmus	typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
8985dbe747SHugo Santos	typedef typename Definition::KeyType	KeyType;
9085dbe747SHugo Santos	typedef typename Definition::ValueType	ValueType;
9185dbe747SHugo Santos
920e30c21cSHugo Santos	static const size_t kMinimumSize = 8;
9385dbe747SHugo Santos
94b20de45eSIngo Weinhold	// All allocations are of power of 2 lengths.
9585dbe747SHugo Santos
9685dbe747SHugo Santos	// regrowth factor: 200 / 256 = 78.125%
9785dbe747SHugo Santos	//                   50 / 256 = 19.53125%
9885dbe747SHugo Santos
995147963dSStephan Aßmus	BOpenHashTable()
10084052230SAxel Dörfler		:
10184052230SAxel Dörfler		fTableSize(0),
10284052230SAxel Dörfler		fItemCount(0),
10384052230SAxel Dörfler		fTable(NULL)
10477e70865SHugo Santos	{
10577e70865SHugo Santos	}
10677e70865SHugo Santos
1075147963dSStephan Aßmus	BOpenHashTable(const Definition& definition)
10884052230SAxel Dörfler		:
10984052230SAxel Dörfler		fDefinition(definition),
11084052230SAxel Dörfler		fTableSize(0),
11184052230SAxel Dörfler		fItemCount(0),
11284052230SAxel Dörfler		fTable(NULL)
11385dbe747SHugo Santos	{
11485dbe747SHugo Santos	}
11585dbe747SHugo Santos
116b20de45eSIngo Weinhold	BOpenHashTable(const Definition& definition, const Allocator& allocator)
117b20de45eSIngo Weinhold		:
118b20de45eSIngo Weinhold		fDefinition(definition),
119b20de45eSIngo Weinhold		fAllocator(allocator),
120b20de45eSIngo Weinhold		fTableSize(0),
121b20de45eSIngo Weinhold		fItemCount(0),
122b20de45eSIngo Weinhold		fTable(NULL)
123b20de45eSIngo Weinhold	{
124b20de45eSIngo Weinhold	}
125b20de45eSIngo Weinhold
1265147963dSStephan Aßmus	~BOpenHashTable()
12785dbe747SHugo Santos	{
128b20de45eSIngo Weinhold		fAllocator.Free(fTable);
12985dbe747SHugo Santos	}
13085dbe747SHugo Santos
131276aa463SIngo Weinhold	status_t Init(size_t initialSize = kMinimumSize)
1320e30c21cSHugo Santos	{
133276aa463SIngo Weinhold		if (initialSize > 0 && !_Resize(initialSize))
134276aa463SIngo Weinhold			return B_NO_MEMORY;
135276aa463SIngo Weinhold		return B_OK;
1360e30c21cSHugo Santos	}
13785dbe747SHugo Santos
1382d4fb82cSIngo Weinhold	size_t TableSize() const
1392d4fb82cSIngo Weinhold	{
1402d4fb82cSIngo Weinhold		return fTableSize;
1412d4fb82cSIngo Weinhold	}
1422d4fb82cSIngo Weinhold
1431eda8517SIngo Weinhold	bool IsEmpty() const
1441eda8517SIngo Weinhold	{
1451eda8517SIngo Weinhold		return fItemCount == 0;
1461eda8517SIngo Weinhold	}
1471eda8517SIngo Weinhold
1482d4fb82cSIngo Weinhold	size_t CountElements() const
1492d4fb82cSIngo Weinhold	{
1502d4fb82cSIngo Weinhold		return fItemCount;
1512d4fb82cSIngo Weinhold	}
1522d4fb82cSIngo Weinhold
15394089b90SOliver Tappe	ValueType* Lookup(typename TypeOperation<KeyType>::ConstRefT key) const
15485dbe747SHugo Santos	{
1550e30c21cSHugo Santos		if (fTableSize == 0)
1560e30c21cSHugo Santos			return NULL;
1570e30c21cSHugo Santos
15877e70865SHugo Santos		size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
1595147963dSStephan Aßmus		ValueType* slot = fTable[index];
16085dbe747SHugo Santos
1612586c25eSHugo Santos		while (slot) {
16277e70865SHugo Santos			if (fDefinition.Compare(key, slot))
1632586c25eSHugo Santos				break;
1645147963dSStephan Aßmus			slot = _Link(slot);
16585dbe747SHugo Santos		}
1662586c25eSHugo Santos
1672586c25eSHugo Santos		return slot;
16885dbe747SHugo Santos	}
16985dbe747SHugo Santos
1705147963dSStephan Aßmus	status_t Insert(ValueType* value)
17185dbe747SHugo Santos	{
1720e30c21cSHugo Santos		if (fTableSize == 0) {
1730e30c21cSHugo Santos			if (!_Resize(kMinimumSize))
1740e30c21cSHugo Santos				return B_NO_MEMORY;
1750e30c21cSHugo Santos		} else if (AutoExpand && fItemCount >= (fTableSize * 200 / 256))
1762586c25eSHugo Santos			_Resize(fTableSize * 2);
17785dbe747SHugo Santos
17885dbe747SHugo Santos		InsertUnchecked(value);
1790e30c21cSHugo Santos		return B_OK;
18085dbe747SHugo Santos	}
18185dbe747SHugo Santos
1829d053f59SAdrien Destugues	/*! \brief Inserts a value without resizing the table.
1839d053f59SAdrien Destugues
1849d053f59SAdrien Destugues		Use this method if you need to insert a value into the table while
1859d053f59SAdrien Destugues		iterating it, as regular insertion can invalidate iterators.
1869d053f59SAdrien Destugues	*/
1875147963dSStephan Aßmus	void InsertUnchecked(ValueType* value)
18885dbe747SHugo Santos	{
18942ef5213SIngo Weinhold		if (CheckDuplicates && _ExhaustiveSearch(value)) {
19042ef5213SIngo Weinhold#ifdef _KERNEL_MODE
191f6cfc5afSHugo Santos			panic("Hash Table: value already in table.");
19242ef5213SIngo Weinhold#else
19342ef5213SIngo Weinhold			debugger("Hash Table: value already in table.");
19442ef5213SIngo Weinhold#endif
19542ef5213SIngo Weinhold		}
19653f23f85SHugo Santos
1972586c25eSHugo Santos		_Insert(fTable, fTableSize, value);
19885dbe747SHugo Santos		fItemCount++;
19985dbe747SHugo Santos	}
20085dbe747SHugo Santos
20130e5affaSAxel Dörfler	// TODO: a ValueType* Remove(const KeyType& key) method is missing
20230e5affaSAxel Dörfler
2035147963dSStephan Aßmus	bool Remove(ValueType* value)
20485dbe747SHugo Santos	{
205505e9853SHugo Santos		if (!RemoveUnchecked(value))
206505e9853SHugo Santos			return false;
20785dbe747SHugo Santos
2082586c25eSHugo Santos		if (AutoExpand && fTableSize > kMinimumSize
2092586c25eSHugo Santos			&& fItemCount < (fTableSize * 50 / 256))
21085dbe747SHugo Santos			_Resize(fTableSize / 2);
211505e9853SHugo Santos
212505e9853SHugo Santos		return true;
21385dbe747SHugo Santos	}
21485dbe747SHugo Santos
2159d053f59SAdrien Destugues	/*! \brief Removes a value without resizing the table.
2169d053f59SAdrien Destugues
2179d053f59SAdrien Destugues		Use this method if you need to remove a value from the table while
2189d053f59SAdrien Destugues		iterating it, as Remove can invalidate iterators.
2199d053f59SAdrien Destugues
2209d053f59SAdrien Destugues		Also use this method if you know you are going to reinsert the item soon
2219d053f59SAdrien Destugues		(possibly with a different hash) to avoid shrinking then growing the
2229d053f59SAdrien Destugues		table again.
2239d053f59SAdrien Destugues	*/
2245147963dSStephan Aßmus	bool RemoveUnchecked(ValueType* value)
22585dbe747SHugo Santos	{
22677e70865SHugo Santos		size_t index = fDefinition.Hash(value) & (fTableSize - 1);
2275147963dSStephan Aßmus		ValueType* previous = NULL;
2285147963dSStephan Aßmus		ValueType* slot = fTable[index];
22985dbe747SHugo Santos
2302586c25eSHugo Santos		while (slot) {
2315147963dSStephan Aßmus			ValueType* next = _Link(slot);
2322586c25eSHugo Santos
2332586c25eSHugo Santos			if (value == slot) {
2342586c25eSHugo Santos				if (previous)
2355147963dSStephan Aßmus					_Link(previous) = next;
2362586c25eSHugo Santos				else
2372586c25eSHugo Santos					fTable[index] = next;
23885dbe747SHugo Santos				break;
23985dbe747SHugo Santos			}
24085dbe747SHugo Santos
2412586c25eSHugo Santos			previous = slot;
2422586c25eSHugo Santos			slot = next;
24385dbe747SHugo Santos		}
24485dbe747SHugo Santos
245505e9853SHugo Santos		if (slot == NULL)
246505e9853SHugo Santos			return false;
247505e9853SHugo Santos
24842ef5213SIngo Weinhold		if (CheckDuplicates && _ExhaustiveSearch(value)) {
24942ef5213SIngo Weinhold#ifdef _KERNEL_MODE
250f6cfc5afSHugo Santos			panic("Hash Table: duplicate detected.");
25142ef5213SIngo Weinhold#else
25242ef5213SIngo Weinhold			debugger("Hash Table: duplicate detected.");
25342ef5213SIngo Weinhold#endif
25442ef5213SIngo Weinhold		}
25553f23f85SHugo Santos
25685dbe747SHugo Santos		fItemCount--;
257505e9853SHugo Santos		return true;
25885dbe747SHugo Santos	}
25985dbe747SHugo Santos
2609d053f59SAdrien Destugues	/*!	\brief Removes all elements from the hash table.
2619d053f59SAdrien Destugues
2629d053f59SAdrien Destugues		No resizing happens. The elements are not deleted. If \a returnElements
2639d053f59SAdrien Destugues		is \c true, the method returns all elements chained via their hash table
2649d053f59SAdrien Destugues		link.
2652d4fb82cSIngo Weinhold	*/
2662d4fb82cSIngo Weinhold	ValueType* Clear(bool returnElements = false)
2672d4fb82cSIngo Weinhold	{
2687fa36995SIngo Weinhold		if (fItemCount == 0)
2692d4fb82cSIngo Weinhold			return NULL;
2702d4fb82cSIngo Weinhold
2712d4fb82cSIngo Weinhold		ValueType* result = NULL;
2722d4fb82cSIngo Weinhold
2732d4fb82cSIngo Weinhold		if (returnElements) {
2742d4fb82cSIngo Weinhold			ValueType** nextPointer = &result;
2752d4fb82cSIngo Weinhold
2762d4fb82cSIngo Weinhold			// iterate through all buckets
2772d4fb82cSIngo Weinhold			for (size_t i = 0; i < fTableSize; i++) {
2782d4fb82cSIngo Weinhold				ValueType* element = fTable[i];
2792d4fb82cSIngo Weinhold				if (element != NULL) {
2802d4fb82cSIngo Weinhold					// add the bucket to the list
2812d4fb82cSIngo Weinhold					*nextPointer = element;
2822d4fb82cSIngo Weinhold
2832d4fb82cSIngo Weinhold					// update nextPointer to point to the fNext of the last
2842d4fb82cSIngo Weinhold					// element in the bucket
2852d4fb82cSIngo Weinhold					while (element != NULL) {
2865147963dSStephan Aßmus						nextPointer = &_Link(element);
2872d4fb82cSIngo Weinhold						element = *nextPointer;
2882d4fb82cSIngo Weinhold					}
2892d4fb82cSIngo Weinhold				}
2902d4fb82cSIngo Weinhold			}
2912d4fb82cSIngo Weinhold		}
2922d4fb82cSIngo Weinhold
2932d4fb82cSIngo Weinhold		memset(this->fTable, 0, sizeof(ValueType*) * this->fTableSize);
2947fa36995SIngo Weinhold		fItemCount = 0;
2952d4fb82cSIngo Weinhold
2962d4fb82cSIngo Weinhold		return result;
2972d4fb82cSIngo Weinhold	}
2982d4fb82cSIngo Weinhold
299fc06a3f8SIngo Weinhold	/*!	If the table needs resizing, the number of bytes for the required
300fc06a3f8SIngo Weinhold		allocation is returned. If no resizing is needed, 0 is returned.
301fc06a3f8SIngo Weinhold	*/
302fc06a3f8SIngo Weinhold	size_t ResizeNeeded() const
303fc06a3f8SIngo Weinhold	{
304fc06a3f8SIngo Weinhold		size_t size = fTableSize;
305fc06a3f8SIngo Weinhold		if (size == 0 || fItemCount >= (size * 200 / 256)) {
306fc06a3f8SIngo Weinhold			// grow table
307fc06a3f8SIngo Weinhold			if (size == 0)
308fc06a3f8SIngo Weinhold				size = kMinimumSize;
309fc06a3f8SIngo Weinhold			while (fItemCount >= size * 200 / 256)
310fc06a3f8SIngo Weinhold				size <<= 1;
311fc06a3f8SIngo Weinhold		} else if (size > kMinimumSize && fItemCount < size * 50 / 256) {
312fc06a3f8SIngo Weinhold			// shrink table
313fc06a3f8SIngo Weinhold			while (fItemCount < size * 50 / 256)
314fc06a3f8SIngo Weinhold				size >>= 1;
315fc06a3f8SIngo Weinhold			if (size < kMinimumSize)
316fc06a3f8SIngo Weinhold				size = kMinimumSize;
317fc06a3f8SIngo Weinhold		}
318fc06a3f8SIngo Weinhold
319fc06a3f8SIngo Weinhold		if (size == fTableSize)
320fc06a3f8SIngo Weinhold			return 0;
321fc06a3f8SIngo Weinhold
322fc06a3f8SIngo Weinhold		return size * sizeof(ValueType*);
323fc06a3f8SIngo Weinhold	}
324fc06a3f8SIngo Weinhold
325fc06a3f8SIngo Weinhold	/*!	Resizes the table using the given allocation. The allocation must not
3269d053f59SAdrien Destugues		be \c NULL. It must be of size \a size, which must be a value returned
327fc06a3f8SIngo Weinhold		earlier by ResizeNeeded(). If the size requirements have changed in the
3285f679d1cSIngo Weinhold		meantime, the method free()s the given allocation and returns \c false,
3295f679d1cSIngo Weinhold		unless \a force is \c true, in which case the supplied allocation is
3305f679d1cSIngo Weinhold		used in any event.
331fc06a3f8SIngo Weinhold		Otherwise \c true is returned.
332b20de45eSIngo Weinhold		If \a oldTable is non-null and resizing is successful, the old table
333b20de45eSIngo Weinhold		will not be freed, but will be returned via this parameter instead.
334fc06a3f8SIngo Weinhold	*/
335b20de45eSIngo Weinhold	bool Resize(void* allocation, size_t size, bool force = false,
336b20de45eSIngo Weinhold		void** oldTable = NULL)
337fc06a3f8SIngo Weinhold	{
3385f679d1cSIngo Weinhold		if (!force && size != ResizeNeeded()) {
339b20de45eSIngo Weinhold			fAllocator.Free(allocation);
340fc06a3f8SIngo Weinhold			return false;
341fc06a3f8SIngo Weinhold		}
342fc06a3f8SIngo Weinhold
343b20de45eSIngo Weinhold		_Resize((ValueType**)allocation, size / sizeof(ValueType*), oldTable);
344fc06a3f8SIngo Weinhold		return true;
345fc06a3f8SIngo Weinhold	}
346fc06a3f8SIngo Weinhold
3479d053f59SAdrien Destugues	/*! \brief Iterator for BOpenHashMap
3489d053f59SAdrien Destugues
3499d053f59SAdrien Destugues		The iterator is not invalidated when removing the current element from
3509d053f59SAdrien Destugues		the table, unless the removal triggers a resize.
3519d053f59SAdrien Destugues	*/
3528ac2dba3SHugo Santos	class Iterator {
3538ac2dba3SHugo Santos	public:
3545147963dSStephan Aßmus		Iterator(const HashTable* table)
35501a10fc5SHugo Santos			: fTable(table)
3568ac2dba3SHugo Santos		{
3578ac2dba3SHugo Santos			Rewind();
3588ac2dba3SHugo Santos		}
3598ac2dba3SHugo Santos
3605147963dSStephan Aßmus		Iterator(const HashTable* table, size_t index, ValueType* value)
361505e9853SHugo Santos			: fTable(table), fIndex(index), fNext(value) {}
362505e9853SHugo Santos
3638ac2dba3SHugo Santos		bool HasNext() const { return fNext != NULL; }
3648ac2dba3SHugo Santos
3655147963dSStephan Aßmus		ValueType* Next()
3668ac2dba3SHugo Santos		{
3675147963dSStephan Aßmus			ValueType* current = fNext;
3688ac2dba3SHugo Santos			_GetNext();
3698ac2dba3SHugo Santos			return current;
3708ac2dba3SHugo Santos		}
3718ac2dba3SHugo Santos
3728ac2dba3SHugo Santos		void Rewind()
3738ac2dba3SHugo Santos		{
3748ac2dba3SHugo Santos			// get the first one
3758ac2dba3SHugo Santos			fIndex = 0;
37601a10fc5SHugo Santos			fNext = NULL;
3778ac2dba3SHugo Santos			_GetNext();
3788ac2dba3SHugo Santos		}
3798ac2dba3SHugo Santos
3808465a069SHugo Santos	protected:
3818465a069SHugo Santos		Iterator() {}
3828465a069SHugo Santos
3838ac2dba3SHugo Santos		void _GetNext()
3848ac2dba3SHugo Santos		{
38501a10fc5SHugo Santos			if (fNext)
3865147963dSStephan Aßmus				fNext = fTable->_Link(fNext);
3878ac2dba3SHugo Santos
3888ac2dba3SHugo Santos			while (fNext == NULL && fIndex < fTable->fTableSize)
3898ac2dba3SHugo Santos				fNext = fTable->fTable[fIndex++];
3908ac2dba3SHugo Santos		}
3918ac2dba3SHugo Santos
3925147963dSStephan Aßmus		const HashTable* fTable;
3938ac2dba3SHugo Santos		size_t fIndex;
3945147963dSStephan Aßmus		ValueType* fNext;
3958ac2dba3SHugo Santos	};
3968ac2dba3SHugo Santos
397db28a227SIngo Weinhold	Iterator GetIterator() const
398db28a227SIngo Weinhold	{
399db28a227SIngo Weinhold		return Iterator(this);
400db28a227SIngo Weinhold	}
401db28a227SIngo Weinhold
40294089b90SOliver Tappe	Iterator GetIterator(typename TypeOperation<KeyType>::ConstRefT key) const
403db28a227SIngo Weinhold	{
404db28a227SIngo Weinhold		if (fTableSize == 0)
405db28a227SIngo Weinhold			return Iterator(this, fTableSize, NULL);
406db28a227SIngo Weinhold
407db28a227SIngo Weinhold		size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
408db28a227SIngo Weinhold		ValueType* slot = fTable[index];
409db28a227SIngo Weinhold
410db28a227SIngo Weinhold		while (slot) {
411db28a227SIngo Weinhold			if (fDefinition.Compare(key, slot))
412db28a227SIngo Weinhold				break;
413db28a227SIngo Weinhold			slot = _Link(slot);
414db28a227SIngo Weinhold		}
415db28a227SIngo Weinhold
416db28a227SIngo Weinhold		if (slot == NULL)
417db28a227SIngo Weinhold			return Iterator(this, fTableSize, NULL);
418db28a227SIngo Weinhold
419db28a227SIngo Weinhold		return Iterator(this, index + 1, slot);
420db28a227SIngo Weinhold	}
4218ac2dba3SHugo Santos
422505e9853SHugo Santosprotected:
4238ac2dba3SHugo Santos	// for g++ 2.95
4248ac2dba3SHugo Santos	friend class Iterator;
4258ac2dba3SHugo Santos
4265147963dSStephan Aßmus	void _Insert(ValueType** table, size_t tableSize, ValueType* value)
42785dbe747SHugo Santos	{
42877e70865SHugo Santos		size_t index = fDefinition.Hash(value) & (tableSize - 1);
42985dbe747SHugo Santos
4305147963dSStephan Aßmus		_Link(value) = table[index];
4312586c25eSHugo Santos		table[index] = value;
43285dbe747SHugo Santos	}
43385dbe747SHugo Santos
43485dbe747SHugo Santos	bool _Resize(size_t newSize)
43585dbe747SHugo Santos	{
436fc06a3f8SIngo Weinhold		ValueType** newTable
437b20de45eSIngo Weinhold			= (ValueType**)fAllocator.Allocate(sizeof(ValueType*) * newSize);
43885dbe747SHugo Santos		if (newTable == NULL)
43985dbe747SHugo Santos			return false;
44085dbe747SHugo Santos
441fc06a3f8SIngo Weinhold		_Resize(newTable, newSize);
442fc06a3f8SIngo Weinhold		return true;
443fc06a3f8SIngo Weinhold	}
444fc06a3f8SIngo Weinhold
4454535495dSIngo Weinhold	void _Resize(ValueType** newTable, size_t newSize, void** _oldTable = NULL)
446fc06a3f8SIngo Weinhold	{
44785dbe747SHugo Santos		for (size_t i = 0; i < newSize; i++)
44885dbe747SHugo Santos			newTable[i] = NULL;
44985dbe747SHugo Santos
45085dbe747SHugo Santos		if (fTable) {
45185dbe747SHugo Santos			for (size_t i = 0; i < fTableSize; i++) {
4525147963dSStephan Aßmus				ValueType* bucket = fTable[i];
4532586c25eSHugo Santos				while (bucket) {
4545147963dSStephan Aßmus					ValueType* next = _Link(bucket);
4552586c25eSHugo Santos					_Insert(newTable, newSize, bucket);
4562586c25eSHugo Santos					bucket = next;
4572586c25eSHugo Santos				}
45885dbe747SHugo Santos			}
45985dbe747SHugo Santos
4604535495dSIngo Weinhold			if (_oldTable != NULL)
4614535495dSIngo Weinhold				*_oldTable = fTable;
462b20de45eSIngo Weinhold			else
463b20de45eSIngo Weinhold				fAllocator.Free(fTable);
4644535495dSIngo Weinhold		} else if (_oldTable != NULL)
4654535495dSIngo Weinhold			*_oldTable = NULL;
46685dbe747SHugo Santos
46785dbe747SHugo Santos		fTableSize = newSize;
46885dbe747SHugo Santos		fTable = newTable;
46985dbe747SHugo Santos	}
47085dbe747SHugo Santos
4715147963dSStephan Aßmus	ValueType*& _Link(ValueType* bucket) const
4722586c25eSHugo Santos	{
47377e70865SHugo Santos		return fDefinition.GetLink(bucket);
4742586c25eSHugo Santos	}
4752586c25eSHugo Santos
4765147963dSStephan Aßmus	bool _ExhaustiveSearch(ValueType* value) const
477f6cfc5afSHugo Santos	{
478f6cfc5afSHugo Santos		for (size_t i = 0; i < fTableSize; i++) {
4795147963dSStephan Aßmus			ValueType* bucket = fTable[i];
480f6cfc5afSHugo Santos			while (bucket) {
481f6cfc5afSHugo Santos				if (bucket == value)
482f6cfc5afSHugo Santos					return true;
4835147963dSStephan Aßmus				bucket = _Link(bucket);
484f6cfc5afSHugo Santos			}
485f6cfc5afSHugo Santos		}
486f6cfc5afSHugo Santos
487f6cfc5afSHugo Santos		return false;
488f6cfc5afSHugo Santos	}
489f6cfc5afSHugo Santos
4905147963dSStephan Aßmus	Definition		fDefinition;
491b20de45eSIngo Weinhold	Allocator		fAllocator;
4925147963dSStephan Aßmus	size_t			fTableSize;
4935147963dSStephan Aßmus	size_t			fItemCount;
4945147963dSStephan Aßmus	ValueType**		fTable;
49585dbe747SHugo Santos};
49685dbe747SHugo Santos
49784052230SAxel Dörfler#endif	// _KERNEL_UTIL_OPEN_HASH_TABLE_H