| 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) |