summaryrefslogtreecommitdiff
path: root/lib/std/test/htab.myr
diff options
context:
space:
mode:
Diffstat (limited to 'lib/std/test/htab.myr')
-rw-r--r--lib/std/test/htab.myr104
1 files changed, 104 insertions, 0 deletions
diff --git a/lib/std/test/htab.myr b/lib/std/test/htab.myr
new file mode 100644
index 0000000..1801d76
--- /dev/null
+++ b/lib/std/test/htab.myr
@@ -0,0 +1,104 @@
+use std
+
+const insertion = {
+ /*
+ var ht
+ var i
+
+ ht = std.mkht(idhash, ideq)
+ /* only a few values; shouldn't trigger growth */
+ for i = 0; i < 5; i++
+ std.htput(ht, i, i)
+ ;;
+ for i = 0; i < 5; i++
+ std.assert(std.htgetv(ht, i, -1) == i, "returned incorrect value from hash table")
+ ;;
+
+ /* and grow */
+ for i = 0; i < 5000; i++
+ std.htput(ht, i, i)
+ ;;
+ for i = 0; i < 5000; i++
+ std.assert(std.htgetv(ht, i, -1) == i, "returned incorrect value from hash table")
+ ;;
+ */
+}
+
+const deletion = {
+ var ht
+ var i
+
+ ht = std.mkht(idhash, ideq)
+ /* create a hash table with a few hundred values */
+ for i = 0; i < 4000; i++
+ std.htput(ht, i, i)
+ ;;
+ for i = 0; i < 200; i++
+ std.htdel(ht, i*2)
+ ;;
+ for i = 0; i < 200; i++
+ std.assert(!std.hthas(ht, i*2), "deleted item still present")
+ ;;
+ for i = 0; i < 200; i++
+ std.assert(std.hthas(ht, i*2+1), "undeleted item missing")
+ ;;
+ for i = 400; i < 4000; i++
+ std.assert(std.hthas(ht, i), "undeleted item missing")
+ ;;
+
+}
+
+const collision = {
+ var ht
+ var i
+
+ ht = std.mkht(idhash, ideq)
+ /* insert an element a few hundred times */
+ for i = 0; i < 500; i++
+ std.htput(ht, 0, i)
+ ;;
+ std.assert(std.hthas(ht, 0), "inserted element not present")
+ std.assert(std.htgetv(ht, 0, -1) == 499, "inserted element has wrong value")
+ std.htdel(ht, 0)
+ std.assert(!std.hthas(ht, 0), "element left in table")
+}
+
+const tombstonefill = {
+ var ht
+ var i
+
+ ht = std.mkht(idhash, ideq)
+ /*
+ insert an element into each slot in the hash table, and
+ delete it. With direct hashing, this is guaranteed to have
+ put a tombstone into each slot.
+ */
+ for i = 0; i <= ht.keys.len; i++
+ std.htput(ht, i, i)
+ std.htdel(ht, i)
+ ;;
+ /* make sure we haven't actually got anything in the table */
+ std.assert(ht.nelt == 0, "elements left in hash table")
+ std.assert(!std.hthas(ht, 1), "found phantom element")
+}
+
+const main = {
+ /* only a few elements */
+ std.put("insertion\n")
+ insertion()
+ std.put("deletion\n")
+ deletion()
+ std.put("collision\n")
+ collision()
+
+ /* what happens if we try to fill everything up with tombstones? */
+ tombstonefill()
+}
+
+const idhash = {x
+ -> x
+}
+
+const ideq = {a, b
+ -> a == b
+}