From patchwork Fri Jan 15 22:28:56 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= X-Patchwork-Id: 12024321 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-19.0 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_CR_TRAILER,INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS, URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1B46BC433E0 for ; Fri, 15 Jan 2021 22:53:24 +0000 (UTC) Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id D4A0423128 for ; Fri, 15 Jan 2021 22:53:23 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org D4A0423128 Authentication-Results: mail.kernel.org; dmarc=fail (p=reject dis=none) header.from=citrix.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=xen-devel-bounces@lists.xenproject.org Received: from list by lists.xenproject.org with outflank-mailman.68748.123224 (Exim 4.92) (envelope-from ) id 1l0Xxy-0002WJ-M7; Fri, 15 Jan 2021 22:53:14 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 68748.123224; Fri, 15 Jan 2021 22:53:14 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1l0Xxy-0002W9-Gq; Fri, 15 Jan 2021 22:53:14 +0000 Received: by outflank-mailman (input) for mailman id 68748; Fri, 15 Jan 2021 22:53:13 +0000 Received: from us1-rack-iad1.inumbo.com ([172.99.69.81]) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1l0Xxx-0001Wj-04 for xen-devel@lists.xenproject.org; Fri, 15 Jan 2021 22:53:13 +0000 Received: from esa6.hc3370-68.iphmx.com (unknown [216.71.155.175]) by us1-rack-iad1.inumbo.com (Halon) with ESMTPS id 3f5fe6cd-fc20-48c5-bbed-42ec3f69d494; Fri, 15 Jan 2021 22:52:35 +0000 (UTC) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 3f5fe6cd-fc20-48c5-bbed-42ec3f69d494 DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=citrix.com; s=securemail; t=1610751154; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=X7XyD2V6jMFkw/QtmgQYzQRGshY0fkhqbVCJVUmwv1A=; b=QcxUH91eX51ccsFO6ttyQ4QWcuP1q6imal2VhHnuzrVS2GIDine7IJYs utvgQS8DDbDO9RU4qh0IUNKz/lq3eQzSOyB1MEiENyLTA+z+uttcmGviC YJ+uJ7WycUuOb+bVq/g3B4Qike6UgQW45btGMUJhNB1LACAQiMKu5CP3Z c=; Authentication-Results: esa6.hc3370-68.iphmx.com; dkim=none (message not signed) header.i=none IronPort-SDR: amcrpVM51Xv+RMjduqtrDS7MY7GC3tzNnjjQlLbMq9NBB+U8ZEzJlWvUdV0GFczUC6uhPSfocp gLKU4kTmfYL8q7IqXireAozZ99Q6m6Hf1kanzVWQWEvh97GqDCRZ1acdQb9jlb7q6wuUVKJKP5 GpjiC0Ry//tbpKFHTJFpD3YB7wGYWrLl+jJdaqiEEuRglyaIifl0cPpUtB659nFj6q9OZFrei4 f8Ci8wweyx6pUz4RmDyOVPyZMP29SenWvGF1wXO6r4LqeRWuesDFtYghRsnPts4RrIYO2nlGrR Fns= X-SBRS: 5.1 X-MesageID: 35435269 X-Ironport-Server: esa6.hc3370-68.iphmx.com X-Remote-IP: 162.221.158.21 X-Policy: $RELAYED X-IronPort-AV: E=Sophos;i="5.79,350,1602561600"; d="scan'208";a="35435269" From: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= To: CC: =?utf-8?b?RWR3aW4gVMO2csO2aw==?= , "Christian Lindig" , David Scott , "Ian Jackson" , Wei Liu Subject: [PATCH v4 2/4] tools/ocaml/xenstored: backport find_opt/update from 4.06 Date: Fri, 15 Jan 2021 22:28:56 +0000 Message-ID: X-Mailer: git-send-email 2.27.0 In-Reply-To: References: MIME-Version: 1.0 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 --- Changed since V3: * repost after XSA to avoid conflicts --- tools/ocaml/xenstored/stdext.ml | 19 +++++++++++++++++++ tools/ocaml/xenstored/trie.ml | 2 ++ 2 files changed, 21 insertions(+) diff --git a/tools/ocaml/xenstored/stdext.ml b/tools/ocaml/xenstored/stdext.ml index e1567c4dfa..0640602449 100644 --- a/tools/ocaml/xenstored/stdext.ml +++ b/tools/ocaml/xenstored/stdext.ml @@ -50,6 +50,25 @@ module Filename = struct cmd :: args |> List.map quote |> String.concat " " end +module Map = struct +module Make(Ord: Map.OrderedType) = struct + +include Map.Make(Ord) + +let find_opt k t = try Some (find k t) with Not_found -> None + +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 + +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 = {