hashtab.c File Reference

Implements a hash table. More...

#include "standard.h"
#include "lookupa.h"
#include "hashtab.h"
#include "recycle.h"

Go to the source code of this file.

Functions
static void	hgrow (htab *t)
htab *	hcreate (word logsize)
	Create a hash table.
void	hdestroy (htab *t)
	Destroy the hash table and free all its memory.
word	hfind (htab *t, ub1 *key, ub4 keyl)
	Find an item with a given key in the hash table.
word	hadd (htab *t, ub1 *key, ub4 keyl, void *stuff)
	Add an item to the hash table.
word	hdel (htab *t)
word	hfirst (htab *t)
	Position the hash table on the first element.
word	hnbucket (htab *t)
void	hstat (htab *t)

Detailed Description

Implements a hash table.

Author

Bob Jenkins

Date

1996

Keys are unique. Adding an item fails if the key is already there. Keys and items are pointed at, not copied. If you change the value of the key after it is inserted then hfind() will not be able to find it. The hash table maintains a position that can be set and queried. The table length doubles dynamically and never shrinks. The insert that causes table doubling may take a long time. The table length splits when the table length equals the number of items. Comparisons usually take 7 instructions. Computing a hash value takes 35+6n instructions for an n-byte key.

Functions provided:

• hcreate() - create a hash table
• hdestroy() - destroy a hash table
• hcount() - the number of items in the hash table
• hkey() - key at the current position
• hkeyl() - key length at the current position
• hstuff() - stuff at the current position
• hfind() - find an item in the table
• hadd() - insert an item into the table
• hdel() - delete an item from the table
• hstat() - print statistics about the table
• hfirst() - position at the first item in the table
• hnext() - move the position to the next item in the table

Definition in file hashtab.c.

Function Documentation

hadd()

word hadd	(	htab *	t,
		ub1 *	key,
		ub4	keyl,
		void *	stuff )

Add an item to the hash table.

Inserts an item into the hash table with the given key and associated data.

Parameters

t	Pointer to the hash table.
key	Key to add to the hash table.
keyl	Length of the key.
stuff	Data to associate with the key.

Returns

TRUE if the item was added successfully, FALSE if the key is already in the table.

Definition at line 207 of file hashtab.c.

{
  register hitem *h, **hp;
  register ub4 y, x = lookup(key, keyl, 0);
  /* make sure the key is not already there */
  for (h = t->table[(y = (x & t->mask))]; h; h = h->next) {
    if ((x == h->hval) && (keyl == h->keyl) && !memcmp(key, h->key, keyl)) {
      t->apos = y;
      t->ipos = h;
      return FALSE;
    }
  }
 
  /* find space for a new item */
  h = (hitem *)renew(t->space);
 
  /* make the hash table bigger if it is getting full */
  if (++t->count > (ub4)1 << (t->logsize)) {
    hgrow(t);
    y = (x & t->mask);
  }
 
  /* add the new key to the table */
 
  h->key = (ub1 *)malloc(keyl); /* dumb use of malloc */
  memcpy(h->key, key, keyl);    /* copy key into h->key */
  h->keyl = keyl;
  h->stuff = stuff;
  h->hval = x;
  hp = &t->table[y];
  h->next = *hp;
  *hp = h;
  t->ipos = h;
  t->apos = y;
 
#ifdef HSANITY
  hsanity(t);
#endif /* HSANITY */
 
  return TRUE;
}

hcreate()

htab * hcreate

(

word

logsize

)

Create a hash table.

Initializes a hash table with an initial size of 2 raised to the power of logsize.

Parameters

logsize

Log base 2 of the initial size of the hash table.

Returns

Pointer to the newly created hash table.

Definition at line 124 of file hashtab.c.

{
  ub4 i, len;
  htab *t = (htab *)malloc(sizeof(htab));
 
  len = ((ub4)1 << logsize);
  t->table = (hitem **)malloc(sizeof(hitem *) * (ub4)len);
  for (i = 0; i < len; ++i)
    t->table[i] = (hitem *)0;
  t->logsize = logsize;
  t->mask = len - 1;
  t->count = 0;
  t->apos = (ub4)0;
  t->ipos = (hitem *)0;
  t->space = remkroot(sizeof(hitem));
  t->bcount = 0;
  return t;
}

hdel()

word hdel

(

htab *

t

)

Definition at line 254 of file hashtab.c.

{
  hitem *h;   /* item being deleted */
  hitem **ip; /* a counter */
 
  /* check for item not existing */
  if (!(h = t->ipos))
    return FALSE;
 
  /* remove item from its list */
  for (ip = &t->table[t->apos]; *ip != h; ip = &(*ip)->next)
    ;
  *ip = (*ip)->next;
  --(t->count);
 
  /* adjust position to something that exists */
  if (!(t->ipos = h->next))
    hnbucket(t);
 
  /* recycle the deleted hitem node */
  redel(t->space, h);
 
#ifdef HSANITY
  hsanity(t);
#endif /* HSANITY */
 
  return TRUE;
}

hdestroy()

void hdestroy

(

htab *

t

)

Destroy the hash table and free all its memory.

Parameters

t	Pointer to the hash table to destroy.

Definition at line 149 of file hashtab.c.

{
  while (hcount(t)) /* while the table is not empty */
  {
    if (hkey(t))
      free(hkey(t)); /* free memory for the line */
    hdel(t);         /* delete from hash table */
  }
  refree(t->space);
  free((char *)t->table);
  free((char *)t);
}

hfind()

word hfind	(	htab *	t,
		ub1 *	key,
		ub4	keyl )

Find an item with a given key in the hash table.

Searches for an item with the specified key in the hash table.

Parameters

t	Pointer to the hash table.
key	Key to find.
keyl	Length of the key.

Returns

TRUE if the item is found, FALSE otherwise.

Definition at line 178 of file hashtab.c.

{
  hitem *h;
  ub4 x = lookup(key, keyl, 0);
  ub4 y;
  for (h = t->table[y = (x & t->mask)]; h; h = h->next) {
    if ((x == h->hval) && (keyl == h->keyl) && !memcmp(key, h->key, keyl)) {
      t->apos = y;
      t->ipos = h;
      return TRUE;
    }
  }
  return FALSE;
}

hfirst()

word hfirst

(

htab *

t

)

Position the hash table on the first element.

Sets the current position to the first item in the hash table.

Parameters

t	Pointer to the hash table.

Returns

TRUE if the first element exists, FALSE otherwise.

Definition at line 292 of file hashtab.c.

{
  t->apos = t->mask;
  (void)hnbucket(t);
  return (t->ipos != (hitem *)0);
}

hgrow()

static void hgrow ( htab * t )

static

Definition at line 82 of file hashtab.c.

{
  register ub4 newsize = (ub4)1 << (++t->logsize);
  register ub4 newmask = newsize - 1;
  register ub4 i;
  register hitem **oldtab = t->table;
  register hitem **newtab = (hitem **)malloc(newsize * sizeof(hitem *));
 
  /* make sure newtab is cleared */
  for (i = 0; i < newsize; ++i)
    newtab[i] = (hitem *)0;
  t->table = newtab;
  t->mask = newmask;
 
  /* Walk through old table putting entries in new table */
  for (i = newsize >> 1; i--;) {
    register hitem *this, *that, **newplace;
    for (this = oldtab[i]; this;) {
      that = this;
      this = this->next;
      newplace = &newtab[(that->hval & newmask)];
      that->next = *newplace;
      *newplace = that;
    }
  }
 
  /* position the hash table on some existing item */
  hfirst(t);
 
  /* free the old array */
  free((char *)oldtab);
}

hnbucket()

word hnbucket

(

htab *

t

)

Definition at line 306 of file hashtab.c.

{
  ub4 oldapos = t->apos;
  ub4 end = (ub4)1 << (t->logsize);
  ub4 i;
 
  /* see if the element can be found without wrapping around */
  for (i = oldapos + 1; i < end; ++i) {
    if (t->table[i & t->mask]) {
      t->apos = i;
      t->ipos = t->table[i];
      return TRUE;
    }
  }
 
  /* must have to wrap around to find the last element */
  for (i = 0; i <= oldapos; ++i) {
    if (t->table[i]) {
      t->apos = i;
      t->ipos = t->table[i];
      return FALSE;
    }
  }
 
  return FALSE;
}

hstat()

void hstat

(

htab *

t

)

Definition at line 334 of file hashtab.c.

{
  ub4 i, j;
  double total = 0.0;
  hitem *h;
  hitem *walk, *walk2, *stat = (hitem *)0;
 
  /* in stat, keyl will store length of list, hval the number of buckets */
  for (i = 0; i <= t->mask; ++i) {
    for (h = t->table[i], j = 0; h; ++j, h = h->next)
      ;
    for (walk = stat; walk && (walk->keyl != j); walk = walk->next)
      ;
    if (walk) {
      ++(walk->hval);
    } else {
      walk = (hitem *)renew(t->space);
      walk->keyl = j;
      walk->hval = 1;
      if (!stat || stat->keyl > j) {
        walk->next = stat;
        stat = walk;
      } else {
        for (walk2 = stat; walk2->next && (walk2->next->keyl < j); walk2 = walk2->next)
          ;
        walk->next = walk2->next;
        walk2->next = walk;
      }
    }
  }
 
  /* figure out average list length for existing elements */
  for (walk = stat; walk; walk = walk->next) {
    total += (double)walk->hval * (double)walk->keyl * (double)walk->keyl;
  }
  if (t->count)
    total /= (double)t->count;
  else
    total = (double)0;
 
  /* print statistics */
  printf("\n");
  for (walk = stat; walk; walk = walk->next) {
    printf("items %ld:  %ld buckets\n", walk->keyl, walk->hval);
  }
  printf("\nbuckets: %ld  items: %ld  existing: %g\n\n", ((ub4)1 << t->logsize), t->count, total);
 
  /* clean up */
  while (stat) {
    walk = stat->next;
    redel(t->space, stat);
    stat = walk;
  }
}