From patchwork Thu Jun 6 07:40: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: 13687964 Received: from mail-pg1-f179.google.com (mail-pg1-f179.google.com [209.85.215.179]) (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 0256B1327E5 for ; Thu, 6 Jun 2024 07:57:15 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660637; cv=none; b=s4jVnd9qplV+ZDCNXET5QExvrjyJgw74yAaT6mMQxXnNDSINXE7SpvbVFsi4UIuV/FyRhxx5F3wCtaXQoOQI0tF2Sz6ZDSKtfSHZHi1FV1MAJcaqqBfkzQPIwgmtQ/sPbLxwmHfbubyQYR2JLX46RpAcvOuZXkNN2mUngkRhehc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660637; c=relaxed/simple; bh=nxGHuT2wMkcElOFugJXOkTq8Kpf/nPoOV7viKGjvxBA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=dAaHS6k5oufLpUCgieDnmdewdkXLc9YzqRNxqtLmTK1KXKoHVaofkV0nSL3JLgkIG4qgn4wUsI4+oYwz0Cg048vmPP2oNP3GePMQLghTfkm43nt9MkhxA2jjq5WJUmuUKG4rkq7REIpjuaQFg/ztag1/RFAd9HpuBARYJgiaWEs= 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=S+xfcO5Z; arc=none smtp.client-ip=209.85.215.179 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="S+xfcO5Z" Received: by mail-pg1-f179.google.com with SMTP id 41be03b00d2f7-6c7df306e86so502633a12.2 for ; Thu, 06 Jun 2024 00:57:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717660635; x=1718265435; 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=ObKsWVnXc6Yl+tO/MHcJd+VKjrh9mp9W8H1SVeJXPsc=; b=S+xfcO5ZcC+/dgB1pl18YcGpz65KVPAPEOP+tcnUpNpiz2VKA00yvGksTN4gpgoSRM VQ+YUsUF3n7ELBhUrV15uV3ZntkrxWsI4P3aVM9vQZoPDfq9LHL+s9pJfhTlsiuG+GYz U4w62rJSpU/5QvwdrBg9LwVtQeA24ib2NGXZBzf5I6Br8Ib18UkvD7UtoP8qUEsvXaqo CGj39T3Nu0jUlawi7B6JUpSTZMT5L0x7iMFtzzTeRmi1g2rRGCvyGXDVXzUgbL2ba0V0 VVXMmdsoPWppjDVDHsiHa2UWAm8HPEPNp49a2CMnV6vCDX+mjMG+1GVwnb+02rGbfvJa OHhQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717660635; x=1718265435; 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=ObKsWVnXc6Yl+tO/MHcJd+VKjrh9mp9W8H1SVeJXPsc=; b=VN8+3sJRpcmSLWyeY3oXOrWQ4U0M0FjhaJpzTxJ+uKQRUgexXbFuvlzjDmcg+TRYSE loh/z27ghNyWLHHmfvLr0uLEEduqkSoC+k0zvlFQUpEhiZWNEtAwtYgu6b1LVCwCHJNW 7zSpnBKg1UVZ8SY8xPEFZsVMHQtdLuvVd3xyxfSSzoa1WKPt8C72FChV6ShI3JlsQ9s2 CRijmzXhWaSiMog6iSa/J1+4VqK1Sqy1IKBk447ZHOGEkzbH4o9mzRjoFYJ1RAobiyNU Vp5cXu1ZoFERExkQHxbb0CWfw3NnA3p3gwwGufT0c9JVIDzGenhOwcqPWTX4joSEOKef z0IA== X-Gm-Message-State: AOJu0YwjJr6K444FD+dIp98bbbLcCMt947dB36LmXrQTbrWdimdEEZWh qy5bWu1kNprYOnnUb09zkHsjDLbIS/QpWaEWSqoG0KMo/F3jn5nivgOaBpS3 X-Google-Smtp-Source: AGHT+IE9b2V2wOGau4DqnvRJ2pn1qYOiJXgEeU4ZZANVJ7CSYepfJAVP4ZAQFekUI2LP51FnmX0SmA== X-Received: by 2002:a05:6a20:3ca4:b0:1ad:878:5006 with SMTP id adf61e73a8af0-1b2b6eab172mr5022515637.14.1717660634898; Thu, 06 Jun 2024 00:57:14 -0700 (PDT) Received: from Ubuntu.. ([27.61.69.112]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd7ed6b2sm8192415ad.246.2024.06.06.00.57.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 00:57:14 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH 1/6] reftable: clean up reftable/pq.c Date: Thu, 6 Jun 2024 13:10:45 +0530 Message-ID: <20240606075601.6989-2-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606075601.6989-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-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, control-flow statements with a single line as their body must omit curly braces. Make reftable/pq.c conform to this guideline. Besides that, remove unnecessary newlines and variable assignment. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- reftable/pq.c | 18 ++++-------------- 1 file changed, 4 insertions(+), 14 deletions(-) diff --git a/reftable/pq.c b/reftable/pq.c index 7fb45d8c60..0401c47068 100644 --- a/reftable/pq.c +++ b/reftable/pq.c @@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) pq->heap[0] = pq->heap[pq->len - 1]; pq->len--; - i = 0; while (i < pq->len) { int min = i; int j = 2 * i + 1; int k = 2 * i + 2; - if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) { + if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) min = j; - } - if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) { + if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) min = k; - } - - if (min == i) { + if (min == i) break; - } - SWAP(pq->heap[i], pq->heap[min]); i = min; } @@ -53,19 +47,15 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e) { int i = 0; - REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap); pq->heap[pq->len++] = *e; i = pq->len - 1; while (i > 0) { int j = (i - 1) / 2; - if (pq_less(&pq->heap[j], &pq->heap[i])) { + if (pq_less(&pq->heap[j], &pq->heap[i])) break; - } - SWAP(pq->heap[j], pq->heap[i]); - i = j; } } From patchwork Thu Jun 6 07:40: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: 13687965 Received: from mail-pg1-f177.google.com (mail-pg1-f177.google.com [209.85.215.177]) (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 D12831327E5 for ; Thu, 6 Jun 2024 07:57:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660640; cv=none; b=nixd0YznyxEfmT/XIqyJmzYDoSOt+ACiFrRpiOFGfZTPrw3/b0ahjaTx/ODx21lOT7gr1NbQcLobxZpJrr9BVvAX314c1w9N5yHsL6lkGNx0BUW6fVAeVlH74i8IAPpLRO++08ipkGg+lYZSLyDDBb7JOVrIYqVdxpAE8u+6FcA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660640; c=relaxed/simple; bh=7gNQeDRx585ssQgwNsS3J+aNzCltHbCwite7rn5dUtk=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=bJ2WnGzFdTnJGil93ENVkqVsCWicmeBv35GCrWlAncfe2yBVDWHH/Cj3TV8BBsVhfV60qTJXKWRX5VqeDOpRd1CRl8eqK3vhNuqy0YxDijvi1gwLIWv2Medqu8O8QtYjDiDYDJH8Tko+6QCcdIaa5KuPFef9loRqgUb4RQObHqg= 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=NGU6A9La; arc=none smtp.client-ip=209.85.215.177 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="NGU6A9La" Received: by mail-pg1-f177.google.com with SMTP id 41be03b00d2f7-6bfd4b88608so526184a12.1 for ; Thu, 06 Jun 2024 00:57:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717660638; x=1718265438; 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=TNhe0chjIYZVnz9qUIX1qeU5XaAjNa4Ck7uEoliYLk0=; b=NGU6A9LaEh/y3DmMop8WYjHj+R17zFVp7U/N0SH4XVhFy95wYe5nQ8xGVbXUw0Lya9 veh/3zI+FbO7FMwiYEXl946myrVKACkgAPEuLSZKYsq3Yw2QNKG6nh1WvcI95C0JH4V/ eimSwEzxz2BIpodMs7LW5ahUpf25joOWa3nGRNWqJR3QF6rk92JmnwEWsqxH3ibtC/W/ yO48LHgcK5q4dvtpmAJ28tXGzMdfe01KrCilEMcIdDGrFyWnCNQ21fcanvtcKF/mjpn4 1PK8ECTmoEv9IwtzQkuD8lzfxXGbmpmzc3zK1sNUACP4sRCwLcQa3ck488U48kvNM2dm CJPg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717660638; x=1718265438; 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=TNhe0chjIYZVnz9qUIX1qeU5XaAjNa4Ck7uEoliYLk0=; b=E8SkM7M7wkDA49WQHuhpSs75/slSziwQWHCRUXUy5xUVF3LmgYY7DGBGnnlMozzIe2 B4gD9q2ptd/g92cbbOgcUbqDzisl4PsKneeGEu/5b9C8hDkYrWAWdrSZ0flX7GJKk1s8 pXl2BeK1bIg9uE6sFi6OxoXQDmC5fhIfxV/K+b9yMZiGDXDzuuoLWA45Yd0er41VmUgZ 9W7LYK4Ldcqe9n/GZNqu4jpBbNwe2fWMQBVmYea9mjJ1zUeseTVgU/oMPAaR4UqpW3jq p0FQzQhUXD5kUg/jvtG5OdlUOU6pgE900z9xS91ZItbzSoL03vBi21t6Hf+33AwL7KcC 68ow== X-Gm-Message-State: AOJu0YzljGpUrLl4atRhYAjtGthzzGdFWnACS1OJijxlBKEQy4iXptT4 lDA5qgilgXh5L2tCUO6FSIhy+8EHd78QA+9vVLFLuIZsQmf2uuTtvtFCPhXo X-Google-Smtp-Source: AGHT+IEx82UML/mplxex8UxrMFCw47bW2xNjk0NZKL2hKBPM0ZFw2iFj6/iB8OO3VB7wYLcBJLTrcg== X-Received: by 2002:a05:6a21:186:b0:1b2:5931:574f with SMTP id adf61e73a8af0-1b2b712df57mr6205050637.40.1717660637657; Thu, 06 Jun 2024 00:57:17 -0700 (PDT) Received: from Ubuntu.. ([27.61.69.112]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd7ed6b2sm8192415ad.246.2024.06.06.00.57.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 00:57:17 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH 2/6] t: move reftable/pq_test.c to the unit testing framework Date: Thu, 6 Jun 2024 13:10:46 +0530 Message-ID: <20240606075601.6989-3-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606075601.6989-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 reftable/pq_test.c exercises a priority queue defined by reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- Makefile | 2 +- t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 35 ++++++++----------- 3 files changed, 15 insertions(+), 23 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (64%) diff --git a/Makefile b/Makefile index 59d98ba688..1cabe4cc69 100644 --- a/Makefile +++ b/Makefile @@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/% UNIT_TEST_PROGRAMS += t-ctype UNIT_TEST_PROGRAMS += t-mem-pool UNIT_TEST_PROGRAMS += t-prio-queue +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-trailer @@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o REFTABLE_TEST_OBJS += reftable/block_test.o REFTABLE_TEST_OBJS += reftable/dump.o REFTABLE_TEST_OBJS += reftable/merged_test.o -REFTABLE_TEST_OBJS += reftable/pq_test.o REFTABLE_TEST_OBJS += reftable/record_test.o REFTABLE_TEST_OBJS += reftable/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c index bae731669c..86a2b0f91a 100644 --- a/t/helper/test-reftable.c +++ b/t/helper/test-reftable.c @@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv) record_test_main(argc, argv); block_test_main(argc, argv); tree_test_main(argc, argv); - pq_test_main(argc, argv); readwrite_test_main(argc, argv); merged_test_main(argc, argv); stack_test_main(argc, argv); diff --git a/reftable/pq_test.c b/t/unit-tests/t-reftable-pq.c similarity index 64% rename from reftable/pq_test.c rename to t/unit-tests/t-reftable-pq.c index b7d3c80cc7..dcde73de66 100644 --- a/reftable/pq_test.c +++ b/t/unit-tests/t-reftable-pq.c @@ -6,35 +6,28 @@ license that can be found in the LICENSE file or at https://developers.google.com/open-source/licenses/bsd */ -#include "system.h" - -#include "basics.h" -#include "constants.h" -#include "pq.h" -#include "record.h" -#include "reftable-tests.h" -#include "test_framework.h" +#include "test-lib.h" +#include "reftable/constants.h" +#include "reftable/pq.h" void merged_iter_pqueue_check(struct merged_iter_pqueue pq) { - int i; - for (i = 1; i < pq.len; i++) { + for (int i = 1; i < pq.len; i++) { int parent = (i - 1) / 2; - - EXPECT(pq_less(&pq.heap[parent], &pq.heap[i])); + check(pq_less(&pq.heap[parent], &pq.heap[i])); } } static void test_pq(void) { - struct merged_iter_pqueue pq = { NULL }; + struct merged_iter_pqueue pq = { 0 }; struct reftable_record recs[54]; - int N = ARRAY_SIZE(recs) - 1, i; + size_t N = ARRAY_SIZE(recs) - 1, i; char *last = NULL; for (i = 0; i < N; i++) { struct strbuf refname = STRBUF_INIT; - strbuf_addf(&refname, "%02d", i); + strbuf_addf(&refname, "%02ld", (long)i); reftable_record_init(&recs[i], BLOCK_TYPE_REF); recs[i].u.ref.refname = strbuf_detach(&refname, NULL); @@ -48,7 +41,6 @@ static void test_pq(void) merged_iter_pqueue_add(&pq, &e); merged_iter_pqueue_check(pq); - i = (i * 7) % N; } while (i != 1); @@ -56,9 +48,9 @@ static void test_pq(void) struct pq_entry e = merged_iter_pqueue_remove(&pq); merged_iter_pqueue_check(pq); - EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF); + check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); if (last) - EXPECT(strcmp(last, e.rec->u.ref.refname) < 0); + check_int(strcmp(last, e.rec->u.ref.refname), <, 0); last = e.rec->u.ref.refname; } @@ -67,8 +59,9 @@ static void test_pq(void) merged_iter_pqueue_release(&pq); } -int pq_test_main(int argc, const char *argv[]) +int cmd_main(int argc, const char *argv[]) { - RUN_TEST(test_pq); - return 0; + TEST(test_pq(), "pq works"); + + return test_done(); } From patchwork Thu Jun 6 07:40: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: 13687966 Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com [209.85.214.170]) (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 D583413C683 for ; Thu, 6 Jun 2024 07:57:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660643; cv=none; b=ke+kDqlAHLtrYDEbBrCj1hOOqVYQeE0DknxnN5B4gxbz5ZTfHJFSiuDewwGQljEIscdlSOaCIU8hyNfze/q9wnpD/OcHH7yPErVVfNG3h/o+FSdR4vfmJcfOcoKRRaOpGaFa9OiBW9FOW+/gqsyKSCJdNcM7IHmNAihlS6Sh0WM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660643; c=relaxed/simple; bh=AVJ2GuvNLpH7T/7ly4HBkvLXnnV91MIswR3YTjrl5WA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=arGPEUCdJEXcCRfFg5GOIhkwhC9JB6czbH4V8qLB0qbhmvThr5tkgfnFu8/CSsXCxVaiw00vW3Md7sqn/mjTxG1i7eIndEzkub1uPQ9lpHKyK4eykFQVnyUkpMt8df86XyZwqWBP/E5Xum4Jz0bujyyOjZ3S8uEHXnM3WJPogMg= 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=OajWtOjF; arc=none smtp.client-ip=209.85.214.170 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="OajWtOjF" Received: by mail-pl1-f170.google.com with SMTP id d9443c01a7336-1f68834bfdfso5463995ad.3 for ; Thu, 06 Jun 2024 00:57:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717660641; x=1718265441; 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=FSddJ1yM2eHM1sv7NU+XFejcF0lHK8KOHxU46kroeK8=; b=OajWtOjFH6sCTCy8pCS0OpLQWOgiap8wXeob1slVp/ag/GTeairEeQELYpirkpoohH KFkSAZ6boMfCs2uEz03Zc7NE4nxBJ0PPLP/YUsXVEu7I+jr1DNCAj7o0HX6BW+bn/Aww +CLsfXV4igBU4ksiPChe8Qu3KvoyF2X1VG9TXVSTvYkYnevFxnTbgbCya0gVaDRSCRRn hw00F9Au3YZUUMSSjSdOzctVk5oPI+q+lT5Va4AJtpeNnLjN1T+qXJvtBKuTF1iO095J OEDXF1/eARCQyi53OYfMoVB7SAW3+DD2K3ymNDjFHIGuiVAbyB1XGJXHFPCN0wRQmpQW 9anA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717660641; x=1718265441; 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=FSddJ1yM2eHM1sv7NU+XFejcF0lHK8KOHxU46kroeK8=; b=Lgo4Thg7/hBfbGLV4G/3I/ROeLzOEAvyn4rBfbH+qQCsHMNN8docn3vxx5GmktjGKx rIbZzz8hxc/Ehfc/MPIXnQF4ESymE7/JlHrpc2+aTVVhmlNavkhe5OR8JRYRqc9UiHLv e3fgJKpJi5KzgxY/eyWeTW6xSWgsDWALjxeEff6r5lge4aMO4QIgrCSuWV8945k7j2Ab ngHIEJCVwmLDF6TCdzm3zuUCCYt8w0Q12c6vFP/Hu96F+8N7yuwGGoRiVEDYrR0QY1Fi joxucI4BP/Mr6Yso3kcAVTkUC+cThj4XK1Jd/0T3fsUMSSdX4bg3lhj8GCodp84PUrdZ p3lw== X-Gm-Message-State: AOJu0YyIV//PzoVp7ao/3V0dVGoal5mTOCqPElUo/snICC7BOYvIVumC jhhXtSnk3Oi4qUSabTTs9I1a52LWhk0RnrWx/l3PLjFhBUrEKtXOJSC5MK0u X-Google-Smtp-Source: AGHT+IGmfylLgJPZMUAGd/leaUihX3qrpR55NM2fcFCI7x/TM8xgKViBqZFBCZmG+42uQuMVu3+m5A== X-Received: by 2002:a17:902:d2c5:b0:1f3:83d:ee82 with SMTP id d9443c01a7336-1f6a5a1043cmr57341715ad.25.1717660640749; Thu, 06 Jun 2024 00:57:20 -0700 (PDT) Received: from Ubuntu.. ([27.61.69.112]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd7ed6b2sm8192415ad.246.2024.06.06.00.57.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 00:57:20 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH 3/6] t-reftable-pq: make merged_iter_pqueue_check() static Date: Thu, 6 Jun 2024 13:10:47 +0530 Message-ID: <20240606075601.6989-4-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606075601.6989-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 merged_iter_pqueue_check() is a function previously defined in reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in the testing of a priority queue as defined by reftable/pq.{c, h}. As such, this function is only called by reftable/pq_test.c and it makes little sense to expose it to non-testing code via reftable/pq.h. Hence, make this function static and remove its prototype from reftable/pq.h. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- reftable/pq.h | 1 - t/unit-tests/t-reftable-pq.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-) diff --git a/reftable/pq.h b/reftable/pq.h index f796c23179..707bd26767 100644 --- a/reftable/pq.h +++ b/reftable/pq.h @@ -22,7 +22,6 @@ struct merged_iter_pqueue { size_t cap; }; -void merged_iter_pqueue_check(struct merged_iter_pqueue pq); struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq); void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e); void merged_iter_pqueue_release(struct merged_iter_pqueue *pq); diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c index dcde73de66..5c5a4ecdc5 100644 --- a/t/unit-tests/t-reftable-pq.c +++ b/t/unit-tests/t-reftable-pq.c @@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at #include "reftable/constants.h" #include "reftable/pq.h" -void merged_iter_pqueue_check(struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check(struct merged_iter_pqueue pq) { for (int i = 1; i < pq.len; i++) { int parent = (i - 1) / 2; From patchwork Thu Jun 6 07:40: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: 13687967 Received: from mail-pl1-f177.google.com (mail-pl1-f177.google.com [209.85.214.177]) (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 7F1CF13BC35 for ; Thu, 6 Jun 2024 07:57:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660645; cv=none; b=ehN4HyvaJO5g8NwSuJe0Chj1FxtAsc0nXLjVcfQGR0d23N1j37bGpc7H24uZ17Oh1YfBqYWtb+KxNI1XJyVe9o+bLjRsMvT6CB07G48bW/4CJXcR83jColnq3uKGqpz6TNICWVh2sktilpuhNMV9weuyUl4XZCVrpH9JYEPB0Ow= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660645; c=relaxed/simple; bh=D9nQ2fEUIFfTJnU7qIz1ApVrJNrk/Bf8EA+KDXb9HEY=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=t9yxAteUUgg1rJJUCZ9ed+3ut6t6bOb8yhTEl/NXXQpe3gyoBham8oNGlz7WkNGUBTdRMXmOIrGf2c2LrC6C4RS022ZtfOnpO3Vbg3rcT1on5RD70wM3hOxsvbNiaSGMI1Sbo6/56Y+Q/V/0QEorQdCF8gGISnjtzI/ukzUdYOM= 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=WHTtadfA; arc=none smtp.client-ip=209.85.214.177 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="WHTtadfA" Received: by mail-pl1-f177.google.com with SMTP id d9443c01a7336-1f6c7cdec83so178455ad.0 for ; Thu, 06 Jun 2024 00:57:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717660643; x=1718265443; 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=QenudIcxVUzKolxgrGVwZKl4XyKKumgzlhfspZL21Ns=; b=WHTtadfAhh7LsQzMcTuaP/h6dJ/1vRPeZIN4FJrW8uWzQSoDIUWg+OM3dr4F+b0e5N 2QyZuxfFHphFoAgk0VFcn7dh/VWK4syvE+f+3eVeZMcXwk8KSt9FHmK75hJZS94jzVoy tnfQ7DxFsjspSFHQvIv8xBhOeqjyjSCW7PMTTIiwRWqer06wNj2oHsAzVhc/jcWtTP0r HCuNeZTeLRMX6FpM+eftjBUauO7IVuA/8BIciFyczMJBYuGosad+JRASXdvv2h0/YPv0 Yfy8FfgQ6NmvniPFQ4o34A9wb2Rx8WZk/r82sFHQc+7QgH3LQMPTZ+knDiW5ZsOCRGPg H0yA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717660643; x=1718265443; 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=QenudIcxVUzKolxgrGVwZKl4XyKKumgzlhfspZL21Ns=; b=YOBz8uQDkF1jrlZaKQfzHV+0n8YdmjSl4kZDRMDwuewH112orzrBM6GsN+p7xEtH6e dpOhh79vueXkmLrqBoBBO00xQJE9eGL8gEg+f+DG8AjJkVuDmrnk9YFcs5S0ICz7XjdD DxS+ylGmuowlPEymNyc6rmkcI+hd6PuU0Zvtan+lST/1Bm7eQOYtWD/ua8jrxBSjPJcf zE3CZ1FIH1mS7EhtGi7K9KVdMcvZw6dW2tW2YMj3qzks3hw/Wi9+gm1Z4h2lb9fx8vzT oXLofiEN+kHnw/RSBaxTi3WFNravMV+uCWg4GH63RgAEL0LJrDfS5ff0Ouet+j92Gcf1 NJlQ== X-Gm-Message-State: AOJu0Yzf4k4uSt4pejwVgKOK7HVfgBzkfh6ohHzI3x/OXGb3nS8FluXY /zxydSV9bDoQyylE/sXdrkZzgFmPUVl6qR56K5AVlg9mWVBMsxRyvNqA3XiA X-Google-Smtp-Source: AGHT+IFFw0B8/O49Le+FiS/LqQK1bsfhF5NL6CiI/QQwKHmMIcVOqNmdXbCpd1Kjwj9z14HCuFTkJA== X-Received: by 2002:a17:902:d2ca:b0:1f6:5013:7842 with SMTP id d9443c01a7336-1f6a5a12932mr61535185ad.27.1717660643518; Thu, 06 Jun 2024 00:57:23 -0700 (PDT) Received: from Ubuntu.. ([27.61.69.112]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd7ed6b2sm8192415ad.246.2024.06.06.00.57.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 00:57:23 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH 4/6] t-reftable-pq: make merged_iter_pqueue_check() callable by reference Date: Thu, 6 Jun 2024 13:10:48 +0530 Message-ID: <20240606075601.6989-5-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606075601.6989-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 merged_iter_pqueue_check() checks the validity of a priority queue represented by a merged_iter_pqueue struct by asserting the parent-child relation in the struct's heap. Explicity passing a struct to this function means a copy of the entire struct is created, which is inefficient. Make the function accept a pointer to the struct instead. This is safe to do since the function doesn't modify the struct in any way. Make the function parameter 'const' to assert immutability. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- t/unit-tests/t-reftable-pq.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c index 5c5a4ecdc5..30bf9cb492 100644 --- a/t/unit-tests/t-reftable-pq.c +++ b/t/unit-tests/t-reftable-pq.c @@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at #include "reftable/constants.h" #include "reftable/pq.h" -static void merged_iter_pqueue_check(struct merged_iter_pqueue pq) +static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) { - for (int i = 1; i < pq.len; i++) { + for (int i = 1; i < pq->len; i++) { int parent = (i - 1) / 2; - check(pq_less(&pq.heap[parent], &pq.heap[i])); + check(pq_less(&pq->heap[parent], &pq->heap[i])); } } @@ -40,13 +40,13 @@ static void test_pq(void) }; merged_iter_pqueue_add(&pq, &e); - merged_iter_pqueue_check(pq); + merged_iter_pqueue_check(&pq); i = (i * 7) % N; } while (i != 1); while (!merged_iter_pqueue_is_empty(pq)) { struct pq_entry e = merged_iter_pqueue_remove(&pq); - merged_iter_pqueue_check(pq); + merged_iter_pqueue_check(&pq); check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); if (last) From patchwork Thu Jun 6 07:40: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: 13687968 Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (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 8094613C839 for ; Thu, 6 Jun 2024 07:57:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660648; cv=none; b=Ymx+hvEC5OFhmQvkbMq30VurkLZrk/WLZRA1dgOK2/p7Zb9eu8H2VVloNe1uGEthEIaNq0kzUamZwuemEQJq2MQ1b+dOB+u8BmY6D+xWn101cZnvZrriKz5M0jy+BntQ3PXmKihklToij1ktXtkMbVGAj3exrWvaSmSi4gZtw6M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660648; c=relaxed/simple; bh=xXngqgh62RZ/0fbXn8qQInGgMtHxNDVVRPdYlYvxIAg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=MkkuXMf9wIKEneCCsHEhuabqbWLY2P7sG8L4lI0lMyToqwAuwQBVOZCkmgFikvkQKONDnQzIJ6JDHwziUwVSGdkkbnpuQU65/+c4a/9ucLE3td71Al5VNnDtA24s2kaCYRLE7JA9whQJ7vKGcFxxMqjhKew7V5rC3rwJ+76QIlA= 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=B19wqniO; arc=none smtp.client-ip=209.85.214.182 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="B19wqniO" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-1f6c7cded01so153015ad.0 for ; Thu, 06 Jun 2024 00:57:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717660647; x=1718265447; 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=WSqITE4lscpEpiyPN4IT3WNL1I4RvWn06OSc1XrW0Oc=; b=B19wqniO+aRRCIXj8FEACHMWfpB6obsHlCXLW5pftjeadI4IhD2XOAcyzGxzEgI0f0 Wru78Sl/0BBuaF7kTK1KbW539oN+Q795IezdeIHIrT2z8YTxR/ICNbynQUh8X+Nhu29u csQ8th3rn9d9Mab53Vd4eUdSjboWI/EvQ+snlJ++M0v1R7066mwAf5jfiNm4uSWq39YZ LBlwU/6b6qBq9LxqvwVk35KZmavt9aqrYggX2mQAgc1kQ/e1LX83k3SWj4haU+tdN69p eynRVqMIiAv4vExckZ5O2O+z6NPmjn6xzzITy54Dfx6FqW1K3z85qBkvvwIOspWrlKIS lgSg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717660647; x=1718265447; 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=WSqITE4lscpEpiyPN4IT3WNL1I4RvWn06OSc1XrW0Oc=; b=MAwN9e90k4o7QD75pKfqaHukBPFjXXqpSZh+aT+FrIegh33KX1NOPbllBE1Ue7ejBF zM/kgqcdWUTWZd1ZaI4nCn2f2PRV8QW7wM55TlkJRtMOvgy3wx10pWJEeFUSiVwK+9ap 1/VphCKj3nc8GEPtWI0QppSRtJt+8tR/xLi3K52r16AoZ5jHB163lVBZ98v/xmDHLqrn XBnAawbD/on2Gg2Qso0uORYA2B+5nhbLoWG1+cy8a2xGR6Ss9+Lrnba/QQG2MrpEOkzC ICpVqBPB4/AR1dbmXOv9Y8ANMHmOgJ0IvBOyfEFKOt9HXMsfExw7do/Gx5w5F0Ts1eW/ XQNw== X-Gm-Message-State: AOJu0YyfhgH2MWwtgGe05Kb1l2/MXHSrHG346EXr2nGFzgwKfSYujhrR uJEwyevUfuRAt4ST5+qsu56fJIxB8Hf2Cpl4zMK9a2yK+MC0n/VcBS68kKYw X-Google-Smtp-Source: AGHT+IGdBqAf1NET++Ib0lK/igG+qOa0PqPpq88cSELdstYJDDLuppfk/UEMqc7Fp5ojMC+lOkg1cg== X-Received: by 2002:a17:902:d511:b0:1f4:7713:8f6 with SMTP id d9443c01a7336-1f6a5a5a85fmr60960235ad.52.1717660646600; Thu, 06 Jun 2024 00:57:26 -0700 (PDT) Received: from Ubuntu.. ([27.61.69.112]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd7ed6b2sm8192415ad.246.2024.06.06.00.57.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 00:57:25 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH 5/6] t-reftable-pq: add test for index based comparison Date: Thu, 6 Jun 2024 13:10:49 +0530 Message-ID: <20240606075601.6989-6-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606075601.6989-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 When comparing two entries, the priority queue as defined by reftable/pq.{c, h} first compares the entries on the basis of their ref-record's keys. If the keys turn out to be equal, the comparison is then made on the basis of their update indices (which are never equal). In the current testing setup, only the case for comparison on the basis of ref-record's keys is exercised. Add a test for index-based comparison as well. Rename the existing test to reflect its nature of only testing record-based comparison. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- t/unit-tests/t-reftable-pq.c | 44 ++++++++++++++++++++++++++++++++++-- 1 file changed, 42 insertions(+), 2 deletions(-) diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c index 30bf9cb492..6f6bf58307 100644 --- a/t/unit-tests/t-reftable-pq.c +++ b/t/unit-tests/t-reftable-pq.c @@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) } } -static void test_pq(void) +static void test_pq_record(void) { struct merged_iter_pqueue pq = { 0 }; struct reftable_record recs[54]; @@ -59,9 +59,49 @@ static void test_pq(void) merged_iter_pqueue_release(&pq); } + +static void test_pq_index(void) +{ + struct merged_iter_pqueue pq = { 0 }; + struct reftable_record recs[14]; + char *last = NULL; + size_t N = ARRAY_SIZE(recs), i; + + for (i = 0; i < N; i++) { + reftable_record_init(&recs[i], BLOCK_TYPE_REF); + recs[i].u.ref.refname = xstrdup("refs/heads/master"); + } + + for (i = 0; i < N; i++) { + struct pq_entry e = { + .rec = &recs[i], + .index = i, + }; + + merged_iter_pqueue_add(&pq, &e); + merged_iter_pqueue_check(&pq); + } + + for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) { + struct pq_entry e = merged_iter_pqueue_remove(&pq); + merged_iter_pqueue_check(&pq); + + check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); + check_int(e.index, ==, i); + if (last) + check_str(last, e.rec->u.ref.refname); + last = e.rec->u.ref.refname; + } + + for (i = 0; i < N; i++) + reftable_record_release(&recs[i]); + merged_iter_pqueue_release(&pq); +} + int cmd_main(int argc, const char *argv[]) { - TEST(test_pq(), "pq works"); + TEST(test_pq_record(), "pq works with record-based comparison"); + TEST(test_pq_index(), "pq works with index-based comparison"); return test_done(); } From patchwork Thu Jun 6 07:40:50 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13687969 Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) (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 3797E13C9AF for ; Thu, 6 Jun 2024 07:57:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660651; cv=none; b=trfJtcK9mMIx5YVze7zT/AXdrUvEPQHx41AKjUrd/DQlZsX5AR2hI4TpJD8gumFX0d+fEuW2535wYlHIYTOpUkpLP5g01oHg0rzyHMmuSElr/l1SLLBJfICbb+qBn3R10Vm+tQqrFiALvt4FIqMrUXtM2oFiO8IKdnGFeTG7LGE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717660651; c=relaxed/simple; bh=+hmp3eR/vLYiNE0paTLneD48vYtJgu5AzfMwehpwaew=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=OV73CNZcLiPi57r65qLe5Vjyo5BWxmMeICTFktND3h5DOFJ63WLow+tKJtAMY+6G7ZLBF9ec3xEPteMUPeczra2N3qY6XTN/k9ROfp3jyDBYkiie27A0bDy0HMay7pgyHdjfTz4q79NiUyu87ENh36OoTklEgtYtKhSNEj4Jg3U= 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=UylL7NTb; arc=none smtp.client-ip=209.85.214.173 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="UylL7NTb" Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1f480624d0fso6178405ad.1 for ; Thu, 06 Jun 2024 00:57:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717660649; x=1718265449; 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=41P4+uR8hPaF8yTksDevGPEqaxe357aIDTa9EsYKjqs=; b=UylL7NTbvUYyCAYpuXRPQfRbVHxCOdi1zxGAxLNtKsOt0JWfpVnN7A2yE388MWdRj5 pH/KK+B3vYgidAH67WJCzfeVm3377FpkRIqDtCHQ925We4lIFnEGYe/ueeToMKn5R1+Q fQwEqm428d/ljXdQIVKDhr1NJf3a/sYxeFXiguTfL6wg7nwhoyiFHBzKP3+X/JFFE9CY ZWhqkNz9I4usJLlqpH9fLbWxbMCJBBrKKDDIPj9yfdpmjhqQdP5SnpDkt+S9VM8DokVH 8/gVPjWNo63HXjZssZby29mcDJwuqAep3Cn0rnYWA0jCVf1RAQ9Fk8ylZOjNgepjUiN2 q6ag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717660649; x=1718265449; 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=41P4+uR8hPaF8yTksDevGPEqaxe357aIDTa9EsYKjqs=; b=izPeF1qKCb2LVG5JqkUU4wHjCwBTxGTHZ9UCOixjbJYFvJszJRS7qkVfJthK6YutTf WDnqRGKJTSQzv/OLseDS7rR3hOMtCbueXP7PZ1fj1VNapkfhlXXnB2rejPeVXab5vkZ+ L2w6BN3AnHKfpG+uv15oPE1W5mq1AyVPvf/7z1YJ2dFJfUBFevrYcF50wPwx/AGlFWgK sn0ufO36Mrdnn6kssxxGlQXqfqFRpyZRrjddqMAvTJgPJxZq+dfp2PzBgPhZMPuqHfev 1HXuljW9FBAN0nhzJruYMOzOq5sZv4K6CAzZcwWC2u7ur2i3MtZIHKH7FQlZCx/SJJI3 RUGQ== X-Gm-Message-State: AOJu0YwLwksA+mpnfOg7h18CXiRw4zxwWHik6GxiYTO3CNrbA+om+VID Sy/IWdx6jmi6e8GWbG9OKZ4cOLmvQkUUcHwcYMnBQR1SP0UVKAcV9CXtHaFq X-Google-Smtp-Source: AGHT+IG8MX+rkbk/CCRwmCjyX/MGtbd4CvwRv8tdhS3kkggOZzHhgChpSny4tffv/aEX24D2gab0Cg== X-Received: by 2002:a17:902:e1c4:b0:1f4:a52a:dca4 with SMTP id d9443c01a7336-1f6a5a9ed36mr38280375ad.69.1717660649187; Thu, 06 Jun 2024 00:57:29 -0700 (PDT) Received: from Ubuntu.. ([27.61.69.112]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd7ed6b2sm8192415ad.246.2024.06.06.00.57.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 00:57:28 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH 6/6] t-reftable-pq: add tests for merged_iter_pqueue_top() Date: Thu, 6 Jun 2024 13:10:50 +0530 Message-ID: <20240606075601.6989-7-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606075601.6989-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 merged_iter_pqueue_top() as defined by reftable/pq.{c, h} returns the element at the top of a priority-queue's heap without removing it. Since there are no tests for this function in the existing setup, add tests for the same. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- t/unit-tests/t-reftable-pq.c | 49 +++++++++++++++++++++++++++++++++++- 1 file changed, 48 insertions(+), 1 deletion(-) diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c index 6f6bf58307..768337912f 100644 --- a/t/unit-tests/t-reftable-pq.c +++ b/t/unit-tests/t-reftable-pq.c @@ -18,6 +18,11 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq) } } +static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b) +{ + return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index); +} + static void test_pq_record(void) { struct merged_iter_pqueue pq = { 0 }; @@ -45,9 +50,11 @@ static void test_pq_record(void) } while (i != 1); while (!merged_iter_pqueue_is_empty(pq)) { + struct pq_entry top = merged_iter_pqueue_top(pq); struct pq_entry e = merged_iter_pqueue_remove(&pq); merged_iter_pqueue_check(&pq); + check(pq_entry_equal(&top, &e)); check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); if (last) check_int(strcmp(last, e.rec->u.ref.refname), <, 0); @@ -59,7 +66,6 @@ static void test_pq_record(void) merged_iter_pqueue_release(&pq); } - static void test_pq_index(void) { struct merged_iter_pqueue pq = { 0 }; @@ -83,9 +89,11 @@ static void test_pq_index(void) } for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) { + struct pq_entry top = merged_iter_pqueue_top(pq); struct pq_entry e = merged_iter_pqueue_remove(&pq); merged_iter_pqueue_check(&pq); + check(pq_entry_equal(&top, &e)); check(reftable_record_type(e.rec) == BLOCK_TYPE_REF); check_int(e.index, ==, i); if (last) @@ -98,10 +106,49 @@ static void test_pq_index(void) merged_iter_pqueue_release(&pq); } +static void test_merged_iter_pqueue_top(void) +{ + struct merged_iter_pqueue pq = { 0 }; + struct reftable_record recs[14]; + size_t N = ARRAY_SIZE(recs), i; + + for (i = 0; i < N; i++) { + reftable_record_init(&recs[i], BLOCK_TYPE_REF); + recs[i].u.ref.refname = xstrdup("refs/heads/master"); + } + + for (i = 0; i < N; i++) { + struct pq_entry e = { + .rec = &recs[i], + .index = i, + }; + + merged_iter_pqueue_add(&pq, &e); + merged_iter_pqueue_check(&pq); + } + + while (!merged_iter_pqueue_is_empty(pq)) { + struct pq_entry top = merged_iter_pqueue_top(pq); + struct pq_entry e = merged_iter_pqueue_remove(&pq); + + merged_iter_pqueue_check(&pq); + check(pq_entry_equal(&top, &e)); + for (i = 0; i < pq.len; i++) { + check(pq_less(&top, &pq.heap[i])); + check_int(top.index, >, i); + } + } + + for (i = 0; i < N; i++) + reftable_record_release(&recs[i]); + merged_iter_pqueue_release(&pq); +} + int cmd_main(int argc, const char *argv[]) { TEST(test_pq_record(), "pq works with record-based comparison"); TEST(test_pq_index(), "pq works with index-based comparison"); + TEST(test_merged_iter_pqueue_top(), "merged_iter_pqueue_top works"); return test_done(); }