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