From patchwork Sun Aug 4 14:06:45 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13752647 Received: from mail-pf1-f172.google.com (mail-pf1-f172.google.com [209.85.210.172]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1E1DD50269 for ; Sun, 4 Aug 2024 14:11:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780694; cv=none; b=opRLZk2df+qF5jySnAxNRwJHnTlDt9KcZ2AiWqqM2xHmuLi/xXjQE7r6H8o2algti93CI/QssmS4o+uL807Ts2KMMDUelX8iyQ3a9hPIzsDpA//YVOdM8s4+7lGNK1APt8bm7dsyanQz6042DH4UJJXeNHo1DiHGtPVArexmRgU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780694; c=relaxed/simple; bh=6dcZwXz7GFp7iAldfAYFiGDg1AfVonu0hu3Z6u9wQN4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=brTd5NXs/3JmkwCoQ9uj3CtHXlt2yo2VCh5oJUtNkVz229ssVVynkzXoad6Pvw+ET9ef6psd0yITcDlD99OW6lL/5ZwgDlQd/WAy3vOQiQlJIsGzK5qQUm/qhki0YH+1Bu5qvoxbZDl9SjDPnCHgh0t/uGNhFQAQ0T77oN5b7/U= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=VLPr6m+a; arc=none smtp.client-ip=209.85.210.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="VLPr6m+a" Received: by mail-pf1-f172.google.com with SMTP id d2e1a72fcca58-70d18112b60so3670559b3a.1 for ; Sun, 04 Aug 2024 07:11:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722780692; x=1723385492; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=nIDjQDvcxNu4l7Bz0MrT/RMIwMtJCJpsOd0bgbZFxZ8=; b=VLPr6m+a9OvUKDLUufjh34Oj4WGae0UKp3V3QPbyuHNnd6TPo7kNk2liuzUwaIxLMK WhnYetvLBhYGb19HVTeu7GcS/UfXnrfK1uz/EzgOaLexKC6PNvEmALfdv3qgF0L5asU3 uyvH2+b0wgJwOt5LWuyNWPMjFbfjMxr/eIHMi7R9f7EZSegnqQGndGtpV4PagLod1Rj0 2vtxQ257Iu8kapUu53v3Ff1ITvqJpYsbRdmokYpYzjvDfdep2WN7LNE2zrpAGjJ+LDC7 7LKZH/CkGSyxGdESSLCuzlJKVAluLFjiLKWc3tLSWas9h2yClAFjEOktVL84FKYpRSq/ GyXA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722780692; x=1723385492; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=nIDjQDvcxNu4l7Bz0MrT/RMIwMtJCJpsOd0bgbZFxZ8=; b=OH7tuNOMKGpDovbNACa9Wn/MqbaYSriR3n0zZPSOdtlelTb/SyERrrJwIihYkW3RdI ps8bKbuxjl9mpDLWq0ySSJGuopi/7BrG6KZ3pOhlpohpjupMMxztpCdEcZcPq1jeSA7H RY3PtmoeORufceXzGhzz0+ziedR9uMOjkKkn4FvPBOlNOcViz5sfIsg+Nk7JnI6mLtBP CSIzyd5qrDC8HiL1X0GAfKlRYzAwkqqoLiHq2YTRyAJ7Jv930pxRm+QMJVcm1OGWz4Au EFa9pQJkJFawf71mxlR7x8rifvztDTWrXZHlKSPIMejqjiXy6DwJcOvX52SYMtvFnP7V mH8Q== X-Gm-Message-State: AOJu0Yy3+kBeqxlLoEYZRUE7re5lGT38JBpnaGngMQF1X7JlyFKi0ylj NCulOgwTr0aFbi36r4RDnVrA9dw8E8ewN9khxLgsrDOFDqOEN0nGXz/TgIUX X-Google-Smtp-Source: AGHT+IG2g/+u1DjIIiIbJp4Fp6uDuHQK+f6hBumb6TtWJtlozVN0pKrhfllF8gXCEDnK1VsI4ueDlQ== X-Received: by 2002:aa7:830b:0:b0:70c:e1ec:4233 with SMTP id d2e1a72fcca58-71065e4c8aemr12647069b3a.6.1722780691636; Sun, 04 Aug 2024 07:11:31 -0700 (PDT) Received: from Ubuntu.. ([27.59.94.183]) by smtp.googlemail.com with ESMTPSA id d2e1a72fcca58-7106ec269d2sm4125047b3a.17.2024.08.04.07.11.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 04 Aug 2024 07:11:31 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v7 1/5] reftable: remove unnecessary curly braces in reftable/tree.c Date: Sun, 4 Aug 2024 19:36:45 +0530 Message-ID: <20240804141105.4268-2-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240804141105.4268-1-chandrapratap3519@gmail.com> References: <20240802121318.4583-1-chandrapratap3519@gmail.com> <20240804141105.4268-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 According to Documentation/CodingGuidelines, single-line control-flow statements must omit curly braces (except for some special cases). Make reftable/tree.c adhere to this guideline. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- reftable/tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-) diff --git a/reftable/tree.c b/reftable/tree.c index 528f33ae38..5ffb2e0d69 100644 --- a/reftable/tree.c +++ b/reftable/tree.c @@ -39,25 +39,20 @@ struct tree_node *tree_search(void *key, struct tree_node **rootp, void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key), void *arg) { - if (t->left) { + if (t->left) infix_walk(t->left, action, arg); - } action(arg, t->key); - if (t->right) { + if (t->right) infix_walk(t->right, action, arg); - } } void tree_free(struct tree_node *t) { - if (!t) { + if (!t) return; - } - if (t->left) { + if (t->left) tree_free(t->left); - } - if (t->right) { + if (t->right) tree_free(t->right); - } reftable_free(t); } From patchwork Sun Aug 4 14:06:46 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13752648 Received: from mail-oa1-f41.google.com (mail-oa1-f41.google.com [209.85.160.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D4D2541A92 for ; Sun, 4 Aug 2024 14:11:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.41 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780698; cv=none; b=q0zgLWR+ESm4chMKa/D97WdJmhCXRe42XBo7kHXIZdLkkd/wzY36EwRdA6Zd8gCOgAGSacWl4zfuODKXCNKVWtLJ7lPYbc5tAheNDPyyedol5msHFEkHe6FC/RTCwh6CpkvaeJrK0uEpbaYqoW3nyDoCNq+D4xjejlWldR/KYzA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780698; c=relaxed/simple; bh=RAKSU9kduzL06rcjoz3mIoEnrGGsM/eS3Np1xn60mx8=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=WiCIAxrxp3UA14oyNYPhTbfStOBWwWEdNqzf+2DH1Rl7gnozGL8QcuRs9+q4ue4CmAdZQZTwp56fK1dIHayuDHC+m37Sc7k11n9iL4IR+QCRXms3AGMnK8Rx9PxHc07DqX6vOtlaRzl3FmpuVL9xI5SKxhl7vgH8CyfJ58NkYPE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=j4W8nW8t; arc=none smtp.client-ip=209.85.160.41 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="j4W8nW8t" Received: by mail-oa1-f41.google.com with SMTP id 586e51a60fabf-267b7ef154aso6269510fac.0 for ; Sun, 04 Aug 2024 07:11:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722780695; x=1723385495; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=53vD0V3zYrdWvpy4M6dnjXGn/EwOET+r+23g2ixiD2U=; b=j4W8nW8tzgwVEkUkPWtIA4tvVdTODb8t1gSGpi46QsKytPwucON8jdB0w/SKCGBVR6 YkFmloiCXGchT99niL4CVLrOHJLaygp0wocrmCO64W3WH3gsOxZSvJ8fIVaymUQpVm5/ tzf8hfMBaxsKbA/dKPsy+aqd7AY0gpg/VvNyaKuKNI9dH/1VlywpsSHj3gXQWpzdgrlE zcSVy4m323SGNmUt1ZkW6pcKs0r/JAbGRVmqigime73auOVFM2wSN6Fm8W8/QR5z+C25 vZYwvimssyo64q9STcebAQygZssR7fC9IlgBUE06++ZGxFvl2nt3F41HIJB7YlMWdQIK PCZw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722780695; x=1723385495; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=53vD0V3zYrdWvpy4M6dnjXGn/EwOET+r+23g2ixiD2U=; b=RucU5/GDj9lLgaThVqpFoxz2SxH1/dassBBEsuwBNIi61XFA67DFXdmnDBKHwzle+9 FENWbkDHR8P4VqQJeQYcPa5O8SCdSFfF2G1S0uZfXl1QzM836Ua5QHnWU+hQJ+olaCB7 U+6b7+Mvts1SLASiTfnfo9l4nZxCzwDdIOK+22QuSL8KWGBcf9dVpYg13A538XYg2Qho /9Wid2m6zbf0nKMBhazuqW+4IKrULjQax9SXCmQWPLeAY7erXdOZadT71aB5yNhJ2YHJ zLwsKEHDTLCumWv5OP1IhZJq9MvGMhvEGXUNBu5pB3uzKDMuzcP/jqCNow9ywk1tVDWm Ackg== X-Gm-Message-State: AOJu0Yy9kSqrd6sYk8wBLrHaxbUznrrVofkWxV0ZYPtd8gEPChPY9JOs FDHAn25N5oURJV1riEvpdGjrkd7P1mRCZOspIr7icSsR0hnHJs1W1ky5DTxl X-Google-Smtp-Source: AGHT+IH5fu3xao1CzQGkPyzofgkM01EHjcAEirXmk2W5jmJOouNP86V23mqevXcMZCu+UvsuBOF2fw== X-Received: by 2002:a05:6870:b4a1:b0:25e:b683:75d0 with SMTP id 586e51a60fabf-26891ee164dmr10861181fac.49.1722780695184; Sun, 04 Aug 2024 07:11:35 -0700 (PDT) Received: from Ubuntu.. ([27.59.94.183]) by smtp.googlemail.com with ESMTPSA id d2e1a72fcca58-7106ec269d2sm4125047b3a.17.2024.08.04.07.11.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 04 Aug 2024 07:11:34 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v7 2/5] t: move reftable/tree_test.c to the unit testing framework Date: Sun, 4 Aug 2024 19:36:46 +0530 Message-ID: <20240804141105.4268-3-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240804141105.4268-1-chandrapratap3519@gmail.com> References: <20240802121318.4583-1-chandrapratap3519@gmail.com> <20240804141105.4268-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 reftable/tree_test.c exercises the functions defined in reftable/tree.{c, h}. Migrate reftable/tree_test.c to the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework and renaming the tests to align with unit-tests' standards. Also add a comment to help understand the test routine. Note that this commit mostly moves the test from reftable/ to t/unit-tests/ and most of the refactoring is performed by the trailing commits. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree_test.c | 60 ---------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 60 ++++++++++++++++++++++++++++++++++ 5 files changed, 61 insertions(+), 63 deletions(-) delete mode 100644 reftable/tree_test.c create mode 100644 t/unit-tests/t-reftable-tree.c diff --git a/Makefile b/Makefile index 3863e60b66..5499f7bcbd 100644 --- a/Makefile +++ b/Makefile @@ -1342,6 +1342,7 @@ UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics UNIT_TEST_PROGRAMS += t-reftable-merged UNIT_TEST_PROGRAMS += t-reftable-record +UNIT_TEST_PROGRAMS += t-reftable-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec @@ -2685,7 +2686,6 @@ REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o REFTABLE_TEST_OBJS += reftable/test_framework.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/reftable-tests.h b/reftable/reftable-tests.h index d5e03dcc1b..8516b1f923 100644 --- a/reftable/reftable-tests.h +++ b/reftable/reftable-tests.h @@ -15,7 +15,6 @@ int pq_test_main(int argc, const char **argv); int record_test_main(int argc, const char **argv); int readwrite_test_main(int argc, const char **argv); int stack_test_main(int argc, const char **argv); -int tree_test_main(int argc, const char **argv); int reftable_dump_main(int argc, char *const *argv); #endif diff --git a/reftable/tree_test.c b/reftable/tree_test.c deleted file mode 100644 index 6961a657ad..0000000000 --- a/reftable/tree_test.c +++ /dev/null @@ -1,60 +0,0 @@ -/* -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 "system.h" -#include "tree.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) { - EXPECT(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++) { - EXPECT(values + i == nodes[i]->key); - EXPECT(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 9d378427da..0acaf85494 100644 --- a/t/helper/test-reftable.c +++ b/t/helper/test-reftable.c @@ -6,7 +6,6 @@ int cmd__reftable(int argc, const char **argv) { /* test from simple to complex. */ block_test_main(argc, argv); - tree_test_main(argc, argv); pq_test_main(argc, argv); readwrite_test_main(argc, argv); stack_test_main(argc, argv); diff --git a/t/unit-tests/t-reftable-tree.c b/t/unit-tests/t-reftable-tree.c new file mode 100644 index 0000000000..8b1f9a66a0 --- /dev/null +++ b/t/unit-tests/t-reftable-tree.c @@ -0,0 +1,60 @@ +/* +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 "test-lib.h" +#include "reftable/tree.h" + +static int t_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) + check_int(t_compare(c->last, key), <, 0); + c->last = key; +} + +static void t_tree(void) +{ + struct tree_node *root = NULL; + void *values[11] = { 0 }; + struct tree_node *nodes[11] = { 0 }; + size_t i = 1; + struct curry c = { 0 }; + + /* + * Pseudo-randomly insert the pointers for elements between + * values[1] and values[10] (inclusive) in the tree. + */ + do { + nodes[i] = tree_search(&values[i], &root, &t_compare, 1); + i = (i * 7) % 11; + } while (i != 1); + + for (i = 1; i < ARRAY_SIZE(nodes); i++) { + check_pointer_eq(&values[i], nodes[i]->key); + check_pointer_eq(nodes[i], tree_search(&values[i], &root, &t_compare, 0)); + } + + infix_walk(root, check_increasing, &c); + tree_free(root); +} + +int cmd_main(int argc, const char *argv[]) +{ + TEST(t_tree(), "tree_search and infix_walk work"); + + return test_done(); +} From patchwork Sun Aug 4 14:06:47 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13752649 Received: from mail-oa1-f45.google.com (mail-oa1-f45.google.com [209.85.160.45]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C9442558BB for ; Sun, 4 Aug 2024 14:11:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.45 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780701; cv=none; b=JmW1tBOzlEW0gdv9hQo7h0HgczaOU4IYQ5bljHITeoi3/vIPno+SOgqzYzdsWq+XTWFIya1ljJVSoHC71Myn/NPs7cTKSZIAiKOla8NU5P+cgcF4KTwIiV6RPH9Px04uJr9Lw0C+h3j2SsJFxC32Sn5r2AHuS1Y++b9DmWMC0X4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780701; c=relaxed/simple; bh=wosj2RHFDPsXy1Q8qWoeEFWWoOhjsuXkN7V/tE4ajnY=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=koSfQlAVungAQjnbKvknCBWa8H4lcqoF2fIxc5TrlRTbZ52kTR0oTGxbRkmBWGpLTdstFYxDK5iP6DkSVKad0SAW84GkUXpo06b7neq9JHZyV3RK81Vz8cgcqmPwbxRKyP8pQz1H6/AG+4aHBnsq6+onCKDBG0evfgpeZHNUBwA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=V0qhfZEK; arc=none smtp.client-ip=209.85.160.45 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="V0qhfZEK" Received: by mail-oa1-f45.google.com with SMTP id 586e51a60fabf-260f057aa9bso6183593fac.2 for ; Sun, 04 Aug 2024 07:11:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722780698; x=1723385498; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=bihLSuYEJeRgrOWRMwTi9dCSTkdxCLdCjmW2QHlGvFs=; b=V0qhfZEKu8SyjJvD7ToVGgh8JQHySCfhonykq9LmDqTVS3JZIo44kMDGgAjQwSpt4N BoKVV5EH/gBC2vP5veDDMHetiLduDcy8kJqRLHQlAWFLed3TnaUEM+qUH5CAhs9QbZZy 6or/pAkpqi199w0bslgarKOU4h8lqod8DQyJjunvp1VjadTTQr1XvPgYR3MPbkXwKTGS NcqFZHnBNRPW+QZabN/O2v/Dv1nU9qwIy+qq+uRy96q85T6ZmxpdRuS3qy1qUOsSKus1 7+DArmH4VhfSEzsQSy+nsW8cEGc8Pw2ezxpEorrRhNilrm4QCaIHBuIgoTgNWLpQdyiQ n5gQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722780698; x=1723385498; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=bihLSuYEJeRgrOWRMwTi9dCSTkdxCLdCjmW2QHlGvFs=; b=csT9Sswcl3x0m28hbO9k0My5yBiPT4+g5Th0XJ3QKVzxOqdR8hDYc4xEN181df7PNT Mq38O33jsxSoIsEpw6716T3UxB2esGIqnzqEqA7Ag67K/cPX5FDukBTd8sxqGOuX79Kv y1DsM4/LvwQbdLZa1UdzYd7In9x42DgdC+TzEyWBc7SUVFZRjBaMaUuzS0OM2Erggzgd o6F3ptao0ysqncfIEZj296IJeCpF/qow3/PaNkIPNtkV5mVQ4zH5b/TqIzS1DwsdDCAt NDxPYBYpQtB4Z5riu6cXzJ+IbEwk4h11ByEHAO+1+pGN27pbL0K1H/9kJKTlNVZIyVIi BPug== X-Gm-Message-State: AOJu0YxAOpQ6T/7hZxV9XgQ3VsqxC+UdJqccn+CpnI0MpUxBnugKJCvt NEnq4eD2jNGVDAhFb/U/jfSjgLunGdSEW6nquJLifs8fJMPEU+4oKOjuZLc0 X-Google-Smtp-Source: AGHT+IGoe0T4atYeoJfCdFmCRCD13lapD2mzePJ/Z/eT0DGvNVzeVOwqT3ZzscB458twkVgx5Iv2bA== X-Received: by 2002:a05:6870:3c07:b0:260:fdda:5068 with SMTP id 586e51a60fabf-26891ab181cmr10675271fac.4.1722780698203; Sun, 04 Aug 2024 07:11:38 -0700 (PDT) Received: from Ubuntu.. ([27.59.94.183]) by smtp.googlemail.com with ESMTPSA id d2e1a72fcca58-7106ec269d2sm4125047b3a.17.2024.08.04.07.11.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 04 Aug 2024 07:11:37 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v7 3/5] t-reftable-tree: split test_tree() into two sub-test functions Date: Sun, 4 Aug 2024 19:36:47 +0530 Message-ID: <20240804141105.4268-4-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240804141105.4268-1-chandrapratap3519@gmail.com> References: <20240802121318.4583-1-chandrapratap3519@gmail.com> <20240804141105.4268-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 In the current testing setup, tests for both tree_search() and infix_walk() defined by reftable/tree.{c, h} are performed by a single test function, test_tree(). Split tree_test() into test_tree_search() and test_infix_walk() responsible for independently testing tree_search() and infix_walk() respectively. This improves the overall readability of the test file as well as simplifies debugging. Note that the last parameter in the tree_search() functiom is 'int insert' which when set, inserts the key if it is not found in the tree. Otherwise, the function returns NULL for such cases. While at it, use 'func' to pass function pointers and not '&func'. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- t/unit-tests/t-reftable-tree.c | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-) diff --git a/t/unit-tests/t-reftable-tree.c b/t/unit-tests/t-reftable-tree.c index 8b1f9a66a0..7cc52a1925 100644 --- a/t/unit-tests/t-reftable-tree.c +++ b/t/unit-tests/t-reftable-tree.c @@ -26,13 +26,12 @@ static void check_increasing(void *arg, void *key) c->last = key; } -static void t_tree(void) +static void t_tree_search(void) { struct tree_node *root = NULL; void *values[11] = { 0 }; struct tree_node *nodes[11] = { 0 }; size_t i = 1; - struct curry c = { 0 }; /* * Pseudo-randomly insert the pointers for elements between @@ -48,13 +47,29 @@ static void t_tree(void) check_pointer_eq(nodes[i], tree_search(&values[i], &root, &t_compare, 0)); } - infix_walk(root, check_increasing, &c); + tree_free(root); +} + +static void t_infix_walk(void) +{ + struct tree_node *root = NULL; + void *values[11] = { 0 }; + struct curry c = { 0 }; + size_t i = 1; + + do { + tree_search(&values[i], &root, t_compare, 1); + i = (i * 7) % 11; + } while (i != 1); + + infix_walk(root, &check_increasing, &c); tree_free(root); } int cmd_main(int argc, const char *argv[]) { - TEST(t_tree(), "tree_search and infix_walk work"); + TEST(t_tree_search(), "tree_search works"); + TEST(t_infix_walk(), "infix_walk works"); return test_done(); } From patchwork Sun Aug 4 14:06:48 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13752650 Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com [209.85.210.171]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9478056766 for ; Sun, 4 Aug 2024 14:11:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780704; cv=none; b=HIjTEhZ1enscC35evLV3WAvqV+gCGyUqje5mosjNDwZK1NxyqzBukur8d7rbIRX9TQZr+HnONl7s9VAaCFrp+NYtDPQdHbMSQ6GSrW3QvvnQyqVZyx+rROna7Swwk8M216zH73ag455COu9Ll6l+rqy0BF8ZxbQgdqR3WZsRrhY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780704; c=relaxed/simple; bh=fEql4UDf4O+NGVTCY/xpS8UYxGIbT6Me4V5hNvMDVIU=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=sD7IXSWldeFC49MIr/xV06IJRn8Ezw21/OjGGehS+If8ntH6tyscCK5xabhmYtyYyM4gwpS9i+KRZ7KM5swHK/N3bmYNqRTRJFvtNK7aRmZgJFu0mUogtMwvlslPF2UMIEJrZ2aN+GDyJnX+XvgZ9jf5fHExcEuoC25r4DSzO7w= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Z5bEFfE8; arc=none smtp.client-ip=209.85.210.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Z5bEFfE8" Received: by mail-pf1-f171.google.com with SMTP id d2e1a72fcca58-70cec4aa1e4so6532860b3a.1 for ; Sun, 04 Aug 2024 07:11:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722780701; x=1723385501; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=e6LdhOVS1MV0pBmGNCTIpy/RdXSBas1kpEK/p/JLXE0=; b=Z5bEFfE84VYYcITaTY61HiAt8HN6pUPjkMqMZkXenc2yWPuyHs1Q2MXxAReEeF13XT H8KEGlOUkzY9och12UA9J9B+QCBWNMy3aO4E/JXhUZ/yQfdKo6b4mW00T+CvP5cp/De7 ot1TcH1fibSxw5PrUh/dna6+V05yF8p9xaCTadhkTmtklMzivWrmZ0zT0Qq+BizkCUFz E3SFWNQOgPmCn8RsVXFPlUvyB6h3b9rXCv0L50HJgZjnSTZfxnrkCeKdwan45rrGX2RP gTBj2+o9vdmoFOiVrqI/QYQf16fcL6psnbAylMsDquLH/wXWZlSHGXn+pv/+4+T4Xabd lzXg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722780701; x=1723385501; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=e6LdhOVS1MV0pBmGNCTIpy/RdXSBas1kpEK/p/JLXE0=; b=kU5jtjIJMGvTPsQubcfnsiQBVeRW74ku4PqZr0239nwywe8oaod6F9oymyf77K7cmw /+Mo54WufJ89Lc6F66Yb35tqFhDSK7cRAyfBKyn8IyDTy6FmOaPlH/gcR7Y7v26HS6mn hLaHQu8rj0hsyho29BQ3uPjJKW4kvMb7qTrkLsKC/iswz6JhB3nu39hFNJnpZ2TE8yQL Ppl7vcFwzbEp4x/uwDVw2/8DLgnaxQtpYf1Lu3ZP2+h6j9U2HdnLuO1fMWrp5+Wim/Hu /3Vi+W0HAXSNTP5bcaqcgXlsBmYHidwAThctjR5ylfirtCuSTc42iLtRvk+VjajYNexm EUFQ== X-Gm-Message-State: AOJu0YwiUJViN76l2OU5EdJF1DsjbRT5WOmCzcfI3AEHzJc/4LUCbz5E HF+c0DNF/aK26CFc1LpMpqbMNN3+kiOxY0mYcKlAJNzvMTY7ECVAN/esznyO X-Google-Smtp-Source: AGHT+IGmxJPql5O5oI/LOLqkPoEjf343Vfd+/7kyXzskQpahPCkLg1BiGl2It71h34joY84MywA4JQ== X-Received: by 2002:a05:6a00:66e7:b0:70b:260:3e2c with SMTP id d2e1a72fcca58-7106d046079mr11189377b3a.28.1722780701319; Sun, 04 Aug 2024 07:11:41 -0700 (PDT) Received: from Ubuntu.. ([27.59.94.183]) by smtp.googlemail.com with ESMTPSA id d2e1a72fcca58-7106ec269d2sm4125047b3a.17.2024.08.04.07.11.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 04 Aug 2024 07:11:40 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v7 4/5] t-reftable-tree: add test for non-existent key Date: Sun, 4 Aug 2024 19:36:48 +0530 Message-ID: <20240804141105.4268-5-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240804141105.4268-1-chandrapratap3519@gmail.com> References: <20240802121318.4583-1-chandrapratap3519@gmail.com> <20240804141105.4268-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 In the current testing setup for tree_search(), the case for non-existent key is not exercised. Improve this by adding a test-case for the same. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- t/unit-tests/t-reftable-tree.c | 1 + 1 file changed, 1 insertion(+) diff --git a/t/unit-tests/t-reftable-tree.c b/t/unit-tests/t-reftable-tree.c index 7cc52a1925..2220414a18 100644 --- a/t/unit-tests/t-reftable-tree.c +++ b/t/unit-tests/t-reftable-tree.c @@ -47,6 +47,7 @@ static void t_tree_search(void) check_pointer_eq(nodes[i], tree_search(&values[i], &root, &t_compare, 0)); } + check(!tree_search(values, &root, t_compare, 0)); tree_free(root); } From patchwork Sun Aug 4 14:06:49 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13752651 Received: from mail-oo1-f48.google.com (mail-oo1-f48.google.com [209.85.161.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0DA0155885 for ; Sun, 4 Aug 2024 14:11:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.161.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780707; cv=none; b=Dk+Bm9q303+l7FEUY2nBY46VRkaK7Hlidq0o3vR6GelFWshsspXWrsay0GlKsc9Kmqo7vENQpOC8WEgyEgHnr9SHlp0T/S2w1CDXM33KDLiztEK7TnCoNpuHV6MjG1Fumy5Yopj9JjP787ByeSidoFeEluMwMwXmuZmhaJpv13Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722780707; c=relaxed/simple; bh=SDgoGoMHoqxXAnjiVK1r06rkyxLRua6etfW6MLTBRvc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=cHRL7RYVqYQMreJoS5j4B3ROWOAuVnl1aBKiJIMzGYAoSKgLYndFkGUnjvUpe5es6Qttrie0Swtf0lkJ53m8myNuYzFLgR/EkHxOwHpMCEurHyYjcCkv8Hi5AY3ckcd8Oe8DvYlitnr1KIOD2O4FiDFY7Vhattq93NH9n4IvXC8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=BIKu4D+e; arc=none smtp.client-ip=209.85.161.48 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BIKu4D+e" Received: by mail-oo1-f48.google.com with SMTP id 006d021491bc7-5d5ed6f51cfso4591244eaf.0 for ; Sun, 04 Aug 2024 07:11:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722780704; x=1723385504; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=91UFm9QvBZlzVtdOiVwXWHHk/jsOEphDU/vi/gSo+Jc=; b=BIKu4D+ei56XI0LcLRNjnHbln/7/qpGkFJdnxENrHe1biYBTjpffrGQCg5Gt+t7eh2 AfJUyGfaKmqU8BQkdTt/dZQF6AtAwoY6IX+Q+bM+2ixAnGtjU9eXrtn9/GHdq1+WDTcL YUNkgreHWASlY9IZASckA6TIcVHxksMQFsL+sy9MbLHpEw6oxbG3WvLNKxHBzVZYdGVi W63Xtt5fedVTN6eCEQN8gFlxSxINIxjQzpYajrld/9kEwP4CoBy3AjQh+nHw04j+u/XN KgnZJ4MlFZoGIIi1+daeBz4SxjcHNLjhaZKWiPSpEh3uqyS8OPs5A2H/xUcS4X6HGHQm /ZXg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722780704; x=1723385504; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=91UFm9QvBZlzVtdOiVwXWHHk/jsOEphDU/vi/gSo+Jc=; b=rd+zen4ARSPhaaGlBMQsSL9urrF4dTKzYwGY7eAJeIrtlv8OiYFHGF6JTUtxkxo24j sZS0e/cnYYBcbtUT997BP4nfAr9gCsjfyaiT/mfwYvmoboqrdXWXo7u5oUSJcEWxqn3s lNaysv4mTXFyut5HZz6xCww/xOSBmbxb5JjY+bAEifbaHs7lcZpQN6WFuyH6NxaMbXLe DeHIFer1HWq0gQLSOVowkTmEmbaP3omRxan3TXnWp7ghKvuCXnpuYMI/RRSFZm9FTwMb x/WvxAlLIpe+2Vcvm5mucwqn89ns72GDTzdFByhl4FYvo+RwNhtIxoXAw0qxckFHeDLw devw== X-Gm-Message-State: AOJu0Yy6qsfTXmQ7Y7vuNeQVqHnK9b4U9teW146ODju8TK1K8VUHzFgR PjQcszxeM2KIzpCGccBORxNAo2//898Nu9j9YW5T1qDks1qOJk8vIaNl/pEe X-Google-Smtp-Source: AGHT+IEFCPnETHiVyYo1xjnvnwa3cXoTzOJJvyOV/o1wsl5N7tjwSwgm7tI8UnJMhfeG+BN1JcU5/g== X-Received: by 2002:a05:6870:214:b0:25e:7a1:ea8f with SMTP id 586e51a60fabf-26891ee21d2mr11351519fac.47.1722780704404; Sun, 04 Aug 2024 07:11:44 -0700 (PDT) Received: from Ubuntu.. ([27.59.94.183]) by smtp.googlemail.com with ESMTPSA id d2e1a72fcca58-7106ec269d2sm4125047b3a.17.2024.08.04.07.11.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 04 Aug 2024 07:11:43 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v7 5/5] t-reftable-tree: improve the test for infix_walk() Date: Sun, 4 Aug 2024 19:36:49 +0530 Message-ID: <20240804141105.4268-6-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240804141105.4268-1-chandrapratap3519@gmail.com> References: <20240802121318.4583-1-chandrapratap3519@gmail.com> <20240804141105.4268-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 In the current testing setup for infix_walk(), the following properties of an infix traversal of a tree remain untested: - every node of the tree must be visited - every node must be visited exactly once In fact, only the property 'traversal in increasing order' is tested. Modify test_infix_walk() to check for all the properties above. This can be achieved by storing the nodes' keys linearly, in a nullified buffer, as we visit them and then checking the input keys against this buffer in increasing order. By checking that the element just after the last input key is 'NULL' in the output buffer, we ensure that every node is traversed exactly once. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- t/unit-tests/t-reftable-tree.c | 22 +++++++++++++++------- 1 file changed, 15 insertions(+), 7 deletions(-) diff --git a/t/unit-tests/t-reftable-tree.c b/t/unit-tests/t-reftable-tree.c index 2220414a18..e7d774d774 100644 --- a/t/unit-tests/t-reftable-tree.c +++ b/t/unit-tests/t-reftable-tree.c @@ -15,15 +15,14 @@ static int t_compare(const void *a, const void *b) } struct curry { - void *last; + void **arr; + size_t len; }; -static void check_increasing(void *arg, void *key) +static void store(void *arg, void *key) { struct curry *c = arg; - if (c->last) - check_int(t_compare(c->last, key), <, 0); - c->last = key; + c->arr[c->len++] = key; } static void t_tree_search(void) @@ -55,15 +54,24 @@ static void t_infix_walk(void) { struct tree_node *root = NULL; void *values[11] = { 0 }; - struct curry c = { 0 }; + void *out[11] = { 0 }; + struct curry c = { + .arr = (void **) &out, + }; size_t i = 1; + size_t count = 0; do { tree_search(&values[i], &root, t_compare, 1); i = (i * 7) % 11; + count++; } while (i != 1); - infix_walk(root, &check_increasing, &c); + infix_walk(root, &store, &c); + for (i = 1; i < ARRAY_SIZE(values); i++) + check_pointer_eq(&values[i], out[i - 1]); + check(!out[i - 1]); + check_int(c.len, ==, count); tree_free(root); }