test_ancient_dict_verify.ml

   1 (* Verify shared dictionary. *)
   2
   3 open Printf
   4 open Unix
   5
   6 let argv = Array.to_list Sys.argv
   7
   8 let wordsfile, datafile =
   9   match argv with
  10   | [_; wordsfile; datafile] ->
  11       wordsfile, datafile
  12   | _ ->
  13       failwith (sprintf "usage: %s wordsfile datafile"
  14                   Sys.executable_name)
  15
  16 let md =
  17   let fd = openfile datafile [O_RDWR] 0o644 in
  18   Ancient.attach fd 0n
  19
  20 let arraysize = 256 (* one element for each character *)
  21
  22 type t = Not_Found | Exists of t array | Not_Exists of t array;;
  23 let tree : t array Ancient.ancient = Ancient.get md 0
  24 let tree = Ancient.follow tree
  25
  26 let word_exists word =
  27   try
  28     let tree = ref tree in
  29     let len = String.length word in
  30     for i = 0 to len-2; do
  31       let c = word.[i] in
  32       let c = Char.code c in
  33       match (!tree).(c) with
  34       | Not_Found -> raise Not_found
  35       | Exists tree'
  36       | Not_Exists tree' -> tree := tree'
  37     done;
  38
  39     (* Final character. *)
  40     let c = word.[len-1] in
  41     let c = Char.code c in
  42     match (!tree).(c) with
  43     | Not_Found
  44     | Not_Exists _ -> false
  45     | Exists _ -> true
  46   with
  47     Not_found -> false
  48
  49 let () =
  50   (* Read in the words and keep in a local list. *)
  51   let words = ref [] in
  52   let chan = open_in wordsfile in
  53   let rec loop () =
  54     let word = input_line chan in
  55     if word <> "" then words := word :: !words;
  56     loop ()
  57   in
  58   (try loop () with End_of_file -> ());
  59   close_in chan;
  60   let words = List.rev !words in
  61
  62   (* Verify that the number of words in the tree is the same as the
  63    * number of words in the words file.
  64    *)
  65   let nr_expected = List.length words in
  66   let nr_actual =
  67     let rec count tree =
  68       let c = ref 0 in
  69       for i = 0 to arraysize-1 do
  70         match tree.(i) with
  71         | Not_Found -> ()
  72         | Exists tree ->
  73             c := !c + 1 + count tree
  74         | Not_Exists tree ->
  75             c := !c + count tree
  76       done;
  77       !c
  78     in
  79     count tree in
  80
  81   if nr_expected <> nr_actual then
  82     failwith (sprintf
  83                 "verify failed: expected %d words but counted %d in tree"
  84                 nr_expected nr_actual);
  85
  86   (* Check each word exists in the tree. *)
  87   List.iter (
  88     fun word ->
  89       if not (word_exists word) then
  90         failwith (sprintf "verify failed: word '%s' missing from tree" word)
  91   ) words;
  92
  93   Ancient.detach md;
  94
  95   (* Garbage collect - good way to check we haven't broken anything. *)
  96   Gc.compact ();
  97
  98   printf "Verification succeeded.\n"