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.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8 - (view) (download)
Original Path: sml/branches/SMLNJ/src/smlnj-lib/Util/hash-table.sml

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

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