33 RCSID(
"$Id: 6ceeaa4f74ea379d554b8766ffd61b568af676d3 $")
35 #include <freeradius-devel/util/hash.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
171 if (key > 0x00ffffff)
172 return (key & 0x00ffffff) | (
parent_byte[key >> 24] << 24);
174 if (key > 0x0000ffff)
175 return (key & 0x0000ffff) | (
parent_byte[key >> 16] << 16);
177 if (key > 0x000000ff)
178 return (key & 0x000000ff) | (
parent_byte[key >> 8] << 8);
194 if (cmp < 0)
continue;
198 if (cur->
reversed > reversed)
break;
223 if (cmp < 0)
continue;
247 if (cur == node)
break;
265 if (!node->
data)
continue;
289 if (!ht)
return NULL;
342 if (!ht->
buckets[parent_entry]) {
351 last = &ht->
buckets[parent_entry];
354 for (cur = *last; cur != &ht->
null; cur = cur->
next) {
357 real_entry = cur->
key & ht->
mask;
358 if (real_entry !=
this) {
377 #define GROW_FACTOR (2)
385 size_t existing = talloc_get_size(ht->
buckets);
388 if (!buckets)
return;
390 memset(((
uint8_t *)buckets) + existing, 0, talloc_get_size(buckets) - existing);
411 entry = key & ht->
mask;
433 if (!node)
return NULL;
452 if (!node)
return NULL;
473 #ifndef TALLOC_GET_TYPE_ABORT_NOOP
474 if (ht->
type) (void)_talloc_get_type_abort(
data, ht->
type, __location__);
478 entry = key & ht->
mask;
531 if (old) *old = NULL;
537 }
else if (ht->
free) {
564 entry = key & ht->
mask;
570 if (!node)
return NULL;
594 if (!old)
return false;
635 if (iter->
bucket == 0)
return NULL;
647 if (node == &ht->
null) {
695 if (
unlikely(!(list = talloc_array(ctx,
void *, num))))
return -1;
726 int i, a, collisions, uninitialized;
731 uninitialized = collisions = 0;
750 for (node = ht->
buckets[i]; node != &ht->
null; node = next) {
764 printf(
"HASH TABLE %p\tbuckets: %d\t(%d uninitialized)\n", ht,
766 printf(
"\tnum entries %d\thash collisions %d\n",
770 for (i = 1; i < 256; i++) {
771 if (!
array[i])
continue;
772 printf(
"%d\t%d\n", i,
array[i]);
786 printf(
"\texpected lookup cost = %d/%d or %f\n\n",
795 #define FNV_MAGIC_INIT (0x811c9dc5)
796 #define FNV_MAGIC_PRIME (0x01000193)
845 if (size == 0)
return hash;
906 (void)_talloc_get_type_abort(ptr, ht->
type, __location__);
922 #define MAX 1024*1024
923 int main(
int argc,
char **argv)
931 fprintf(stderr,
"Hash create failed\n");
935 array = talloc_zero_array(NULL,
int, MAX);
938 for (i = 0; i < MAX; i++) {
943 fprintf(stderr,
"Failed insert %08x\n", i);
949 fprintf(stderr,
"Bad data %d\n", i);
955 fr_hash_table_info(ht);
962 for (i = 0; i < MAX ; i++) {
965 fprintf(stderr,
"Failed finding %d\n", i);
971 fprintf(stderr,
"Failed deleting %d\n", i);
976 fprintf(stderr,
"Failed to delete %08x\n", i);
982 fr_hash_table_info(ht);
985 fr_hash_table_free(ht);
#define UNCONST(_type, _ptr)
Remove const qualification from a pointer.
#define fr_exit(_x)
Exit, producing a log message in debug builds.
int main(int argc, char **argv)
void * fr_hash_table_iter_init(fr_hash_table_t *ht, fr_hash_iter_t *iter)
Initialise an iterator.
fr_hash_entry_t ** buckets
Array of hash buckets.
void * fr_hash_table_iter_next(fr_hash_table_t *ht, fr_hash_iter_t *iter)
Iterate over entries in a hash table.
char const * type
Talloc type to check elements against.
void * fr_hash_table_remove(fr_hash_table_t *ht, void const *data)
Remove an entry from the hash table, without freeing the data.
void * fr_hash_table_find(fr_hash_table_t *ht, void const *data)
Find data in a hash table.
static fr_hash_entry_t * list_find(fr_hash_table_t *ht, fr_hash_entry_t *head, uint32_t reversed, void const *data)
uint32_t fr_hash_case_string(char const *p)
Hash a C string, converting all chars to lowercase.
static int _fr_hash_table_free(fr_hash_table_t *ht)
fr_hash_table_t * _fr_hash_table_alloc(TALLOC_CTX *ctx, char const *type, fr_hash_t hash_func, fr_cmp_t cmp_func, fr_free_t free_func)
uint32_t fr_hash_update(void const *data, size_t size, uint32_t hash)
static uint8_t parent_byte[256]
uint32_t fr_hash(void const *data, size_t size)
bool fr_hash_table_insert(fr_hash_table_t *ht, void const *data)
Insert data into a hash table.
fr_hash_t hash
Hashing function.
static uint32_t parent_of(uint32_t key)
fr_cmp_t cmp
Comparison function.
static const uint8_t reversed_byte[256]
uint32_t num_buckets
Number of buckets (how long the array is) - power of 2 */.
int fr_hash_table_flatten(TALLOC_CTX *ctx, void **out[], fr_hash_table_t *ht)
Copy all entries out of a hash table into an array.
static void list_delete(fr_hash_table_t *ht, fr_hash_entry_t **head, fr_hash_entry_t *node)
static uint32_t reverse(uint32_t key)
uint32_t num_elements
Number of elements in the hash table.
uint32_t fr_hash_string(char const *p)
bool fr_hash_table_delete(fr_hash_table_t *ht, void const *data)
Remove and free data (if a free function was specified)
void fr_hash_table_verify(fr_hash_table_t *ht)
Check hash table is sane.
fr_free_t free
Data free function.
static fr_hash_entry_t * hash_table_find(fr_hash_table_t *ht, uint32_t key, void const *data)
static bool list_insert(fr_hash_table_t *ht, fr_hash_entry_t **head, fr_hash_entry_t *node)
void fr_hash_table_fill(fr_hash_table_t *ht)
Ensure all buckets are filled.
static void fr_hash_table_fixup(fr_hash_table_t *ht, uint32_t entry)
void * fr_hash_table_find_by_key(fr_hash_table_t *ht, uint32_t key, void const *data)
Hash table lookup with pre-computed key.
int fr_hash_table_replace(void **old, fr_hash_table_t *ht, void const *data)
Replace old data with new data, OR insert if there is no old.
uint32_t fr_hash_table_num_elements(fr_hash_table_t *ht)
#define FR_HASH_NUM_BUCKETS
static void fr_hash_table_grow(fr_hash_table_t *ht)
struct fr_hash_table_s fr_hash_table_t
uint32_t(* fr_hash_t)(void const *)
#define fr_hash_table_alloc(_ctx, _hash_node, _cmp_node, _free_node)
Stores the state of the current iteration operation.
static void * item(fr_lst_t const *lst, fr_lst_index_t idx)
static size_t array[MY_ARRAY_SIZE]
int8_t(* fr_cmp_t)(void const *a, void const *b)
void(* fr_free_t)(void *)
static unsigned int hash(char const *username, unsigned int tablesize)
fr_aka_sim_id_type_t type
static size_t char ** out