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/intmap.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/library/intmap.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 651 - (view) (download)

1 : monnier 496 (* Copyright 1989 by AT&T Bell Laboratories *)
2 :     structure Intmap : INTMAP =
3 :     struct
4 :     open Array List
5 :     infix 9 sub
6 :     val wtoi = Word.toIntX
7 :     val itow = Word.fromInt
8 :     datatype 'a bucket = NIL | B of (int * 'a * 'a bucket)
9 :     datatype 'a intmap =
10 :     H of {table: 'a bucket array ref,elems: int ref,exn: exn,name: string option}
11 :     fun clear(H{table,elems,...}) =
12 :     if !elems > 0 then (table := array(32,NIL); elems := 0) else ()
13 :     fun bucketapp f =
14 :     let fun loop NIL = ()
15 :     | loop(B(i,j,r)) = (f(i,j); loop r)
16 :     in loop
17 :     end
18 :     fun roundsize size =
19 :     let fun f x = if x >= size then x else f (x*2)
20 :     in f 1
21 :     end
22 :     fun namednew(name, size, exn) =
23 :     H {table=ref(array(roundsize size,NIL)),elems=ref 0,exn=exn,name=SOME name}
24 :     fun new(size, exn) =
25 :     H {table=ref(array(roundsize size,NIL)),elems=ref 0,exn=exn,name=NONE}
26 :     val elems = fn (H{elems,...}) => !elems
27 :     fun index(a, i) = wtoi (Word.andb(itow i, itow(Array.length a - 1)))
28 :     fun map (H{table,exn,...}) =
29 :     (fn i => let fun find NIL = raise exn
30 :     | find(B(i',j,r)) = if i=i' then j else find r
31 :     val ref a = table
32 :     in find(a sub (index(a, i)))
33 :     end)
34 :     fun mapWithDefault (H{table,exn,...},default) =
35 :     (fn i => let fun find NIL = default
36 :     | find(B(i',j,r)) = if i=i' then j else find r
37 :     val ref a = table
38 :     in find(a sub (index(a, i)))
39 :     end)
40 :     fun mapInt (H{table,exn,...}) =
41 :     (fn i => let fun find NIL = i
42 :     | find(B(i',j,r)) = if i=i' then j else find r
43 :     val ref a = table
44 :     in find(a sub (index(a, i)))
45 :     end)
46 :     fun rmv (H{table=ref a,elems,...}) i =
47 :     let fun f(B(i',j,r)) = if i=i' then (elems := !elems-1; r) else B(i',j,f r)
48 :     | f x = x
49 :     val indx = index(a, i)
50 :     in update(a, indx, f(a sub indx))
51 :     end
52 :     fun app f (H{table=ref a,...}) =
53 :     let fun zap 0 = ()
54 :     | zap n = let val m = n-1 in bucketapp f (a sub m); zap m end
55 :     in zap(Array.length a)
56 :     end
57 :     fun add (m as H{table as ref a, elems, name, ...}) (v as (i,j)) =
58 :     let val size = Array.length a
59 :     in if !elems <> size
60 :     then let val index = wtoi (Word.andb(itow i, itow(size-1)))
61 :     fun f(B(i',j',r)) = if i=i' then B(i,j,r) else B(i',j',f r)
62 :     | f x = (elems := !elems+1; B(i,j,x))
63 :     in update(a,index,f(a sub index))
64 :     end
65 :     else let val newsize = size+size
66 :     val newsize1 = newsize-1
67 :     val new = array(newsize,NIL)
68 :     fun bucket n =
69 :     let fun add'(a,b,B(i,j,r)) =
70 :     if wtoi (Word.andb(itow i, itow newsize1)) = n
71 :     then add'(B(i,j,a),b,r)
72 :     else add'(a,B(i,j,b),r)
73 :     | add'(a,b,NIL) =
74 :     (update(new,n,a);
75 :     update(new,n+size,b);
76 :     bucket(n+1))
77 :     in add'(NIL,NIL,a sub n)
78 :     end
79 :     in
80 :     bucket 0 handle Subscript => ();
81 :     table := new;
82 :     add m v
83 :     end
84 :     end
85 :     fun intMapToList(H{table,...})=
86 :     let val a = !table;
87 :     val last = Array.length a - 1
88 :     fun loop (0, NIL, acc) = acc
89 :     | loop (n, B(i,j,r), acc) = loop(n, r, (i,j)::acc)
90 :     | loop (n, NIL, acc) = loop(n-1, a sub (n-1), acc)
91 :     in loop(last,a sub last,[])
92 :     end
93 :     fun values(H{table,...})=
94 :     let val a = !table;
95 :     val last = Array.length a - 1
96 :     fun loop (0, NIL, acc) = acc
97 :     | loop (n, B(i,j,r), acc) = loop(n, r, j::acc)
98 :     | loop (n, NIL, acc) = loop(n-1, a sub (n-1), acc)
99 :     in loop(last,a sub last,[])
100 :     end
101 :     fun keys(H{table,...})=
102 :     let val a = !table;
103 :     val last = Array.length a - 1
104 :     fun loop (0, NIL, acc) = acc
105 :     | loop (n, B(i,j,r), acc) = loop(n, r, i::acc)
106 :     | loop (n, NIL, acc) = loop(n-1, a sub (n-1), acc)
107 :     in loop(last,a sub last,[])
108 :     end
109 :    
110 :     fun copy(H{table=ref a,elems,exn,name}) =
111 :     let val a' = Array.array(Array.length a,NIL)
112 :     in Array.copy{di=0, dst=a', len=NONE, si=0, src=a};
113 :     H{table=ref a', elems=ref(!elems), exn=exn, name=name}
114 :     end
115 :    
116 :     end
117 :    

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