hashtable.c

/*\
||| This file a part of Pike, and is copyright by Fredrik Hubinette
||| Pike is distributed as GPL (General Public License)
||| See the files COPYING and DISCLAIMER for more information.
\*/
#include "global.h"
#include "hashtable.h"
#include "stralloc.h"
#include "stuff.h"
#include "error.h"

RCSID("$Id: hashtable.c,v 1.4 1998/03/28 15:14:56 grubba Exp $");

static unsigned INT32 gobble(struct pike_string *s)
{
  unsigned INT32 i;
  i=my_hash_string(s);
  i+=i >> 3;
  i+=i >> 7;
  i+=i >> 12;
  return i;
}

/*
 * Search hash for a specific string.
 */
struct hash_entry *hash_lookup(struct hash_table *h, struct pike_string *s)
{
  struct hash_entry *e, **prev, **base;

  if(!h) return 0;
  base = prev = h->htable + (gobble(s) & h->mask);
  for( ;(e = *prev); prev= &e->next)
  {
    if(s == e->s)
    {
      /* Teleport entry to beginning of line */
      *prev = e->next;
      e->next = *base;
      *base = e;
      /* Entry arrives in a puff of smoke. */

      return e;
    }
  }
  return 0;
}

/*
 * We want to keep the order of the hash chain, as it has been carefully
 * built up to be fast.
 */
static void rehash_list_backwards(struct hash_table *h,
				  struct hash_entry *n)
{
  struct hash_entry **base;
  if(!n) return;
  rehash_list_backwards(h,n->next);
  base=h->htable + (gobble(n->s) & h->mask);
  n->next = *base;
  *base=n;
}

/*
 * create a new, empty hashable
*/
struct hash_table *create_hash_table(void)
{
  struct hash_table *new;
  new=(struct hash_table *)calloc(1,sizeof(struct hash_table)+