Category : C Source Code
Archive   : HASHTAB.ZIP
Filename : HASH.C

 
Output of file : HASH.C contained in archive : HASHTAB.ZIP
#ifndef lint
static char rcsid[] = "$Id: hash.c,v 1.2 90/10/02 13:32:23 chris Exp $";
#endif

/*
* Hash table routines.
*/

#include
#include
#include
#include "hash.h"

/*
* Hash table entries keep track of name=value pairs.
* The names may be numeric IDs instead (by having a null name).
*/
struct hashent {
struct hashent *h_next;/* next in chain */
int h_hash; /* hash value or ID */
char *h_name; /* name (null if from numeric ID) */
char *h_value; /* value */
};

struct hashtab {
int ht_size; /* size (power of 2) */
int ht_mask; /* == ht_size - 1 */
int ht_used; /* number of entries used */
int ht_lim; /* when to expand */
struct hashent **ht_tab;/* base of table */
char ht_name[1]; /* table name; actually larger */
};

extern char *progname;

char *
emalloc(n)
size_t n;
{
register char *p = malloc(n);

if (p == NULL) {
(void) fprintf(stderr, "%s: out of memory\n", progname);
exit(1);
}
return (p);
}

/* round up to next multiple of y, where y is a power of 2 */
#define ROUND(x, y) (((x) + (y) - 1) & ~((y) - 1))

/* compute a `good' number of objects to allocate via malloc */
int
goodnumber(n, s)
int n;
size_t s;
{

/* 16384 is a guess at a good page size for malloc */
/* 32 is a guess at malloc's overhead */
return ((int)((ROUND(n * s + 32, 16384) - 32) / s));
}

/*
* Make a new hash table.
*/
struct hashtab *
ht_new(name)
char *name;
{
register struct hashtab *ht;
register struct hashent **h;
register int n;

ht = (struct hashtab *)emalloc(sizeof *ht + strlen(name));
ht->ht_tab = h = (struct hashent **)emalloc(128 * sizeof *h);
ht->ht_size = 128;
ht->ht_mask = 127;
for (n = 128; --n >= 0;)
*h++ = NULL;
ht->ht_used = 0;
ht->ht_lim = (128 * 2) / 3;
(void) strcpy(ht->ht_name, name);
return (ht);
}

/*
* Expand an existing hash table.
*/
static void
ht_expand(ht)
register struct hashtab *ht;
{
register int n = ht->ht_size * 2, i;
register struct hashent *p, **h, **oldh, *q;

h = (struct hashent **)emalloc(n * sizeof *h);
for (i = n; --i >= 0;)
*h++ = NULL;
h -= n;
oldh = ht->ht_tab;
n--;
for (i = ht->ht_size; --i >= 0;) {
for (p = *oldh++; p != NULL; p = q) {
q = p->h_next;
p->h_next = h[p->h_hash & n];
h[p->h_hash & n] = p;
}
}
free((char *)ht->ht_tab);
ht->ht_tab = h;
ht->ht_mask = n;
ht->ht_size = ++n;
ht->ht_lim = (n * 2) / 3;
}

/*
* Make a new hash entry. Its h_next will be NULL.
*/
static struct hashent *
newhashent(hash, name, value)
int hash;
char *name, *value;
{
static struct hashent *hfree;
register struct hashent *h;
register int n, nalloc;

if ((h = hfree) != NULL)
hfree = h->h_next;
else {
nalloc = goodnumber(2, sizeof *h); /* need at least 2 */
hfree = h = (struct hashent *)emalloc(nalloc * sizeof *h) + 1;
for (n = nalloc - 2; --n >= 0; h++)
h->h_next = h + 1;
h->h_next = NULL;
h -= nalloc - 1;
}
h->h_next = NULL;
h->h_hash = hash;
h->h_name = name;
h->h_value = value;
return (h);
}

#define HASH(str, h, p) \
for (p = str, h = 0; *p;) h = (h << 5) - h + *p++

/*
* Look up a name=value.
*/
char *
ht_nget(ht, name)
register struct hashtab *ht;
char *name;
{
register char *p;
register int hash;
register struct hashent *h;

HASH(name, hash, p);
p = name;
for (h = ht->ht_tab[hash & ht->ht_mask]; h != NULL; h = h->h_next)
if (h->h_hash == hash && h->h_name != NULL &&
strcmp(h->h_name, p) == 0)
return (h->h_value);
return (NULL);
}

/*
* Look up an ID=value.
*/
char *
ht_iget(ht, id)
register struct hashtab *ht;
register int id;
{
register struct hashent *h;

for (h = ht->ht_tab[id & ht->ht_mask]; h != NULL; h = h->h_next)
if (h->h_hash == id && h->h_name == NULL)
return (h->h_value);
return (NULL);
}

/*
* Insert (do not clobber) a name=value.
* Return zero on success.
*/
int
ht_nins(ht, name, value)
register struct hashtab *ht;
char *name, *value;
{
register char *p;
register int hash;
register struct hashent *h, **hp;

HASH(name, hash, p);
p = name;
for (hp = &ht->ht_tab[hash & ht->ht_mask]; (h = *hp) != NULL;
hp = &h->h_next)
if (h->h_hash == hash && h->h_name != NULL &&
strcmp(h->h_name, p) == 0)
return (-1);
*hp = newhashent(hash, name, value);
if (++ht->ht_used > ht->ht_lim)
ht_expand(ht);
return (0);
}

/*
* Insert (do not clobber) an ID=value.
* Return zero on success.
*/
int
ht_iins(ht, id, value)
register struct hashtab *ht;
register int id;
char *value;
{
register struct hashent *h, **hp;

for (hp = &ht->ht_tab[id & ht->ht_mask]; (h = *hp) != NULL;
hp = &h->h_next)
if (h->h_hash == id && h->h_name == NULL)
return (-1);
*hp = newhashent(id, (char *)NULL, value);
if (++ht->ht_used > ht->ht_lim)
ht_expand(ht);
return (0);
}

/*
* Stash a copy of a string away; it will never be freed.
*/
static char *
poolstr(s)
char *s;
{
register char *p;
register size_t l = strlen(s) + 1;
static char *poolp;
static size_t nleft;

if (nleft < l)
poolp = emalloc(nleft = goodnumber(l, 1));
bcopy(s, p = poolp, l);
poolp += l;
return (p);
}

/*
* Generate a single unique copy of the given string.
*/
char *
string(s)
char *s;
{
register char *p;
register int hash;
register struct hashent *h, **hp;
static struct hashtab *ht;

if (ht == NULL)
ht = ht_new("strings");
HASH(s, hash, p);
p = s;
for (hp = &ht->ht_tab[hash & ht->ht_mask]; (h = *hp) != NULL;
hp = &h->h_next)
if (h->h_hash == hash && strcmp(h->h_name, p) == 0)
return (h->h_name);
*hp = h = newhashent(hash, poolstr(s), (char *)NULL);
if (++ht->ht_used > ht->ht_lim)
ht_expand(ht);
return (h->h_name);
}

/*
* Call fn on all the name=value pairs.
*/
void
ht_niterate(ht, fn)
struct hashtab *ht;
register void (*fn)();
{
register struct hashent *h, **hp;
register int n;

for (n = ht->ht_size, hp = ht->ht_tab; --n >= 0;)
for (h = *hp++; h != NULL; h = h->h_next)
if (h->h_name != NULL)
(*fn)(h->h_name, h->h_value);
}

/*
* Call fn on all the id=value pairs.
*/
void
ht_iiterate(ht, fn)
struct hashtab *ht;
register void (*fn)();
{
register struct hashent *h, **hp;
register int n;

for (n = ht->ht_size, hp = ht->ht_tab; --n >= 0;)
for (h = *hp++; h != NULL; h = h->h_next)
if (h->h_name == NULL)
(*fn)(h->h_hash, h->h_value);
}


  3 Responses to “Category : C Source Code
Archive   : HASHTAB.ZIP
Filename : HASH.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/