/*
  Hash table library using separate chaining

    > Created (Julienne Walker): August 7, 2005
    > Modified (Julienne Walker): August 11, 2005
      Added a cast for malloc to enable clean
      compilation as C++
*/
#include "jsw_hlib.h"

#ifdef __cplusplus
#include <cstdlib>

using std::malloc;
using std::free;
#else
#include <stdlib.h>
#endif

typedef struct jsw_node {
  void            *key;  /* Key used for searching */
  void            *item; /* Actual content of a node */
  struct jsw_node *next; /* Next link in the chain */
} jsw_node_t;

typedef struct jsw_head {
  jsw_node_t *first;     /* First link in the chain */
  size_t      size;      /* Length of the chain */
} jsw_head_t;

struct jsw_hash {
  jsw_head_t **table;    /* Dynamic chained hash table */
  size_t       size;     /* Current item count */
  size_t       capacity; /* Current table size */
  size_t       curri;    /* Current index for traversal */
  jsw_node_t  *currl;    /* Current link for traversal */
  hash_f       hash;     /* User defined key hash function */
  cmp_f        cmp;      /* User defined key comparison function */
  keydup_f     keydup;   /* User defined key copy function */
  itemdup_f    itemdup;  /* User defined item copy function */
  keyrel_f     keyrel;   /* User defined key delete function */
  itemrel_f    itemrel;  /* User defined item delete function */
};

static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )
{
  jsw_node_t *node = (jsw_node_t *)malloc ( sizeof *node );

  if ( node == NULL )
    return NULL;

  node->key = key;
  node->item = item;
  node->next = next;

  return node;
}

static jsw_head_t *new_chain ( void )
{
  jsw_head_t *chain = (jsw_head_t *)malloc ( sizeof *chain );

  if ( chain == NULL )
    return NULL;

  chain->first = NULL;
  chain->size = 0;

  return chain;
}

/*
  Create a new hash table with a capacity of size, and
  user defined functions for handling keys and items.

  Returns: An empty hash table, or NULL on failure.
*/
jsw_hash_t  *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
  keydup_f keydup, itemdup_f itemdup,
  keyrel_f keyrel, itemrel_f itemrel )
{
  jsw_hash_t *htab = (jsw_hash_t *)malloc ( sizeof *htab );
  size_t i;

  if ( htab == NULL )
    return NULL;

  htab->table = (jsw_head_t **)malloc ( size * sizeof *htab->table );

  if ( htab->table == NULL ) {
    free ( htab );
    return NULL;
  }

  /* Empty chains have no head */
  for ( i = 0; i < size; i++ )
    htab->table[i] = NULL;

  htab->size = 0;
  htab->capacity = size;
  htab->curri = 0;
  htab->currl = NULL;
  htab->hash = hash;
  htab->cmp = cmp;
  htab->keydup = keydup;
  htab->itemdup = itemdup;
  htab->keyrel = keyrel;
  htab->itemrel = itemrel;

  return htab;
}

/* Release all memory used by the hash table */
void jsw_hdelete ( jsw_hash_t *htab )
{
  size_t i;

  /* Release each chain individually */
  for ( i = 0; i < htab->capacity; i++ ) {
    jsw_node_t *save, *it;

    if ( htab->table[i] == NULL )
      continue;

    it = htab->table[i]->first;

    for ( ; it != NULL; it = save ) {
      save = it->next;
      htab->keyrel ( it->key );
      htab->itemrel ( it->item );
      free ( it );
    }

    free ( htab->table[i] );
  }

  /* Release the hash table */
  free ( htab->table );
  free ( htab );
}

/*
  Find an item with the selected key

  Returns: The item, or NULL if not found
*/
void *jsw_hfind ( jsw_hash_t *htab, void *key )
{
  unsigned h = htab->hash ( key ) % htab->capacity;

  /* Search the chain only if it exists */
  if ( htab->table[h] != NULL ) {
    jsw_node_t *it = htab->table[h]->first;

    for ( ; it != NULL; it = it->next ) {
      if ( htab->cmp ( key, it->key ) == 0 )
        return it->item;
    }
  }

  return NULL;
}

/*
  Insert an item with the selected key

  Returns: non-zero for success, zero for failure
*/
int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item )
{
  unsigned h = htab->hash ( key ) % htab->capacity;
  void *dupkey, *dupitem;
  jsw_node_t *new_item;

  /* Disallow duplicate keys */
  if ( jsw_hfind ( htab, key ) != NULL )
    return 0;

  /* Attempt to create a new item */
  dupkey = htab->keydup ( key );
  dupitem = htab->itemdup ( item );

  new_item = new_node ( dupkey, dupitem, NULL );

  if ( new_item == NULL )
    return 0;

  /* Create a chain if the bucket is empty */
  if ( htab->table[h] == NULL ) {
    htab->table[h] = new_chain();

    if ( htab->table[h] == NULL ) {
      htab->keyrel ( new_item->key );
      htab->itemrel ( new_item->item );
      free ( new_item );
      return 0;
    }
  }

  /* Insert at the front of the chain */
  new_item->next = htab->table[h]->first;
  htab->table[h]->first = new_item;

  ++htab->table[h]->size;
  ++htab->size;

  return 1;
}

/*
  Remove an item with the selected key

  Returns: non-zero for success, zero for failure
*/
int jsw_herase ( jsw_hash_t *htab, void *key )
{
  unsigned h = htab->hash ( key ) % htab->capacity;
  jsw_node_t *save, *it;

  if ( htab->table[h] == NULL )
    return 0;

  it = htab->table[h]->first;

  /* Remove the first node in the chain? */
  if ( htab->cmp ( key, it->key ) == 0 ) {
    htab->table[h]->first = it->next;

    /* Release the node's memory */
    htab->keyrel ( it->key );
    htab->itemrel ( it->item );
    free ( it );

    /* Remove the chain if it's empty */
    if ( htab->table[h]->first == NULL ) {
      free ( htab->table[h] );
      htab->table[h] = NULL;
    }
    else
      --htab->table[h]->size;
  }
  else {
    /* Search for the node */
    while ( it->next != NULL ) {
      if ( htab->cmp ( key, it->next->key ) == 0 )
        break;

      it = it->next;
    }

    /* Not found? */
    if ( it->next == NULL )
      return 0;

    save = it->next;
    it->next = it->next->next;

    /* Release the node's memory */
    htab->keyrel ( save->key );
    htab->itemrel ( save->item );
    free ( save );

    --htab->table[h]->size;
  }

  /* Erasure invalidates traversal markers */
  jsw_hreset ( htab );

  --htab->size;

  return 1;
}

/*
  Grow or shrink the table, this is a slow operation
  
  Returns: non-zero for success, zero for failure
*/
int jsw_hresize ( jsw_hash_t *htab, size_t new_size )
{
  jsw_hash_t *new_htab;
  jsw_node_t *it;
  size_t i;

  /* Build a new hash table, then assign it to the old one */
  new_htab = jsw_hnew ( new_size, htab->hash, htab->cmp,
    htab->keydup, htab->itemdup, htab->keyrel, htab->itemrel );

  if ( new_htab == NULL )
    return 0;

  for ( i = 0; i < htab->capacity; i++ ) {
    if ( htab->table[i] == NULL )
      continue;

    for ( it = htab->table[i]->first; it != NULL; it = it->next )
      jsw_hinsert ( new_htab, it->key, it->item );
  }

  /* A hash table holds copies, so release the old table */
  jsw_hdelete ( htab );
  htab = new_htab;

  return 1;
}

/* Reset the traversal markers to the beginning */
void jsw_hreset ( jsw_hash_t *htab )
{
  size_t i;

  htab->curri = 0;
  htab->currl = NULL;

  /* Find the first non-empty bucket */
  for ( i = 0; i < htab->capacity; i++ ) {
    if ( htab->table[i] != NULL )
      break;
  }

  htab->curri = i;

  /* Set the link marker if the table was not empty */
  if ( i != htab->capacity )
    htab->currl = htab->table[i]->first;
}

/* Traverse forward by one key */
int jsw_hnext ( jsw_hash_t *htab )
{
  if ( htab->currl != NULL ) {
    htab->currl = htab->currl->next;

    /* At the end of the chain? */
    if ( htab->currl == NULL ) {
      /* Find the next chain */
      while ( ++htab->curri < htab->capacity ) {
        if ( htab->table[htab->curri] != NULL )
          break;
      }

      /* No more chains? */
      if ( htab->curri == htab->capacity )
        return 0;

      htab->currl = htab->table[htab->curri]->first;
    }
  }

  return 1;
}

/* Get the current key */
const void *jsw_hkey ( jsw_hash_t *htab )
{
  return htab->currl != NULL ? htab->currl->key : NULL;
}

/* Get the current item */
void *jsw_hitem ( jsw_hash_t *htab )
{
  return htab->currl != NULL ? htab->currl->item : NULL;
}

/* Current number of items in the table */
size_t jsw_hsize ( jsw_hash_t *htab )
{
  return htab->size;
}

/* Total allowable number of items without resizing */
size_t jsw_hcapacity ( jsw_hash_t *htab )
{
  return htab->capacity;
}

/* Get statistics for the hash table */
jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab )
{
  jsw_hstat_t *stat;
  double sum = 0, used = 0;
  size_t i;

  /* No stats for an empty table */
  if ( htab->size == 0 )
    return NULL;

  stat = (jsw_hstat_t *)malloc ( sizeof *stat );

  if ( stat == NULL )
    return NULL;

  stat->lchain = 0;
  stat->schain = (size_t)-1;

  for ( i = 0; i < htab->capacity; i++ ) {
    if ( htab->table[i] != NULL ) {
      sum += htab->table[i]->size;

      ++used; /* Non-empty buckets */

      if ( htab->table[i]->size > stat->lchain )
        stat->lchain = htab->table[i]->size;

      if ( htab->table[i]->size < stat->schain )
        stat->schain = htab->table[i]->size;
    }
  }

  stat->load = used / htab->capacity;
  stat->achain = sum / used;

  return stat;
}