shithub: mc

ref: 30c662571c4f64f72171cca0efc7bedc59bd53fa
dir: /lib/std/htab.myr/

use "alloc"
use "die"
use "extremum"
use "option"
use "traits"
use "types"

pkg std =
	type htab(@k, @v) = struct
		hash	: (k : @k	-> uint64)
		eq	: (a : @k, b : @k -> bool)

		nelt	: size
		ndead	: size
		keys	: @k[:]
		vals	: @v[:]
		hashes	: uint64[:]
		dead	: bool[:]
	;;

	generic mkht	: ( -> htab(@k, @v)#)
	generic htinit	: (ht : htab(@k, @v)# -> void)
	generic htfree	: (ht : htab(@k, @v)# -> void)
	generic htput	: (ht : htab(@k, @v)#, k : @k, v : @v -> void)
	generic htdel	: (ht : htab(@k, @v)#, k : @k -> void)
	generic htget	: (ht : htab(@k, @v)#, k : @k -> option(@v))
	generic htgetv	: (ht : htab(@k, @v)#, k : @k, fallback : @v-> @v)
	generic hthas	: (ht : htab(@k, @v)#, k : @k -> bool)
	generic htkeys	: (ht : htab(@k, @v)# -> @k[:])
	generic htcount	: (ht : htab(@k, @v)# -> std.size)

	generic byhtkeyvals	: (ht : htab(@k, @v)# -> htkviter(@k, @v))
	impl iterable htkviter(@k, @v) -> (@k, @v)
	type htkviter(@k, @v) = struct
		ht	: std.htab(@k, @v)#
		idx	: size
	;;
;;

const Initsz = 32

generic xhash = {k
	var h

	h = hash(k)
	if h == 0
		-> 1
	else
		-> h
	;;
}

generic resize = {ht, sz
	var oldk
	var oldv
	var oldh
	var oldd

	oldk = ht.keys
	oldv = ht.vals
	oldh = ht.hashes
	oldd = ht.dead
	ht.keys = slalloc(sz)
	ht.vals = slalloc(sz)
	ht.hashes = slzalloc(sz)
	ht.dead = slzalloc(sz)

	ht.nelt = 0
	ht.ndead = 0
	for var i = 0; i < oldk.len; i++
		if oldh[i] != 0 && !oldd[i]
			htput(ht, oldk[i], oldv[i])
		;;
	;;
	slfree(oldk)
	slfree(oldv)
	slfree(oldh)
	slfree(oldd)
}

generic idx = {ht, k
	var i, di
	var h

	di = 0
	h = xhash(k)
	i = h & (ht.keys.len - 1)
	while true
		while ht.hashes[i] != 0 && !ht.dead[i] && ht.hashes[i] != h
			di++
			i = (h + di) & (ht.keys.len - 1)
		;;
		if ht.hashes[i] == 0
			-> `None
		;;
		if ht.hashes[i] == h && !ht.dead[i] && eq(ht.keys[i], k)
			break
		;;
		di++
		i = (h + di) & (ht.keys.len - 1)
	;;
	-> `Some i
}

generic mkht = {
	var ht

	ht = alloc()
	htinit(ht)

	-> ht
}

generic htinit = {ht
	ht.nelt = 0
	ht.ndead = 0
	ht.keys = slalloc(Initsz)
	ht.vals = slalloc(Initsz)
	ht.hashes = slzalloc(Initsz)
	ht.dead = slzalloc(Initsz)
}

generic htfree = {ht
	slfree(ht.keys)
	slfree(ht.vals)
	slfree(ht.hashes)
	slfree(ht.dead)
	free(ht)
}

generic htput = {ht, k, v
	var i, di
	var h
	var neltincr

	di = 0
	h = xhash(k)
	i = h & (ht.keys.len - 1)
	neltincr = 1
	while ht.hashes[i] != 0 && !ht.dead[i]
		if ht.hashes[i] == h &&	eq(ht.keys[i], k)
			neltincr = 0
			break
		;;
		di++
		i = (h + di) & (ht.keys.len - 1)
	;;
	ht.nelt += neltincr
	ht.hashes[i] = h
	ht.keys[i] = k
	ht.vals[i] = v
	ht.dead[i] = false
	if ht.keys.len < ht.nelt * 2
		resize(ht, 2*ht.keys.len)
	;;
}

generic htdel = {ht, k
	match idx(ht, k)
	| `Some i:
		ht.dead[i] = true
		ht.nelt--
		ht.ndead++
		/* remove tombstones if we shrink enough */
		if ht.keys.len < ht.ndead * 4
			resize(ht, ht.keys.len)
		;;
	| _:	
		/* do nothing */
	;;
}

generic htget = {ht, k
	match idx(ht, k)
	| `Some i:	-> `Some ht.vals[i]
	| `None:	-> `None
	;;
}

generic htgetv = {ht, k, v
	match idx(ht, k)
	| `Some i:	-> ht.vals[i]
	| `None:	-> v
	;;
}

generic hthas = {ht, k
	match idx(ht, k)
	| `Some i:	-> true
	| `None:	-> false
	;;
}

generic htkeys = {ht
	var keys
	var j

	keys = slalloc(ht.nelt)
	j = 0
	for var i = 0; i < ht.keys.len; i++
		if ht.hashes[i] != 0 && !ht.dead[i]
			keys[j++] = ht.keys[i]
		;;
	;;
	-> keys
}

generic htcount = {ht
	-> ht.nelt
}

generic byhtkeyvals = {ht
	-> [.ht = ht, .idx = 0]
}

impl iterable htkviter(@k, @v) -> (@k, @v) =
	__iternext__ = {itp, valp
		var i, ht

		ht = itp.ht
		for i = itp.idx; i < ht.keys.len; i++
			if ht.hashes[i] != 0 && !ht.dead[i]
				itp.idx = i + 1
				valp# = (ht.keys[i], ht.vals[i])
				-> true
			;;
		;;
		itp.idx = i
		-> false
	}

	__iterfin__ = {itp, valp -> void
	}
;;