1505e9853SHugo Santos/*
2505e9853SHugo Santos * Copyright 2007, Hugo Santos. All Rights Reserved.
3505e9853SHugo Santos * Distributed under the terms of the MIT License.
4505e9853SHugo Santos *
5505e9853SHugo Santos * Authors:
6505e9853SHugo Santos *      Hugo Santos, hugosantos@gmail.com
7505e9853SHugo Santos */
884052230SAxel Dörfler#ifndef _KERNEL_UTIL_MULTI_HASH_TABLE_H
984052230SAxel Dörfler#define _KERNEL_UTIL_MULTI_HASH_TABLE_H
10505e9853SHugo Santos
11505e9853SHugo Santos
12505e9853SHugo Santos#include <KernelExport.h>
13505e9853SHugo Santos#include <util/kernel_cpp.h>
14505e9853SHugo Santos#include <util/OpenHashTable.h>
15505e9853SHugo Santos
1684052230SAxel Dörfler
17505e9853SHugo Santos// MultiHashTable is a container which acts a bit like multimap<>
18505e9853SHugo Santos// but with hash table semantics.
19505e9853SHugo Santos
20505e9853SHugo Santos// refer to OpenHashTable.h for how to use this container.
21505e9853SHugo Santos
22505e9853SHugo Santostemplate<typename Definition, bool AutoExpand = true,
23505e9853SHugo Santos	bool CheckDuplicates = false>
245147963dSStephan Aßmusclass MultiHashTable : private BOpenHashTable<Definition,
25505e9853SHugo Santos	AutoExpand, CheckDuplicates> {
26505e9853SHugo Santospublic:
275147963dSStephan Aßmus	typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
28505e9853SHugo Santos	typedef MultiHashTable<Definition, AutoExpand, CheckDuplicates> MultiTable;
29505e9853SHugo Santos
30505e9853SHugo Santos	typedef typename HashTable::Iterator Iterator;
31505e9853SHugo Santos	typedef typename Definition::KeyType KeyType;
32505e9853SHugo Santos	typedef typename Definition::ValueType ValueType;
33505e9853SHugo Santos
34276aa463SIngo Weinhold	MultiHashTable()
35276aa463SIngo Weinhold		: HashTable() {}
36505e9853SHugo Santos
37276aa463SIngo Weinhold	MultiHashTable(const Definition& definition)
38276aa463SIngo Weinhold		: HashTable(definition) {}
39505e9853SHugo Santos
40276aa463SIngo Weinhold	status_t Init(size_t initialSize = HashTable::kMinimumSize)
41276aa463SIngo Weinhold	{
42276aa463SIngo Weinhold		return HashTable::Init(initialSize);
43276aa463SIngo Weinhold	}
44505e9853SHugo Santos
45505e9853SHugo Santos	void Insert(ValueType *value)
46505e9853SHugo Santos	{
47505e9853SHugo Santos		if (AutoExpand
48505e9853SHugo Santos			&& HashTable::fItemCount >= (HashTable::fTableSize * 200 / 256))
49505e9853SHugo Santos			_Resize(HashTable::fTableSize * 2);
50505e9853SHugo Santos
51505e9853SHugo Santos		InsertUnchecked(value);
52505e9853SHugo Santos	}
53505e9853SHugo Santos
54505e9853SHugo Santos	void InsertUnchecked(ValueType *value)
55505e9853SHugo Santos	{
56505e9853SHugo Santos		_Insert(HashTable::fTable, HashTable::fTableSize, value);
57505e9853SHugo Santos		HashTable::fItemCount++;
58505e9853SHugo Santos	}
59505e9853SHugo Santos
60505e9853SHugo Santos	bool Remove(ValueType *value)
61505e9853SHugo Santos	{
62505e9853SHugo Santos		if (!HashTable::RemoveUnchecked(value))
63505e9853SHugo Santos			return false;
64505e9853SHugo Santos
65505e9853SHugo Santos		if (AutoExpand && HashTable::fTableSize > HashTable::kMinimumSize
66505e9853SHugo Santos			&& HashTable::fItemCount < (HashTable::fTableSize * 50 / 256))
67505e9853SHugo Santos			_Resize(HashTable::fTableSize / 2);
68505e9853SHugo Santos
69505e9853SHugo Santos		return true;
70505e9853SHugo Santos	}
71505e9853SHugo Santos
728aa4c7e3SHugo Santos	Iterator GetIterator() const { return HashTable::GetIterator(); }
738aa4c7e3SHugo Santos
748465a069SHugo Santos	class ValueIterator : protected Iterator {
758465a069SHugo Santos	public:
768465a069SHugo Santos		ValueIterator(const HashTable *table, size_t index, ValueType *value)
778465a069SHugo Santos			: fOriginalIndex(index), fOriginalValue(value)
788465a069SHugo Santos		{
798465a069SHugo Santos			Iterator::fTable = table;
80f6cfc5afSHugo Santos			Rewind();
818465a069SHugo Santos		}
828465a069SHugo Santos
838465a069SHugo Santos		bool HasNext() const
848465a069SHugo Santos		{
858465a069SHugo Santos			if (Iterator::fNext == NULL)
868465a069SHugo Santos				return false;
878465a069SHugo Santos			if (Iterator::fNext == fOriginalValue)
888465a069SHugo Santos				return true;
898465a069SHugo Santos			return ((const MultiTable *)Iterator::fTable)->_Definition().CompareValues(
908465a069SHugo Santos				fOriginalValue, Iterator::fNext);
918465a069SHugo Santos		}
928465a069SHugo Santos
938465a069SHugo Santos		void Rewind()
948465a069SHugo Santos		{
95f6cfc5afSHugo Santos			Iterator::fIndex = fOriginalIndex + 1;
968465a069SHugo Santos			Iterator::fNext = fOriginalValue;
978465a069SHugo Santos		}
988465a069SHugo Santos
998465a069SHugo Santos		ValueType *Next() { return Iterator::Next(); }
1008465a069SHugo Santos
1018465a069SHugo Santos	private:
1028465a069SHugo Santos		size_t fOriginalIndex;
1038465a069SHugo Santos		ValueType *fOriginalValue;
1048465a069SHugo Santos	};
1058465a069SHugo Santos
1068465a069SHugo Santos	ValueIterator Lookup(const KeyType &key) const
1078465a069SHugo Santos	{
108276aa463SIngo Weinhold		size_t index = 0;
109276aa463SIngo Weinhold		ValueType *slot = NULL;
110276aa463SIngo Weinhold		if (HashTable::fTableSize > 0) {
111276aa463SIngo Weinhold			index = HashTable::fDefinition.HashKey(key)
112276aa463SIngo Weinhold				& (HashTable::fTableSize - 1);
113276aa463SIngo Weinhold			slot = HashTable::fTable[index];
114276aa463SIngo Weinhold		}
1158465a069SHugo Santos
1168465a069SHugo Santos		while (slot) {
1178465a069SHugo Santos			if (HashTable::fDefinition.Compare(key, slot))
1188465a069SHugo Santos				break;
1195147963dSStephan Aßmus			slot = HashTable::_Link(slot);
1208465a069SHugo Santos		}
1218465a069SHugo Santos
1228465a069SHugo Santos		if (slot == NULL)
1238465a069SHugo Santos			return ValueIterator(this, HashTable::fTableSize, NULL);
1248465a069SHugo Santos
1258465a069SHugo Santos		return ValueIterator(this, index, slot);
1268465a069SHugo Santos	}
1278465a069SHugo Santos
128505e9853SHugo Santosprivate:
1298465a069SHugo Santos	// for g++ 2.95
1308465a069SHugo Santos	friend class ValueIterator;
1318465a069SHugo Santos
1328465a069SHugo Santos	const Definition &_Definition() const { return HashTable::fDefinition; }
1338465a069SHugo Santos
134505e9853SHugo Santos	void _Insert(ValueType **table, size_t tableSize, ValueType *value)
135505e9853SHugo Santos	{
136505e9853SHugo Santos		size_t index = HashTable::fDefinition.Hash(value) & (tableSize - 1);
137505e9853SHugo Santos
138505e9853SHugo Santos		ValueType *previous;
139505e9853SHugo Santos
140505e9853SHugo Santos		// group values with the same key
141505e9853SHugo Santos		for (previous = table[index]; previous
142505e9853SHugo Santos				&& !HashTable::fDefinition.CompareValues(previous, value);
1435147963dSStephan Aßmus				previous = HashTable::_Link(previous));
144505e9853SHugo Santos
145505e9853SHugo Santos		if (previous) {
146a636d1e3SFredrik Holmqvist			HashTable::_Link(value) = HashTable::_Link(previous);
147a636d1e3SFredrik Holmqvist			HashTable::_Link(previous) = value;
148505e9853SHugo Santos		} else {
149a636d1e3SFredrik Holmqvist			HashTable::_Link(value) = table[index];
150505e9853SHugo Santos			table[index] = value;
151505e9853SHugo Santos		}
152505e9853SHugo Santos	}
153505e9853SHugo Santos
1545147963dSStephan Aßmus	// TODO use BOpenHashTable's _Resize
155505e9853SHugo Santos	bool _Resize(size_t newSize)
156505e9853SHugo Santos	{
157505e9853SHugo Santos		ValueType **newTable = new ValueType *[newSize];
158505e9853SHugo Santos		if (newTable == NULL)
159505e9853SHugo Santos			return false;
160505e9853SHugo Santos
161505e9853SHugo Santos		for (size_t i = 0; i < newSize; i++)
162505e9853SHugo Santos			newTable[i] = NULL;
163505e9853SHugo Santos
164505e9853SHugo Santos		if (HashTable::fTable) {
165505e9853SHugo Santos			for (size_t i = 0; i < HashTable::fTableSize; i++) {
166505e9853SHugo Santos				ValueType *bucket = HashTable::fTable[i];
167505e9853SHugo Santos				while (bucket) {
168a636d1e3SFredrik Holmqvist					ValueType *next = HashTable::_Link(bucket);
169505e9853SHugo Santos					_Insert(newTable, newSize, bucket);
170505e9853SHugo Santos					bucket = next;
171505e9853SHugo Santos				}
172505e9853SHugo Santos			}
173505e9853SHugo Santos
174505e9853SHugo Santos			delete [] HashTable::fTable;
175505e9853SHugo Santos		}
176505e9853SHugo Santos
177505e9853SHugo Santos		HashTable::fTableSize = newSize;
178505e9853SHugo Santos		HashTable::fTable = newTable;
179505e9853SHugo Santos		return true;
180505e9853SHugo Santos	}
181505e9853SHugo Santos};
182505e9853SHugo Santos
18384052230SAxel Dörfler#endif	// _KERNEL_UTIL_MULTI_HASH_TABLE_H
184