src/lib/hash.c

	hash.c revision a3b6849ec9a7e7cb209d0e330211aed6395daabd
/* GLIB - Library of useful routines for C programming
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 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
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

/*
 * Modified by the GLib Team and others 1997-1999.  See the AUTHORS
 * file for a list of people on the GLib Team.  See the ChangeLog
 * files for a list of changes.  These files are distributed with
 * GLib at ftp://ftp.gtk.org/pub/gtk/.
 */

/* several modifications Copyright (C) 2002 by Timo Sirainen */

#include "lib.h"
#include "hash.h"
#include "primes.h"

#include <ctype.h>

#define HASH_TABLE_MIN_SIZE 11
#define HASH_TABLE_MAX_SIZE 13845163

typedef struct _HashNode {
    void *key;
    void *value;

    int destroyed;
    struct _HashNode *next;
} HashNode;

struct _HashTable {
    Pool pool;

    unsigned int size;
    unsigned int nodes_count, nodes_destroyed;
    int frozen;
    HashNode **nodes;

    HashFunc hash_func;
    HashCompareFunc key_compare_func;
};

static void hash_cleanup(HashTable *table);
static int hash_resize(HashTable *table);

static int foreach_stop;

static unsigned int direct_hash(const void *p)
{
    /* NOTE: may truncate the value, but that doesn't matter. */
    return POINTER_TO_UINT(p);
}

static HashNode *hash_node_create(Pool pool, const void *key,
                  const void *value)
{
    HashNode *node;

        node = p_new(pool, HashNode, 1);
    node->key = (void *) key;
    node->value = (void *) value;

    return node;
}

static void hash_nodes_destroy(HashTable *table, HashNode *node)
{
    HashNode *next;

    while (node != NULL) {
        next = node->next;
                p_free(table->pool, node);
                node = next;
    }
}

HashTable *hash_create(Pool pool, unsigned int initial_size,
               HashFunc hash_func, HashCompareFunc key_compare_func)
{
    HashTable *table;

        i_assert(pool != NULL);

    table = p_new(pool, HashTable, 1);
        table->pool = pool;
    table->size = CLAMP(primes_closest(initial_size),
                HASH_TABLE_MIN_SIZE,
                HASH_TABLE_MAX_SIZE);

    table->hash_func = hash_func != NULL ? hash_func : direct_hash;
    table->key_compare_func = key_compare_func;
    table->nodes = p_new(pool, HashNode *, table->size);

    return table;
}

void hash_destroy(HashTable *table)
{
    unsigned int i;

    if (table == NULL)
                return;

    for (i = 0; i < table->size; i++)
        hash_nodes_destroy(table, table->nodes[i]);

    p_free(table->pool, table->nodes);
    p_free(table->pool, table);
}

void hash_clear(HashTable *table)
{
    unsigned int i;

    i_assert(table != NULL);

    for (i = 0; i < table->size; i++) {
        hash_nodes_destroy(table, table->nodes[i]);
        table->nodes[i] = NULL;
    }
}

static inline HashNode **
hash_lookup_node(HashTable *table, const void *key)
{
    HashNode **node;

    node = &table->nodes[table->hash_func(key) % table->size];

    /* Hash table lookup needs to be fast.
       We therefore remove the extra conditional of testing
       whether to call the key_compare_func or not from
       the inner loop. */
    if (table->key_compare_func) {
        while (*node != NULL) {
                        if (!(*node)->destroyed &&
                table->key_compare_func((*node)->key, key) == 0)
                                break;
            node = &(*node)->next;
        }
    } else {
        while (*node != NULL && (*node)->key != key)
            node = &(*node)->next;
    }

    return node;
}

void *hash_lookup(HashTable *table, const void *key)
{
    HashNode *node;

    i_assert(table != NULL);

    node = *hash_lookup_node(table, key);
    return node != NULL && !node->destroyed ? node->value : NULL;
}

int hash_lookup_full(HashTable *table, const void *lookup_key,
             void **orig_key, void **value)
{
    HashNode *node;

    i_assert(table != NULL);

    node = *hash_lookup_node(table, lookup_key);
    if (node == NULL || node->destroyed)
        return FALSE;

    if (orig_key != NULL)
        *orig_key = node->key;
    if (value != NULL)
        *value = node->value;
    return TRUE;
}

static void hash_insert_full(HashTable *table, const void *key,
                 const void *value, int replace_key)
{
    HashNode **node;

    i_assert(table != NULL);

    node = hash_lookup_node(table, key);
    if (*node == NULL) {
        *node = hash_node_create(table->pool, key, value);

        table->nodes_count++;
        if (!table->frozen)
            hash_resize(table);
    } else {
        if (replace_key || (*node)->destroyed) {
            (*node)->key = (void *) key;
            (*node)->destroyed = FALSE;
        }

        (*node)->value = (void *) value;
    }
}

void hash_insert(HashTable *table, const void *key, const void *value)
{
    hash_insert_full(table, key, value, TRUE);
}

void hash_update(HashTable *table, const void *key, const void *value)
{
    hash_insert_full(table, key, value, FALSE);
}

void hash_remove(HashTable *table, const void *key)
{
    HashNode **node, *old_node;

    i_assert(table != NULL);

    node = hash_lookup_node(table, key);
    if (*node != NULL && !(*node)->destroyed) {
        table->nodes_count--;

        if (table->frozen) {
            (*node)->destroyed = TRUE;
                        table->nodes_destroyed++;
        } else {
            old_node = *node;
            *node = old_node->next;
            p_free(table->pool, old_node);

            hash_resize(table);
        }
    }
}

void hash_freeze(HashTable *table)
{
    i_assert(table != NULL);

    table->frozen++;
}

void hash_thaw(HashTable *table)
{
    i_assert(table != NULL);
    i_assert(table->frozen > 0);

    if (--table->frozen == 0)
                hash_cleanup(table);
}

void hash_foreach(HashTable *table, HashForeachFunc func, void *context)
{
    HashNode *node;
    unsigned int i;

    i_assert(table != NULL);
    i_assert(func != NULL);

    hash_freeze(table);

        foreach_stop = FALSE;
    for (i = 0; i < table->size; i++) {
        for (node = table->nodes[i]; node; node = node->next) {
            if (!node->destroyed) {
                func(node->key, node->value, context);

                if (foreach_stop) {
                    foreach_stop = FALSE;
                    hash_thaw(table);
                                        return;
                }
            }
        }
    }
        hash_thaw(table);
}

void hash_foreach_stop(void)
{
        foreach_stop = TRUE;
}

/* Returns the number of elements contained in the hash table. */
unsigned int hash_size(HashTable *table)
{
    i_assert(table != NULL);

    return table->nodes_count;
}

static int hash_resize(HashTable *table)
{
        HashFunc hash_func;
    HashNode *node, *next, **new_nodes;
    float nodes_per_list;
    unsigned int hash_val, new_size, i;

    nodes_per_list = (float) table->nodes_count / (float) table->size;
    if ((nodes_per_list > 0.3 || table->size <= HASH_TABLE_MIN_SIZE) &&
        (nodes_per_list < 3.0 || table->size >= HASH_TABLE_MAX_SIZE))
        return FALSE;

    new_size = CLAMP(primes_closest(table->nodes_count+1),
             HASH_TABLE_MIN_SIZE,
             HASH_TABLE_MAX_SIZE);

    new_nodes = p_new(table->pool, HashNode *, new_size);

        hash_func = table->hash_func;
    for (i = 0; i < table->size; i++) {
        for (node = table->nodes[i]; node != NULL; node = next) {
            next = node->next;

            if (node->destroyed) {
                                p_free(table->pool, node);
            } else {
                hash_val = hash_func(node->key) % new_size;

                node->next = new_nodes[hash_val];
                new_nodes[hash_val] = node;
            }
        }
    }

    p_free(table->pool, table->nodes);
    table->nodes = new_nodes;
    table->size = new_size;
    table->nodes_destroyed = 0;
        return TRUE;
}

static void hash_cleanup(HashTable *table)
{
    HashNode **node, **next, *old_node;
        unsigned int i;

    if (hash_resize(table))
        return;

    if (table->nodes_destroyed == 0)
                return;

        /* find the destroyed nodes from hash table and remove them */
    for (i = 0; i < table->size; i++) {
        for (node = &table->nodes[i]; *node != NULL; node = next) {
            next = &(*node)->next;

            if ((*node)->destroyed) {
                                old_node = *node;
                *node = *next;
                p_free(table->pool, old_node);

                /* next points to free'd memory area now,
                   fix it */
                next = node;

                if (--table->nodes_destroyed == 0)
                                        return;
            }
        }
    }
}

/* a char* hash function from ASU -- from glib */
unsigned int str_hash(const void *p)
{
        const unsigned char *s = 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 void *p)
{
        const unsigned char *s = 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;
}