shithub: mc

ref: eb21d4f1381f73045c81df0840aa50df20515045
dir: /lib/std/htab.myr/

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

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

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

	generic mkht	: (h : (k : @k -> uint32), eq : (a : @k, b : @k -> bool) -> htab(@k, @v)#)
	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 htbykeyvals	: (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 hash = {ht, k
	var h

	h = ht.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 = hash(ht, 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] && ht.eq(ht.keys[i], k)
			break
		;;
		di++
		i = (h + di) & (ht.keys.len - 1)
	;;
	-> `Some i
}

generic mkht = {h, eq
	var ht

	ht = alloc()

	ht.hash = h
	ht.eq = eq

	ht.nelt = 0
	ht.ndead = 0
	ht.keys = slalloc(Initsz)
	ht.vals = slalloc(Initsz)
	ht.hashes = slzalloc(Initsz)
	ht.dead = slzalloc(Initsz)
	-> ht
}

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 = hash(ht, k)
	i = h & (ht.keys.len - 1)
	neltincr = 1
	while ht.hashes[i] != 0 && !ht.dead[i]
		/* second insertion overwrites */
		if ht.hashes[i] == h && !ht.dead[i]
			/* dead key, we can just insert here */
			if ht.dead[i]
				break
			/* replacing a key */
			elif ht.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 htbykeyvals = {ht
	-> [.ht = ht, .idx = 0]
}

extern const put	: (str : byte[:], args : ... -> size)

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
	}
;;