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/smlnj-lib/Util/hash-table-rep.sml
ViewVC logotype

Annotation of /sml/trunk/src/smlnj-lib/Util/hash-table-rep.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 596 - (view) (download)

1 : monnier 2 (* hash-table-rep.sml
2 :     *
3 :     * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.
4 :     * COPYRIGHT (c) 1996 AT&T Research.
5 :     *
6 :     * This is the internal representation of hash tables, along with some
7 :     * utility functions. It is used in both the polymorphic and functor
8 :     * hash table implementations.
9 :     *
10 :     * AUTHOR: John Reppy
11 :     * AT&T Bell Laboratories
12 :     * Murray Hill, NJ 07974
13 :     * jhr@research.att.com
14 :     *)
15 :    
16 :     structure HashTableRep : sig
17 :    
18 :     datatype ('a, 'b) bucket
19 :     = NIL
20 :     | B of (word * 'a * 'b * ('a, 'b) bucket)
21 :    
22 :     type ('a, 'b) table = ('a, 'b) bucket array
23 :    
24 :     val alloc : int -> ('a, 'b) table
25 :     (* allocate a table of at least the given size *)
26 :    
27 :     val growTable : (('a, 'b) table * int) -> ('a, 'b) table
28 :     (* grow a table to the specified size *)
29 :    
30 :     val growTableIfNeeded : (('a, 'b) table ref * int) -> bool
31 :     (* conditionally grow a table; the second argument is the number
32 :     * of items currently in the table.
33 :     *)
34 :    
35 : monnier 8 val clear : ('a, 'b) table -> unit
36 :     (* remove all items *)
37 :    
38 : monnier 2 val listItems : (('a, 'b) table * int ref) -> 'b list
39 :     val listItemsi : (('a, 'b) table * int ref) -> ('a * 'b) list
40 :    
41 :    
42 :     val appi : ('a * 'b -> 'c) -> ('a, 'b) table -> unit
43 :     val app : ('a -> 'b) -> ('c, 'a) table -> unit
44 :    
45 :     val mapi : ('a * 'b -> 'c) -> ('a, 'b) table -> ('a, 'c) table
46 :     val map : ('a -> 'b) -> ('c, 'a) table -> ('c, 'b) table
47 :    
48 :     val foldi : ('a * 'b * 'c -> 'c) -> 'c -> ('a, 'b) table -> 'c
49 :     val fold : ('a * 'b -> 'b) -> 'b -> ('c, 'a) table -> 'b
50 :    
51 : jhr 596 val modify : ('b -> 'b) -> ('a, 'b) table -> unit
52 :     val modifyi : (('a * 'b) -> 'b) -> ('a, 'b) table -> unit
53 : monnier 2
54 : jhr 596 val filteri : ('a * 'b -> bool) -> ('a, 'b) table -> int
55 :     val filter : ('a -> bool) -> ('b,'a) table -> int
56 :    
57 : monnier 2 val copy : ('a, 'b) table -> ('a, 'b) table
58 :    
59 :     val bucketSizes : ('a, 'b) table -> int list
60 :    
61 :     end = struct
62 :    
63 :     datatype ('a, 'b) bucket
64 :     = NIL
65 :     | B of (word * 'a * 'b * ('a, 'b) bucket)
66 :    
67 :     type ('a, 'b) table = ('a, 'b) bucket array
68 :    
69 :     fun index (i, sz) = Word.toIntX(Word.andb(i, Word.fromInt sz - 0w1))
70 :    
71 :     (* find smallest power of 2 (>= 32) that is >= n *)
72 :     fun roundUp n = let
73 :     fun f i = if (i >= n) then i else f(i * 2)
74 :     in
75 :     f 32
76 :     end
77 :    
78 :     (* Create a new table; the int is a size hint and the exception
79 :     * is to be raised by find.
80 :     *)
81 :     fun alloc sizeHint = Array.array(roundUp sizeHint, NIL)
82 :    
83 :     (* grow a table to the specified size *)
84 :     fun growTable (table, newSz) = let
85 :     val newArr = Array.array (newSz, NIL)
86 :     fun copy NIL = ()
87 :     | copy (B(h, key, v, rest)) = let
88 :     val indx = index (h, newSz)
89 :     in
90 :     Array.update (newArr, indx,
91 :     B(h, key, v, Array.sub(newArr, indx)));
92 :     copy rest
93 :     end
94 :     in
95 :     Array.app copy table;
96 :     newArr
97 :     end
98 :    
99 :     (* conditionally grow a table; return true if it grew. *)
100 :     fun growTableIfNeeded (table, nItems) = let
101 :     val arr = !table
102 :     val sz = Array.length arr
103 :     in
104 :     if (nItems >= sz)
105 :     then (table := growTable (arr, sz+sz); true)
106 :     else false
107 :     end
108 :    
109 : monnier 8 (* remove all items *)
110 :     fun clear table = Array.modify (fn _ => NIL) table
111 :    
112 : monnier 2 (* return a list of the items in the table *)
113 :     fun listItems (table, nItems) = let
114 :     fun f (_, l, 0) = l
115 :     | f (~1, l, _) = l
116 :     | f (i, l, n) = let
117 :     fun g (NIL, l, n) = f (i-1, l, n)
118 :     | g (B(_, k, v, r), l, n) = g(r, v::l, n-1)
119 :     in
120 :     g (Array.sub(table, i), l, n)
121 :     end
122 :     in
123 :     f ((Array.length table) - 1, [], !nItems)
124 :     end (* listItems *)
125 :     fun listItemsi (table, nItems) = let
126 :     fun f (_, l, 0) = l
127 :     | f (~1, l, _) = l
128 :     | f (i, l, n) = let
129 :     fun g (NIL, l, n) = f (i-1, l, n)
130 :     | g (B(_, k, v, r), l, n) = g(r, (k, v)::l, n-1)
131 :     in
132 :     g (Array.sub(table, i), l, n)
133 :     end
134 :     in
135 :     f ((Array.length table) - 1, [], !nItems)
136 :     end (* listItems *)
137 :    
138 :     (* Apply a function to the entries of the table *)
139 :     fun appi f table = let
140 :     fun appF NIL = ()
141 :     | appF (B(_, key, item, rest)) = (f (key, item); appF rest)
142 :     in
143 :     Array.app appF table
144 :     end (* appi *)
145 :     fun app f table = let
146 :     fun appF NIL = ()
147 :     | appF (B(_, key, item, rest)) = (f item; appF rest)
148 :     in
149 :     Array.app appF table
150 :     end (* app *)
151 :    
152 :     (* Map a table to a new table that has the same keys *)
153 :     fun mapi f table = let
154 :     fun mapF NIL = NIL
155 :     | mapF (B(hash, key, item, rest)) =
156 :     B(hash, key, f (key, item), mapF rest)
157 :     val newTbl = Array.tabulate (
158 :     Array.length table,
159 :     fn i => mapF (Array.sub(table, i)))
160 :     in
161 :     newTbl
162 :     end (* transform *)
163 :    
164 :     (* Map a table to a new table that has the same keys *)
165 :     fun map f table = let
166 :     fun mapF NIL = NIL
167 :     | mapF (B(hash, key, item, rest)) = B(hash, key, f item, mapF rest)
168 :     val newTbl = Array.tabulate (
169 :     Array.length table,
170 :     fn i => mapF (Array.sub(table, i)))
171 :     in
172 :     newTbl
173 :     end (* map *)
174 :    
175 :     fun foldi f init table = let
176 :     fun foldF (NIL, accum) = accum
177 :     | foldF (B(hash, key, item, rest), accum) =
178 :     foldF(rest, f(key, item, accum))
179 :     in
180 :     Array.foldl foldF init table
181 :     end
182 :     fun fold f init table = let
183 :     fun foldF (NIL, accum) = accum
184 :     | foldF (B(hash, key, item, rest), accum) =
185 :     foldF(rest, f(item, accum))
186 :     in
187 :     Array.foldl foldF init table
188 :     end
189 :    
190 : jhr 596 (* modify the hash-table items in place *)
191 :     fun modify f table = let
192 :     fun modifyF NIL = NIL
193 :     | modifyF (B(hash, key, item, rest)) = B(hash, key, f item, modifyF rest)
194 :     in
195 :     Array.modify modifyF table
196 :     end
197 :     fun modifyi f table = let
198 :     fun modifyF NIL = NIL
199 :     | modifyF (B(hash, key, item, rest)) =
200 :     B(hash, key, f(key, item), modifyF rest)
201 :     in
202 :     Array.modify modifyF table
203 :     end
204 :    
205 : monnier 2 (* remove any hash table items that do not satisfy the given
206 : jhr 596 * predicate. Return the number of items left in the table.
207 : monnier 2 *)
208 :     fun filteri pred table = let
209 : jhr 596 val nItems = ref 0
210 : monnier 2 fun filterP NIL = NIL
211 :     | filterP (B(hash, key, item, rest)) = if (pred(key, item))
212 : jhr 596 then (
213 :     nItems := !nItems+1;
214 :     B(hash, key, item, filterP rest))
215 : monnier 2 else filterP rest
216 :     in
217 : jhr 596 Array.modify filterP table;
218 :     !nItems
219 : monnier 2 end (* filteri *)
220 :     fun filter pred table = let
221 : jhr 596 val nItems = ref 0
222 : monnier 2 fun filterP NIL = NIL
223 :     | filterP (B(hash, key, item, rest)) = if (pred item)
224 : jhr 596 then (
225 :     nItems := !nItems+1;
226 :     B(hash, key, item, filterP rest))
227 : monnier 2 else filterP rest
228 :     in
229 : jhr 596 Array.modify filterP table;
230 :     !nItems
231 : monnier 2 end (* filter *)
232 :    
233 :     (* Create a copy of a hash table *)
234 :     fun copy table =
235 :     Array.tabulate (Array.length table, fn i => Array.sub(table, i));
236 :    
237 :     (* returns a list of the sizes of the various buckets. This is to
238 :     * allow users to gauge the quality of their hashing function.
239 :     *)
240 :     fun bucketSizes table = let
241 :     fun len (NIL, n) = n
242 :     | len (B(_, _, _, r), n) = len(r, n+1)
243 :     in
244 :     Array.foldr (fn (b, l) => len(b, 0) :: l) [] table
245 :     end
246 :    
247 :     end (* HashTableRep *)

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