[PATCH 2/2] Use new traits to implement hash tables

[Lucas Gabriel Vuotto <lvuotto92@xxxxxxxxx>]

Signed-off-by: Lucas Gabriel Vuotto <lvuotto92@xxxxxxxxx>
---
 bench/hashit.myr                  |  12 ++--
 lib/date/parse.myr                |   2 +-
 lib/fileutil/loopcheck+posixy.myr |  30 +++++----
 lib/http/parse.myr                |  15 ++++-
 lib/inifile/parse.myr             |  19 +-----
 lib/inifile/types.myr             |  23 +++++++
 lib/regex/compile.myr             |   2 +-
 lib/std/bitset.myr                |  44 +++++++------
 lib/std/fmt.myr                   |   3 +-
 lib/std/hashfuncs.myr             | 128 --------------------------------------
 lib/std/htab.myr                  |  27 ++++----
 lib/std/resolve+posixy.myr        |   4 +-
 lib/std/wait+plan9.myr            |   2 +-
 mbld/deps.myr                     |   4 +-
 mbld/libs.myr                     |   6 +-
 mbld/main.myr                     |  12 ++--
 mbld/parse.myr                    |   4 +-
 mbld/syssel.myr                   |   4 +-
 support/dumpleak.myr              |  14 +----
 19 files changed, 122 insertions(+), 233 deletions(-)

diff --git a/bench/hashit.myr b/bench/hashit.myr
index e06343e7..8ec3b26e 100644
--- a/bench/hashit.myr
+++ b/bench/hashit.myr
@@ -5,21 +5,21 @@ const main = {
 	testr.bench([
 		[.name="hashstr", .fn={ctx;
 			for var i = 0; i < 1000; i++
-				std.strhash("foobar")
+				std.hash("foobar")
 			;;
 		}],
 		[.name="hashint", .fn={ctx
 			for var i = 0; i < 1000; i++
-				std.inthash(123)
+				std.hash(123)
 			;;
 		}],
 		[.name="hashlongstr", .fn={ctx
 			for var i = 0; i < 1000; i++
-				std.strhash(a)
+				std.hash(a)
 			;;
 		}],
 		[.name="htget", .fn={ctx
-			var h = std.mkht(std.strhash, std.streq)
+			var h = std.mkht()
 			std.htput(h, "foo", 123)
 			for var i = 0; i < 1000; i++
 				std.htget(h, "foo")
@@ -27,14 +27,14 @@ const main = {
 			std.htfree(h)
 		}],
 		[.name="htput", .fn={ctx
-			var h = std.mkht(std.strhash, std.streq)
+			var h = std.mkht()
 			for var i = 0; i < 1000; i++
 				std.htput(h, "foo", 123)
 			;;
 			std.htfree(h)
 		}],
 		[.name="htputmany", .fn={ctx
-			var h = std.mkht(std.inthash, std.inteq)
+			var h = std.mkht()
 			for var i = 0; i < 1000; i++
 				std.htput(h, i, 123)
 			;;
diff --git a/lib/date/parse.myr b/lib/date/parse.myr
index 19798ddf..559edc34 100644
--- a/lib/date/parse.myr
+++ b/lib/date/parse.myr
@@ -164,7 +164,7 @@ const eatspace = {s
 
 const indexof = {dst, s, set, err
 	for var i = 0; i < set.len; i++
-		if s.len >= set[i].len && std.streq(s[:set[i].len], set[i])
+		if s.len >= set[i].len && std.cmp(s[:set[i].len], set[i])
 			dst# = i
 			-> s[set[i].len:]
 		;;
diff --git a/lib/fileutil/loopcheck+posixy.myr b/lib/fileutil/loopcheck+posixy.myr
index 784fe3ff..0a311bfd 100644
--- a/lib/fileutil/loopcheck+posixy.myr
+++ b/lib/fileutil/loopcheck+posixy.myr
@@ -14,7 +14,7 @@ const mkloopcheck = {cwd
 	var ht : std.htab((int64, int64), void)#
 	var l
 
-	ht = std.mkht(fidhash, fideq)
+	ht = std.mkht()
 	l = (ht : loopcheck)
 	looped(l, cwd)
 	-> l
@@ -48,18 +48,22 @@ const fid = {p
 	;;
 }
 
-const fidhash = {fid
-	var dev, ino
+impl std.hashable (int64, int64) =
+	hash = {fid
+		var dev, ino
 
-	(dev, ino) = fid
-	-> std.inthash(dev) ^ std.inthash(ino)
-}
+		(dev, ino) = fid
+		-> std.hash(dev) ^ std.hash(ino)
+	}
+;;
 
-const fideq = {a, b
-	var adev, aino
-	var bdev, bino
+impl std.comparable (int64, int64) =
+	cmp = {a, b
+		var adev, aino
+		var bdev, bino
 
-	(adev, aino) = a
-	(bdev, bino) = b
-	-> adev == bdev && aino == bino
-}
+		(adev, aino) = a
+		(bdev, bino) = b
+		-> adev == bdev && aino == bino
+	}
+;;
diff --git a/lib/http/parse.myr b/lib/http/parse.myr
index fabf7a23..b92852fb 100644
--- a/lib/http/parse.myr
+++ b/lib/http/parse.myr
@@ -10,6 +10,19 @@ pkg http =
 	pkglocal const parsenumber	: (str : byte[:]#, base : int -> std.option(int))
 ;;
 
+const strcaseeq = {a : byte[:], b : byte[:] -> bool
+	var ca, cb
+
+	while a.len == 0 || b.len == 0
+		(ca, a) = std.strstep(a)
+		(cb, b) = std.strstep(b)
+		if std.tolower(ca) != std.tolower(cb)
+			-> false
+		;;
+	;;
+	-> a.len == b.len
+}
+
 const parsereq = {s
 	var r, err
 
@@ -221,7 +234,7 @@ const getenc = {r
 
 const findhdr = {r, name
 	for (k, v) : r.hdrs
-		if std.strcaseeq(k, name)
+		if strcaseeq(k, name)
 			-> `std.Some v
 		;;
 	;;
diff --git a/lib/inifile/parse.myr b/lib/inifile/parse.myr
index 6b9be91e..6276cf80 100644
--- a/lib/inifile/parse.myr
+++ b/lib/inifile/parse.myr
@@ -44,7 +44,7 @@ const loadf = {fd
 	var f
 
 	ini = std.mk([
-		.elts = std.mkht(keyhash, keyeq)
+		.elts = std.mkht()
 	])
 	p = std.mk([
 		.line = 1,
@@ -138,20 +138,3 @@ const parsekvp = {p, ini, ln
 		-> true
 	;;
 }
-
-const keyhash = {k
-	var sect, key
-
-	(sect, key) = k
-	-> std.strhash(sect) ^ std.strhash(key)
-}
-
-const keyeq = {a, b
-	var s1, k1
-	var s2, k2
-
-	(s1, k1) = a
-	(s2, k2) = a
-	-> std.streq(s1, s2) && std.streq(k1, k2)
-}
-
diff --git a/lib/inifile/types.myr b/lib/inifile/types.myr
index f573b7b4..f2736e07 100644
--- a/lib/inifile/types.myr
+++ b/lib/inifile/types.myr
@@ -11,4 +11,27 @@ pkg inifile =
 		sects	: byte[:][:]
 		elts	: std.htab((byte[:], byte[:]), byte[:])#
 	;;
+
+	impl std.hashable (byte[:], byte[:])
+	impl std.comparable (byte[:], byte[:])
+;;
+
+impl std.hashable (byte[:], byte[:]) =
+	hash = {k
+		var sect, key
+
+		(sect, key) = k
+		-> std.hash(sect) ^ std.hash(key)
+	}
+;;
+
+impl std.comparable (byte[:], byte[:]) =
+	cmp = {a, b
+		var s1, k1
+		var s2, k2
+
+		(s1, k1) = a
+		(s2, k2) = a
+		-> std.cmp(s1, s2) && std.cmp(k1, k2)
+	}
 ;;
diff --git a/lib/regex/compile.myr b/lib/regex/compile.myr
index edfa3aa7..29e53a25 100644
--- a/lib/regex/compile.myr
+++ b/lib/regex/compile.myr
@@ -46,7 +46,7 @@ const dbgcompile = {pat, trace
 		.nmatch = 1,
 		.debug = true,
 		.trace = trace,
-		.astloc = std.mkht(std.ptrhash, std.ptreq),
+		.astloc = std.mkht(),
 	])
 	res = regexcompile(re, 0)
 	-> res
diff --git a/lib/std/bitset.myr b/lib/std/bitset.myr
index afc66b40..3786758c 100644
--- a/lib/std/bitset.myr
+++ b/lib/std/bitset.myr
@@ -1,12 +1,13 @@
 use "alloc"
 use "die"
 use "extremum"
+use "hashfuncs"
 use "mk"
 use "slcp"
 use "sldup"
 use "slfill"
+use "traits"
 use "types"
-use "hashfuncs"
 
 pkg std =
 	type bitset = struct
@@ -28,9 +29,10 @@ pkg std =
 	const bsdiff	: (a : bitset#, b : bitset# -> void)
 	const bsintersect	: (a : bitset#, b : bitset# -> void)
 	const bsunion	: (a : bitset#, b : bitset# -> void)
-	const bseq	: (a : bitset#, b : bitset# -> bool)
 	const bsissubset	: (a : bitset#, b : bitset# -> bool)
-	const bshash	: (a : bitset# -> uint64)
+
+	impl comparable bitset#
+	impl hashable bitset#
 
 	type bsiter = struct
 		idx	: size
@@ -145,25 +147,29 @@ const bsissubset = {a, b
 	-> true
 }
 
-const bseq = {a, b
-	eqsz(a, b)
-	for var i = 0; i < a.bits.len; i++
-		if a.bits[i] != b.bits[i]
-			-> false
+impl comparable bitset# =
+	cmp = {a, b
+		eqsz(a, b)
+		for var i = 0; i < a.bits.len; i++
+			if a.bits[i] != b.bits[i]
+				-> false
+			;;
 		;;
-	;;
-	-> true
-}
+		-> true
+	}
+;;
 
-const bshash = {a
-	var end : size
+impl hashable bitset# =
+	hash = {a
+		var end : size
 
-	end = a.bits.len
-	while end > 0 && a.bits[end - 1] == 0
-		end--
-	;;
-	-> std.slhash(a.bits[:end])
-}
+		end = a.bits.len
+		while end > 0 && a.bits[end - 1] == 0
+			end--
+		;;
+		-> std.hash(a.bits[:end])
+	}
+;;
 
 const ensurelen = {bs, len
 	if bs.bits.len <= len
diff --git a/lib/std/fmt.myr b/lib/std/fmt.myr
index 1f542d31..e060bac5 100644
--- a/lib/std/fmt.myr
+++ b/lib/std/fmt.myr
@@ -21,6 +21,7 @@ use "striter"
 use "strsplit"
 use "syswrap"
 use "syswrap-ss"
+use "traits"
 use "types"
 use "utf"
 use "varargs"
@@ -55,7 +56,7 @@ pkg std =
 ;;
 
 const __init__ = {
-	fmtmap = mkht(strhash, streq)
+	fmtmap = mkht()
 }
 
 type fmtdesc = struct
diff --git a/lib/std/hashfuncs.myr b/lib/std/hashfuncs.myr
index 41422a16..fa72f904 100644
--- a/lib/std/hashfuncs.myr
+++ b/lib/std/hashfuncs.myr
@@ -9,23 +9,8 @@ use "types"
 use "utf"
 
 pkg std =
-	const strhash	: (s : byte[:]	-> uint64)
-	const streq	: (a : byte[:], b : byte[:]	-> bool)
-
-	const strcasehash	: (s : byte[:]	-> uint64)
-	const strcaseeq	: (a : byte[:], b : byte[:]	-> bool)
-
-	generic ptrhash	: (p : @a#	-> uint64)
-	generic ptreq	: (a : @a#, b : @a#	-> bool)
-
-	generic inthash	: (v : @a::(integral,numeric)	-> uint64)
-	generic inteq	: (a : @a::(integral,numeric), b : @a::(integral,numeric) -> bool)
-
-	const murmurhash2	: (data : byte[:], seed : uint32 -> uint32)
 	const siphash24	: (data : byte[:], seed : byte[16] -> uint64)
 
-	generic slhash	: (sl : @a[:] -> uint64)
-
 	impl comparable @a[:] =
 		cmp = {a, b
 			-> sleq(a, b)
@@ -65,119 +50,6 @@ pkg std =
 
 const Seed : byte[16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
 
-generic slhash = {data : @a[:]
-	-> strhash(slbytes(data))
-}
-
-generic slbytes = {data : @a[:]
-	var n
-
-	n = data.len * sizeof(@a)
-	-> (data : byte#)[:n]
-}
-
-const strhash = {s
-	-> siphash24(s, Seed)
-}
-
-const strcaseeq = {a, b
-	var ca, cb
-
-	while true
-		if a.len == 0 || b.len == 0
-			break
-		;;
-		(ca, a) = std.strstep(a)
-		(cb, b) = std.strstep(b)
-		if std.tolower(ca) != std.tolower(cb)
-			-> false
-		;;
-	;;
-	-> a.len == b.len
-}
-
-const strcasehash = {s
-	var chars
-	var c, h
-
-	chars = [][:]
-	while s.len != 0
-		(c, s) = std.strstep(s)
-		std.slpush(&chars, std.tolower(c))
-	;;
-	h = siphash24(slbytes(chars), Seed)
-	slfree(chars)
-	-> h
-}
-
-const streq = {a, b
-	-> sleq(a, b)
-}
-
-generic ptrhash = {p : @a#
-	-> inthash((p : intptr))
-}
-
-generic ptreq = {a, b
-	-> a == b
-}
-
-generic inthash = {v : @a::(integral,numeric)
-	var p
-
-	p = (&v : byte#)
-	-> siphash24(p[0:sizeof(@a)], Seed)
-}
-
-generic inteq = {a, b
-	-> a == b
-}
-
-const murmurhash2 = {data, seed
-	const m = 0x5bd1e995;
-	const r = 24
-	var h, k
-	
-	h = seed ^ data.len
-	while data.len >= 4
-		k = (data[0] : uint32)
-		k |= (data[1] : uint32) << 8
-		k |= (data[2] : uint32) << 16
-		k |= (data[3] : uint32) << 24
-
-		k *= m
-		k ^= k >> r
-		k *= m
-
-		h *= m
-		h ^= k
-		data = data[4:]
-	;;
-
-	match data.len
-	| 3:
-		h ^= (data[2] : uint32) << 16
-		h ^= (data[1] : uint32) << 8
-		h ^= (data[0] : uint32)
-		h *= m
-	| 2:
-		h ^= (data[1] : uint32) << 8
-		h ^= (data[0] : uint32)
-		h *= m
-	| 1:
-		h ^= (data[0] : uint32)
-		h *= m
-	| 0:	/* nothing */
-	| _:	die("0 < len < 4 must be true")
-	;;
-
-	h ^= h >> 13
-	h *= m
-	h ^= h >> 15
-
-	-> h
-}
-
 const sipround = {v0, v1, v2, v3 -> (uint64, uint64, uint64, uint64)
 	v0 += v1
 	v1 = (v1 << 13) | (v1 >> 51)
diff --git a/lib/std/htab.myr b/lib/std/htab.myr
index b728124d..368389f4 100644
--- a/lib/std/htab.myr
+++ b/lib/std/htab.myr
@@ -2,6 +2,7 @@ use "alloc"
 use "die"
 use "extremum"
 use "option"
+use "traits"
 use "types"
 
 pkg std =
@@ -17,8 +18,8 @@ pkg std =
 		dead	: bool[:]
 	;;
 
-	generic mkht	: (h : (k : @k -> uint64), eq : (a : @k, b : @k -> bool) -> htab(@k, @v)#)
-	generic htinit	: (ht : htab(@k, @v)#, h : (k : @k -> uint64), eq : (a : @k, b : @k -> bool) -> void)
+	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)
@@ -38,10 +39,10 @@ pkg std =
 
 const Initsz = 32
 
-generic hash = {ht, k
+generic xhash = {k
 	var h
 
-	h = ht.hash(k)
+	h = hash(k)
 	if h == 0
 		-> 1
 	else
@@ -82,7 +83,7 @@ generic idx = {ht, k
 	var h
 
 	di = 0
-	h = hash(ht, k)
+	h = xhash(k)
 	i = h & (ht.keys.len - 1)
 	while true
 		while ht.hashes[i] != 0 && !ht.dead[i] && ht.hashes[i] != h
@@ -92,7 +93,7 @@ generic idx = {ht, k
 		if ht.hashes[i] == 0
 			-> `None
 		;;
-		if ht.hashes[i] == h && !ht.dead[i] && ht.eq(ht.keys[i], k)
+		if ht.hashes[i] == h && !ht.dead[i] && cmp(ht.keys[i], k)
 			break
 		;;
 		di++
@@ -101,20 +102,16 @@ generic idx = {ht, k
 	-> `Some i
 }
 
-generic mkht = {h, eq
+generic mkht = {
 	var ht
 
 	ht = alloc()
-	htinit(ht, h, eq)
+	htinit(ht)
 
 	-> ht
 }
 
-generic htinit = {ht, h, eq
-
-	ht.hash = h
-	ht.eq = eq
-
+generic htinit = {ht
 	ht.nelt = 0
 	ht.ndead = 0
 	ht.keys = slalloc(Initsz)
@@ -137,11 +134,11 @@ generic htput = {ht, k, v
 	var neltincr
 
 	di = 0
-	h = hash(ht, k)
+	h = xhash(k)
 	i = h & (ht.keys.len - 1)
 	neltincr = 1
 	while ht.hashes[i] != 0 && !ht.dead[i]
-		if ht.hashes[i] == h &&	ht.eq(ht.keys[i], k)
+		if ht.hashes[i] == h &&	cmp(ht.keys[i], k)
 			neltincr = 0
 			break
 		;;
diff --git a/lib/std/resolve+posixy.myr b/lib/std/resolve+posixy.myr
index 8fa83525..b0f98f4f 100644
--- a/lib/std/resolve+posixy.myr
+++ b/lib/std/resolve+posixy.myr
@@ -72,8 +72,8 @@ var search	: byte[:][:]
 var nameservers	: netaddr[:]
 
 const __init__ = {
-	hostmap = mkht(strhash, streq)
-	dnscache = mkht(strhash, streq)
+	hostmap = mkht()
+	dnscache = mkht()
 	loadhosts()
 	loadresolv()
 }
diff --git a/lib/std/wait+plan9.myr b/lib/std/wait+plan9.myr
index 44177db7..2097c008 100644
--- a/lib/std/wait+plan9.myr
+++ b/lib/std/wait+plan9.myr
@@ -32,7 +32,7 @@ pkg std =
 var statusmap	: htab(pid, waitstatus)#
 
 const __init__ = {
-	statusmap = mkht(inthash, inteq)
+	statusmap = mkht()
 }
 
 const waitany = {
diff --git a/mbld/deps.myr b/mbld/deps.myr
index 1ad1b22d..6a2db692 100644
--- a/mbld/deps.myr
+++ b/mbld/deps.myr
@@ -362,8 +362,8 @@ const resolve = {b
 	;;
 
 	stk = [][:]
-	visited = std.mkht(std.ptrhash, std.ptreq)
-	looped = std.mkht(std.ptrhash, std.ptreq)
+	visited = std.mkht()
+	looped = std.mkht()
 	for n : g.nodes
 		checkloop(g, n, visited, looped, &stk)
 	;;
diff --git a/mbld/libs.myr b/mbld/libs.myr
index 487d1107..1aa2ad33 100644
--- a/mbld/libs.myr
+++ b/mbld/libs.myr
@@ -119,9 +119,9 @@ const addlibs = {b, sl, libs, incs
 	var added, diradded, looped
 	var lo
 
-	added  = std.mkht(std.strhash, std.streq)
-	looped  = std.mkht(std.strhash, std.streq)
-	diradded  = std.mkht(std.strhash, std.streq)
+	added  = std.mkht()
+	looped  = std.mkht()
+	diradded  = std.mkht()
 
 	lo = sl#.len
 	for l : libs
diff --git a/mbld/main.myr b/mbld/main.myr
index 606ae3bd..3362d3af 100644
--- a/mbld/main.myr
+++ b/mbld/main.myr
@@ -140,13 +140,13 @@ const mkbuild = {tags
 	var b
 
 	b = std.zalloc()
-	b.libs = std.mkht(std.strhash, std.streq)
-	b.proc = std.mkht(std.inthash, std.inteq)
-	b.targs = std.mkht(std.strhash, std.streq)
-	b.tags = std.mkht(std.strhash, std.streq)
+	b.libs = std.mkht()
+	b.proc = std.mkht()
+	b.targs = std.mkht()
+	b.tags = std.mkht()
 	b.deps = std.mk([
-		.targs = std.mkht(std.strhash, std.streq),
-		.gen = std.mkht(std.strhash, std.streq),
+		.targs = std.mkht(),
+		.gen = std.mkht(),
 		.leaves = [][:],
 		.nodes = [][:],
 	])
diff --git a/mbld/parse.myr b/mbld/parse.myr
index 0f1d0533..4d3d8508 100644
--- a/mbld/parse.myr
+++ b/mbld/parse.myr
@@ -61,8 +61,8 @@ const sortdeps = {b
 	var all
 
 	all = [][:]
-	looped = std.mkht(std.strhash, std.streq)
-	marked = std.mkht(std.strhash, std.streq)
+	looped = std.mkht()
+	marked = std.mkht()
 	for dep : b.all
 		match gettarg(b.targs, dep)
 		| `Bin _:	all = visit(all, b, "all", dep, looped, marked)
diff --git a/mbld/syssel.myr b/mbld/syssel.myr
index 9208d715..93ac5815 100644
--- a/mbld/syssel.myr
+++ b/mbld/syssel.myr
@@ -27,8 +27,8 @@ generic mksyssel = {b, file, line, targ
 		.file = file,
 		.line = line,
 		.targ = targ,
-		._match = std.mkht(std.strhash, std.streq),
-		._best = std.mkht(std.strhash, std.streq),
+		._match = std.mkht(),
+		._best = std.mkht(),
 		.sysattrs = b.tags
 	])
 	-> syssel
diff --git a/support/dumpleak.myr b/support/dumpleak.myr
index dcd6c07f..32d8e25f 100644
--- a/support/dumpleak.myr
+++ b/support/dumpleak.myr
@@ -38,7 +38,7 @@ const main = {args
 		;;
 	;;
 
-	stats.tab = std.mkht(std.inthash, std.inteq)
+	stats.tab = std.mkht()
 	for d : cmd.args
 		match bio.open(d, bio.Rd)
 		| `std.Ok f:	dump(d, f, &stats)
@@ -99,7 +99,7 @@ const tracefree = {path, f, stats
 const dumptrace = {tab
 	var aggr
 
-	aggr = std.mkht(hashintsl, std.sleq)
+	aggr = std.mkht()
 	for (k, (sz, stk)) : std.byhtkeyvals(tab)
 		match std.htget(aggr, stk[:stackaggr])
 		| `std.Some (count, total):	
@@ -120,13 +120,3 @@ const get64 = {path, f
 	| res:	std.fatal("failed to read {}: {}\n", path, res)
 	;;
 }
-
-const hashintsl = {sl
-	var h
-
-	h = 0
-	for i : sl
-		h ^= std.inthash(i)
-	;;
-	-> h
-}
-- 
2.14.2