236 lines · 3.7 KB · Text
RawDownload
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 found 	di = 0	h = xhash(k)	i = h & (ht.keys.len - 1)	found = false	while ht.hashes[i] != 0 && !ht.dead[i]		if ht.hashes[i] == h &&	eq(ht.keys[i], k)			found = true			break		;;		di++		i = (h + di) & (ht.keys.len - 1)	;;	if !found		ht.keys[i] = k		ht.nelt++	;;	ht.hashes[i] = h	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	};;

Keyboard shortcuts

General

Show keyboard shortcuts
?
Focus the current search
/

Issues and pull requests

Open filters
f

Issues, pull requests and Inbox

Select next item
j↓
Select previous item
k↑
Open selected item
Enter
Dismiss filters or clear selection
Esc

Repository code

Go to file
t