Source Code 1992 March/Source_Code_CD-ROM_Walnut_Creek_March_1992.iso/usenet/altsrcs/1/1969

Text File | 1990-12-28 | 10.0 KB | 424 lines

Newsgroups: alt.sources
From: [e-mail] (Chris Torek)
Subject: [comp.lang.c] Re: hash function for text in C
Message-ID: <[e-mail]>
Date: Thu, 18 Oct 90 18:44:51 GMT

Archive-name: hash/18-Oct-90
Original-posting-by: [e-mail] (Chris Torek)
Original-subject: Re: hash function for text in C
Reposted-by: [e-mail] (Edward Vielmetti)

[Reposted from comp.lang.c.
Comments on this service to [e-mail] (Edward Vielmetti).]

The following implements expanding chained hash tables for strings and
numbers.  This is unmodified from a special-purpose program (having to
do with reading a large number of files with name=id pairs and doing
various operations on them).  Chain lengths are not monitored; instead,
the table is invariably expanded whenever it becomes 2/3 full.  Entries
may be neither removed nor modified.

An essentially-unrelated function called `string' maintains a string
pool such that string(x) == string(y) iff strcmp(x,y)==0 (the program
typically stores each name several times, and often needs to test for
name equality, so this helps there).

: Run this shell script with "sh" not "csh"
PATH=/bin:/usr/bin:/usr/ucb:/etc:$PATH
export PATH
all=false
if [ x$1 = x-a ]; then
    all=true
fi
echo Extracting hash.h
sed 's/^X//' <<'//go.sysin dd *' >hash.h
X/*
X * $Id: hash.h,v 1.1 90/09/24 23:58:38 chris Exp $
X *
X * Hash table entries keep track of name (or id) = value pairs.
X * Values are simply pointers.  Hash tables themselves are named
X * (for debugging).
X */
X
Xstruct    hashtab;
X
X/*
X * The `ins' functions return nonzero if the old value existed,
X * without changing the value.
X * The iterate functions calls a given function with name,value
X * or id,value pairs.
X */
Xstruct    hashtab *ht_new();    /* given name, create new hash table */
Xchar    *ht_nget();        /* given table and name, get value */
Xchar    *ht_iget();        /* given table and ID, get value */
Xint    ht_nins();        /* given table and name, insert new value */
Xint    ht_iins();        /* given table and id, insert new value */
Xvoid    ht_niterate();        /* given table and function, iterate */
Xvoid    ht_iiterate();        /* given table and function, iterate */
X
X/*
X * Some things that ought not to be here, but are anyway.
X * goodnumber() takes a number of objects and a size and returns
X * a new number of objects, such that malloc(goodnumber(n,size)*size)
X * calls malloc with a `good' size value (resulting in less wasted
X * memory).  emalloc is malloc with program-abort on out-of-memory.
X * string() makes a `read-only' copy of a string, reusing the previous
X * copy if any.
X */
Xint    goodnumber();        /* given n & sizeof, return new n */
Xchar    *emalloc();        /* malloc, exit on error */
Xchar    *string();        /* make an `ideal' copy of a string */
//go.sysin dd *
if [ `wc -c < hash.h` != 1415 ]; then
    made=false
    echo error transmitting hash.h --
    echo length should be 1415, not `wc -c < hash.h`
else
    made=true
fi
if $all; then
    echo '    Changing owner to bin'
    chown bin hash.h
else
    echo '    Original owner was bin'
fi
if $made; then
    chmod 444 hash.h
    echo -n '    '; ls -ld hash.h
fi
echo Extracting hash.c
sed 's/^X//' <<'//go.sysin dd *' >hash.c
X#ifndef lint
Xstatic char rcsid[] = "$Id: hash.c,v 1.2 90/10/02 13:32:23 chris Exp $";
X#endif
X
X/*
X * Hash table routines.
X */
X
X#include <stdio.h>
X#include <stdlib.h>
X#include <string.h>
X#include "hash.h"
X
X/*
X * Hash table entries keep track of name=value pairs.
X * The names may be numeric IDs instead (by having a null name).
X */
Xstruct hashent {
X    struct    hashent *h_next;/* next in chain */
X    int    h_hash;        /* hash value or ID */
X    char    *h_name;    /* name (null if from numeric ID) */
X    char    *h_value;    /* value */
X};
X
Xstruct hashtab {
X    int    ht_size;    /* size (power of 2) */
X    int    ht_mask;    /* == ht_size - 1 */
X    int    ht_used;    /* number of entries used */
X    int    ht_lim;        /* when to expand */
X    struct    hashent **ht_tab;/* base of table */
X    char    ht_name[1];    /* table name; actually larger */
X};
X
Xextern char *progname;
X
Xchar *
Xemalloc(n)
X    size_t n;
X{
X    register char *p = malloc(n);
X
X    if (p == NULL) {
X        (void) fprintf(stderr, "%s: out of memory\n", progname);
X        exit(1);
X    }
X    return (p);
X}
X
X/* round up to next multiple of y, where y is a power of 2 */
X#define    ROUND(x, y) (((x) + (y) - 1) & ~((y) - 1))
X
X/* compute a `good' number of objects to allocate via malloc */
Xint
Xgoodnumber(n, s)
X    int n;
X    size_t s;
X{
X
X    /* 16384 is a guess at a good page size for malloc */
X    /* 32 is a guess at malloc's overhead */
X    return ((int)((ROUND(n * s + 32, 16384) - 32) / s));
X}
X
X/*
X * Make a new hash table.
X */
Xstruct hashtab *
Xht_new(name)
X    char *name;
X{
X    register struct hashtab *ht;
X    register struct hashent **h;
X    register int n;
X
X    ht = (struct hashtab *)emalloc(sizeof *ht + strlen(name));
X    ht->ht_tab = h = (struct hashent **)emalloc(128 * sizeof *h);
X    ht->ht_size = 128;
X    ht->ht_mask = 127;
X    for (n = 128; --n >= 0;)
X        *h++ = NULL;
X    ht->ht_used = 0;
X    ht->ht_lim = (128 * 2) / 3;
X    (void) strcpy(ht->ht_name, name);
X    return (ht);
X}
X
X/*
X * Expand an existing hash table.
X */
Xstatic void
Xht_expand(ht)
X    register struct hashtab *ht;
X{
X    register int n = ht->ht_size * 2, i;
X    register struct hashent *p, **h, **oldh, *q;
X
X    h = (struct hashent **)emalloc(n * sizeof *h);
X    for (i = n; --i >= 0;)
X        *h++ = NULL;
X    h -= n;
X    oldh = ht->ht_tab;
X    n--;
X    for (i = ht->ht_size; --i >= 0;) {
X        for (p = *oldh++; p != NULL; p = q) {
X            q = p->h_next;
X            p->h_next = h[p->h_hash & n];
X            h[p->h_hash & n] = p;
X        }
X    }
X    free((char *)ht->ht_tab);
X    ht->ht_tab = h;
X    ht->ht_mask = n;
X    ht->ht_size = ++n;
X    ht->ht_lim = (n * 2) / 3;
X}
X
X/*
X * Make a new hash entry.  Its h_next will be NULL.
X */
Xstatic struct hashent *
Xnewhashent(hash, name, value)
X    int hash;
X    char *name, *value;
X{
X    static struct hashent *hfree;
X    register struct hashent *h;
X    register int n, nalloc;
X
X    if ((h = hfree) != NULL)
X        hfree = h->h_next;
X    else {
X        nalloc = goodnumber(2, sizeof *h);    /* need at least 2 */
X        hfree = h = (struct hashent *)emalloc(nalloc * sizeof *h) + 1;
X        for (n = nalloc - 2; --n >= 0; h++)
X            h->h_next = h + 1;
X        h->h_next = NULL;
X        h -= nalloc - 1;
X    }
X    h->h_next = NULL;
X    h->h_hash = hash;
X    h->h_name = name;
X    h->h_value = value;
X    return (h);
X}
X
X#define    HASH(str, h, p) \
X    for (p = str, h = 0; *p;) h = (h << 5) - h + *p++
X
X/*
X * Look up a name=value.
X */
Xchar *
Xht_nget(ht, name)
X    register struct hashtab *ht;
X    char *name;
X{
X    register char *p;
X    register int hash;
X    register struct hashent *h;
X
X    HASH(name, hash, p);
X    p = name;
X    for (h = ht->ht_tab[hash & ht->ht_mask]; h != NULL; h = h->h_next)
X        if (h->h_hash == hash && h->h_name != NULL &&
X            strcmp(h->h_name, p) == 0)
X            return (h->h_value);
X    return (NULL);
X}
X
X/*
X * Look up an ID=value.
X */
Xchar *
Xht_iget(ht, id)
X    register struct hashtab *ht;
X    register int id;
X{
X    register struct hashent *h;
X
X    for (h = ht->ht_tab[id & ht->ht_mask]; h != NULL; h = h->h_next)
X        if (h->h_hash == id && h->h_name == NULL)
X            return (h->h_value);
X    return (NULL);
X}
X
X/*
X * Insert (do not clobber) a name=value.
X * Return zero on success.
X */
Xint
Xht_nins(ht, name, value)
X    register struct hashtab *ht;
X    char *name, *value;
X{
X    register char *p;
X    register int hash;
X    register struct hashent *h, **hp;
X
X    HASH(name, hash, p);
X    p = name;
X    for (hp = &ht->ht_tab[hash & ht->ht_mask]; (h = *hp) != NULL;
X         hp = &h->h_next)
X        if (h->h_hash == hash && h->h_name != NULL &&
X            strcmp(h->h_name, p) == 0)
X            return (-1);
X    *hp = newhashent(hash, name, value);
X    if (++ht->ht_used > ht->ht_lim)
X        ht_expand(ht);
X    return (0);
X}
X
X/*
X * Insert (do not clobber) an ID=value.
X * Return zero on success.
X */
Xint
Xht_iins(ht, id, value)
X    register struct hashtab *ht;
X    register int id;
X    char *value;
X{
X    register struct hashent *h, **hp;
X
X    for (hp = &ht->ht_tab[id & ht->ht_mask]; (h = *hp) != NULL;
X         hp = &h->h_next)
X        if (h->h_hash == id && h->h_name == NULL)
X            return (-1);
X    *hp = newhashent(id, (char *)NULL, value);
X    if (++ht->ht_used > ht->ht_lim)
X        ht_expand(ht);
X    return (0);
X}
X
X/*
X * Stash a copy of a string away; it will never be freed.
X */
Xstatic char *
Xpoolstr(s)
X    char *s;
X{
X    register char *p;
X    register size_t l = strlen(s) + 1;
X    static char *poolp;
X    static size_t nleft;
X
X    if (nleft < l)
X        poolp = emalloc(nleft = goodnumber(l, 1));
X    bcopy(s, p = poolp, l);
X    poolp += l;
X    return (p);
X}
X
X/*
X * Generate a single unique copy of the given string.
X */
Xchar *
Xstring(s)
X    char *s;
X{
X    register char *p;
X    register int hash;
X    register struct hashent *h, **hp;
X    static struct hashtab *ht;
X
X    if (ht == NULL)
X        ht = ht_new("strings");
X    HASH(s, hash, p);
X    p = s;
X    for (hp = &ht->ht_tab[hash & ht->ht_mask]; (h = *hp) != NULL;
X         hp = &h->h_next)
X        if (h->h_hash == hash && strcmp(h->h_name, p) == 0)
X            return (h->h_name);
X    *hp = h = newhashent(hash, poolstr(s), (char *)NULL);
X    if (++ht->ht_used > ht->ht_lim)
X        ht_expand(ht);
X    return (h->h_name);
X}
X
X/*
X * Call fn on all the name=value pairs.
X */
Xvoid
Xht_niterate(ht, fn)
X    struct hashtab *ht;
X    register void (*fn)();
X{
X    register struct hashent *h, **hp;
X    register int n;
X
X    for (n = ht->ht_size, hp = ht->ht_tab; --n >= 0;)
X        for (h = *hp++; h != NULL; h = h->h_next)
X            if (h->h_name != NULL)
X                (*fn)(h->h_name, h->h_value);
X}
X
X/*
X * Call fn on all the id=value pairs.
X */
Xvoid
Xht_iiterate(ht, fn)
X    struct hashtab *ht;
X    register void (*fn)();
X{
X    register struct hashent *h, **hp;
X    register int n;
X
X    for (n = ht->ht_size, hp = ht->ht_tab; --n >= 0;)
X        for (h = *hp++; h != NULL; h = h->h_next)
X            if (h->h_name == NULL)
X                (*fn)(h->h_hash, h->h_value);
X}
//go.sysin dd *
if [ `wc -c < hash.c` != 6291 ]; then
    made=false
    echo error transmitting hash.c --
    echo length should be 6291, not `wc -c < hash.c`
else
    made=true
fi
if $all; then
    echo '    Changing owner to bin'
    chown bin hash.c
else
    echo '    Original owner was bin'
fi
if $made; then
    chmod 444 hash.c
    echo -n '    '; ls -ld hash.c
fi
--
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept ([phone])
Domain:    [e-mail]    Path:    uunet!mimsy!chris