hashtab.c File Reference

#include <string.h>
#include <malloc.h>
#include "standard.h"
#include "lookupa.h"
#include "hashtab.h"
#include "recycle.h"

Include dependency graph for hashtab.c:

Go to the source code of this file.

Functions
static void	hgrow (htab *t)
htab *	hcreate (word logsize)
void	hdestroy (htab *t)
word	hfind (htab *t, ub1 *key, ub4 keyl)
word	hadd (htab *t, ub1 *key, ub4 keyl, void *stuff)
word	hdel (htab *t)
word	hfirst (htab *t)
word	hnbucket (htab *t)

Function Documentation

hadd()

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

Definition at line 183 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   = 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;
}

References FALSE, hgrow(), hitem::hval, hitem::key, hitem::keyl, lookup(), hitem::next, renew, hitem::stuff, TRUE, x, and y.

hcreate()

htab* hcreate

(

word

logsize

)

Definition at line 123 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;
}

References htab::apos, htab::bcount, htab::count, htab::ipos, htab::logsize, htab::mask, remkroot(), htab::space, and htab::table.

hdel()

word hdel

(

htab *

t

)

Definition at line 234 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;
}

References FALSE, hnbucket(), hitem::next, redel, and TRUE.

hdestroy()

void hdestroy

(

htab *

t

)

Definition at line 143 of file hashtab.c.

{
  refree(t->space);
  free((char *)t->table);
  free((char *)t);
}

References refree().

hfind()

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

Definition at line 157 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;
}

References FALSE, hitem::hval, hitem::key, hitem::keyl, lookup(), hitem::next, TRUE, x, and y.

hfirst()

word hfirst

(

htab *

t

)

Definition at line 263 of file hashtab.c.

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

References htab::apos, and hnbucket().

Referenced by hgrow().

hgrow()

static void hgrow ( htab *  t )

static

Definition at line 86 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);
 
}

References hfirst(), hitem::hval, and hitem::next.

Referenced by hadd().

hnbucket()

word hnbucket

(

htab *

t

)

Definition at line 277 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;
}

References htab::apos, FALSE, and TRUE.

Referenced by hdel(), and hfirst().