Re: [PATCH v4 2/4] Map: backport find_opt/update from 4.06

[Christian Lindig <christian.lindig@xxxxxxxxxx>]

________________________________________
From: Edwin Török <edvin.torok@xxxxxxxxxx>
Sent: 27 August 2020 18:35
To: xen-devel@xxxxxxxxxxxxxxxxxxxx
Cc: Edwin Torok; Christian Lindig; David Scott; Ian Jackson; Wei Liu
Subject: [PATCH v4 2/4] Map: backport find_opt/update from 4.06

We are currently on OCaml 4.02 as minimum version.
To make the followup optimizations compile backport these functions from
OCaml 4.06.

This implementation is less efficient than the one in the 4.06 standard
library which has access to the internals of the Map.

Signed-off-by: Edwin Török <edvin.torok@xxxxxxxxxx>
---
Changes since V3:
* this patch is new in V4
---
 tools/ocaml/xenstored/stdext.ml | 21 +++++++++++++++++++++
 tools/ocaml/xenstored/trie.ml   |  2 ++
 2 files changed, 23 insertions(+)

diff --git a/tools/ocaml/xenstored/stdext.ml b/tools/ocaml/xenstored/stdext.ml
index 4f2f3a2c8c..5bebe2aa27 100644
--- a/tools/ocaml/xenstored/stdext.ml
+++ b/tools/ocaml/xenstored/stdext.ml
@@ -44,6 +44,27 @@ let default d v =
 let maybe f v =
        match v with None -> () | Some x -> f x

+module Map = struct
+module Make(Ord: Map.OrderedType) = struct
+
+include Map.Make(Ord)
+
+let find_opt k t =
+       (* avoid raising exceptions, they can be expensive *)
+       if mem k t then Some (find k t) else None

I disagree with this argument. Exceptions in OCaml are cheap because they don't 
walk the stack and cut to the exception handler directly. Is there a reason why 
they could be expensive here? In any case, the code is correct.

+
+let update k f t =
+  let r = find_opt k t in
+  let r' = f r in
+  match r, r' with
+  | None, None -> t
+  | Some _, None -> remove k t
+  | Some r, Some r' when r == r' -> t
+  | _, Some r' -> add k r' t

This looks correct to me.

+
+end
+end
+
 module String = struct include String

 let of_char c = String.make 1 c
diff --git a/tools/ocaml/xenstored/trie.ml b/tools/ocaml/xenstored/trie.ml
index dc42535092..f513f4e608 100644
--- a/tools/ocaml/xenstored/trie.ml
+++ b/tools/ocaml/xenstored/trie.ml
@@ -13,6 +13,8 @@
  * GNU Lesser General Public License for more details.
  *)

+open Stdext
+
 module Node =
 struct
        type ('a,'b) t =  {
--
2.25.1

-- 
Acked-by: Christian Lindig <christian.lindig@xxxxxxxxxx>