/**************************************************************************\
 *
 *  This file is part of the Coin 3D visualization library.
 *  Copyright (C) 1998-2006 by Systems in Motion.  All rights reserved.
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  ("GPL") version 2 as published by the Free Software Foundation.
 *  See the file LICENSE.GPL at the root directory of this source
 *  distribution for additional information about the GNU GPL.
 *
 *  For using Coin with software that can not be combined with the GNU
 *  GPL, and for taking advantage of the additional benefits of our
 *  support services, please contact Systems in Motion about acquiring
 *  a Coin Professional Edition License.
 *
 *  See http://www.coin3d.org/ for more information.
 *
 *  Systems in Motion, Postboks 1283, Pirsenteret, 7462 Trondheim, NORWAY.
 *  http://www.sim.no/  sales@sim.no  coin-support@coin3d.org
 *
\**************************************************************************/

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

#include "hash_adt.h"
#include <assert.h>
#include <string.h>

unsigned long
default_hashfunc(const unsigned long key)
{
  return key;
}

unsigned int
getIndex(hash_table * ht, unsigned long key)
{
    key = ht->hashfunc(key);
    key -= (key << 7); /* i.e. key = key * -127; */
    return key & (ht->size-1);    
}

void
resize(hash_table * ht, unsigned int newsize)
{
    hash_entry ** oldbuckets = ht->buckets;
    unsigned int oldsize = ht->size, i;

    assert((newsize & -newsize) == newsize); /* must be power of 2 */

    /* Never shrink the table */
    if (ht->size > newsize)
        return;

    ht->size = newsize;
    ht->elements = 0;
    ht->threshold = (unsigned int) (newsize * ht->loadfactor);
    ht->buckets = (hash_entry **) calloc(newsize, sizeof(hash_entry *));

    /* Transfer all mappings */
    for (i = 0; i < oldsize; i++) {
        hash_entry * he = oldbuckets[i];
        while (he) {
            HashTable_put(ht, he->key, he->val);
            he = he->next;
        }
    }
    free(oldbuckets);
}

hash_table *
HashTable_new(unsigned int size, float loadfactor)
{
    hash_table * ht = (hash_table *) malloc(sizeof(hash_table));
    
    /* Size must be a power of two */
    unsigned int s = 1;
    while (s < size)
        s <<= 1;

    if (loadfactor == 0.0f) loadfactor = 0.75f;

    ht->size = s;
    ht->elements = 0;
    ht->threshold = (unsigned int) (s * loadfactor);
    ht->loadfactor = loadfactor;
    ht->buckets = (hash_entry **) calloc(s, sizeof(hash_entry));
    ht->hashfunc = default_hashfunc;
    return ht;
}

void
HashTable_delete(hash_table * ht)
{
    HashTable_clear(ht);
    free(ht->buckets);
    free(ht);
}

void
HashTable_clear(hash_table * ht)
{
    unsigned int i;
    for (i = 0; i < ht->size; i++) {
        hash_entry * he = ht->buckets[i];
        while (he) {
            hash_entry * next = he->next;
            free(he);
            he = next;
        }
    }
    memset(ht->buckets, 0, ht->size * sizeof(hash_entry));
    ht->elements = 0;
}

/*!
  Inserts a new entry into the dictionary. \a key should be
  a unique number, and \a val is the generic user data.

  \e If \a key does not exist in the dictionary, a new entry
  is created and \c TRUE is returned. Otherwise, the generic user
  data is changed to \a val, and \c FALSE is returned.
*/
int
HashTable_put(hash_table * ht, unsigned long key, void * val)
{
    unsigned int i = getIndex(ht, key);
    hash_entry * he = ht->buckets[i];
    while (he) {
        if (he->key == key) {
            /* Replace the old value */
            he->val = val;
            return 0;
        }
        he = he->next;
    }

    /* Key not already in the hash table; insert a new
     * entry as the first element in the bucket
     */
    he = (hash_entry *) malloc(sizeof(hash_entry));
    he->key = key;
    he->val = val;
    he->next = ht->buckets[i];
    ht->buckets[i] = he;

    if (ht->elements++ >= ht->threshold)
        resize(ht, ht->size * 2);
    return 1;
}

/*!
  Searches for \a key in the dictionary. If an entry with this
  key exists, \c TRUE is returned and the entry value is returned
  in \a val. Otherwise, \c FALSE is returned.
*/
int
HashTable_get(hash_table * ht, unsigned long key, void ** val)
{
    unsigned int i = getIndex(ht, key);
    hash_entry * he = ht->buckets[i];
    while (he) {
        if (he->key == key) {
            *val = he->val;
            return 1;
        }
        he = he->next;
    }
    *val = NULL;
    return 0;
}

/*!
  Removes the entry with key \a key. \c TRUE is returned if an entry
  with this key was present, \c FALSE otherwise.
*/
int
HashTable_remove(hash_table * ht, unsigned long key)
{
    unsigned int i = getIndex(ht, key);
    hash_entry * he = ht->buckets[i];
    hash_entry * prev = NULL;
    while (he) {
        hash_entry * next = he->next;
        if (he->key == key) {
            ht->elements--;
            if (prev == NULL)
                ht->buckets[i] = next;
            else
                prev->next = next;

            free(he);
            return 1;
        }
        prev = he;
        he = next;
    }
    return 0;
}

unsigned int
HashTable_elements(hash_table * ht)
{
    return ht->elements;
}

void
HashTable_setHashFunc(hash_table * ht, unsigned long (*func)(const unsigned long key))
{
    ht->hashfunc = func;
}

void
HashTable_print_stat(hash_table * ht)
{
    unsigned int i, used_buckets = 0, max_chain_l = 0;
    for (i = 0; i < ht->size; i++) {
        if (ht->buckets[i]) {
            unsigned int chain_l = 0;
            hash_entry * he = ht->buckets[i];
            used_buckets++;
            while (he) {
                chain_l++;
                he = he->next;
            }
            if (chain_l > max_chain_l) max_chain_l = chain_l;
        }
    }
    printf("Used buckets %u of %u (%u elements), avg chain length: %.2f, max chain length: %u\n", used_buckets, ht->size, ht->elements, (float)ht->elements / used_buckets, max_chain_l);
}




