Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/unix/volume26/ns2tab/part02/hash.c

C/C++ Source or Header | 1993-04-04 | 11.3 KB | 483 lines

#include <stdio.h>

/*
**
**    Copyright (c) 1987, Robert L. McQueer
**        All Rights Reserved
**
** Permission granted for use, modification and redistribution of this
** software provided that no use is made for commercial gain without the
** written consent of the author, that all copyright notices remain intact,
** and that all changes are clearly documented.  No warranty of any kind
** concerning any use which may be made of this software is offered or implied.
**
*/

/*
** generic hash table routines.
**
**    htab_init - initialize a new hash table
**    htab_free - destroy a hash table, freeing associated memory
**    htab_clear - remove all hash table entries
**    htab_find - find entry
**    htab_del - delete entry
**    htab_enter - enter item into table
**    htab_list - scan hash table entries.
**
** Multiple hash tables may be used.  Caller may provide key comparison
** and hash routines, or use defaults.
*/

/*
** HASHMAGIC define may be used to compile a version of these routines
** which will catch bad context blocks passed in by client routines
** through a magic number check.  If defined, HASHMAGIC should be the
** actual number to use for a magic number.  Configurable so that you
** may avoid the overhead of checking it all the time in these routines
** which may have high entry rates.
*/

/*
** allocation: nodes are allocated starting with a block of ALLOCINIT,
** doubling the size for the next allocation as long as the size is strictly
** less than ALLOCLIMIT.  If you make ALLOCLIMIT a value encountered by
** successive doubling of ALLOCINIT, that will be the final size, otherwise the
** next doubling larger.
**
** The idea of this stunt is that we don't know whether the caller is going
** to make a lot of entries, or just a few.  So we start out allocating
** just a few nodes at a crack, and as the caller makes more and more
** entries, allocate bigger bunches.  For memory-restrictive environments
** like MS-DOS, one could set ALLOCLIMIT low & simply pay the penalty for
** lots of malloc calls.
*/
#define ALLOCINIT 25
#define ALLOCLIMIT 800

#define MAGCHECK(T,N) if (T->magic != HASHMAGIC) fatal(Merr,N)

typedef struct _htab
{
    struct _htab *next;
    char *key;
    char *data;
} HASHTAB;

typedef struct _faddr
{
    struct _faddr *next;
} FADDR;

/*
** fpool, tpool - tpool is the pool of available nodes.  Every time
** a new block is allocated, one FADDR is allocated along with it.
** The address allocated is coerced into the FADDR and placed on fpool
** to facilitate freeing.
*/

typedef struct
{
#ifdef HASHMAGIC
    int magic;
#endif
    HASHTAB **tab;        /* hash table */
    HASHTAB *tpool;        /* available nodes */
    HASHTAB *srch;        /* current search pointer for htab_list */
    FADDR *fpool;        /* alloc pointers for htab_free */
    int (*afail)();        /* allocation error handler */
    int (*compare)();    /* comparison routine */
    int (*hashfunc)();    /* hash function */
    int size;        /* size of table (length of tab item) */
    int ablock;        /* current allocation block size */
    int srchidx;        /* current table index for htab_list */
} CONTEXT;
#ifdef __STDC__
#include <stdlib.h>
#else
extern char *malloc();
#endif
static HASHTAB * get_node(CONTEXT *);
static int hash(register char *,int);
static int def_afail();

#ifdef HASHMAGIC
static char *Merr = "Bad magic number in hash table context block, %s()";
#endif

/*
** free hash table.  tab is pointer returned by htab_init.
*/
htab_free(void *tab)
{
    register FADDR *ptr, *next;
    int i;
    register CONTEXT *cb;

    cb = (CONTEXT *) tab;

#ifdef HASHMAGIC
    MAGCHECK(cb,"htab_free");
    ++(cb->magic);
#endif

    for (ptr = cb->fpool; ptr != NULL; ptr = next)
    {
        next = ptr->next;
        free ((char *) ptr);
    }

    free (tab);
}

/*
** remove all hash table entries.  Does not free memory, simply restores
** empty table, as if one had called htab_delete on all the keys.  tab is
** pointer returned by htab_init.
*/
htab_clear(void *tab)
{
    register CONTEXT *cb;
    register HASHTAB **tptr;
    register HASHTAB *nptr;
    int i;

    cb = (CONTEXT *) tab;

#ifdef HASHMAGIC
    MAGCHECK(cb,"htab_clear");
#endif

    tptr = cb->tab;

    for (i=0; i < cb->size; ++i,++tptr)
    {
        nptr = *tptr;
        if (nptr == NULL)
            continue;
        while (nptr->next != NULL)
            nptr = nptr->next;
        nptr->next = cb->tpool;
        cb->tpool = *tptr;
        *tptr = NULL;
    }

    /* force any open htab_list's to return empty */
    cb->srch = NULL;
    cb->srchidx = cb->size;
}

/*
** initialize a hash table.  Returns a pointer to be used with other
** calls, NULL for failure.
**
** The hash table will be maintained as a linked list for each node,
** so any number of entries can be made to it, whatever the value for
** size (>100% density is perfectly OK).
**
**    size - size of table.  If hfunc is NULL, will be incremented
**        up to a prime size to suit the type of hash function
**        used by default.  Caller may find out the actual size
**        by calling next_prime().
**
**    allocfail - routine to call in case of memory allocation failure.
**        If NULL, allocation failure will make a call to fatal().
**
**    comp - routine used to compare keys.  returns 0 if equal, non-zero
**        otherwise.  If NULL, strcmp() will be used.  Your own will
**        have to be provided if your keys are something other than
**        strings.  These routines will always call this with the
**        comparison key as the first argument, and the one in the
**        table already as a second argument.  This fact is most
**        useful for making comparisons up to the length of the entered
**        key, for instance.
**
**    hfunc - hash function.  called as (*hfunc)(key, size).  size argument
**        may be ignored if function was written for a specific size.
**        Must return an integer between 0 and size-1.  If NULL, the
**        default hash function is the typical "string-divided-modulo
**        -table-size" algorithm.
*/
void *
htab_init(size,allocfail,comp,hfunc)
int size;
int (*allocfail)();
int (*comp)();
int (*hfunc)();
{
    int def_afail();
    int strcmp();
    int i;
    CONTEXT *cb;

    if (allocfail == NULL)
        allocfail = def_afail;

    if (comp == NULL)
        comp = strcmp;

    if (hfunc == NULL)
    {
        size = next_prime(size);
        hfunc = hash;
    }

    i = sizeof(CONTEXT) + size * sizeof(HASHTAB *);

    if ((cb = (CONTEXT *) malloc(i)) == NULL)
    {
        (*allocfail)();
        return (NULL);
    }

#ifdef HASHMAGIC
    cb->magic = HASHMAGIC;
#endif

    cb->afail = allocfail;
    cb->compare = comp;
    cb->hashfunc = hfunc;
    cb->size = size;
    cb->tab = (HASHTAB **)(cb+1);

    for (i=0; i < cb->size; ++i)
        (cb->tab)[i] = NULL;
    cb->tpool = NULL;
    cb->fpool = NULL;
    cb->ablock = ALLOCINIT;

    /* safety, in case somebody calls htab_list wrong */
    cb->srch = NULL;
    cb->srchidx = size;

    return ((char *) cb);
}


/*
** find an entry in hash table.  The pointer returned is NULL for
** failure, or the data pointer associated with the key in htab_enter.
**
**    tab - table pointer returned by htab_init.
**    s - search key.
*/
char *
htab_find(void *tab,void *s)
{
    register HASHTAB *ptr;
    register CONTEXT *cb;

    cb = (CONTEXT *) tab;

#ifdef HASHMAGIC
    MAGCHECK(cb,"htab_find");
#endif

    for (ptr = (cb->tab)[(*(cb->hashfunc))(s,cb->size)];
                    ptr != NULL; ptr = ptr->next)
    {
        if ((*(cb->compare))(s,ptr->key) == 0)
            return (ptr->data);
    }

    return (NULL);
}

/*
** delete a hash table entry.  Returns 0 for success, <0 for no entry.
**
**    tab - table pointer returned by htab_init.
**    s - search key.
*/
htab_del(void *tab,void *s)
{
    register HASHTAB *ptr;
    register CONTEXT *cb;
    register HASHTAB *pred;
    int idx;

    cb = (CONTEXT *) tab;

#ifdef HASHMAGIC
    MAGCHECK(cb,"htab_del");
#endif

    pred = NULL;
    for (ptr = (cb->tab)[idx = (*(cb->hashfunc))(s,cb->size)];
                        ptr != NULL; ptr = ptr->next)
    {
        if ((*(cb->compare))(s,ptr->key) == 0)
            break;
        pred = ptr;
    }

    if (ptr == NULL)
        return (-1);

    /*
    ** if we're deleting the current search index in the middle
    ** of an htab_list, go to next item.
    */
    if (ptr == cb->srch)
        cb->srch = ptr->next;

    if (pred == NULL)
        (cb->tab)[idx] = ptr->next;
    else
        pred->next = ptr->next;
    ptr->next = cb->tpool;
    cb->tpool = ptr;

    return (0);
}

/*
** enter new item into hash table:
**
**    tab - table pointer from htab_init.
**    s - key.
**    data - data to associate with key.  In most cases, will probably
**        actually be a pointer to some sort of structure known
**        to the caller.
**
**    both s and data should point to storage valid for the entire life of
**    the table.  htab_enter can not allocate copies of either of these
**    things since it does not know their structure (if you provided
**    comparison & hash routines, the key may not actually be a string).
**    htab_enter WILL allocate actual table nodes.  Returns 0 for success,
**    -1 for failure.  Failure return is possible only if allocation
**    failure occurs, and was not set up as fatal in htab_init().
*/
htab_enter(void *tab,void *s,void *data)
{
    register HASHTAB *ptr;
    register CONTEXT *cb;
    int i;

    cb = (CONTEXT *) tab;

#ifdef HASHMAGIC
    MAGCHECK(cb,"htab_enter");
#endif

    if ((ptr = get_node(cb)) == NULL)
        return (-1);

    ptr->next = (cb->tab)[i = (*(cb->hashfunc))(s,cb->size)];
    (cb->tab)[i] = ptr;
    ptr->key = s;
    ptr->data = data;
    return (0);
}

/*
** Routine to scan all hash table entries through successive calls.
** Returns 1 if an entry found, 0 for no more entries.  Will not
** be returned in any particular order comprehensible to the
** calling program (hash table order).
**
**    tab - table pointer from htab_init
**    first - 1 to start scan, 0 on succesive calls.
**    data, key - returned data and key.
**
** Precautions have been taken to allow interleave of this routine with
** htab_del and htab_clear, but the only interleave that truly makes
** sense is to selectively htab_del() entries on some basis as they
** come back from htab_list().  htab_enter()'s in mid list scan may be
** done, but they may or may not show up on following calls, dependent
** on where they were entered in relation to the current list pointer.
**
** This routine sets a global variable on all successful calls:
**
**    int Htab_Index; hash table index entry was found at.
**
** By examining this while scanning the list of entries, a caller may
** obtain statistics on table distribution.  The value will increase
** monotonically as the search proceeds, skipping across indices
** with no entries.
*/

int Htab_Index;

htab_list(void *tab,int first,void **data,void **key)
{
    register CONTEXT *cb;

    cb = (CONTEXT *) tab;

#ifdef HASHMAGIC
    MAGCHECK(cb,"htab_list");
#endif

    if (first)
    {
        cb->srch = NULL;
        cb->srchidx = -1;
    }

    while (cb->srch == NULL)
    {
        ++(cb->srchidx);
        if (cb->srchidx >= cb->size)
            return (0);
        cb->srch = (cb->tab)[cb->srchidx];
    }

    Htab_Index = cb->srchidx;

    *data = (cb->srch)->data;
    *key = (cb->srch)->key;

    cb->srch = (cb->srch)->next;
    return(1);
}

static HASHTAB *
get_node(CONTEXT *cb)
{
    char *addr;
    HASHTAB *ptr;
    int i;

    if (cb->tpool == NULL)
    {
        addr = malloc((cb->ablock)*sizeof(HASHTAB)+sizeof(FADDR));
        if (addr == NULL)
        {
            (*(cb->afail))();
            return (NULL);
        }

        ((FADDR *) addr)->next = cb->fpool;
        cb->fpool = (FADDR *) addr;
        addr += sizeof(FADDR);
        cb->tpool = (HASHTAB *) addr;
        for (i=1; i < cb->ablock; ++i)
            (cb->tpool)[i-1].next = cb->tpool + i;
        (cb->tpool)[i-1].next = NULL;

        if (cb->ablock < ALLOCLIMIT)
            cb->ablock *= 2;
    }

    ptr = cb->tpool;
    cb->tpool = (cb->tpool)->next;
    return (ptr);
}

static int
hash(register char *s,int size)
{
    register long rem;

    for (rem = 0; *s != '\0'; ++s)
        rem = (rem * 128 + *s) % size;
    return(rem);
}

static int
def_afail()
{
    fprintf(stderr,"Memory allocation failure in hash table routines\n");
    exit(1);
}