[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [PATCH v1 5/6] tools/ocaml/xenstored: use more efficient node trees
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 >
|
Lists.xenproject.org is hosted with RackSpace, monitoring our |