1/*
2 * Copyright 2005, Haiku.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 *		Axel Dörfler, axeld@pinc-software.de
7 */
8
9
10#include "HashTable.h"
11
12#include <new>
13
14#include <stdlib.h>
15//#include <stdarg.h>
16#include <string.h>
17
18using std::nothrow;
19
20struct HashTable::entry {
21	entry*		next;
22	Hashable*	value;
23};
24
25
26HashTable::HashTable(bool owning, int32 capacity, float loadFactor)
27	:
28	fTable(NULL),
29	fCount(0),
30	fThreshold(0),
31	fOwning(owning)
32{
33	if (capacity < 10)
34		capacity = 10;
35	if (loadFactor <= 0.3)
36		loadFactor = 0.3;
37
38	fLoadFactor = loadFactor;
39	fCapacity = capacity;
40}
41
42
43HashTable::~HashTable()
44{
45	MakeEmpty(fOwning);
46}
47
48
49void
50HashTable::MakeEmpty(bool deleteValues)
51{
52	if (fTable == NULL)
53		return;
54
55	for (int32 index = fCapacity; --index >= 0;) {
56		struct entry *entry, *next;
57
58		for (entry = fTable[index]; entry != NULL; entry = next) {
59			next = entry->next;
60
61			if (deleteValues)
62				delete entry->value;
63			delete entry;
64		}
65	}
66
67	free(fTable);
68	fTable = NULL;
69}
70
71
72Hashable *
73HashTable::GetValue(Hashable& key) const
74{
75	struct entry* entry = _GetHashEntry(key);
76
77	return entry != NULL ? entry->value : NULL;
78}
79
80
81bool
82HashTable::AddItem(Hashable *value)
83{
84	struct entry *entry = _GetHashEntry(*value);
85	int32 hash = value->Hash();
86	int32 index;
87
88	// already in hash?
89	if (entry != NULL)
90		return true;
91
92	if (fCount >= fThreshold)
93		_Rehash();
94
95	index = hash % fCapacity;
96
97	entry = new (nothrow) HashTable::entry;
98	if (entry == NULL)
99		return false;
100
101	entry->value = value;
102	entry->next = fTable[index];
103	fTable[index] = entry;
104	fCount++;
105	return true;
106}
107
108
109Hashable *
110HashTable::RemoveItem(Hashable& key)
111{
112	struct entry* previous = NULL;
113	struct entry* entry;
114	uint32 hash;
115	int32 index;
116
117	if (fTable == NULL)
118		return NULL;
119
120	hash = key.Hash();
121	index = hash % fCapacity;
122
123	for (entry = fTable[index]; entry != NULL; entry = entry->next) {
124		if (entry->value->Hash() == hash && entry->value->CompareTo(key)) {
125			// found value in array
126			Hashable* value;
127
128			if (previous)
129				previous->next = entry->next;
130			else
131				fTable[index] = entry->next;
132
133			fCount--;
134			value = entry->value;
135			delete entry;
136			return value;
137		}
138
139		previous = entry;
140	}
141	return NULL;
142}
143
144
145bool
146HashTable::_Rehash()
147{
148	struct entry** newTable;
149	int32 oldCapacity = fCapacity;
150	int32 newCapacity, i;
151
152	if (fCount != 0)
153		newCapacity = oldCapacity * 2 + 1;
154	else
155		newCapacity = fCapacity;
156
157	newTable = (struct entry **)malloc(newCapacity * sizeof(struct entry *));
158	if (newTable == NULL)
159		return false;
160
161	memset(newTable, 0, newCapacity * sizeof(struct entry *));
162
163	if (fTable != NULL) {
164		// repopulate the entries into the new array
165		for (i = fCapacity; i-- > 0;) {
166			struct entry* entry;
167			struct entry* next;
168
169			for (entry = fTable[i]; entry != NULL; entry = next) {
170				next = entry->next;
171
172				int32 index = entry->value->Hash() % newCapacity;
173				entry->next = newTable[index];
174				newTable[index] = entry;
175			}
176		}
177
178		free(fTable);
179	}
180
181	fTable = newTable;
182	fCapacity = newCapacity;
183	fThreshold = int32(newCapacity * fLoadFactor);
184
185	return true;
186}
187
188
189struct HashTable::entry *
190HashTable::_GetHashEntry(Hashable& key) const
191{
192	struct entry* entry;
193	uint32 hash = key.Hash();
194
195	if (fTable == NULL)
196		return NULL;
197
198	for (entry = fTable[hash % fCapacity]; entry != NULL; entry = entry->next) {
199		if (entry->value->Hash() == hash && entry->value->CompareTo(key))
200			return entry;
201	}
202
203	return NULL;
204}
205
206