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.c593
1 files changed, 593 insertions, 0 deletions
diff --git a/src/lib/hash.c b/src/lib/hash.c
new file mode 100644
index 0000000..5530de1
--- /dev/null
+++ b/src/lib/hash.c
@@ -0,0 +1,593 @@
+/* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */
+
+/* @UNSAFE: whole file */
+
+#include "lib.h"
+#include "hash.h"
+#include "primes.h"
+
+#include <ctype.h>
+
+#define HASH_TABLE_MIN_SIZE 67
+
+#undef hash_table_create
+#undef hash_table_create_direct
+#undef hash_table_destroy
+#undef hash_table_clear
+#undef hash_table_lookup
+#undef hash_table_lookup_full
+#undef hash_table_insert
+#undef hash_table_update
+#undef hash_table_try_remove
+#undef hash_table_count
+#undef hash_table_iterate_init
+#undef hash_table_iterate
+#undef hash_table_freeze
+#undef hash_table_thaw
+#undef hash_table_copy
+
+struct hash_node {
+ struct hash_node *next;
+ void *key;
+ void *value;
+};
+
+struct hash_table {
+ pool_t node_pool;
+
+ int frozen;
+ unsigned int initial_size, nodes_count, removed_count;
+
+ unsigned int size;
+ struct hash_node *nodes;
+ struct hash_node *free_nodes;
+
+ hash_callback_t *hash_cb;
+ hash_cmp_callback_t *key_compare_cb;
+};
+
+struct hash_iterate_context {
+ struct hash_table *table;
+ struct hash_node *next;
+ unsigned int pos;
+};
+
+enum hash_table_operation{
+ HASH_TABLE_OP_INSERT,
+ HASH_TABLE_OP_UPDATE,
+ HASH_TABLE_OP_RESIZE
+};
+
+static bool hash_table_resize(struct hash_table *table, bool grow);
+
+void hash_table_create(struct hash_table **table_r, pool_t node_pool,
+ unsigned int initial_size, hash_callback_t *hash_cb,
+ hash_cmp_callback_t *key_compare_cb)
+{
+ struct hash_table *table;
+
+ pool_ref(node_pool);
+ table = i_new(struct hash_table, 1);
+ table->node_pool = node_pool;
+ table->initial_size =
+ I_MAX(primes_closest(initial_size), HASH_TABLE_MIN_SIZE);
+
+ table->hash_cb = hash_cb;
+ table->key_compare_cb = key_compare_cb;
+
+ table->size = table->initial_size;
+ table->nodes = i_new(struct hash_node, table->size);
+ *table_r = table;
+}
+
+static unsigned int direct_hash(const void *p)
+{
+ /* NOTE: may truncate the value, but that doesn't matter. */
+ return POINTER_CAST_TO(p, unsigned int);
+}
+
+static int direct_cmp(const void *p1, const void *p2)
+{
+ return p1 == p2 ? 0 : 1;
+}
+
+void hash_table_create_direct(struct hash_table **table_r, pool_t node_pool,
+ unsigned int initial_size)
+{
+ hash_table_create(table_r, node_pool, initial_size,
+ direct_hash, direct_cmp);
+}
+
+static void free_node(struct hash_table *table, struct hash_node *node)
+{
+ if (!table->node_pool->alloconly_pool)
+ p_free(table->node_pool, node);
+ else {
+ node->next = table->free_nodes;
+ table->free_nodes = node;
+ }
+}
+
+static void destroy_node_list(struct hash_table *table, struct hash_node *node)
+{
+ struct hash_node *next;
+
+ while (node != NULL) {
+ next = node->next;
+ p_free(table->node_pool, node);
+ node = next;
+ }
+}
+
+static void hash_table_destroy_nodes(struct hash_table *table)
+{
+ unsigned int i;
+
+ for (i = 0; i < table->size; i++) {
+ if (table->nodes[i].next != NULL)
+ destroy_node_list(table, table->nodes[i].next);
+ }
+}
+
+void hash_table_destroy(struct hash_table **_table)
+{
+ struct hash_table *table = *_table;
+
+ if (table == NULL)
+ return;
+ *_table = NULL;
+
+ i_assert(table->frozen == 0);
+
+ if (!table->node_pool->alloconly_pool) {
+ hash_table_destroy_nodes(table);
+ destroy_node_list(table, table->free_nodes);
+ }
+
+ pool_unref(&table->node_pool);
+ i_free(table->nodes);
+ i_free(table);
+}
+
+void hash_table_clear(struct hash_table *table, bool free_nodes)
+{
+ i_assert(table->frozen == 0);
+
+ if (!table->node_pool->alloconly_pool)
+ hash_table_destroy_nodes(table);
+
+ if (free_nodes) {
+ if (!table->node_pool->alloconly_pool)
+ destroy_node_list(table, table->free_nodes);
+ table->free_nodes = NULL;
+ }
+
+ memset(table->nodes, 0, sizeof(struct hash_node) * table->size);
+
+ table->nodes_count = 0;
+ table->removed_count = 0;
+}
+
+static struct hash_node *
+hash_table_lookup_node(const struct hash_table *table,
+ const void *key, unsigned int hash)
+{
+ struct hash_node *node;
+
+ node = &table->nodes[hash % table->size];
+
+ do {
+ if (node->key != NULL) {
+ if (table->key_compare_cb(node->key, key) == 0)
+ return node;
+ }
+ node = node->next;
+ } while (node != NULL);
+
+ return NULL;
+}
+
+void *hash_table_lookup(const struct hash_table *table, const void *key)
+{
+ struct hash_node *node;
+
+ node = hash_table_lookup_node(table, key, table->hash_cb(key));
+ return node != NULL ? node->value : NULL;
+}
+
+bool hash_table_lookup_full(const struct hash_table *table,
+ const void *lookup_key,
+ void **orig_key, void **value)
+{
+ struct hash_node *node;
+
+ node = hash_table_lookup_node(table, lookup_key,
+ table->hash_cb(lookup_key));
+ if (node == NULL)
+ return FALSE;
+
+ *orig_key = node->key;
+ *value = node->value;
+ return TRUE;
+}
+
+static void
+hash_table_insert_node(struct hash_table *table, void *key, void *value,
+ enum hash_table_operation opcode)
+{
+ struct hash_node *node, *prev;
+ unsigned int hash;
+ bool check_existing = TRUE;
+
+ i_assert(table->nodes_count < UINT_MAX);
+ i_assert(key != NULL);
+
+ if(opcode == HASH_TABLE_OP_RESIZE)
+ check_existing = FALSE;
+ hash = table->hash_cb(key);
+
+ if (check_existing && table->removed_count > 0) {
+ /* there may be holes, have to check everything */
+ node = hash_table_lookup_node(table, key, hash);
+ if (node != NULL) {
+ i_assert(opcode == HASH_TABLE_OP_UPDATE);
+ node->value = value;
+ return;
+ }
+
+ check_existing = FALSE;
+ }
+
+ /* a) primary node */
+ node = &table->nodes[hash % table->size];
+ if (node->key == NULL) {
+ table->nodes_count++;
+
+ node->key = key;
+ node->value = value;
+ return;
+ }
+ if (check_existing) {
+ if (table->key_compare_cb(node->key, key) == 0) {
+ i_assert(opcode == HASH_TABLE_OP_UPDATE);
+ node->value = value;
+ return;
+ }
+ }
+
+ /* b) collisions list */
+ prev = node; node = node->next;
+ while (node != NULL) {
+ if (node->key == NULL)
+ break;
+
+ if (check_existing) {
+ if (table->key_compare_cb(node->key, key) == 0) {
+ i_assert(opcode == HASH_TABLE_OP_UPDATE);
+ node->value = value;
+ return;
+ }
+ }
+ prev = node;
+ node = node->next;
+ }
+
+ if (node == NULL) {
+ if (table->frozen == 0 && hash_table_resize(table, TRUE)) {
+ /* resized table, try again */
+ hash_table_insert_node(table, key, value, HASH_TABLE_OP_RESIZE);
+ return;
+ }
+
+ if (table->free_nodes == NULL)
+ node = p_new(table->node_pool, struct hash_node, 1);
+ else {
+ node = table->free_nodes;
+ table->free_nodes = node->next;
+ node->next = NULL;
+ }
+ prev->next = node;
+ }
+
+ node->key = key;
+ node->value = value;
+
+ table->nodes_count++;
+}
+
+void hash_table_insert(struct hash_table *table, void *key, void *value)
+{
+ hash_table_insert_node(table, key, value, HASH_TABLE_OP_INSERT);
+}
+
+void hash_table_update(struct hash_table *table, void *key, void *value)
+{
+ hash_table_insert_node(table, key, value, HASH_TABLE_OP_UPDATE);
+}
+
+static void
+hash_table_compress(struct hash_table *table, struct hash_node *root)
+{
+ struct hash_node *node, *next;
+
+ i_assert(table->frozen == 0);
+
+ /* remove deleted nodes from the list */
+ for (node = root; node->next != NULL; ) {
+ next = node->next;
+
+ if (next->key == NULL) {
+ node->next = next->next;
+ free_node(table, next);
+ } else {
+ node = next;
+ }
+ }
+
+ /* update root */
+ if (root->key == NULL && root->next != NULL) {
+ next = root->next;
+ *root = *next;
+ free_node(table, next);
+ }
+}
+
+static void hash_table_compress_removed(struct hash_table *table)
+{
+ unsigned int i;
+
+ for (i = 0; i < table->size; i++)
+ hash_table_compress(table, &table->nodes[i]);
+
+ table->removed_count = 0;
+}
+
+bool hash_table_try_remove(struct hash_table *table, const void *key)
+{
+ struct hash_node *node;
+ unsigned int hash;
+
+ hash = table->hash_cb(key);
+
+ node = hash_table_lookup_node(table, key, hash);
+ if (unlikely(node == NULL))
+ return FALSE;
+
+ node->key = NULL;
+ table->nodes_count--;
+
+ if (table->frozen != 0)
+ table->removed_count++;
+ else if (!hash_table_resize(table, FALSE))
+ hash_table_compress(table, &table->nodes[hash % table->size]);
+ return TRUE;
+}
+
+unsigned int hash_table_count(const struct hash_table *table)
+{
+ return table->nodes_count;
+}
+
+struct hash_iterate_context *hash_table_iterate_init(struct hash_table *table)
+{
+ struct hash_iterate_context *ctx;
+
+ hash_table_freeze(table);
+
+ ctx = i_new(struct hash_iterate_context, 1);
+ ctx->table = table;
+ ctx->next = &table->nodes[0];
+ return ctx;
+}
+
+static struct hash_node *
+hash_table_iterate_next(struct hash_iterate_context *ctx,
+ struct hash_node *node)
+{
+ do {
+ node = node->next;
+ if (node == NULL) {
+ if (++ctx->pos == ctx->table->size) {
+ ctx->pos--;
+ return NULL;
+ }
+ node = &ctx->table->nodes[ctx->pos];
+ }
+ } while (node->key == NULL);
+
+ return node;
+}
+
+bool hash_table_iterate(struct hash_iterate_context *ctx,
+ void **key_r, void **value_r)
+{
+ struct hash_node *node;
+
+ node = ctx->next;
+ if (node != NULL && node->key == NULL)
+ node = hash_table_iterate_next(ctx, node);
+ if (node == NULL) {
+ *key_r = *value_r = NULL;
+ return FALSE;
+ }
+ *key_r = node->key;
+ *value_r = node->value;
+
+ ctx->next = hash_table_iterate_next(ctx, node);
+ return TRUE;
+}
+
+void hash_table_iterate_deinit(struct hash_iterate_context **_ctx)
+{
+ struct hash_iterate_context *ctx = *_ctx;
+
+ if (ctx == NULL)
+ return;
+
+ *_ctx = NULL;
+ hash_table_thaw(ctx->table);
+ i_free(ctx);
+}
+
+void hash_table_freeze(struct hash_table *table)
+{
+ table->frozen++;
+}
+
+void hash_table_thaw(struct hash_table *table)
+{
+ i_assert(table->frozen > 0);
+
+ if (--table->frozen > 0)
+ return;
+
+ if (table->removed_count > 0) {
+ if (!hash_table_resize(table, FALSE))
+ hash_table_compress_removed(table);
+ }
+}
+
+static bool hash_table_resize(struct hash_table *table, bool grow)
+{
+ struct hash_node *old_nodes, *node, *next;
+ unsigned int next_size, old_size, i;
+ float nodes_per_list;
+
+ i_assert(table->frozen == 0);
+
+ nodes_per_list = (float) table->nodes_count / (float) table->size;
+ if (nodes_per_list > 0.3 && nodes_per_list < 2.0)
+ return FALSE;
+
+ next_size = I_MAX(primes_closest(table->nodes_count+1),
+ table->initial_size);
+ if (next_size == table->size)
+ return FALSE;
+
+ if (grow && table->size >= next_size)
+ return FALSE;
+
+ /* recreate primary table */
+ old_size = table->size;
+ old_nodes = table->nodes;
+
+ table->size = I_MAX(next_size, HASH_TABLE_MIN_SIZE);
+ table->nodes = i_new(struct hash_node, table->size);
+
+ table->nodes_count = 0;
+ table->removed_count = 0;
+
+ table->frozen++;
+
+ /* move the data */
+ for (i = 0; i < old_size; i++) {
+ node = &old_nodes[i];
+ if (node->key != NULL) {
+ hash_table_insert_node(table, node->key,
+ node->value, HASH_TABLE_OP_RESIZE);
+ }
+
+ for (node = node->next; node != NULL; node = next) {
+ next = node->next;
+
+ if (node->key != NULL) {
+ hash_table_insert_node(table, node->key,
+ node->value, HASH_TABLE_OP_RESIZE);
+ }
+ free_node(table, node);
+ }
+ }
+
+ table->frozen--;
+
+ i_free(old_nodes);
+ return TRUE;
+}
+
+void hash_table_copy(struct hash_table *dest, struct hash_table *src)
+{
+ struct hash_iterate_context *iter;
+ void *key, *value;
+
+ hash_table_freeze(dest);
+
+ iter = hash_table_iterate_init(src);
+ while (hash_table_iterate(iter, &key, &value))
+ hash_table_insert(dest, key, value);
+ hash_table_iterate_deinit(&iter);
+
+ hash_table_thaw(dest);
+}
+
+/* a char* hash function from ASU -- from glib */
+unsigned int ATTR_NO_SANITIZE_INTEGER
+str_hash(const char *p)
+{
+ const unsigned char *s = (const unsigned char *)p;
+ unsigned int g, h = 0;
+
+ while (*s != '\0') {
+ h = (h << 4) + *s;
+ if ((g = h & 0xf0000000UL) != 0) {
+ h = h ^ (g >> 24);
+ h = h ^ g;
+ }
+ s++;
+ }
+
+ return h;
+}
+
+/* a char* hash function from ASU -- from glib */
+unsigned int ATTR_NO_SANITIZE_INTEGER
+strcase_hash(const char *p)
+{
+ const unsigned char *s = (const unsigned char *)p;
+ unsigned int g, h = 0;
+
+ while (*s != '\0') {
+ h = (h << 4) + i_toupper(*s);
+ if ((g = h & 0xf0000000UL) != 0) {
+ h = h ^ (g >> 24);
+ h = h ^ g;
+ }
+ s++;
+ }
+
+ return h;
+}
+
+unsigned int ATTR_NO_SANITIZE_INTEGER
+mem_hash(const void *p, unsigned int size)
+{
+ const unsigned char *s = p;
+ unsigned int i, g, h = 0;
+
+ for (i = 0; i < size; i++) {
+ h = (h << 4) + *s;
+ if ((g = h & 0xf0000000UL) != 0) {
+ h = h ^ (g >> 24);
+ h = h ^ g;
+ }
+ s++;
+ }
+ return h;
+}
+
+unsigned int ATTR_NO_SANITIZE_INTEGER
+strfastcase_hash(const char *p)
+{
+ const unsigned char *s = (const unsigned char *)p;
+ unsigned int g, h = 0;
+
+ while (*s != '\0') {
+ h = (h << 4) + ((*s) & ~0x20U);
+ if ((g = h & 0xf0000000UL) != 0) {
+ h = h ^ (g >> 24);
+ h = h ^ g;
+ }
+ s++;
+ }
+
+ return h;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-25 13:22:42 +0000