From patchwork Thu Jun 6 15:23:37 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13688701 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 7BE6319755C for ; Thu, 6 Jun 2024 15:48:17 +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=1717688898; cv=none; b=JK2rD10Ah0HeF2Ot6dNkF+YDEhy4AyS3ybvkgPWMTOQrTvuMiMWY06zmC7sf61U/8U2MSF7RhdbWhHzJI7PWTeeDZYgg4TWMvVGG0CvfTcFPvsBEDnV4/a2ASJIIdxB+b8Al/aVaDXY90LUEOrREXTSt+PoAOz8SHezIc92N8HY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717688898; c=relaxed/simple; bh=nxGHuT2wMkcElOFugJXOkTq8Kpf/nPoOV7viKGjvxBA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=sPVPcze7mU1OiqVkd8KGU5yIK+Fzil7j3iIzAcvxD/pgJMNWXwcM096GJGgZ7HynmDlU1BRqpvzFgjWBvPeeles9pnbrlkULsJhR+zXuHZmgPSD+3/HlU+WxGgLqfPvNM8v98c3IJNv5bIkU/BKQ9LRm0Yrz8vZA7opsbfDrA0k= 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=SLQb0lHJ; 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="SLQb0lHJ" Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1f6c7cded3fso4013445ad.0 for ; Thu, 06 Jun 2024 08:48:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717688896; x=1718293696; 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=SLQb0lHJ2M+6UZBVIjHHRORvgUjyLSyX1iJHiZXIld4DK7ZtDhJk3Il3uTYJyvrhAQ 3Rq1X/xTKP7bfMCu4pIoI+KjkxFm3vKWLyIPbL4Sl40l/fTqqsH0UDwgl5ChmCxglOw4 r/jzH3gnBSbSVZGsamx5R7C51aN8/oS0LRKX5lErZZj79Sugi5xOnxLFHqY3jt35OINY C3zX9ZnFrupzCOTFeeFD6aUaX/KO4ItIhWgiEPB++2gR8UoZL/BNyXGcSmpWpBtj2RLv 1zz5b36cUdB3goQWW1e4B2DYnkVjoe4JvsoMGTdkX1HRX+Rmow6rleNTLNXNP2ghgJKJ X1+Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717688896; x=1718293696; 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=qnJMO6G8gW8HbH6oZXrDp6IM/KaZH5lXkk8S2HeXIbI4+fBuIvhUo7tP0wKTDfKPBe x0QqNrl8v/Y8fQih4jJjjbCAY0dcTixex/zW4Wm6OatdYj/dgAYIT4wyCGXap/K3ixct f76PXG0BKhgaixWB9wgr1RhGjSk0uY6MxHFfTQ9WvGwXGgJulitZLlXc0EIgPPTMR+eG sV1o37XX91AKbPvJWzueg6YZZXA73B2LqAuW21oSAWMMmzN6kIdkVTJTZ17unV0Q1z8J 04hYh1gwqq7JAJx4yHr+7+OzgFsZeRrM2cDsMWbrRI3DYImaS9K4VFcLVFo6VwRorvKn KPTQ== X-Gm-Message-State: AOJu0YyChLRN99WG9UJr6AAbh5R2BT3Q4vP90VWqoQAwJjchdhzt9qFl Vi6mLGdti8LYkX4AkAu7TR0rlq0lKHOqzZOihYyK1ciWFXUUTOyLaPs5trkt0aM= X-Google-Smtp-Source: AGHT+IG9NH5wFMqNLu0LUcrZuDkn97Un3bm/+1vqSWH1dnlnWKhrX7pM9mKdvZoq/Cqz9jOshkGTyw== X-Received: by 2002:a17:902:ed4c:b0:1e7:eeb3:e295 with SMTP id d9443c01a7336-1f6a5aa5a58mr57463075ad.69.1717688896327; Thu, 06 Jun 2024 08:48:16 -0700 (PDT) Received: from Ubuntu.. ([223.176.20.76]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd76fa8fsm16937405ad.100.2024.06.06.08.48.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 08:48:15 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH v2 1/6] reftable: clean up reftable/pq.c Date: Thu, 6 Jun 2024 20:53:37 +0530 Message-ID: <20240606154712.15935-2-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606154712.15935-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> <20240606154712.15935-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 15:23:38 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13688702 Received: from mail-pl1-f181.google.com (mail-pl1-f181.google.com [209.85.214.181]) (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 5965F197A7A for ; Thu, 6 Jun 2024 15:48:23 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717688904; cv=none; b=Ir1UtJEq6RGb6NzW1hq+zAaap+oVaGEDoR5C3beq817KZ5xZCmClIUZzwPBQiqwoHfQ5W8EyED0205uzDfThmI8HlAiw/GQHu0/FppwKQd1dAuutNLFLwdYKOUurdBXlW06fbXAPsdWGFvWaoIu5JTxaLjMas9mwBRn33LUiFlY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717688904; c=relaxed/simple; bh=lDezlVhbx4xsaZZRDTavwaiORNa5S6p3fLN6vjDPF2g=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=MlWC3NX2gEG1J80TXvvkmGzhVK+nfu4Qsd1O1wtLpSnaeQg9rLoCA5ZVf6FarqpbcE73zjlCo0jNpoaVQGvCFEQY/ci2mGNjpVJoxMFkMbhS171c2nzK8d0O0yCQP5LddEn7aYvnFVyUTsCt171UmzL1U4UmyA1l7MVCTFK64eY= 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=NngYZKK1; arc=none smtp.client-ip=209.85.214.181 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="NngYZKK1" Received: by mail-pl1-f181.google.com with SMTP id d9443c01a7336-1f62217f806so10815195ad.2 for ; Thu, 06 Jun 2024 08:48:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717688902; x=1718293702; 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=QJRxUKvgzPgiuPQGG7wF/Iiv7ARwpsrNISAnWEDh/wg=; b=NngYZKK1zzgf6LcY6Zid1JYrwtWpiKZ6M47FWiRxVq7jy3B+zjxvq0s2MhK+yw188d IDYWyZFULqlZ0K6ZLn4VsRKlYzZAuaXd/Yuz5x8UMc3T2HFN3bAqVtFQYIzhhwjR63Tf oVqS6cyjy5t9VvtoX4JRzcj/dsF4p+vlzV4Sf4vWDPANO3IA0w8xctIaKLvnEnFvDfED OIG51l0OGfKhxh92mZfGxrU8HUoYwKQzAMJwXj7QZcOs/BxAuTet3F8vsDjE/h2unoVS n2vjW/wxKS3Py64MM0KGSiaFNmZxpxabJToo/hShz/17zIBQ8YAKGJn9plK3VaabkmaD iIFQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717688902; x=1718293702; 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=QJRxUKvgzPgiuPQGG7wF/Iiv7ARwpsrNISAnWEDh/wg=; b=YdYOHSS43TJGwsaS2W8koCJiajis4U3lwzhhZtaHa8yl4nee84cdvrdxMLyc6ICYHp nGfnyttvYkqCbmCZh3jIqkO9wyWVg7M46zGbPVSI903Ivb3h9bKES3TCykfBkihyGsL6 38Fnio0b2vtuxRClQTqIIkXZOmkGvul9y/IPb51HhlIw1OI8F4E5C6YbH/LjMdhigbWF 6J6m5ToedUM2nrNEBAzRKxWIZnM6wEYH7rsbcjDxJz9653Sa5E5mp+AnZz56r38EGAx3 11Lv/QTFWh0wl2e5N2GoCK+eM0Qd58xWVyPkn/0QfRaEv/3tXQheTVJST2caM7a/IzU4 2xdg== X-Gm-Message-State: AOJu0Yys5Vn2SGftISBYuOfur7nGDAQ/qxox0sPGHMgfjmo7ODJ4lLKq viqHJJHXBDviBC1pX7+8LTq6PzfTRxoO+lislbD3ZKkNI1HM1Yxurkx2piWJX/g= X-Google-Smtp-Source: AGHT+IEz3d6OSPqogRBcL/GJ90KT0/UbAdQUeQBfKxCNCRC97vqrYVYOKQgPM83WhxPhhZEkbFur3w== X-Received: by 2002:a17:902:d504:b0:1f6:80e2:e423 with SMTP id d9443c01a7336-1f6a5a849fcmr71247375ad.68.1717688902123; Thu, 06 Jun 2024 08:48:22 -0700 (PDT) Received: from Ubuntu.. ([223.176.20.76]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd76fa8fsm16937405ad.100.2024.06.06.08.48.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 08:48:21 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH v2 2/6] t: move reftable/pq_test.c to the unit testing framework Date: Thu, 6 Jun 2024 20:53:38 +0530 Message-ID: <20240606154712.15935-3-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606154712.15935-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> <20240606154712.15935-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 | 37 ++++++++----------- 3 files changed, 16 insertions(+), 24 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (62%) 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 62% rename from reftable/pq_test.c rename to t/unit-tests/t-reftable-pq.c index b7d3c80cc7..a47a9473f3 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++) { - int parent = (i - 1) / 2; - - EXPECT(pq_less(&pq.heap[parent], &pq.heap[i])); + for (size_t i = 1; i < pq.len; i++) { + size_t parent = (i - 1) / 2; + 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, "%02"PRIuMAX, (uintmax_t)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 15:23:39 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13688703 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) (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 162C7198823 for ; Thu, 6 Jun 2024 15:48:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717688908; cv=none; b=oo98pkxT8tzw71baW7diedTJbB7F0Qgrfpho/oGkUqm2KNoGt+5mOMN12Y+nr1NBs/wOVG2Ebi4tjnMsc7eGa0E7pp3aFVy+E+crY55SAyKp/es2HJ7F9rSi/PE/n2qEzhTT3oaqeIvjWs2UBPhDon7oPy4N1fitt6LHW4Dhlks= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717688908; c=relaxed/simple; bh=ZBvpDLNHNjoQCJ3AZJra3cFXcfo2DTAZf2kQPpx1UIA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=UnVXDCuFubz3fNVmk2etKhyEsKoYHcTlaqRjYdpQCDDQVZgKKRg1s6Km1C+yR/W/SKKOx+GBb9Pj3BltHVypZXdH1YzZYm8y2k4bNbvgc/AjXefecYSj1d+I1USmEKhOmpG+CvxxUbKmphBPqA2IfPDsS5ixXpLYN8wnDha4lPM= 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=A1+4JENy; arc=none smtp.client-ip=209.85.214.178 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="A1+4JENy" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-1f61f775738so10173265ad.2 for ; Thu, 06 Jun 2024 08:48:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717688906; x=1718293706; 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=gOyBXezJzIQcgORZHKSHMuaHcOuwfGm1OzY8yhzYeac=; b=A1+4JENyfBmJ6jP0R4DhMWIrZVDvVQ86d9r7l8y5slNbYbJKWeV5GvtSJ/n/6AIsGS U+SHBDkvhSoUTTnSOIVRDfRkuNQ/HQZa/eKsHF0xT4BHDnuOU6d2Ap7l1HKTYiPG1Jtc inE0tehWq6xXqs3dRWmoNS+tmfFahdO2dbXqcDQsJxmHjR5wvL9eQBJT5sRdN99iIPcz CiC4LATDLr1+HF5fkMapm5Eh0f0YbrAF0gLKsb25MzY6j35cuoI63Ffwq4ODXQAlfOG3 /j4htc2ON5Wwm0Tn9a2281swssWgHnZp2IK/CJOYA/xAOoYd9gjfkW0OgJF5GPxtTDKV 3wEQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717688906; x=1718293706; 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=gOyBXezJzIQcgORZHKSHMuaHcOuwfGm1OzY8yhzYeac=; b=tSCJiWpoGNmgg/AbVMQK8+3kXLrzLJnaoAEjVf3uQvnEjib8yY0Dh/BbGM5p9tL8qU 8d0JxWcXYan4oj1RNxQugjoldaYlWhDmFVzBQW2ouYR+ClmoMC7Pg+r//XBpd+VR2fFb MabMlFw/IpSkAWkEieHQ2DpTZVrxxzfz9DyT9ft0zkYz1pamxppc4rPgD3VK/69Ybq4P BleEEkh+Lz/y1j2+rL58Go4rZQsEmaxEQ0zXGwo6RKg9+fHS76DfEcP0QiCVekXLB34R MsGF8yC7tgSoT4KRcrBNczQF/45juxSLhUCj69bpifVVCKsDU7JeL9hyauJtYC70W6fO ijPQ== X-Gm-Message-State: AOJu0YwMs1vyPv5zwH9AR+tNpAGFMs1gLqMxV1jcOmk1Ge42azduJgnN 5p/WZt4ZMgVkUCkUjfCn/lYayNGMs8xn1xtFxIll7NQgWgQTe9jADePLkOWnWX0= X-Google-Smtp-Source: AGHT+IGNs4YQTCghFZB2ssijBIxoPRcQgNe3c4nF7Td+bxg4SiCAPuZGsLV8BoeaJFEJ2/nczIPgqg== X-Received: by 2002:a17:902:f606:b0:1f4:64d9:5cfd with SMTP id d9443c01a7336-1f6a5a5ca36mr72854655ad.42.1717688906115; Thu, 06 Jun 2024 08:48:26 -0700 (PDT) Received: from Ubuntu.. ([223.176.20.76]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd76fa8fsm16937405ad.100.2024.06.06.08.48.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 08:48:25 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH v2 3/6] t-reftable-pq: make merged_iter_pqueue_check() static Date: Thu, 6 Jun 2024 20:53:39 +0530 Message-ID: <20240606154712.15935-4-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606154712.15935-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> <20240606154712.15935-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 a47a9473f3..7d151f8582 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 (size_t i = 1; i < pq.len; i++) { size_t parent = (i - 1) / 2; From patchwork Thu Jun 6 15:23:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13688704 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 52574197A7A for ; Thu, 6 Jun 2024 15:48:30 +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=1717688911; cv=none; b=QYB5GBGIXJvRP/FiU8v6qiLR+i22kBvsCx5b2t0iMI6h1604AY8N1V0mzc3FXdb97ZVtoCUK9ZPeTH6dkU5srYpDafCuzdQJb0wlBOiJMxPUZIq1RT2C+D0A3uwkqvnuTvOHTkPZNEHpUq2qUuxK2+8K2VWfWflr6b05qGQg1jM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717688911; c=relaxed/simple; bh=L2kOQvVmitR9fKv557cUouCHnCFAU5dqKoO9TVT+NHE=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=tF1jyHAl/RBTrGO+qaRpz8GTbcDpY4brKGwOVtWpMeI93tMDQwFRvVVFw5c5VaIoqrm9CMd6cYCmze4OVl3kCI9jexG8H0d9KJklKjIj+q2dS09QicnbZxJUPLE6eJIsz6RH/kUIYJS0LTHlfJLCyZswWIwask88hIdNYzOhk5U= 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=RkNTYpOA; 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="RkNTYpOA" Received: by mail-pl1-f177.google.com with SMTP id d9443c01a7336-1f62217f806so10816655ad.2 for ; Thu, 06 Jun 2024 08:48:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717688909; x=1718293709; 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=w84840wpWTiEFCwuNJLf+jbnu/yNvhoCiinN3sTzrPY=; b=RkNTYpOAFHo8MWAuNPSHr76BFCANBrqkwDuhZc4snoHKWHIQUfhMBaImeAXTWZw1ME N+pppJlUSTsxsOZe1fZN8zNaZw0aG5KwSKusDespN9z1K81l6QewHy9D2a1kBNYuUtkm 9KipYw7bru9RDhKTL7j20au9z1SS/+TSi1mmiShAARXwCBEUYlmnZQsQ47hUI+1vBUaX MnNXCbVfaL2Zh9YvIPM5MUFqi+6SUxuTXQB2YLzTe3mjYjo3DJLz+rO2aE50dUQDm89Y klDyRmFBmtgGb19nuIwo9awpwgKL59Dlp3tcUXnlFK5kyqNJg3hKCWplszfwtgSQUGXn tDcw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717688909; x=1718293709; 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=w84840wpWTiEFCwuNJLf+jbnu/yNvhoCiinN3sTzrPY=; b=juh7N4zuHDbGLpoED1R9uN+N6npJmeREi1wLd/PPRWLzC37ovOqxnpH8qPe2w19Llr DHHtLSgrpskWgpptOu3flOSstW1TlGFKVimKuXj6Yyi5ZLUtTJqV0GML5qHOCoNP60i1 IdpfEF3fuPRDNGPdKlGFOmVKEC6Y2qd9c6qxM+U6tMA8ExmGMgaA39pbXNWiwX/dOvya fbb56RTsfxqachsCZlcoiGMukWMH9dgsGqbvDCtu+OaN0abEKfG22scbhG7ztz8Tv4HB BCQwyB2CSl0ue2wQK3MBy/skRVl1jac5FcBMwMD+50kHNR4E11uHb2D0a/76nHf2nUpz J4fA== X-Gm-Message-State: AOJu0YwEHU/BsfKMnE5Zm1FjR2/+J5r6CJec2etXmteHV/K4ycMQTc18 4HwObhMbIf/ZGgjWt3HbR6mUZuxWxem20Buh8q++q49iOJxdxPQqMIZEN0EiEn8= X-Google-Smtp-Source: AGHT+IFL/4CiGdq6dX0VgIvFqeQx3fZoRa3DhehUhjSoUOEEOx13nO41B7B2lkss7Lux7h3qTUZ7qA== X-Received: by 2002:a17:902:ce91:b0:1f4:b9d3:adce with SMTP id d9443c01a7336-1f6d02dd8cbmr180425ad.27.1717688909292; Thu, 06 Jun 2024 08:48:29 -0700 (PDT) Received: from Ubuntu.. ([223.176.20.76]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd76fa8fsm16937405ad.100.2024.06.06.08.48.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 08:48:29 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH v2 4/6] t-reftable-pq: make merged_iter_pqueue_check() callable by reference Date: Thu, 6 Jun 2024 20:53:40 +0530 Message-ID: <20240606154712.15935-5-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606154712.15935-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> <20240606154712.15935-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 7d151f8582..774c4194e5 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 (size_t i = 1; i < pq.len; i++) { + for (size_t i = 1; i < pq->len; i++) { size_t 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 15:23:41 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13688705 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 10BC8197525 for ; Thu, 6 Jun 2024 15:48:34 +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=1717688916; cv=none; b=doAYJ40eTJB/TUC41nAM2lEidbq9946isZ99cN8vC9X6JIFWbtFg8lPqtT49Ig2qLN4AbUhPtrMMOnHE7WqySKhNqoTjWI/MPXqHqsae5MaodakH+W21OIxk5jzyr0R8sysqCvXeTz0VHpK5kGhPnZsBnK+TvmzJzDzSJvvfsjk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717688916; c=relaxed/simple; bh=eziVbiL0LUGaEg6d4C+WXfmKilNXwroxU5hjbTdR3E8=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=DbmoH2JNYspmejkTD+FuojvRIgjkquTkBx2yY9oElgI9JCX73wfQBS5ZOHeGpaOAgqLLOmsxpR0O0iFP7ihblyOnJ4HfqE3+I54FcUxBQ9dIacDr/TEtqfLJPc70wBCXcLQwFPQ5bvGJAfIQus3pXLlXeaJDOnyZ6pLSSovF9OE= 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=ZsTTGoQW; 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="ZsTTGoQW" Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1f6342c5faaso10359095ad.2 for ; Thu, 06 Jun 2024 08:48:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717688914; x=1718293714; 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=2A1jaJbvylBYtbwBpSmIIsBRdMautt6SxxGgpkJHVVg=; b=ZsTTGoQWfrSRT2mF+zmH9Q7hFg9JSUk6haDHOBJmxcYqfHzNK1WAWNMrTzztVdOYH1 ie9+u4zx4jlvnl4NEoy1TQRa8SGQ1hURjxltYXg2SAC8LgPkfrHBfzwpty+HZ1eE/jTu z6KoInJA2ifpfLbNPmX0pQALztCUtUNf1YIz9hbrY2PQl0bhDurJTnfipfCykf+zWflV cMsa/pFWux1hSpB+Q4hTvZC7UGcgPSyumbP5CyTO7FkLtWRzHu4ZfkMdliYUUJwwI1hc c2rqUSamb77StgwwiZpP/3fS0z0ZfYKV9AilmHjK0xj/hncSqHMEviC3JNKrDFCkv4MO J9Qg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717688914; x=1718293714; 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=2A1jaJbvylBYtbwBpSmIIsBRdMautt6SxxGgpkJHVVg=; b=YY5/1p/WGVracE9WHTOV32PE5poKpJJBCZu5US7FBk0hUtKixnmDTa08wfe9oFfx2d upwOy0YsxczJcI/rISOV13gcEc+lrjmZOdKc+m2mllKRtEXT1SudKIlbvPr/RsVJjfw0 ssUhulXBh1IjOgICXcP55knmFsixE7rWmcF8PpfRaDU95WqWxzVPxwIVPykd6zVJ5Yj6 2mKXwyvwxrDJvbRMiQe4mkhW3gDmDOUvFW+QRW6rPqvb8GzG1/pCD7bKa8zB79rGrn6s lq5pYXCTGoZuDD3oo/C5fqz9sm/RKrhxII8gUHSEFND6vrAddUOE454uNQNvzSo/F+et seyg== X-Gm-Message-State: AOJu0YwILRX5BGhbd4IsdtQbTBbPzrxzRWaPKUmGG05FCFuFbZjBOJXk N/22aU+mdGD2bKjj7eSAnnrbdCA/oVTRqij5BxU9Qb88ffIzVfV/kxcRuSYbPdM= X-Google-Smtp-Source: AGHT+IE31tjwmsC2VifZpmR73enGL2sJLlxtEppqYwpOEAr1TSOLC51+tJ6jsIgbHuCtauNTHz4FEg== X-Received: by 2002:a17:902:e883:b0:1f3:2e5d:902d with SMTP id d9443c01a7336-1f6d02d2274mr98875ad.4.1717688913980; Thu, 06 Jun 2024 08:48:33 -0700 (PDT) Received: from Ubuntu.. ([223.176.20.76]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd76fa8fsm16937405ad.100.2024.06.06.08.48.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 08:48:33 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH v2 5/6] t-reftable-pq: add test for index based comparison Date: Thu, 6 Jun 2024 20:53:41 +0530 Message-ID: <20240606154712.15935-6-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606154712.15935-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> <20240606154712.15935-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 | 43 ++++++++++++++++++++++++++++++++++-- 1 file changed, 41 insertions(+), 2 deletions(-) diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c index 774c4194e5..e114a8cb0f 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,48 @@ 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 15:23:42 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13688706 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) (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 2740D198E78 for ; Thu, 6 Jun 2024 15:48:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717688919; cv=none; b=oDOaJn/+P+W01k/1bS4QmCxs088EEa5A3M7owWoC/G/L0saz/wdOqT6akbXqvKEE1RDc8QhwGW1+ij6i67yl1iMN5eLEqfWYp1mmdQlifjk1XuZ7jLchVxbX/9VKQEa9ymmlyA0kLf0RclPuqHhDOuQZ1fRSrLyW3i1VKSwIEU8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717688919; c=relaxed/simple; bh=M3NmnPJY+UewlcIXn2gNvLekbAtEtQCb1WnANKxJPUA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=sefUT69GZ/CsFmODN//VJE9v4YVy+xDqmbnU0h8T0hKsk0eS8+69XfxMzVQtny/9MdhOvTJRAuY9dXXrDSkE18MOjpiBpf7hNHOZajivnH3KEqsubYbzz7GNeBLGKZARFBb0br1epAwc3gfm9Y6U8dGe3NeSc3dDhB8lAwVQ37Q= 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=A6hpE2eI; arc=none smtp.client-ip=209.85.214.178 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="A6hpE2eI" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-1f61f775738so10175265ad.2 for ; Thu, 06 Jun 2024 08:48:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1717688917; x=1718293717; 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=RTbXFHflckCzDT75U/jzwQ6rjk8DD6Zkca0vVmURxp8=; b=A6hpE2eIxAbX3vjMnlLbQunqaUNNouUys78NIedeQ8GHn+vE84Qqf19csbcClI6P8o 0OZSp9Fm/0NHn4KHQBQeyJWzJDeKH7Rz8Qyppn5pAm00rL4CXdfqie0Ta79D5hrDQEJO YrCW1ych7fe+IGHqXk8SMuoTbde6OA3Ry+QO8PlTOPT3q3BhQAySYEHkCUn0iHFYGw14 humo3CPnr13czTaBx9XKLirE9I5cQo6wJ2oIU8fnDNdlGNGf08fCNghbxYCT1ILHmIpM U1ATOYpBlojF9+/SfluVlqo2Xiw0bmwVERcIu8Pr2LGE6dhvdR/HdkZJaFLK81O4WE+l UcaA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1717688917; x=1718293717; 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=RTbXFHflckCzDT75U/jzwQ6rjk8DD6Zkca0vVmURxp8=; b=E0R/yl4Ba3gXV2tyPGoCXm8CSdljK0V7YEGc/MqIaFxav9NLD/RlreTzrYZxvM13Ln qpdBQGDvYb/2ce/VBsY50n9qxH6Pjh02IBulpVTPKQXi/n1H4OO96KG+zqCL0JIMipdX VAgZHV0jXBP2i90zRNx1/Ek/WrpvFwdrNflU0NK4HFwn795MqG4sbfN+4ZkoDrzn2G5I SM43jOJpWKaFXaeQUzZZVOVHe5ogT9CYnYQWHEkVGI+zch8PlBqtamgVKEQI+FxqMg6a fuRRs3RSq8j4dRmPSG0nyELiM6d753iVEDTZEY+nysSdrW3Uph7QdF2gUAEyslUalXyL kOjA== X-Gm-Message-State: AOJu0YyJPmyA5zG9vi5K3bjhrD5zteWlmbtKmnqPCgG3SR+Etnc4NL6b 2WtBUTQouwvPsL27gToGh524ze+9vDsoJb7cBCt8OH9UX/IZ37sDHKNDm1R3L+c= X-Google-Smtp-Source: AGHT+IGvZ4kFPZxjVIquFtVUyJtHQqRPvb3rx76lURFoYRGjuMWKjGwP+/vHnzzgB+r5gCDe5mx12Q== X-Received: by 2002:a17:903:32c7:b0:1f6:7e02:6ae0 with SMTP id d9443c01a7336-1f6a5a5c816mr70655765ad.44.1717688917198; Thu, 06 Jun 2024 08:48:37 -0700 (PDT) Received: from Ubuntu.. ([223.176.20.76]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1f6bd76fa8fsm16937405ad.100.2024.06.06.08.48.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 06 Jun 2024 08:48:36 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [GSoC][PATCH v2 6/6] t-reftable-pq: add tests for merged_iter_pqueue_top() Date: Thu, 6 Jun 2024 20:53:42 +0530 Message-ID: <20240606154712.15935-7-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.2.404.g9eaef5822c In-Reply-To: <20240606154712.15935-1-chandrapratap3519@gmail.com> References: <20240606075601.6989-1-chandrapratap3519@gmail.com> <20240606154712.15935-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, 49 insertions(+) diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c index e114a8cb0f..0e93cc97b1 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); @@ -82,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) @@ -97,10 +106,50 @@ 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); + } + + 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_equal(top.rec, &recs[i], GIT_SHA1_RAWSZ)); + for (size_t j = 0; i < pq.len; j++) { + check(pq_less(&top, &pq.heap[j])); + check_int(top.index, >, j); + } + } + + 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(); }