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

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