src/lib/hash.c

	hash.c revision c04da04cc300ef1c143ff09b566e44f74f5626df
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith/* Copyright (c) 2002-2014 Dovecot authors, see the included COPYING file */
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith/* @UNSAFE: whole file */
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#include "lib.h"
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#include "hash.h"
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#include "primes.h"
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#include <ctype.h>
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#define HASH_TABLE_MIN_SIZE 67
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_create
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_create_direct
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_destroy
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_clear
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_lookup
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_lookup_full
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_insert
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_update
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_try_remove
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_count
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_iterate_init
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_iterate
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_freeze
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_thaw
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith#undef hash_table_copy
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstruct hash_node {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *next;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    void *key;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    void *value;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith};
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstruct hash_table {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    pool_t node_pool;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    int frozen;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    unsigned int initial_size, nodes_count, removed_count;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    unsigned int size;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *nodes;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *free_nodes;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    hash_callback_t *hash_cb;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    hash_cmp_callback_t *key_compare_cb;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith};
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstruct hash_iterate_context {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_table *table;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *next;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    unsigned int pos;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith};
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstatic bool hash_table_resize(struct hash_table *table, bool grow);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithvoid hash_table_create(struct hash_table **table_r, pool_t node_pool,
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith               unsigned int initial_size, hash_callback_t *hash_cb,
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith               hash_cmp_callback_t *key_compare_cb)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_table *table;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    pool_ref(node_pool);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table = i_new(struct hash_table, 1);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table->node_pool = node_pool;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table->initial_size =
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        I_MAX(primes_closest(initial_size), HASH_TABLE_MIN_SIZE);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table->hash_cb = hash_cb;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table->key_compare_cb = key_compare_cb;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table->size = table->initial_size;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table->nodes = i_new(struct hash_node, table->size);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    *table_r = table;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstatic unsigned int direct_hash(const void *p)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    /* NOTE: may truncate the value, but that doesn't matter. */
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    return POINTER_CAST_TO(p, unsigned int);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstatic int direct_cmp(const void *p1, const void *p2)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    return p1 == p2 ? 0 : 1;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithvoid hash_table_create_direct(struct hash_table **table_r, pool_t node_pool,
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith                  unsigned int initial_size)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    hash_table_create(table_r, node_pool, initial_size,
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith              direct_hash, direct_cmp);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstatic void free_node(struct hash_table *table, struct hash_node *node)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    if (!table->node_pool->alloconly_pool)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        p_free(table->node_pool, node);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    else {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        node->next = table->free_nodes;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        table->free_nodes = node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstatic void destroy_node_list(struct hash_table *table, struct hash_node *node)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *next;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    while (node != NULL) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        next = node->next;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        p_free(table->node_pool, node);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        node = next;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstatic void hash_table_destroy_nodes(struct hash_table *table)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    unsigned int i;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    for (i = 0; i < table->size; i++) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        if (table->nodes[i].next != NULL)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            destroy_node_list(table, table->nodes[i].next);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithvoid hash_table_destroy(struct hash_table **_table)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_table *table = *_table;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    *_table = NULL;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    if (!table->node_pool->alloconly_pool) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        hash_table_destroy_nodes(table);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        destroy_node_list(table, table->free_nodes);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    pool_unref(&table->node_pool);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    i_free(table->nodes);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    i_free(table);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithvoid hash_table_clear(struct hash_table *table, bool free_nodes)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    if (!table->node_pool->alloconly_pool)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        hash_table_destroy_nodes(table);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    if (free_nodes) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        if (!table->node_pool->alloconly_pool)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            destroy_node_list(table, table->free_nodes);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith                table->free_nodes = NULL;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    memset(table->nodes, 0, sizeof(struct hash_node) * table->size);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table->nodes_count = 0;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table->removed_count = 0;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstatic struct hash_node *
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithhash_table_lookup_node(const struct hash_table *table,
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith               const void *key, unsigned int hash)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    node = &table->nodes[hash % table->size];
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    do {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        if (node->key != NULL) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            if (table->key_compare_cb(node->key, key) == 0)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith                return node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        node = node->next;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    } while (node != NULL);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    return NULL;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithvoid *hash_table_lookup(const struct hash_table *table, const void *key)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    node = hash_table_lookup_node(table, key, table->hash_cb(key));
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    return node != NULL ? node->value : NULL;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithbool hash_table_lookup_full(const struct hash_table *table,
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith                const void *lookup_key,
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith                void **orig_key, void **value)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    node = hash_table_lookup_node(table, lookup_key,
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith                      table->hash_cb(lookup_key));
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    if (node == NULL)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        return FALSE;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    *orig_key = node->key;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    *value = node->value;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    return TRUE;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstatic struct hash_node * ATTR_NOWARN_UNUSED_RESULT
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithhash_table_insert_node(struct hash_table *table, void *key, void *value,
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith               bool check_existing)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *node, *prev;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    unsigned int hash;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    i_assert(key != NULL);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    hash = table->hash_cb(key);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    if (check_existing && table->removed_count > 0) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        /* there may be holes, have to check everything */
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        node = hash_table_lookup_node(table, key, hash);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        if (node != NULL) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            node->value = value;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            return node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith                check_existing = FALSE;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    /* a) primary node */
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    node = &table->nodes[hash % table->size];
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    if (node->key == NULL) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        table->nodes_count++;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        node->key = key;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        node->value = value;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        return node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    if (check_existing) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        if (table->key_compare_cb(node->key, key) == 0) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            node->value = value;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            return node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    /* b) collisions list */
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    prev = node; node = node->next;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    while (node != NULL) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        if (node->key == NULL)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            break;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        if (check_existing) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            if (table->key_compare_cb(node->key, key) == 0) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith                node->value = value;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith                return node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        prev = node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        node = node->next;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    if (node == NULL) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        if (table->frozen == 0 && hash_table_resize(table, TRUE)) {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            /* resized table, try again */
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            return hash_table_insert_node(table, key, value, FALSE);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        if (table->free_nodes == NULL)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            node = p_new(table->node_pool, struct hash_node, 1);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        else {
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            node = table->free_nodes;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            table->free_nodes = node->next;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith            node->next = NULL;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith        prev->next = node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    }
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    node->key = key;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    node->value = value;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    table->nodes_count++;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    return node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithvoid hash_table_insert(struct hash_table *table, void *key, void *value)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    struct hash_node *node;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    node = hash_table_insert_node(table, key, value, TRUE);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    node->key = key;
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithvoid hash_table_update(struct hash_table *table, void *key, void *value)
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith{
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith    hash_table_insert_node(table, key, value, TRUE);
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith}
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmith
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithstatic void
c1bef59b02d89a84c23d29663cc4e6d46148ebd2David Goldsmithhash_table_compress(struct hash_table *table, struct hash_node *root)
{
    struct hash_node *node, *next;

    /* 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;

    *_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;

        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, FALSE);
        }

        for (node = node->next; node != NULL; node = next) {
            next = node->next;

            if (node->key != NULL) {
                hash_table_insert_node(table, node->key,
                               node->value, FALSE);
            }
            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 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)) {
            h = h ^ (g >> 24);
            h = h ^ g;
        }
        s++;
    }

    return h;
}

/* a char* hash function from ASU -- from glib */
unsigned int 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)) {
            h = h ^ (g >> 24);
            h = h ^ g;
        }
        s++;
    }

    return h;
}

unsigned int 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)) {
            h = h ^ (g >> 24);
            h = h ^ g;
        }
        s++;
    }
    return h;
}