/* 
   elmo - ELectronic Mail Operator

   Copyright (C) 2002 rzyjontko

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software Foundation,
   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  

   ----------------------------------------------------------------------

   hash tables
   
*/
/****************************************************************************
 *    IMPLEMENTATION HEADERS
 ****************************************************************************/

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

#include <string.h>
#include <math.h>

#include "hash.h"
#include "xmalloc.h"
#include "memblock.h"
#include "debug.h"

/****************************************************************************
 *    IMPLEMENTATION PRIVATE DEFINITIONS / ENUMERATIONS / SIMPLE TYPEDEFS
 ****************************************************************************/

/**
 * This is
 *   floor (((sqrt (5) - 1) / 2) * 2 ^ (8 * sizeof (unsigned)))
 */
#if SIZEOF_UNSIGNED == 4
#define KNUTH_CONST (2654435769U)
#elif SIZEOF_UNSIGNED == 8
#define KNUTH_CONST (11400714819323198485U)
#elif SIZEOF_UNSIGNED == 2
#define KNUTH_CONST (40503U)
#endif

/****************************************************************************
 *    IMPLEMENTATION PRIVATE CLASS PROTOTYPES / EXTERNAL CLASS REFERENCES
 ****************************************************************************/
/****************************************************************************
 *    IMPLEMENTATION PRIVATE STRUCTURES / UTILITY CLASSES
 ****************************************************************************/
/****************************************************************************
 *    IMPLEMENTATION REQUIRED EXTERNAL REFERENCES (AVOID)
 ****************************************************************************/
/****************************************************************************
 *    IMPLEMENTATION PRIVATE DATA
 ****************************************************************************/
/****************************************************************************
 *    INTERFACE DATA
 ****************************************************************************/
/****************************************************************************
 *    IMPLEMENTATION PRIVATE FUNCTION PROTOTYPES
 ****************************************************************************/

static unsigned hash (const char *s, unsigned exponent);
static entry_t *lookup_with_hash (htable_t *table, const char *key,
                                  unsigned hashval);

/****************************************************************************
 *    IMPLEMENTATION PRIVATE FUNCTIONS
 ****************************************************************************/

static unsigned
hashpjw (const char *s)
{
  unsigned h = 0;
  unsigned g;

  while (*s){
    h <<= 4;
    h  += *s;
    if ((g = h & 0xf0000000)){
      h ^= (g >> 24);
      h ^= g;
    }
    s++;
  }
  return h;
}


static unsigned
hash (const char *s, unsigned exponent)
{
  unsigned wordval;
  int      shift = 8 * sizeof (unsigned) - exponent;

  wordval = hashpjw (s);

  return (wordval * KNUTH_CONST) >> shift;
}



static entry_t *
lookup_with_hash (htable_t *table, const char *key, unsigned hashval)
{
  entry_t *entry;

  for (entry = table->array[hashval]; entry; entry = entry->next){
    if (!strcmp (entry->key, key))
      break;
  }
  return entry;
}



static void
rehash (htable_t *table)
{
  entry_aux_t *list;
  entry_t     *item;
  unsigned     hashval;

  debug_msg (DEBUG_INFO, "rehashing table of exponent %d", table->exponent);
  for (list = table->list; list; list = list->next){
    item                  = list->entry;
    hashval               = hash (item->key, table->exponent);
    item->next            = table->array[hashval];
    table->array[hashval] = item;
  }
}


/****************************************************************************
 *    INTERFACE FUNCTIONS
 ****************************************************************************/


htable_t *
htable_create (unsigned exponent)
{
  int       size   = 1 << exponent;
  htable_t *result = xmalloc (sizeof (htable_t));

  result->memblock = memblock_create (1 << (exponent + 4));
  result->exponent = exponent;
  result->count    = 0;
  result->list     = NULL;
  result->array    = xcalloc (size * sizeof (entry_t), 1);
  return result;
}



void
htable_destroy (htable_t *table, void (*fun)(void *))
{
  entry_aux_t *item;

  while (table->list){
    item        = table->list;
    table->list = table->list->next;

    if (fun)
      fun (item->entry->content);
  }
  memblock_destroy (table->memblock);
  xfree (table->array);
  xfree (table);
}



entry_t *
htable_lookup (htable_t *table, const char *key)
{
  unsigned hashval = hash (key, table->exponent);

  return lookup_with_hash (table, key, hashval);
}




entry_t *
htable_insert (htable_t *table, const char *key, void *content)
{
  int          size;
  unsigned     hashval = hash (key, table->exponent);
  entry_t     *found   = lookup_with_hash (table, key, hashval);
  entry_aux_t *list_item;
  
  if (found)
    return found;

  found                 = memblock_malloc (&table->memblock, sizeof (entry_t));
  found->key            = memblock_strdup (&table->memblock, key);
  found->content        = content;
  found->next           = table->array[hashval];
  table->array[hashval] = found;

  list_item        = memblock_malloc (&table->memblock, sizeof (entry_aux_t));
  list_item->next  = table->list;
  list_item->entry = found;
  table->list      = list_item;

  table->count++;

  size = 1 << table->exponent;
  if (table->count > 2 * size){
    xfree (table->array);
    table->exponent++;
    size <<= 1;
    table->array = xcalloc (size * sizeof (entry_t), 1);
    rehash (table);
  }

  return found;
}



/**
 * I don't recommend using this function because it drops some memory
 * which will be unavailable from this moment.
 */
entry_t *
htable_remove (htable_t *table, const char *key)
{
  unsigned     hashval = hash (key, table->exponent);
  entry_t     *entry   = lookup_with_hash (table, key, hashval);
  entry_t     *e_prev  = table->array[hashval];
  entry_aux_t *list    = table->list;
  entry_aux_t *prev    = NULL;

  if (entry == NULL)
    return NULL;

  while (list){

    if (list->entry == entry)
      break;
    
    prev = list;
    list = list->next;
  }

  if (list == NULL)
    return NULL;

  if (prev == NULL)
    table->list = list->next;
  else
    prev->next  = list->next;

  if (e_prev == entry)
    table->array[hashval] = entry->next;
  else {
    while (e_prev->next != entry)
      e_prev = e_prev->next;
    e_prev->next = entry->next;
  }
  return entry;
}



void
htable_clear (htable_t *table, void (*fun)(void *))
{
  entry_aux_t *item;

  while (table->list){
    item        = table->list;
    table->list = table->list->next;

    if (fun)
      fun (item->entry->content);
  }
  memblock_destroy (table->memblock);
  table->list     = NULL;
  table->count    = 0;
  table->memblock = memblock_create (1 << (table->exponent + 4));
  memset (table->array, 0, (1 << table->exponent) * sizeof (entry_t *));
}



void
htable_iterator (htable_t *table, void (*fun)(entry_t *))
{
  entry_aux_t *list;

  for (list = table->list; list; list = list->next){
    fun (list->entry);
  }
}


/****************************************************************************
 *    INTERFACE CLASS BODIES
 ****************************************************************************/
/****************************************************************************
 *
 *    END MODULE hash.c
 *
 ****************************************************************************/