Debian Codegraph @

testsuite/tests/lib-hashtbl/htbl.ml

raw
1 (* TEST *)
2
3 (* Hashtable operations, using maps as a reference *)
4
5 open Printf
6
7 module Test(H: Hashtbl.SeededS) (M: Map.S with type key = H.key) = struct
8
9 let incl_mh m h =
10 try
11 M.iter
12 (fun k d ->
13 let d' = H.find h k in if d <> d' then raise Exit)
14 m;
15 true
16 with Exit | Not_found -> false
17
18 let domain_hm h m =
19 try
20 H.iter
21 (fun k d -> if not (M.mem k m) then raise Exit)
22 h;
23 true
24 with Exit -> false
25
26 let incl_hm h m =
27 try
28 H.iter
29 (fun k d ->
30 let d' = M.find k m in if d <> d' then raise Exit)
31 h;
32 true
33 with Exit | Not_found -> false
34
35 let to_list_ h : _ list =
36 H.fold (fun k v acc -> (k,v) :: acc) h []
37 |> List.sort Stdlib.compare
38
39 let check_to_seq h =
40 let l = to_list_ h in
41 let l2 = List.of_seq (H.to_seq h) in
42 assert (l = List.sort Stdlib.compare l2)
43
44 let check_to_seq_of_seq h =
45 let h' = H.create (H.length h) in
46 H.add_seq h' (H.to_seq h);
47 (*printf "h.len=%d, h'.len=%d\n" (List.length @@ to_list_ h)
48 (List.length @@ to_list_ h');*)
49 assert (to_list_ h = to_list_ h')
50
51 let test data =
52 let n = Array.length data in
53 let h = H.create 51 and m = ref M.empty in
54 (* Insert all data with H.add *)
55 Array.iter
56 (fun (k, d) -> H.add h k d; m := M.add k d !m)
57 data;
58 printf "Insertion: %s\n"
59 (if incl_mh !m h && domain_hm h !m then "passed" else "FAILED");
60 check_to_seq_of_seq h;
61 check_to_seq h;
62 (* Insert all data with H.replace *)
63 H.clear h; m := M.empty;
64 Array.iter
65 (fun (k, d) -> H.replace h k d; m := M.add k d !m)
66 data;
67 printf "Insertion: %s\n"
68 (if incl_mh !m h && incl_hm h !m then "passed" else "FAILED");
69 check_to_seq_of_seq h;
70 check_to_seq h;
71 (* Remove some of the data *)
72 for i = 0 to n/3 - 1 do
73 let (k, _) = data.(i) in H.remove h k; m := M.remove k !m
74 done;
75 printf "Removal: %s\n"
76 (if incl_mh !m h && incl_hm h !m then "passed" else "FAILED");
77 check_to_seq_of_seq h;
78 check_to_seq h;
79 ()
80
81 end
82
83 module SS = struct
84 type t = string
85 let compare (x:t) (y:t) = Stdlib.compare x y
86 let equal (x:t) (y:t) = x=y
87 let seeded_hash = Hashtbl.seeded_hash
88 end
89 module SI = struct
90 type t = int
91 let compare (x:t) (y:t) = Stdlib.compare x y
92 let equal (x:t) (y:t) = x=y
93 let seeded_hash = Hashtbl.seeded_hash
94 end
95 module SSP = struct
96 type t = string*string
97 let compare (x:t) (y:t) = Stdlib.compare x y
98 let equal (x:t) (y:t) = x=y
99 let seeded_hash = Hashtbl.seeded_hash
100 end
101 module SSL = struct
102 type t = string list
103 let compare (x:t) (y:t) = Stdlib.compare x y
104 let equal (x:t) (y:t) = x=y
105 let seeded_hash = Hashtbl.seeded_hash
106 end
107 module SSA = struct
108 type t = string array
109 let compare (x:t) (y:t) = Stdlib.compare x y
110 let equal (x:t) (y:t) = x=y
111 let seeded_hash = Hashtbl.seeded_hash
112 end
113
114 module MS = Map.Make(SS)
115 module MI = Map.Make(SI)
116 module MSP = Map.Make(SSP)
117 module MSL = Map.Make(SSL)
118 module MSA = Map.Make(SSA)
119
120
121 (* Generic hash wrapped as a functorial hash *)
122
123 module HofM (M: Map.S) : Hashtbl.SeededS with type key = M.key =
124 struct
125 type key = M.key
126 type 'a t = (key, 'a) Hashtbl.t
127 let create ?random:bool s = Hashtbl.create s
128 let clear = Hashtbl.clear
129 let reset = Hashtbl.reset
130 let copy = Hashtbl.copy
131 let add = Hashtbl.add
132 let remove = Hashtbl.remove
133 let find = Hashtbl.find
134 let find_opt = Hashtbl.find_opt
135 let find_all = Hashtbl.find_all
136 let replace = Hashtbl.replace
137 let mem = Hashtbl.mem
138 let iter = Hashtbl.iter
139 let fold = Hashtbl.fold
140 let length = Hashtbl.length
141 let stats = Hashtbl.stats
142 let filter_map_inplace = Hashtbl.filter_map_inplace
143 let to_seq = Hashtbl.to_seq
144 let to_seq_keys = Hashtbl.to_seq_keys
145 let to_seq_values = Hashtbl.to_seq_values
146 let of_seq = Hashtbl.of_seq
147 let add_seq = Hashtbl.add_seq
148 let replace_seq = Hashtbl.replace_seq
149 end
150
151 module HS1 = HofM(MS)
152 module HI1 = HofM(MI)
153 module HSP = HofM(MSP)
154 module HSL = HofM(MSL)
155
156 (* Specific functorial hashes *)
157
158 module HS2 = Hashtbl.MakeSeeded(SS)
159 module HS3 = Hashtbl.MakeSeeded(String)
160 module HI2 = Hashtbl.MakeSeeded(SI)
161
162 (* Specific weak functorial hashes *)
163 module WS = Ephemeron.K1.MakeSeeded(SS)
164 module WSP1 = Ephemeron.K1.MakeSeeded(SSP)
165 module WSP2 = Ephemeron.K2.MakeSeeded(SS)(SS)
166 module WSL = Ephemeron.K1.MakeSeeded(SSL)
167 module WSA = Ephemeron.Kn.MakeSeeded(SS)
168
169 (* Instantiating the test *)
170
171 module TS1 = Test(HS1)(MS)
172 module TS2 = Test(HS2)(MS)
173 module TS3 = Test(HS3)(MS)
174 module TI1 = Test(HI1)(MI)
175 module TI2 = Test(HI2)(MI)
176 module TSP = Test(HSP)(MSP)
177 module TSL = Test(HSL)(MSL)
178
179 (* Data set: strings from a file, associated with their line number *)
180
181 let file_data filename =
182 let ic = open_in filename in
183 let lineno = ref 0 in
184 let data = ref [] in
185 begin try
186 while true do
187 let l = input_line ic in
188 incr lineno;
189 data := (l, !lineno) :: !data
190 done
191 with End_of_file -> ()
192 end;
193 close_in ic;
194 Array.of_list !data
195
196 (* Data set: fixed strings *)
197
198 let string_data = [|
199 "Si", 0; "non", 1; "e", 2; "vero", 3; "e", 4; "ben", 5; "trovato", 6;
200 "An", 10; "apple", 11; "a", 12; "day", 13; "keeps", 14; "the", 15;
201 "doctor", 16; "away", 17;
202 "Pierre", 20; "qui", 21; "roule", 22; "n'amasse", 23; "pas", 24; "mousse", 25;
203 "Asinus", 30; "asinum", 31; "fricat", 32
204 |]
205
206 (* Data set: random integers *)
207
208 let random_integers num range =
209 let data = Array.make num (0,0) in
210 for i = 0 to num - 1 do
211 data.(i) <- (Random.int range, i)
212 done;
213 data
214
215 (* Data set: pairs *)
216
217 let pair_data data =
218 Array.map (fun (k, d) -> ((k, k), d)) data
219
220 (* Data set: lists *)
221
222 let list_data data =
223 let d = Array.make (Array.length data / 10) ([], "0") in
224 let j = ref 0 in
225 let rec mklist n =
226 if n <= 0 || !j >= Array.length data then [] else begin
227 let hd = fst data.(!j) in
228 incr j;
229 let tl = mklist (n-1) in
230 hd :: tl
231 end in
232 for i = 0 to Array.length d - 1 do
233 d.(i) <- (mklist (Random.int 16), Int.to_string i)
234 done;
235 d
236
237 (* The test *)
238
239 let _ =
240 printf "-- Random integers, large range\n%!";
241 TI1.test (random_integers 20_000 1_000_000);
242 printf "-- Random integers, narrow range\n%!";
243 TI2.test (random_integers 20_000 1_000);
244 let d =
245 try file_data "../../LICENSE" with Sys_error _ -> string_data in
246 printf "-- Strings, generic interface\n%!";
247 TS1.test d;
248 printf "-- Strings, functorial interface\n%!";
249 TS2.test d;
250 printf "-- Strings, functorial(String) interface\n%!";
251 TS3.test d;
252 printf "-- Pairs of strings\n%!";
253 TSP.test (pair_data d);
254 printf "-- Lists of strings\n%!";
255 TSL.test (list_data d)
256
257
258 let () =
259 let h = Hashtbl.create 16 in
260 for i = 1 to 1000 do Hashtbl.add h i (i * 2) done;
261 Printf.printf "%i elements\n" (Hashtbl.length h);
262 let () =
263 (* Check that filter_map_inplace of nothing changes nothing *)
264 let marshaled_before = Marshal.to_string h [Marshal.No_sharing] in
265 Hashtbl.filter_map_inplace (fun _k v -> Some v) h;
266 let marshaled_after = Marshal.to_string h [Marshal.No_sharing] in
267 assert (marshaled_before = marshaled_after) in
268 Hashtbl.filter_map_inplace (fun k v ->
269 if k mod 100 = 0 then ((*Hashtbl.add h v v;*) Some (v / 100)) else None)
270 h;
271 let l = Hashtbl.fold (fun k v acc -> (k, v) :: acc) h [] in
272 let l = List.sort compare l in
273 List.iter (fun (k, v) -> Printf.printf "%i,%i\n" k v) l;
274 Printf.printf "%i elements\n" (Hashtbl.length h)