/****************************************************************************
 * KONOHA COPYRIGHT, LICENSE NOTICE, AND DISCRIMER  
 * 
 * Copyright (c) 2005-2008, Kimio Kuramitsu <kimio at ynu.ac.jp>
 *           (c) 2008-      Konoha Software Foundation  
 * All rights reserved.
 * 
 * You may choose one of the following two licenses when you use konoha. 
 * See www.konohaware.org/license.html for further information.
 * 
 * (1) GNU General Public License 2.0      (with    KONOHA_UNDER_GPL2)
 * (2) Konoha Software Foundation License 1.0
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 ****************************************************************************/

/* ************************************************************************ */

#include"commons.h"


/* ************************************************************************ */

#ifdef __cplusplus 
extern "C" {
#endif

/* ------------------------------------------------------------------------ */

#define _LRUMap                          HashMap
#define _knh_LRUMap                      knh_HashMap

#define _new_LRUMap(ctx,n)               new_HashMap(ctx,n)
#define _knh_LRUMap_get(ctx,b,kh,ko)     knh_HashMap_get(ctx,b,kh,ko)
#define _knh_LRUMap_set(ctx,b,kh,ko,v)   knh_HashMap_set(ctx,b,kh,ko,v)

/* ======================================================================== */
/* [hashmape] */

INLINE
knh_hashmape_t *knh_HashMape_new(Ctx *ctx, knh_hcode_t key, Object *kobj, Object *value) 
{
	knh_hashmape_t *cur = (knh_hashmape_t*)KNH_MALLOC(ctx, sizeof(knh_hashmape_t));
	cur->h.key = key;
	if(kobj == NULL) kobj = KNH_NULL;
	KNH_INITv(cur->h.keyobj, kobj);
	KNH_INITv(cur->value, value);
	cur->next = NULL;
	return cur;
}

/* ------------------------------------------------------------------------ */

INLINE
void knh_HashMape_traverse(Ctx *ctx, knh_hashmape_t *cur, f_traverse gc)
{
	gc(ctx, cur->h.keyobj);
	gc(ctx, cur->value);
	if(IS_SWEEP(gc)) {
		KNH_FREE(cur, sizeof(knh_hashmape_t));
	}
}

/* ======================================================================== */
/* [structs] */

void
knh_HashMap_struct_init(Ctx *ctx, knh_HashMap *b, int init, Object *cs)
{
	if(init == 0) init = KNH_HASHMAP_INITSIZE; 
	b->capacity = KNH_MAX(13, init);
	b->factor   = KNH_HASHMAP_INITFACTOR;
	b->size = 0;
	b->array = (knh_hashmape_t**)KNH_MALLOC(ctx, sizeof(knh_hashmape_t*) * b->capacity);
	knh_bzero(b->array, sizeof(knh_hashmape_t*) * b->capacity);
}

/* ------------------------------------------------------------------------ */

void
knh_HashMap_struct_copy(Ctx *ctx, knh_HashMap *b1, knh_HashMap *b2)
{
	TODO();
}

/* ------------------------------------------------------------------------ */

#define _knh_HashMap_struct_compare NULL

/* ------------------------------------------------------------------------ */

void
knh_HashMap_struct_traverse(Ctx *ctx, knh_HashMap *b, f_traverse gc)
{
	knh_hashmape_t *cur, *next;
	size_t i;
	for(i = 0; i < b->capacity; i++) {
		cur = b->array[i];
		while(cur != NULL) {
			next = cur->next;
			knh_HashMape_traverse(ctx, cur, gc);
			cur = next;
		}
	}
	if(IS_SWEEP(gc)) {
		KNH_FREE(b->array, sizeof(knh_hashmape_t*) * b->capacity);
	}
}

/* ======================================================================== */
/* [constructors] */

HashMap* new_HashMap(Ctx *ctx, size_t capacity)
{
	HashMap* o = 
		(HashMap*)new_Object__RAW(ctx, FLAG_HashMap, CLASS_HashMap, sizeof(knh_HashMap));
	knh_HashMap_struct_init(ctx, DP(o), capacity, NULL);
	return o;
}


/* ======================================================================== */
/* [methods] */

/* @method Any2 HashMap.get(Any1 key) */

Object *knh_HashMap_get(Ctx *ctx, HashMap *b, knh_hcode_t key, Any *kobj)
{
	knh_uint_t h = key % DP(b)->capacity;
	knh_hashmape_t *cur = DP(b)->array[h];
	while(cur != NULL) {
		if(cur->h.key == key) {
			if(kobj == NULL) {
				return cur->value;
			}
			if(knh_Object_equals(kobj, cur->h.keyobj)) {
				return cur->value;
			}
		}
		cur = cur->next;
	}
	return KNH_NULL;
}

/* ------------------------------------------------------------------------ */

Object *knh_HashMap_get__b(HashMap *b, knh_bytes_t kv)  
{
	knh_hcode_t key = knh_bytes_hcode(kv);
	knh_uint_t h =  key % DP(b)->capacity;
	knh_hashmape_t *cur = DP(b)->array[h];
	
	while(cur != NULL) {
		if(cur->h.key == key) {
			if(IS_bString(cur->h.keyobj) && knh_String_equals((String*)cur->h.keyobj, kv)) {
				return cur->value;
			}
		}
		cur = cur->next;
	}
	return KNH_NULL;
}

/* ------------------------------------------------------------------------ */

void knh_HashMap_rehash(Ctx *ctx, HashMap *b)
{
	if(((float)DP(b)->size / DP(b)->capacity) < DP(b)->factor) {
		return ;
	}
	knh_HashMap_resize(ctx, b, DP(b)->capacity * 2 + 1);
}

/* ------------------------------------------------------------------------ */

void knh_HashMap_resize(Ctx *ctx, HashMap *b, size_t nc)
{
	size_t i, nh;
	//DEBUG_RESIZE(b, DP(b)->array, DP(b)->capacity, nc);
	knh_hashmape_t **na = (knh_hashmape_t**)KNH_MALLOC(ctx, sizeof(knh_hashmape_t*) * nc);	
	for(i = 0; i < nc; i++) na[i] = NULL;

	knh_hashmape_t *cur, *next;
	for(i = 0; i < DP(b)->capacity; i++) {
		cur = DP(b)->array[i];
		while(cur != NULL) {
			next = cur->next; 
			nh = cur->h.key % nc;
			cur->next = na[nh];
			na[nh] = cur;  /* push top */
			cur = next;
		}	
	}
	KNH_FREE(DP(b)->array, sizeof(knh_hashmape_t*) * DP(b)->capacity);
	DP(b)->array = na;
	DP(b)->capacity = nc;
}

/* ------------------------------------------------------------------------ */
/* @method void HashMap.set(Any1 key, Any2 value) */

void knh_HashMap_set(Ctx *ctx, HashMap *b, knh_hcode_t key, Any *kobj, Any *value)
{
	KNH_ASSERT(IS_HashMap(b));
	if(((float)DP(b)->size / DP(b)->capacity) > DP(b)->factor) {
		knh_HashMap_rehash(ctx, b);
	}

	knh_uint_t h = key % DP(b)->capacity;
	knh_hashmape_t *cur = DP(b)->array[h];

	while(cur != NULL) {
		if(cur->h.key == key) {
			if(kobj == NULL) {
				KNH_ASSERT(cur->h.keyobj == NULL);
				KNH_SETv(ctx, cur->value, value);
				return;
			}
			if(knh_Object_equals(kobj, cur->h.keyobj)) {
				KNH_SETv(ctx, cur->h.keyobj, kobj);
				KNH_SETv(ctx, cur->value, value);
				return;
			}
		}
		cur = cur->next;
	}
	cur = knh_HashMape_new(ctx, key, kobj, value);
	cur->next = DP(b)->array[h];
	DP(b)->array[h] = cur;
	DP(b)->size++;
}

#define _knh_HashMap_put(ctx,b,h,k,v) knh_HashMap_set(ctx,b,h,k,v)

/* ------------------------------------------------------------------------ */
/* @method void HashMap.remove(Any1 key) */

void knh_HashMap_remove(Ctx *ctx, HashMap *b, knh_hcode_t key, Any *kobj)
{
	knh_uint_t h = key % DP(b)->capacity;
	knh_hashmape_t **prev, *cur;
	
	prev = &DP(b)->array[h];
	cur = *prev;
	while(cur != NULL) {
		if(cur->h.key == key) {
			if(kobj == NULL || knh_Object_equals(kobj, cur->h.keyobj)) {
				*prev = cur->next;
				knh_HashMape_traverse(ctx, cur, knh_Object_RCsweep);
				DP(b)->size--;
				return ;
			}
		}
		prev = &cur->next;
		cur = *prev;
	}
}

/* ------------------------------------------------------------------------ */


#ifdef __cplusplus
}
#endif
