1/*
2 * Copyright 2007, Hugo Santos. All Rights Reserved.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 *      Hugo Santos, hugosantos@gmail.com
7 */
8#ifndef _KERNEL_UTIL_MULTI_HASH_TABLE_H
9#define _KERNEL_UTIL_MULTI_HASH_TABLE_H
10
11
12#include <KernelExport.h>
13#include <util/kernel_cpp.h>
14#include <util/OpenHashTable.h>
15
16
17// MultiHashTable is a container which acts a bit like multimap<>
18// but with hash table semantics.
19
20// refer to OpenHashTable.h for how to use this container.
21
22template<typename Definition, bool AutoExpand = true,
23	bool CheckDuplicates = false>
24class MultiHashTable : private BOpenHashTable<Definition,
25	AutoExpand, CheckDuplicates> {
26public:
27	typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
28	typedef MultiHashTable<Definition, AutoExpand, CheckDuplicates> MultiTable;
29
30	typedef typename HashTable::Iterator Iterator;
31	typedef typename Definition::KeyType KeyType;
32	typedef typename Definition::ValueType ValueType;
33
34	MultiHashTable()
35		: HashTable() {}
36
37	MultiHashTable(const Definition& definition)
38		: HashTable(definition) {}
39
40	status_t Init(size_t initialSize = HashTable::kMinimumSize)
41	{
42		return HashTable::Init(initialSize);
43	}
44
45	void Insert(ValueType *value)
46	{
47		if (AutoExpand
48			&& HashTable::fItemCount >= (HashTable::fTableSize * 200 / 256))
49			_Resize(HashTable::fTableSize * 2);
50
51		InsertUnchecked(value);
52	}
53
54	void InsertUnchecked(ValueType *value)
55	{
56		_Insert(HashTable::fTable, HashTable::fTableSize, value);
57		HashTable::fItemCount++;
58	}
59
60	bool Remove(ValueType *value)
61	{
62		if (!HashTable::RemoveUnchecked(value))
63			return false;
64
65		if (AutoExpand && HashTable::fTableSize > HashTable::kMinimumSize
66			&& HashTable::fItemCount < (HashTable::fTableSize * 50 / 256))
67			_Resize(HashTable::fTableSize / 2);
68
69		return true;
70	}
71
72	Iterator GetIterator() const { return HashTable::GetIterator(); }
73
74	class ValueIterator : protected Iterator {
75	public:
76		ValueIterator(const HashTable *table, size_t index, ValueType *value)
77			: fOriginalIndex(index), fOriginalValue(value)
78		{
79			Iterator::fTable = table;
80			Rewind();
81		}
82
83		bool HasNext() const
84		{
85			if (Iterator::fNext == NULL)
86				return false;
87			if (Iterator::fNext == fOriginalValue)
88				return true;
89			return ((const MultiTable *)Iterator::fTable)->_Definition().CompareValues(
90				fOriginalValue, Iterator::fNext);
91		}
92
93		void Rewind()
94		{
95			Iterator::fIndex = fOriginalIndex + 1;
96			Iterator::fNext = fOriginalValue;
97		}
98
99		ValueType *Next() { return Iterator::Next(); }
100
101	private:
102		size_t fOriginalIndex;
103		ValueType *fOriginalValue;
104	};
105
106	ValueIterator Lookup(const KeyType &key) const
107	{
108		size_t index = 0;
109		ValueType *slot = NULL;
110		if (HashTable::fTableSize > 0) {
111			index = HashTable::fDefinition.HashKey(key)
112				& (HashTable::fTableSize - 1);
113			slot = HashTable::fTable[index];
114		}
115
116		while (slot) {
117			if (HashTable::fDefinition.Compare(key, slot))
118				break;
119			slot = HashTable::_Link(slot);
120		}
121
122		if (slot == NULL)
123			return ValueIterator(this, HashTable::fTableSize, NULL);
124
125		return ValueIterator(this, index, slot);
126	}
127
128private:
129	// for g++ 2.95
130	friend class ValueIterator;
131
132	const Definition &_Definition() const { return HashTable::fDefinition; }
133
134	void _Insert(ValueType **table, size_t tableSize, ValueType *value)
135	{
136		size_t index = HashTable::fDefinition.Hash(value) & (tableSize - 1);
137
138		ValueType *previous;
139
140		// group values with the same key
141		for (previous = table[index]; previous
142				&& !HashTable::fDefinition.CompareValues(previous, value);
143				previous = HashTable::_Link(previous));
144
145		if (previous) {
146			HashTable::_Link(value) = HashTable::_Link(previous);
147			HashTable::_Link(previous) = value;
148		} else {
149			HashTable::_Link(value) = table[index];
150			table[index] = value;
151		}
152	}
153
154	// TODO use BOpenHashTable's _Resize
155	bool _Resize(size_t newSize)
156	{
157		ValueType **newTable = new ValueType *[newSize];
158		if (newTable == NULL)
159			return false;
160
161		for (size_t i = 0; i < newSize; i++)
162			newTable[i] = NULL;
163
164		if (HashTable::fTable) {
165			for (size_t i = 0; i < HashTable::fTableSize; i++) {
166				ValueType *bucket = HashTable::fTable[i];
167				while (bucket) {
168					ValueType *next = HashTable::_Link(bucket);
169					_Insert(newTable, newSize, bucket);
170					bucket = next;
171				}
172			}
173
174			delete [] HashTable::fTable;
175		}
176
177		HashTable::fTableSize = newSize;
178		HashTable::fTable = newTable;
179		return true;
180	}
181};
182
183#endif	// _KERNEL_UTIL_MULTI_HASH_TABLE_H
184