/* $Id: hash.c,v 10.1 92/10/06 23:10:27 ca Exp $ */
/*LINTLIBRARY*/

/* Hash table.
   Works with arbitrary length keys (<700000 bytes) & records.

   This file contains:
   	ht_create	Make a table
	ht_insert	Insert a new record
	ht_delete	Delete a record
	ht_find		Look up a record
	ht_obliterate	Destroy the table & free all of its memory
	ht_iter		CLU-like iterator to return all records in the table

   Also:  (internal routines that should not be called by others)
        ht_qfind	Finds a record in a bucket (queue)
	hash		Computes the hash value of a key

Notes on use:
  The table automatically allocates memory & makes a copy of a record that
  is inserted, so the storage that is passed to the ht_insert function may be
  reused.  However, the pointer that is returned from the ht_find is a
  pointer into the table.  The memory pointed to should NOT be modified.
*/

#include <sys/types.h>
#include "sim.h"
#include "q.h"
#include "hash.h"

Hash_elem *ht_qfind();

/******************************************
  Create function--the size passed should be approximately the maximum
  number of records to be stored in the table, and should be a prime number.
  Returns a pointer to the table.
*/

Htable
ht_create(size, key_size, rec_size)
     int size, key_size, rec_size;
{
  Htable ht;
  
  /* Allocate memory with wild abandon */
  ht = (Htable)sim_calloc(1, sizeof(struct _Htable));
  ht->ht_size = size;
  ht->ht_key_size = key_size;
  ht->ht_rec_size = rec_size;

  ht->ht_table = (Hash_bucket *)sim_calloc((unsigned)size,
					     sizeof(Hash_bucket));
  return(ht);
}


/*********************************************
  Insert a new record into the hash table.  Duplicate insertions are
  not allowed.
  Returns 0 if sim_calloc() failed, 1 if okay, -1 if record already exists.
*/

ht_insert(ht, key, rec)
     register Htable ht;
     register char *key, *rec;
{
  register Hash_elem *he;
  register int num;
  
  num = hash(ht, key);
  if (!ht_qfind(&ht->ht_table[num], key, ht->ht_key_size))  {
    he = (Hash_elem *)sim_calloc(1, (unsigned)(sizeof(Hash_elem)
				   + ht->ht_key_size + ht->ht_rec_size));
    /* Copy key & record into the Hash_elem */
    bcopy(key, he->he_key, ht->ht_key_size);
    bcopy(rec, he->he_key + ht->ht_key_size, ht->ht_rec_size);
    qe_addt(&ht->ht_table[num], he);
    return(1);
  } else   /* A record with this key already exists */
    return(-1);
}


/******************************************
  Remove an element from the hash table.
  Returns 0 if element not found, 1 if successful deletion.
*/

ht_delete(ht, key)
     register Htable ht;
     register char *key;
{
  register Hash_elem *he, *prev;
  register int num;

  num = hash(ht, key);
  if (prev = ht_qfind(&ht->ht_table[num], key, ht->ht_key_size))  {
    /* Since qfind returns a pointer to the previous item, can
       just use qe_dela to delete it */
    he = prev->he_next;
    qe_dela(&ht->ht_table[num], prev);
    free((char *)he);
    return(1);
  } else   /* Not found */
    return(0);
}


/********************************************
  Find an element.  Returns pointer to the stored record.
  Note that the pointer points into the hash table and so
  should not be modified.  Note also that if you delete this record
  after finding it, this pointer is no longer valid.
  Returns NULL if not found.
*/

char *
ht_find(ht, key)
     register Htable ht;
     register char *key;
{
  register Hash_elem *prev;
  register int num;

  num = hash(ht, key);
  if (prev = ht_qfind(&ht->ht_table[num], key, ht->ht_key_size))  {
    /* Since qfind returns a pointer to the previous item,
       must follow the link once. */
    /* Return a pointer to the record part of the entry */
    return(prev->he_next->he_key + ht->ht_key_size);
  } else   /* Not found */
    return(NULL);
}


/********************************************
  Wipe out the hash table.  Free all of its memory.
*/
ht_obliterate(ht)
     register Htable ht;
{
  register int i;
  Hash_elem *he, *next;

  for (i = 0; i < ht->ht_size; i++)  {
    he = (Hash_elem *)ht->ht_table[i].q_head;
       while (he)  {
	 next = he->he_next;
	 free((char *)he);
	 he = next;
       }
  }
  free((char *)ht->ht_table);
  free((char *)ht);
}


/***********************************************
  Return all of the records in the hash table, in some random order.
  Must call ht_iter_setup() once to initialize the iteration, and
  then call ht_iter to get each element.  ht_iter returns NULL when
  done.  While iterating, you may delete any record from the table
  that has already been returned (including the most recent one).
  ht_iter returns a char *p such that p points to the key and p + key_size
  points to the record.
*/

ht_iter_setup(ht)
     Htable ht;
{
  ht->ht_iter_current_bucket = 0;
  ht->ht_iter_next_item = (Hash_elem *)(ht->ht_table[0].q_head);
}

char *
ht_iter(ht)
     Htable ht;
{
  register Hash_elem *he;

  while (!ht->ht_iter_next_item)  {
    ht->ht_iter_current_bucket++;
    if (ht->ht_iter_current_bucket == ht->ht_size)
      return(NULL);
    ht->ht_iter_next_item = (Hash_elem *)
      		(ht->ht_table[ht->ht_iter_current_bucket].q_head);
  }
  he = ht->ht_iter_next_item;
  ht->ht_iter_next_item = he->he_next;
  return((char *)(he->he_key));
}


/* Routine for use by the rest of the hash table routines.
   Looks for a record with the passed key in the passed queue.
   Returns a pointer to the ***PREVIOUS*** record in the queue.
   (So that deletes are easy.)
*/
Hash_elem *
ht_qfind(q, key, size)
     register queue *q;
     register char *key;
     register int size;
{
  register Hash_elem *qe, *prev;

  for (qe=(Hash_elem *)(q->q_head), prev = (Hash_elem *)(&q->q_head); qe;
       qe = qe->he_next)  {
    if (!bcmp(key, qe->he_key, size))
      return(prev);
    prev = qe;
  }

  /* If we get here, we haven't found it */
  return(NULL);
}


/* Hash routine.  More-or-less from Knuth Vol. III.  */

/* Macro to rotate (rather than just shift) a number.  This macro will
   work only on machines with 8-bit bytes.   */
#define rotl(x) ((x) & (1 << (8*sizeof(x)-1)) ? ((x) << 1) | 1 : (x) << 1)

hash(ht, key)
     register Htable ht;
     register char *key;
{
  register unsigned int hash_val;
  register int j;

  for (hash_val = j = 0; j < ht->ht_key_size; j++, key++)  {
    hash_val ^= *key * 23;   /* ^ is XOR */
    /* Rotate so that permutations hash to different values */
    hash_val = rotl(hash_val);
  }

  return(hash_val % ht->ht_size);
}