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

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