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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 496 - (view) (download)

1 : monnier 496 (* hash-table-fn.sml
2 :     *
3 :     * COPYRIGHT (c) 1999 Bell Labs, Lucent Technologies.
4 :     *
5 :     * A specialization of the hash table functor to integer keys.
6 :     *
7 :     * AUTHOR: John Reppy
8 :     * Bell Labs
9 :     * Murray Hill, NJ 07974
10 :     * jhr@research.bell-labs.com
11 :     *)
12 :    
13 :     structure IntHashTable :> MONO_HASH_TABLE where type Key.hash_key = int =
14 :     struct
15 :    
16 :     structure Key =
17 :     struct
18 :     type hash_key = int
19 :     fun sameKey (a : int, b) = (a = b)
20 :     fun hashVal a = Word.fromInt 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 :     (* find an item, the table's exception is raised if the item doesn't exist *)
74 :     fun lookup (HT{table, not_found, ...}) key = let
75 :     val arr = !table
76 :     val hash = hashVal key
77 :     val indx = index (hash, Array.length arr)
78 :     fun look HTRep.NIL = raise not_found
79 :     | look (HTRep.B(h, k, v, r)) = if ((hash = h) andalso sameKey(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{table, ...}) key = let
88 :     val arr = !table
89 :     val sz = Array.length arr
90 :     val hash = hashVal 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 sameKey(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{not_found, table, n_items}) key = let
104 :     val arr = !table
105 :     val sz = Array.length arr
106 :     val hash = hashVal 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 sameKey(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{table, n_items, not_found}) = HT{
134 :     table = ref(HTRep.mapi f (! table)),
135 :     n_items = ref(!n_items),
136 :     not_found = not_found
137 :     }
138 :     fun map f (HT{table, n_items, not_found}) = HT{
139 :     table = ref(HTRep.map f (! table)),
140 :     n_items = ref(!n_items),
141 :     not_found = not_found
142 :     }
143 :    
144 :     (* Fold a function over the entries of the table *)
145 :     fun foldi f init (HT{table, ...}) = HTRep.foldi f init (! table)
146 :     fun fold f init (HT{table, ...}) = HTRep.fold f init (! table)
147 :    
148 :     (* remove any hash table items that do not satisfy the given
149 :     * predicate.
150 :     *)
151 :     fun filteri pred (HT{table, ...}) = HTRep.filteri pred (! table)
152 :     fun filter pred (HT{table, ...}) = HTRep.filter pred (! table)
153 :    
154 :     (* Create a copy of a hash table *)
155 :     fun copy (HT{table, n_items, not_found}) = HT{
156 :     table = ref(HTRep.copy(! table)),
157 :     n_items = ref(!n_items),
158 :     not_found = not_found
159 :     }
160 :    
161 :     (* returns a list of the sizes of the various buckets. This is to
162 :     * allow users to gauge the quality of their hashing function.
163 :     *)
164 :     fun bucketSizes (HT{table, ...}) = HTRep.bucketSizes (! table)
165 :    
166 :     end (* HashTableFn *)

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