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/word-hash-table.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 816 - (view) (download)

1 : jhr 702 (* word-hash-table.sml
2 :     *
3 :     * COPYRIGHT (c) 2000 Bell Labs, Lucent Technologies.
4 :     *
5 :     * A specialization of the hash table functor to word keys.
6 :     *
7 :     * AUTHOR: John Reppy
8 :     * Bell Labs
9 :     * Murray Hill, NJ 07974
10 :     * jhr@research.bell-labs.com
11 :     *)
12 :    
13 :     structure WordHashTable :> MONO_HASH_TABLE where type Key.hash_key = word =
14 :     struct
15 :    
16 :     structure Key =
17 :     struct
18 :     type hash_key = word
19 :     fun sameKey (a : word, b) = (a = b)
20 :     fun hashVal a = a
21 :     end
22 :    
23 :     open Key
24 :    
25 :     structure HTRep = HashTableRep
26 :    
27 :     datatype 'a hash_table = HT of {
28 :     not_found : exn,
29 :     table : (hash_key, 'a) HTRep.table ref,
30 :     n_items : int ref
31 :     }
32 :    
33 :     fun index (i, sz) = Word.toIntX(Word.andb(i, Word.fromInt sz - 0w1))
34 :    
35 :     (* Create a new table; the int is a size hint and the exception
36 :     * is to be raised by find.
37 :     *)
38 :     fun mkTable (sizeHint, notFound) = HT{
39 :     not_found = notFound,
40 :     table = ref (HTRep.alloc sizeHint),
41 :     n_items = ref 0
42 :     }
43 :    
44 :     (* remove all elements from the table *)
45 :     fun clear (HT{table, n_items, ...}) = (HTRep.clear(!table); n_items := 0)
46 :    
47 :     (* Insert an item. If the key already has an item associated with it,
48 :     * then the old item is discarded.
49 :     *)
50 :     fun insert (tbl as HT{table, n_items, ...}) (key, item) = let
51 :     val arr = !table
52 :     val sz = Array.length arr
53 :     val hash = hashVal key
54 :     val indx = index (hash, sz)
55 :     fun look HTRep.NIL = (
56 :     Array.update(arr, indx, HTRep.B(hash, key, item, Array.sub(arr, indx)));
57 :     n_items := !n_items + 1;
58 :     HTRep.growTableIfNeeded (table, !n_items);
59 :     HTRep.NIL)
60 :     | look (HTRep.B(h, k, v, r)) = if ((hash = h) andalso sameKey(key, k))
61 :     then HTRep.B(hash, key, item, r)
62 :     else (case (look r)
63 :     of HTRep.NIL => HTRep.NIL
64 :     | rest => HTRep.B(h, k, v, rest)
65 :     (* end case *))
66 :     in
67 :     case (look (Array.sub (arr, indx)))
68 :     of HTRep.NIL => ()
69 :     | b => Array.update(arr, indx, b)
70 :     (* end case *)
71 :     end
72 :    
73 : jhr 816 (* return true, if the key is in the domain of the table *)
74 :     fun inDomain (HT{table, ...}) key = let
75 :     val arr = !table
76 :     val hash = hashVal key
77 :     val indx = index (hash, Array.length arr)
78 :     fun look HTRep.NIL = false
79 :     | look (HTRep.B(h, k, v, r)) =
80 :     ((hash = h) andalso sameKey(key, k)) orelse look r
81 :     in
82 :     look (Array.sub (arr, indx))
83 :     end
84 :    
85 : jhr 702 (* find an item, the table's exception is raised if the item doesn't exist *)
86 :     fun lookup (HT{table, not_found, ...}) key = let
87 :     val arr = !table
88 :     val hash = hashVal key
89 :     val indx = index (hash, Array.length arr)
90 :     fun look HTRep.NIL = raise not_found
91 :     | look (HTRep.B(h, k, v, r)) = if ((hash = h) andalso sameKey(key, k))
92 :     then v
93 :     else look r
94 :     in
95 :     look (Array.sub (arr, indx))
96 :     end
97 :    
98 :     (* look for an item, return NONE if the item doesn't exist *)
99 :     fun find (HT{table, ...}) key = let
100 :     val arr = !table
101 :     val sz = Array.length arr
102 :     val hash = hashVal key
103 :     val indx = index (hash, sz)
104 :     fun look HTRep.NIL = NONE
105 :     | look (HTRep.B(h, k, v, r)) = if ((hash = h) andalso sameKey(key, k))
106 :     then SOME v
107 :     else look r
108 :     in
109 :     look (Array.sub (arr, indx))
110 :     end
111 :    
112 :     (* Remove an item. The table's exception is raised if
113 :     * the item doesn't exist.
114 :     *)
115 :     fun remove (HT{not_found, table, n_items}) key = let
116 :     val arr = !table
117 :     val sz = Array.length arr
118 :     val hash = hashVal key
119 :     val indx = index (hash, sz)
120 :     fun look HTRep.NIL = raise not_found
121 :     | look (HTRep.B(h, k, v, r)) = if ((hash = h) andalso sameKey(key, k))
122 :     then (v, r)
123 :     else let val (item, r') = look r in (item, HTRep.B(h, k, v, r')) end
124 :     val (item, bucket) = look (Array.sub (arr, indx))
125 :     in
126 :     Array.update (arr, indx, bucket);
127 :     n_items := !n_items - 1;
128 :     item
129 :     end (* remove *)
130 :    
131 :     (* Return the number of items in the table *)
132 :     fun numItems (HT{n_items, ...}) = !n_items
133 :    
134 :     (* return a list of the items in the table *)
135 :     fun listItems (HT{table = ref arr, n_items, ...}) =
136 :     HTRep.listItems (arr, n_items)
137 :     fun listItemsi (HT{table = ref arr, n_items, ...}) =
138 :     HTRep.listItemsi (arr, n_items)
139 :    
140 :     (* Apply a function to the entries of the table *)
141 :     fun appi f (HT{table, ...}) = HTRep.appi f (! table)
142 :     fun app f (HT{table, ...}) = HTRep.app f (! table)
143 :    
144 :     (* Map a table to a new table that has the same keys and exception *)
145 :     fun mapi f (HT{table, n_items, not_found}) = HT{
146 :     table = ref(HTRep.mapi f (! table)),
147 :     n_items = ref(!n_items),
148 :     not_found = not_found
149 :     }
150 :     fun map f (HT{table, n_items, not_found}) = HT{
151 :     table = ref(HTRep.map f (! table)),
152 :     n_items = ref(!n_items),
153 :     not_found = not_found
154 :     }
155 :    
156 :     (* Fold a function over the entries of the table *)
157 :     fun foldi f init (HT{table, ...}) = HTRep.foldi f init (! table)
158 :     fun fold f init (HT{table, ...}) = HTRep.fold f init (! table)
159 :    
160 :     (* modify the hash-table items in place *)
161 :     fun modifyi f (HT{table, ...}) = HTRep.modifyi f (!table)
162 :     fun modify f (HT{table, ...}) = HTRep.modify f (!table)
163 :    
164 :     (* remove any hash table items that do not satisfy the given
165 :     * predicate.
166 :     *)
167 :     fun filteri pred (HT{table, n_items, ...}) =
168 :     n_items := HTRep.filteri pred (! table)
169 :     fun filter pred (HT{table, n_items, ...}) =
170 :     n_items := HTRep.filter pred (! table)
171 :    
172 :     (* Create a copy of a hash table *)
173 :     fun copy (HT{table, n_items, not_found}) = HT{
174 :     table = ref(HTRep.copy(! table)),
175 :     n_items = ref(!n_items),
176 :     not_found = not_found
177 :     }
178 :    
179 :     (* returns a list of the sizes of the various buckets. This is to
180 :     * allow users to gauge the quality of their hashing function.
181 :     *)
182 :     fun bucketSizes (HT{table, ...}) = HTRep.bucketSizes (! table)
183 :    
184 :     end (* HashTableFn *)

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