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