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
|
structure Hashtable: HASHTABLE = struct
open Array
open Word
(* buf * taken * mask *)
type 'a t = ((string * 'a) option array * int * word) ref
val ` = Word.fromInt
val ~> = Word.toInt
infixr 4 <<
infix 5 andb
infixr 6 +
infixr 7 *
fun createLog log =
let
val size = `1 << `log
val mask = size - `1
in
ref (array (Word.toInt size, NONE), 0, mask)
end
exception Full
fun hash key =
List.foldl (fn (c, s) => s * `31 + `(ord c)) (`17) (explode key)
fun checkFreeSpace (array, taken, _) =
let
open Real
val ` = fromInt
in
if `taken / `(length array) > 0.75 then
raise Full
else
()
end
fun next idx mask = (idx + `1) andb mask
fun insertIfNew H key v =
let
val (array, _, mask) = !H
fun inc H =
let
open Int
val (array, taken, mask) = !H
in
H := (array, taken + 1, mask)
end
val () = checkFreeSpace $ !H
fun find idx =
case sub (array, ~> idx) of
NONE => (update (array, ~> idx, SOME (key, v)); inc H; NONE)
| SOME (key', v') =>
if key' = key then
(SOME v')
else
find (next idx mask)
in
find (hash key andb mask)
end
fun taken H =
let
val (_, taken, _) = !H
in
taken
end
fun size H =
let
val (array, _, _) = !H
in
length array
end
end
|
