/* flib - fundamental c library.
 *
 * Copyright (C) 2008- Luo Jinghua <sunmoon1997@gmail.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library 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
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
#include "milkwayint.h"
#include "milkway/mw-hash.h"

#include <stdlib.h>

/*
 * Credit for primes table: Aaron Krowne
 * http://br.endernet.org/~akrowne/
 * http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
 */
static const mw_uint_t primes[] = {
    11, 19, 37, 53, 97, 193, 389,
    769, 1543, 3079, 6151,
    12289, 24593, 49157, 98317,
    196613, 393241, 786433, 1572869,
    3145739, 6291469, 12582917, 25165843,
    50331653, 100663319, 201326611, 402653189,
    805306457, 1610612741
};

typedef struct _mw_hash_bucket {
    mw_pointer_t              key;
    mw_pointer_t              value;
    mw_uint_t                 hash_code;

    struct _mw_hash_bucket * next;
} mw_hash_bucket_t;

struct _mw_hash {
    mw_object_t         base;

    mw_size_t           size;
    mw_size_t           num_buckets;
    mw_hash_bucket_t ** buckets;

    mw_hash_func_t      hash_func;
    mw_equal_func_t     equal_func;

    mw_destroy_func_t   key_destroy_func;
    mw_destroy_func_t   value_destroy_func;
};

#define BUCKET_MATCH_KEY(b, h, hash_code, key)                  \
    ((b)->hash_code == (hash_code) &&                           \
     ((b)->key == (key) || (h)->equal_func ((b)->key, key)))

static mw_hash_t *
mw_hash_init (mw_hash_t        *self,
	      mw_hash_func_t    hash_func,
	      mw_equal_func_t   equal_func,
	      mw_destroy_func_t key_destroy_func,
	      mw_destroy_func_t value_destroy_func)
{
    if (!mw_object_init(&self->base))
	return NULL;

    self->buckets = calloc (sizeof (mw_hash_bucket_t *), primes[0]);
    if (!self->buckets) {
	MW_SUPER_FINALIZE(self, MW_HASH_TYPE)(&self->base);
        return NULL;
    }

    self->size = primes[0];
    self->num_buckets = 0;
    self->hash_func = hash_func;
    self->equal_func = equal_func;
    self->key_destroy_func = key_destroy_func;
    self->value_destroy_func = value_destroy_func;
    return self;
}

mw_hash_t *
mw_hash_new (mw_hash_func_t    hash_func,
	     mw_equal_func_t   equal_func,
	     mw_destroy_func_t key_destroy_func,
	     mw_destroy_func_t value_destroy_func)
{
    mw_hash_t *self = mw_object_alloc(MW_HASH_TYPE);

    if (!self)
	return NULL;
    return mw_hash_init(self, hash_func, equal_func,
			key_destroy_func, value_destroy_func);
}

static void
mw_hash_finalize (mw_object_t *super)
{
    mw_hash_t *self = (mw_hash_t*)super;

    mw_hash_clear (self);
    free (self->buckets);

    MW_SUPER_FINALIZE(super, MW_HASH_TYPE)(super);
}

static mw_hash_bucket_t *
mw_hash_bucket_alloc (mw_pointer_t   key,
		      mw_pointer_t   value,
		      mw_uint_t      hash_code,
		      mw_hash_t    * hash)
{
    mw_hash_bucket_t * bucket;

    bucket = malloc (sizeof (mw_hash_bucket_t));
    if (!bucket)
        return NULL;

    bucket->key = key;
    bucket->value = value;
    bucket->hash_code = hash_code;
    bucket->next = NULL;

    return bucket;
}

static void
mw_hash_bucket_fini (mw_hash_bucket_t * bucket,
		     mw_hash_t        * hash)
{
    if (hash->key_destroy_func)
        hash->key_destroy_func (bucket->key);
    if (hash->value_destroy_func)
        hash->value_destroy_func (bucket->value);
}

static void
mw_hash_bucket_free (mw_hash_bucket_t * bucket,
		     mw_hash_t        * hash)
{
    mw_hash_bucket_fini (bucket, hash);
    free (bucket);
}

void
mw_hash_clear (mw_hash_t * hash)
{
    mw_uint_t i;

    for (i = 0; i < hash->size; i++) {
        if (hash->buckets[i]) {
            mw_hash_bucket_free (hash->buckets[i], hash);
            hash->buckets[i] = NULL;
        }
    }

    hash->num_buckets = 0;
}

static mw_int_t
mw_hash_lookup_bucket (mw_hash_t          * hash,
		       mw_pointer_t         key,
		       mw_hash_bucket_t *** parent)
{
    mw_uint_t hash_code;
    mw_hash_bucket_t ** pos, * bucket;

    hash_code = hash->hash_func (key);
    pos = &hash->buckets[hash_code % hash->size];
    if (!(*pos))
        return -1;

    if (BUCKET_MATCH_KEY (*pos, hash, hash_code, key)) {
        if (parent)
            *parent = pos;
        return pos - hash->buckets;
    }

    for (bucket = (*pos)->next; bucket; bucket = bucket->next) {
        if (BUCKET_MATCH_KEY (bucket, hash, hash_code, key)) {
            if (parent)
                *parent = pos;
            return pos - hash->buckets;
        }
    }

    return -1;
}

static mw_uint_t
mw_hash_closest_size (mw_uint_t num)
{
    mw_uint_t i;

    for (i = 0; i < MW_ARRAY_SIZE (primes); i++)
        if (primes[i] > num)
            return primes[i];

    return primes[MW_ARRAY_SIZE (primes) - 1];
}

static mw_bool_t
mw_hash_resize (mw_hash_t    * hash)
{
    mw_hash_bucket_t ** old_buckets = hash->buckets;
    mw_hash_bucket_t ** new_buckets;
    mw_hash_bucket_t * bucket;
    mw_uint_t new_size;
    mw_uint_t i;

    new_size = mw_hash_closest_size (hash->num_buckets);
    if (new_size == hash->size)
        return MW_TRUE;

    new_buckets = calloc (sizeof (mw_hash_bucket_t *), new_size);
    if (!new_buckets)
        return MW_FALSE;

    for (i = 0; i < hash->size; i++) {
        mw_uint_t pos;

        bucket = hash->buckets[i];
        if (bucket) {
            pos = bucket->hash_code % new_size;
            bucket->next = new_buckets[pos];
            new_buckets[pos] = bucket;
        }
    }

    hash->buckets = new_buckets;
    hash->size = new_size;

    free (old_buckets);

    return MW_TRUE;
}

static mw_inline mw_bool_t
mw_hash_maybe_resize (mw_hash_t * hash)
{
    if ((hash->num_buckets * 4 >= hash->size * 3) ||
        (hash->num_buckets * 3 < hash->size))
        return mw_hash_resize (hash);

    return MW_TRUE;
}

mw_bool_t
mw_hash_lookup (mw_hash_t    * hash,
		mw_pointer_t   key,
		mw_pointer_t * retval)
{
    mw_int_t pos;

    pos = mw_hash_lookup_bucket (hash, key, NULL);
    if (pos < 0)
        return MW_FALSE;

    if (retval)
        *retval = hash->buckets[(mw_uint_t)pos]->value;

    return MW_TRUE;
}

mw_bool_t
mw_hash_insert (mw_hash_t    * hash,
		mw_pointer_t   key,
		mw_pointer_t   value)
{
    mw_uint_t hash_code;
    mw_hash_bucket_t ** pos, * bucket;

    mw_hash_maybe_resize (hash);
    if (hash->num_buckets == hash->size)
        return MW_FALSE;
    hash_code = hash->hash_func (key);
    pos = &hash->buckets[hash_code % hash->size];
    if (*pos && BUCKET_MATCH_KEY (*pos, hash, hash_code, key))
        return MW_FALSE;

    bucket = mw_hash_bucket_alloc (key, value, hash_code, hash);
    if (!bucket)
        return MW_FALSE;

    if (!*pos) {
        *pos = bucket;
    } else {
        mw_uint_t i;

        for (i = 0; i < hash->size; i++)
            if (!hash->buckets[i])
                break;

        mw_assert (i < hash->size);
        bucket->next = *pos;
        hash->buckets[i] = bucket;
    }
    hash->num_buckets++;

    return MW_TRUE;
}

mw_bool_t
mw_hash_replace (mw_hash_t    * hash,
		 mw_pointer_t   key,
		 mw_pointer_t   value)
{
    mw_uint_t hash_code;
    mw_hash_bucket_t ** parent, * bucket, * old;

    mw_hash_maybe_resize (hash);
    if (hash->num_buckets == hash->size)
        return MW_FALSE;
    hash_code = hash->hash_func (key);
    parent = &hash->buckets[hash_code % hash->size];

    for (bucket = *parent; bucket; bucket = bucket->next)
        if (BUCKET_MATCH_KEY (bucket, hash, hash_code, key))
            break;

    if (!bucket) {
        bucket = mw_hash_bucket_alloc (key, value, hash_code, hash);
        if (!bucket)
            return MW_FALSE;
        old = NULL;
    } else {
        old = bucket;
    }

    if (!*parent) {
        *parent = bucket;
    } else if (old) {
        mw_hash_bucket_fini (old, hash);

        old->key = key;
        old->value = value;
        old->hash_code = hash_code;
    } else {
        mw_uint_t i;

        for (i = 0; i < hash->size; i++)
            if (!hash->buckets[i])
                break;

        mw_assert (i < hash->size);
        bucket->next = *parent;
        hash->buckets[i] = bucket;
    }
    if (!old)
        hash->num_buckets++;

    return MW_TRUE;
}

mw_bool_t
mw_hash_remove (mw_hash_t    * hash,
		mw_pointer_t   key)
{
    mw_int_t pos;
    mw_hash_bucket_t ** parent, * bucket, *iter;

    pos = mw_hash_lookup_bucket (hash, key, &parent);
    if (pos < 0)
        return MW_FALSE;

    bucket = hash->buckets[(mw_uint_t)pos];
    if (parent - hash->buckets == pos) {
        *parent = bucket->next;
    } else {
        for (iter = *parent; iter->next && iter->next != bucket; iter = iter->next)
            ;

        mw_assert (iter && iter->next == bucket);
        iter->next = bucket->next;
    }

    mw_hash_bucket_free (bucket, hash);
    hash->num_buckets--;

    mw_hash_maybe_resize (hash);

    return MW_TRUE;
}

mw_bool_t
mw_hash_take (mw_hash_t    * hash,
	      mw_pointer_t   key,
	      mw_pointer_t * origin_key,
	      mw_pointer_t * value)
{
    mw_int_t pos;
    mw_hash_bucket_t ** parent, * bucket, *iter;

    pos = mw_hash_lookup_bucket (hash, key, &parent);
    if (pos < 0)
        return MW_FALSE;

    bucket = hash->buckets[(mw_uint_t)pos];
    if (parent - hash->buckets == pos) {
        *parent = bucket->next;
    } else {
        for (iter = *parent; iter->next && iter->next != bucket;
	     iter = iter->next)
            ;

        mw_assert (iter && iter->next == bucket);
        iter->next = bucket->next;
    }

    if (origin_key)
        *origin_key = bucket->key;
    if (value)
        *value = bucket->value;
    free (bucket);
    hash->num_buckets--;

    mw_hash_maybe_resize (hash);

    return MW_TRUE;
}

mw_hash_iter_t*
mw_hash_first(mw_hash_t *hash, mw_hash_iter_t *iter)
{
    if (!hash->num_buckets)
	return NULL;

    for (iter->pos = 0; iter->pos < hash->size; iter->pos++)
	if (hash->buckets[iter->pos]) {
	    iter->key = hash->buckets[iter->pos]->key;
	    iter->value = hash->buckets[iter->pos]->value;
	    return iter;
	}

    return MW_FALSE;
}

mw_hash_iter_t*
mw_hash_next(mw_hash_t *hash, mw_hash_iter_t *iter)
{
    iter->pos++;
    for (; iter->pos < hash->size; iter->pos++)
	if (hash->buckets[iter->pos]) {
	    iter->key = hash->buckets[iter->pos]->key;
	    iter->value = hash->buckets[iter->pos]->value;
	    return iter;
	}

    return NULL;
}

size_t
mw_hash_get_size(mw_hash_t *hash)
{
    return hash->num_buckets;
}

static void
mw_hash_type_init(mw_hash_type_t *self)
{
    self->base.finalize = mw_hash_finalize;
}

MW_DEFINE_GET_TYPE(mw_hash, mw_hash_type_t,
		   MW_OBJECT_TYPE, "MWHashTable", 0);