ref: 285be77897e18d68efede25a98f423bddd4f2cb9
dir: /lib/std/test/htab.myr/
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() /* create a hash table with a few hundred values */ for i = 0; i < 4000; i++ std.htput(ht, (i : collisionprone), (i : collisionprone)) ;; for i = 0; i < 200; i++ std.htdel(ht, (i*2 : collisionprone)) ;; for i = 0; i < 200; i++ std.assert(!std.hthas(ht, (i*2 : collisionprone)), "deleted item still present") ;; for i = 0; i < 200; i++ std.assert(std.hthas(ht, (i*2+1 : collisionprone)), "undeleted item missing") ;; for i = 400; i < 4000; i++ std.assert(std.hthas(ht, (i : collisionprone)), "undeleted item missing") ;; } const collision = { var ht var i ht = std.mkht() /* insert an element a few hundred times */ for i = 0; i < 500; i++ std.htput(ht, 0, (i : collisionprone)) ;; std.assert(std.hthas(ht, (0 : collisionprone)), "inserted element not present") std.assert(std.htgetv(ht, (0 : collisionprone), -1) == 499, "inserted element has wrong value") std.htdel(ht, 0) std.assert(!std.hthas(ht, (0 : collisionprone)), "element left in table") } const tombstonefill = { var ht var i ht = std.mkht() /* 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 : collisionprone), i) std.htdel(ht, (i : collisionprone)) ;; /* 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 : collisionprone)), "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() } type collisionprone = int impl std.hashable collisionprone = hash = {x -> (x : uint64) } ;; impl std.equatable collisionprone = eq = {a, b -> a == b } ;;