1/**********
2This library is free software; you can redistribute it and/or modify it under
3the terms of the GNU Lesser General Public License as published by the
4Free Software Foundation; either version 3 of the License, or (at your
5option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
6
7This library is distributed in the hope that it will be useful, but WITHOUT
8ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
9FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
10more details.
11
12You should have received a copy of the GNU Lesser General Public License
13along with this library; if not, write to the Free Software Foundation, Inc.,
1451 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
15**********/
16// Copyright (c) 1996-2020 Live Networks, Inc. All rights reserved.
17// Basic Hash Table implementation
18// Implementation
19
20#include "BasicHashTable.hh"
21#include "strDup.hh"
22
23#if defined(__WIN32__) || defined(_WIN32)
24#else
25#include <stddef.h>
26#endif
27#include <string.h>
28#include <stdio.h>
29
30// When there are this many entries per bucket, on average, rebuild
31// the table to increase the number of buckets
32#define REBUILD_MULTIPLIER 3
33
34BasicHashTable::BasicHashTable(int keyType)
35 : fBuckets(fStaticBuckets), fNumBuckets(SMALL_HASH_TABLE_SIZE),
36 fNumEntries(0), fRebuildSize(SMALL_HASH_TABLE_SIZE*REBUILD_MULTIPLIER),
37 fDownShift(28), fMask(0x3), fKeyType(keyType) {
38 for (unsigned i = 0; i < SMALL_HASH_TABLE_SIZE; ++i) {
39 fStaticBuckets[i] = NULL;
40 }
41}
42
43BasicHashTable::~BasicHashTable() {
44 // Free all the entries in the table:
45 for (unsigned i = 0; i < fNumBuckets; ++i) {
46 TableEntry* entry;
47 while ((entry = fBuckets[i]) != NULL) {
48 deleteEntry(i, entry);
49 }
50 }
51
52 // Also free the bucket array, if it was dynamically allocated:
53 if (fBuckets != fStaticBuckets) delete[] fBuckets;
54}
55
56void* BasicHashTable::Add(char const* key, void* value) {
57 void* oldValue;
58 unsigned index;
59 TableEntry* entry = lookupKey(key, index);
60 if (entry != NULL) {
61 // There's already an item with this key
62 oldValue = entry->value;
63 } else {
64 // There's no existing entry; create a new one:
65 entry = insertNewEntry(index, key);
66 oldValue = NULL;
67 }
68 entry->value = value;
69
70 // If the table has become too large, rebuild it with more buckets:
71 if (fNumEntries >= fRebuildSize) rebuild();
72
73 return oldValue;
74}
75
76Boolean BasicHashTable::Remove(char const* key) {
77 unsigned index;
78 TableEntry* entry = lookupKey(key, index);
79 if (entry == NULL) return False; // no such entry
80
81 deleteEntry(index, entry);
82
83 return True;
84}
85
86void* BasicHashTable::Lookup(char const* key) const {
87 unsigned index;
88 TableEntry* entry = lookupKey(key, index);
89 if (entry == NULL) return NULL; // no such entry
90
91 return entry->value;
92}
93
94unsigned BasicHashTable::numEntries() const {
95 return fNumEntries;
96}
97
98BasicHashTable::Iterator::Iterator(BasicHashTable const& table)
99 : fTable(table), fNextIndex(0), fNextEntry(NULL) {
100}
101
102void* BasicHashTable::Iterator::next(char const*& key) {
103 while (fNextEntry == NULL) {
104 if (fNextIndex >= fTable.fNumBuckets) return NULL;
105
106 fNextEntry = fTable.fBuckets[fNextIndex++];
107 }
108
109 BasicHashTable::TableEntry* entry = fNextEntry;
110 fNextEntry = entry->fNext;
111
112 key = entry->key;
113 return entry->value;
114}
115
116////////// Implementation of HashTable creation functions //////////
117
118HashTable* HashTable::create(int keyType) {
119 return new BasicHashTable(keyType);
120}
121
122HashTable::Iterator* HashTable::Iterator::create(HashTable const& hashTable) {
123 // "hashTable" is assumed to be a BasicHashTable
124 return new BasicHashTable::Iterator((BasicHashTable const&)hashTable);
125}
126
127////////// Implementation of internal member functions //////////
128
129BasicHashTable::TableEntry* BasicHashTable
130::lookupKey(char const* key, unsigned& index) const {
131 TableEntry* entry;
132 index = hashIndexFromKey(key);
133
134 for (entry = fBuckets[index]; entry != NULL; entry = entry->fNext) {
135 if (keyMatches(key, entry->key)) break;
136 }
137
138 return entry;
139}
140
141Boolean BasicHashTable
142::keyMatches(char const* key1, char const* key2) const {
143 // The way we check the keys for a match depends upon their type:
144 if (fKeyType == STRING_HASH_KEYS) {
145 return (strcmp(key1, key2) == 0);
146 } else if (fKeyType == ONE_WORD_HASH_KEYS) {
147 return (key1 == key2);
148 } else {
149 unsigned* k1 = (unsigned*)key1;
150 unsigned* k2 = (unsigned*)key2;
151
152 for (int i = 0; i < fKeyType; ++i) {
153 if (k1[i] != k2[i]) return False; // keys differ
154 }
155 return True;
156 }
157}
158
159BasicHashTable::TableEntry* BasicHashTable
160::insertNewEntry(unsigned index, char const* key) {
161 TableEntry* entry = new TableEntry();
162 entry->fNext = fBuckets[index];
163 fBuckets[index] = entry;
164
165 ++fNumEntries;
166 assignKey(entry, key);
167
168 return entry;
169}
170
171void BasicHashTable::assignKey(TableEntry* entry, char const* key) {
172 // The way we assign the key depends upon its type:
173 if (fKeyType == STRING_HASH_KEYS) {
174 entry->key = strDup(key);
175 } else if (fKeyType == ONE_WORD_HASH_KEYS) {
176 entry->key = key;
177 } else if (fKeyType > 0) {
178 unsigned* keyFrom = (unsigned*)key;
179 unsigned* keyTo = new unsigned[fKeyType];
180 for (int i = 0; i < fKeyType; ++i) keyTo[i] = keyFrom[i];
181
182 entry->key = (char const*)keyTo;
183 }
184}
185
186void BasicHashTable::deleteEntry(unsigned index, TableEntry* entry) {
187 TableEntry** ep = &fBuckets[index];
188
189 Boolean foundIt = False;
190 while (*ep != NULL) {
191 if (*ep == entry) {
192 foundIt = True;
193 *ep = entry->fNext;
194 break;
195 }
196 ep = &((*ep)->fNext);
197 }
198
199 if (!foundIt) { // shouldn't happen
200#ifdef DEBUG
201 fprintf(stderr, "BasicHashTable[%p]::deleteEntry(%d,%p): internal error - not found (first entry %p", this, index, entry, fBuckets[index]);
202 if (fBuckets[index] != NULL) fprintf(stderr, ", next entry %p", fBuckets[index]->fNext);
203 fprintf(stderr, ")\n");
204#endif
205 }
206
207 --fNumEntries;
208 deleteKey(entry);
209 delete entry;
210}
211
212void BasicHashTable::deleteKey(TableEntry* entry) {
213 // The way we delete the key depends upon its type:
214 if (fKeyType == ONE_WORD_HASH_KEYS) {
215 entry->key = NULL;
216 } else {
217 delete[] (char*)entry->key;
218 entry->key = NULL;
219 }
220}
221
222void BasicHashTable::rebuild() {
223 // Remember the existing table size:
224 unsigned oldSize = fNumBuckets;
225 TableEntry** oldBuckets = fBuckets;
226
227 // Create the new sized table:
228 fNumBuckets *= 4;
229 fBuckets = new TableEntry*[fNumBuckets];
230 for (unsigned i = 0; i < fNumBuckets; ++i) {
231 fBuckets[i] = NULL;
232 }
233 fRebuildSize *= 4;
234 fDownShift -= 2;
235 fMask = (fMask<<2)|0x3;
236
237 // Rehash the existing entries into the new table:
238 for (TableEntry** oldChainPtr = oldBuckets; oldSize > 0;
239 --oldSize, ++oldChainPtr) {
240 for (TableEntry* hPtr = *oldChainPtr; hPtr != NULL;
241 hPtr = *oldChainPtr) {
242 *oldChainPtr = hPtr->fNext;
243
244 unsigned index = hashIndexFromKey(hPtr->key);
245
246 hPtr->fNext = fBuckets[index];
247 fBuckets[index] = hPtr;
248 }
249 }
250
251 // Free the old bucket array, if it was dynamically allocated:
252 if (oldBuckets != fStaticBuckets) delete[] oldBuckets;
253}
254
255unsigned BasicHashTable::hashIndexFromKey(char const* key) const {
256 unsigned result = 0;
257
258 if (fKeyType == STRING_HASH_KEYS) {
259 while (1) {
260 char c = *key++;
261 if (c == 0) break;
262 result += (result<<3) + (unsigned)c;
263 }
264 result &= fMask;
265 } else if (fKeyType == ONE_WORD_HASH_KEYS) {
266 result = randomIndex((uintptr_t)key);
267 } else {
268 unsigned* k = (unsigned*)key;
269 uintptr_t sum = 0;
270 for (int i = 0; i < fKeyType; ++i) {
271 sum += k[i];
272 }
273 result = randomIndex(sum);
274 }
275
276 return result;
277}
278