From patchwork Mon Aug 23 12:12:21 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?b?w4Z2YXIgQXJuZmrDtnLDsCBCamFybWFzb24=?= X-Patchwork-Id: 12452595 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=-15.7 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,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 7D4B2C4338F for ; Mon, 23 Aug 2021 12:13:29 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6959261391 for ; Mon, 23 Aug 2021 12:13:29 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S236926AbhHWMOF (ORCPT ); Mon, 23 Aug 2021 08:14:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55178 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S236928AbhHWMNs (ORCPT ); Mon, 23 Aug 2021 08:13:48 -0400 Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4BF10C061292 for ; Mon, 23 Aug 2021 05:13:05 -0700 (PDT) Received: by mail-wr1-x42b.google.com with SMTP id d26so5626994wrc.0 for ; Mon, 23 Aug 2021 05:13:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=KxwY9rarD8b0ICvJdkHzt9ObJCkK6dxkm3RMamIW/hU=; b=Rl5XbgOjvAkfP87jbmvMWX/ADe0INp8Ssrf/RT5yFRz+02tAetz3jZ+4wCiLew4sCm b3nH6TqsjUpbLckaFNRT0ZbuRduygvBEYBBFVtbmlSojUwfa8MlEN6UZL1Q+5yhXcoED rTomToWHl3X564uDKk61hrN9LiGTgN/feTzahgow8fd2wbi+wvodbmEyaVsG2VF1sRRc b6KYKIlfYR9YyevLKfTRRD4ziJBezrKYsMnhzGA2wLUEN5ObhxLynhB/ghqKb5HcHQI4 spwWsqmCD6hF1mSH4oUNgCBNxU2x/Y6nHGiZnf/bEpd5sdLdsRg4d3zoCqFTeLKdnVPU uaUQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=KxwY9rarD8b0ICvJdkHzt9ObJCkK6dxkm3RMamIW/hU=; b=P7wQ5LTYncwcas9gzIzP1ap9ID13AXLxc3y5UCWL9kLhgS7hPMA99aqjx/pG1vpOut ej7koCv8gevej2fQLuqwZOmZ/nPC3urXQrspkAsbeLmfWrlyR2QjQhEoWTKI/aVt0dvj uzJbLxaA2k2XYfjYSga1euebHK+QkqnbXoFBhVcxDqp+ZP1F5lMZ3zYcxuaFS6JMGnLj L90mpO5KcPSYLtB1r+1ZCbqJyWvvsViNXnlZOWSjtWmgS3Afw6Cn7DjWV/MQNqUK1Uqy 20gKQJ96yneDpGxe6kiKnmnGzUJqg68x8LKCKN148xtHcgvO+t14IeP3nAEtJXAB6EZi wYWw== X-Gm-Message-State: AOAM533gGQhgTXPtt3jUUSo68EY6vK4JsZiMEk+M/u3R4kXi5oqRnQJf zvu0bkWOwPSTZx816cdq2ejV6r9sfZuWXX3F X-Google-Smtp-Source: ABdhPJy0RIvgL6B7vWIevgkCNDNsMng5YNNCsneC0RJ7Ua6ejE9E/mZtov1jqWtNq+KlEo28AteubA== X-Received: by 2002:a5d:51c6:: with SMTP id n6mr13236937wrv.370.1629720783647; Mon, 23 Aug 2021 05:13:03 -0700 (PDT) Received: from vm.nix.is (vm.nix.is. [2a01:4f8:120:2468::2]) by smtp.gmail.com with ESMTPSA id u10sm14824952wrt.14.2021.08.23.05.13.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 23 Aug 2021 05:13:03 -0700 (PDT) From: =?utf-8?b?w4Z2YXIgQXJuZmrDtnLDsCBCamFybWFzb24=?= To: git@vger.kernel.org Cc: Junio C Hamano , =?utf-8?q?Carlo_Marcelo_Arenas_Bel?= =?utf-8?q?=C3=B3n?= , Han-Wen Nienhuys Subject: [PATCH v4 10/28] reftable: a generic binary tree implementation Date: Mon, 23 Aug 2021 14:12:21 +0200 Message-Id: X-Mailer: git-send-email 2.33.0.662.gbaddc25a55e In-Reply-To: References: MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Han-Wen Nienhuys The reftable format includes support for an (OID => ref) map. This map can speed up visibility and reachability checks. In particular, various operations along the fetch/push path within Gerrit have ben sped up by using this structure. The map is constructed with help of a binary tree. Object IDs are hashes, so they are uniformly distributed. Hence, the tree does not attempt forced rebalancing. Signed-off-by: Han-Wen Nienhuys --- Makefile | 4 ++- reftable/tree.c | 63 ++++++++++++++++++++++++++++++++++++++++ reftable/tree.h | 34 ++++++++++++++++++++++ reftable/tree_test.c | 61 ++++++++++++++++++++++++++++++++++++++ t/helper/test-reftable.c | 1 + 5 files changed, 162 insertions(+), 1 deletion(-) create mode 100644 reftable/tree.c create mode 100644 reftable/tree.h create mode 100644 reftable/tree_test.c diff --git a/Makefile b/Makefile index 1d396c87be9..be14b66f9e3 100644 --- a/Makefile +++ b/Makefile @@ -2458,11 +2458,13 @@ REFTABLE_OBJS += reftable/block.o REFTABLE_OBJS += reftable/blocksource.o REFTABLE_OBJS += reftable/publicbasics.o REFTABLE_OBJS += reftable/record.o +REFTABLE_OBJS += reftable/tree.o +REFTABLE_TEST_OBJS += reftable/basics_test.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/record_test.o REFTABLE_TEST_OBJS += reftable/test_framework.o -REFTABLE_TEST_OBJS += reftable/basics_test.o +REFTABLE_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS)) diff --git a/reftable/tree.c b/reftable/tree.c new file mode 100644 index 00000000000..82db7995dd6 --- /dev/null +++ b/reftable/tree.c @@ -0,0 +1,63 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "tree.h" + +#include "basics.h" +#include "system.h" + +struct tree_node *tree_search(void *key, struct tree_node **rootp, + int (*compare)(const void *, const void *), + int insert) +{ + int res; + if (*rootp == NULL) { + if (!insert) { + return NULL; + } else { + struct tree_node *n = + reftable_calloc(sizeof(struct tree_node)); + n->key = key; + *rootp = n; + return *rootp; + } + } + + res = compare(key, (*rootp)->key); + if (res < 0) + return tree_search(key, &(*rootp)->left, compare, insert); + else if (res > 0) + return tree_search(key, &(*rootp)->right, compare, insert); + return *rootp; +} + +void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key), + void *arg) +{ + if (t->left) { + infix_walk(t->left, action, arg); + } + action(arg, t->key); + if (t->right) { + infix_walk(t->right, action, arg); + } +} + +void tree_free(struct tree_node *t) +{ + if (t == NULL) { + return; + } + if (t->left) { + tree_free(t->left); + } + if (t->right) { + tree_free(t->right); + } + reftable_free(t); +} diff --git a/reftable/tree.h b/reftable/tree.h new file mode 100644 index 00000000000..fbdd002e23a --- /dev/null +++ b/reftable/tree.h @@ -0,0 +1,34 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#ifndef TREE_H +#define TREE_H + +/* tree_node is a generic binary search tree. */ +struct tree_node { + void *key; + struct tree_node *left, *right; +}; + +/* looks for `key` in `rootp` using `compare` as comparison function. If insert + * is set, insert the key if it's not found. Else, return NULL. + */ +struct tree_node *tree_search(void *key, struct tree_node **rootp, + int (*compare)(const void *, const void *), + int insert); + +/* performs an infix walk of the tree. */ +void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key), + void *arg); + +/* + * deallocates the tree nodes recursively. Keys should be deallocated separately + * by walking over the tree. */ +void tree_free(struct tree_node *t); + +#endif diff --git a/reftable/tree_test.c b/reftable/tree_test.c new file mode 100644 index 00000000000..09a970e17b9 --- /dev/null +++ b/reftable/tree_test.c @@ -0,0 +1,61 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "tree.h" + +#include "basics.h" +#include "record.h" +#include "test_framework.h" +#include "reftable-tests.h" + +static int test_compare(const void *a, const void *b) +{ + return (char *)a - (char *)b; +} + +struct curry { + void *last; +}; + +static void check_increasing(void *arg, void *key) +{ + struct curry *c = arg; + if (c->last) { + assert(test_compare(c->last, key) < 0); + } + c->last = key; +} + +static void test_tree(void) +{ + struct tree_node *root = NULL; + + void *values[11] = { NULL }; + struct tree_node *nodes[11] = { NULL }; + int i = 1; + struct curry c = { NULL }; + do { + nodes[i] = tree_search(values + i, &root, &test_compare, 1); + i = (i * 7) % 11; + } while (i != 1); + + for (i = 1; i < ARRAY_SIZE(nodes); i++) { + assert(values + i == nodes[i]->key); + assert(nodes[i] == + tree_search(values + i, &root, &test_compare, 0)); + } + + infix_walk(root, check_increasing, &c); + tree_free(root); +} + +int tree_test_main(int argc, const char *argv[]) +{ + RUN_TEST(test_tree); + return 0; +} diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c index c9deeaf08c7..050551fa698 100644 --- a/t/helper/test-reftable.c +++ b/t/helper/test-reftable.c @@ -6,5 +6,6 @@ int cmd__reftable(int argc, const char **argv) basics_test_main(argc, argv); block_test_main(argc, argv); record_test_main(argc, argv); + tree_test_main(argc, argv); return 0; }