1 /*
2 * hash.c Non-thread-safe split-ordered hash table.
3 *
4 * The weird "reverse" function is based on an idea from
5 * "Split-Ordered Lists - Lock-free Resizable Hash Tables", with
6 * modifications so that they're not lock-free. :(
7 *
8 * However, the split-order idea allows a fast & easy splitting of the
9 * hash bucket chain when the hash table is resized. Without it, we'd
10 * have to check & update the pointers for every node in the buck chain,
11 * rather than being able to move 1/2 of the entries in the chain with
12 * one update.
13 *
14 * Version: $Id: f9d088196f294b1cf1df4a64bdc7d8715bc69220 $
15 *
16 * This library is free software; you can redistribute it and/or
17 * modify it under the terms of the GNU Lesser General Public
18 * License as published by the Free Software Foundation; either
19 * version 2.1 of the License, or (at your option) any later version.
20 *
21 * This library is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
24 * Lesser General Public License for more details.
25 *
26 * You should have received a copy of the GNU Lesser General Public
27 * License along with this library; if not, write to the Free Software
28 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
29 *
30 * Copyright 2005,2006 The FreeRADIUS server project
31 */
32
33 RCSID("$Id: f9d088196f294b1cf1df4a64bdc7d8715bc69220 $")
34
35 #include <freeradius-devel/libradius.h>
36
37 /*
38 * A reasonable number of buckets to start off with.
39 * Should be a power of two.
40 */
41 #define FR_HASH_NUM_BUCKETS (64)
42
43 struct fr_hash_entry_s {
44 fr_hash_entry_t *next;
45 uint32_t reversed;
46 uint32_t key;
47 void const *data;
48 };
49
50
51 struct fr_hash_table_t {
52 int num_elements;
53 int num_buckets; /* power of 2 */
54 int next_grow;
55 int mask;
56
57 fr_hash_table_free_t free;
58 fr_hash_table_hash_t hash;
59 fr_hash_table_cmp_t cmp;
60
61 fr_hash_entry_t null;
62
63 fr_hash_entry_t **buckets;
64 };
65
66 #ifdef TESTING
67 static int grow = 0;
68 #endif
69
70 /*
71 * perl -e 'foreach $i (0..255) {$r = 0; foreach $j (0 .. 7 ) { if (($i & ( 1<< $j)) != 0) { $r |= (1 << (7 - $j));}} print $r, ", ";if (($i & 7) == 7) {print "\n";}}'
72 */
73 static const uint8_t reversed_byte[256] = {
74 0, 128, 64, 192, 32, 160, 96, 224,
75 16, 144, 80, 208, 48, 176, 112, 240,
76 8, 136, 72, 200, 40, 168, 104, 232,
77 24, 152, 88, 216, 56, 184, 120, 248,
78 4, 132, 68, 196, 36, 164, 100, 228,
79 20, 148, 84, 212, 52, 180, 116, 244,
80 12, 140, 76, 204, 44, 172, 108, 236,
81 28, 156, 92, 220, 60, 188, 124, 252,
82 2, 130, 66, 194, 34, 162, 98, 226,
83 18, 146, 82, 210, 50, 178, 114, 242,
84 10, 138, 74, 202, 42, 170, 106, 234,
85 26, 154, 90, 218, 58, 186, 122, 250,
86 6, 134, 70, 198, 38, 166, 102, 230,
87 22, 150, 86, 214, 54, 182, 118, 246,
88 14, 142, 78, 206, 46, 174, 110, 238,
89 30, 158, 94, 222, 62, 190, 126, 254,
90 1, 129, 65, 193, 33, 161, 97, 225,
91 17, 145, 81, 209, 49, 177, 113, 241,
92 9, 137, 73, 201, 41, 169, 105, 233,
93 25, 153, 89, 217, 57, 185, 121, 249,
94 5, 133, 69, 197, 37, 165, 101, 229,
95 21, 149, 85, 213, 53, 181, 117, 245,
96 13, 141, 77, 205, 45, 173, 109, 237,
97 29, 157, 93, 221, 61, 189, 125, 253,
98 3, 131, 67, 195, 35, 163, 99, 227,
99 19, 147, 83, 211, 51, 179, 115, 243,
100 11, 139, 75, 203, 43, 171, 107, 235,
101 27, 155, 91, 219, 59, 187, 123, 251,
102 7, 135, 71, 199, 39, 167, 103, 231,
103 23, 151, 87, 215, 55, 183, 119, 247,
104 15, 143, 79, 207, 47, 175, 111, 239,
105 31, 159, 95, 223, 63, 191, 127, 255
106 };
107
108
109 /*
110 * perl -e 'foreach $i (0..255) {$r = 0;foreach $j (0 .. 7) { $r = $i & (1 << (7 - $j)); last if ($r)} print $i & ~($r), ", ";if (($i & 7) == 7) {print "\n";}}'
111 */
112 static uint8_t parent_byte[256] = {
113 0, 0, 0, 1, 0, 1, 2, 3,
114 0, 1, 2, 3, 4, 5, 6, 7,
115 0, 1, 2, 3, 4, 5, 6, 7,
116 8, 9, 10, 11, 12, 13, 14, 15,
117 0, 1, 2, 3, 4, 5, 6, 7,
118 8, 9, 10, 11, 12, 13, 14, 15,
119 16, 17, 18, 19, 20, 21, 22, 23,
120 24, 25, 26, 27, 28, 29, 30, 31,
121 0, 1, 2, 3, 4, 5, 6, 7,
122 8, 9, 10, 11, 12, 13, 14, 15,
123 16, 17, 18, 19, 20, 21, 22, 23,
124 24, 25, 26, 27, 28, 29, 30, 31,
125 32, 33, 34, 35, 36, 37, 38, 39,
126 40, 41, 42, 43, 44, 45, 46, 47,
127 48, 49, 50, 51, 52, 53, 54, 55,
128 56, 57, 58, 59, 60, 61, 62, 63,
129 0, 1, 2, 3, 4, 5, 6, 7,
130 8, 9, 10, 11, 12, 13, 14, 15,
131 16, 17, 18, 19, 20, 21, 22, 23,
132 24, 25, 26, 27, 28, 29, 30, 31,
133 32, 33, 34, 35, 36, 37, 38, 39,
134 40, 41, 42, 43, 44, 45, 46, 47,
135 48, 49, 50, 51, 52, 53, 54, 55,
136 56, 57, 58, 59, 60, 61, 62, 63,
137 64, 65, 66, 67, 68, 69, 70, 71,
138 72, 73, 74, 75, 76, 77, 78, 79,
139 80, 81, 82, 83, 84, 85, 86, 87,
140 88, 89, 90, 91, 92, 93, 94, 95,
141 96, 97, 98, 99, 100, 101, 102, 103,
142 104, 105, 106, 107, 108, 109, 110, 111,
143 112, 113, 114, 115, 116, 117, 118, 119,
144 120, 121, 122, 123, 124, 125, 126, 127
145 };
146
147
148 /*
149 * Reverse a key.
150 */
reverse(uint32_t key)151 static uint32_t reverse(uint32_t key)
152 {
153 return ((reversed_byte[key & 0xff] << 24) |
154 (reversed_byte[(key >> 8) & 0xff] << 16) |
155 (reversed_byte[(key >> 16) & 0xff] << 8) |
156 (reversed_byte[(key >> 24) & 0xff]));
157 }
158
159 /*
160 * Take the parent by discarding the highest bit that is set.
161 */
parent_of(uint32_t key)162 static uint32_t parent_of(uint32_t key)
163 {
164 if (key > 0x00ffffff)
165 return (key & 0x00ffffff) | (parent_byte[key >> 24] << 24);
166
167 if (key > 0x0000ffff)
168 return (key & 0x0000ffff) | (parent_byte[key >> 16] << 16);
169
170 if (key > 0x000000ff)
171 return (key & 0x000000ff) | (parent_byte[key >> 8] << 8);
172
173 return parent_byte[key];
174 }
175
176
list_find(fr_hash_table_t * ht,fr_hash_entry_t * head,uint32_t reversed,void const * data)177 static fr_hash_entry_t *list_find(fr_hash_table_t *ht,
178 fr_hash_entry_t *head,
179 uint32_t reversed,
180 void const *data)
181 {
182 fr_hash_entry_t *cur;
183
184 for (cur = head; cur != &ht->null; cur = cur->next) {
185 if (cur->reversed == reversed) {
186 if (ht->cmp) {
187 int cmp = ht->cmp(data, cur->data);
188 if (cmp > 0) break;
189 if (cmp < 0) continue;
190 }
191 return cur;
192 }
193 if (cur->reversed > reversed) break;
194 }
195
196 return NULL;
197 }
198
199
200 /*
201 * Inserts a new entry into the list, in order.
202 */
list_insert(fr_hash_table_t * ht,fr_hash_entry_t ** head,fr_hash_entry_t * node)203 static int list_insert(fr_hash_table_t *ht,
204 fr_hash_entry_t **head, fr_hash_entry_t *node)
205 {
206 fr_hash_entry_t **last, *cur;
207
208 last = head;
209
210 for (cur = *head; cur != &ht->null; cur = cur->next) {
211 if (cur->reversed > node->reversed) break;
212 last = &(cur->next);
213
214 if (cur->reversed == node->reversed) {
215 if (ht->cmp) {
216 int cmp = ht->cmp(node->data, cur->data);
217 if (cmp > 0) break;
218 if (cmp < 0) continue;
219 }
220 return 0;
221 }
222 }
223
224 node->next = *last;
225 *last = node;
226
227 return 1;
228 }
229
230
231 /*
232 * Delete an entry from the list.
233 */
list_delete(fr_hash_table_t * ht,fr_hash_entry_t ** head,fr_hash_entry_t * node)234 static int list_delete(fr_hash_table_t *ht,
235 fr_hash_entry_t **head, fr_hash_entry_t *node)
236 {
237 fr_hash_entry_t **last, *cur;
238
239 last = head;
240
241 for (cur = *head; cur != &ht->null; cur = cur->next) {
242 if (cur == node) break;
243 last = &(cur->next);
244 }
245
246 *last = node->next;
247 return 1;
248 }
249
250
251 /*
252 * Create the table.
253 *
254 * Memory usage in bytes is (20/3) * number of entries.
255 */
fr_hash_table_create(fr_hash_table_hash_t hashNode,fr_hash_table_cmp_t cmpNode,fr_hash_table_free_t freeNode)256 fr_hash_table_t *fr_hash_table_create(fr_hash_table_hash_t hashNode,
257 fr_hash_table_cmp_t cmpNode,
258 fr_hash_table_free_t freeNode)
259 {
260 fr_hash_table_t *ht;
261
262 if (!hashNode) return NULL;
263
264 ht = malloc(sizeof(*ht));
265 if (!ht) return NULL;
266
267 memset(ht, 0, sizeof(*ht));
268 ht->free = freeNode;
269 ht->hash = hashNode;
270 ht->cmp = cmpNode;
271 ht->num_buckets = FR_HASH_NUM_BUCKETS;
272 ht->mask = ht->num_buckets - 1;
273
274 /*
275 * Have a default load factor of 2.5. In practice this
276 * means that the average load will hit 3 before the
277 * table grows.
278 */
279 ht->next_grow = (ht->num_buckets << 1) + (ht->num_buckets >> 1);
280
281 ht->buckets = malloc(sizeof(*ht->buckets) * ht->num_buckets);
282 if (!ht->buckets) {
283 free(ht);
284 return NULL;
285 }
286 memset(ht->buckets, 0, sizeof(*ht->buckets) * ht->num_buckets);
287
288 ht->null.reversed = ~0;
289 ht->null.key = ~0;
290 ht->null.next = &ht->null;
291
292 ht->buckets[0] = &ht->null;
293
294 return ht;
295 }
296
297
298 /*
299 * If the current bucket is uninitialized, initialize it
300 * by recursively copying information from the parent.
301 *
302 * We may have a situation where entry E is a parent to 2 other
303 * entries E' and E". If we split E into E and E', then the
304 * nodes meant for E" end up in E or E', either of which is
305 * wrong. To solve that problem, we walk down the whole chain,
306 * inserting the elements into the correct place.
307 */
fr_hash_table_fixup(fr_hash_table_t * ht,uint32_t entry)308 static void fr_hash_table_fixup(fr_hash_table_t *ht, uint32_t entry)
309 {
310 uint32_t parent_entry;
311 fr_hash_entry_t **last, *cur;
312 uint32_t this;
313
314 parent_entry = parent_of(entry);
315
316 /* parent_entry == entry if and only if entry == 0 */
317
318 if (!ht->buckets[parent_entry]) {
319 fr_hash_table_fixup(ht, parent_entry);
320 }
321
322 /*
323 * Keep walking down cur, trying to find entries that
324 * don't belong here any more. There may be multiple
325 * ones, so we can't have a naive algorithm...
326 */
327 last = &ht->buckets[parent_entry];
328 this = parent_entry;
329
330 for (cur = *last; cur != &ht->null; cur = cur->next) {
331 uint32_t real_entry;
332
333 real_entry = cur->key & ht->mask;
334 if (real_entry != this) { /* ht->buckets[real_entry] == NULL */
335 *last = &ht->null;
336 ht->buckets[real_entry] = cur;
337 this = real_entry;
338 }
339
340 last = &(cur->next);
341 }
342
343 /*
344 * We may NOT have initialized this bucket, so do it now.
345 */
346 if (!ht->buckets[entry]) ht->buckets[entry] = &ht->null;
347 }
348
349 /*
350 * This should be a power of two. Changing it to 4 doesn't seem
351 * to make any difference.
352 */
353 #define GROW_FACTOR (2)
354
355 /*
356 * Grow the hash table.
357 */
fr_hash_table_grow(fr_hash_table_t * ht)358 static void fr_hash_table_grow(fr_hash_table_t *ht)
359 {
360 fr_hash_entry_t **buckets;
361
362 buckets = malloc(sizeof(*buckets) * GROW_FACTOR * ht->num_buckets);
363 if (!buckets) return;
364
365 memcpy(buckets, ht->buckets,
366 sizeof(*buckets) * ht->num_buckets);
367 memset(&buckets[ht->num_buckets], 0,
368 sizeof(*buckets) * ht->num_buckets);
369
370 free(ht->buckets);
371 ht->buckets = buckets;
372 ht->num_buckets *= GROW_FACTOR;
373 ht->next_grow *= GROW_FACTOR;
374 ht->mask = ht->num_buckets - 1;
375 #ifdef TESTING
376 grow = 1;
377 fprintf(stderr, "GROW TO %d\n", ht->num_buckets);
378 #endif
379 }
380
381
382 /*
383 * Insert data.
384 */
fr_hash_table_insert(fr_hash_table_t * ht,void const * data)385 int fr_hash_table_insert(fr_hash_table_t *ht, void const *data)
386 {
387 uint32_t key;
388 uint32_t entry;
389 uint32_t reversed;
390 fr_hash_entry_t *node;
391
392 if (!ht || !data) return 0;
393
394 key = ht->hash(data);
395 entry = key & ht->mask;
396 reversed = reverse(key);
397
398 if (!ht->buckets[entry]) fr_hash_table_fixup(ht, entry);
399
400 /*
401 * If we try to do our own memory allocation here, the
402 * speedup is only ~15% or so, which isn't worth it.
403 */
404 node = malloc(sizeof(*node));
405 if (!node) return 0;
406 memset(node, 0, sizeof(*node));
407
408 node->next = &ht->null;
409 node->reversed = reversed;
410 node->key = key;
411 node->data = data;
412
413 /* already in the table, can't insert it */
414 if (!list_insert(ht, &ht->buckets[entry], node)) {
415 free(node);
416 return 0;
417 }
418
419 /*
420 * Check the load factor, and grow the table if
421 * necessary.
422 */
423 ht->num_elements++;
424 if (ht->num_elements >= ht->next_grow) {
425 fr_hash_table_grow(ht);
426 }
427
428 return 1;
429 }
430
431
432 /*
433 * Internal find a node routine.
434 */
fr_hash_table_find(fr_hash_table_t * ht,void const * data)435 static fr_hash_entry_t *fr_hash_table_find(fr_hash_table_t *ht, void const *data)
436 {
437 uint32_t key;
438 uint32_t entry;
439 uint32_t reversed;
440
441 if (!ht) return NULL;
442
443 key = ht->hash(data);
444 entry = key & ht->mask;
445 reversed = reverse(key);
446
447 if (!ht->buckets[entry]) fr_hash_table_fixup(ht, entry);
448
449 return list_find(ht, ht->buckets[entry], reversed, data);
450 }
451
452
453 /*
454 * Replace old data with new data, OR insert if there is no old.
455 */
fr_hash_table_replace(fr_hash_table_t * ht,void const * data)456 int fr_hash_table_replace(fr_hash_table_t *ht, void const *data)
457 {
458 fr_hash_entry_t *node;
459 void *tofree;
460
461 if (!ht || !data) return 0;
462
463 node = fr_hash_table_find(ht, data);
464 if (!node) {
465 return fr_hash_table_insert(ht, data);
466 }
467
468 if (ht->free) {
469 memcpy(&tofree, &node->data, sizeof(tofree));
470 ht->free(tofree);
471 }
472 node->data = data;
473
474 return 1;
475 }
476
477
478 /*
479 * Find data from a template
480 */
fr_hash_table_finddata(fr_hash_table_t * ht,void const * data)481 void *fr_hash_table_finddata(fr_hash_table_t *ht, void const *data)
482 {
483 fr_hash_entry_t *node;
484 void *out;
485
486 node = fr_hash_table_find(ht, data);
487 if (!node) return NULL;
488
489 memcpy(&out, &node->data, sizeof(out));
490
491 return out;
492 }
493
494
495
496 /*
497 * Yank an entry from the hash table, without freeing the data.
498 */
fr_hash_table_yank(fr_hash_table_t * ht,void const * data)499 void *fr_hash_table_yank(fr_hash_table_t *ht, void const *data)
500 {
501 uint32_t key;
502 uint32_t entry;
503 uint32_t reversed;
504 void *old;
505 fr_hash_entry_t *node;
506
507 if (!ht) return NULL;
508
509 key = ht->hash(data);
510 entry = key & ht->mask;
511 reversed = reverse(key);
512
513 if (!ht->buckets[entry]) fr_hash_table_fixup(ht, entry);
514
515 node = list_find(ht, ht->buckets[entry], reversed, data);
516 if (!node) return NULL;
517
518 list_delete(ht, &ht->buckets[entry], node);
519 ht->num_elements--;
520
521 memcpy(&old, &node->data, sizeof(old));
522 free(node);
523
524 return old;
525 }
526
527
528 /*
529 * Delete a piece of data from the hash table.
530 */
fr_hash_table_delete(fr_hash_table_t * ht,void const * data)531 int fr_hash_table_delete(fr_hash_table_t *ht, void const *data)
532 {
533 void *old;
534
535 old = fr_hash_table_yank(ht, data);
536 if (!old) return 0;
537
538 if (ht->free) ht->free(old);
539
540 return 1;
541 }
542
543
544 /*
545 * Free a hash table
546 */
fr_hash_table_free(fr_hash_table_t * ht)547 void fr_hash_table_free(fr_hash_table_t *ht)
548 {
549 int i;
550 fr_hash_entry_t *node, *next;
551
552 if (!ht) return;
553
554 /*
555 * Walk over the buckets, freeing them all.
556 */
557 for (i = 0; i < ht->num_buckets; i++) {
558 if (ht->buckets[i]) for (node = ht->buckets[i];
559 node != &ht->null;
560 node = next) {
561 next = node->next;
562
563 if (node->data && ht->free) {
564 void *tofree;
565 memcpy(&tofree, &node->data, sizeof(tofree));
566 ht->free(tofree);
567 }
568
569 free(node);
570 }
571 }
572
573 free(ht->buckets);
574 free(ht);
575 }
576
577
578 /*
579 * Count number of elements
580 */
fr_hash_table_num_elements(fr_hash_table_t * ht)581 int fr_hash_table_num_elements(fr_hash_table_t *ht)
582 {
583 if (!ht) return 0;
584
585 return ht->num_elements;
586 }
587
588
589 /*
590 * Walk over the nodes, allowing deletes & inserts to happen.
591 */
fr_hash_table_walk(fr_hash_table_t * ht,fr_hash_table_walk_t callback,void * context)592 int fr_hash_table_walk(fr_hash_table_t *ht,
593 fr_hash_table_walk_t callback,
594 void *context)
595 {
596 int i, rcode;
597
598 if (!ht || !callback) return 0;
599
600 for (i = ht->num_buckets - 1; i >= 0; i--) {
601 fr_hash_entry_t *node, *next;
602
603 /*
604 * Ensure that the current bucket is filled.
605 */
606 if (!ht->buckets[i]) fr_hash_table_fixup(ht, i);
607
608 for (node = ht->buckets[i]; node != &ht->null; node = next) {
609 void *arg;
610
611 next = node->next;
612
613 memcpy(&arg, &node->data, sizeof(arg));
614 rcode = callback(context, arg);
615
616 if (rcode != 0) return rcode;
617 }
618 }
619
620 return 0;
621 }
622
623 /** Iterate over entries in a hash table
624 *
625 * @note If the hash table is modified the iterator should be considered invalidated.
626 *
627 * @param[in] ht to iterate over.
628 * @param[in] iter Pointer to an iterator struct, used to maintain
629 * state between calls.
630 * @return
631 * - User data.
632 * - NULL if at the end of the list.
633 */
fr_hash_table_iter_next(fr_hash_table_t * ht,fr_hash_iter_t * iter)634 void *fr_hash_table_iter_next(fr_hash_table_t *ht, fr_hash_iter_t *iter)
635 {
636 fr_hash_entry_t *node;
637 uint32_t i;
638 void *out;
639
640 /*
641 * Return the next element in the bucket
642 */
643 if (iter->node != &ht->null) {
644 node = iter->node;
645 iter->node = node->next;
646
647 memcpy(&out, &node->data, sizeof(out)); /* const issues */
648 return out;
649 }
650
651 if (iter->bucket == 0) return NULL;
652
653 /*
654 * We might have to go through multiple empty
655 * buckets to find one that contains something
656 * we should return
657 */
658 i = iter->bucket - 1;
659 for (;;) {
660 if (!ht->buckets[i]) fr_hash_table_fixup(ht, i);
661
662 node = ht->buckets[i];
663 if (node == &ht->null) {
664 if (i == 0) break;
665 i--;
666 continue; /* This bucket was empty too... */
667 }
668
669 iter->node = node->next; /* Store the next one to examine */
670 iter->bucket = i;
671
672 memcpy(&out, &node->data, sizeof(out)); /* const issues */
673 return out;
674 }
675 iter->bucket = i;
676
677 return NULL;
678 }
679
680 /** Initialise an iterator
681 *
682 * @note If the hash table is modified the iterator should be considered invalidated.
683 *
684 * @param[in] ht to iterate over.
685 * @param[out] iter to initialise.
686 * @return
687 * - The first entry in the hash table.
688 * - NULL if the hash table is empty.
689 */
fr_hash_table_iter_init(fr_hash_table_t * ht,fr_hash_iter_t * iter)690 void *fr_hash_table_iter_init(fr_hash_table_t *ht, fr_hash_iter_t *iter)
691 {
692 iter->bucket = ht->num_buckets;
693 iter->node = &ht->null;
694
695 return fr_hash_table_iter_next(ht, iter);
696 }
697
698
699 #ifdef TESTING
700 /*
701 * Show what the hash table is doing.
702 */
fr_hash_table_info(fr_hash_table_t * ht)703 int fr_hash_table_info(fr_hash_table_t *ht)
704 {
705 int i, a, collisions, uninitialized;
706 int array[256];
707
708 if (!ht) return 0;
709
710 uninitialized = collisions = 0;
711 memset(array, 0, sizeof(array));
712
713 for (i = 0; i < ht->num_buckets; i++) {
714 uint32_t key;
715 int load;
716 fr_hash_entry_t *node, *next;
717
718 /*
719 * If we haven't inserted or looked up an entry
720 * in a bucket, it's uninitialized.
721 */
722 if (!ht->buckets[i]) {
723 uninitialized++;
724 continue;
725 }
726
727 load = 0;
728 key = ~0;
729 for (node = ht->buckets[i]; node != &ht->null; node = next) {
730 if (node->reversed == key) {
731 collisions++;
732 } else {
733 key = node->reversed;
734 }
735 next = node->next;
736 load++;
737 }
738
739 if (load > 255) load = 255;
740 array[load]++;
741 }
742
743 printf("HASH TABLE %p\tbuckets: %d\t(%d uninitialized)\n", ht,
744 ht->num_buckets, uninitialized);
745 printf("\tnum entries %d\thash collisions %d\n",
746 ht->num_elements, collisions);
747
748 a = 0;
749 for (i = 1; i < 256; i++) {
750 if (!array[i]) continue;
751 printf("%d\t%d\n", i, array[i]);
752
753 /*
754 * Since the entries are ordered, the lookup cost
755 * for any one element in a chain is (on average)
756 * the cost of walking half of the chain.
757 */
758 if (i > 1) {
759 a += array[i] * i;
760 }
761 }
762 a /= 2;
763 a += array[1];
764
765 printf("\texpected lookup cost = %d/%d or %f\n\n",
766 ht->num_elements, a,
767 (float) ht->num_elements / (float) a);
768
769 return 0;
770 }
771 #endif
772
773
774 #define FNV_MAGIC_INIT (0x811c9dc5)
775 #define FNV_MAGIC_PRIME (0x01000193)
776
777 /*
778 * A fast hash function. For details, see:
779 *
780 * http://www.isthe.com/chongo/tech/comp/fnv/
781 *
782 * Which also includes public domain source. We've re-written
783 * it here for our purposes.
784 */
fr_hash(void const * data,size_t size)785 uint32_t fr_hash(void const *data, size_t size)
786 {
787 uint8_t const *p = data;
788 uint8_t const *q = p + size;
789 uint32_t hash = FNV_MAGIC_INIT;
790
791 /*
792 * FNV-1 hash each octet in the buffer
793 */
794 while (p != q) {
795 /*
796 * XOR the 8-bit quantity into the bottom of
797 * the hash.
798 */
799 hash ^= (uint32_t) (*p++);
800
801 /*
802 * Multiple by 32-bit magic FNV prime, mod 2^32
803 */
804 hash *= FNV_MAGIC_PRIME;
805 #if 0
806 /*
807 * Potential optimization.
808 */
809 hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
810 #endif
811 }
812
813 return hash;
814 }
815
816 /*
817 * Continue hashing data.
818 */
fr_hash_update(void const * data,size_t size,uint32_t hash)819 uint32_t fr_hash_update(void const *data, size_t size, uint32_t hash)
820 {
821 uint8_t const *p = data;
822 uint8_t const *q = p + size;
823
824 while (p != q) {
825 hash *= FNV_MAGIC_PRIME;
826 hash ^= (uint32_t) (*p++);
827 }
828
829 return hash;
830
831 }
832
833 /*
834 * Hash a C string, so we loop over it once.
835 */
fr_hash_string(char const * p)836 uint32_t fr_hash_string(char const *p)
837 {
838 uint32_t hash = FNV_MAGIC_INIT;
839
840 while (*p) {
841 hash *= FNV_MAGIC_PRIME;
842 hash ^= (uint32_t) (*p++);
843 }
844
845 return hash;
846 }
847
848
849 #ifdef TESTING
850 /*
851 * cc -g -DTESTING -I ../include hash.c -o hash
852 *
853 * ./hash
854 */
hash_int(void const * data)855 static uint32_t hash_int(void const *data)
856 {
857 return fr_hash((int *) data, sizeof(int));
858 }
859
860 #define MAX 1024*1024
main(int argc,char ** argv)861 int main(int argc, char **argv)
862 {
863 int i, *p, *q, k;
864 fr_hash_table_t *ht;
865 int *array;
866
867 ht = fr_hash_table_create(hash_int, NULL, NULL);
868 if (!ht) {
869 fprintf(stderr, "Hash create failed\n");
870 fr_exit(1);
871 }
872
873 array = malloc(sizeof(int) * MAX);
874 if (!array) fr_exit(1);
875
876 for (i = 0; i < MAX; i++) {
877 p = array + i;
878 *p = i;
879
880 if (!fr_hash_table_insert(ht, p)) {
881 fprintf(stderr, "Failed insert %08x\n", i);
882 fr_exit(1);
883 }
884 #ifdef TEST_INSERT
885 q = fr_hash_table_finddata(ht, p);
886 if (q != p) {
887 fprintf(stderr, "Bad data %d\n", i);
888 fr_exit(1);
889 }
890 #endif
891 }
892
893 fr_hash_table_info(ht);
894
895 /*
896 * Build this to see how lookups result in shortening
897 * of the hash chains.
898 */
899 if (1) {
900 for (i = 0; i < MAX ; i++) {
901 q = fr_hash_table_finddata(ht, &i);
902 if (!q || *q != i) {
903 fprintf(stderr, "Failed finding %d\n", i);
904 fr_exit(1);
905 }
906
907 #if 0
908 if (!fr_hash_table_delete(ht, &i)) {
909 fprintf(stderr, "Failed deleting %d\n", i);
910 fr_exit(1);
911 }
912 q = fr_hash_table_finddata(ht, &i);
913 if (q) {
914 fprintf(stderr, "Failed to delete %08x\n", i);
915 fr_exit(1);
916 }
917 #endif
918 }
919
920 fr_hash_table_info(ht);
921 }
922
923 fr_hash_table_free(ht);
924 free(array);
925
926 fr_exit(0);
927 }
928 #endif
929