1 |
|
/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- |
2 |
|
* |
3 |
|
* ***** BEGIN LICENSE BLOCK ***** |
4 |
|
* Version: MPL 1.1/GPL 2.0/LGPL 2.1 |
5 |
|
* |
6 |
|
* The contents of this file are subject to the Mozilla Public License Version |
7 |
|
* 1.1 (the "License"); you may not use this file except in compliance with |
8 |
|
* the License. You may obtain a copy of the License at |
9 |
|
* http://www.mozilla.org/MPL/ |
10 |
|
* |
11 |
|
* Software distributed under the License is distributed on an "AS IS" basis, |
12 |
|
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License |
13 |
|
* for the specific language governing rights and limitations under the |
14 |
|
* License. |
15 |
|
* |
16 |
|
* The Original Code is Mozilla Communicator client code, released |
17 |
|
* March 31, 1998. |
18 |
|
* |
19 |
|
* The Initial Developer of the Original Code is |
20 |
|
* Netscape Communications Corporation. |
21 |
|
* Portions created by the Initial Developer are Copyright (C) 1998 |
22 |
|
* the Initial Developer. All Rights Reserved. |
23 |
|
* |
24 |
|
* Contributor(s): |
25 |
|
* |
26 |
|
* Alternatively, the contents of this file may be used under the terms of |
27 |
|
* either of the GNU General Public License Version 2 or later (the "GPL"), |
28 |
|
* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), |
29 |
|
* in which case the provisions of the GPL or the LGPL are applicable instead |
30 |
|
* of those above. If you wish to allow use of your version of this file only |
31 |
|
* under the terms of either the GPL or the LGPL, and not to allow others to |
32 |
|
* use your version of this file under the terms of the MPL, indicate your |
33 |
|
* decision by deleting the provisions above and replace them with the notice |
34 |
|
* and other provisions required by the GPL or the LGPL. If you do not delete |
35 |
|
* the provisions above, a recipient may use your version of this file under |
36 |
|
* the terms of any one of the MPL, the GPL or the LGPL. |
37 |
|
* |
38 |
|
* ***** END LICENSE BLOCK ***** */ |
39 |
|
|
40 |
|
/* |
41 |
|
* PR hash table package. |
42 |
|
*/ |
43 |
|
#include "jsstddef.h" |
44 |
|
#include <stdlib.h> |
45 |
|
#include <string.h> |
46 |
|
#include "jstypes.h" |
47 |
|
#include "jsbit.h" |
48 |
|
#include "jsutil.h" /* Added by JSIFY */ |
49 |
|
#include "jshash.h" /* Added by JSIFY */ |
50 |
|
|
51 |
|
/* Compute the number of buckets in ht */ |
52 |
|
#define NBUCKETS(ht) JS_BIT(JS_HASH_BITS - (ht)->shift) |
53 |
|
|
54 |
|
/* The smallest table has 16 buckets */ |
55 |
|
#define MINBUCKETSLOG2 4 |
56 |
|
#define MINBUCKETS JS_BIT(MINBUCKETSLOG2) |
57 |
|
|
58 |
|
/* Compute the maximum entries given n buckets that we will tolerate, ~90% */ |
59 |
|
#define OVERLOADED(n) ((n) - ((n) >> 3)) |
60 |
|
|
61 |
|
/* Compute the number of entries below which we shrink the table by half */ |
62 |
|
#define UNDERLOADED(n) (((n) > MINBUCKETS) ? ((n) >> 2) : 0) |
63 |
|
|
64 |
|
/* |
65 |
|
** Stubs for default hash allocator ops. |
66 |
|
*/ |
67 |
|
static void * |
68 |
|
DefaultAllocTable(void *pool, size_t size) |
69 |
280 |
{ |
70 |
280 |
return malloc(size); |
71 |
|
} |
72 |
|
|
73 |
|
static void |
74 |
|
DefaultFreeTable(void *pool, void *item) |
75 |
248 |
{ |
76 |
248 |
free(item); |
77 |
|
} |
78 |
|
|
79 |
|
static JSHashEntry * |
80 |
|
DefaultAllocEntry(void *pool, const void *key) |
81 |
35436 |
{ |
82 |
35436 |
return (JSHashEntry*) malloc(sizeof(JSHashEntry)); |
83 |
|
} |
84 |
|
|
85 |
|
static void |
86 |
|
DefaultFreeEntry(void *pool, JSHashEntry *he, uintN flag) |
87 |
35436 |
{ |
88 |
35436 |
if (flag == HT_FREE_ENTRY) |
89 |
35436 |
free(he); |
90 |
|
} |
91 |
|
|
92 |
|
static JSHashAllocOps defaultHashAllocOps = { |
93 |
|
DefaultAllocTable, DefaultFreeTable, |
94 |
|
DefaultAllocEntry, DefaultFreeEntry |
95 |
|
}; |
96 |
|
|
97 |
|
JS_PUBLIC_API(JSHashTable *) |
98 |
|
JS_NewHashTable(uint32 n, JSHashFunction keyHash, |
99 |
|
JSHashComparator keyCompare, JSHashComparator valueCompare, |
100 |
|
JSHashAllocOps *allocOps, void *allocPriv) |
101 |
2833 |
{ |
102 |
2833 |
JSHashTable *ht; |
103 |
2833 |
size_t nb; |
104 |
|
|
105 |
2833 |
if (n <= MINBUCKETS) { |
106 |
2817 |
n = MINBUCKETSLOG2; |
107 |
|
} else { |
108 |
16 |
n = JS_CeilingLog2(n); |
109 |
16 |
if ((int32)n < 0) |
110 |
0 |
return NULL; |
111 |
|
} |
112 |
|
|
113 |
2833 |
if (!allocOps) allocOps = &defaultHashAllocOps; |
114 |
|
|
115 |
2833 |
ht = (JSHashTable*) allocOps->allocTable(allocPriv, sizeof *ht); |
116 |
2833 |
if (!ht) |
117 |
0 |
return NULL; |
118 |
2833 |
memset(ht, 0, sizeof *ht); |
119 |
2833 |
ht->shift = JS_HASH_BITS - n; |
120 |
2833 |
n = JS_BIT(n); |
121 |
2833 |
nb = n * sizeof(JSHashEntry *); |
122 |
2833 |
ht->buckets = (JSHashEntry**) allocOps->allocTable(allocPriv, nb); |
123 |
2833 |
if (!ht->buckets) { |
124 |
0 |
allocOps->freeTable(allocPriv, ht); |
125 |
0 |
return NULL; |
126 |
|
} |
127 |
2833 |
memset(ht->buckets, 0, nb); |
128 |
|
|
129 |
2833 |
ht->keyHash = keyHash; |
130 |
2833 |
ht->keyCompare = keyCompare; |
131 |
2833 |
ht->valueCompare = valueCompare; |
132 |
2833 |
ht->allocOps = allocOps; |
133 |
2833 |
ht->allocPriv = allocPriv; |
134 |
2833 |
return ht; |
135 |
|
} |
136 |
|
|
137 |
|
JS_PUBLIC_API(void) |
138 |
|
JS_HashTableDestroy(JSHashTable *ht) |
139 |
32 |
{ |
140 |
32 |
uint32 i, n; |
141 |
32 |
JSHashEntry *he, **hep; |
142 |
32 |
JSHashAllocOps *allocOps = ht->allocOps; |
143 |
32 |
void *allocPriv = ht->allocPriv; |
144 |
|
|
145 |
32 |
n = NBUCKETS(ht); |
146 |
23200 |
for (i = 0; i < n; i++) { |
147 |
23168 |
hep = &ht->buckets[i]; |
148 |
31000 |
while ((he = *hep) != NULL) { |
149 |
7832 |
*hep = he->next; |
150 |
7832 |
allocOps->freeEntry(allocPriv, he, HT_FREE_ENTRY); |
151 |
|
} |
152 |
|
} |
153 |
|
#ifdef DEBUG |
154 |
|
memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]); |
155 |
|
#endif |
156 |
32 |
allocOps->freeTable(allocPriv, ht->buckets); |
157 |
|
#ifdef DEBUG |
158 |
|
memset(ht, 0xDB, sizeof *ht); |
159 |
|
#endif |
160 |
32 |
allocOps->freeTable(allocPriv, ht); |
161 |
|
} |
162 |
|
|
163 |
|
/* |
164 |
|
** Multiplicative hash, from Knuth 6.4. |
165 |
|
*/ |
166 |
|
JS_PUBLIC_API(JSHashEntry **) |
167 |
|
JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key) |
168 |
3779041 |
{ |
169 |
3779041 |
JSHashEntry *he, **hep, **hep0; |
170 |
3779041 |
JSHashNumber h; |
171 |
|
|
172 |
|
#ifdef HASHMETER |
173 |
|
ht->nlookups++; |
174 |
|
#endif |
175 |
3779041 |
h = keyHash * JS_GOLDEN_RATIO; |
176 |
3779041 |
h >>= ht->shift; |
177 |
3779041 |
hep = hep0 = &ht->buckets[h]; |
178 |
4076568 |
while ((he = *hep) != NULL) { |
179 |
3371921 |
if (he->keyHash == keyHash && ht->keyCompare(key, he->key)) { |
180 |
|
/* Move to front of chain if not already there */ |
181 |
3074394 |
if (hep != hep0) { |
182 |
95423 |
*hep = he->next; |
183 |
95423 |
he->next = *hep0; |
184 |
95423 |
*hep0 = he; |
185 |
|
} |
186 |
3074394 |
return hep0; |
187 |
|
} |
188 |
297527 |
hep = &he->next; |
189 |
|
#ifdef HASHMETER |
190 |
|
ht->nsteps++; |
191 |
|
#endif |
192 |
|
} |
193 |
704647 |
return hep; |
194 |
|
} |
195 |
|
|
196 |
|
JS_PUBLIC_API(JSHashEntry *) |
197 |
|
JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **hep, |
198 |
|
JSHashNumber keyHash, const void *key, void *value) |
199 |
215632 |
{ |
200 |
215632 |
uint32 i, n; |
201 |
215632 |
JSHashEntry *he, *next, **oldbuckets; |
202 |
215632 |
size_t nb; |
203 |
|
|
204 |
|
/* Grow the table if it is overloaded */ |
205 |
215632 |
n = NBUCKETS(ht); |
206 |
215632 |
if (ht->nentries >= OVERLOADED(n)) { |
207 |
5187 |
oldbuckets = ht->buckets; |
208 |
5187 |
nb = 2 * n * sizeof(JSHashEntry *); |
209 |
5187 |
ht->buckets = (JSHashEntry**) |
210 |
|
ht->allocOps->allocTable(ht->allocPriv, nb); |
211 |
5187 |
if (!ht->buckets) { |
212 |
0 |
ht->buckets = oldbuckets; |
213 |
0 |
return NULL; |
214 |
|
} |
215 |
5187 |
memset(ht->buckets, 0, nb); |
216 |
|
#ifdef HASHMETER |
217 |
|
ht->ngrows++; |
218 |
|
#endif |
219 |
5187 |
ht->shift--; |
220 |
|
|
221 |
359891 |
for (i = 0; i < n; i++) { |
222 |
665070 |
for (he = oldbuckets[i]; he; he = next) { |
223 |
310366 |
next = he->next; |
224 |
310366 |
hep = JS_HashTableRawLookup(ht, he->keyHash, he->key); |
225 |
310366 |
JS_ASSERT(*hep == NULL); |
226 |
310366 |
he->next = NULL; |
227 |
310366 |
*hep = he; |
228 |
|
} |
229 |
|
} |
230 |
|
#ifdef DEBUG |
231 |
|
memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]); |
232 |
|
#endif |
233 |
5187 |
ht->allocOps->freeTable(ht->allocPriv, oldbuckets); |
234 |
5187 |
hep = JS_HashTableRawLookup(ht, keyHash, key); |
235 |
|
} |
236 |
|
|
237 |
|
/* Make a new key value entry */ |
238 |
215632 |
he = ht->allocOps->allocEntry(ht->allocPriv, key); |
239 |
215632 |
if (!he) |
240 |
0 |
return NULL; |
241 |
215632 |
he->keyHash = keyHash; |
242 |
215632 |
he->key = key; |
243 |
215632 |
he->value = value; |
244 |
215632 |
he->next = *hep; |
245 |
215632 |
*hep = he; |
246 |
215632 |
ht->nentries++; |
247 |
215632 |
return he; |
248 |
|
} |
249 |
|
|
250 |
|
JS_PUBLIC_API(JSHashEntry *) |
251 |
|
JS_HashTableAdd(JSHashTable *ht, const void *key, void *value) |
252 |
0 |
{ |
253 |
0 |
JSHashNumber keyHash; |
254 |
0 |
JSHashEntry *he, **hep; |
255 |
|
|
256 |
0 |
keyHash = ht->keyHash(key); |
257 |
0 |
hep = JS_HashTableRawLookup(ht, keyHash, key); |
258 |
0 |
if ((he = *hep) != NULL) { |
259 |
|
/* Hit; see if values match */ |
260 |
0 |
if (ht->valueCompare(he->value, value)) { |
261 |
|
/* key,value pair is already present in table */ |
262 |
0 |
return he; |
263 |
|
} |
264 |
0 |
if (he->value) |
265 |
0 |
ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_VALUE); |
266 |
0 |
he->value = value; |
267 |
0 |
return he; |
268 |
|
} |
269 |
0 |
return JS_HashTableRawAdd(ht, hep, keyHash, key, value); |
270 |
|
} |
271 |
|
|
272 |
|
JS_PUBLIC_API(void) |
273 |
|
JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he) |
274 |
76304 |
{ |
275 |
76304 |
uint32 i, n; |
276 |
76304 |
JSHashEntry *next, **oldbuckets; |
277 |
76304 |
size_t nb; |
278 |
|
|
279 |
76304 |
*hep = he->next; |
280 |
76304 |
ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY); |
281 |
|
|
282 |
|
/* Shrink table if it's underloaded */ |
283 |
76304 |
n = NBUCKETS(ht); |
284 |
76304 |
if (--ht->nentries < UNDERLOADED(n)) { |
285 |
158 |
oldbuckets = ht->buckets; |
286 |
158 |
nb = n * sizeof(JSHashEntry*) / 2; |
287 |
158 |
ht->buckets = (JSHashEntry**) |
288 |
|
ht->allocOps->allocTable(ht->allocPriv, nb); |
289 |
158 |
if (!ht->buckets) { |
290 |
0 |
ht->buckets = oldbuckets; |
291 |
0 |
return; |
292 |
|
} |
293 |
158 |
memset(ht->buckets, 0, nb); |
294 |
|
#ifdef HASHMETER |
295 |
|
ht->nshrinks++; |
296 |
|
#endif |
297 |
158 |
ht->shift++; |
298 |
|
|
299 |
207902 |
for (i = 0; i < n; i++) { |
300 |
247933 |
for (he = oldbuckets[i]; he; he = next) { |
301 |
40189 |
next = he->next; |
302 |
40189 |
hep = JS_HashTableRawLookup(ht, he->keyHash, he->key); |
303 |
40189 |
JS_ASSERT(*hep == NULL); |
304 |
40189 |
he->next = NULL; |
305 |
40189 |
*hep = he; |
306 |
|
} |
307 |
|
} |
308 |
|
#ifdef DEBUG |
309 |
|
memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]); |
310 |
|
#endif |
311 |
158 |
ht->allocOps->freeTable(ht->allocPriv, oldbuckets); |
312 |
|
} |
313 |
|
} |
314 |
|
|
315 |
|
JS_PUBLIC_API(JSBool) |
316 |
|
JS_HashTableRemove(JSHashTable *ht, const void *key) |
317 |
0 |
{ |
318 |
0 |
JSHashNumber keyHash; |
319 |
0 |
JSHashEntry *he, **hep; |
320 |
|
|
321 |
0 |
keyHash = ht->keyHash(key); |
322 |
0 |
hep = JS_HashTableRawLookup(ht, keyHash, key); |
323 |
0 |
if ((he = *hep) == NULL) |
324 |
0 |
return JS_FALSE; |
325 |
|
|
326 |
|
/* Hit; remove element */ |
327 |
0 |
JS_HashTableRawRemove(ht, hep, he); |
328 |
0 |
return JS_TRUE; |
329 |
|
} |
330 |
|
|
331 |
|
JS_PUBLIC_API(void *) |
332 |
|
JS_HashTableLookup(JSHashTable *ht, const void *key) |
333 |
0 |
{ |
334 |
0 |
JSHashNumber keyHash; |
335 |
0 |
JSHashEntry *he, **hep; |
336 |
|
|
337 |
0 |
keyHash = ht->keyHash(key); |
338 |
0 |
hep = JS_HashTableRawLookup(ht, keyHash, key); |
339 |
0 |
if ((he = *hep) != NULL) { |
340 |
0 |
return he->value; |
341 |
|
} |
342 |
0 |
return NULL; |
343 |
|
} |
344 |
|
|
345 |
|
/* |
346 |
|
** Iterate over the entries in the hash table calling func for each |
347 |
|
** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP). |
348 |
|
** Return a count of the number of elements scanned. |
349 |
|
*/ |
350 |
|
JS_PUBLIC_API(int) |
351 |
|
JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg) |
352 |
2705 |
{ |
353 |
2705 |
JSHashEntry *he, **hep; |
354 |
2705 |
uint32 i, nbuckets; |
355 |
2705 |
int rv, n = 0; |
356 |
2705 |
JSHashEntry *todo = NULL; |
357 |
|
|
358 |
2705 |
nbuckets = NBUCKETS(ht); |
359 |
654481 |
for (i = 0; i < nbuckets; i++) { |
360 |
651776 |
hep = &ht->buckets[i]; |
361 |
1013370 |
while ((he = *hep) != NULL) { |
362 |
361594 |
rv = f(he, n, arg); |
363 |
361594 |
n++; |
364 |
361594 |
if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) { |
365 |
40868 |
*hep = he->next; |
366 |
40868 |
if (rv & HT_ENUMERATE_REMOVE) { |
367 |
40868 |
he->next = todo; |
368 |
40868 |
todo = he; |
369 |
|
} |
370 |
|
} else { |
371 |
320726 |
hep = &he->next; |
372 |
|
} |
373 |
361594 |
if (rv & HT_ENUMERATE_STOP) { |
374 |
0 |
goto out; |
375 |
|
} |
376 |
|
} |
377 |
|
} |
378 |
|
|
379 |
|
out: |
380 |
2705 |
hep = &todo; |
381 |
43573 |
while ((he = *hep) != NULL) { |
382 |
40868 |
JS_HashTableRawRemove(ht, hep, he); |
383 |
|
} |
384 |
2705 |
return n; |
385 |
|
} |
386 |
|
|
387 |
|
#ifdef HASHMETER |
388 |
|
#include <math.h> |
389 |
|
#include <stdio.h> |
390 |
|
|
391 |
|
JS_PUBLIC_API(void) |
392 |
|
JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp) |
393 |
|
{ |
394 |
|
double sqsum, mean, variance, sigma; |
395 |
|
uint32 nchains, nbuckets, nentries; |
396 |
|
uint32 i, n, maxChain, maxChainLen; |
397 |
|
JSHashEntry *he; |
398 |
|
|
399 |
|
sqsum = 0; |
400 |
|
nchains = 0; |
401 |
|
maxChainLen = 0; |
402 |
|
nbuckets = NBUCKETS(ht); |
403 |
|
for (i = 0; i < nbuckets; i++) { |
404 |
|
he = ht->buckets[i]; |
405 |
|
if (!he) |
406 |
|
continue; |
407 |
|
nchains++; |
408 |
|
for (n = 0; he; he = he->next) |
409 |
|
n++; |
410 |
|
sqsum += n * n; |
411 |
|
if (n > maxChainLen) { |
412 |
|
maxChainLen = n; |
413 |
|
maxChain = i; |
414 |
|
} |
415 |
|
} |
416 |
|
nentries = ht->nentries; |
417 |
|
mean = (double)nentries / nchains; |
418 |
|
variance = nchains * sqsum - nentries * nentries; |
419 |
|
if (variance < 0 || nchains == 1) |
420 |
|
variance = 0; |
421 |
|
else |
422 |
|
variance /= nchains * (nchains - 1); |
423 |
|
sigma = sqrt(variance); |
424 |
|
|
425 |
|
fprintf(fp, "\nHash table statistics:\n"); |
426 |
|
fprintf(fp, " number of lookups: %u\n", ht->nlookups); |
427 |
|
fprintf(fp, " number of entries: %u\n", ht->nentries); |
428 |
|
fprintf(fp, " number of grows: %u\n", ht->ngrows); |
429 |
|
fprintf(fp, " number of shrinks: %u\n", ht->nshrinks); |
430 |
|
fprintf(fp, " mean steps per hash: %g\n", (double)ht->nsteps |
431 |
|
/ ht->nlookups); |
432 |
|
fprintf(fp, "mean hash chain length: %g\n", mean); |
433 |
|
fprintf(fp, " standard deviation: %g\n", sigma); |
434 |
|
fprintf(fp, " max hash chain length: %u\n", maxChainLen); |
435 |
|
fprintf(fp, " max hash chain: [%u]\n", maxChain); |
436 |
|
|
437 |
|
for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++) |
438 |
|
if (dump(he, i, fp) != HT_ENUMERATE_NEXT) |
439 |
|
break; |
440 |
|
} |
441 |
|
#endif /* HASHMETER */ |
442 |
|
|
443 |
|
JS_PUBLIC_API(int) |
444 |
|
JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp) |
445 |
0 |
{ |
446 |
0 |
int count; |
447 |
|
|
448 |
0 |
count = JS_HashTableEnumerateEntries(ht, dump, fp); |
449 |
|
#ifdef HASHMETER |
450 |
|
JS_HashTableDumpMeter(ht, dump, fp); |
451 |
|
#endif |
452 |
0 |
return count; |
453 |
|
} |
454 |
|
|
455 |
|
JS_PUBLIC_API(JSHashNumber) |
456 |
|
JS_HashString(const void *key) |
457 |
4759 |
{ |
458 |
4759 |
JSHashNumber h; |
459 |
4759 |
const unsigned char *s; |
460 |
|
|
461 |
4759 |
h = 0; |
462 |
427118 |
for (s = (const unsigned char *)key; *s; s++) |
463 |
422359 |
h = (h >> (JS_HASH_BITS - 4)) ^ (h << 4) ^ *s; |
464 |
4759 |
return h; |
465 |
|
} |
466 |
|
|
467 |
|
JS_PUBLIC_API(int) |
468 |
|
JS_CompareValues(const void *v1, const void *v2) |
469 |
776050 |
{ |
470 |
776050 |
return v1 == v2; |