path: root/src/hash.c

/*
 * hash.c: chained hash tables
 *
 * Reference: Your favorite introductory book on algorithms
 *
 * Copyright (C) 2000 Bjorn Reese and Daniel Veillard.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
 *
 * Author: breese@users.sourceforge.net
 */

#include <string.h>
#include <stdlib.h>
#include "hash.h"

#define MAX_HASH_LEN 8

/* #define DEBUG_GROW */

/*
 * A single entry in the hash table
 */
typedef struct _virHashEntry virHashEntry;
typedef virHashEntry *virHashEntryPtr;
struct _virHashEntry {
    struct _virHashEntry *next;
    char *name;
    void *payload;
    int valid;
};

/*
 * The entire hash table
 */
struct _virHashTable {
    struct _virHashEntry *table;
    int size;
    int nbElems;
};

/*
 * virHashComputeKey:
 * Calculate the hash key
 */
static unsigned long
virHashComputeKey(virHashTablePtr table, const char *name)
{
    unsigned long value = 0L;
    char ch;

    if (name != NULL) {
        value += 30 * (*name);
        while ((ch = *name++) != 0) {
            value =
                value ^ ((value << 5) + (value >> 3) + (unsigned long) ch);
        }
    }
    return (value % table->size);
}

/**
 * virHashCreate:
 * @size: the size of the hash table
 *
 * Create a new virHashTablePtr.
 *
 * Returns the newly created object, or NULL if an error occured.
 */
virHashTablePtr
virHashCreate(int size)
{
    virHashTablePtr table;

    if (size <= 0)
        size = 256;

    table = malloc(sizeof(virHashTable));
    if (table) {
        table->size = size;
        table->nbElems = 0;
        table->table = malloc(size * sizeof(virHashEntry));
        if (table->table) {
            memset(table->table, 0, size * sizeof(virHashEntry));
            return (table);
        }
        free(table);
    }
    return (NULL);
}

/**
 * virHashGrow:
 * @table: the hash table
 * @size: the new size of the hash table
 *
 * resize the hash table
 *
 * Returns 0 in case of success, -1 in case of failure
 */
static int
virHashGrow(virHashTablePtr table, int size)
{
    unsigned long key;
    int oldsize, i;
    virHashEntryPtr iter, next;
    struct _virHashEntry *oldtable;

#ifdef DEBUG_GROW
    unsigned long nbElem = 0;
#endif

    if (table == NULL)
        return (-1);
    if (size < 8)
        return (-1);
    if (size > 8 * 2048)
        return (-1);

    oldsize = table->size;
    oldtable = table->table;
    if (oldtable == NULL)
        return (-1);

    table->table = malloc(size * sizeof(virHashEntry));
    if (table->table == NULL) {
        table->table = oldtable;
        return (-1);
    }
    memset(table->table, 0, size * sizeof(virHashEntry));
    table->size = size;

    /*  If the two loops are merged, there would be situations where
     * a new entry needs to allocated and data copied into it from 
     * the main table. So instead, we run through the array twice, first
     * copying all the elements in the main array (where we can't get
     * conflicts) and then the rest, so we only free (and don't allocate)
     */
    for (i = 0; i < oldsize; i++) {
        if (oldtable[i].valid == 0)
            continue;
        key = virHashComputeKey(table, oldtable[i].name);
        memcpy(&(table->table[key]), &(oldtable[i]), sizeof(virHashEntry));
        table->table[key].next = NULL;
    }

    for (i = 0; i < oldsize; i++) {
        iter = oldtable[i].next;
        while (iter) {
            next = iter->next;

            /*
             * put back the entry in the new table
             */

            key = virHashComputeKey(table, iter->name);
            if (table->table[key].valid == 0) {
                memcpy(&(table->table[key]), iter, sizeof(virHashEntry));
                table->table[key].next = NULL;
                free(iter);
            } else {
                iter->next = table->table[key].next;
                table->table[key].next = iter;
            }

#ifdef DEBUG_GROW
            nbElem++;
#endif

            iter = next;
        }
    }

    free(oldtable);

#ifdef DEBUG_GROW
    xmlGenericError(xmlGenericErrorContext,
                    "virHashGrow : from %d to %d, %d elems\n", oldsize,
                    size, nbElem);
#endif

    return (0);
}

/**
 * virHashFree:
 * @table: the hash table
 * @f:  the deallocator function for items in the hash
 *
 * Free the hash @table and its contents. The userdata is
 * deallocated with @f if provided.
 */
void
virHashFree(virHashTablePtr table, virHashDeallocator f)
{
    int i;
    virHashEntryPtr iter;
    virHashEntryPtr next;
    int inside_table = 0;
    int nbElems;

    if (table == NULL)
        return;
    if (table->table) {
        nbElems = table->nbElems;
        for (i = 0; (i < table->size) && (nbElems > 0); i++) {
            iter = &(table->table[i]);
            if (iter->valid == 0)
                continue;
            inside_table = 1;
            while (iter) {
                next = iter->next;
                if ((f != NULL) && (iter->payload != NULL))
                    f(iter->payload, iter->name);
                if (iter->name)
                    free(iter->name);
                iter->payload = NULL;
                if (!inside_table)
                    free(iter);
                nbElems--;
                inside_table = 0;
                iter = next;
            }
            inside_table = 0;
        }
        free(table->table);
    }
    free(table);
}

/**
 * virHashAddEntry3:
 * @table: the hash table
 * @name: the name of the userdata
 * @userdata: a pointer to the userdata
 *
 * Add the @userdata to the hash @table. This can later be retrieved
 * by using @name. Duplicate entries generate errors.
 *
 * Returns 0 the addition succeeded and -1 in case of error.
 */
int
virHashAddEntry(virHashTablePtr table, const char *name, void *userdata)
{
    unsigned long key, len = 0;
    virHashEntryPtr entry;
    virHashEntryPtr insert;

    if ((table == NULL) || (name == NULL))
        return (-1);

    /*
     * Check for duplicate and insertion location.
     */
    key = virHashComputeKey(table, name);
    if (table->table[key].valid == 0) {
        insert = NULL;
    } else {
        for (insert = &(table->table[key]); insert->next != NULL;
             insert = insert->next) {
            if (!strcmp(insert->name, name))
                return (-1);
            len++;
        }
        if (!strcmp(insert->name, name))
            return (-1);
    }

    if (insert == NULL) {
        entry = &(table->table[key]);
    } else {
        entry = malloc(sizeof(virHashEntry));
        if (entry == NULL)
            return (-1);
    }

    entry->name = strdup(name);
    entry->payload = userdata;
    entry->next = NULL;
    entry->valid = 1;


    if (insert != NULL)
        insert->next = entry;

    table->nbElems++;

    if (len > MAX_HASH_LEN)
        virHashGrow(table, MAX_HASH_LEN * table->size);

    return (0);
}

/**
 * virHashUpdateEntry:
 * @table: the hash table
 * @name: the name of the userdata
 * @userdata: a pointer to the userdata
 * @f: the deallocator function for replaced item (if any)
 *
 * Add the @userdata to the hash @table. This can later be retrieved
 * by using @name. Existing entry for this tuple
 * will be removed and freed with @f if found.
 *
 * Returns 0 the addition succeeded and -1 in case of error.
 */
int
virHashUpdateEntry(virHashTablePtr table, const char *name,
                   void *userdata, virHashDeallocator f)
{
    unsigned long key;
    virHashEntryPtr entry;
    virHashEntryPtr insert;

    if ((table == NULL) || name == NULL)
        return (-1);

    /*
     * Check for duplicate and insertion location.
     */
    key = virHashComputeKey(table, name);
    if (table->table[key].valid == 0) {
        insert = NULL;
    } else {
        for (insert = &(table->table[key]); insert->next != NULL;
             insert = insert->next) {
            if (!strcmp(insert->name, name)) {
                if (f)
                    f(insert->payload, insert->name);
                insert->payload = userdata;
                return (0);
            }
        }
        if (!strcmp(insert->name, name)) {
            if (f)
                f(insert->payload, insert->name);
            insert->payload = userdata;
            return (0);
        }
    }

    if (insert == NULL) {
        entry = &(table->table[key]);
    } else {
        entry = malloc(sizeof(virHashEntry));
        if (entry == NULL)
            return (-1);
    }

    entry->name = strdup(name);
    entry->payload = userdata;
    entry->next = NULL;
    entry->valid = 1;
    table->nbElems++;


    if (insert != NULL) {
        insert->next = entry;
    }
    return (0);
}

/**
 * virHashLookup:
 * @table: the hash table
 * @name: the name of the userdata
 *
 * Find the userdata specified by the (@name, @name2, @name3) tuple.
 *
 * Returns the a pointer to the userdata
 */
void *
virHashLookup(virHashTablePtr table, const char *name)
{
    unsigned long key;
    virHashEntryPtr entry;

    if (table == NULL)
        return (NULL);
    if (name == NULL)
        return (NULL);
    key = virHashComputeKey(table, name);
    if (table->table[key].valid == 0)
        return (NULL);
    for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
        if (!strcmp(entry->name, name))
            return (entry->payload);
    }
    return (NULL);
}

/**
 * virHashSize:
 * @table: the hash table
 *
 * Query the number of elements installed in the hash @table.
 *
 * Returns the number of elements in the hash table or
 * -1 in case of error
 */
int
virHashSize(virHashTablePtr table)
{
    if (table == NULL)
        return (-1);
    return (table->nbElems);
}

/**
 * virHashRemoveEntry:
 * @table: the hash table
 * @name: the name of the userdata
 * @f: the deallocator function for removed item (if any)
 *
 * Find the userdata specified by the @name and remove
 * it from the hash @table. Existing userdata for this tuple will be removed
 * and freed with @f.
 *
 * Returns 0 if the removal succeeded and -1 in case of error or not found.
 */
int
virHashRemoveEntry(virHashTablePtr table, const char *name,
                   virHashDeallocator f)
{
    unsigned long key;
    virHashEntryPtr entry;
    virHashEntryPtr prev = NULL;

    if (table == NULL || name == NULL)
        return (-1);

    key = virHashComputeKey(table, name);
    if (table->table[key].valid == 0) {
        return (-1);
    } else {
        for (entry = &(table->table[key]); entry != NULL;
             entry = entry->next) {
            if (!strcmp(entry->name, name)) {
                if ((f != NULL) && (entry->payload != NULL))
                    f(entry->payload, entry->name);
                entry->payload = NULL;
                if (entry->name)
                    free(entry->name);
                if (prev) {
                    prev->next = entry->next;
                    free(entry);
                } else {
                    if (entry->next == NULL) {
                        entry->valid = 0;
                    } else {
                        entry = entry->next;
                        memcpy(&(table->table[key]), entry,
                               sizeof(virHashEntry));
                        free(entry);
                    }
                }
                table->nbElems--;
                return (0);
            }
            prev = entry;
        }
        return (-1);
    }
}