33 RCSID(
"$Id: 538151ef3bf5ca78be2dd9b4156883f7fc2a10a0 $")
35 #include <freeradius-devel/libradius.h>
41 #define FR_HASH_NUM_BUCKETS (64)
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
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
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]));
164 if (key > 0x00ffffff)
165 return (key & 0x00ffffff) | (parent_byte[key >> 24] << 24);
167 if (key > 0x0000ffff)
168 return (key & 0x0000ffff) | (parent_byte[key >> 16] << 16);
170 if (key > 0x000000ff)
171 return (key & 0x000000ff) | (parent_byte[key >> 8] << 8);
173 return parent_byte[key];
184 for (cur = head; cur != &ht->
null; cur = cur->
next) {
189 if (cmp < 0)
continue;
193 if (cur->
reversed > reversed)
break;
210 for (cur = *head; cur != &ht->
null; cur = cur->
next) {
218 if (cmp < 0)
continue;
241 for (cur = *head; cur != &ht->
null; cur = cur->
next) {
242 if (cur == node)
break;
264 if (!node->
data)
continue;
286 if (!hashNode)
return NULL;
289 if (!ht)
return NULL;
333 uint32_t parent_entry;
341 if (!ht->
buckets[parent_entry]) {
350 last = &ht->
buckets[parent_entry];
353 for (cur = *last; cur != &ht->
null; cur = cur->
next) {
356 real_entry = cur->
key & ht->
mask;
357 if (real_entry !=
this) {
376 #define GROW_FACTOR (2)
386 if (!buckets)
return;
412 if (!ht || !data)
return 0;
414 key = ht->
hash(data);
415 entry = key & ht->
mask;
458 if (!ht)
return NULL;
460 key = ht->
hash(data);
461 entry = key & ht->
mask;
478 if (!ht || !data)
return 0;
484 memcpy(&tofree, &node->
data,
sizeof(tofree));
502 if (!node)
return NULL;
504 memcpy(&out, &node->
data,
sizeof(out));
522 if (!ht)
return NULL;
524 key = ht->
hash(data);
525 entry = key & ht->
mask;
531 if (!node)
return NULL;
536 memcpy(&old, &node->
data,
sizeof(old));
580 if (!node->
data)
continue;
582 memcpy(&tofree, &node->
data,
sizeof(tofree));
615 if (!ht || !callback)
return 0;
625 for (node = ht->
buckets[i]; node != &ht->
null; node = next) {
630 memcpy(&arg, node->
data,
sizeof(arg));
631 rcode = callback(context, arg);
633 if (rcode != 0)
return rcode;
647 int i, a, collisions, uninitialized;
652 uninitialized = collisions = 0;
653 memset(array, 0,
sizeof(array));
671 for (node = ht->
buckets[i]; node != &ht->
null; node = next) {
681 if (load > 255) load = 255;
685 printf(
"HASH TABLE %p\tbuckets: %d\t(%d uninitialized)\n", ht,
687 printf(
"\tnum entries %d\thash collisions %d\n",
691 for (i = 1; i < 256; i++) {
692 if (!array[i])
continue;
693 printf(
"%d\t%d\n", i, array[i]);
707 printf(
"\texpected lookup cost = %d/%d or %f\n\n",
716 #define FNV_MAGIC_INIT (0x811c9dc5)
717 #define FNV_MAGIC_PRIME (0x01000193)
729 uint8_t
const *p =
data;
730 uint8_t
const *q = p + size;
741 hash ^= (uint32_t) (*p++);
751 hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
763 uint8_t
const *p =
data;
764 uint8_t
const *q = p + size;
768 hash ^= (uint32_t) (*p++);
784 hash ^= (uint32_t) (*p++);
797 static uint32_t hash_int(
void const *
data)
799 return fr_hash((
int *) data,
sizeof(
int));
802 #define MAX 1024*1024
803 int main(
int argc,
char **argv)
811 fprintf(stderr,
"Hash create failed\n");
815 array = talloc_zero_array(NULL,
int, MAX);
818 for (i = 0; i < MAX; i++) {
823 fprintf(stderr,
"Failed insert %08x\n", i);
829 fprintf(stderr,
"Bad data %d\n", i);
835 fr_hash_table_info(ht);
842 for (i = 0; i < MAX ; i++) {
845 fprintf(stderr,
"Failed finding %d\n", i);
851 fprintf(stderr,
"Failed deleting %d\n", i);
856 fprintf(stderr,
"Failed to delete %08x\n", i);
862 fr_hash_table_info(ht);
static void fr_hash_table_fixup(fr_hash_table_t *ht, uint32_t entry)
fr_hash_table_hash_t hash
fr_hash_entry_t ** buckets
fr_hash_table_free_t free
uint32_t fr_hash(void const *data, size_t size)
int fr_hash_table_delete(fr_hash_table_t *ht, void const *data)
static void fr_hash_table_grow(fr_hash_table_t *ht)
int fr_hash_table_insert(fr_hash_table_t *ht, void const *data)
static fr_hash_entry_t * list_find(fr_hash_table_t *ht, fr_hash_entry_t *head, uint32_t reversed, void const *data)
void * fr_hash_table_finddata(fr_hash_table_t *ht, void const *data)
static uint8_t parent_byte[256]
static unsigned int hash(char const *username, unsigned int tablesize)
#define FR_HASH_NUM_BUCKETS
int fr_hash_table_num_elements(fr_hash_table_t *ht)
static int _fr_hash_table_free(fr_hash_table_t *ht)
struct fr_hash_entry_t fr_hash_entry_t
void fr_hash_table_free(fr_hash_table_t *ht)
uint32_t(* fr_hash_table_hash_t)(void const *)
static int list_insert(fr_hash_table_t *ht, fr_hash_entry_t **head, fr_hash_entry_t *node)
uint32_t fr_hash_update(void const *data, size_t size, uint32_t hash)
void(* fr_hash_table_free_t)(void *)
int(* fr_hash_table_walk_t)(void *, void *)
int fr_hash_table_walk(fr_hash_table_t *ht, fr_hash_table_walk_t callback, void *context)
static const uint8_t reversed_byte[256]
uint32_t fr_hash_string(char const *p)
static uint32_t parent_of(uint32_t key)
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.
static uint32_t reverse(uint32_t key)
static fr_hash_entry_t * fr_hash_table_find(fr_hash_table_t *ht, void const *data)
struct fr_hash_entry_t * next
int main(int argc, char *argv[])
void * fr_hash_table_yank(fr_hash_table_t *ht, void const *data)
int(* fr_hash_table_cmp_t)(void const *, void const *)
static int list_delete(fr_hash_table_t *ht, fr_hash_entry_t **head, fr_hash_entry_t *node)
int fr_hash_table_replace(fr_hash_table_t *ht, void const *data)
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)