/*


 Copyright (C) 1990 Texas Instruments Incorporated.

 Permission is granted to any individual or institution to use, copy, modify,
 and distribute this software, provided that this complete copyright and
 permission notice is maintained, intact, in all copies and supporting
 documentation.

 Texas Instruments Incorporated provides this software "as is" without
 express or implied warranty.


 *
 * Edit history
 * Created: LGO 30-Mar-89 -- Initial design and implementation.
 *
 * Hash functions
 */

#include "defmacio.h"

static int hash_primes[] = {3, 7, 13, 19, 29, 41, 53, 67, 83, 97, 113, 137,
			    163, 191, 223, 263, 307, 349, 401, 461, 521, 587,
			    653, 719, 773, 839, 911, 983, 1049, 1123, 1201,
			    1279, 1367, 1459, 1549, 1657, 1759, 1861, 1973,
			    2081, 2179, 2281, 2383, 2503, 2617, 2729, 2843,
			    2963, 3089, 3203, 3323, 3449, 3571, 3697, 3833,
			    3967, 4099, 4241, 4391, 4549, 4703, 4861, 5011,
			    5171, 5333, 5483, 5669, 5839, 6029, 6197, 6361,
  			    6547, 6761, 6961, 7177, 7393, 7517, 7727, 7951,
			    8101, 8209, 16411, 32771, 65537, 131301, 262147,
			    524287};

void*
next_hash(h, firstp)
   struct Hash_Table* h;
   Boolean firstp;
{
  if(firstp) {
    h->current_bucket = 0;
    h->current_index = 0;
  }
  while (h->current_bucket < hash_primes[h->bucket_index]) {
    if (h->current_index < h->items_in_buckets[h->current_bucket])
      return h->table[h->current_bucket].data[h->current_index++].value;
    else {
      h->current_bucket += 1;
      h->current_index = 0;
    }
  }
  return NULL;
}

/* sxhash -- Hash function for char*
 * Input:	Character string
 * Output:	unsigned long hash value
 */
unsigned long sxhash(string)
  char* string;
{
  register unsigned long hash = *string++;
  if(*string != EOS) {
    hash = (hash << 7) ^ *string++;
    if (*string != EOS) {
      hash = (hash << 7) ^ *string++;
      if (*string != EOS) {
	hash = (hash << 7) ^ *string++;
	while (*string != EOS) { /* rotate hash left 7 bits */
	  int rest = hash >> 25;
	  hash = ((hash << 7) | rest) ^ *string++;
	}
      }
    }
  }
  return hash;
}

struct Hash_Table*
init_Hash_Table() {
  struct Hash_Table* h = (struct Hash_Table*) getmem(sizeof(struct Hash_Table));
  int prime, i;
  h->entry_count = 0;	
  h->bucket_index = 0;	
  prime  = hash_primes[h->bucket_index];	
  h->items_in_buckets = (unsigned char*) getmem (prime);	
  for (i = 0; i < prime; i++)		
    h->items_in_buckets[i] = 0;
  h->table = (struct bucket*) getmem(sizeof(struct bucket)*prime);
  return h;
}

static void
resize (h, n)
     struct Hash_Table* h;
     int n;
{
  unsigned char* temp1;
  struct bucket* temp2;			
  long old_prime, i, j, new_prime, hash;
  old_prime = hash_primes[h->bucket_index];

  while (hash_primes[h->bucket_index]*BUCKET_SIZE < n)
    h->bucket_index++;

 retry:
  new_prime = hash_primes[h->bucket_index];
  temp1 = (unsigned char*) getmem (new_prime);		
  for (i = 0; i < new_prime; i++)		
    temp1[i] = 0;				
  temp2 = (struct bucket*) getmem(sizeof (struct bucket) * new_prime); 
  for (i = 0; i < old_prime; i++) {	
    for (j = 0; j < h->items_in_buckets[i]; j++) { 
      char* key = h->table[i].data[j].key;
      hash = sxhash(key) % new_prime;
      if (temp1[hash] >= BUCKET_SIZE) {	  /* Bucket Overflow */
	free (temp1);
	free (temp2);
	h->bucket_index++;
	goto retry;
      }
      temp2[hash].data[temp1[hash]].key = key;	
      temp2[hash].data[temp1[hash]].value = h->table[i].data[j].value;	
      ++temp1[hash];
    }
  }
  free (h->items_in_buckets);
  free (h->table);			
  h->items_in_buckets = temp1;		
  h->table = temp2;			
}

int
get_entry_count (h)
     struct Hash_Table* h;
{
  return (h->entry_count);
}

Boolean
put_hash (h, key, value)
    struct Hash_Table* h;
    char* key;
    void* value;
{
  long prime,hash;
  int next, i;
 retry:
  prime = hash_primes[h->bucket_index];
  hash = sxhash(key) % prime;
  for (i = 0; i < h->items_in_buckets[hash]; i++)
    if (!strcmp(key,h->table[hash].data[i].key))
      return FALSE;
  if (h->items_in_buckets[hash] >= BUCKET_SIZE) {
    resize (h, hash_primes[h->bucket_index+1]*BUCKET_SIZE);
    goto retry;
  }
  next = h->items_in_buckets[hash]++;
  h->table[hash].data[next].key = key;
  h->table[hash].data[next].value = value;
  h->entry_count++;			
  return TRUE;
}

void*
get_hash (h, key)
     struct Hash_Table* h;
     char* key;
{
  long prime, hash;
  int i, len;
  prime = hash_primes[h->bucket_index];
  hash = sxhash(key) % prime;
  len = h->items_in_buckets[hash];
  for (i = 0; i < len; i++) {
    if (!strcmp(key,h->table[hash].data[i].key))
      return (h->table[hash].data[i].value);
  }
  return NULL;
}