/*
 * frost_hash_table.cpp
 *
 *  Created on: Jul 5, 2012
 *      Author: ergino
 */

#include <stdio.h>
#include <math.h>
#include "frost_mem.h"
#include "frost_list.h"
#include "frost_common.h"



static frost_pointer KEYMARKER_REMOVED = &KEYMARKER_REMOVED;


static const frost_uint prime_tbl[] = {
    11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237,
    1861, 2777, 4177, 6247, 9371, 14057, 21089, 31627,
    47431, 71143, 106721, 160073, 240101, 360163,
    540217, 810343, 1215497, 1823231, 2734867, 4102283,
    6153409, 9230113, 13845163
};

static frost_bool
test_prime (int x)
{
    if ((x & 1) != 0) {
        int n;
        for (n = 3; n< (int)sqrt (x); n += 2) {
            if ((x % n) == 0)
                return frost_false;
        }
        return frost_true;
    }
    // There is only one even prime - 2.
    return (x == 2);
}

static int
calc_prime (int x)
{
    int i;

    for (i = (x & (~1))-1; i< FROST_MAXINT32; i += 2) {
        if (test_prime (i))
            return i;
    }
    return x;
}

frost_uint
frost_spaced_primes_closest (frost_uint x)
{
    int i;

    for (i = 0; i < FROST_N_ELEMENTS (prime_tbl); i++) {
        if (x <= prime_tbl [i])
            return prime_tbl [i];
    }
    return calc_prime (x);
}

FROSTHashTable *
frost_hash_table_new (FROSTHashFunc hash_func, FROSTEqualFunc key_equal_func)
{
    FROSTHashTable *hash;

    if (hash_func == NULL)
        hash_func = frost_direct_hash;
    if (key_equal_func == NULL)
        key_equal_func = frost_direct_equal;
    hash = frost_new0 (FROSTHashTable, 1);

    hash->hash_func = hash_func;
    hash->key_equal_func = key_equal_func;

    hash->table_size = frost_spaced_primes_closest (1);
    hash->table = frost_new0 (Slot *, hash->table_size);
    hash->last_rehash = hash->table_size;

    return hash;
}

FROSTHashTable *
frost_hash_table_new_full (FROSTHashFunc hash_func, FROSTEqualFunc key_equal_func,
               FROSTDestroyNotify key_destroy_func, FROSTDestroyNotify value_destroy_func)
{
    FROSTHashTable *hash = frost_hash_table_new (hash_func, key_equal_func);
    if (hash == NULL)
        return NULL;

    hash->key_destroy_func = key_destroy_func;
    hash->value_destroy_func = value_destroy_func;

    return hash;
}

#if 0
static void
dump_hash_table (FROSTHashTable *hash)
{
    int i;

    for (i = 0; i < hash->table_size; i++) {
        Slot *s;

        for (s = hash->table [i]; s != NULL; s = s->next){
            frost_uint hashcode = (*hash->hash_func) (s->key);
            frost_uint slot = (hashcode) % hash->table_size;
            printf ("key %p hash %x on slot %d correct slot %d tb size %d\n", s->key, hashcode, i, slot, hash->table_size);
        }
    }
}
#endif

#ifdef SANITY_CHECK
static void
sanity_check (FROSTHashTable *hash)
{
    int i;

    for (i = 0; i < hash->table_size; i++) {
        Slot *s;

        for (s = hash->table [i]; s != NULL; s = s->next){
            frost_uint hashcode = (*hash->hash_func) (s->key);
            frost_uint slot = (hashcode) % hash->table_size;
            if (slot != i) {
                dump_hashcode_func = 1;
                hashcode = (*hash->hash_func) (s->key);
                dump_hashcode_func = 0;
                frost_error ("Key %p (bucket %d) on invalid bucket %d (hashcode %x) (tb size %d)", s->key, slot, i, hashcode, hash->table_size);
            }
        }
    }
}
#else

#define sanity_check(HASH) do {}while(0)

#endif

static void
do_rehash (FROSTHashTable *hash)
{
    int current_size, i;
    Slot **table;

    /* printf ("Resizing diff=%d slots=%d\n", hash->in_use - hash->last_rehash, hash->table_size); */
    hash->last_rehash = hash->table_size;
    current_size = hash->table_size;
    hash->table_size = frost_spaced_primes_closest (hash->in_use);
    /* printf ("New size: %d\n", hash->table_size); */
    table = hash->table;
    hash->table = frost_new0 (Slot *, hash->table_size);

    for (i = 0; i < current_size; i++){
        Slot *s, *next;

        for (s = table [i]; s != NULL; s = next){
            frost_uint hashcode = ((*hash->hash_func) (s->key)) % hash->table_size;
            next = s->next;

            s->next = hash->table [hashcode];
            hash->table [hashcode] = s;
        }
    }
    frost_free (table);
}

static void
rehash (FROSTHashTable *hash)
{
    int diff = ABS (hash->last_rehash - hash->in_use);

    /* These are the factors to play with to change the rehashing strategy */
    /* I played with them with a large range, and could not really get */
    /* something that was too good, maybe the tests are not that great */
    if (!(diff * 0.75 > hash->table_size * 2))
        return;
    do_rehash (hash);
    sanity_check (hash);
}

void
frost_hash_table_insert_replace (FROSTHashTable *hash, frost_pointer key, frost_pointer value, frost_bool replace)
{
    frost_uint hashcode;
    Slot *s;
    FROSTEqualFunc equal;

    frost_return_if_fail (hash != NULL);
    sanity_check (hash);

    equal = hash->key_equal_func;
    if (hash->in_use >= hash->threshold)
        rehash (hash);

    hashcode = ((*hash->hash_func) (key)) % hash->table_size;
    for (s = hash->table [hashcode]; s != NULL; s = s->next){
        if ((*equal) (s->key, key)){
            if (replace){
                if (hash->key_destroy_func != NULL)
                    (*hash->key_destroy_func)(s->key);
                s->key = key;
            }
            if (hash->value_destroy_func != NULL)
                (*hash->value_destroy_func) (s->value);
            s->value = value;
            sanity_check (hash);
            return;
        }
    }
    s = frost_new (Slot, 1);
    s->key = key;
    s->value = value;
    s->next = hash->table [hashcode];
    hash->table [hashcode] = s;
    hash->in_use++;
    sanity_check (hash);
}

FROST_List*
frost_hash_table_get_keys (FROSTHashTable *hash)
{
    FROSTHashTableIter iter;
    FROST_List *rv = NULL;
    frost_pointer key;

    frost_hash_table_iter_init (&iter, hash);

    while (frost_hash_table_iter_next (&iter, &key, NULL))
        rv = frost_list_prepend (rv, key);

    return frost_list_reverse (rv);
}

FROST_List*
frost_hash_table_get_values (FROSTHashTable *hash)
{
    FROSTHashTableIter iter;
    FROST_List *rv = NULL;
    frost_pointer value;

    frost_hash_table_iter_init (&iter, hash);

    while (frost_hash_table_iter_next (&iter, NULL, &value))
        rv = frost_list_prepend (rv, value);

    return frost_list_reverse (rv);
}


frost_uint
frost_hash_table_size (FROSTHashTable *hash)
{
    frost_return_val_if_fail (hash != NULL, 0);

    return hash->in_use;
}

frost_pointer
frost_hash_table_lookup (FROSTHashTable *hash, frost_constpointer key)
{
    frost_pointer orig_key, value;

    if (frost_hash_table_lookup_extended (hash, key, &orig_key, &value))
        return value;
    else
        return NULL;
}

frost_bool
frost_hash_table_lookup_extended (FROSTHashTable *hash, frost_constpointer key, frost_pointer *orig_key, frost_pointer *value)
{
    FROSTEqualFunc equal;
    Slot *s;
    frost_uint hashcode;

    frost_return_val_if_fail (hash != NULL, frost_false);
    sanity_check (hash);
    equal = hash->key_equal_func;

    hashcode = ((*hash->hash_func) (key)) % hash->table_size;

    for (s = hash->table [hashcode]; s != NULL; s = s->next){
        if ((*equal)(s->key, key)){
            if (orig_key)
                *orig_key = s->key;
            if (value)
                *value = s->value;
            return frost_true;
        }
    }
    return frost_false;
}

void
frost_hash_table_foreach (FROSTHashTable *hash, FROSTHFunc func, frost_pointer user_data)
{
    int i;

    frost_return_if_fail (hash != NULL);
    frost_return_if_fail (func != NULL);

    for (i = 0; i < hash->table_size; i++){
        Slot *s;

        for (s = hash->table [i]; s != NULL; s = s->next)
            (*func)(s->key, s->value, user_data);
    }
}

frost_pointer
frost_hash_table_find (FROSTHashTable *hash, FROSTHRFunc predicate, frost_pointer user_data)
{
    int i;

    frost_return_val_if_fail (hash != NULL, NULL);
    frost_return_val_if_fail (predicate != NULL, NULL);

    for (i = 0; i < hash->table_size; i++){
        Slot *s;

        for (s = hash->table [i]; s != NULL; s = s->next)
            if ((*predicate)(s->key, s->value, user_data))
                return s->value;
    }
    return NULL;
}

void
frost_hash_table_remove_all (FROSTHashTable *hash)
{
    int i;

    frost_return_if_fail (hash != NULL);

    for (i = 0; i < hash->table_size; i++){
        Slot *s;

        while (hash->table [i]) {
            s = hash->table [i];
            frost_hash_table_remove (hash, s->key);
        }
    }
}

frost_bool
frost_hash_table_remove (FROSTHashTable *hash, frost_constpointer key)
{
    FROSTEqualFunc equal;
    Slot *s, *last;
    frost_uint hashcode;

    frost_return_val_if_fail (hash != NULL, frost_false);
    sanity_check (hash);
    equal = hash->key_equal_func;

    hashcode = ((*hash->hash_func)(key)) % hash->table_size;
    last = NULL;
    for (s = hash->table [hashcode]; s != NULL; s = s->next){
        if ((*equal)(s->key, key)){
            if (hash->key_destroy_func != NULL)
                (*hash->key_destroy_func)(s->key);
            if (hash->value_destroy_func != NULL)
                (*hash->value_destroy_func)(s->value);
            if (last == NULL)
                hash->table [hashcode] = s->next;
            else
                last->next = s->next;
            frost_free (s);
            hash->in_use--;
            sanity_check (hash);
            return frost_true;
        }
        last = s;
    }
    sanity_check (hash);
    return frost_false;
}

frost_uint
frost_hash_table_foreach_remove (FROSTHashTable *hash, FROSTHRFunc func, frost_pointer user_data)
{
    int i;
    int count = 0;

    frost_return_val_if_fail (hash != NULL, 0);
    frost_return_val_if_fail (func != NULL, 0);

    sanity_check (hash);
    for (i = 0; i < hash->table_size; i++){
        Slot *s, *last;

        last = NULL;
        for (s = hash->table [i]; s != NULL; ){
            if ((*func)(s->key, s->value, user_data)){
                Slot *n;

                if (hash->key_destroy_func != NULL)
                    (*hash->key_destroy_func)(s->key);
                if (hash->value_destroy_func != NULL)
                    (*hash->value_destroy_func)(s->value);
                if (last == NULL){
                    hash->table [i] = s->next;
                    n = s->next;
                } else  {
                    last->next = s->next;
                    n = last->next;
                }
                frost_free (s);
                hash->in_use--;
                count++;
                s = n;
            } else {
                last = s;
                s = s->next;
            }
        }
    }
    sanity_check (hash);
    if (count > 0)
        rehash (hash);
    return count;
}

frost_bool
frost_hash_table_steal (FROSTHashTable *hash, frost_constpointer key)
{
    FROSTEqualFunc equal;
    Slot *s, *last;
    frost_uint hashcode;

    frost_return_val_if_fail (hash != NULL, frost_false);
    sanity_check (hash);
    equal = hash->key_equal_func;

    hashcode = ((*hash->hash_func)(key)) % hash->table_size;
    last = NULL;
    for (s = hash->table [hashcode]; s != NULL; s = s->next){
        if ((*equal)(s->key, key)) {
            if (last == NULL)
                hash->table [hashcode] = s->next;
            else
                last->next = s->next;
            frost_free (s);
            hash->in_use--;
            sanity_check (hash);
            return frost_true;
        }
        last = s;
    }
    sanity_check (hash);
    return frost_false;

}

frost_uint
frost_hash_table_foreach_steal (FROSTHashTable *hash, FROSTHRFunc func, frost_pointer user_data)
{
    int i;
    int count = 0;

    frost_return_val_if_fail (hash != NULL, 0);
    frost_return_val_if_fail (func != NULL, 0);

    sanity_check (hash);
    for (i = 0; i < hash->table_size; i++){
        Slot *s, *last;

        last = NULL;
        for (s = hash->table [i]; s != NULL; ){
            if ((*func)(s->key, s->value, user_data)){
                Slot *n;

                if (last == NULL){
                    hash->table [i] = s->next;
                    n = s->next;
                } else  {
                    last->next = s->next;
                    n = last->next;
                }
                frost_free (s);
                hash->in_use--;
                count++;
                s = n;
            } else {
                last = s;
                s = s->next;
            }
        }
    }
    sanity_check (hash);
    if (count > 0)
        rehash (hash);
    return count;
}

void
frost_hash_table_destroy (FROSTHashTable *hash)
{
    int i;

    frost_return_if_fail (hash != NULL);

    for (i = 0; i < hash->table_size; i++){
        Slot *s, *next;

        for (s = hash->table [i]; s != NULL; s = next){
            next = s->next;

            if (hash->key_destroy_func != NULL)
                (*hash->key_destroy_func)(s->key);
            if (hash->value_destroy_func != NULL)
                (*hash->value_destroy_func)(s->value);
            frost_free (s);
        }
    }
    frost_free (hash->table);

    frost_free (hash);
}

void
frost_hash_table_print_stats (FROSTHashTable *table)
{
    int i, max_chain_index, chain_size, max_chain_size;
    Slot *node;

    max_chain_size = 0;
    max_chain_index = -1;
    for (i = 0; i < table->table_size; i++) {
        chain_size = 0;
        for (node = table->table [i]; node; node = node->next)
            chain_size ++;
        if (chain_size > max_chain_size) {
            max_chain_size = chain_size;
            max_chain_index = i;
        }
    }

    printf ("Size: %d Table Size: %d Max Chain Length: %d at %d\n", table->in_use, table->table_size, max_chain_size, max_chain_index);
}

void
frost_hash_table_iter_init (FROSTHashTableIter *it, FROSTHashTable *hash_table)
{
    Iter *iter = (Iter*)it;

    memset (iter, 0, sizeof (Iter));
    iter->ht = hash_table;
    iter->slot_index = -1;
}

frost_bool frost_hash_table_iter_next (FROSTHashTableIter *it, frost_pointer *key, frost_pointer *value)
{
    Iter *iter = (Iter*)it;

    FROSTHashTable *hash = iter->ht;

    if(! (iter->slot_index != -2)) return frost_false ;
    if(! (sizeof (Iter) <= sizeof (FROSTHashTableIter))) return frost_false ;

    if (!iter->slot) {
        while (frost_true) {
            iter->slot_index ++;
            if (iter->slot_index >= hash->table_size) {
                iter->slot_index = -2;
                return frost_false;
            }
            if (hash->table [iter->slot_index])
                break;
        }
        iter->slot = hash->table [iter->slot_index];
    }

    if (key)
        *key = iter->slot->key;
    if (value)
        *value = iter->slot->value;
    iter->slot = iter->slot->next;

    return frost_true;
}

frost_bool
frost_direct_equal (frost_constpointer v1, frost_constpointer v2)
{
    return v1 == v2;
}

frost_uint
frost_direct_hash (frost_constpointer v1)
{
    return frost_pointer_TO_UINT(v1);
}

frost_bool
frost_int_equal (frost_constpointer v1, frost_constpointer v2)
{
    return *(frost_int *)v1 == *(frost_int *)v2;
}

frost_uint
frost_int_hash (frost_constpointer v1)
{
    return *(frost_uint *)v1;
}

frost_bool
frost_str_equal (frost_constpointer v1, frost_constpointer v2)
{
    return strcmp (v1, v2) == 0;
}

frost_uint
frost_str_hash (frost_constpointer v1)
{
    frost_uint hash = 0;
    char *p = (char *) v1;

    while (*p++)
        hash = (hash << 5) - (hash + *p);

    return hash;
}
