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 2 - (view) (download)

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 :     (* Insert an item. If the key already has an item associated with it,
47 :     * then the old item is discarded.
48 :     *)
49 :     fun insert (tbl as HT{hash_fn, eq_pred, table, n_items, ...}) (key, item) = let
50 :     val arr = !table
51 :     val sz = Array.length arr
52 :     val hash = hash_fn key
53 :     val indx = index (hash, sz)
54 :     fun look HTRep.NIL = (
55 :     Array.update(arr, indx,
56 :     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 eq_pred(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
71 :    
72 :     (* find an item, the table's exception is raised if the item doesn't exist *)
73 :     fun lookup (HT{hash_fn, eq_pred, table, not_found, ...}) key = let
74 :     val arr = !table
75 :     val sz = Array.length arr
76 :     val hash = hash_fn key
77 :     val indx = index (hash, sz)
78 :     fun look HTRep.NIL = raise not_found
79 :     | look (HTRep.B(h, k, v, r)) = if ((hash = h) andalso eq_pred(key, k))
80 :     then v
81 :     else look r
82 :     in
83 :     look (Array.sub (arr, indx))
84 :     end
85 :    
86 :     (* look for an item, return NONE if the item doesn't exist *)
87 :     fun find (HT{hash_fn, eq_pred, table, ...}) key = let
88 :     val arr = !table
89 :     val sz = Array.length arr
90 :     val hash = hash_fn key
91 :     val indx = index (hash, sz)
92 :     fun look HTRep.NIL = NONE
93 :     | look (HTRep.B(h, k, v, r)) = if ((hash = h) andalso eq_pred(key, k))
94 :     then SOME v
95 :     else look r
96 :     in
97 :     look (Array.sub (arr, indx))
98 :     end
99 :    
100 :     (* Remove an item. The table's exception is raised if
101 :     * the item doesn't exist.
102 :     *)
103 :     fun remove (HT{hash_fn, eq_pred, not_found, table, n_items}) key = let
104 :     val arr = !table
105 :     val sz = Array.length arr
106 :     val hash = hash_fn key
107 :     val indx = index (hash, sz)
108 :     fun look HTRep.NIL = raise not_found
109 :     | look (HTRep.B(h, k, v, r)) = if ((hash = h) andalso eq_pred(key, k))
110 :     then (v, r)
111 :     else let val (item, r') = look r in (item, HTRep.B(h, k, v, r')) end
112 :     val (item, bucket) = look (Array.sub (arr, indx))
113 :     in
114 :     Array.update (arr, indx, bucket);
115 :     n_items := !n_items - 1;
116 :     item
117 :     end (* remove *)
118 :    
119 :     (* Return the number of items in the table *)
120 :     fun numItems (HT{n_items, ...}) = !n_items
121 :    
122 :     (* return a list of the items in the table *)
123 :     fun listItems (HT{table = ref arr, n_items, ...}) =
124 :     HTRep.listItems (arr, n_items)
125 :     fun listItemsi (HT{table = ref arr, n_items, ...}) =
126 :     HTRep.listItemsi (arr, n_items)
127 :    
128 :     (* Apply a function to the entries of the table *)
129 :     fun appi f (HT{table, ...}) = HTRep.appi f (! table)
130 :     fun app f (HT{table, ...}) = HTRep.app f (! table)
131 :    
132 :     (* Map a table to a new table that has the same keys and exception *)
133 :     fun mapi f (HT{hash_fn, eq_pred, table, n_items, not_found}) = HT{
134 :     hash_fn = hash_fn, eq_pred = eq_pred,
135 :     table = ref(HTRep.mapi f (! table)),
136 :     n_items = ref(!n_items),
137 :     not_found = not_found
138 :     }
139 :    
140 :     (* Map a table to a new table that has the same keys and exception *)
141 :     fun map f (HT{hash_fn, eq_pred, table, n_items, not_found}) = HT{
142 :     hash_fn = hash_fn, eq_pred = eq_pred,
143 :     table = ref(HTRep.map f (! table)),
144 :     n_items = ref(!n_items),
145 :     not_found = not_found
146 :     }
147 :    
148 :     (* Fold a function over the entries of the table *)
149 :     fun foldi f init (HT{table, ...}) = HTRep.foldi f init (! table)
150 :     fun fold f init (HT{table, ...}) = HTRep.fold f init (! table)
151 :    
152 :     (* remove any hash table items that do not satisfy the given
153 :     * predicate.
154 :     *)
155 :     fun filteri pred (HT{table, ...}) = HTRep.filteri pred (! table)
156 :     fun filter pred (HT{table, ...}) = HTRep.filter pred (! table)
157 :    
158 :     (* Create a copy of a hash table *)
159 :     fun copy (HT{hash_fn, eq_pred, table, n_items, not_found}) =HT{
160 :     hash_fn = hash_fn, eq_pred = eq_pred,
161 :     table = ref(HTRep.copy (! table)), n_items = ref(!n_items),
162 :     not_found = not_found
163 :     }
164 :    
165 :     (* returns a list of the sizes of the various buckets. This is to
166 :     * allow users to gauge the quality of their hashing function.
167 :     *)
168 :     fun bucketSizes (HT{table, ...}) = HTRep.bucketSizes(! table)
169 :    
170 :     end (* HashTable *)

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