/*
 * %CopyrightBegin%
 *
 * Copyright Ericsson AB 2011. All Rights Reserved.
 *
 * The contents of this file are subject to the Erlang Public License,
 * Version 1.1, (the "License"); you may not use this file except in
 * compliance with the License. You should have received a copy of the
 * Erlang Public License along with this software. If not, it can be
 * retrieved online at http://www.erlang.org/.
 *
 * Software distributed under the License is distributed on an "AS IS"
 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
 * the License for the specific language governing rights and limitations
 * under the License.
 *
 * %CopyrightEnd%
 *
 * hashmaps are an adaption of Rich Hickeys Persistent HashMaps
 *   which were an adaption of Phil Bagwells - Hash Array Mapped Tries
 *
 * Author: Björn-Egil Dahlberg
 */
/*
 * Ls = lists:seq(1,188888).
 * A = lists:foldl(fun(I,O) -> hashmap:put(I,I,O) end, hashmap:new(), Ls).
 * lists:foreach(fun(I) -> io:format("looking up ~p got ~p~n", [I, hashmap:get(I, A)]), I = hashmap:get(I,A) end, Ls).
 *
 * lists:foldl(fun(I,O) -> hashmap:put(I,I,O) end, hashmap:new(), lists:seq(1,7)).
 *
 */

#ifdef HAVE_CONFIG_H
#  include "config.h"
#endif

#include "sys.h"
#include "erl_vm.h"
#include "global.h"
#include "erl_process.h"
#include "error.h"
#include "bif.h"

#include "erl_hashmap.h"

#ifndef DECL_AM
#define DECL_AM(S) Eterm AM_ ## S = am_atom_put(#S, sizeof(#S) - 1)
#endif

static char *format_binary(Uint64 x, char *b) {
    int z;
    b[64] = '\0';
    for (z = 0; z < 64; z++) { 
	b[63-z] = ((x>>z) & 0x1) ? '1' : '0'; 
    }
    return b;
}

static Uint32 hashmap_shift_hash(Uint32 hx, Uint *lvl, Eterm key);
static Uint32 hashmap_restore_hash(Uint lvl, Eterm key);
static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node);
static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node);
static Eterm hashmap_to_list(Process *p, Eterm map);

/* hashmap:new/0 */

BIF_RETTYPE hashmap_new_0(BIF_ALIST_0) {
    Eterm* hp;
    hashmap_head_t *head;

    hp   = HAlloc(BIF_P, HAMT_HEAD_EMPTY_SZ);
    head = (hashmap_head_t *) hp;

    head->thing_word = MAP_HEADER_HAMT_HEAD_BITMAP(0);
    head->size       = 0;

    BIF_RET(make_hashmap(head));
}

/* hashmap:put/3 */

BIF_RETTYPE hashmap_put_3(BIF_ALIST_3) {
    if (is_hashmap(BIF_ARG_3)) {
	Uint32 hx = make_hash2(BIF_ARG_1);
	Eterm map;

	map = hashmap_insert(BIF_P, hx, BIF_ARG_1, BIF_ARG_2, BIF_ARG_3);
	ASSERT(is_hashmap(map));
	BIF_RET(map);
    }
    BIF_ERROR(BIF_P, BADARG);
}

/* hashmap:to_list/1 */

BIF_RETTYPE hashmap_to_list_1(BIF_ALIST_1) {
    if (is_hashmap(BIF_ARG_1)) {
	return hashmap_to_list(BIF_P, BIF_ARG_1);
    }

    BIF_ERROR(BIF_P, BADARG);
}

/* hashmap:get/2 */

BIF_RETTYPE hashmap_get_2(BIF_ALIST_2) {
    if (is_hashmap(BIF_ARG_2)) {
	const Eterm *value;
	Uint32 hx = make_hash2(BIF_ARG_1);
	
	if ((value = hashmap_get(hx, BIF_ARG_1, BIF_ARG_2)) != NULL) {
	    BIF_RET(*value);
	}
    }
    BIF_ERROR(BIF_P, BADARG);
}

/* hashmap:size/1 */

BIF_RETTYPE hashmap_size_1(BIF_ALIST_1) {
    if (is_hashmap(BIF_ARG_1)) {
	Eterm *head, *hp, res;
	Uint size, hsz=0;

	head = hashmap_val(BIF_ARG_1);
	size = head[1];
	(void) erts_bld_uint(NULL, &hsz, size);
	hp = HAlloc(BIF_P, hsz);
	res = erts_bld_uint(&hp, NULL, size);
	BIF_RET(res);
    }
    BIF_ERROR(BIF_P, BADARG);
}

/* erlang:is_hashmap/1 */

BIF_RETTYPE is_hashmap_1(BIF_ALIST_1) {
    if (is_hashmap(BIF_ARG_1)) {
	BIF_RET(am_true);
    }
    BIF_RET(am_false);
}

/* impl. */

static const Eterm *hashmap_get(Uint32 hx, Eterm key, Eterm node) {
    Eterm *ptr, hdr;
    Uint ix,slot, lvl = 0;
    Uint32 hval,bp;

    for (;;) {
	switch(primary_tag(node)) {
	    case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */
		ptr = list_val(node);
		if (EQ(CAR(ptr), key)) {
		    return &(CDR(ptr));
		}
		return NULL;
	    case TAG_PRIMARY_BOXED:
		ptr = boxed_val(node);
		hdr = *ptr;
		ASSERT(is_header(hdr));

		switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
		    case HAMT_SUBTAG_NODE_ARRAY:
			ix   = hashmap_index(hx);
			hx   = hashmap_shift_hash(hx,&lvl,key);
			node = ptr[ix+1];
			break;
		    case HAMT_SUBTAG_HEAD_ARRAY:
			ix   = hashmap_index(hx);
			hx   = hashmap_shift_hash(hx,&lvl,key);
			node = ptr[ix+2];
			break;
		    case HAMT_SUBTAG_NODE_BITMAP:
			hval = MAP_HEADER_VAL(hdr);
			ix   = hashmap_index(hx);
			bp   = 1 << ix;
			slot = hashmap_bitcount(hval & (bp - 1));

			/* occupied */
			if (bp & hval) {
			    hx    = hashmap_shift_hash(hx,&lvl,key);
			    node  = ptr[slot+1];
			    break;
			}
			/* not occupied */
			return NULL;
		    case HAMT_SUBTAG_HEAD_BITMAP:
			hval = MAP_HEADER_VAL(hdr);
			ix   = hashmap_index(hx);
			bp   = 1 << ix;
			slot = hashmap_bitcount(hval & (bp - 1));

			/* occupied */
			if (bp & hval) {
			    hx    = hashmap_shift_hash(hx,&lvl,key);
			    node  = ptr[slot+2];
			    break;
			}
			/* not occupied */
			return NULL;
		    default:
			erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
			break;
		}
		break;
	    default:
		erl_exit(1, "bad primary tag %p\r\n", node);
		break;
	}
    }
    return NULL;
}

static Eterm hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value, Eterm node) {
    Eterm *hp = NULL, *nhp = NULL;
    Eterm *ptr;
    Eterm hdr,res,ckey,fake;
    Uint32 ix, cix, bp, hval, chx;
    Uint slot, lvl = 0, clvl;
    Uint size = 0, n = 0, update_size = 1;
    DECLARE_ESTACK(stack);

    for (;;) {
	switch(primary_tag(node)) {
	    case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */
		ptr  = list_val(node);
		ckey = CAR(ptr);
		if (EQ(ckey, key)) {
		    update_size = 0;
		    goto unroll;
		}
		goto insert_subnodes;
	    case TAG_PRIMARY_BOXED:
		ptr = boxed_val(node);
		hdr = *ptr;
		ASSERT(is_header(hdr));

		switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
		    case HAMT_SUBTAG_NODE_ARRAY:
			ix    = hashmap_index(hx);
			hx    = hashmap_shift_hash(hx,&lvl,key);
			size += HAMT_NODE_ARRAY_SZ;
			ESTACK_PUSH2(stack, ix, node);
			node  = ptr[ix+1];
			break;
		    case HAMT_SUBTAG_HEAD_ARRAY:
			ix    = hashmap_index(hx);
			hx    = hashmap_shift_hash(hx,&lvl,key);
			size += HAMT_HEAD_ARRAY_SZ;
			ESTACK_PUSH2(stack, ix, node);
			node  = ptr[ix+2];
			break;
		    case HAMT_SUBTAG_NODE_BITMAP:
			hval = MAP_HEADER_VAL(hdr);
			ix   = hashmap_index(hx);
			bp   = 1 << ix;
			slot = hashmap_bitcount(hval & (bp - 1));
			n    = hashmap_bitcount(hval);

			ESTACK_PUSH(stack, n);
			ESTACK_PUSH3(stack, bp, slot, node);

			/* occupied */
			if (bp & hval) {
			    hx    = hashmap_shift_hash(hx,&lvl,key);
			    node  = ptr[slot+1];
			    ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); 
			    size += HAMT_NODE_BITMAP_SZ(n);
			    break;
			}
			/* not occupied */
			size += HAMT_NODE_BITMAP_SZ(n+1);
			goto unroll;
		    case HAMT_SUBTAG_HEAD_BITMAP:
			hval = MAP_HEADER_VAL(hdr);
			ix   = hashmap_index(hx);
			bp   = 1 << ix;
			slot = hashmap_bitcount(hval & (bp - 1));
			n    = hashmap_bitcount(hval);

			ESTACK_PUSH(stack, n);
			ESTACK_PUSH3(stack, bp, slot, node);

			/* occupied */
			if (bp & hval) {
			    hx    = hashmap_shift_hash(hx,&lvl,key);
			    node  = ptr[slot+2];
			    ASSERT(HAMT_HEAD_BITMAP_SZ(n) <= 18); 
			    size += HAMT_HEAD_BITMAP_SZ(n);
			    break;
			}
			/* not occupied */
			size += HAMT_HEAD_BITMAP_SZ(n+1);
			goto unroll;
		    default:
			erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
			break;
		}
		break;
	    default:
		erl_exit(1, "bad primary tag %p\r\n", node);
		break;
	}
    }
insert_subnodes:
    clvl  = lvl;
    chx   = hashmap_restore_hash(clvl,ckey);
    size += HAMT_NODE_BITMAP_SZ(2);
    ix    = hashmap_index(hx);
    cix   = hashmap_index(chx);

    while (cix == ix) {
	ESTACK_PUSH(stack, 0);
	ESTACK_PUSH3(stack, 1 << ix, 0, MAP_HEADER_HAMT_NODE_BITMAP(0));
	size += HAMT_NODE_BITMAP_SZ(1);
	hx    = hashmap_shift_hash(hx,&lvl,key);
	chx   = hashmap_shift_hash(chx,&clvl,ckey);
	ix    = hashmap_index(hx);
	cix   = hashmap_index(chx);
    }
    ESTACK_PUSH3(stack, cix, ix, node);

unroll:
    size += 2;
    hp  = HAlloc(p, size);
    res = CONS(hp, key, value); hp += 2;

    do {
	node = ESTACK_POP(stack);
	switch(primary_tag(node)) {
	    case TAG_PRIMARY_LIST:
		ix   = (Uint32) ESTACK_POP(stack);
		cix  = (Uint32) ESTACK_POP(stack);

		nhp   = hp;
		*hp++ = MAP_HEADER_HAMT_NODE_BITMAP((1 << ix) | (1 << cix));
		if (ix < cix) {
		    *hp++ = res;
		    *hp++ = node;
		} else {
		    *hp++ = node;
		    *hp++ = res;
		}
		res = make_hashmap(nhp);
		break;
	    case TAG_PRIMARY_HEADER:
		/* subnodes, fake it */
		fake = node;
		node = make_boxed(&fake);
	    case TAG_PRIMARY_BOXED:
		ptr = boxed_val(node);
		hdr = *ptr;
		ASSERT(is_header(hdr));

		switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
		    case HAMT_SUBTAG_NODE_ARRAY:
			slot  = (Uint)   ESTACK_POP(stack);
			nhp   = hp;
			n     = HAMT_NODE_ARRAY_SZ;
			while(n--) { *hp++ = *ptr++; }
			nhp[slot+1] = res;
			res = make_hashmap(nhp);
			break;
		    case HAMT_SUBTAG_HEAD_ARRAY:
			slot  = (Uint)   ESTACK_POP(stack);
			nhp   = hp;
			n     = HAMT_HEAD_ARRAY_SZ - 2;
			*hp++ = MAP_HEADER_HAMT_HEAD_ARRAY; ptr++;
			*hp++ = (*ptr++) + update_size;
			while(n--) { *hp++ = *ptr++; }
			nhp[slot+2] = res;
			res = make_hashmap(nhp);
			break;
		    case HAMT_SUBTAG_NODE_BITMAP:
			slot  = (Uint)   ESTACK_POP(stack);
			bp    = (Uint32) ESTACK_POP(stack);
			n     = (Uint32) ESTACK_POP(stack);
			hval  = MAP_HEADER_VAL(hdr);
			nhp   = hp;
			*hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hval | bp); ptr++;

			n -= slot;
			while(slot--) { *hp++ = *ptr++; }
			*hp++ = res;
			if (hval & bp) { ptr++; n--; }
			while(n--) { *hp++ = *ptr++; }

			if ((hval | bp) == 0xffff) {
			    *nhp = make_arityval(16);
			}
			res = make_hashmap(nhp);
			break;
		    case HAMT_SUBTAG_HEAD_BITMAP:
			slot  = (Uint)   ESTACK_POP(stack);
			bp    = (Uint32) ESTACK_POP(stack);
			n     = (Uint32) ESTACK_POP(stack);
			hval  = MAP_HEADER_VAL(hdr);
			nhp   = hp;
			*hp++ = MAP_HEADER_HAMT_HEAD_BITMAP(hval | bp); ptr++;
			*hp++ = (*ptr++) + update_size;

			n -= slot;
			while(slot--) { *hp++ = *ptr++; }
			*hp++ = res;
			if (hval & bp) { ptr++; n--; }
			while(n--) { *hp++ = *ptr++; }

			if ((hval | bp) == 0xffff) {
			    *nhp = MAP_HEADER_HAMT_HEAD_ARRAY;
			}
			res = make_hashmap(nhp);
			break;
		    default:
			erl_exit(1, "bad header tag %x\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
			break;
		}
		break;
	    default:
		erl_exit(1, "bad primary tag %x\r\n", primary_tag(node));
		break;
	}

    } while(!ESTACK_ISEMPTY(stack));

    DESTROY_ESTACK(stack);
    ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
    ERTS_HOLE_CHECK(p);
    return res;
}

static Eterm hashmap_to_list(Process *p, Eterm node) {
    Eterm *hp;
    Eterm res = NIL;
    Eterm *ptr, tup, hdr;
    Uint sz, n;
    DECLARE_ESTACK(stack);

    ptr = boxed_val(node);
    n   = (Uint)ptr[1];
    hp  = HAlloc(p, n * (2 + 3));
    ESTACK_PUSH(stack, node);
    do {
	node = ESTACK_POP(stack);
	switch(primary_tag(node)) {
	    case TAG_PRIMARY_LIST:
		ptr = list_val(node);
		tup = TUPLE2(hp, CAR(ptr), CDR(ptr)); hp += 3;
		res = CONS(hp, tup, res); hp += 2;
		break;
	    case TAG_PRIMARY_BOXED:
		ptr = boxed_val(node);
		hdr = *ptr;
		ASSERT(is_header(hdr));
		switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
		    case HAMT_SUBTAG_HEAD_ARRAY:
			ptr++;
		    case HAMT_SUBTAG_NODE_ARRAY:
			ptr++;
			sz = 16;
			while(sz--) { ESTACK_PUSH(stack, ptr[sz]); }
			break;
		    case HAMT_SUBTAG_HEAD_BITMAP:
			ptr++;
		    case HAMT_SUBTAG_NODE_BITMAP:
			sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
			ASSERT(sz < 17);
			ptr++;
			while(sz--) { ESTACK_PUSH(stack, ptr[sz]); }
			break;
		    default:
			erl_exit(1, "bad header\r\n");
			break;
		}
	}
    } while(!ESTACK_ISEMPTY(stack));

    DESTROY_ESTACK(stack);
    ERTS_HOLE_CHECK(p);
    return res;
}

static Uint32 hashmap_restore_hash(Uint lvl, Eterm key) {
    Eterm heap[2], ret;

    if (lvl < 8) {
	return make_hash2(key) >> (4*lvl);
    }
    ret = CONS(heap, make_small(lvl), key);

    return make_hash2(ret) >> (4*(lvl % 8));
}

static Uint32 hashmap_shift_hash(Uint32 hx, Uint *lvl, Eterm key) {
    Eterm heap[2], ret;

    /* rehash with [ lvl | key ] */
    *lvl = *lvl + 1;
    if (*lvl % 8) {
	return hx >> 4;
    }

    ret = CONS(heap, make_small((*lvl)), key);
    return make_hash2(ret);
}