/* hash.c - Don Yang (uguu.org)

   12/27/05
                                                                           */
/*@ -branchstate -mustdefine -onlytrans -temptrans @*/

#include <stdio.h>
#include <stdlib.h>
#include "hash.h"

#define MAX_HASHTABLE_SIZE    0x40000000
#define MIN_HASHTABLE_SIZE    4
#define MAX_LINEAR_PROBE      5

/* One at a time hash, from here: http://burtleburtle.net/bob/hash/doobs.html
   This is the same function used in Perl 5.8.7                            */
static unsigned int Hash(char *key, size_t len)
{
   unsigned int h;
   size_t i;

   h = 0U;
   for(i = 0; i < len; i++)
   {
      h += (unsigned int)*(key++);
      h += (h << 10);
      h ^= (h >> 6);
   }
   h += (h << 3);
   h ^= (h >> 11);
   h += (h << 15);
   return h;
}

/* Find hash index, -1 if key not found */
static int Find(/*@observer@*/HashTable *h,
                /*@observer@*/void *key, size_t key_size)
{
   unsigned int index, mask, hash, i;

   mask = (unsigned int)h->capacity - 1;
   index = hash = Hash(key, key_size);
   for(i = 0; i < MAX_LINEAR_PROBE; i++, index++)
   {
      if( h->entries[index &= mask].key == NULL ) continue;
      if( h->entries[index].key_size != key_size ) continue;
      if( h->entries[index].hash != hash ) continue;
      if( memcmp(h->entries[index].key, key, key_size) == 0 )
         return (int)index;
   }
   return -1;
}

/* Replace value in hash table entry, abort if out of memory */
static void ReplaceValue(HashTableEntry *entry,
                         /*@observer@*/void *value, size_t value_size)
{
   if( value_size == 0 )
   {
      if( entry->value != NULL )
      {
         free(entry->value);
         entry->value = NULL;
         entry->value_size = 0;
      }
   }
   else
   {
      if( entry->value_size != value_size )
      {
         if( entry->value != NULL )
            free(entry->value);
         if( (entry->value = malloc(value_size)) == NULL )
            abort();
         entry->value_size = value_size;
      }
      memcpy(entry->value, value, value_size);
   }
}

/* Increase hash table size, abort if out of memory */
static void ResizeTable(HashTable *h)
{
   HashTableEntry *n, *x;
   size_t new_capacity, i, j;
   unsigned int index, mask;

   for(new_capacity = h->capacity << 1; new_capacity <= MAX_HASHTABLE_SIZE;
       new_capacity <<= 1)
   {
      /* Allocate new table */
      if( (n = (HashTableEntry*)calloc(
            new_capacity, sizeof(HashTableEntry))) == NULL )
         abort();

      /* Rehash entries */
      x = h->entries;
      mask = (unsigned int)new_capacity - 1;
      for(i = 0; i < h->capacity; i++, x++)
      {
         if( x->key != NULL )
         {
            index = x->hash;
            for(j = 0; j < MAX_LINEAR_PROBE; j++, index++)
            {
               if( n[index & mask].key == NULL )
               {
                  memcpy(&n[index & mask], x, sizeof(HashTableEntry));
                  break;
               }
            }
            if( j == MAX_LINEAR_PROBE )
               break;
         }
      }
      if( i == h->capacity )
      {
         /* Success */
         free(h->entries);
         h->entries = n;
         h->capacity = new_capacity;
         return;
      }

      /* Too many collisions, increase hash table size again */
      free(n);
   }

   /* Can not resolve collisions even after increasing hash table
      to maximum size                                             */
   abort();
}


/* Create hash table */
/*@only@*/HashTable *HashTable_create(size_t capacity)
{
   HashTable *h;

   if( capacity > MAX_HASHTABLE_SIZE )
      abort();
   if( (h = (HashTable*)malloc(sizeof(HashTable))) == NULL )
      abort();

   h->size = 0;
   for(h->capacity = MIN_HASHTABLE_SIZE;
       h->capacity < capacity;
       h->capacity <<= 1);
   if( (h->entries = (HashTableEntry*)calloc(
         h->capacity, sizeof(HashTableEntry))) == NULL )
      abort();

   return h;
}

/* Free hash table */
void HashTable_destroy(/*@only@*//*@notnull@*/HashTable *h) /*@releases h@*/
{
   HashTable_destroy_custom(h, free);
}
void HashTable_destroy_custom(/*@only@*//*@notnull@*/HashTable *h,
                              void (*free_value)(void*)) /*@releases h@*/
{
   HashTableEntry *x;
   size_t i;

   x = h->entries;
   for(i = 0; i < h->capacity; i++, x++)
   {
      if( x->key != NULL )
      {
         free(x->key);
         if( x->value != NULL )
            (*free_value)(x->value);
      }
   }
   free(h->entries);
   free(h);
}

/* Free hash table, calling chech_value on each value first */
void HashTable_destroy_deep(/*@only@*//*@notnull@*/HashTable *h,
                            void (*check_value)(void*,size_t)) /*@releases h@*/
{
   HashTableEntry *x;
   size_t i;

   x = h->entries;
   for(i = 0; i < h->capacity; i++, x++)
   {
      if( x->key != NULL )
      {
         free(x->key);
         if( x->value != NULL )
         {
            (*check_value)(x->value, x->value_size);
            free(x->value);
         }
      }
   }
   free(h->entries);
   free(h);
}

/* Add entry */
void HashTable_add(HashTable *h,
                   /*@observer@*/void *key, size_t key_size,
                   /*@observer@*/void *value, size_t value_size)
{
   HashTableEntry *entry;
   unsigned int new_hash, index, slot, mask, i;

   new_hash = Hash(key, key_size);
   for(;;)
   {
      index = new_hash;
      slot = ~0U;
      mask = (unsigned int)h->capacity - 1;

      /* Scan linearly for previous keys */
      for(i = 0; i < MAX_LINEAR_PROBE; i++, index++)
      {
         entry = &(h->entries[index &= mask]);
         if( entry->key == NULL )
         {
            /* Empty slot found */
            if( slot == ~0U )
               slot = index;
            continue;
         }
         if( entry->key_size == key_size )
         {
            if( memcmp(entry->key, key, key_size) == 0 )
            {
               /* Previous key found, replace value and return */
               ReplaceValue(entry, value, value_size);
               return;
            }
         }
      }

      /* Previous key not found */
      if( slot != ~0U )
      {
         /* Empty slot available, insert (key, value) and return */
         entry = &(h->entries[slot]);
         if( (entry->key = malloc(key_size)) == NULL )
            abort();
         memcpy(entry->key, key, key_size);
         entry->key_size = key_size;
         entry->hash = new_hash;
         ReplaceValue(entry, value, value_size);
         h->size++;
         return;
      }

      /* Too many keys at current slot, increase table size and retry */
      ResizeTable(h);
   }
}

/* Remove entry */
void HashTable_remove(HashTable *h, /*@observer@*/void *key, size_t key_size)
{
   int index;
   if( (index = Find(h, key, key_size)) < 0 )
      return;
   free(h->entries[index].key);
   if( h->entries[index].value != NULL )
      free(h->entries[index].value);
   h->size--;
   memset(&(h->entries[index]), 0, sizeof(HashTableEntry));
}

/* Find entry */
/*@null@*//*@dependent@*/
void *HashTable_find(/*@observer@*/HashTable *h,
                     /*@observer@*/void *key, size_t key_size,
                     /*@out@*//*@null@*/size_t *value_size)
{
   int index;
   if( (index = Find(h, key, key_size)) < 0 )
   {
      if( value_size != NULL )
         *value_size = (size_t)~0U;
      return NULL;
   }
   if( value_size != NULL )
      *value_size = h->entries[index].value_size;
   return h->entries[index].value;
}