1
2 /*
3 * bltHash.c --
4 *
5 *
6 * This module implements an in-memory hash table for the BLT
7 * toolkit. Built upon the Tcl hash table, it adds pool
8 * allocation 64-bit address handling, improved array hash
9 * function.
10 *
11 * Copyright 2001 Silicon Metrics Corporation.
12 *
13 * Permission to use, copy, modify, and distribute this software and
14 * its documentation for any purpose and without fee is hereby
15 * granted, provided that the above copyright notice appear in all
16 * copies and that both that the copyright notice and warranty
17 * disclaimer appear in supporting documentation, and that the names
18 * of Lucent Technologies any of their entities not be used in
19 * advertising or publicity pertaining to distribution of the software
20 * without specific, written prior permission.
21 *
22 * Silicon Metrics disclaims all warranties with regard to this
23 * software, including all implied warranties of merchantability and
24 * fitness. In no event shall Lucent Technologies be liable for any
25 * special, indirect or consequential damages or any damages
26 * whatsoever resulting from loss of use, data or profits, whether in
27 * an action of contract, negligence or other tortuous action, arising
28 * out of or in connection with the use or performance of this
29 * software.
30 *
31 * Bob Jenkins, 1996. hash.c. Public Domain.
32 * Bob Jenkins, 1997. lookup8.c. Public Domain.
33 *
34 * Copyright (c) 1991-1993 The Regents of the University of California.
35 * Copyright (c) 1994 Sun Microsystems, Inc.
36 *
37 * See the file "license.terms" for information on usage and redistribution
38 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
39 *
40 * RCS: @(#) $Id: bltHash.c,v 1.1.1.1 2009/05/09 16:27:09 pcmacdon Exp $
41 */
42
43 #include <bltInt.h>
44
45 #include <stdio.h>
46 #include <string.h>
47 /* The following header is required for LP64 compilation */
48 #include <stdlib.h>
49
50 #include "bltHash.h"
51
52 /*
53 * When there are this many entries per bucket, on average, rebuild
54 * the hash table to make it larger.
55 */
56
57 #define REBUILD_MULTIPLIER 3
58
59 #if (SIZEOF_VOID_P == 8)
60 #define RANDOM_INDEX HashOneWord
61 #define DOWNSHIFT_START 62
62 #else
63
64 /*
65 * The following macro takes a preliminary integer hash value and
66 * produces an index into a hash tables bucket list. The idea is
67 * to make it so that preliminary values that are arbitrarily similar
68 * will end up in different buckets. The hash function was taken
69 * from a random-number generator.
70 */
71 #define RANDOM_INDEX(tablePtr, i) \
72 (((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)
73 #define DOWNSHIFT_START 28
74 #endif
75
76 /*
77 * Procedure prototypes for static procedures in this file:
78 */
79 static Blt_Hash HashArray _ANSI_ARGS_((CONST void *key, size_t length));
80 static Blt_HashEntry *ArrayFind _ANSI_ARGS_((Blt_HashTable *tablePtr,
81 CONST void *key));
82 static Blt_HashEntry *ArrayCreate _ANSI_ARGS_((Blt_HashTable *tablePtr,
83 CONST void *key, int *newPtr));
84 static Blt_HashEntry *BogusFind _ANSI_ARGS_((Blt_HashTable *tablePtr,
85 CONST void *key));
86 static Blt_HashEntry *BogusCreate _ANSI_ARGS_((Blt_HashTable *tablePtr,
87 CONST void *key, int *newPtr));
88 static Blt_Hash HashString _ANSI_ARGS_((CONST char *string));
89 static void RebuildTable _ANSI_ARGS_((Blt_HashTable *tablePtr));
90 static Blt_HashEntry *StringFind _ANSI_ARGS_((Blt_HashTable *tablePtr,
91 CONST void *key));
92 static Blt_HashEntry *StringCreate _ANSI_ARGS_((Blt_HashTable *tablePtr,
93 CONST void *key, int *newPtr));
94 static Blt_HashEntry *OneWordFind _ANSI_ARGS_((Blt_HashTable *tablePtr,
95 CONST void *key));
96 static Blt_HashEntry *OneWordCreate _ANSI_ARGS_((Blt_HashTable *tablePtr,
97 CONST void *key, int *newPtr));
98
99 #if (SIZEOF_VOID_P == 8)
100 static Blt_Hash HashOneWord _ANSI_ARGS_((Blt_HashTable *tablePtr,
101 CONST void *key));
102
103 #endif /* SIZEOF_VOID_P == 8 */
104
105 /*
106 *----------------------------------------------------------------------
107 *
108 * HashString --
109 *
110 * Compute a one-word summary of a text string, which can be
111 * used to generate a hash index.
112 *
113 * Results:
114 * The return value is a one-word summary of the information in
115 * string.
116 *
117 * Side effects:
118 * None.
119 *
120 *----------------------------------------------------------------------
121 */
122 static Blt_Hash
HashString(register CONST char * string)123 HashString(register CONST char *string) /* String from which to
124 * compute hash value. */
125 {
126 register Blt_Hash result;
127 register Blt_Hash c;
128
129 /*
130 * I tried a zillion different hash functions and asked many other
131 * people for advice. Many people had their own favorite functions,
132 * all different, but no-one had much idea why they were good ones.
133 * I chose the one below (multiply by 9 and add new character)
134 * because of the following reasons:
135 *
136 * 1. Multiplying by 10 is perfect for keys that are decimal strings,
137 * and multiplying by 9 is just about as good.
138 * 2. Times-9 is (shift-left-3) plus (old). This means that each
139 * character's bits hang around in the low-order bits of the
140 * hash value for ever, plus they spread fairly rapidly up to
141 * the high-order bits to fill out the hash value. This seems
142 * to work well both for decimal and non-decimal strings.
143 */
144
145 result = 0;
146 while ((c = *string++) != 0) {
147 result += (result << 3) + c;
148 }
149 return (Blt_Hash)result;
150 }
151
152 /*
153 *----------------------------------------------------------------------
154 *
155 * StringFind --
156 *
157 * Given a hash table with string keys, and a string key, find
158 * the entry with a matching key.
159 *
160 * Results:
161 * The return value is a token for the matching entry in the
162 * hash table, or NULL if there was no matching entry.
163 *
164 * Side effects:
165 * None.
166 *
167 *----------------------------------------------------------------------
168 */
169 static Blt_HashEntry *
StringFind(Blt_HashTable * tablePtr,CONST void * key)170 StringFind(
171 Blt_HashTable *tablePtr, /* Table in which to lookup entry. */
172 CONST void *key) /* Key to use to find matching entry. */
173 {
174 Blt_Hash hval;
175 register Blt_HashEntry *hPtr;
176 size_t hindex;
177
178 hval = HashString((char *)key);
179 hindex = hval & tablePtr->mask;
180
181 /*
182 * Search all of the entries in the appropriate bucket.
183 */
184
185 for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
186 hPtr = hPtr->nextPtr) {
187 if (hPtr->hval == hval) {
188 register CONST char *p1, *p2;
189
190 for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {
191 if (*p1 != *p2) {
192 break;
193 }
194 if (*p1 == '\0') {
195 return hPtr;
196 }
197 }
198 }
199 }
200 return NULL;
201 }
202
203 /*
204 *----------------------------------------------------------------------
205 *
206 * StringCreate --
207 *
208 * Given a hash table with string keys, and a string key, find
209 * the entry with a matching key. If there is no matching entry,
210 * then create a new entry that does match.
211 *
212 * Results:
213 * The return value is a pointer to the matching entry. If this
214 * is a newly-created entry, then *newPtr will be set to a non-zero
215 * value; otherwise *newPtr will be set to 0. If this is a new
216 * entry the value stored in the entry will initially be 0.
217 *
218 * Side effects:
219 * A new entry may be added to the hash table.
220 *
221 *----------------------------------------------------------------------
222 */
223 static Blt_HashEntry *
StringCreate(Blt_HashTable * tablePtr,CONST void * key,int * newPtr)224 StringCreate(
225 Blt_HashTable *tablePtr, /* Table in which to lookup entry. */
226 CONST void *key, /* Key to use to find or create matching
227 * entry. */
228 int *newPtr) /* Store info here telling whether a new
229 * entry was created. */
230 {
231 Blt_Hash hval;
232 Blt_HashEntry **bucketPtr;
233 register Blt_HashEntry *hPtr;
234 size_t size, hindex;
235
236 hval = HashString(key);
237 hindex = hval & tablePtr->mask;
238
239 /*
240 * Search all of the entries in this bucket.
241 */
242
243 for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
244 hPtr = hPtr->nextPtr) {
245 if (hPtr->hval == hval) {
246 register CONST char *p1, *p2;
247
248 for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {
249 if (*p1 != *p2) {
250 break;
251 }
252 if (*p1 == '\0') {
253 *newPtr = FALSE;
254 return hPtr;
255 }
256 }
257 }
258 }
259
260 /*
261 * Entry not found. Add a new one to the bucket.
262 */
263
264 *newPtr = TRUE;
265 size = sizeof(Blt_HashEntry) + strlen(key) - sizeof(Blt_HashKey) + 1;
266 if (tablePtr->hPool != NULL) {
267 hPtr = Blt_PoolAllocItem(tablePtr->hPool, size);
268 } else {
269 hPtr = Blt_Malloc(size);
270 }
271 bucketPtr = tablePtr->buckets + hindex;
272 hPtr->nextPtr = *bucketPtr;
273 hPtr->hval = hval;
274 hPtr->clientData = 0;
275 strcpy(hPtr->key.string, key);
276 *bucketPtr = hPtr;
277 tablePtr->numEntries++;
278
279 /*
280 * If the table has exceeded a decent size, rebuild it with many
281 * more buckets.
282 */
283
284 if (tablePtr->numEntries >= tablePtr->rebuildSize) {
285 RebuildTable(tablePtr);
286 }
287 return hPtr;
288 }
289
290 #if (SIZEOF_VOID_P == 8)
291 /*
292 *----------------------------------------------------------------------
293 *
294 * HashOneWord --
295 *
296 * Compute a one-word hash value of a 64-bit word, which then can
297 * be used to generate a hash index.
298 *
299 * From Knuth, it's a multiplicative hash. Multiplies an unsigned
300 * 64-bit value with the golden ratio (sqrt(5) - 1) / 2. The
301 * downshift value is 64 - n, when n is the log2 of the size of
302 * the hash table.
303 *
304 * Results:
305 * The return value is a one-word summary of the information in
306 * 64 bit word.
307 *
308 * Side effects:
309 * None.
310 *
311 *----------------------------------------------------------------------
312 */
313 static Blt_Hash
HashOneWord(Blt_HashTable * tablePtr,CONST void * key)314 HashOneWord(
315 Blt_HashTable *tablePtr,
316 CONST void *key)
317 {
318 uint64_t a0, a1;
319 uint64_t y0, y1;
320 uint64_t y2, y3;
321 uint64_t p1, p2;
322 uint64_t result;
323 /* Compute key * GOLDEN_RATIO in 128-bit arithmetic */
324 a0 = (uint64_t)key & 0x00000000FFFFFFFF;
325 a1 = (uint64_t)key >> 32;
326
327 y0 = a0 * 0x000000007f4a7c13;
328 y1 = a0 * 0x000000009e3779b9;
329 y2 = a1 * 0x000000007f4a7c13;
330 y3 = a1 * 0x000000009e3779b9;
331 y1 += y0 >> 32; /* Can't carry */
332 y1 += y2; /* Might carry */
333 if (y1 < y2) {
334 y3 += (1LL << 32); /* Propagate */
335 }
336
337 /* 128-bit product: p1 = loword, p2 = hiword */
338 p1 = ((y1 & 0x00000000FFFFFFFF) << 32) + (y0 & 0x00000000FFFFFFFF);
339 p2 = y3 + (y1 >> 32);
340
341 /* Left shift the value downward by the size of the table */
342 if (tablePtr->downShift > 0) {
343 if (tablePtr->downShift < 64) {
344 result = ((p2 << (64 - tablePtr->downShift)) |
345 (p1 >> (tablePtr->downShift & 63)));
346 } else {
347 result = p2 >> (tablePtr->downShift & 63);
348 }
349 } else {
350 result = p1;
351 }
352 /* Finally mask off the high bits */
353 return (Blt_Hash)(result & tablePtr->mask);
354 }
355
356 #endif /* SIZEOF_VOID_P == 8 */
357
358 /*
359 *----------------------------------------------------------------------
360 *
361 * OneWordFind --
362 *
363 * Given a hash table with one-word keys, and a one-word key,
364 * find the entry with a matching key.
365 *
366 * Results:
367 * The return value is a token for the matching entry in the
368 * hash table, or NULL if there was no matching entry.
369 *
370 * Side effects:
371 * None.
372 *
373 *----------------------------------------------------------------------
374 */
375 static Blt_HashEntry *
OneWordFind(Blt_HashTable * tablePtr,register CONST void * key)376 OneWordFind(
377 Blt_HashTable *tablePtr, /* Table in which to lookup entry. */
378 register CONST void *key) /* Key to use to find matching entry. */
379 {
380 register Blt_HashEntry *hPtr;
381 size_t hindex;
382
383 hindex = RANDOM_INDEX(tablePtr, key);
384
385 /*
386 * Search all of the entries in the appropriate bucket.
387 */
388 for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
389 hPtr = hPtr->nextPtr) {
390 if (hPtr->key.oneWordValue == key) {
391 return hPtr;
392 }
393 }
394 return NULL;
395 }
396
397 /*
398 *----------------------------------------------------------------------
399 *
400 * OneWordCreate --
401 *
402 * Given a hash table with one-word keys, and a one-word key, find
403 * the entry with a matching key. If there is no matching entry,
404 * then create a new entry that does match.
405 *
406 * Results:
407 * The return value is a pointer to the matching entry. If this
408 * is a newly-created entry, then *newPtr will be set to a non-zero
409 * value; otherwise *newPtr will be set to 0. If this is a new
410 * entry the value stored in the entry will initially be 0.
411 *
412 * Side effects:
413 * A new entry may be added to the hash table.
414 *
415 *----------------------------------------------------------------------
416 */
417 static Blt_HashEntry *
OneWordCreate(Blt_HashTable * tablePtr,CONST void * key,int * newPtr)418 OneWordCreate(
419 Blt_HashTable *tablePtr, /* Table in which to lookup entry. */
420 CONST void *key, /* Key to use to find or create matching
421 * entry. */
422 int *newPtr) /* Store info here telling whether a new
423 * entry was created. */
424 {
425 Blt_HashEntry **bucketPtr;
426 register Blt_HashEntry *hPtr;
427 size_t hindex;
428
429 hindex = RANDOM_INDEX(tablePtr, key);
430
431 /*
432 * Search all of the entries in this bucket.
433 */
434 for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
435 hPtr = hPtr->nextPtr) {
436 if (hPtr->key.oneWordValue == key) {
437 *newPtr = FALSE;
438 return hPtr;
439 }
440 }
441
442 /*
443 * Entry not found. Add a new one to the bucket.
444 */
445
446 *newPtr = TRUE;
447 if (tablePtr->hPool != NULL) {
448 hPtr = Blt_PoolAllocItem(tablePtr->hPool, sizeof(Blt_HashEntry));
449 } else {
450 hPtr = Blt_Malloc(sizeof(Blt_HashEntry));
451 }
452 bucketPtr = tablePtr->buckets + hindex;
453 hPtr->nextPtr = *bucketPtr;
454 hPtr->hval = (Blt_Hash)key;
455 hPtr->clientData = 0;
456 hPtr->key.oneWordValue = (void *)key; /* CONST XXXX */
457 *bucketPtr = hPtr;
458 tablePtr->numEntries++;
459
460 /*
461 * If the table has exceeded a decent size, rebuild it with many
462 * more buckets.
463 */
464
465 if (tablePtr->numEntries >= tablePtr->rebuildSize) {
466 RebuildTable(tablePtr);
467 }
468 return hPtr;
469 }
470
471
472 #if (SIZEOF_VOID_P == 4)
473 /*
474 * --------------------------------------------------------------------
475 *
476 * MIX32 --
477 *
478 * Bob Jenkins, 1996. Public Domain.
479 *
480 * Mix 3 32/64-bit values reversibly. For every delta with one or
481 * two bit set, and the deltas of all three high bits or all
482 * three low bits, whether the original value of a,b,c is almost
483 * all zero or is uniformly distributed, If mix() is run
484 * forward or backward, at least 32 bits in a,b,c have at least
485 * 1/4 probability of changing. * If mix() is run forward, every
486 * bit of c will change between 1/3 and 2/3 of the time. (Well,
487 * 22/100 and 78/100 for some 2-bit deltas.) mix() was built out
488 * of 36 single-cycle latency instructions in a structure that
489 * could supported 2x parallelism, like so:
490 *
491 * a -= b;
492 * a -= c; x = (c>>13);
493 * b -= c; a ^= x;
494 * b -= a; x = (a<<8);
495 * c -= a; b ^= x;
496 * c -= b; x = (b>>13);
497 * ...
498 *
499 * Unfortunately, superscalar Pentiums and Sparcs can't take
500 * advantage of that parallelism. They've also turned some of
501 * those single-cycle latency instructions into multi-cycle
502 * latency instructions. Still, this is the fastest good hash I
503 * could find. There were about 2^^68 to choose from. I only
504 * looked at a billion or so.
505 *
506 * --------------------------------------------------------------------
507 */
508 #define MIX32(a,b,c) \
509 a -= b, a -= c, a ^= (c >> 13), \
510 b -= c, b -= a, b ^= (a << 8), \
511 c -= a, c -= b, c ^= (b >> 13), \
512 a -= b, a -= c, a ^= (c >> 12), \
513 b -= c, b -= a, b ^= (a << 16), \
514 c -= a, c -= b, c ^= (b >> 5), \
515 a -= b, a -= c, a ^= (c >> 3), \
516 b -= c, b -= a, b ^= (a << 10), \
517 c -= a, c -= b, c ^= (b >> 15)
518
519 #define GOLDEN_RATIO32 0x9e3779b9 /* An arbitrary value */
520
521 /*
522 * --------------------------------------------------------------------
523 *
524 * HashArray --
525 *
526 * Bob Jenkins, 1996. Public Domain.
527 *
528 * This works on all machines. Length has to be measured in
529 * unsigned longs instead of bytes. It requires that
530 *
531 * o The key be an array of unsigned ints.
532 * o All your machines have the same endianness
533 * o The length be the number of unsigned ints in the key.
534 *
535 * --------------------------------------------------------------------
536 */
537 static Blt_Hash
HashArray(CONST void * key,size_t length)538 HashArray(
539 CONST void *key,
540 size_t length) /* Length of the key in 32-bit words */
541 {
542 register uint32_t a, b, c, len;
543 register uint32_t *arrayPtr = (uint32_t *)key;
544 /* Set up the internal state */
545 len = length;
546 a = b = GOLDEN_RATIO32; /* An arbitrary value */
547 c = 0; /* Previous hash value */
548
549 while (len >= 3) { /* Handle most of the key */
550 a += arrayPtr[0];
551 b += arrayPtr[1];
552 c += arrayPtr[2];
553 MIX32(a, b, c);
554 arrayPtr += 3; len -= 3;
555 }
556 c += length;
557 /* And now the last 2 words */
558 /* Note that all the case statements fall through */
559 switch(len) {
560 /* c is reserved for the length */
561 case 2 : b += arrayPtr[1];
562 case 1 : a += arrayPtr[0];
563 /* case 0: nothing left to add */
564 }
565 MIX32(a, b, c);
566 return (Blt_Hash)c;
567 }
568 #endif /* SIZEOF_VOID_P == 4 */
569
570 #if (SIZEOF_VOID_P == 8)
571
572 /*
573 * --------------------------------------------------------------------
574 *
575 * MIX64 --
576 *
577 * Bob Jenkins, January 4 1997, Public Domain. You can use
578 * this free for any purpose. It has no warranty.
579 *
580 * Returns a 64-bit value. Every bit of the key affects every
581 * bit of the return value. No funnels. Every 1-bit and 2-bit
582 * delta achieves avalanche. About 41+5len instructions.
583 *
584 * The best hash table sizes are powers of 2. There is no need
585 * to do mod a prime (mod is sooo slow!). If you need less than
586 * 64 bits, use a bitmask. For example, if you need only 10
587 * bits, do h = (h & hashmask(10)); In which case, the hash table
588 * should have hashsize(10) elements.
589 *
590 * By Bob Jenkins, Jan 4 1997. bob_jenkins@burtleburtle.net.
591 * You may use this code any way you wish, private, educational,
592 * or commercial, as long as this whole comment accompanies it.
593 *
594 * See http://burtleburtle.net/bob/hash/evahash.html
595 * Use for hash table lookup, or anything where one collision in
596 * 2^^64 * is acceptable. Do NOT use for cryptographic purposes.
597 *
598 * --------------------------------------------------------------------
599 */
600
601 #define MIX64(a,b,c) \
602 a -= b, a -= c, a ^= (c >> 43), \
603 b -= c, b -= a, b ^= (a << 9), \
604 c -= a, c -= b, c ^= (b >> 8), \
605 a -= b, a -= c, a ^= (c >> 38), \
606 b -= c, b -= a, b ^= (a << 23), \
607 c -= a, c -= b, c ^= (b >> 5), \
608 a -= b, a -= c, a ^= (c >> 35), \
609 b -= c, b -= a, b ^= (a << 49), \
610 c -= a, c -= b, c ^= (b >> 11), \
611 a -= b, a -= c, a ^= (c >> 12), \
612 b -= c, b -= a, b ^= (a << 18), \
613 c -= a, c -= b, c ^= (b >> 22)
614
615 #define GOLDEN_RATIO64 0x9e3779b97f4a7c13LL
616
617 /*
618 * --------------------------------------------------------------------
619 *
620 * HashArray --
621 *
622 * Bob Jenkins, January 4 1997, Public Domain. You can use
623 * this free for any purpose. It has no warranty.
624 *
625 * This works on all machines. The length has to be measured in
626 * 64 bit words, instead of bytes. It requires that
627 *
628 * o The key be an array of 64 bit words (unsigned longs).
629 * o All your machines have the same endianness.
630 * o The length be the number of 64 bit words in the key.
631 *
632 * --------------------------------------------------------------------
633 */
634 static Blt_Hash
HashArray(CONST void * key,size_t length)635 HashArray(
636 CONST void *key,
637 size_t length) /* Length of key in 32-bit words. */
638 {
639 register uint64_t a, b, c, len;
640 register uint32_t *iPtr = (uint32_t *)key;
641
642 #ifdef WORDS_BIGENDIAN
643 #define PACK(a,b) ((uint64_t)(b) | ((uint64_t)(a) << 32))
644 #else
645 #define PACK(a,b) ((uint64_t)(a) | ((uint64_t)(b) << 32))
646 #endif
647 /* Set up the internal state */
648 len = length; /* Length is the number of 64-bit words. */
649 a = b = GOLDEN_RATIO64; /* An arbitrary value */
650 c = 0; /* Previous hash value */
651
652 while (len >= 6) { /* Handle most of the key */
653 a += PACK(iPtr[0], iPtr[1]);
654 b += PACK(iPtr[2], iPtr[3]);
655 c += PACK(iPtr[4], iPtr[5]);
656 MIX64(a,b,c);
657 iPtr += 6; len -= 6;
658 }
659 c += length;
660 /* And now the last 2 words */
661 /* Note that all the case statements fall through */
662 switch(len) {
663 /* c is reserved for the length */
664 case 5 :
665 case 4 :
666 a += PACK(iPtr[0], iPtr[1]);
667 b += PACK(iPtr[2], iPtr[3]);
668 iPtr += 4; len -= 4;
669 break;
670 case 3 :
671 case 2 :
672 a += PACK(iPtr[0], iPtr[1]);
673 iPtr += 2; len -= 2;
674 /* case 0: nothing left to add */
675 }
676 if (len > 0) {
677 b += iPtr[0];
678 }
679 MIX64(a,b,c);
680 return (Blt_Hash)c;
681 }
682 #endif /* SIZEOF_VOID_P == 8 */
683
684 /*
685 *----------------------------------------------------------------------
686 *
687 * ArrayFind --
688 *
689 * Given a hash table with array-of-int keys, and a key, find
690 * the entry with a matching key.
691 *
692 * Results:
693 * The return value is a token for the matching entry in the
694 * hash table, or NULL if there was no matching entry.
695 *
696 * Side effects:
697 * None.
698 *
699 *----------------------------------------------------------------------
700 */
701 static Blt_HashEntry *
ArrayFind(Blt_HashTable * tablePtr,CONST void * key)702 ArrayFind(
703 Blt_HashTable *tablePtr, /* Table in which to lookup entry. */
704 CONST void *key) /* Key to use to find matching entry. */
705 {
706 Blt_Hash hval;
707 register Blt_HashEntry *hPtr;
708 size_t hindex;
709
710 hval = HashArray(key, tablePtr->keyType);
711 hindex = hval & tablePtr->mask;
712 /*
713 * Search all of the entries in the appropriate bucket.
714 */
715
716 for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
717 hPtr = hPtr->nextPtr) {
718 if (hPtr->hval == hval) {
719 register unsigned int *iPtr1, *iPtr2;
720 unsigned int count;
721
722 for (iPtr1 = (uint32_t *)key, iPtr2 = (uint32_t *)hPtr->key.words,
723 count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
724 if (count == 0) {
725 return hPtr;
726 }
727 if (*iPtr1 != *iPtr2) {
728 break;
729 }
730 }
731 }
732 }
733 return NULL;
734 }
735
736 /*
737 *----------------------------------------------------------------------
738 *
739 * ArrayCreate --
740 *
741 * Given a hash table with one-word keys, and a one-word key, find
742 * the entry with a matching key. If there is no matching entry,
743 * then create a new entry that does match.
744 *
745 * Results:
746 * The return value is a pointer to the matching entry. If this
747 * is a newly-created entry, then *newPtr will be set to a non-zero
748 * value; otherwise *newPtr will be set to 0. If this is a new
749 * entry the value stored in the entry will initially be 0.
750 *
751 * Side effects:
752 * A new entry may be added to the hash table.
753 *
754 *----------------------------------------------------------------------
755 */
756 static Blt_HashEntry *
ArrayCreate(Blt_HashTable * tablePtr,register CONST void * key,int * newPtr)757 ArrayCreate(
758 Blt_HashTable *tablePtr, /* Table in which to lookup entry. */
759 register CONST void *key, /* Key to use to find or create matching
760 * entry. */
761 int *newPtr) /* Store info here telling whether a new
762 * entry was created. */
763 {
764 Blt_Hash hval;
765 Blt_HashEntry **bucketPtr;
766 int count;
767 register Blt_HashEntry *hPtr;
768 register uint32_t *iPtr1, *iPtr2;
769 size_t size, hindex;
770
771 hval = HashArray(key, tablePtr->keyType);
772 hindex = hval & tablePtr->mask;
773
774 /*
775 * Search all of the entries in the appropriate bucket.
776 */
777 for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
778 hPtr = hPtr->nextPtr) {
779 if (hPtr->hval == hval) {
780 for (iPtr1 = (uint32_t *)key, iPtr2 = (uint32_t *)hPtr->key.words,
781 count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
782 if (count == 0) {
783 *newPtr = FALSE;
784 return hPtr;
785 }
786 if (*iPtr1 != *iPtr2) {
787 break;
788 }
789 }
790 }
791 }
792
793 /*
794 * Entry not found. Add a new one to the bucket.
795 */
796 *newPtr = TRUE;
797 /* We assume here that the size of the key is at least 2 words */
798 size = sizeof(Blt_HashEntry) + tablePtr->keyType * sizeof(uint32_t) -
799 sizeof(Blt_HashKey);
800 if (tablePtr->hPool != NULL) {
801 hPtr = Blt_PoolAllocItem(tablePtr->hPool, size);
802 } else {
803 hPtr = Blt_Malloc(size);
804 }
805 bucketPtr = tablePtr->buckets + hindex;
806 hPtr->nextPtr = *bucketPtr;
807 hPtr->hval = hval;
808 hPtr->clientData = 0;
809 count = tablePtr->keyType;
810 for (iPtr1 = (uint32_t *)key, iPtr2 = (uint32_t *)hPtr->key.words;
811 count > 0; count--, iPtr1++, iPtr2++) {
812 *iPtr2 = *iPtr1;
813 }
814 *bucketPtr = hPtr;
815 tablePtr->numEntries++;
816
817 /*
818 * If the table has exceeded a decent size, rebuild it with many
819 * more buckets.
820 */
821 if (tablePtr->numEntries >= tablePtr->rebuildSize) {
822 RebuildTable(tablePtr);
823 }
824 return hPtr;
825 }
826
827 /*
828 *----------------------------------------------------------------------
829 *
830 * BogusFind --
831 *
832 * This procedure is invoked when an Blt_FindHashEntry is called
833 * on a table that has been deleted.
834 *
835 * Results:
836 * If panic returns (which it shouldn't) this procedure returns
837 * NULL.
838 *
839 * Side effects:
840 * Generates a panic.
841 *
842 *----------------------------------------------------------------------
843 */
844 /* ARGSUSED */
845 static Blt_HashEntry *
BogusFind(Blt_HashTable * tablePtr,CONST void * key)846 BogusFind(
847 Blt_HashTable *tablePtr, /* Table in which to lookup entry. */
848 CONST void *key) /* Key to use to find matching entry. */
849 {
850 Blt_Panic("called Blt_FindHashEntry on deleted table");
851 return NULL;
852 }
853
854 /*
855 *----------------------------------------------------------------------
856 *
857 * BogusCreate --
858 *
859 * This procedure is invoked when an Blt_CreateHashEntry is called
860 * on a table that has been deleted.
861 *
862 * Results:
863 * If panic returns (which it shouldn't) this procedure returns
864 * NULL.
865 *
866 * Side effects:
867 * Generates a panic.
868 *
869 *----------------------------------------------------------------------
870 */
871 /* ARGSUSED */
872 static Blt_HashEntry *
BogusCreate(Blt_HashTable * tablePtr,CONST void * key,int * newPtr)873 BogusCreate(
874 Blt_HashTable *tablePtr, /* Table in which to lookup entry. */
875 CONST void *key, /* Key to use to find or create matching
876 * entry. */
877 int *newPtr) /* Store info here telling whether a new
878 * entry was created. */
879 {
880 Blt_Panic("called Blt_CreateHashEntry on deleted table");
881 return NULL;
882 }
883
884 /*
885 *----------------------------------------------------------------------
886 *
887 * RebuildTable --
888 *
889 * This procedure is invoked when the ratio of entries to hash
890 * buckets becomes too large. It creates a new table with a
891 * larger bucket array and moves all of the entries into the
892 * new table.
893 *
894 * Results:
895 * None.
896 *
897 * Side effects:
898 * Memory gets reallocated and entries get re-hashed to new
899 * buckets.
900 *
901 *----------------------------------------------------------------------
902 */
903 static void
RebuildTable(Blt_HashTable * tablePtr)904 RebuildTable(Blt_HashTable *tablePtr) /* Table to enlarge. */
905 {
906 Blt_HashEntry **bucketPtr, **oldBuckets;
907 register Blt_HashEntry **oldChainPtr, **endPtr;
908 register Blt_HashEntry *hPtr, *nextPtr;
909 size_t hindex;
910
911 oldBuckets = tablePtr->buckets;
912 endPtr = tablePtr->buckets + tablePtr->numBuckets;
913 /*
914 * Allocate and initialize the new bucket array, and set up
915 * hashing constants for new array size.
916 */
917 tablePtr->numBuckets <<= 2;
918 tablePtr->buckets = Blt_Calloc(tablePtr->numBuckets,
919 sizeof(Blt_HashEntry *));
920 tablePtr->rebuildSize <<= 2;
921 tablePtr->downShift -= 2;
922 tablePtr->mask = tablePtr->numBuckets - 1;
923
924 /*
925 * Move all of the existing entries into the new bucket array,
926 * based on their hash values.
927 */
928 if (tablePtr->keyType == BLT_ONE_WORD_KEYS) {
929 /*
930 * BLT_ONE_WORD_KEYS are handled slightly differently because
931 * they use the current table size (number of buckets) to be
932 * distributed.
933 */
934 for (oldChainPtr = oldBuckets; oldChainPtr < endPtr; oldChainPtr++) {
935 for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = nextPtr) {
936 nextPtr = hPtr->nextPtr;
937 hindex = RANDOM_INDEX(tablePtr, hPtr->key.oneWordValue);
938 bucketPtr = tablePtr->buckets + hindex;
939 hPtr->nextPtr = *bucketPtr;
940 *bucketPtr = hPtr;
941 }
942 }
943 } else {
944 for (oldChainPtr = oldBuckets; oldChainPtr < endPtr; oldChainPtr++) {
945 for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = nextPtr) {
946 nextPtr = hPtr->nextPtr;
947 hindex = hPtr->hval & tablePtr->mask;
948 bucketPtr = tablePtr->buckets + hindex;
949 hPtr->nextPtr = *bucketPtr;
950 *bucketPtr = hPtr;
951 }
952 }
953 }
954
955 /*
956 * Free up the old bucket array, if it was dynamically allocated.
957 */
958 if (oldBuckets != tablePtr->staticBuckets) {
959 Blt_Free(oldBuckets);
960 }
961 }
962
963
964 /* Public hash table routines */
965
966 /*
967 *----------------------------------------------------------------------
968 *
969 * Blt_InitHashTable --
970 *
971 * Given storage for a hash table, set up the fields to prepare
972 * the hash table for use.
973 *
974 * Results:
975 * None.
976 *
977 * Side effects:
978 * TablePtr is now ready to be passed to Blt_FindHashEntry and
979 * Blt_CreateHashEntry.
980 *
981 *----------------------------------------------------------------------
982 */
983 void
Blt_InitHashTable(register Blt_HashTable * tablePtr,size_t keyType)984 Blt_InitHashTable(
985 register Blt_HashTable *tablePtr, /* Pointer to table record, which
986 * is supplied by the caller. */
987 size_t keyType) /* Type of keys to use in table. */
988 {
989 #if (BLT_SMALL_HASH_TABLE != 4)
990 Blt_Panic("Blt_InitHashTable: BLT_SMALL_HASH_TABLE is %d, not 4\n",
991 BLT_SMALL_HASH_TABLE);
992 #endif
993 tablePtr->buckets = tablePtr->staticBuckets;
994 tablePtr->numBuckets = BLT_SMALL_HASH_TABLE;
995 tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0;
996 tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0;
997 tablePtr->numEntries = 0;
998 tablePtr->rebuildSize = BLT_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
999 tablePtr->downShift = DOWNSHIFT_START;
1000
1001 /* The number of buckets is always a power of 2, so we can
1002 * generate the mask by simply subtracting 1 from the number of
1003 * buckets. */
1004 tablePtr->mask = (Blt_Hash)(tablePtr->numBuckets - 1);
1005 tablePtr->keyType = keyType;
1006
1007 switch (keyType) {
1008 case BLT_STRING_KEYS: /* NUL terminated string keys. */
1009 tablePtr->findProc = StringFind;
1010 tablePtr->createProc = StringCreate;
1011 break;
1012
1013 case BLT_ONE_WORD_KEYS: /* 32 or 64 bit atomic keys. */
1014 tablePtr->findProc = OneWordFind;
1015 tablePtr->createProc = OneWordCreate;
1016 break;
1017
1018 default: /* Structures/arrays. */
1019 if (keyType == 0) {
1020 Blt_Panic("Blt_InitHashTable: Key size can't be %d, must be > 0\n",
1021 keyType);
1022 }
1023 tablePtr->findProc = ArrayFind;
1024 tablePtr->createProc = ArrayCreate;
1025 break;
1026 }
1027 tablePtr->hPool = NULL;
1028 }
1029
1030 /*
1031 *----------------------------------------------------------------------
1032 *
1033 * Blt_InitHashTableWithPool --
1034 *
1035 * Given storage for a hash table, set up the fields to prepare
1036 * the hash table for use. The only difference between this
1037 * routine and Blt_InitHashTable is that is uses a pool allocator
1038 * to allocate memory for hash table entries. The type of pool
1039 * is either fixed or variable size (string) keys.
1040 *
1041 * Results:
1042 * None.
1043 *
1044 * Side effects:
1045 * TablePtr is now ready to be passed to Blt_FindHashEntry and
1046 * Blt_CreateHashEntry.
1047 *
1048 *----------------------------------------------------------------------
1049 */
1050 void
Blt_InitHashTableWithPool(register Blt_HashTable * tablePtr,size_t keyType)1051 Blt_InitHashTableWithPool(
1052 register Blt_HashTable *tablePtr, /* Pointer to table record, which
1053 * is supplied by the caller. */
1054 size_t keyType) /* Type of keys to use in table. */
1055 {
1056 Blt_InitHashTable(tablePtr, keyType);
1057 if (keyType == BLT_STRING_KEYS) {
1058 tablePtr->hPool = Blt_PoolCreate(BLT_VARIABLE_SIZE_ITEMS);
1059 } else {
1060 tablePtr->hPool = Blt_PoolCreate(BLT_FIXED_SIZE_ITEMS);
1061 }
1062 }
1063
1064 /*
1065 *----------------------------------------------------------------------
1066 *
1067 * Blt_DeleteHashEntry --
1068 *
1069 * Remove a single entry from a hash table.
1070 *
1071 * Results:
1072 * None.
1073 *
1074 * Side effects:
1075 * The entry given by entryPtr is deleted from its table and
1076 * should never again be used by the caller. It is up to the
1077 * caller to free the clientData field of the entry, if that
1078 * is relevant.
1079 *
1080 *----------------------------------------------------------------------
1081 */
1082 void
Blt_DeleteHashEntry(Blt_HashTable * tablePtr,Blt_HashEntry * entryPtr)1083 Blt_DeleteHashEntry(
1084 Blt_HashTable *tablePtr,
1085 Blt_HashEntry *entryPtr)
1086 {
1087 register Blt_HashEntry *prevPtr;
1088 Blt_HashEntry **bucketPtr;
1089 size_t hindex;
1090
1091 if (tablePtr->keyType == BLT_ONE_WORD_KEYS) {
1092 hindex = RANDOM_INDEX(tablePtr, (CONST void *)entryPtr->hval);
1093 } else {
1094 hindex = (entryPtr->hval & tablePtr->mask);
1095 }
1096 bucketPtr = tablePtr->buckets + hindex;
1097 if (*bucketPtr == entryPtr) {
1098 *bucketPtr = entryPtr->nextPtr;
1099 } else {
1100 for (prevPtr = *bucketPtr; /*empty*/; prevPtr = prevPtr->nextPtr) {
1101 if (prevPtr == NULL) {
1102 Blt_Panic("malformed bucket chain in Blt_DeleteHashEntry");
1103 }
1104 if (prevPtr->nextPtr == entryPtr) {
1105 prevPtr->nextPtr = entryPtr->nextPtr;
1106 break;
1107 }
1108 }
1109 }
1110 tablePtr->numEntries--;
1111 if (tablePtr->hPool != NULL) {
1112 Blt_PoolFreeItem(tablePtr->hPool, (char *)entryPtr);
1113 } else {
1114 Blt_Free(entryPtr);
1115 }
1116 }
1117
1118 /*
1119 *----------------------------------------------------------------------
1120 *
1121 * Blt_DeleteHashTable --
1122 *
1123 * Free up everything associated with a hash table except for
1124 * the record for the table itself.
1125 *
1126 * Results:
1127 * None.
1128 *
1129 * Side effects:
1130 * The hash table is no longer useable.
1131 *
1132 *----------------------------------------------------------------------
1133 */
1134 void
Blt_DeleteHashTable(Blt_HashTable * tablePtr)1135 Blt_DeleteHashTable(Blt_HashTable *tablePtr) /* Table to delete. */
1136 {
1137 /*
1138 * Free up all the entries in the table.
1139 */
1140 if (tablePtr->hPool != NULL) {
1141 Blt_PoolDestroy(tablePtr->hPool);
1142 tablePtr->hPool = NULL;
1143 } else {
1144 register Blt_HashEntry *hPtr, *nextPtr;
1145 size_t i;
1146
1147 for (i = 0; i < tablePtr->numBuckets; i++) {
1148 hPtr = tablePtr->buckets[i];
1149 while (hPtr != NULL) {
1150 nextPtr = hPtr->nextPtr;
1151 Blt_Free(hPtr);
1152 hPtr = nextPtr;
1153 }
1154 }
1155 }
1156
1157 /*
1158 * Free up the bucket array, if it was dynamically allocated.
1159 */
1160 if (tablePtr->buckets != tablePtr->staticBuckets) {
1161 Blt_Free(tablePtr->buckets);
1162 }
1163
1164 /*
1165 * Arrange for panics if the table is used again without
1166 * re-initialization.
1167 */
1168
1169 tablePtr->findProc = BogusFind;
1170 tablePtr->createProc = BogusCreate;
1171 }
1172
1173 /*
1174 *----------------------------------------------------------------------
1175 *
1176 * Blt_FirstHashEntry --
1177 *
1178 * Locate the first entry in a hash table and set up a record
1179 * that can be used to step through all the remaining entries
1180 * of the table.
1181 *
1182 * Results:
1183 * The return value is a pointer to the first entry in tablePtr,
1184 * or NULL if tablePtr has no entries in it. The memory at
1185 * *searchPtr is initialized so that subsequent calls to
1186 * Blt_NextHashEntry will return all of the entries in the table,
1187 * one at a time.
1188 *
1189 * Side effects:
1190 * None.
1191 *
1192 *----------------------------------------------------------------------
1193 */
1194 Blt_HashEntry *
Blt_FirstHashEntry(Blt_HashTable * tablePtr,Blt_HashSearch * searchPtr)1195 Blt_FirstHashEntry(
1196 Blt_HashTable *tablePtr, /* Table to search. */
1197 Blt_HashSearch *searchPtr) /* Place to store information about
1198 * progress through the table. */
1199 {
1200 searchPtr->tablePtr = tablePtr;
1201 searchPtr->nextIndex = 0;
1202 searchPtr->nextEntryPtr = NULL;
1203 return Blt_NextHashEntry(searchPtr);
1204 }
1205
1206 /*
1207 *----------------------------------------------------------------------
1208 *
1209 * Blt_NextHashEntry --
1210 *
1211 * Once a hash table enumeration has been initiated by calling
1212 * Blt_FirstHashEntry, this procedure may be called to return
1213 * successive elements of the table.
1214 *
1215 * Results:
1216 * The return value is the next entry in the hash table being
1217 * enumerated, or NULL if the end of the table is reached.
1218 *
1219 * Side effects:
1220 * None.
1221 *
1222 *----------------------------------------------------------------------
1223 */
1224 Blt_HashEntry *
Blt_NextHashEntry(Blt_HashSearch * searchPtr)1225 Blt_NextHashEntry(Blt_HashSearch *searchPtr)
1226 {
1227 Blt_HashEntry *hPtr;
1228
1229 while (searchPtr->nextEntryPtr == NULL) {
1230 if (searchPtr->nextIndex >= searchPtr->tablePtr->numBuckets) {
1231 return NULL;
1232 }
1233 searchPtr->nextEntryPtr =
1234 searchPtr->tablePtr->buckets[searchPtr->nextIndex];
1235 searchPtr->nextIndex++;
1236 }
1237 hPtr = searchPtr->nextEntryPtr;
1238 searchPtr->nextEntryPtr = hPtr->nextPtr;
1239 return hPtr;
1240 }
1241
1242 /*
1243 *----------------------------------------------------------------------
1244 *
1245 * Blt_HashStats --
1246 *
1247 * Return statistics describing the layout of the hash table
1248 * in its hash buckets.
1249 *
1250 * Results:
1251 * The return value is a malloc-ed string containing information
1252 * about tablePtr. It is the caller's responsibility to free
1253 * this string.
1254 *
1255 * Side effects:
1256 * None.
1257 *
1258 *----------------------------------------------------------------------
1259 */
1260 char *
Blt_HashStats(Blt_HashTable * tablePtr)1261 Blt_HashStats(Blt_HashTable *tablePtr) /* Table for which to produce stats. */
1262 {
1263 #define NUM_COUNTERS 10
1264 size_t count[NUM_COUNTERS], overflow, i, j, max;
1265 double average, tmp;
1266 register Blt_HashEntry *hPtr;
1267 Blt_HashEntry **bucketPtr, **endPtr;
1268 char *result, *p;
1269
1270 /*
1271 * Compute a histogram of bucket usage.
1272 */
1273 for (i = 0; i < NUM_COUNTERS; i++) {
1274 count[i] = 0;
1275 }
1276 overflow = 0;
1277 average = 0.0;
1278 max = 0;
1279 endPtr = tablePtr->buckets + tablePtr->numBuckets;
1280 for (bucketPtr = tablePtr->buckets; bucketPtr < endPtr; bucketPtr++) {
1281 j = 0;
1282 for (hPtr = *bucketPtr; hPtr != NULL; hPtr = hPtr->nextPtr) {
1283 j++;
1284 }
1285 if (j > max) {
1286 max = j;
1287 }
1288 if (j < NUM_COUNTERS) {
1289 count[j]++;
1290 } else {
1291 overflow++;
1292 }
1293 tmp = j;
1294 average += (tmp+1.0)*(tmp/tablePtr->numEntries)/2.0;
1295 }
1296
1297 /*
1298 * Print out the histogram and a few other pieces of information.
1299 */
1300 result = Blt_Malloc((unsigned) ((NUM_COUNTERS*60) + 300));
1301 #if SIZEOF_VOID_P == 8
1302 sprintf(result, "%ld entries in table, %ld buckets\n",
1303 tablePtr->numEntries, tablePtr->numBuckets);
1304 #else
1305 sprintf(result, "%d entries in table, %d buckets\n",
1306 tablePtr->numEntries, tablePtr->numBuckets);
1307 #endif
1308 p = result + strlen(result);
1309 for (i = 0; i < NUM_COUNTERS; i++) {
1310 #if SIZEOF_VOID_P == 8
1311 sprintf(p, "number of buckets with %ld entries: %ld\n",
1312 i, count[i]);
1313 #else
1314 sprintf(p, "number of buckets with %d entries: %d\n",
1315 i, count[i]);
1316 #endif
1317 p += strlen(p);
1318 }
1319 #if SIZEOF_VOID_P == 8
1320 sprintf(p, "number of buckets with %d or more entries: %ld\n",
1321 NUM_COUNTERS, overflow);
1322 #else
1323 sprintf(p, "number of buckets with %d or more entries: %d\n",
1324 NUM_COUNTERS, overflow);
1325 #endif
1326 p += strlen(p);
1327 sprintf(p, "average search distance for entry: %.2f\n", average);
1328 p += strlen(p);
1329 #if SIZEOF_VOID_P == 8
1330 sprintf(p, "maximum search distance for entry: %ld", max);
1331 #else
1332 sprintf(p, "maximum search distance for entry: %d", max);
1333 #endif
1334 return result;
1335 }
1336