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

# SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/library/hash-array.sml
 [smlnj] / sml / trunk / src / MLRISC / library / hash-array.sml

# Diff of /sml/trunk/src/MLRISC/library/hash-array.sml

revision 411, Fri Sep 3 00:25:03 1999 UTC revision 429, Wed Sep 8 09:47:00 1999 UTC
# Line 28  Line 28
28
29      fun unimplemented _ = raise HashArrayUnimplemented      fun unimplemented _ = raise HashArrayUnimplemented
30
31      fun array(n,d) = ARRAY(ref(A.array(13,[])),V d,ref n,ref 0)      fun array(n,d) = ARRAY(ref(A.array(16,[])),V d,ref n,ref 0)
32      fun array'(n,f) = ARRAY(ref(A.array(13,[])),F f,ref n,ref 0)      fun array'(n,f) = ARRAY(ref(A.array(16,[])),F f,ref n,ref 0)
33      fun array''(n,f) = ARRAY(ref(A.array(13,[])),U f,ref n,ref 0)      fun array''(n,f) = ARRAY(ref(A.array(16,[])),U f,ref n,ref 0)
34      fun clear(ARRAY(r,d,n,c)) = (r := A.array(13,[]); n := 0; c := 0)      fun clear(ARRAY(r,d,n,c)) = (r := A.array(16,[]); n := 0; c := 0)
35
36        fun roundsize n =
37        let fun loop i = if i >= n then i else loop(i+i)
38        in  loop 1 end
39
40      fun copy_array(ARRAY(ref a,d,ref n,ref c)) =      fun copy_array(ARRAY(ref a,d,ref n,ref c)) =
41           let val a' = A.array(n,[])           let val a' = A.array(n,[])
42               val _  = A.copy{src=a,dst=a',si=0,di=0,len=NONE}               val _  = A.copy{src=a,dst=a',si=0,di=0,len=NONE}
43           in  ARRAY(ref a',d,ref n,ref c)           in  ARRAY(ref a',d,ref n,ref c)
44           end           end
45
46        val itow = Word.fromInt
47        val wtoi = Word.toIntX
48        fun index(a, i) = wtoi(Word.andb(itow i, itow(Array.length a - 1)))
49
50      fun tabulate(n,f) =      fun tabulate(n,f) =
51      let val N = n*n+1      let val N = n*n+1
52          val N = if N < 13 then 13 else N          val N = if N < 16 then 16 else roundsize N
53          val a = A.array(N,[])          val a = A.array(N,[])
54          fun ins i =          fun ins i =
55              let val pos = i mod N              let val pos = index(a, i)
56                  val x   = f i                  val x   = f i
57              in  A.update(a,pos,(i,x)::A.sub(a,pos)); x              in  A.update(a,pos,(i,x)::A.sub(a,pos)); x
58              end              end
# Line 58  Line 67
67      fun fromList l =      fun fromList l =
68      let val n = length l      let val n = length l
69          val N = n*n+1          val N = n*n+1
70          val N = if N < 13 then 13 else N          val N = if N < 16 then 16 else roundsize N
71          val a = A.array(N,[])          val a = A.array(N,[])
72          fun ins(i,x) =          fun ins(i,x) =
73              let val pos = i mod N              let val pos = index(a,i)
74              in  A.update(a,pos,(i,x)::A.sub(a,pos)); x              in  A.update(a,pos,(i,x)::A.sub(a,pos)); x
75              end              end
76          fun insert(i,[])   = F(fn _ => raise Subscript)          fun insert(i,[])   = F(fn _ => raise Subscript)
# Line 73  Line 82
82      fun length(ARRAY(_,_,ref n,_)) = n      fun length(ARRAY(_,_,ref n,_)) = n
83
84      fun sub(a' as ARRAY(ref a,d,_,_),i) =      fun sub(a' as ARRAY(ref a,d,_,_),i) =
85      let val pos = i mod A.length a      let val pos = index(a,i)
86          fun search [] = (case d of          fun search [] = (case d of
87                             V d => d                             V d => d
88                           | F f => f i                           | F f => f i
# Line 85  Line 94
94
95      and update(a' as ARRAY(ref a,_,n,s as ref size),i,x) =      and update(a' as ARRAY(ref a,_,n,s as ref size),i,x) =
96      let val N   = A.length a      let val N   = A.length a
97          val pos = i mod N          val pos = index(a,i)
98          fun change([],l) =          fun change([],l) =
99                if size+size >= N then grow(a',i,x)                if size+size >= N then grow(a',i,x)
100                else (s := size + 1; A.update(a,pos,(i,x)::l))                else (s := size + 1; A.update(a,pos,(i,x)::l))
# Line 99  Line 108
108
109      and grow(ARRAY(a' as ref a,_,_,_),i,x) =      and grow(ARRAY(a' as ref a,_,_,_),i,x) =
110      let val N   = A.length a      let val N   = A.length a
111          val N'  = N+N+1          val N'  = N+N
112          val a'' = A.array(N',[])          val a'' = A.array(N',[])
113          fun insert(i,x) =          fun insert(i,x) =
114              let val pos = i mod N'              let val pos = index(a'',i)
115              in  A.update(a'',pos,(i,x)::A.sub(a'',pos)) end              in  A.update(a'',pos,(i,x)::A.sub(a'',pos)) end
116      in      in
117          A.app (List.app insert) a;          A.app (List.app insert) a;
# Line 112  Line 121
121
122      fun remove(a' as ARRAY(ref a,_,n,s as ref size),i) =      fun remove(a' as ARRAY(ref a,_,n,s as ref size),i) =
123      let val N   = A.length a      let val N   = A.length a
124          val pos = i mod N          val pos = index(a,i)
125          fun change([],_) = ()          fun change([],_) = ()
126            | change((y as (j,_))::l',l) =            | change((y as (j,_))::l',l) =
127                if j = i then (s := size - 1; A.update(a,pos,l'@l))                if j = i then (s := size - 1; A.update(a,pos,l'@l))

Legend:
 Removed from v.411 changed lines Added in v.429