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 245 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/library/hash-table.sml

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

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