Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : /*
7 : * PL hash table package.
8 : */
9 : #include "plhash.h"
10 : #include "prbit.h"
11 : #include "prlog.h"
12 : #include "prmem.h"
13 : #include "prtypes.h"
14 : #include <stdlib.h>
15 : #include <string.h>
16 :
17 : /* Compute the number of buckets in ht */
18 : #define NBUCKETS(ht) (1 << (PL_HASH_BITS - (ht)->shift))
19 :
20 : /* The smallest table has 16 buckets */
21 : #define MINBUCKETSLOG2 4
22 : #define MINBUCKETS (1 << MINBUCKETSLOG2)
23 :
24 : /* Compute the maximum entries given n buckets that we will tolerate, ~90% */
25 : #define OVERLOADED(n) ((n) - ((n) >> 3))
26 :
27 : /* Compute the number of entries below which we shrink the table by half */
28 : #define UNDERLOADED(n) (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
29 :
30 : /*
31 : ** Stubs for default hash allocator ops.
32 : */
33 : static void * PR_CALLBACK
34 199 : DefaultAllocTable(void *pool, PRSize size)
35 : {
36 199 : return PR_MALLOC(size);
37 : }
38 :
39 : static void PR_CALLBACK
40 45 : DefaultFreeTable(void *pool, void *item)
41 : {
42 45 : PR_Free(item);
43 45 : }
44 :
45 : static PLHashEntry * PR_CALLBACK
46 2243 : DefaultAllocEntry(void *pool, const void *key)
47 : {
48 2243 : return PR_NEW(PLHashEntry);
49 : }
50 :
51 : static void PR_CALLBACK
52 771 : DefaultFreeEntry(void *pool, PLHashEntry *he, PRUintn flag)
53 : {
54 771 : if (flag == HT_FREE_ENTRY)
55 671 : PR_Free(he);
56 771 : }
57 :
58 : static PLHashAllocOps defaultHashAllocOps = {
59 : DefaultAllocTable, DefaultFreeTable,
60 : DefaultAllocEntry, DefaultFreeEntry
61 : };
62 :
63 : PR_IMPLEMENT(PLHashTable *)
64 176 : PL_NewHashTable(PRUint32 n, PLHashFunction keyHash,
65 : PLHashComparator keyCompare, PLHashComparator valueCompare,
66 : const PLHashAllocOps *allocOps, void *allocPriv)
67 : {
68 : PLHashTable *ht;
69 : PRSize nb;
70 :
71 176 : if (n <= MINBUCKETS) {
72 85 : n = MINBUCKETSLOG2;
73 : } else {
74 91 : n = PR_CeilingLog2(n);
75 91 : if ((PRInt32)n < 0)
76 0 : return 0;
77 : }
78 :
79 176 : if (!allocOps) allocOps = &defaultHashAllocOps;
80 :
81 176 : ht = (PLHashTable*)((*allocOps->allocTable)(allocPriv, sizeof *ht));
82 176 : if (!ht)
83 0 : return 0;
84 176 : memset(ht, 0, sizeof *ht);
85 176 : ht->shift = PL_HASH_BITS - n;
86 176 : n = 1 << n;
87 176 : nb = n * sizeof(PLHashEntry *);
88 176 : ht->buckets = (PLHashEntry**)((*allocOps->allocTable)(allocPriv, nb));
89 176 : if (!ht->buckets) {
90 0 : (*allocOps->freeTable)(allocPriv, ht);
91 0 : return 0;
92 : }
93 176 : memset(ht->buckets, 0, nb);
94 :
95 176 : ht->keyHash = keyHash;
96 176 : ht->keyCompare = keyCompare;
97 176 : ht->valueCompare = valueCompare;
98 176 : ht->allocOps = allocOps;
99 176 : ht->allocPriv = allocPriv;
100 176 : return ht;
101 : }
102 :
103 : PR_IMPLEMENT(void)
104 8 : PL_HashTableDestroy(PLHashTable *ht)
105 : {
106 : PRUint32 i, n;
107 : PLHashEntry *he, *next;
108 8 : const PLHashAllocOps *allocOps = ht->allocOps;
109 8 : void *allocPriv = ht->allocPriv;
110 :
111 8 : n = NBUCKETS(ht);
112 136 : for (i = 0; i < n; i++) {
113 128 : for (he = ht->buckets[i]; he; he = next) {
114 0 : next = he->next;
115 0 : (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY);
116 : }
117 : }
118 : #ifdef DEBUG
119 8 : memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
120 : #endif
121 8 : (*allocOps->freeTable)(allocPriv, ht->buckets);
122 : #ifdef DEBUG
123 8 : memset(ht, 0xDB, sizeof *ht);
124 : #endif
125 8 : (*allocOps->freeTable)(allocPriv, ht);
126 8 : }
127 :
128 : /*
129 : ** Multiplicative hash, from Knuth 6.4.
130 : */
131 : #define GOLDEN_RATIO 0x9E3779B9U /* 2/(1+sqrt(5))*(2^32) */
132 :
133 : PR_IMPLEMENT(PLHashEntry **)
134 14649 : PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key)
135 : {
136 : PLHashEntry *he, **hep, **hep0;
137 : PLHashNumber h;
138 :
139 : #ifdef HASHMETER
140 : ht->nlookups++;
141 : #endif
142 14649 : h = keyHash * GOLDEN_RATIO;
143 14649 : h >>= ht->shift;
144 14649 : hep = hep0 = &ht->buckets[h];
145 32330 : while ((he = *hep) != 0) {
146 8175 : if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
147 : /* Move to front of chain if not already there */
148 5143 : if (hep != hep0) {
149 280 : *hep = he->next;
150 280 : he->next = *hep0;
151 280 : *hep0 = he;
152 : }
153 5143 : return hep0;
154 : }
155 3032 : hep = &he->next;
156 : #ifdef HASHMETER
157 : ht->nsteps++;
158 : #endif
159 : }
160 9506 : return hep;
161 : }
162 :
163 : /*
164 : ** Same as PL_HashTableRawLookup but doesn't reorder the hash entries.
165 : */
166 : PR_IMPLEMENT(PLHashEntry **)
167 6312 : PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash,
168 : const void *key)
169 : {
170 : PLHashEntry *he, **hep;
171 : PLHashNumber h;
172 :
173 : #ifdef HASHMETER
174 : ht->nlookups++;
175 : #endif
176 6312 : h = keyHash * GOLDEN_RATIO;
177 6312 : h >>= ht->shift;
178 6312 : hep = &ht->buckets[h];
179 13263 : while ((he = *hep) != 0) {
180 6818 : if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
181 6179 : break;
182 : }
183 639 : hep = &he->next;
184 : #ifdef HASHMETER
185 : ht->nsteps++;
186 : #endif
187 : }
188 6312 : return hep;
189 : }
190 :
191 : PR_IMPLEMENT(PLHashEntry *)
192 3863 : PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep,
193 : PLHashNumber keyHash, const void *key, void *value)
194 : {
195 : PRUint32 i, n;
196 : PLHashEntry *he, *next, **oldbuckets;
197 : PRSize nb;
198 :
199 : /* Grow the table if it is overloaded */
200 3863 : n = NBUCKETS(ht);
201 3863 : if (ht->nentries >= OVERLOADED(n)) {
202 46 : oldbuckets = ht->buckets;
203 46 : nb = 2 * n * sizeof(PLHashEntry *);
204 46 : ht->buckets = (PLHashEntry**)
205 46 : ((*ht->allocOps->allocTable)(ht->allocPriv, nb));
206 46 : if (!ht->buckets) {
207 0 : ht->buckets = oldbuckets;
208 0 : return 0;
209 : }
210 46 : memset(ht->buckets, 0, nb);
211 : #ifdef HASHMETER
212 : ht->ngrows++;
213 : #endif
214 46 : ht->shift--;
215 :
216 3518 : for (i = 0; i < n; i++) {
217 6510 : for (he = oldbuckets[i]; he; he = next) {
218 3038 : next = he->next;
219 3038 : hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
220 3038 : PR_ASSERT(*hep == 0);
221 3038 : he->next = 0;
222 3038 : *hep = he;
223 : }
224 : }
225 : #ifdef DEBUG
226 46 : memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
227 : #endif
228 46 : (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
229 46 : hep = PL_HashTableRawLookup(ht, keyHash, key);
230 : }
231 :
232 : /* Make a new key value entry */
233 3863 : he = (*ht->allocOps->allocEntry)(ht->allocPriv, key);
234 3863 : if (!he)
235 0 : return 0;
236 3863 : he->keyHash = keyHash;
237 3863 : he->key = key;
238 3863 : he->value = value;
239 3863 : he->next = *hep;
240 3863 : *hep = he;
241 3863 : ht->nentries++;
242 3863 : return he;
243 : }
244 :
245 : PR_IMPLEMENT(PLHashEntry *)
246 3963 : PL_HashTableAdd(PLHashTable *ht, const void *key, void *value)
247 : {
248 : PLHashNumber keyHash;
249 : PLHashEntry *he, **hep;
250 :
251 3963 : keyHash = (*ht->keyHash)(key);
252 3963 : hep = PL_HashTableRawLookup(ht, keyHash, key);
253 3963 : if ((he = *hep) != 0) {
254 : /* Hit; see if values match */
255 100 : if ((*ht->valueCompare)(he->value, value)) {
256 : /* key,value pair is already present in table */
257 0 : return he;
258 : }
259 100 : if (he->value)
260 100 : (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE);
261 100 : he->value = value;
262 100 : return he;
263 : }
264 3863 : return PL_HashTableRawAdd(ht, hep, keyHash, key, value);
265 : }
266 :
267 : PR_IMPLEMENT(void)
268 1199 : PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he)
269 : {
270 : PRUint32 i, n;
271 : PLHashEntry *next, **oldbuckets;
272 : PRSize nb;
273 :
274 1199 : *hep = he->next;
275 1199 : (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY);
276 :
277 : /* Shrink table if it's underloaded */
278 1199 : n = NBUCKETS(ht);
279 1199 : if (--ht->nentries < UNDERLOADED(n)) {
280 7 : oldbuckets = ht->buckets;
281 7 : nb = n * sizeof(PLHashEntry*) / 2;
282 7 : ht->buckets = (PLHashEntry**)(
283 7 : (*ht->allocOps->allocTable)(ht->allocPriv, nb));
284 7 : if (!ht->buckets) {
285 0 : ht->buckets = oldbuckets;
286 0 : return;
287 : }
288 7 : memset(ht->buckets, 0, nb);
289 : #ifdef HASHMETER
290 : ht->nshrinks++;
291 : #endif
292 7 : ht->shift++;
293 :
294 743 : for (i = 0; i < n; i++) {
295 892 : for (he = oldbuckets[i]; he; he = next) {
296 156 : next = he->next;
297 156 : hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
298 156 : PR_ASSERT(*hep == 0);
299 156 : he->next = 0;
300 156 : *hep = he;
301 : }
302 : }
303 : #ifdef DEBUG
304 7 : memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
305 : #endif
306 7 : (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
307 : }
308 : }
309 :
310 : PR_IMPLEMENT(PRBool)
311 1199 : PL_HashTableRemove(PLHashTable *ht, const void *key)
312 : {
313 : PLHashNumber keyHash;
314 : PLHashEntry *he, **hep;
315 :
316 1199 : keyHash = (*ht->keyHash)(key);
317 1199 : hep = PL_HashTableRawLookup(ht, keyHash, key);
318 1199 : if ((he = *hep) == 0)
319 0 : return PR_FALSE;
320 :
321 : /* Hit; remove element */
322 1199 : PL_HashTableRawRemove(ht, hep, he);
323 1199 : return PR_TRUE;
324 : }
325 :
326 : PR_IMPLEMENT(void *)
327 6247 : PL_HashTableLookup(PLHashTable *ht, const void *key)
328 : {
329 : PLHashNumber keyHash;
330 : PLHashEntry *he, **hep;
331 :
332 6247 : keyHash = (*ht->keyHash)(key);
333 6247 : hep = PL_HashTableRawLookup(ht, keyHash, key);
334 6247 : if ((he = *hep) != 0) {
335 3844 : return he->value;
336 : }
337 2403 : return 0;
338 : }
339 :
340 : /*
341 : ** Same as PL_HashTableLookup but doesn't reorder the hash entries.
342 : */
343 : PR_IMPLEMENT(void *)
344 6312 : PL_HashTableLookupConst(PLHashTable *ht, const void *key)
345 : {
346 : PLHashNumber keyHash;
347 : PLHashEntry *he, **hep;
348 :
349 6312 : keyHash = (*ht->keyHash)(key);
350 6312 : hep = PL_HashTableRawLookupConst(ht, keyHash, key);
351 6312 : if ((he = *hep) != 0) {
352 6179 : return he->value;
353 : }
354 133 : return 0;
355 : }
356 :
357 : /*
358 : ** Iterate over the entries in the hash table calling func for each
359 : ** entry found. Stop if "f" says to (return value & PR_ENUMERATE_STOP).
360 : ** Return a count of the number of elements scanned.
361 : */
362 : PR_IMPLEMENT(int)
363 96 : PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg)
364 : {
365 : PLHashEntry *he, **hep;
366 : PRUint32 i, nbuckets;
367 96 : int rv, n = 0;
368 96 : PLHashEntry *todo = 0;
369 :
370 96 : nbuckets = NBUCKETS(ht);
371 1632 : for (i = 0; i < nbuckets; i++) {
372 1536 : hep = &ht->buckets[i];
373 3072 : while ((he = *hep) != 0) {
374 0 : rv = (*f)(he, n, arg);
375 0 : n++;
376 0 : if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
377 0 : *hep = he->next;
378 0 : if (rv & HT_ENUMERATE_REMOVE) {
379 0 : he->next = todo;
380 0 : todo = he;
381 : }
382 : } else {
383 0 : hep = &he->next;
384 : }
385 0 : if (rv & HT_ENUMERATE_STOP) {
386 0 : goto out;
387 : }
388 : }
389 : }
390 :
391 : out:
392 96 : hep = &todo;
393 192 : while ((he = *hep) != 0) {
394 0 : PL_HashTableRawRemove(ht, hep, he);
395 : }
396 96 : return n;
397 : }
398 :
399 : #ifdef HASHMETER
400 : #include <math.h>
401 : #include <stdio.h>
402 :
403 : PR_IMPLEMENT(void)
404 : PL_HashTableDumpMeter(PLHashTable *ht, PLHashEnumerator dump, FILE *fp)
405 : {
406 : double mean, variance;
407 : PRUint32 nchains, nbuckets;
408 : PRUint32 i, n, maxChain, maxChainLen;
409 : PLHashEntry *he;
410 :
411 : variance = 0;
412 : nchains = 0;
413 : maxChainLen = 0;
414 : nbuckets = NBUCKETS(ht);
415 : for (i = 0; i < nbuckets; i++) {
416 : he = ht->buckets[i];
417 : if (!he)
418 : continue;
419 : nchains++;
420 : for (n = 0; he; he = he->next)
421 : n++;
422 : variance += n * n;
423 : if (n > maxChainLen) {
424 : maxChainLen = n;
425 : maxChain = i;
426 : }
427 : }
428 : mean = (double)ht->nentries / nchains;
429 : variance = fabs(variance / nchains - mean * mean);
430 :
431 : fprintf(fp, "\nHash table statistics:\n");
432 : fprintf(fp, " number of lookups: %u\n", ht->nlookups);
433 : fprintf(fp, " number of entries: %u\n", ht->nentries);
434 : fprintf(fp, " number of grows: %u\n", ht->ngrows);
435 : fprintf(fp, " number of shrinks: %u\n", ht->nshrinks);
436 : fprintf(fp, " mean steps per hash: %g\n", (double)ht->nsteps
437 : / ht->nlookups);
438 : fprintf(fp, "mean hash chain length: %g\n", mean);
439 : fprintf(fp, " standard deviation: %g\n", sqrt(variance));
440 : fprintf(fp, " max hash chain length: %u\n", maxChainLen);
441 : fprintf(fp, " max hash chain: [%u]\n", maxChain);
442 :
443 : for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
444 : if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT)
445 : break;
446 : }
447 : #endif /* HASHMETER */
448 :
449 : PR_IMPLEMENT(int)
450 0 : PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp)
451 : {
452 : int count;
453 :
454 0 : count = PL_HashTableEnumerateEntries(ht, dump, fp);
455 : #ifdef HASHMETER
456 : PL_HashTableDumpMeter(ht, dump, fp);
457 : #endif
458 0 : return count;
459 : }
460 :
461 : PR_IMPLEMENT(PLHashNumber)
462 255 : PL_HashString(const void *key)
463 : {
464 : PLHashNumber h;
465 : const PRUint8 *s;
466 :
467 255 : h = 0;
468 7461 : for (s = (const PRUint8*)key; *s; s++)
469 7206 : h = PR_ROTATE_LEFT32(h, 4) ^ *s;
470 255 : return h;
471 : }
472 :
473 : PR_IMPLEMENT(int)
474 83 : PL_CompareStrings(const void *v1, const void *v2)
475 : {
476 83 : return strcmp((const char*)v1, (const char*)v2) == 0;
477 : }
478 :
479 : PR_IMPLEMENT(int)
480 8154 : PL_CompareValues(const void *v1, const void *v2)
481 : {
482 8154 : return v1 == v2;
483 : }
|
