1eff1e73cSAugustin Cavalier/*
2eff1e73cSAugustin CavalierOpen Tracker License
3eff1e73cSAugustin Cavalier
4eff1e73cSAugustin CavalierTerms and Conditions
5eff1e73cSAugustin Cavalier
6eff1e73cSAugustin CavalierCopyright (c) 1991-2000, Be Incorporated. All rights reserved.
7eff1e73cSAugustin Cavalier
8eff1e73cSAugustin CavalierPermission is hereby granted, free of charge, to any person obtaining a copy of
9eff1e73cSAugustin Cavalierthis software and associated documentation files (the "Software"), to deal in
10eff1e73cSAugustin Cavalierthe Software without restriction, including without limitation the rights to
11eff1e73cSAugustin Cavalieruse, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
12eff1e73cSAugustin Cavalierof the Software, and to permit persons to whom the Software is furnished to do
13eff1e73cSAugustin Cavalierso, subject to the following conditions:
14eff1e73cSAugustin Cavalier
15eff1e73cSAugustin CavalierThe above copyright notice and this permission notice applies to all licensees
16eff1e73cSAugustin Cavalierand shall be included in all copies or substantial portions of the Software.
17eff1e73cSAugustin Cavalier
18eff1e73cSAugustin CavalierTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19eff1e73cSAugustin CavalierIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF TITLE, MERCHANTABILITY,
20eff1e73cSAugustin CavalierFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
21eff1e73cSAugustin CavalierBE INCORPORATED BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
22eff1e73cSAugustin CavalierAN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF, OR IN CONNECTION
23eff1e73cSAugustin CavalierWITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24eff1e73cSAugustin Cavalier
25eff1e73cSAugustin CavalierExcept as contained in this notice, the name of Be Incorporated shall not be
26eff1e73cSAugustin Cavalierused in advertising or otherwise to promote the sale, use or other dealings in
27eff1e73cSAugustin Cavalierthis Software without prior written authorization from Be Incorporated.
28eff1e73cSAugustin Cavalier
29eff1e73cSAugustin CavalierTracker(TM), Be(R), BeOS(R), and BeIA(TM) are trademarks or registered trademarks
30eff1e73cSAugustin Cavalierof Be Incorporated in the United States and other countries. Other brand product
31eff1e73cSAugustin Cavaliernames are registered trademarks or trademarks of their respective holders.
32eff1e73cSAugustin CavalierAll rights reserved.
33eff1e73cSAugustin Cavalier*/
34eff1e73cSAugustin Cavalier
35eff1e73cSAugustin Cavalier// bonefish:
36eff1e73cSAugustin Cavalier// * removed need for exceptions
37eff1e73cSAugustin Cavalier// * fixed warnings
38eff1e73cSAugustin Cavalier// * implemented rehashing
39eff1e73cSAugustin Cavalier// * added RemoveAll()
40eff1e73cSAugustin Cavalier// TODO:
41eff1e73cSAugustin Cavalier// * shrinking of element vectors
42eff1e73cSAugustin Cavalier
43eff1e73cSAugustin Cavalier// Hash table with open addresssing
44eff1e73cSAugustin Cavalier
45eff1e73cSAugustin Cavalier#ifndef __OPEN_HASH_TABLE__
46eff1e73cSAugustin Cavalier#define __OPEN_HASH_TABLE__
47eff1e73cSAugustin Cavalier
48eff1e73cSAugustin Cavalier#include <stdlib.h>
49eff1e73cSAugustin Cavalier#include <new>
50eff1e73cSAugustin Cavalier
51eff1e73cSAugustin Cavalier// don't include <Debug.h>
52eff1e73cSAugustin Cavalier#ifndef _OPEN_HASH_TABLE_ASSERT
53eff1e73cSAugustin Cavalier#	define _OPEN_HASH_TABLE_ASSERT(E)	(void)0
54eff1e73cSAugustin Cavalier#endif
55eff1e73cSAugustin Cavalier#ifndef _OPEN_HASH_TABLE_TRESPASS
56eff1e73cSAugustin Cavalier#	define _OPEN_HASH_TABLE_TRESPASS()	(void)0
57eff1e73cSAugustin Cavalier#endif
58eff1e73cSAugustin Cavalier
59eff1e73cSAugustin Cavaliernamespace BPrivate {
60eff1e73cSAugustin Cavalier
61eff1e73cSAugustin Cavaliertemplate <class Element>
62eff1e73cSAugustin Cavalierclass ElementVector {
63eff1e73cSAugustin Cavalier	// element vector for OpenHashTable needs to implement this
64eff1e73cSAugustin Cavalier	// interface
65eff1e73cSAugustin Cavalierpublic:
66eff1e73cSAugustin Cavalier	Element &At(int32 index);
67eff1e73cSAugustin Cavalier	Element *Add();
68eff1e73cSAugustin Cavalier	int32 IndexOf(const Element &) const;
69eff1e73cSAugustin Cavalier	void Remove(int32 index);
70eff1e73cSAugustin Cavalier};
71eff1e73cSAugustin Cavalier
72eff1e73cSAugustin Cavalierclass OpenHashElement {
73eff1e73cSAugustin Cavalierpublic:
74eff1e73cSAugustin Cavalier	uint32 Hash() const;
75eff1e73cSAugustin Cavalier	bool operator==(const OpenHashElement &) const;
76eff1e73cSAugustin Cavalier	void Adopt(OpenHashElement &);
77eff1e73cSAugustin Cavalier		// low overhead copy, original element is in undefined state
78eff1e73cSAugustin Cavalier		// after call (calls Adopt on BString members, etc.)
79eff1e73cSAugustin Cavalier	int32 fNext;
80eff1e73cSAugustin Cavalier};
81eff1e73cSAugustin Cavalier
82eff1e73cSAugustin Cavalierconst uint32 kPrimes [] = {
83eff1e73cSAugustin Cavalier	509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139,
84eff1e73cSAugustin Cavalier	524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859,
85eff1e73cSAugustin Cavalier	134217689, 268435399, 536870909, 1073741789, 2147483647, 0
86eff1e73cSAugustin Cavalier};
87eff1e73cSAugustin Cavalier
88eff1e73cSAugustin Cavaliertemplate <class Element, class ElementVec = ElementVector<Element> >
89eff1e73cSAugustin Cavalierclass OpenHashTable {
90eff1e73cSAugustin Cavalierpublic:
91eff1e73cSAugustin Cavalier	OpenHashTable(int32 minSize, ElementVec *elementVector = 0,
92eff1e73cSAugustin Cavalier				  float maxLoadFactor = 0.8);
93eff1e73cSAugustin Cavalier		// it is up to the subclass of OpenHashTable to supply
94eff1e73cSAugustin Cavalier		// elementVector
95eff1e73cSAugustin Cavalier	~OpenHashTable();
96eff1e73cSAugustin Cavalier
97eff1e73cSAugustin Cavalier	bool InitCheck() const;
98eff1e73cSAugustin Cavalier
99eff1e73cSAugustin Cavalier	void SetElementVector(ElementVec *elementVector);
100eff1e73cSAugustin Cavalier
101eff1e73cSAugustin Cavalier	Element *FindFirst(uint32 elementHash) const;
102eff1e73cSAugustin Cavalier	Element *Add(uint32 elementHash);
103eff1e73cSAugustin Cavalier
104eff1e73cSAugustin Cavalier	void Remove(Element *element, bool dontRehash = false);
105eff1e73cSAugustin Cavalier	void RemoveAll();
106eff1e73cSAugustin Cavalier
107eff1e73cSAugustin Cavalier	// when calling Add, any outstanding element pointer may become
108eff1e73cSAugustin Cavalier	// invalid; to deal with this, get the element index and restore
109eff1e73cSAugustin Cavalier	// it after the add
110eff1e73cSAugustin Cavalier	int32 ElementIndex(const Element *) const;
111eff1e73cSAugustin Cavalier	Element *ElementAt(int32 index) const;
112eff1e73cSAugustin Cavalier
113eff1e73cSAugustin Cavalier	int32 ArraySize() const;
114eff1e73cSAugustin Cavalier	int32 VectorSize() const;
115eff1e73cSAugustin Cavalier	int32 CountElements() const;
116eff1e73cSAugustin Cavalier
117eff1e73cSAugustin Cavalierprotected:
118eff1e73cSAugustin Cavalier	static int32 OptimalSize(int32 minSize);
119eff1e73cSAugustin Cavalier
120eff1e73cSAugustin Cavalierprivate:
121eff1e73cSAugustin Cavalier	bool _RehashIfNeeded();
122eff1e73cSAugustin Cavalier	bool _Rehash();
123eff1e73cSAugustin Cavalier
124eff1e73cSAugustin Cavalier	int32 fArraySize;
125eff1e73cSAugustin Cavalier	int32 fInitialSize;
126eff1e73cSAugustin Cavalier	int32 fElementCount;
127eff1e73cSAugustin Cavalier	int32 *fHashArray;
128eff1e73cSAugustin Cavalier	ElementVec *fElementVector;
129eff1e73cSAugustin Cavalier	float fMaxLoadFactor;
130eff1e73cSAugustin Cavalier};
131eff1e73cSAugustin Cavalier
132eff1e73cSAugustin Cavaliertemplate <class Element>
133eff1e73cSAugustin Cavalierclass OpenHashElementArray : public ElementVector<Element> {
134eff1e73cSAugustin Cavalier	// this is a straightforward implementation of an element vector
135eff1e73cSAugustin Cavalier	// deleting is handled by linking deleted elements into a free list
136eff1e73cSAugustin Cavalier	// the vector never shrinks
137eff1e73cSAugustin Cavalierpublic:
138eff1e73cSAugustin Cavalier	OpenHashElementArray(int32 initialSize);
139eff1e73cSAugustin Cavalier	~OpenHashElementArray();
140eff1e73cSAugustin Cavalier
141eff1e73cSAugustin Cavalier	bool InitCheck() const;
142eff1e73cSAugustin Cavalier
143eff1e73cSAugustin Cavalier	Element &At(int32 index);
144eff1e73cSAugustin Cavalier	const Element &At(int32 index) const;
145eff1e73cSAugustin Cavalier	Element *Add(const Element &);
146eff1e73cSAugustin Cavalier	Element *Add();
147eff1e73cSAugustin Cavalier	void Remove(int32 index);
148eff1e73cSAugustin Cavalier	int32 IndexOf(const Element &) const;
149eff1e73cSAugustin Cavalier	int32 Size() const;
150eff1e73cSAugustin Cavalier
151eff1e73cSAugustin Cavalierprivate:
152eff1e73cSAugustin Cavalier	Element *fData;
153eff1e73cSAugustin Cavalier	int32 fSize;
154eff1e73cSAugustin Cavalier	int32 fNextFree;
155eff1e73cSAugustin Cavalier	int32 fNextDeleted;
156eff1e73cSAugustin Cavalier};
157eff1e73cSAugustin Cavalier
158eff1e73cSAugustin Cavalier
159eff1e73cSAugustin Cavalier//-----------------------------------
160eff1e73cSAugustin Cavalier
161eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
162eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::OpenHashTable(int32 minSize,
163eff1e73cSAugustin Cavalier	ElementVec *elementVector, float maxLoadFactor)
164eff1e73cSAugustin Cavalier	:	fArraySize(OptimalSize(minSize)),
165eff1e73cSAugustin Cavalier		fInitialSize(fArraySize),
166eff1e73cSAugustin Cavalier		fElementCount(0),
167eff1e73cSAugustin Cavalier		fElementVector(elementVector),
168eff1e73cSAugustin Cavalier		fMaxLoadFactor(maxLoadFactor)
169eff1e73cSAugustin Cavalier{
170eff1e73cSAugustin Cavalier	// sanity check the maximal load factor
171eff1e73cSAugustin Cavalier	if (fMaxLoadFactor < 0.5)
172eff1e73cSAugustin Cavalier		fMaxLoadFactor = 0.5;
173eff1e73cSAugustin Cavalier	// allocate and init the array
174eff1e73cSAugustin Cavalier	fHashArray = (int32*)calloc(fArraySize, sizeof(int32));
175eff1e73cSAugustin Cavalier	if (fHashArray) {
176eff1e73cSAugustin Cavalier		for (int32 index = 0; index < fArraySize; index++)
177eff1e73cSAugustin Cavalier			fHashArray[index] = -1;
178eff1e73cSAugustin Cavalier	}
179eff1e73cSAugustin Cavalier}
180eff1e73cSAugustin Cavalier
181eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
182eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::~OpenHashTable()
183eff1e73cSAugustin Cavalier{
184eff1e73cSAugustin Cavalier	RemoveAll();
185eff1e73cSAugustin Cavalier	free(fHashArray);
186eff1e73cSAugustin Cavalier}
187eff1e73cSAugustin Cavalier
188eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
189eff1e73cSAugustin Cavalierbool
190eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::InitCheck() const
191eff1e73cSAugustin Cavalier{
192eff1e73cSAugustin Cavalier	return (fHashArray && fElementVector);
193eff1e73cSAugustin Cavalier}
194eff1e73cSAugustin Cavalier
195eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
196eff1e73cSAugustin Cavalierint32
197eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::OptimalSize(int32 minSize)
198eff1e73cSAugustin Cavalier{
199eff1e73cSAugustin Cavalier	for (int32 index = 0; ; index++)
200eff1e73cSAugustin Cavalier		if (!kPrimes[index] || kPrimes[index] >= (uint32)minSize)
201eff1e73cSAugustin Cavalier			return (int32)kPrimes[index];
202eff1e73cSAugustin Cavalier
203eff1e73cSAugustin Cavalier	return 0;
204eff1e73cSAugustin Cavalier}
205eff1e73cSAugustin Cavalier
206eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
207eff1e73cSAugustin CavalierElement *
208eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::FindFirst(uint32 hash) const
209eff1e73cSAugustin Cavalier{
210eff1e73cSAugustin Cavalier	_OPEN_HASH_TABLE_ASSERT(fElementVector);
211eff1e73cSAugustin Cavalier	hash %= fArraySize;
212eff1e73cSAugustin Cavalier	if (fHashArray[hash] < 0)
213eff1e73cSAugustin Cavalier		return 0;
214eff1e73cSAugustin Cavalier
215eff1e73cSAugustin Cavalier	return &fElementVector->At(fHashArray[hash]);
216eff1e73cSAugustin Cavalier}
217eff1e73cSAugustin Cavalier
218eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
219eff1e73cSAugustin Cavalierint32
220eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::ElementIndex(const Element *element) const
221eff1e73cSAugustin Cavalier{
222eff1e73cSAugustin Cavalier	return fElementVector->IndexOf(*element);
223eff1e73cSAugustin Cavalier}
224eff1e73cSAugustin Cavalier
225eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
226eff1e73cSAugustin CavalierElement *
227eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::ElementAt(int32 index) const
228eff1e73cSAugustin Cavalier{
229eff1e73cSAugustin Cavalier	return &fElementVector->At(index);
230eff1e73cSAugustin Cavalier}
231eff1e73cSAugustin Cavalier
232eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
233eff1e73cSAugustin Cavalierint32
234eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::ArraySize() const
235eff1e73cSAugustin Cavalier{
236eff1e73cSAugustin Cavalier	return fArraySize;
237eff1e73cSAugustin Cavalier}
238eff1e73cSAugustin Cavalier
239eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
240eff1e73cSAugustin Cavalierint32
241eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::VectorSize() const
242eff1e73cSAugustin Cavalier{
243eff1e73cSAugustin Cavalier	return fElementVector->Size();
244eff1e73cSAugustin Cavalier}
245eff1e73cSAugustin Cavalier
246eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
247eff1e73cSAugustin Cavalierint32
248eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::CountElements() const
249eff1e73cSAugustin Cavalier{
250eff1e73cSAugustin Cavalier	return fElementCount;
251eff1e73cSAugustin Cavalier}
252eff1e73cSAugustin Cavalier
253eff1e73cSAugustin Cavalier
254eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
255eff1e73cSAugustin CavalierElement *
256eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::Add(uint32 hash)
257eff1e73cSAugustin Cavalier{
258eff1e73cSAugustin Cavalier	_OPEN_HASH_TABLE_ASSERT(fElementVector);
259eff1e73cSAugustin Cavalier	_RehashIfNeeded();
260eff1e73cSAugustin Cavalier	hash %= fArraySize;
261eff1e73cSAugustin Cavalier	Element *result = fElementVector->Add();
262eff1e73cSAugustin Cavalier	if (result) {
263eff1e73cSAugustin Cavalier		result->fNext = fHashArray[hash];
264eff1e73cSAugustin Cavalier		fHashArray[hash] = fElementVector->IndexOf(*result);
265eff1e73cSAugustin Cavalier		fElementCount++;
266eff1e73cSAugustin Cavalier	}
267eff1e73cSAugustin Cavalier	return result;
268eff1e73cSAugustin Cavalier}
269eff1e73cSAugustin Cavalier
270eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
271eff1e73cSAugustin Cavaliervoid
272eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::Remove(Element *element, bool dontRehash)
273eff1e73cSAugustin Cavalier{
274eff1e73cSAugustin Cavalier	if (!dontRehash)
275eff1e73cSAugustin Cavalier		_RehashIfNeeded();
276eff1e73cSAugustin Cavalier	uint32 hash = element->Hash() % fArraySize;
277eff1e73cSAugustin Cavalier	int32 next = fHashArray[hash];
278eff1e73cSAugustin Cavalier	_OPEN_HASH_TABLE_ASSERT(next >= 0);
279eff1e73cSAugustin Cavalier
280eff1e73cSAugustin Cavalier	if (&fElementVector->At(next) == element) {
281eff1e73cSAugustin Cavalier		fHashArray[hash] = element->fNext;
282eff1e73cSAugustin Cavalier		fElementVector->Remove(next);
283eff1e73cSAugustin Cavalier		fElementCount--;
284eff1e73cSAugustin Cavalier		return;
285eff1e73cSAugustin Cavalier	}
286eff1e73cSAugustin Cavalier
287eff1e73cSAugustin Cavalier	for (int32 index = next; index >= 0; ) {
288eff1e73cSAugustin Cavalier		// look for an existing match in table
289eff1e73cSAugustin Cavalier		next = fElementVector->At(index).fNext;
290eff1e73cSAugustin Cavalier		if (next < 0) {
291eff1e73cSAugustin Cavalier			_OPEN_HASH_TABLE_TRESPASS();
292eff1e73cSAugustin Cavalier			return;
293eff1e73cSAugustin Cavalier		}
294eff1e73cSAugustin Cavalier
295eff1e73cSAugustin Cavalier		if (&fElementVector->At(next) == element) {
296eff1e73cSAugustin Cavalier			fElementVector->At(index).fNext = element->fNext;
297eff1e73cSAugustin Cavalier			fElementVector->Remove(next);
298eff1e73cSAugustin Cavalier			fElementCount--;
299eff1e73cSAugustin Cavalier			return;
300eff1e73cSAugustin Cavalier		}
301eff1e73cSAugustin Cavalier		index = next;
302eff1e73cSAugustin Cavalier	}
303eff1e73cSAugustin Cavalier}
304eff1e73cSAugustin Cavalier
305eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
306eff1e73cSAugustin Cavaliervoid
307eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::RemoveAll()
308eff1e73cSAugustin Cavalier{
309eff1e73cSAugustin Cavalier	for (int32 i = 0; fElementCount > 0 && i < fArraySize; i++) {
310eff1e73cSAugustin Cavalier		int32 index = fHashArray[i];
311eff1e73cSAugustin Cavalier		while (index >= 0) {
312eff1e73cSAugustin Cavalier			Element* element = &fElementVector->At(index);
313eff1e73cSAugustin Cavalier			int32 next = element->fNext;
314eff1e73cSAugustin Cavalier			fElementVector->Remove(index);
315eff1e73cSAugustin Cavalier			fElementCount--;
316eff1e73cSAugustin Cavalier			index = next;
317eff1e73cSAugustin Cavalier		}
318eff1e73cSAugustin Cavalier		fHashArray[i] = -1;
319eff1e73cSAugustin Cavalier	}
320eff1e73cSAugustin Cavalier	_RehashIfNeeded();
321eff1e73cSAugustin Cavalier}
322eff1e73cSAugustin Cavalier
323eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
324eff1e73cSAugustin Cavaliervoid
325eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::SetElementVector(ElementVec *elementVector)
326eff1e73cSAugustin Cavalier{
327eff1e73cSAugustin Cavalier	fElementVector = elementVector;
328eff1e73cSAugustin Cavalier}
329eff1e73cSAugustin Cavalier
330eff1e73cSAugustin Cavalier// _RehashIfNeeded
331eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
332eff1e73cSAugustin Cavalierbool
333eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::_RehashIfNeeded()
334eff1e73cSAugustin Cavalier{
335eff1e73cSAugustin Cavalier	// The load factor range [fMaxLoadFactor / 3, fMaxLoadFactor] is fine,
336eff1e73cSAugustin Cavalier	// I think. After rehashing the load factor will be about
337eff1e73cSAugustin Cavalier	// fMaxLoadFactor * 2 / 3, respectively fMaxLoadFactor / 2.
338eff1e73cSAugustin Cavalier	float loadFactor = (float)fElementCount / (float)fArraySize;
339eff1e73cSAugustin Cavalier	if (loadFactor > fMaxLoadFactor
340eff1e73cSAugustin Cavalier		|| (fArraySize > fInitialSize && loadFactor < fMaxLoadFactor / 3)) {
341eff1e73cSAugustin Cavalier		return _Rehash();
342eff1e73cSAugustin Cavalier	}
343eff1e73cSAugustin Cavalier	return true;
344eff1e73cSAugustin Cavalier}
345eff1e73cSAugustin Cavalier
346eff1e73cSAugustin Cavalier// _Rehash
347eff1e73cSAugustin Cavaliertemplate<class Element, class ElementVec>
348eff1e73cSAugustin Cavalierbool
349eff1e73cSAugustin CavalierOpenHashTable<Element, ElementVec>::_Rehash()
350eff1e73cSAugustin Cavalier{
351eff1e73cSAugustin Cavalier	bool result = true;
352eff1e73cSAugustin Cavalier	int32 newSize = int32(fElementCount * 1.73 * fMaxLoadFactor);
353eff1e73cSAugustin Cavalier	newSize = (fInitialSize > newSize ? fInitialSize : newSize);
354eff1e73cSAugustin Cavalier	if (newSize != fArraySize) {
355eff1e73cSAugustin Cavalier		// allocate a new array
356eff1e73cSAugustin Cavalier		int32 *newHashArray = (int32*)calloc(newSize, sizeof(int32));
357eff1e73cSAugustin Cavalier		if (newHashArray) {
358eff1e73cSAugustin Cavalier			// init the new hash array
359eff1e73cSAugustin Cavalier			for (int32 index = 0; index < newSize; index++)
360eff1e73cSAugustin Cavalier				newHashArray[index] = -1;
361eff1e73cSAugustin Cavalier			// iterate through all elements and put them into the new
362eff1e73cSAugustin Cavalier			// hash array
363eff1e73cSAugustin Cavalier			for (int i = 0; i < fArraySize; i++) {
364eff1e73cSAugustin Cavalier				int32 index = fHashArray[i];
365eff1e73cSAugustin Cavalier				while (index >= 0) {
366eff1e73cSAugustin Cavalier					// insert the element in the new array
367eff1e73cSAugustin Cavalier					Element &element = fElementVector->At(index);
368eff1e73cSAugustin Cavalier					int32 next = element.fNext;
369eff1e73cSAugustin Cavalier					uint32 hash = (element.Hash() % newSize);
370eff1e73cSAugustin Cavalier					element.fNext = newHashArray[hash];
371eff1e73cSAugustin Cavalier					newHashArray[hash] = index;
372eff1e73cSAugustin Cavalier					// next element in old list
373eff1e73cSAugustin Cavalier					index = next;
374eff1e73cSAugustin Cavalier				}
375eff1e73cSAugustin Cavalier			}
376eff1e73cSAugustin Cavalier			// delete the old array and set the new one
377eff1e73cSAugustin Cavalier			free(fHashArray);
378eff1e73cSAugustin Cavalier			fHashArray = newHashArray;
379eff1e73cSAugustin Cavalier			fArraySize = newSize;
380eff1e73cSAugustin Cavalier		} else
381eff1e73cSAugustin Cavalier			result = false;
382eff1e73cSAugustin Cavalier	}
383eff1e73cSAugustin Cavalier	return result;
384eff1e73cSAugustin Cavalier}
385eff1e73cSAugustin Cavalier
386eff1e73cSAugustin Cavalier
387eff1e73cSAugustin Cavaliertemplate<class Element>
388eff1e73cSAugustin CavalierOpenHashElementArray<Element>::OpenHashElementArray(int32 initialSize)
389eff1e73cSAugustin Cavalier	:	fSize(initialSize),
390eff1e73cSAugustin Cavalier		fNextFree(0),
391eff1e73cSAugustin Cavalier		fNextDeleted(-1)
392eff1e73cSAugustin Cavalier{
393eff1e73cSAugustin Cavalier	fData = (Element*)calloc((size_t)initialSize, sizeof(Element));
394eff1e73cSAugustin Cavalier}
395eff1e73cSAugustin Cavalier
396eff1e73cSAugustin Cavaliertemplate<class Element>
397eff1e73cSAugustin CavalierOpenHashElementArray<Element>::~OpenHashElementArray()
398eff1e73cSAugustin Cavalier{
399eff1e73cSAugustin Cavalier	free(fData);
400eff1e73cSAugustin Cavalier}
401eff1e73cSAugustin Cavalier
402eff1e73cSAugustin Cavaliertemplate<class Element>
403eff1e73cSAugustin Cavalierbool
404eff1e73cSAugustin CavalierOpenHashElementArray<Element>::InitCheck() const
405eff1e73cSAugustin Cavalier{
406eff1e73cSAugustin Cavalier	return fData;
407eff1e73cSAugustin Cavalier}
408eff1e73cSAugustin Cavalier
409eff1e73cSAugustin Cavaliertemplate<class Element>
410eff1e73cSAugustin CavalierElement &
411eff1e73cSAugustin CavalierOpenHashElementArray<Element>::At(int32 index)
412eff1e73cSAugustin Cavalier{
413eff1e73cSAugustin Cavalier	_OPEN_HASH_TABLE_ASSERT(index < fSize);
414eff1e73cSAugustin Cavalier	return fData[index];
415eff1e73cSAugustin Cavalier}
416eff1e73cSAugustin Cavalier
417eff1e73cSAugustin Cavaliertemplate<class Element>
418eff1e73cSAugustin Cavalierconst Element &
419eff1e73cSAugustin CavalierOpenHashElementArray<Element>::At(int32 index) const
420eff1e73cSAugustin Cavalier{
421eff1e73cSAugustin Cavalier	_OPEN_HASH_TABLE_ASSERT(index < fSize);
422eff1e73cSAugustin Cavalier	return fData[index];
423eff1e73cSAugustin Cavalier}
424eff1e73cSAugustin Cavalier
425eff1e73cSAugustin Cavaliertemplate<class Element>
426eff1e73cSAugustin Cavalierint32
427eff1e73cSAugustin CavalierOpenHashElementArray<Element>::IndexOf(const Element &element) const
428eff1e73cSAugustin Cavalier{
429eff1e73cSAugustin Cavalier	int32 result = &element - fData;
430eff1e73cSAugustin Cavalier	if (result < 0 || result > fSize)
431eff1e73cSAugustin Cavalier		return -1;
432eff1e73cSAugustin Cavalier
433eff1e73cSAugustin Cavalier	return result;
434eff1e73cSAugustin Cavalier}
435eff1e73cSAugustin Cavalier
436eff1e73cSAugustin Cavaliertemplate<class Element>
437eff1e73cSAugustin Cavalierint32
438eff1e73cSAugustin CavalierOpenHashElementArray<Element>::Size() const
439eff1e73cSAugustin Cavalier{
440eff1e73cSAugustin Cavalier	return fSize;
441eff1e73cSAugustin Cavalier}
442eff1e73cSAugustin Cavalier
443eff1e73cSAugustin Cavalier
444eff1e73cSAugustin Cavaliertemplate<class Element>
445eff1e73cSAugustin CavalierElement *
446eff1e73cSAugustin CavalierOpenHashElementArray<Element>::Add(const Element &newElement)
447eff1e73cSAugustin Cavalier{
448eff1e73cSAugustin Cavalier	Element *element = Add();
449eff1e73cSAugustin Cavalier	if (element)
450eff1e73cSAugustin Cavalier		element->Adopt(newElement);
451eff1e73cSAugustin Cavalier	return element;
452eff1e73cSAugustin Cavalier}
453eff1e73cSAugustin Cavalier
454eff1e73cSAugustin Cavalier#if DEBUG
455eff1e73cSAugustin Cavalierconst int32 kGrowChunk = 10;
456eff1e73cSAugustin Cavalier#else
457eff1e73cSAugustin Cavalierconst int32 kGrowChunk = 1024;
458eff1e73cSAugustin Cavalier#endif
459eff1e73cSAugustin Cavalier
460eff1e73cSAugustin Cavaliertemplate<class Element>
461eff1e73cSAugustin CavalierElement *
462eff1e73cSAugustin CavalierOpenHashElementArray<Element>::Add()
463eff1e73cSAugustin Cavalier{
464eff1e73cSAugustin Cavalier	int32 index = fNextFree;
465eff1e73cSAugustin Cavalier	if (fNextDeleted >= 0) {
466eff1e73cSAugustin Cavalier		index = fNextDeleted;
467eff1e73cSAugustin Cavalier		fNextDeleted = At(index).fNext;
468eff1e73cSAugustin Cavalier	} else if (fNextFree >= fSize - 1) {
469eff1e73cSAugustin Cavalier		int32 newSize = fSize + kGrowChunk;
470eff1e73cSAugustin Cavalier/*
471eff1e73cSAugustin Cavalier		Element *newData = (Element *)calloc((size_t)newSize , sizeof(Element));
472eff1e73cSAugustin Cavalier		if (!newData)
473eff1e73cSAugustin Cavalier			return NULL;
474eff1e73cSAugustin Cavalier		memcpy(newData, fData, fSize * sizeof(Element));
475eff1e73cSAugustin Cavalier		free(fData);
476eff1e73cSAugustin Cavalier*/
4771705656eSAugustin Cavalier		Element *newData = (Element*)realloc((void*)fData,
478eff1e73cSAugustin Cavalier			(size_t)newSize * sizeof(Element));
479eff1e73cSAugustin Cavalier		if (!newData)
480eff1e73cSAugustin Cavalier			return NULL;
481eff1e73cSAugustin Cavalier
482eff1e73cSAugustin Cavalier		fData = newData;
483eff1e73cSAugustin Cavalier		fSize = newSize;
484eff1e73cSAugustin Cavalier		index = fNextFree;
485eff1e73cSAugustin Cavalier		fNextFree++;
486eff1e73cSAugustin Cavalier	} else
487eff1e73cSAugustin Cavalier		fNextFree++;
488eff1e73cSAugustin Cavalier
489eff1e73cSAugustin Cavalier	new (&At(index)) Element;
490eff1e73cSAugustin Cavalier		// call placement new to initialize the element properly
491eff1e73cSAugustin Cavalier	_OPEN_HASH_TABLE_ASSERT(At(index).fNext == -1);
492eff1e73cSAugustin Cavalier
493eff1e73cSAugustin Cavalier	return &At(index);
494eff1e73cSAugustin Cavalier}
495eff1e73cSAugustin Cavalier
496eff1e73cSAugustin Cavaliertemplate<class Element>
497eff1e73cSAugustin Cavaliervoid
498eff1e73cSAugustin CavalierOpenHashElementArray<Element>::Remove(int32 index)
499eff1e73cSAugustin Cavalier{
500eff1e73cSAugustin Cavalier	// delete by chaining empty elements in a single linked
501eff1e73cSAugustin Cavalier	// list, reusing the next field
502eff1e73cSAugustin Cavalier	_OPEN_HASH_TABLE_ASSERT(index < fSize);
503eff1e73cSAugustin Cavalier	At(index).~Element();
504eff1e73cSAugustin Cavalier		// call the destructor explicitly to destroy the element
505eff1e73cSAugustin Cavalier		// properly
506eff1e73cSAugustin Cavalier	At(index).fNext = fNextDeleted;
507eff1e73cSAugustin Cavalier	fNextDeleted = index;
508eff1e73cSAugustin Cavalier}
509eff1e73cSAugustin Cavalier
510eff1e73cSAugustin Cavalier} // namespace BPrivate
511eff1e73cSAugustin Cavalier
512eff1e73cSAugustin Cavalierusing BPrivate::OpenHashTable;
513eff1e73cSAugustin Cavalier
514eff1e73cSAugustin Cavalier#endif // __OPEN_HASH_TABLE__
515