2 * Routines to provide a memory-efficient hashtable.
4 * Copyright (C) 2007-2020 Wayne Davison
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 3 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; if not, visit the http://fsf.org website.
22 #define HASH_LOAD_LIMIT(size) ((size)*3/4)
24 struct hashtable
*hashtable_create(int size
, int key64
)
27 struct hashtable
*tbl
;
28 int node_size
= key64
? sizeof (struct ht_int64_node
)
29 : sizeof (struct ht_int32_node
);
31 /* Pick a power of 2 that can hold the requested size. */
32 if (size
& (size
-1) || size
< 16) {
38 tbl
= new(struct hashtable
);
39 tbl
->nodes
= new_array0(char, size
* node_size
);
42 tbl
->node_size
= node_size
;
43 tbl
->key64
= key64
? 1 : 0;
45 if (DEBUG_GTE(HASH
, 1)) {
48 snprintf(buf
, sizeof buf
, "req: %d, ", req
);
51 rprintf(FINFO
, "[%s] created hashtable %lx (%ssize: %d, keys: %d-bit)\n",
52 who_am_i(), (long)tbl
, buf
, size
, key64
? 64 : 32);
58 void hashtable_destroy(struct hashtable
*tbl
)
60 if (DEBUG_GTE(HASH
, 1)) {
61 rprintf(FINFO
, "[%s] destroyed hashtable %lx (size: %d, keys: %d-bit)\n",
62 who_am_i(), (long)tbl
, tbl
->size
, tbl
->key64
? 64 : 32);
68 /* Returns the node that holds the indicated key if it exists. When it does not
69 * exist, it returns either NULL (when data_when_new is NULL), or it returns a
70 * new node with its node->data set to the indicated value.
72 * If your code doesn't know the data value for a new node in advance (usually
73 * because it doesn't know if a node is new or not) you should pass in a unique
74 * (non-0) value that you can use to check if the returned node is new. You can
75 * then overwrite the data with any value you want (even 0) since it only needs
76 * to be different than whatever data_when_new value you use later on.
78 * This return is a void* just because it might be pointing at a ht_int32_node
79 * or a ht_int64_node, and that makes the caller's assignment a little easier. */
80 void *hashtable_find(struct hashtable
*tbl
, int64 key
, void *data_when_new
)
82 int key64
= tbl
->key64
;
83 struct ht_int32_node
*node
;
86 if (key64
? key
== 0 : (int32
)key
== 0) {
87 rprintf(FERROR
, "Internal hashtable error: illegal key supplied!\n");
88 exit_cleanup(RERR_MESSAGEIO
);
91 if (data_when_new
&& tbl
->entries
> HASH_LOAD_LIMIT(tbl
->size
)) {
92 void *old_nodes
= tbl
->nodes
;
93 int size
= tbl
->size
* 2;
96 tbl
->nodes
= new_array0(char, size
* tbl
->node_size
);
100 if (DEBUG_GTE(HASH
, 1)) {
101 rprintf(FINFO
, "[%s] growing hashtable %lx (size: %d, keys: %d-bit)\n",
102 who_am_i(), (long)tbl
, size
, key64
? 64 : 32);
105 for (i
= size
/ 2; i
-- > 0; ) {
106 struct ht_int32_node
*move_node
= HT_NODE(tbl
, old_nodes
, i
);
107 int64 move_key
= HT_KEY(move_node
, key64
);
111 hashtable_find(tbl
, move_key
, move_node
->data
);
113 node
= hashtable_find(tbl
, move_key
, "");
122 /* Based on Jenkins One-at-a-time hash. */
123 uchar buf
[4], *keyp
= buf
;
127 for (ndx
= 0, i
= 0; i
< 4; i
++) {
136 /* Based on Jenkins hashword() from lookup3.c. */
139 /* Set up the internal state */
140 a
= b
= c
= 0xdeadbeef + (8 << 2);
142 #define rot(x,k) (((x)<<(k)) ^ ((x)>>(32-(k))))
143 #if SIZEOF_INT64 >= 8
144 b
+= (uint32
)(key
>> 32);
147 c
^= b
; c
-= rot(b
, 14);
148 a
^= c
; a
-= rot(c
, 11);
149 b
^= a
; b
-= rot(a
, 25);
150 c
^= b
; c
-= rot(b
, 16);
151 a
^= c
; a
-= rot(c
, 4);
152 b
^= a
; b
-= rot(a
, 14);
153 c
^= b
; c
-= rot(b
, 24);
158 /* If it already exists, return the node. If we're not
159 * allocating, return NULL if the key is not found. */
163 ndx
&= tbl
->size
- 1;
164 node
= HT_NODE(tbl
, tbl
->nodes
, ndx
);
165 nkey
= HT_KEY(node
, key64
);
177 /* Take over this empty spot and then return the node. */
179 ((struct ht_int64_node
*)node
)->key
= key
;
181 node
->key
= (int32
)key
;
182 node
->data
= data_when_new
;
187 #ifndef WORDS_BIGENDIAN
188 # define HASH_LITTLE_ENDIAN 1
189 # define HASH_BIG_ENDIAN 0
191 # define HASH_LITTLE_ENDIAN 0
192 # define HASH_BIG_ENDIAN 1
196 -------------------------------------------------------------------------------
197 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
199 These are functions for producing 32-bit hashes for hash table lookup.
200 hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
201 are externally useful functions. Routines to test the hash are included
202 if SELF_TEST is defined. You can use this free for any purpose. It's in
203 the public domain. It has no warranty.
205 You probably want to use hashlittle(). hashlittle() and hashbig()
206 hash byte arrays. hashlittle() is is faster than hashbig() on
207 little-endian machines. Intel and AMD are little-endian machines.
208 On second thought, you probably want hashlittle2(), which is identical to
209 hashlittle() except it returns two 32-bit hashes for the price of one.
210 You could implement hashbig2() if you wanted but I haven't bothered here.
212 If you want to find a hash of, say, exactly 7 integers, do
213 a = i1; b = i2; c = i3;
215 a += i4; b += i5; c += i6;
219 then use c as the hash value. If you have a variable length array of
220 4-byte integers to hash, use hash_word(). If you have a byte array (like
221 a character string), use hashlittle(). If you have several byte arrays, or
222 a mix of things, see the comments above hashlittle().
224 Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
225 then mix those integers. This is fast (you can do a lot more thorough
226 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
227 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
230 #define hashsize(n) ((uint32_t)1<<(n))
231 #define hashmask(n) (hashsize(n)-1)
232 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
235 -------------------------------------------------------------------------------
236 mix -- mix 3 32-bit values reversibly.
238 This is reversible, so any information in (a,b,c) before mix() is
239 still in (a,b,c) after mix().
241 If four pairs of (a,b,c) inputs are run through mix(), or through
242 mix() in reverse, there are at least 32 bits of the output that
243 are sometimes the same for one pair and different for another pair.
245 * pairs that differed by one bit, by two bits, in any combination
246 of top bits of (a,b,c), or in any combination of bottom bits of
248 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
249 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
250 is commonly produced by subtraction) look like a single 1-bit
252 * the base values were pseudorandom, all zero but one bit set, or
253 all zero plus a counter that starts at zero.
255 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
260 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
261 for "differ" defined as + with a one-bit base and a two-bit delta. I
262 used http://burtleburtle.net/bob/hash/avalanche.html to choose
263 the operations, constants, and arrangements of the variables.
265 This does not achieve avalanche. There are input bits of (a,b,c)
266 that fail to affect some output bits of (a,b,c), especially of a. The
267 most thoroughly mixed value is c, but it doesn't really even achieve
270 This allows some parallelism. Read-after-writes are good at doubling
271 the number of bits affected, so the goal of mixing pulls in the opposite
272 direction as the goal of parallelism. I did what I could. Rotates
273 seem to cost as much as shifts on every machine I could lay my hands
274 on, and rotates are much kinder to the top and bottom bits, so I used
276 -------------------------------------------------------------------------------
280 a -= c; a ^= rot(c, 4); c += b; \
281 b -= a; b ^= rot(a, 6); a += c; \
282 c -= b; c ^= rot(b, 8); b += a; \
283 a -= c; a ^= rot(c,16); c += b; \
284 b -= a; b ^= rot(a,19); a += c; \
285 c -= b; c ^= rot(b, 4); b += a; \
289 -------------------------------------------------------------------------------
290 final -- final mixing of 3 32-bit values (a,b,c) into c
292 Pairs of (a,b,c) values differing in only a few bits will usually
293 produce values of c that look totally different. This was tested for
294 * pairs that differed by one bit, by two bits, in any combination
295 of top bits of (a,b,c), or in any combination of bottom bits of
297 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
298 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
299 is commonly produced by subtraction) look like a single 1-bit
301 * the base values were pseudorandom, all zero but one bit set, or
302 all zero plus a counter that starts at zero.
304 These constants passed:
307 and these came close:
311 -------------------------------------------------------------------------------
313 #define final(a,b,c) \
315 c ^= b; c -= rot(b,14); \
316 a ^= c; a -= rot(c,11); \
317 b ^= a; b -= rot(a,25); \
318 c ^= b; c -= rot(b,16); \
319 a ^= c; a -= rot(c,4); \
320 b ^= a; b -= rot(a,14); \
321 c ^= b; c -= rot(b,24); \
326 -------------------------------------------------------------------------------
327 hashlittle() -- hash a variable-length key into a 32-bit value
328 k : the key (the unaligned variable-length array of bytes)
329 length : the length of the key, counting by bytes
330 val2 : IN: can be any 4-byte value OUT: second 32 bit hash.
331 Returns a 32-bit value. Every bit of the key affects every bit of
332 the return value. Two keys differing by one or two bits will have
333 totally different hash values. Note that the return value is better
334 mixed than val2, so use that first.
336 The best hash table sizes are powers of 2. There is no need to do
337 mod a prime (mod is sooo slow!). If you need less than 32 bits,
338 use a bitmask. For example, if you need only 10 bits, do
339 h = (h & hashmask(10));
340 In which case, the hash table should have hashsize(10) elements.
342 If you are hashing n strings (uint8_t **)k, do it like this:
343 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
345 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
346 code any way you wish, private, educational, or commercial. It's free.
348 Use for hash table lookup, or anything where one collision in 2^^32 is
349 acceptable. Do NOT use for cryptographic purposes.
350 -------------------------------------------------------------------------------
353 #define NON_ZERO_32(x) ((x) ? (x) : (uint32_t)1)
354 #define NON_ZERO_64(x, y) ((x) || (y) ? (y) | (int64)(x) << 32 | (y) : (int64)1)
356 uint32_t hashlittle(const void *key
, size_t length
)
358 uint32_t a
,b
,c
; /* internal state */
359 union { const void *ptr
; size_t i
; } u
; /* needed for Mac Powerbook G4 */
361 /* Set up the internal state */
362 a
= b
= c
= 0xdeadbeef + ((uint32_t)length
);
365 if (HASH_LITTLE_ENDIAN
&& ((u
.i
& 0x3) == 0)) {
366 const uint32_t *k
= (const uint32_t *)key
; /* read 32-bit chunks */
369 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
380 /*----------------------------- handle the last (probably partial) block */
381 k8
= (const uint8_t *)k
;
384 case 12: c
+=k
[2]; b
+=k
[1]; a
+=k
[0]; break;
385 case 11: c
+=((uint32_t)k8
[10])<<16; /* fall through */
386 case 10: c
+=((uint32_t)k8
[9])<<8; /* fall through */
387 case 9 : c
+=k8
[8]; /* fall through */
388 case 8 : b
+=k
[1]; a
+=k
[0]; break;
389 case 7 : b
+=((uint32_t)k8
[6])<<16; /* fall through */
390 case 6 : b
+=((uint32_t)k8
[5])<<8; /* fall through */
391 case 5 : b
+=k8
[4]; /* fall through */
392 case 4 : a
+=k
[0]; break;
393 case 3 : a
+=((uint32_t)k8
[2])<<16; /* fall through */
394 case 2 : a
+=((uint32_t)k8
[1])<<8; /* fall through */
395 case 1 : a
+=k8
[0]; break;
396 case 0 : return NON_ZERO_32(c
);
398 } else if (HASH_LITTLE_ENDIAN
&& ((u
.i
& 0x1) == 0)) {
399 const uint16_t *k
= (const uint16_t *)key
; /* read 16-bit chunks */
402 /*--------------- all but last block: aligned reads and different mixing */
405 a
+= k
[0] + (((uint32_t)k
[1])<<16);
406 b
+= k
[2] + (((uint32_t)k
[3])<<16);
407 c
+= k
[4] + (((uint32_t)k
[5])<<16);
413 /*----------------------------- handle the last (probably partial) block */
414 k8
= (const uint8_t *)k
;
417 case 12: c
+=k
[4]+(((uint32_t)k
[5])<<16);
418 b
+=k
[2]+(((uint32_t)k
[3])<<16);
419 a
+=k
[0]+(((uint32_t)k
[1])<<16);
421 case 11: c
+=((uint32_t)k8
[10])<<16; /* fall through */
423 b
+=k
[2]+(((uint32_t)k
[3])<<16);
424 a
+=k
[0]+(((uint32_t)k
[1])<<16);
426 case 9 : c
+=k8
[8]; /* fall through */
427 case 8 : b
+=k
[2]+(((uint32_t)k
[3])<<16);
428 a
+=k
[0]+(((uint32_t)k
[1])<<16);
430 case 7 : b
+=((uint32_t)k8
[6])<<16; /* fall through */
432 a
+=k
[0]+(((uint32_t)k
[1])<<16);
434 case 5 : b
+=k8
[4]; /* fall through */
435 case 4 : a
+=k
[0]+(((uint32_t)k
[1])<<16);
437 case 3 : a
+=((uint32_t)k8
[2])<<16; /* fall through */
442 case 0 : return NON_ZERO_32(c
); /* zero length requires no mixing */
445 } else { /* need to read the key one byte at a time */
446 const uint8_t *k
= (const uint8_t *)key
;
448 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
452 a
+= ((uint32_t)k
[1])<<8;
453 a
+= ((uint32_t)k
[2])<<16;
454 a
+= ((uint32_t)k
[3])<<24;
456 b
+= ((uint32_t)k
[5])<<8;
457 b
+= ((uint32_t)k
[6])<<16;
458 b
+= ((uint32_t)k
[7])<<24;
460 c
+= ((uint32_t)k
[9])<<8;
461 c
+= ((uint32_t)k
[10])<<16;
462 c
+= ((uint32_t)k
[11])<<24;
468 /*-------------------------------- last block: affect all 32 bits of (c) */
469 switch(length
) /* all the case statements fall through */
471 case 12: c
+=((uint32_t)k
[11])<<24;
473 case 11: c
+=((uint32_t)k
[10])<<16;
475 case 10: c
+=((uint32_t)k
[9])<<8;
479 case 8 : b
+=((uint32_t)k
[7])<<24;
481 case 7 : b
+=((uint32_t)k
[6])<<16;
483 case 6 : b
+=((uint32_t)k
[5])<<8;
487 case 4 : a
+=((uint32_t)k
[3])<<24;
489 case 3 : a
+=((uint32_t)k
[2])<<16;
491 case 2 : a
+=((uint32_t)k
[1])<<8;
495 case 0 : return NON_ZERO_32(c
);
500 return NON_ZERO_32(c
);
503 #if SIZEOF_INT64 >= 8
505 * hashlittle2: return 2 32-bit hash values joined into an int64.
507 * This is identical to hashlittle(), except it returns two 32-bit hash
508 * values instead of just one. This is good enough for hash table
509 * lookup with 2^^64 buckets, or if you want a second hash if you're not
510 * happy with the first, or if you want a probably-unique 64-bit ID for
511 * the key. *pc is better mixed than *pb, so use *pc first. If you want
512 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
514 int64
hashlittle2(const void *key
, size_t length
)
516 uint32_t a
,b
,c
; /* internal state */
517 union { const void *ptr
; size_t i
; } u
; /* needed for Mac Powerbook G4 */
519 /* Set up the internal state */
520 a
= b
= c
= 0xdeadbeef + ((uint32_t)length
);
523 if (HASH_LITTLE_ENDIAN
&& ((u
.i
& 0x3) == 0)) {
524 const uint32_t *k
= (const uint32_t *)key
; /* read 32-bit chunks */
527 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
538 /*----------------------------- handle the last (probably partial) block */
539 k8
= (const uint8_t *)k
;
542 case 12: c
+=k
[2]; b
+=k
[1]; a
+=k
[0]; break;
543 case 11: c
+=((uint32_t)k8
[10])<<16; /* fall through */
544 case 10: c
+=((uint32_t)k8
[9])<<8; /* fall through */
545 case 9 : c
+=k8
[8]; /* fall through */
546 case 8 : b
+=k
[1]; a
+=k
[0]; break;
547 case 7 : b
+=((uint32_t)k8
[6])<<16; /* fall through */
548 case 6 : b
+=((uint32_t)k8
[5])<<8; /* fall through */
549 case 5 : b
+=k8
[4]; /* fall through */
550 case 4 : a
+=k
[0]; break;
551 case 3 : a
+=((uint32_t)k8
[2])<<16; /* fall through */
552 case 2 : a
+=((uint32_t)k8
[1])<<8; /* fall through */
553 case 1 : a
+=k8
[0]; break;
554 case 0 : return NON_ZERO_64(b
, c
);
556 } else if (HASH_LITTLE_ENDIAN
&& ((u
.i
& 0x1) == 0)) {
557 const uint16_t *k
= (const uint16_t *)key
; /* read 16-bit chunks */
560 /*--------------- all but last block: aligned reads and different mixing */
563 a
+= k
[0] + (((uint32_t)k
[1])<<16);
564 b
+= k
[2] + (((uint32_t)k
[3])<<16);
565 c
+= k
[4] + (((uint32_t)k
[5])<<16);
571 /*----------------------------- handle the last (probably partial) block */
572 k8
= (const uint8_t *)k
;
575 case 12: c
+=k
[4]+(((uint32_t)k
[5])<<16);
576 b
+=k
[2]+(((uint32_t)k
[3])<<16);
577 a
+=k
[0]+(((uint32_t)k
[1])<<16);
579 case 11: c
+=((uint32_t)k8
[10])<<16; /* fall through */
581 b
+=k
[2]+(((uint32_t)k
[3])<<16);
582 a
+=k
[0]+(((uint32_t)k
[1])<<16);
584 case 9 : c
+=k8
[8]; /* fall through */
585 case 8 : b
+=k
[2]+(((uint32_t)k
[3])<<16);
586 a
+=k
[0]+(((uint32_t)k
[1])<<16);
588 case 7 : b
+=((uint32_t)k8
[6])<<16; /* fall through */
590 a
+=k
[0]+(((uint32_t)k
[1])<<16);
592 case 5 : b
+=k8
[4]; /* fall through */
593 case 4 : a
+=k
[0]+(((uint32_t)k
[1])<<16);
595 case 3 : a
+=((uint32_t)k8
[2])<<16; /* fall through */
600 case 0 : return NON_ZERO_64(b
, c
); /* zero length strings require no mixing */
603 } else { /* need to read the key one byte at a time */
604 const uint8_t *k
= (const uint8_t *)key
;
606 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
610 a
+= ((uint32_t)k
[1])<<8;
611 a
+= ((uint32_t)k
[2])<<16;
612 a
+= ((uint32_t)k
[3])<<24;
614 b
+= ((uint32_t)k
[5])<<8;
615 b
+= ((uint32_t)k
[6])<<16;
616 b
+= ((uint32_t)k
[7])<<24;
618 c
+= ((uint32_t)k
[9])<<8;
619 c
+= ((uint32_t)k
[10])<<16;
620 c
+= ((uint32_t)k
[11])<<24;
626 /*-------------------------------- last block: affect all 32 bits of (c) */
627 switch(length
) /* all the case statements fall through */
629 case 12: c
+=((uint32_t)k
[11])<<24;
631 case 11: c
+=((uint32_t)k
[10])<<16;
633 case 10: c
+=((uint32_t)k
[9])<<8;
637 case 8 : b
+=((uint32_t)k
[7])<<24;
639 case 7 : b
+=((uint32_t)k
[6])<<16;
641 case 6 : b
+=((uint32_t)k
[5])<<8;
645 case 4 : a
+=((uint32_t)k
[3])<<24;
647 case 3 : a
+=((uint32_t)k
[2])<<16;
649 case 2 : a
+=((uint32_t)k
[1])<<8;
653 case 0 : return NON_ZERO_64(b
, c
);
658 return NON_ZERO_64(b
, c
);
661 #define hashlittle2(key, len) hashlittle(key, len)