Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/library/hash-table.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/library/hash-table.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 651 - (view) (download)

1 : monnier 411 (*
2 :     * Hash table.
3 :     *
4 :     * -- Allen
5 :     *)
6 :     structure Hashtable :> HASHTABLE =
7 : monnier 245 struct
8 :    
9 :     structure A = Array
10 :    
11 : monnier 411 type ('a,'b) table = ('a -> word) *
12 : monnier 245 ('a * 'a -> bool) *
13 :     exn *
14 :     ('a * 'b) list A.array ref *
15 :     int ref
16 :    
17 :     infix ==
18 :    
19 :     fun create{hash,==,exn,size} = (hash,op==,exn,ref(A.array(size,[])),ref 0)
20 :     fun copy(hash,op==,exn,ref a,ref c) =
21 :     (hash,op==,exn,ref(A.tabulate(A.length a,fn i => A.sub(a,i))), ref c)
22 :     fun size (_,_,_,_,ref n) = n
23 :     fun clear (_,_,_,ref a,c) =
24 :     let fun f ~1 = ()
25 :     | f i = (A.update(a,i,[]); f(i-1))
26 :     in f(A.length a - 1); c := 0 end
27 :     fun insert (hash,op==,exn,A as ref a,c) (k,v) =
28 :     let val N = A.length a
29 : monnier 411 val h = Word.toIntX(hash k) mod N
30 : monnier 245 val es = A.sub(a,h)
31 :     fun ins ([],es') = (A.update(a,h,(k,v)::es');
32 :     c := !c + 1;
33 :     if !c >= N then grow(hash,A,N) else ()
34 :     )
35 :     | ins ((e as (k',_))::es,es') =
36 :     if k == k' then A.update(a,h,(k,v)::es'@es)
37 :     else ins(es,e::es')
38 :     in ins (es,[])
39 :     end
40 :    
41 :     and grow(hash,A as ref a,N) =
42 :     let val M = N + N
43 :     val M = if M < 13 then 13 else M
44 :     val a' = A.array(M,[])
45 : monnier 411 fun ins (k,v) = let val h = Word.toIntX(hash k) mod M
46 : monnier 245 in A.update(a',h,(k,v)::A.sub(a',h)) end
47 :     in A.app (fn es => app ins es) a;
48 :     A := a'
49 :     end
50 :    
51 :     fun remove (hash,op==,exn,ref a,c) k =
52 :     let val N = A.length a
53 : monnier 411 val h = Word.toIntX(hash k) mod N
54 : monnier 245 val es = A.sub(a,h)
55 :     fun del ([],es') = ()
56 :     | del ((e as (k',_))::es,es') =
57 :     if k == k' then (A.update(a,h,es'@es); c := !c - 1)
58 :     else del(es,e::es')
59 :     in del (es,[])
60 :     end
61 :    
62 :     fun lookup(hash,op==,exn,ref a,_) k =
63 :     let val N = A.length a
64 : monnier 411 val h = Word.toIntX(hash k) mod N
65 : monnier 245 fun find [] = raise exn
66 :     | find ((k',v)::es) = if k == k' then v else find es
67 :     in find(A.sub(a,h))
68 :     end
69 :    
70 :     fun app f (_,_,_,ref A,_) = A.app (List.app f) A
71 :    
72 : monnier 411 fun map f (_,_,_,ref A,_) =
73 :     let fun fl([],x) = x
74 :     | fl((k,v)::es,x) = f(k,v)::fl(es,x)
75 :     in A.foldr fl [] A end
76 :    
77 :     fun fold f x (_,_,_,ref A,_) =
78 :     let fun fl([],x) = x
79 :     | fl((k,v)::es,x) = f(k,v,fl(es,x))
80 :     in A.foldr fl x A end
81 :    
82 : monnier 245 end
83 :    

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0