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 9 - (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 :     val filteri : ('a * 'b -> bool) -> ('a, 'b) table -> unit
52 :     val filter : ('a -> bool) -> ('b,'a) table -> unit
53 :    
54 :     val copy : ('a, 'b) table -> ('a, 'b) table
55 :    
56 :     val bucketSizes : ('a, 'b) table -> int list
57 :    
58 :     end = struct
59 :    
60 :     datatype ('a, 'b) bucket
61 :     = NIL
62 :     | B of (word * 'a * 'b * ('a, 'b) bucket)
63 :    
64 :     type ('a, 'b) table = ('a, 'b) bucket array
65 :    
66 :     fun index (i, sz) = Word.toIntX(Word.andb(i, Word.fromInt sz - 0w1))
67 :    
68 :     (* find smallest power of 2 (>= 32) that is >= n *)
69 :     fun roundUp n = let
70 :     fun f i = if (i >= n) then i else f(i * 2)
71 :     in
72 :     f 32
73 :     end
74 :    
75 :     (* Create a new table; the int is a size hint and the exception
76 :     * is to be raised by find.
77 :     *)
78 :     fun alloc sizeHint = Array.array(roundUp sizeHint, NIL)
79 :    
80 :     (* grow a table to the specified size *)
81 :     fun growTable (table, newSz) = let
82 :     val newArr = Array.array (newSz, NIL)
83 :     fun copy NIL = ()
84 :     | copy (B(h, key, v, rest)) = let
85 :     val indx = index (h, newSz)
86 :     in
87 :     Array.update (newArr, indx,
88 :     B(h, key, v, Array.sub(newArr, indx)));
89 :     copy rest
90 :     end
91 :     in
92 :     Array.app copy table;
93 :     newArr
94 :     end
95 :    
96 :     (* conditionally grow a table; return true if it grew. *)
97 :     fun growTableIfNeeded (table, nItems) = let
98 :     val arr = !table
99 :     val sz = Array.length arr
100 :     in
101 :     if (nItems >= sz)
102 :     then (table := growTable (arr, sz+sz); true)
103 :     else false
104 :     end
105 :    
106 : monnier 8 (* remove all items *)
107 :     fun clear table = Array.modify (fn _ => NIL) table
108 :    
109 : monnier 2 (* return a list of the items in the table *)
110 :     fun listItems (table, nItems) = let
111 :     fun f (_, l, 0) = l
112 :     | f (~1, l, _) = l
113 :     | f (i, l, n) = let
114 :     fun g (NIL, l, n) = f (i-1, l, n)
115 :     | g (B(_, k, v, r), l, n) = g(r, v::l, n-1)
116 :     in
117 :     g (Array.sub(table, i), l, n)
118 :     end
119 :     in
120 :     f ((Array.length table) - 1, [], !nItems)
121 :     end (* listItems *)
122 :     fun listItemsi (table, nItems) = let
123 :     fun f (_, l, 0) = l
124 :     | f (~1, l, _) = l
125 :     | f (i, l, n) = let
126 :     fun g (NIL, l, n) = f (i-1, l, n)
127 :     | g (B(_, k, v, r), l, n) = g(r, (k, v)::l, n-1)
128 :     in
129 :     g (Array.sub(table, i), l, n)
130 :     end
131 :     in
132 :     f ((Array.length table) - 1, [], !nItems)
133 :     end (* listItems *)
134 :    
135 :     (* Apply a function to the entries of the table *)
136 :     fun appi f table = let
137 :     fun appF NIL = ()
138 :     | appF (B(_, key, item, rest)) = (f (key, item); appF rest)
139 :     in
140 :     Array.app appF table
141 :     end (* appi *)
142 :     fun app f table = let
143 :     fun appF NIL = ()
144 :     | appF (B(_, key, item, rest)) = (f item; appF rest)
145 :     in
146 :     Array.app appF table
147 :     end (* app *)
148 :    
149 :     (* Map a table to a new table that has the same keys *)
150 :     fun mapi f table = let
151 :     fun mapF NIL = NIL
152 :     | mapF (B(hash, key, item, rest)) =
153 :     B(hash, key, f (key, item), mapF rest)
154 :     val newTbl = Array.tabulate (
155 :     Array.length table,
156 :     fn i => mapF (Array.sub(table, i)))
157 :     in
158 :     newTbl
159 :     end (* transform *)
160 :    
161 :     (* Map a table to a new table that has the same keys *)
162 :     fun map f table = let
163 :     fun mapF NIL = NIL
164 :     | mapF (B(hash, key, item, rest)) = B(hash, key, f item, mapF rest)
165 :     val newTbl = Array.tabulate (
166 :     Array.length table,
167 :     fn i => mapF (Array.sub(table, i)))
168 :     in
169 :     newTbl
170 :     end (* map *)
171 :    
172 :     fun foldi f init table = let
173 :     fun foldF (NIL, accum) = accum
174 :     | foldF (B(hash, key, item, rest), accum) =
175 :     foldF(rest, f(key, item, accum))
176 :     in
177 :     Array.foldl foldF init table
178 :     end
179 :     fun fold f init table = let
180 :     fun foldF (NIL, accum) = accum
181 :     | foldF (B(hash, key, item, rest), accum) =
182 :     foldF(rest, f(item, accum))
183 :     in
184 :     Array.foldl foldF init table
185 :     end
186 :    
187 :     (* remove any hash table items that do not satisfy the given
188 :     * predicate.
189 :     *)
190 :     fun filteri pred table = let
191 :     fun filterP NIL = NIL
192 :     | filterP (B(hash, key, item, rest)) = if (pred(key, item))
193 :     then B(hash, key, item, filterP rest)
194 :     else filterP rest
195 :     in
196 :     Array.modify filterP table
197 :     end (* filteri *)
198 :     fun filter pred table = let
199 :     fun filterP NIL = NIL
200 :     | filterP (B(hash, key, item, rest)) = if (pred item)
201 :     then B(hash, key, item, filterP rest)
202 :     else filterP rest
203 :     in
204 :     Array.modify filterP table
205 :     end (* filter *)
206 :    
207 :     (* Create a copy of a hash table *)
208 :     fun copy table =
209 :     Array.tabulate (Array.length table, fn i => Array.sub(table, i));
210 :    
211 :     (* returns a list of the sizes of the various buckets. This is to
212 :     * allow users to gauge the quality of their hashing function.
213 :     *)
214 :     fun bucketSizes table = let
215 :     fun len (NIL, n) = n
216 :     | len (B(_, _, _, r), n) = len(r, n+1)
217 :     in
218 :     Array.foldr (fn (b, l) => len(b, 0) :: l) [] table
219 :     end
220 :    
221 :     end (* HashTableRep *)

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