summaryrefslogtreecommitdiffstats
path: root/src/lib/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/hash.c')
-rw-r--r--src/lib/hash.c928
1 files changed, 928 insertions, 0 deletions
diff --git a/src/lib/hash.c b/src/lib/hash.c
new file mode 100644
index 0000000..f9d0881
--- /dev/null
+++ b/src/lib/hash.c
@@ -0,0 +1,928 @@
+/*
+ * hash.c Non-thread-safe split-ordered hash table.
+ *
+ * The weird "reverse" function is based on an idea from
+ * "Split-Ordered Lists - Lock-free Resizable Hash Tables", with
+ * modifications so that they're not lock-free. :(
+ *
+ * However, the split-order idea allows a fast & easy splitting of the
+ * hash bucket chain when the hash table is resized. Without it, we'd
+ * have to check & update the pointers for every node in the buck chain,
+ * rather than being able to move 1/2 of the entries in the chain with
+ * one update.
+ *
+ * Version: $Id$
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
+ *
+ * Copyright 2005,2006 The FreeRADIUS server project
+ */
+
+RCSID("$Id$")
+
+#include <freeradius-devel/libradius.h>
+
+/*
+ * A reasonable number of buckets to start off with.
+ * Should be a power of two.
+ */
+#define FR_HASH_NUM_BUCKETS (64)
+
+struct fr_hash_entry_s {
+ fr_hash_entry_t *next;
+ uint32_t reversed;
+ uint32_t key;
+ void const *data;
+};
+
+
+struct fr_hash_table_t {
+ int num_elements;
+ int num_buckets; /* power of 2 */
+ int next_grow;
+ int mask;
+
+ fr_hash_table_free_t free;
+ fr_hash_table_hash_t hash;
+ fr_hash_table_cmp_t cmp;
+
+ fr_hash_entry_t null;
+
+ fr_hash_entry_t **buckets;
+};
+
+#ifdef TESTING
+static int grow = 0;
+#endif
+
+/*
+ * 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";}}'
+ */
+static const uint8_t reversed_byte[256] = {
+ 0, 128, 64, 192, 32, 160, 96, 224,
+ 16, 144, 80, 208, 48, 176, 112, 240,
+ 8, 136, 72, 200, 40, 168, 104, 232,
+ 24, 152, 88, 216, 56, 184, 120, 248,
+ 4, 132, 68, 196, 36, 164, 100, 228,
+ 20, 148, 84, 212, 52, 180, 116, 244,
+ 12, 140, 76, 204, 44, 172, 108, 236,
+ 28, 156, 92, 220, 60, 188, 124, 252,
+ 2, 130, 66, 194, 34, 162, 98, 226,
+ 18, 146, 82, 210, 50, 178, 114, 242,
+ 10, 138, 74, 202, 42, 170, 106, 234,
+ 26, 154, 90, 218, 58, 186, 122, 250,
+ 6, 134, 70, 198, 38, 166, 102, 230,
+ 22, 150, 86, 214, 54, 182, 118, 246,
+ 14, 142, 78, 206, 46, 174, 110, 238,
+ 30, 158, 94, 222, 62, 190, 126, 254,
+ 1, 129, 65, 193, 33, 161, 97, 225,
+ 17, 145, 81, 209, 49, 177, 113, 241,
+ 9, 137, 73, 201, 41, 169, 105, 233,
+ 25, 153, 89, 217, 57, 185, 121, 249,
+ 5, 133, 69, 197, 37, 165, 101, 229,
+ 21, 149, 85, 213, 53, 181, 117, 245,
+ 13, 141, 77, 205, 45, 173, 109, 237,
+ 29, 157, 93, 221, 61, 189, 125, 253,
+ 3, 131, 67, 195, 35, 163, 99, 227,
+ 19, 147, 83, 211, 51, 179, 115, 243,
+ 11, 139, 75, 203, 43, 171, 107, 235,
+ 27, 155, 91, 219, 59, 187, 123, 251,
+ 7, 135, 71, 199, 39, 167, 103, 231,
+ 23, 151, 87, 215, 55, 183, 119, 247,
+ 15, 143, 79, 207, 47, 175, 111, 239,
+ 31, 159, 95, 223, 63, 191, 127, 255
+};
+
+
+/*
+ * 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";}}'
+ */
+static uint8_t parent_byte[256] = {
+ 0, 0, 0, 1, 0, 1, 2, 3,
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 8, 9, 10, 11, 12, 13, 14, 15,
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 8, 9, 10, 11, 12, 13, 14, 15,
+ 16, 17, 18, 19, 20, 21, 22, 23,
+ 24, 25, 26, 27, 28, 29, 30, 31,
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 8, 9, 10, 11, 12, 13, 14, 15,
+ 16, 17, 18, 19, 20, 21, 22, 23,
+ 24, 25, 26, 27, 28, 29, 30, 31,
+ 32, 33, 34, 35, 36, 37, 38, 39,
+ 40, 41, 42, 43, 44, 45, 46, 47,
+ 48, 49, 50, 51, 52, 53, 54, 55,
+ 56, 57, 58, 59, 60, 61, 62, 63,
+ 0, 1, 2, 3, 4, 5, 6, 7,
+ 8, 9, 10, 11, 12, 13, 14, 15,
+ 16, 17, 18, 19, 20, 21, 22, 23,
+ 24, 25, 26, 27, 28, 29, 30, 31,
+ 32, 33, 34, 35, 36, 37, 38, 39,
+ 40, 41, 42, 43, 44, 45, 46, 47,
+ 48, 49, 50, 51, 52, 53, 54, 55,
+ 56, 57, 58, 59, 60, 61, 62, 63,
+ 64, 65, 66, 67, 68, 69, 70, 71,
+ 72, 73, 74, 75, 76, 77, 78, 79,
+ 80, 81, 82, 83, 84, 85, 86, 87,
+ 88, 89, 90, 91, 92, 93, 94, 95,
+ 96, 97, 98, 99, 100, 101, 102, 103,
+ 104, 105, 106, 107, 108, 109, 110, 111,
+ 112, 113, 114, 115, 116, 117, 118, 119,
+ 120, 121, 122, 123, 124, 125, 126, 127
+};
+
+
+/*
+ * Reverse a key.
+ */
+static uint32_t reverse(uint32_t key)
+{
+ return ((reversed_byte[key & 0xff] << 24) |
+ (reversed_byte[(key >> 8) & 0xff] << 16) |
+ (reversed_byte[(key >> 16) & 0xff] << 8) |
+ (reversed_byte[(key >> 24) & 0xff]));
+}
+
+/*
+ * Take the parent by discarding the highest bit that is set.
+ */
+static uint32_t parent_of(uint32_t key)
+{
+ if (key > 0x00ffffff)
+ return (key & 0x00ffffff) | (parent_byte[key >> 24] << 24);
+
+ if (key > 0x0000ffff)
+ return (key & 0x0000ffff) | (parent_byte[key >> 16] << 16);
+
+ if (key > 0x000000ff)
+ return (key & 0x000000ff) | (parent_byte[key >> 8] << 8);
+
+ return parent_byte[key];
+}
+
+
+static fr_hash_entry_t *list_find(fr_hash_table_t *ht,
+ fr_hash_entry_t *head,
+ uint32_t reversed,
+ void const *data)
+{
+ fr_hash_entry_t *cur;
+
+ for (cur = head; cur != &ht->null; cur = cur->next) {
+ if (cur->reversed == reversed) {
+ if (ht->cmp) {
+ int cmp = ht->cmp(data, cur->data);
+ if (cmp > 0) break;
+ if (cmp < 0) continue;
+ }
+ return cur;
+ }
+ if (cur->reversed > reversed) break;
+ }
+
+ return NULL;
+}
+
+
+/*
+ * Inserts a new entry into the list, in order.
+ */
+static int list_insert(fr_hash_table_t *ht,
+ fr_hash_entry_t **head, fr_hash_entry_t *node)
+{
+ fr_hash_entry_t **last, *cur;
+
+ last = head;
+
+ for (cur = *head; cur != &ht->null; cur = cur->next) {
+ if (cur->reversed > node->reversed) break;
+ last = &(cur->next);
+
+ if (cur->reversed == node->reversed) {
+ if (ht->cmp) {
+ int cmp = ht->cmp(node->data, cur->data);
+ if (cmp > 0) break;
+ if (cmp < 0) continue;
+ }
+ return 0;
+ }
+ }
+
+ node->next = *last;
+ *last = node;
+
+ return 1;
+}
+
+
+/*
+ * Delete an entry from the list.
+ */
+static int list_delete(fr_hash_table_t *ht,
+ fr_hash_entry_t **head, fr_hash_entry_t *node)
+{
+ fr_hash_entry_t **last, *cur;
+
+ last = head;
+
+ for (cur = *head; cur != &ht->null; cur = cur->next) {
+ if (cur == node) break;
+ last = &(cur->next);
+ }
+
+ *last = node->next;
+ return 1;
+}
+
+
+/*
+ * Create the table.
+ *
+ * Memory usage in bytes is (20/3) * number of entries.
+ */
+fr_hash_table_t *fr_hash_table_create(fr_hash_table_hash_t hashNode,
+ fr_hash_table_cmp_t cmpNode,
+ fr_hash_table_free_t freeNode)
+{
+ fr_hash_table_t *ht;
+
+ if (!hashNode) return NULL;
+
+ ht = malloc(sizeof(*ht));
+ if (!ht) return NULL;
+
+ memset(ht, 0, sizeof(*ht));
+ ht->free = freeNode;
+ ht->hash = hashNode;
+ ht->cmp = cmpNode;
+ ht->num_buckets = FR_HASH_NUM_BUCKETS;
+ ht->mask = ht->num_buckets - 1;
+
+ /*
+ * Have a default load factor of 2.5. In practice this
+ * means that the average load will hit 3 before the
+ * table grows.
+ */
+ ht->next_grow = (ht->num_buckets << 1) + (ht->num_buckets >> 1);
+
+ ht->buckets = malloc(sizeof(*ht->buckets) * ht->num_buckets);
+ if (!ht->buckets) {
+ free(ht);
+ return NULL;
+ }
+ memset(ht->buckets, 0, sizeof(*ht->buckets) * ht->num_buckets);
+
+ ht->null.reversed = ~0;
+ ht->null.key = ~0;
+ ht->null.next = &ht->null;
+
+ ht->buckets[0] = &ht->null;
+
+ return ht;
+}
+
+
+/*
+ * If the current bucket is uninitialized, initialize it
+ * by recursively copying information from the parent.
+ *
+ * We may have a situation where entry E is a parent to 2 other
+ * entries E' and E". If we split E into E and E', then the
+ * nodes meant for E" end up in E or E', either of which is
+ * wrong. To solve that problem, we walk down the whole chain,
+ * inserting the elements into the correct place.
+ */
+static void fr_hash_table_fixup(fr_hash_table_t *ht, uint32_t entry)
+{
+ uint32_t parent_entry;
+ fr_hash_entry_t **last, *cur;
+ uint32_t this;
+
+ parent_entry = parent_of(entry);
+
+ /* parent_entry == entry if and only if entry == 0 */
+
+ if (!ht->buckets[parent_entry]) {
+ fr_hash_table_fixup(ht, parent_entry);
+ }
+
+ /*
+ * Keep walking down cur, trying to find entries that
+ * don't belong here any more. There may be multiple
+ * ones, so we can't have a naive algorithm...
+ */
+ last = &ht->buckets[parent_entry];
+ this = parent_entry;
+
+ for (cur = *last; cur != &ht->null; cur = cur->next) {
+ uint32_t real_entry;
+
+ real_entry = cur->key & ht->mask;
+ if (real_entry != this) { /* ht->buckets[real_entry] == NULL */
+ *last = &ht->null;
+ ht->buckets[real_entry] = cur;
+ this = real_entry;
+ }
+
+ last = &(cur->next);
+ }
+
+ /*
+ * We may NOT have initialized this bucket, so do it now.
+ */
+ if (!ht->buckets[entry]) ht->buckets[entry] = &ht->null;
+}
+
+/*
+ * This should be a power of two. Changing it to 4 doesn't seem
+ * to make any difference.
+ */
+#define GROW_FACTOR (2)
+
+/*
+ * Grow the hash table.
+ */
+static void fr_hash_table_grow(fr_hash_table_t *ht)
+{
+ fr_hash_entry_t **buckets;
+
+ buckets = malloc(sizeof(*buckets) * GROW_FACTOR * ht->num_buckets);
+ if (!buckets) return;
+
+ memcpy(buckets, ht->buckets,
+ sizeof(*buckets) * ht->num_buckets);
+ memset(&buckets[ht->num_buckets], 0,
+ sizeof(*buckets) * ht->num_buckets);
+
+ free(ht->buckets);
+ ht->buckets = buckets;
+ ht->num_buckets *= GROW_FACTOR;
+ ht->next_grow *= GROW_FACTOR;
+ ht->mask = ht->num_buckets - 1;
+#ifdef TESTING
+ grow = 1;
+ fprintf(stderr, "GROW TO %d\n", ht->num_buckets);
+#endif
+}
+
+
+/*
+ * Insert data.
+ */
+int fr_hash_table_insert(fr_hash_table_t *ht, void const *data)
+{
+ uint32_t key;
+ uint32_t entry;
+ uint32_t reversed;
+ fr_hash_entry_t *node;
+
+ if (!ht || !data) return 0;
+
+ key = ht->hash(data);
+ entry = key & ht->mask;
+ reversed = reverse(key);
+
+ if (!ht->buckets[entry]) fr_hash_table_fixup(ht, entry);
+
+ /*
+ * If we try to do our own memory allocation here, the
+ * speedup is only ~15% or so, which isn't worth it.
+ */
+ node = malloc(sizeof(*node));
+ if (!node) return 0;
+ memset(node, 0, sizeof(*node));
+
+ node->next = &ht->null;
+ node->reversed = reversed;
+ node->key = key;
+ node->data = data;
+
+ /* already in the table, can't insert it */
+ if (!list_insert(ht, &ht->buckets[entry], node)) {
+ free(node);
+ return 0;
+ }
+
+ /*
+ * Check the load factor, and grow the table if
+ * necessary.
+ */
+ ht->num_elements++;
+ if (ht->num_elements >= ht->next_grow) {
+ fr_hash_table_grow(ht);
+ }
+
+ return 1;
+}
+
+
+/*
+ * Internal find a node routine.
+ */
+static fr_hash_entry_t *fr_hash_table_find(fr_hash_table_t *ht, void const *data)
+{
+ uint32_t key;
+ uint32_t entry;
+ uint32_t reversed;
+
+ if (!ht) return NULL;
+
+ key = ht->hash(data);
+ entry = key & ht->mask;
+ reversed = reverse(key);
+
+ if (!ht->buckets[entry]) fr_hash_table_fixup(ht, entry);
+
+ return list_find(ht, ht->buckets[entry], reversed, data);
+}
+
+
+/*
+ * Replace old data with new data, OR insert if there is no old.
+ */
+int fr_hash_table_replace(fr_hash_table_t *ht, void const *data)
+{
+ fr_hash_entry_t *node;
+ void *tofree;
+
+ if (!ht || !data) return 0;
+
+ node = fr_hash_table_find(ht, data);
+ if (!node) {
+ return fr_hash_table_insert(ht, data);
+ }
+
+ if (ht->free) {
+ memcpy(&tofree, &node->data, sizeof(tofree));
+ ht->free(tofree);
+ }
+ node->data = data;
+
+ return 1;
+}
+
+
+/*
+ * Find data from a template
+ */
+void *fr_hash_table_finddata(fr_hash_table_t *ht, void const *data)
+{
+ fr_hash_entry_t *node;
+ void *out;
+
+ node = fr_hash_table_find(ht, data);
+ if (!node) return NULL;
+
+ memcpy(&out, &node->data, sizeof(out));
+
+ return out;
+}
+
+
+
+/*
+ * Yank an entry from the hash table, without freeing the data.
+ */
+void *fr_hash_table_yank(fr_hash_table_t *ht, void const *data)
+{
+ uint32_t key;
+ uint32_t entry;
+ uint32_t reversed;
+ void *old;
+ fr_hash_entry_t *node;
+
+ if (!ht) return NULL;
+
+ key = ht->hash(data);
+ entry = key & ht->mask;
+ reversed = reverse(key);
+
+ if (!ht->buckets[entry]) fr_hash_table_fixup(ht, entry);
+
+ node = list_find(ht, ht->buckets[entry], reversed, data);
+ if (!node) return NULL;
+
+ list_delete(ht, &ht->buckets[entry], node);
+ ht->num_elements--;
+
+ memcpy(&old, &node->data, sizeof(old));
+ free(node);
+
+ return old;
+}
+
+
+/*
+ * Delete a piece of data from the hash table.
+ */
+int fr_hash_table_delete(fr_hash_table_t *ht, void const *data)
+{
+ void *old;
+
+ old = fr_hash_table_yank(ht, data);
+ if (!old) return 0;
+
+ if (ht->free) ht->free(old);
+
+ return 1;
+}
+
+
+/*
+ * Free a hash table
+ */
+void fr_hash_table_free(fr_hash_table_t *ht)
+{
+ int i;
+ fr_hash_entry_t *node, *next;
+
+ if (!ht) return;
+
+ /*
+ * Walk over the buckets, freeing them all.
+ */
+ for (i = 0; i < ht->num_buckets; i++) {
+ if (ht->buckets[i]) for (node = ht->buckets[i];
+ node != &ht->null;
+ node = next) {
+ next = node->next;
+
+ if (node->data && ht->free) {
+ void *tofree;
+ memcpy(&tofree, &node->data, sizeof(tofree));
+ ht->free(tofree);
+ }
+
+ free(node);
+ }
+ }
+
+ free(ht->buckets);
+ free(ht);
+}
+
+
+/*
+ * Count number of elements
+ */
+int fr_hash_table_num_elements(fr_hash_table_t *ht)
+{
+ if (!ht) return 0;
+
+ return ht->num_elements;
+}
+
+
+/*
+ * Walk over the nodes, allowing deletes & inserts to happen.
+ */
+int fr_hash_table_walk(fr_hash_table_t *ht,
+ fr_hash_table_walk_t callback,
+ void *context)
+{
+ int i, rcode;
+
+ if (!ht || !callback) return 0;
+
+ for (i = ht->num_buckets - 1; i >= 0; i--) {
+ fr_hash_entry_t *node, *next;
+
+ /*
+ * Ensure that the current bucket is filled.
+ */
+ if (!ht->buckets[i]) fr_hash_table_fixup(ht, i);
+
+ for (node = ht->buckets[i]; node != &ht->null; node = next) {
+ void *arg;
+
+ next = node->next;
+
+ memcpy(&arg, &node->data, sizeof(arg));
+ rcode = callback(context, arg);
+
+ if (rcode != 0) return rcode;
+ }
+ }
+
+ return 0;
+}
+
+/** Iterate over entries in a hash table
+ *
+ * @note If the hash table is modified the iterator should be considered invalidated.
+ *
+ * @param[in] ht to iterate over.
+ * @param[in] iter Pointer to an iterator struct, used to maintain
+ * state between calls.
+ * @return
+ * - User data.
+ * - NULL if at the end of the list.
+ */
+void *fr_hash_table_iter_next(fr_hash_table_t *ht, fr_hash_iter_t *iter)
+{
+ fr_hash_entry_t *node;
+ uint32_t i;
+ void *out;
+
+ /*
+ * Return the next element in the bucket
+ */
+ if (iter->node != &ht->null) {
+ node = iter->node;
+ iter->node = node->next;
+
+ memcpy(&out, &node->data, sizeof(out)); /* const issues */
+ return out;
+ }
+
+ if (iter->bucket == 0) return NULL;
+
+ /*
+ * We might have to go through multiple empty
+ * buckets to find one that contains something
+ * we should return
+ */
+ i = iter->bucket - 1;
+ for (;;) {
+ if (!ht->buckets[i]) fr_hash_table_fixup(ht, i);
+
+ node = ht->buckets[i];
+ if (node == &ht->null) {
+ if (i == 0) break;
+ i--;
+ continue; /* This bucket was empty too... */
+ }
+
+ iter->node = node->next; /* Store the next one to examine */
+ iter->bucket = i;
+
+ memcpy(&out, &node->data, sizeof(out)); /* const issues */
+ return out;
+ }
+ iter->bucket = i;
+
+ return NULL;
+}
+
+/** Initialise an iterator
+ *
+ * @note If the hash table is modified the iterator should be considered invalidated.
+ *
+ * @param[in] ht to iterate over.
+ * @param[out] iter to initialise.
+ * @return
+ * - The first entry in the hash table.
+ * - NULL if the hash table is empty.
+ */
+void *fr_hash_table_iter_init(fr_hash_table_t *ht, fr_hash_iter_t *iter)
+{
+ iter->bucket = ht->num_buckets;
+ iter->node = &ht->null;
+
+ return fr_hash_table_iter_next(ht, iter);
+}
+
+
+#ifdef TESTING
+/*
+ * Show what the hash table is doing.
+ */
+int fr_hash_table_info(fr_hash_table_t *ht)
+{
+ int i, a, collisions, uninitialized;
+ int array[256];
+
+ if (!ht) return 0;
+
+ uninitialized = collisions = 0;
+ memset(array, 0, sizeof(array));
+
+ for (i = 0; i < ht->num_buckets; i++) {
+ uint32_t key;
+ int load;
+ fr_hash_entry_t *node, *next;
+
+ /*
+ * If we haven't inserted or looked up an entry
+ * in a bucket, it's uninitialized.
+ */
+ if (!ht->buckets[i]) {
+ uninitialized++;
+ continue;
+ }
+
+ load = 0;
+ key = ~0;
+ for (node = ht->buckets[i]; node != &ht->null; node = next) {
+ if (node->reversed == key) {
+ collisions++;
+ } else {
+ key = node->reversed;
+ }
+ next = node->next;
+ load++;
+ }
+
+ if (load > 255) load = 255;
+ array[load]++;
+ }
+
+ printf("HASH TABLE %p\tbuckets: %d\t(%d uninitialized)\n", ht,
+ ht->num_buckets, uninitialized);
+ printf("\tnum entries %d\thash collisions %d\n",
+ ht->num_elements, collisions);
+
+ a = 0;
+ for (i = 1; i < 256; i++) {
+ if (!array[i]) continue;
+ printf("%d\t%d\n", i, array[i]);
+
+ /*
+ * Since the entries are ordered, the lookup cost
+ * for any one element in a chain is (on average)
+ * the cost of walking half of the chain.
+ */
+ if (i > 1) {
+ a += array[i] * i;
+ }
+ }
+ a /= 2;
+ a += array[1];
+
+ printf("\texpected lookup cost = %d/%d or %f\n\n",
+ ht->num_elements, a,
+ (float) ht->num_elements / (float) a);
+
+ return 0;
+}
+#endif
+
+
+#define FNV_MAGIC_INIT (0x811c9dc5)
+#define FNV_MAGIC_PRIME (0x01000193)
+
+/*
+ * A fast hash function. For details, see:
+ *
+ * http://www.isthe.com/chongo/tech/comp/fnv/
+ *
+ * Which also includes public domain source. We've re-written
+ * it here for our purposes.
+ */
+uint32_t fr_hash(void const *data, size_t size)
+{
+ uint8_t const *p = data;
+ uint8_t const *q = p + size;
+ uint32_t hash = FNV_MAGIC_INIT;
+
+ /*
+ * FNV-1 hash each octet in the buffer
+ */
+ while (p != q) {
+ /*
+ * XOR the 8-bit quantity into the bottom of
+ * the hash.
+ */
+ hash ^= (uint32_t) (*p++);
+
+ /*
+ * Multiple by 32-bit magic FNV prime, mod 2^32
+ */
+ hash *= FNV_MAGIC_PRIME;
+#if 0
+ /*
+ * Potential optimization.
+ */
+ hash += (hash<<1) + (hash<<4) + (hash<<7) + (hash<<8) + (hash<<24);
+#endif
+ }
+
+ return hash;
+}
+
+/*
+ * Continue hashing data.
+ */
+uint32_t fr_hash_update(void const *data, size_t size, uint32_t hash)
+{
+ uint8_t const *p = data;
+ uint8_t const *q = p + size;
+
+ while (p != q) {
+ hash *= FNV_MAGIC_PRIME;
+ hash ^= (uint32_t) (*p++);
+ }
+
+ return hash;
+
+}
+
+/*
+ * Hash a C string, so we loop over it once.
+ */
+uint32_t fr_hash_string(char const *p)
+{
+ uint32_t hash = FNV_MAGIC_INIT;
+
+ while (*p) {
+ hash *= FNV_MAGIC_PRIME;
+ hash ^= (uint32_t) (*p++);
+ }
+
+ return hash;
+}
+
+
+#ifdef TESTING
+/*
+ * cc -g -DTESTING -I ../include hash.c -o hash
+ *
+ * ./hash
+ */
+static uint32_t hash_int(void const *data)
+{
+ return fr_hash((int *) data, sizeof(int));
+}
+
+#define MAX 1024*1024
+int main(int argc, char **argv)
+{
+ int i, *p, *q, k;
+ fr_hash_table_t *ht;
+ int *array;
+
+ ht = fr_hash_table_create(hash_int, NULL, NULL);
+ if (!ht) {
+ fprintf(stderr, "Hash create failed\n");
+ fr_exit(1);
+ }
+
+ array = malloc(sizeof(int) * MAX);
+ if (!array) fr_exit(1);
+
+ for (i = 0; i < MAX; i++) {
+ p = array + i;
+ *p = i;
+
+ if (!fr_hash_table_insert(ht, p)) {
+ fprintf(stderr, "Failed insert %08x\n", i);
+ fr_exit(1);
+ }
+#ifdef TEST_INSERT
+ q = fr_hash_table_finddata(ht, p);
+ if (q != p) {
+ fprintf(stderr, "Bad data %d\n", i);
+ fr_exit(1);
+ }
+#endif
+ }
+
+ fr_hash_table_info(ht);
+
+ /*
+ * Build this to see how lookups result in shortening
+ * of the hash chains.
+ */
+ if (1) {
+ for (i = 0; i < MAX ; i++) {
+ q = fr_hash_table_finddata(ht, &i);
+ if (!q || *q != i) {
+ fprintf(stderr, "Failed finding %d\n", i);
+ fr_exit(1);
+ }
+
+#if 0
+ if (!fr_hash_table_delete(ht, &i)) {
+ fprintf(stderr, "Failed deleting %d\n", i);
+ fr_exit(1);
+ }
+ q = fr_hash_table_finddata(ht, &i);
+ if (q) {
+ fprintf(stderr, "Failed to delete %08x\n", i);
+ fr_exit(1);
+ }
+#endif
+ }
+
+ fr_hash_table_info(ht);
+ }
+
+ fr_hash_table_free(ht);
+ free(array);
+
+ fr_exit(0);
+}
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 10:18:15 +0000