Re: [PATCH v1 5/6] tools/ocaml/xenstored: use more efficient node trees

[Edwin Torok <edvin.torok@xxxxxxxxxx>]

On Mon, 2020-08-17 at 14:52 +0200, Christian Lindig wrote:
> +let compare a b =
> +  if equal a b then 0
> +  else -(String.compare a b)
> 
> I think this bit could use an inline comment why the sort order is
> reversed. This could be also simplified to -(String.compare a b)
> because this goes to the internal (polymorphic) compare implemented
> in C which does a physical equivalence check first.

Good point, I've dropped the equal, and instead of negating the compare
I swapped its arguments.

See V3 of the patch (ignore V2, for some reason it looked nearly
identical to V1, not matching what I had in my git tree,
perhaps git-format-patch didn't overwrite the patches?).

Best regards,
--Edwin

> 
> -- C
> 
> ________________________________________
> From: Edwin Torok
> Sent: 14 August 2020 23:14
> To: xen-devel@xxxxxxxxxxxxxxxxxxxx
> Cc: Edwin Torok; Christian Lindig; David Scott; Ian Jackson; Wei Liu
> Subject: [PATCH v1 5/6] tools/ocaml/xenstored: use more efficient
> node trees
> 
> This changes the output of xenstore-ls to be sorted.
> Previously the keys were listed in the order in which they were
> inserted
> in.
> docs/misc/xenstore.txt doesn't specify in what order keys are listed.
> 
> Map.update is used to retain semantics with replace_child:
> only an existing child is replaced, if it wasn't part of the original
> map we don't add it.
> Similarly exception behaviour is retained for del_childname and
> related
> functions.
> 
> Entries are stored in reverse sort order, so that upon Map.fold the
> constructed list is sorted in ascending order and there is no need
> for a
> List.rev.
> 
> Signed-off-by: Edwin Török <edvin.torok@xxxxxxxxxx>
> ---
>  tools/ocaml/xenstored/store.ml   | 46 +++++++++++++++---------------
> --
>  tools/ocaml/xenstored/symbol.ml  |  4 +++
>  tools/ocaml/xenstored/symbol.mli |  3 +++
>  3 files changed, 29 insertions(+), 24 deletions(-)
> 
> diff --git a/tools/ocaml/xenstored/store.ml
> b/tools/ocaml/xenstored/store.ml
> index 45659a23ee..d9dfa36045 100644
> --- a/tools/ocaml/xenstored/store.ml
> +++ b/tools/ocaml/xenstored/store.ml
> @@ -16,17 +16,19 @@
>   *)
>  open Stdext
> 
> +module SymbolMap = Map.Make(Symbol)
> +
>  module Node = struct
> 
>  type t = {
>         name: Symbol.t;
>         perms: Perms.Node.t;
>         value: string;
> -       children: t list;
> +       children: t SymbolMap.t;
>  }
> 
>  let create _name _perms _value =
> -       { name = Symbol.of_string _name; perms = _perms; value =
> _value; children = []; }
> +       { name = Symbol.of_string _name; perms = _perms; value =
> _value; children = SymbolMap.empty; }
> 
>  let get_owner node = Perms.Node.get_owner node.perms
>  let get_children node = node.children
> @@ -42,38 +44,34 @@ let set_value node nvalue =
>  let set_perms node nperms = { node with perms = nperms }
> 
>  let add_child node child =
> -       { node with children = child :: node.children }
> +       let children = SymbolMap.add child.name child node.children
> in
> +       { node with children }
> 
>  let exists node childname =
>         let childname = Symbol.of_string childname in
> -       List.exists (fun n -> Symbol.equal n.name childname)
> node.children
> +       SymbolMap.mem childname node.children
> 
>  let find node childname =
>         let childname = Symbol.of_string childname in
> -       List.find (fun n -> Symbol.equal n.name childname)
> node.children
> +       SymbolMap.find childname node.children
> 
>  let replace_child node child nchild =
> -       (* this is the on-steroid version of the filter one-replace
> one *)
> -       let rec replace_one_in_list l =
> -               match l with
> -               | []                               -> []
> -               | h :: tl when Symbol.equal h.name child.name ->
> nchild :: tl
> -               | h :: tl                          -> h ::
> replace_one_in_list tl
> -               in
> -       { node with children = (replace_one_in_list node.children) }
> +       { node with
> +         children = SymbolMap.update child.name
> +                    (function None -> None | Some _ -> Some nchild)
> +                    node.children
> +       }
> 
>  let del_childname node childname =
>         let sym = Symbol.of_string childname in
> -       let rec delete_one_in_list l =
> -               match l with
> -               | []                        -> raise Not_found
> -               | h :: tl when Symbol.equal h.name sym -> tl
> -               | h :: tl                   -> h ::
> delete_one_in_list tl
> -               in
> -       { node with children = (delete_one_in_list node.children) }
> +       { node with children =
> +               SymbolMap.update sym
> +                 (function None -> raise Not_found | Some _ -> None)
> +                 node.children
> +       }
> 
>  let del_all_children node =
> -       { node with children = [] }
> +       { node with children = SymbolMap.empty }
> 
>  (* check if the current node can be accessed by the current
> connection with rperm permissions *)
>  let check_perm node connection request =
> @@ -87,7 +85,7 @@ let check_owner node connection =
>                 raise Define.Permission_denied;
>         end
> 
> -let rec recurse fct node = fct node; List.iter (recurse fct)
> node.children
> +let rec recurse fct node = fct node; SymbolMap.iter (fun _ ->
> recurse fct) node.children
> 
>  let unpack node = (Symbol.to_string node.name, node.perms,
> node.value)
> 
> @@ -321,7 +319,7 @@ let ls store perm path =
>                                 Node.check_perm cnode perm
> Perms.READ;
>                                 cnode.Node.children in
>                         Path.apply store.root path do_ls in
> -       List.rev (List.map (fun n -> Symbol.to_string n.Node.name)
> children)
> +       SymbolMap.fold (fun k _ accu -> Symbol.to_string k :: accu)
> children []
> 
>  let getperms store perm path =
>         if path = [] then
> @@ -350,7 +348,7 @@ let traversal root_node f =
>         let rec _traversal path node =
>                 f path node;
>                 let node_path = Path.of_path_and_name path
> (Symbol.to_string node.Node.name) in
> -               List.iter (_traversal node_path) node.Node.children
> +               SymbolMap.iter (fun _ -> _traversal node_path)
> node.Node.children
>                 in
>         _traversal [] root_node
> 
> diff --git a/tools/ocaml/xenstored/symbol.ml
> b/tools/ocaml/xenstored/symbol.ml
> index dac6f9f819..2697915623 100644
> --- a/tools/ocaml/xenstored/symbol.ml
> +++ b/tools/ocaml/xenstored/symbol.ml
> @@ -31,6 +31,10 @@ let equal a b =
>    (* compare using physical equality, both members have to be part
> of the above weak table *)
>    a == b
> 
> +let compare a b =
> +  if equal a b then 0
> +  else -(String.compare a b)
> +
>  let stats () =
>    let len, entries, _, _, _, _ = WeakTable.stats tbl in
>    len, entries
> diff --git a/tools/ocaml/xenstored/symbol.mli
> b/tools/ocaml/xenstored/symbol.mli
> index 586ab57507..dd0f014796 100644
> --- a/tools/ocaml/xenstored/symbol.mli
> +++ b/tools/ocaml/xenstored/symbol.mli
> @@ -32,6 +32,9 @@ val to_string : t -> string
>  val equal: t -> t -> bool
>  (** Compare two symbols for equality *)
> 
> +val compare: t -> t -> int
> +(** Compare two symbols *)
> +
>  (** {6 Statistics } *)
> 
>  val stats : unit -> int * int
> --
> 2.25.1
>