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