hash.c

gridgen是一款强大的网格生成程序

/******************************************************************************
 *
 * File:           hash.c
 *
 * Purpose:        Hash table implementation
 *
 * Author:         Jerry Coffin
 *
 * Description:    Public domain code by Jerry Coffin, with improvements by
 *                 HenkJan Wolthuis.
 *                 Date last modified: 05-Jul-1997
 *
 * Revisions:      18-09-2002 -- modified by Pavel Sakov
 *
 *****************************************************************************/

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

#define INT_PER_DOUBLE 2
#define BYTE_PER_INT 4

/** A hash table consists of an array of these buckets.
 */
typedef struct ht_bucket {
    void* key;
    void* data;
    int id;                     /* unique id -- just in case */
    struct ht_bucket* next;
} ht_bucket;

/** Hash table structure. 
 * Note that more nodes than `size' can be inserted in the table,
 * but performance degrades as this happens.
 */
struct hashtable {
    int size;                   /* table size */
    int n;                      /* current number of entries */
    int naccum;                 /* number of inserted entries */
    int nhash;                  /* number of used table elements */
    ht_keycp cp;
    ht_keyeq eq;
    ht_key2hash hash;
    ht_bucket** table;
};

/* Creates a hashtable of specified size.
 */
hashtable* ht_create(int size, ht_keycp cp, ht_keyeq eq, ht_key2hash hash)
{
    hashtable* table = malloc(sizeof(hashtable));
    ht_bucket** bucket;
    int i;

    assert(table != NULL);

    if (size <= 0) {
        free(table);
        return NULL;
    }

    table->size = size;
    table->table = malloc(sizeof(ht_bucket*) * size);
    assert(table->table != NULL);
    bucket = table->table;

    if (bucket == NULL) {
        free(table);
        return NULL;
    }

    for (i = 0; i < size; ++i)
        bucket[i] = NULL;
    table->n = 0;
    table->naccum = 0;
    table->nhash = 0;
    table->eq = eq;
    table->cp = cp;
    table->hash = hash;

    return table;
}

/* Destroys a hash table. 
 * (Take care of deallocating data by ht_process() prior to destroying the
 * table if necessary.)
 *
 * @param table Hash table to be destroyed
 */
void ht_destroy(hashtable* table)
{
    int i;

    if (table == NULL)
        return;

    for (i = 0; i < table->size; ++i) {
        ht_bucket* bucket;

        for (bucket = (table->table)[i]; bucket != NULL;) {
            ht_bucket* prev = bucket;

            free(bucket->key);
            bucket = bucket->next;
            free(prev);
        }
    }

    free(table->table);
    free(table);
}

/* Inserts a new entry into the hash table.
 *
 * @param table The hash table
 * @param key Ponter to entry's key
 * @param data Pointer to associated data
 * @return Pointer to the old data associated with the key, NULL if the key
 *         wasn't in the table previously
 */
void* ht_insert(hashtable* table, void* key, void* data)
{
    unsigned int val = table->hash(key) % table->size;
    ht_bucket* bucket;

    /*
     * NULL means this bucket hasn't been used yet.  We'll simply allocate
     * space for our new bucket and put our data there, with the table
     * pointing at it. 
     */
    if ((table->table)[val] == NULL) {
        bucket = malloc(sizeof(ht_bucket));
        assert(bucket != NULL);

        bucket->key = table->cp(key);
        bucket->next = NULL;
        bucket->data = data;
        bucket->id = table->naccum;

        (table->table)[val] = bucket;
        table->n++;
        table->naccum++;
        table->nhash++;

        return NULL;
    }

    /*
     * This spot in the table is already in use.  See if the current string
     * has already been inserted, and if so, return corresponding data. 
     */
    for (bucket = (table->table)[val]; bucket != NULL; bucket = bucket->next)
        if (table->eq(key, bucket->key) == 1) {
            void* old_data = bucket->data;

            bucket->data = data;
            bucket->id = table->naccum;
            table->naccum++;

            return old_data;
        }

    /*
     * This key must not be in the table yet.  We'll add it to the head of
     * the list at this spot in the hash table.  Speed would be slightly
     * improved if the list was kept sorted instead.  In this case, this
     * code would be moved into the loop above, and the insertion would take 
     * place as soon as it was determined that the present key in the list
     * was larger than this one. 
     */
    bucket = (ht_bucket*) malloc(sizeof(ht_bucket));
    assert(bucket != NULL);
    bucket->key = table->cp(key);
    bucket->data = data;
    bucket->next = (table->table)[val];
    bucket->id = table->naccum;

    (table->table)[val] = bucket;
    table->n++;
    table->naccum++;

    return NULL;
}

/* Returns a pointer to the data associated with a key.  If the key has
 * not been inserted in the table, returns NULL.
 *
 * @param table The hash table
 * @param key The key
 * @return The associated data or NULL
 */
void* ht_find(hashtable* table, void* key)
{
    unsigned int val = table->hash(key) % table->size;
    ht_bucket* bucket;

    if ((table->table)[val] == NULL)
        return NULL;

    for (bucket = (table->table)[val]; bucket != NULL; bucket = bucket->next)
        if (table->eq(key, bucket->key) == 1)
            return bucket->data;

    return NULL;
}

/* Deletes an entry from the table.  Returns a pointer to the data that
 * was associated with the key so that the calling code can dispose it
 * properly.
 *
 * @param table The hash table
 * @param key The key
 * @return The associated data or NULL
 */
void* ht_delete(hashtable* table, void* key)
{
    unsigned int val = table->hash(key) % table->size;
    ht_bucket* prev;
    ht_bucket* bucket;
    void* data;

    if ((table->table)[val] == NULL)
        return NULL;

    /*
     * Traverse the list, keeping track of the previous node in the list.
     * When we find the node to delete, we set the previous node's next
     * pointer to point to the node after ourself instead.  We then delete
     * the key from the present node, and return a pointer to the data it
     * contains. 
     */
    for (prev = NULL, bucket = (table->table)[val]; bucket != NULL; prev = bucket, bucket = bucket->next) {
        if (table->eq(key, bucket->key) == 1) {
            data = bucket->data;
            if (prev != NULL)
                prev->next = bucket->next;
            else {
                /*
                 * If 'prev' still equals NULL, it means that we need to
                 * delete the first node in the list. This simply consists
                 * of putting our own 'next' pointer in the array holding
                 * the head of the list.  We then dispose of the current
                 * node as above. 
                 */
                (table->table)[val] = bucket->next;
                table->nhash--;
            }
            free(bucket->key);
            free(bucket);
            table->n--;

            return data;
        }
    }

    /*
     * If we get here, it means we didn't find the item in the table. Signal 
     * this by returning NULL. 
     */
    return NULL;
}

/* For each entry, calls a specified function with corresponding data as a
 * parameter.
 *
 * @param table The hash table
 * @param func The action function
 */
void ht_process(hashtable* table, void (*func) (void*))
{
    int i;

    for (i = 0; i < table->size; ++i)
        if ((table->table)[i] != NULL) {
            ht_bucket* bucket;

            for (bucket = (table->table)[i]; bucket != NULL; bucket = bucket->next)
                func(bucket->data);
        }
}

/* 
 * functions for for string keys 
 */

static unsigned int strhash(void* key)
{
    char* str = key;
    unsigned int hashvalue = 0;

    while (*str != 0) {
        hashvalue ^= *(unsigned int*) str;
        hashvalue <<= 1;
        str++;
    }

    return hashvalue;
}

static void* strcp(void* key)
{
    return strdup(key);
}

static int streq(void* key1, void* key2)
{
    return !strcmp(key1, key2);
}

/* functions for for double keys */

static unsigned int d1hash(void* key)
{
    unsigned int* v = key;

#if INT_PER_DOUBLE == 2
    return v[0] + v[1];
#else
#error not implemented
#endif
}

static void* d1cp(void* key)
{
    double* newkey = malloc(sizeof(double));

    *newkey = *(double*) key;

    return newkey;
}

static int d1eq(void* key1, void* key2)
{
    return *(double*) key1 == *(double*) key2;
}

/* 
 * functions for for double[2] keys 
 */

static unsigned int d2hash(void* key)
{
    unsigned int* v = key;

#if INT_PER_DOUBLE == 2
    /*
     * PS: here multiplications suppose to make (a,b) and (b,a) generate
     * different hash values 
     */
    return v[0] + v[1] + v[2] * 3 + v[3] * 7;
#else
#error not implemented
#endif
}

static void* d2cp(void* key)
{
    double* newkey = malloc(sizeof(double) * 2);

    newkey[0] = ((double*) key)[0];
    newkey[1] = ((double*) key)[1];

    return newkey;
}

static int d2eq(void* key1, void* key2)
{
    return (((double*) key1)[0] == ((double*) key2)[0]) && (((double*) key1)[1] == ((double*) key2)[1]);
}

/* 
 * functions for for int[1] keys 
 */

static unsigned int i1hash(void* key)
{