summaryrefslogtreecommitdiff
path: root/lib/std/test/htab.myr
blob: 16040f0e7527dddb048b96e7b62d56408c1fa72e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
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
	}
;;