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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 596 - (view) (download)

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

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