Magazyn Amiga 13/MA_Cover_13.bin/source/c/nfsd/src/hashtable.c

C/C++ Source or Header | 1999-11-29 | 5.4 KB | 232 lines

/*  Routines to manage hash tables

    ©1999 Joseph Walton

    This software is distributed under the terms of the GNU General Public
    License; either version 2 of the License, or (at your option) any
    later version.
*/

/*
    Many features are currently commented out - they're not being used
     at the moment.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "hashtable.h"
#include "nfsd.h"
#include "memory.h"

struct HashTable {
    HashFunc ht_HashFunc;
    EqualsFunc ht_EqualsFunc;
    LONG ht_NumEntries;
    LONG ht_NumBuckets;
    struct Entry **ht_Table;
};

struct Entry {
    ULONG e_HashCode;
    APTR e_Key;
    APTR e_Data;
    struct Entry *e_Next;
};

#define ALLOCTABLE(n) ((struct Entry **)AllocVecPooled((n) * sizeof(struct Entry *)))
#define CLEARTABLE(t, n) (memset((t), 0, sizeof(struct Entry *) * (n)))
#define BUCKETFOR(ht,c) ((ht)->ht_Table[(c) % (ht)->ht_NumBuckets])
#define MIN_SIZE 11

static void insertEntry(struct HashTable *ht, struct Entry *e);
static void resizeTable(struct HashTable *ht);

struct HashTable *htMakeNew(HashFunc hf, EqualsFunc ef)
{
    struct HashTable *ht = (struct HashTable *)AllocVecPooled(sizeof(struct HashTable));
    if (ht) {
        ht->ht_HashFunc = hf;
        ht->ht_EqualsFunc = ef;
        ht->ht_NumEntries = 0;
        ht->ht_NumBuckets = MIN_SIZE;
        ht->ht_Table = ALLOCTABLE(MIN_SIZE);
        if (ht->ht_Table) {
            CLEARTABLE(ht->ht_Table, MIN_SIZE);
            return ht;
        }
        FreeVecPooled(ht);
    }
    return NULL;
}

/* I never explicitly free the hashtables I'm using - the mempools
    take care of this.

void htFree(struct HashTable *ht, DataFreeFunc dff)
{
    int i;
    for (i = 0 ; i < ht->ht_NumBuckets ; i++) {
        struct Entry *e = BUCKETFOR(ht, i);
        while (e) {
            struct Entry *next = e->e_Next;
            if (dff)
                dff(e->e_Data);
            FreeVecPooled(e);
            e = next;
        }
    }
    FreeVecPooled(ht->ht_Table);
    FreeVecPooled(ht);
}
*/

BOOL htAdd(struct HashTable *ht, APTR key, APTR data)
{
    struct Entry *e = (struct Entry *)AllocVecPooled(sizeof(struct Entry));
    if (e) {
        ULONG hashCode = ht->ht_HashFunc(key);

        e->e_HashCode = hashCode;
        e->e_Key = key;
        e->e_Data = data;

        insertEntry(ht, e);
        resizeTable(ht);

        return TRUE;
    }
    return FALSE;
}

static void insertEntry(struct HashTable *ht, struct Entry *e)
{
    struct Entry **list;
    list = &BUCKETFOR(ht, e->e_HashCode);
    e->e_Next = *list;
    *list = e;
    ht->ht_NumEntries++;
}

static void resizeTable(struct HashTable *ht)
{
    /* Is it outside reasonable bounds? */
    int size = ht->ht_NumBuckets,
        entries = ht->ht_NumEntries;

    if (((entries > MIN_SIZE) && (entries < (size / 3))) || (entries > (3 * size))) {
        struct Entry **newTable;
        int newSize = entries | 1; /* Make it odd, just for luck */

/*
        printf("Outside reasonable range. Is %d, should be %d\n", size, newSize);
        printf("before: avg = %f, sd = %f\n",
               (float)ht->ht_NumEntries / (float)ht->ht_NumBuckets,
               getStdDev(ht));
*/

        newTable = ALLOCTABLE(newSize);
        if (newTable) {
            struct Entry **oldTable = ht->ht_Table;
            int oldSize = ht->ht_NumBuckets;
            int i;

            CLEARTABLE(newTable, newSize);
            ht->ht_NumEntries = 0;
            ht->ht_Table = newTable;
            ht->ht_NumBuckets = newSize;

            /* Move over all the entries */
            for (i = 0 ; i < oldSize ; i++) {
                struct Entry *e = oldTable[i];
                while (e) {
                    struct Entry *next = e->e_Next;
                    insertEntry(ht, e);
                    e = next;
                }
            }
            FreeVecPooled(oldTable);
            DEBUG(puts("Hashtable size succesfully changed"));
        }
/*
        printf("after: avg = %f, sd = %f\n",
            (float)ht->ht_NumEntries / (float)ht->ht_NumBuckets,
            getStdDev(ht));
*/
    }
}

APTR htGet(struct HashTable *ht, APTR key)
{
    struct Entry *e;
    ULONG hashCode;

    hashCode = ht->ht_HashFunc(key);

    e = BUCKETFOR(ht, hashCode);

    while (e) {
        if (ht->ht_EqualsFunc(key, e->e_Key)) {
            return e->e_Data;
        }
        e = e->e_Next;
    }
    return NULL;
}

APTR htRemove(struct HashTable *ht, APTR key)
{
    struct Entry **e;
    ULONG hashCode;

    hashCode = ht->ht_HashFunc(key);
    e = &BUCKETFOR(ht, hashCode);

    while (*e) {
        if (ht->ht_EqualsFunc(key, (*e)->e_Key)) {
            struct Entry *must_go = *e;
            APTR data = must_go->e_Data;

            *e = (*e)->e_Next;
            FreeVecPooled(must_go);
            ht->ht_NumEntries--;
            resizeTable(ht);

            return data;
        }
        e = &(*e)->e_Next;
    }
    return NULL;
}

int htGetSize(struct HashTable *ht)
{
    return ht->ht_NumEntries;
}

/* Gather some statistics

#include <math.h>
double getStdDev(struct HashTable *ht)
{
    struct Entry *e;
    int i;
    double avgLength = (float)ht->ht_NumEntries / (float)ht->ht_NumBuckets;
    double sum = 0.0;

    for (i = 0 ; i < ht->ht_NumBuckets ; i++) {
        int l = 0;
        e = BUCKETFOR(ht, i);
        while (e) {
            l++;
            e = e->e_Next;
        }

        sum += (avgLength - (double)l) * (avgLength - (double)l);
    }

    return sqrt(sum / (double)ht->ht_NumBuckets);
}
*/