All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
hash.c
Go to the documentation of this file.
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: 538151ef3bf5ca78be2dd9b4156883f7fc2a10a0 $
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: 538151ef3bf5ca78be2dd9b4156883f7fc2a10a0 $")
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 typedef struct fr_hash_entry_t {
45  uint32_t reversed;
46  uint32_t key;
47  void const *data;
49 
50 
53  int num_buckets; /* power of 2 */
54  int next_grow;
55  int mask;
56 
60 
62 
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  */
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  */
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 
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  */
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  */
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 
252 {
253  int i;
254  fr_hash_entry_t *node, *next;
255 
256  /*
257  * Walk over the buckets, freeing them all.
258  */
259  for (i = 0; i < ht->num_buckets; i++) {
260  if (ht->buckets[i]) for (node = ht->buckets[i];
261  node != &ht->null;
262  node = next) {
263  next = node->next;
264  if (!node->data) continue; /* dummy entry */
265 
266  talloc_free(node);
267  }
268  }
269  talloc_free(ht->buckets);
270 
271  return 0;
272 }
273 
274 /*
275  * Create the table.
276  *
277  * Memory usage in bytes is (20/3) * number of entries.
278  */
280  fr_hash_table_hash_t hashNode,
281  fr_hash_table_cmp_t cmpNode,
282  fr_hash_table_free_t freeNode)
283 {
284  fr_hash_table_t *ht;
285 
286  if (!hashNode) return NULL;
287 
288  ht = talloc_zero(NULL, fr_hash_table_t);
289  if (!ht) return NULL;
290  talloc_set_destructor(ht, _fr_hash_table_free);
291  fr_talloc_link_ctx(ctx, ht);
292 
293  ht->free = freeNode;
294  ht->hash = hashNode;
295  ht->cmp = cmpNode;
297  ht->mask = ht->num_buckets - 1;
298 
299  /*
300  * Have a default load factor of 2.5. In practice this
301  * means that the average load will hit 3 before the
302  * table grows.
303  */
304  ht->next_grow = (ht->num_buckets << 1) + (ht->num_buckets >> 1);
305 
306  ht->buckets = talloc_zero_array(NULL, fr_hash_entry_t *, ht->num_buckets);
307  if (!ht->buckets) {
308  talloc_free(ht);
309  return NULL;
310  }
311 
312  ht->null.reversed = ~0;
313  ht->null.key = ~0;
314  ht->null.next = &ht->null;
315  ht->buckets[0] = &ht->null;
316 
317  return ht;
318 }
319 
320 
321 /*
322  * If the current bucket is uninitialized, initialize it
323  * by recursively copying information from the parent.
324  *
325  * We may have a situation where entry E is a parent to 2 other
326  * entries E' and E". If we split E into E and E', then the
327  * nodes meant for E" end up in E or E', either of which is
328  * wrong. To solve that problem, we walk down the whole chain,
329  * inserting the elements into the correct place.
330  */
331 static void fr_hash_table_fixup(fr_hash_table_t *ht, uint32_t entry)
332 {
333  uint32_t parent_entry;
334  fr_hash_entry_t **last, *cur;
335  uint32_t this;
336 
337  parent_entry = parent_of(entry);
338 
339  /* parent_entry == entry if and only if entry == 0 */
340 
341  if (!ht->buckets[parent_entry]) {
342  fr_hash_table_fixup(ht, parent_entry);
343  }
344 
345  /*
346  * Keep walking down cur, trying to find entries that
347  * don't belong here any more. There may be multiple
348  * ones, so we can't have a naive algorithm...
349  */
350  last = &ht->buckets[parent_entry];
351  this = parent_entry;
352 
353  for (cur = *last; cur != &ht->null; cur = cur->next) {
354  uint32_t real_entry;
355 
356  real_entry = cur->key & ht->mask;
357  if (real_entry != this) { /* ht->buckets[real_entry] == NULL */
358  *last = &ht->null;
359  ht->buckets[real_entry] = cur;
360  this = real_entry;
361  }
362 
363  last = &(cur->next);
364  }
365 
366  /*
367  * We may NOT have initialized this bucket, so do it now.
368  */
369  if (!ht->buckets[entry]) ht->buckets[entry] = &ht->null;
370 }
371 
372 /*
373  * This should be a power of two. Changing it to 4 doesn't seem
374  * to make any difference.
375  */
376 #define GROW_FACTOR (2)
377 
378 /*
379  * Grow the hash table.
380  */
382 {
383  fr_hash_entry_t **buckets;
384 
385  buckets = talloc_zero_array(NULL, fr_hash_entry_t *, GROW_FACTOR * ht->num_buckets);
386  if (!buckets) return;
387 
388  memcpy(buckets, ht->buckets, sizeof(*buckets) * ht->num_buckets);
389  talloc_free(ht->buckets); /* Free the old buckets */
390 
391  ht->buckets = buckets;
392  ht->num_buckets *= GROW_FACTOR;
393  ht->next_grow *= GROW_FACTOR;
394  ht->mask = ht->num_buckets - 1;
395 #ifdef TESTING
396  grow = 1;
397  fprintf(stderr, "GROW TO %d\n", ht->num_buckets);
398 #endif
399 }
400 
401 
402 /*
403  * Insert data.
404  */
406 {
407  uint32_t key;
408  uint32_t entry;
409  uint32_t reversed;
410  fr_hash_entry_t *node;
411 
412  if (!ht || !data) return 0;
413 
414  key = ht->hash(data);
415  entry = key & ht->mask;
416  reversed = reverse(key);
417 
418  if (!ht->buckets[entry]) fr_hash_table_fixup(ht, entry);
419 
420  /*
421  * If we try to do our own memory allocation here, the
422  * speedup is only ~15% or so, which isn't worth it.
423  */
424  node = talloc_zero(NULL, fr_hash_entry_t);
425  if (!node) return 0;
426 
427  node->next = &ht->null;
428  node->reversed = reversed;
429  node->key = key;
430  node->data = data;
431 
432  /* already in the table, can't insert it */
433  if (!list_insert(ht, &ht->buckets[entry], node)) {
434  talloc_free(node);
435  return 0;
436  }
437 
438  /*
439  * Check the load factor, and grow the table if
440  * necessary.
441  */
442  ht->num_elements++;
443  if (ht->num_elements >= ht->next_grow) fr_hash_table_grow(ht);
444 
445  return 1;
446 }
447 
448 
449 /*
450  * Internal find a node routine.
451  */
453 {
454  uint32_t key;
455  uint32_t entry;
456  uint32_t reversed;
457 
458  if (!ht) return NULL;
459 
460  key = ht->hash(data);
461  entry = key & ht->mask;
462  reversed = reverse(key);
463 
464  if (!ht->buckets[entry]) fr_hash_table_fixup(ht, entry);
465 
466  return list_find(ht, ht->buckets[entry], reversed, data);
467 }
468 
469 
470 /*
471  * Replace old data with new data, OR insert if there is no old.
472  */
474 {
475  fr_hash_entry_t *node;
476  void *tofree;
477 
478  if (!ht || !data) return 0;
479 
480  node = fr_hash_table_find(ht, data);
481  if (!node) return fr_hash_table_insert(ht, data);
482 
483  if (ht->free) {
484  memcpy(&tofree, &node->data, sizeof(tofree));
485  ht->free(tofree);
486  }
487  node->data = data;
488 
489  return 1;
490 }
491 
492 
493 /*
494  * Find data from a template
495  */
497 {
498  fr_hash_entry_t *node;
499  void *out;
500 
501  node = fr_hash_table_find(ht, data);
502  if (!node) return NULL;
503 
504  memcpy(&out, &node->data, sizeof(out));
505 
506  return out;
507 }
508 
509 
510 
511 /*
512  * Yank an entry from the hash table, without freeing the data.
513  */
514 void *fr_hash_table_yank(fr_hash_table_t *ht, void const *data)
515 {
516  uint32_t key;
517  uint32_t entry;
518  uint32_t reversed;
519  void *old;
520  fr_hash_entry_t *node;
521 
522  if (!ht) return NULL;
523 
524  key = ht->hash(data);
525  entry = key & ht->mask;
526  reversed = reverse(key);
527 
528  if (!ht->buckets[entry]) fr_hash_table_fixup(ht, entry);
529 
530  node = list_find(ht, ht->buckets[entry], reversed, data);
531  if (!node) return NULL;
532 
533  list_delete(ht, &ht->buckets[entry], node);
534  ht->num_elements--;
535 
536  memcpy(&old, &node->data, sizeof(old));
537  talloc_free(node);
538 
539  return old;
540 }
541 
542 
543 /*
544  * Delete a piece of data from the hash table.
545  */
547 {
548  void *old;
549 
550  old = fr_hash_table_yank(ht, data);
551  if (!old) return 0;
552 
553  if (ht->free) ht->free(old);
554 
555  return 1;
556 }
557 
558 
559 /*
560  * Free a hash table
561  */
563 {
564  int i;
565  fr_hash_entry_t *node, *next;
566 
567  if (!ht) return;
568 
569  /*
570  * Walk over the buckets, freeing them all.
571  */
572  if (ht->free) {
573  for (i = 0; i < ht->num_buckets; i++) {
574  if (ht->buckets[i]) for (node = ht->buckets[i];
575  node != &ht->null;
576  node = next) {
577  void *tofree;
578 
579  next = node->next;
580  if (!node->data) continue; /* dummy entry */
581 
582  memcpy(&tofree, &node->data, sizeof(tofree));
583  ht->free(tofree);
584  }
585  }
586  }
587 
588  /*
589  * Also frees nodes and buckets
590  */
591  talloc_free(ht);
592 }
593 
594 
595 /*
596  * Count number of elements
597  */
599 {
600  if (!ht) return 0;
601 
602  return ht->num_elements;
603 }
604 
605 
606 /*
607  * Walk over the nodes, allowing deletes & inserts to happen.
608  */
610  fr_hash_table_walk_t callback,
611  void *context)
612 {
613  int i, rcode;
614 
615  if (!ht || !callback) return 0;
616 
617  for (i = ht->num_buckets - 1; i >= 0; i--) {
618  fr_hash_entry_t *node, *next;
619 
620  /*
621  * Ensure that the current bucket is filled.
622  */
623  if (!ht->buckets[i]) fr_hash_table_fixup(ht, i);
624 
625  for (node = ht->buckets[i]; node != &ht->null; node = next) {
626  void *arg;
627 
628  next = node->next;
629 
630  memcpy(&arg, node->data, sizeof(arg));
631  rcode = callback(context, arg);
632 
633  if (rcode != 0) return rcode;
634  }
635  }
636 
637  return 0;
638 }
639 
640 
641 #ifdef TESTING
642 /*
643  * Show what the hash table is doing.
644  */
645 int fr_hash_table_info(fr_hash_table_t *ht)
646 {
647  int i, a, collisions, uninitialized;
648  int array[256];
649 
650  if (!ht) return 0;
651 
652  uninitialized = collisions = 0;
653  memset(array, 0, sizeof(array));
654 
655  for (i = 0; i < ht->num_buckets; i++) {
656  uint32_t key;
657  int load;
658  fr_hash_entry_t *node, *next;
659 
660  /*
661  * If we haven't inserted or looked up an entry
662  * in a bucket, it's uninitialized.
663  */
664  if (!ht->buckets[i]) {
665  uninitialized++;
666  continue;
667  }
668 
669  load = 0;
670  key = ~0;
671  for (node = ht->buckets[i]; node != &ht->null; node = next) {
672  if (node->reversed == key) {
673  collisions++;
674  } else {
675  key = node->reversed;
676  }
677  next = node->next;
678  load++;
679  }
680 
681  if (load > 255) load = 255;
682  array[load]++;
683  }
684 
685  printf("HASH TABLE %p\tbuckets: %d\t(%d uninitialized)\n", ht,
686  ht->num_buckets, uninitialized);
687  printf("\tnum entries %d\thash collisions %d\n",
688  ht->num_elements, collisions);
689 
690  a = 0;
691  for (i = 1; i < 256; i++) {
692  if (!array[i]) continue;
693  printf("%d\t%d\n", i, array[i]);
694 
695  /*
696  * Since the entries are ordered, the lookup cost
697  * for any one element in a chain is (on average)
698  * the cost of walking half of the chain.
699  */
700  if (i > 1) {
701  a += array[i] * i;
702  }
703  }
704  a /= 2;
705  a += array[1];
706 
707  printf("\texpected lookup cost = %d/%d or %f\n\n",
708  ht->num_elements, a,
709  (float) ht->num_elements / (float) a);
710 
711  return 0;
712 }
713 #endif
714 
715 
716 #define FNV_MAGIC_INIT (0x811c9dc5)
717 #define FNV_MAGIC_PRIME (0x01000193)
718 
719 /*
720  * A fast hash function. For details, see:
721  *
722  * http://www.isthe.com/chongo/tech/comp/fnv/
723  *
724  * Which also includes public domain source. We've re-written
725  * it here for our purposes.
726  */
727 uint32_t fr_hash(void const *data, size_t size)
728 {
729  uint8_t const *p = data;
730  uint8_t const *q = p + size;
731  uint32_t hash = FNV_MAGIC_INIT;
732 
733  /*
734  * FNV-1 hash each octet in the buffer
735  */
736  while (p != q) {
737  /*
738  * XOR the 8-bit quantity into the bottom of
739  * the hash.
740  */
741  hash ^= (uint32_t) (*p++);
742 
743  /*
744  * Multiple by 32-bit magic FNV prime, mod 2^32
745  */
746  hash *= FNV_MAGIC_PRIME;
747 #if 0
748  /*
749  * Potential optimization.
750  */
751  hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
752 #endif
753  }
754 
755  return hash;
756 }
757 
758 /*
759  * Continue hashing data.
760  */
761 uint32_t fr_hash_update(void const *data, size_t size, uint32_t hash)
762 {
763  uint8_t const *p = data;
764  uint8_t const *q = p + size;
765 
766  while (p != q) {
767  hash *= FNV_MAGIC_PRIME;
768  hash ^= (uint32_t) (*p++);
769  }
770 
771  return hash;
772 
773 }
774 
775 /*
776  * Hash a C string, so we loop over it once.
777  */
778 uint32_t fr_hash_string(char const *p)
779 {
780  uint32_t hash = FNV_MAGIC_INIT;
781 
782  while (*p) {
783  hash *= FNV_MAGIC_PRIME;
784  hash ^= (uint32_t) (*p++);
785  }
786 
787  return hash;
788 }
789 
790 
791 #ifdef TESTING
792 /*
793  * cc -g -DTESTING -I ../include hash.c -o hash
794  *
795  * ./hash
796  */
797 static uint32_t hash_int(void const *data)
798 {
799  return fr_hash((int *) data, sizeof(int));
800 }
801 
802 #define MAX 1024*1024
803 int main(int argc, char **argv)
804 {
805  int i, *p, *q, k;
806  fr_hash_table_t *ht;
807  int *array;
808 
809  ht = fr_hash_table_create(NULL, hash_int, NULL, NULL);
810  if (!ht) {
811  fprintf(stderr, "Hash create failed\n");
812  fr_exit(1);
813  }
814 
815  array = talloc_zero_array(NULL, int, MAX);
816  if (!array) fr_exit(1);
817 
818  for (i = 0; i < MAX; i++) {
819  p = array + i;
820  *p = i;
821 
822  if (!fr_hash_table_insert(ht, p)) {
823  fprintf(stderr, "Failed insert %08x\n", i);
824  fr_exit(1);
825  }
826 #ifdef TEST_INSERT
827  q = fr_hash_table_finddata(ht, p);
828  if (q != p) {
829  fprintf(stderr, "Bad data %d\n", i);
830  fr_exit(1);
831  }
832 #endif
833  }
834 
835  fr_hash_table_info(ht);
836 
837  /*
838  * Build this to see how lookups result in shortening
839  * of the hash chains.
840  */
841  if (1) {
842  for (i = 0; i < MAX ; i++) {
843  q = fr_hash_table_finddata(ht, &i);
844  if (!q || *q != i) {
845  fprintf(stderr, "Failed finding %d\n", i);
846  fr_exit(1);
847  }
848 
849 #if 0
850  if (!fr_hash_table_delete(ht, &i)) {
851  fprintf(stderr, "Failed deleting %d\n", i);
852  fr_exit(1);
853  }
854  q = fr_hash_table_finddata(ht, &i);
855  if (q) {
856  fprintf(stderr, "Failed to delete %08x\n", i);
857  fr_exit(1);
858  }
859 #endif
860  }
861 
862  fr_hash_table_info(ht);
863  }
864 
865  fr_hash_table_free(ht);
866  talloc_free(array);
867 
868  fr_exit(0);
869 }
870 #endif
static void fr_hash_table_fixup(fr_hash_table_t *ht, uint32_t entry)
Definition: hash.c:331
Definition: hash.c:43
#define GROW_FACTOR
Definition: hash.c:376
fr_hash_table_hash_t hash
Definition: hash.c:58
fr_hash_entry_t ** buckets
Definition: hash.c:63
fr_hash_table_free_t free
Definition: hash.c:57
int num_elements
Definition: hash.c:52
int mask
Definition: hash.c:55
uint32_t key
Definition: hash.c:46
uint32_t fr_hash(void const *data, size_t size)
Definition: hash.c:727
int fr_hash_table_delete(fr_hash_table_t *ht, void const *data)
Definition: hash.c:546
fr_hash_table_cmp_t cmp
Definition: hash.c:59
static void fr_hash_table_grow(fr_hash_table_t *ht)
Definition: hash.c:381
#define FNV_MAGIC_INIT
Definition: hash.c:716
int fr_hash_table_insert(fr_hash_table_t *ht, void const *data)
Definition: hash.c:405
static fr_hash_entry_t * list_find(fr_hash_table_t *ht, fr_hash_entry_t *head, uint32_t reversed, void const *data)
Definition: hash.c:177
void * fr_hash_table_finddata(fr_hash_table_t *ht, void const *data)
Definition: hash.c:496
static uint8_t parent_byte[256]
Definition: hash.c:112
static unsigned int hash(char const *username, unsigned int tablesize)
Definition: rlm_passwd.c:124
#define FR_HASH_NUM_BUCKETS
Definition: hash.c:41
int fr_hash_table_num_elements(fr_hash_table_t *ht)
Definition: hash.c:598
static int _fr_hash_table_free(fr_hash_table_t *ht)
Definition: hash.c:251
struct fr_hash_entry_t fr_hash_entry_t
void fr_hash_table_free(fr_hash_table_t *ht)
Definition: hash.c:562
uint32_t(* fr_hash_table_hash_t)(void const *)
Definition: hash.h:42
static int list_insert(fr_hash_table_t *ht, fr_hash_entry_t **head, fr_hash_entry_t *node)
Definition: hash.c:203
fr_hash_entry_t null
Definition: hash.c:61
uint32_t fr_hash_update(void const *data, size_t size, uint32_t hash)
Definition: hash.c:761
void(* fr_hash_table_free_t)(void *)
Definition: hash.h:41
int(* fr_hash_table_walk_t)(void *, void *)
Definition: hash.h:44
int fr_hash_table_walk(fr_hash_table_t *ht, fr_hash_table_walk_t callback, void *context)
Definition: hash.c:609
uint8_t data[]
Definition: eap_pwd.h:625
static const uint8_t reversed_byte[256]
Definition: hash.c:73
int next_grow
Definition: hash.c:54
uint32_t fr_hash_string(char const *p)
Definition: hash.c:778
#define FNV_MAGIC_PRIME
Definition: hash.c:717
static uint32_t parent_of(uint32_t key)
Definition: hash.c:162
int fr_talloc_link_ctx(TALLOC_CTX *parent, TALLOC_CTX *child)
Link a parent and a child context, so the child is freed before the parent.
Definition: misc.c:105
static uint32_t reverse(uint32_t key)
Definition: hash.c:151
static fr_hash_entry_t * fr_hash_table_find(fr_hash_table_t *ht, void const *data)
Definition: hash.c:452
struct fr_hash_entry_t * next
Definition: hash.c:44
int main(int argc, char *argv[])
Definition: radattr.c:959
int num_buckets
Definition: hash.c:53
void * fr_hash_table_yank(fr_hash_table_t *ht, void const *data)
Definition: hash.c:514
Definition: pair.c:37
int(* fr_hash_table_cmp_t)(void const *, void const *)
Definition: hash.h:43
uint32_t reversed
Definition: hash.c:45
#define RCSID(id)
Definition: build.h:135
static int list_delete(fr_hash_table_t *ht, fr_hash_entry_t **head, fr_hash_entry_t *node)
Definition: hash.c:234
void const * data
Definition: hash.c:47
#define fr_exit(_x)
Definition: libradius.h:508
int fr_hash_table_replace(fr_hash_table_t *ht, void const *data)
Definition: hash.c:473
fr_hash_table_t * fr_hash_table_create(TALLOC_CTX *ctx, fr_hash_table_hash_t hashNode, fr_hash_table_cmp_t cmpNode, fr_hash_table_free_t freeNode)
Definition: hash.c:279