From patchwork Tue Jul 23 14:17:11 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13740131 Received: from mail-pl1-f180.google.com (mail-pl1-f180.google.com [209.85.214.180]) (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 7BE57154C0A for ; Tue, 23 Jul 2024 14:33:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745192; cv=none; b=W+q4x1zooRfnWbVui+8WJycXDnsyQ5uxpVx2d5Z2bMat0YR+pckFV/5SDMg4ALPkBQT/bYkS+Pt72Y2FQl+DeL54TxbFIGzxpplb6WTNvR+iH4AdsyiAr6XBInEOQwCFSmiGbihMgrDZ7FjHsrLMG9J7fVPwQcBmlaVSHxbT4Fk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745192; c=relaxed/simple; bh=hWXgMZ34iw7PGAEbfN9sMooQpaywW4W6Yp/28C6kGHE=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=cDOjao/02MKC74oXyVWjO8zJ/+nChEmW3KBST8Nal0v7naWUKXtG+D3qYGjWlQxz+rP6VkNfvpAxPMLW5XKKe74tFF12JG8yt2uCzZEWvaci24JZCmVZatO4YdESwAAz0jgjS1XH7rHhTA3z49g6QLpvTajCKv7P6Si8BiUAz3w= 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=WGvjjtqV; arc=none smtp.client-ip=209.85.214.180 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="WGvjjtqV" Received: by mail-pl1-f180.google.com with SMTP id d9443c01a7336-1fc47abc040so5928285ad.0 for ; Tue, 23 Jul 2024 07:33:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721745190; x=1722349990; 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=8NuaX3k1wXTe8+nrMWrHgqNmNsBhzatJwf158k3A+PY=; b=WGvjjtqV65qlIw0+86R1CBX6kd0gpS33qn6DKEolA4lwGLLSe/oheaZBOiVZUMsotD CdppaiwGPGE8A3+zoGHU6Q01WY0VqrjrccIk8Bi8Pkd6ZojyyozIq+rBWjlk+1PhsQOl oCKFOp/aEB+pH1unNSLe70vgj0xdDjdYxP2UBbseDF/s82S8gn4jLXwJ0rknmavUJVh0 U14A9ngpAHdl6lDOEXYrDpofe1jcMqzz7Nj7+QOuVGTGZlvHPKRy5MtvrJ7rV5i2ukYn GXuM5gL6yF7sCnAXYLxpBOc4I+UCmR2n/sTusgu6YBYdJqE0Ys2pXyX5LIV2CgVbXJ76 entw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721745190; x=1722349990; 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=8NuaX3k1wXTe8+nrMWrHgqNmNsBhzatJwf158k3A+PY=; b=cpvzZso3R5UYU5NDeEbNFTtTaSiL/p9tOUuq83nHU8K4xkgGGWQ1NPrPAM+64zYOA6 lMcH9PE95HfkVVo9or9oOkX2Z0i/5T1VsNzfpWO2CoVh9Y/cQiwpU+d9G4uf33Uyf3Ey yLsfEuUhRp0JMw3WJCD7/D/0SR4kngLmgR9F1RYvrE/JhSV9rCbzWVC0SoboYLvwxsfC tHy0KGXjcQuFSSAsiq25AOrwy46E5QEsLfQK5+avBvD7UEaLbVznPTkVIx5T9lUxYXPt oZIeHG5qvikdYaBR92InuwoTLEApoRpUqNilBwH1WJHYWSndwH5fPd+ayl5NA5rJYLLJ uTAQ== X-Gm-Message-State: AOJu0YwVQVVRnBVxwIaR+GAOCeLlTVqYf/Su3qwFcyOcdKLYE1USomn+ K5u9dh37xrBkheWEiCYkZBrQP5XTH72KCXqRxdMGdvwCM7+lSdBY/mW1L3xKFFQ= X-Google-Smtp-Source: AGHT+IFk1kDKajDEqsYZMZmpNu3yhu5sFyDFB/tC9ssUqCAfH9EeO2AneFa8XG+KFRGqeppiedL0iw== X-Received: by 2002:a17:903:191:b0:1fd:93d2:fb67 with SMTP id d9443c01a7336-1fd93d3012amr54678545ad.52.1721745190425; Tue, 23 Jul 2024 07:33:10 -0700 (PDT) Received: from Ubuntu.. ([223.176.63.81]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1fd6f256c09sm75301305ad.2.2024.07.23.07.33.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Jul 2024 07:33:10 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v5 1/7] reftable: remove unncessary curly braces in reftable/pq.c Date: Tue, 23 Jul 2024 19:47:11 +0530 Message-ID: <20240723143032.4261-2-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240723143032.4261-1-chandrapratap3519@gmail.com> References: <20240614095136.12052-1-chandrapratap3519@gmail.com> <20240723143032.4261-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 | 17 ++++------------- 1 file changed, 4 insertions(+), 13 deletions(-) diff --git a/reftable/pq.c b/reftable/pq.c index 7fb45d8c60..1a180c5fa6 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; } @@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry 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 Tue Jul 23 14:17:12 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13740132 Received: from mail-pl1-f169.google.com (mail-pl1-f169.google.com [209.85.214.169]) (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 2B6CE154C1E for ; Tue, 23 Jul 2024 14:33:14 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745195; cv=none; b=mc9xtI6NuuTQm6sm7zjmABijE5VhaU3v9uxvSQrRHSn/DQGp4RydbTuzraQ6/JhzCuzrXSFGKYEmYakimqpd+FwVVv5EEc6LSLTqGSR0HpNIgBLRnDjeAWlAz5XhBS1p0C06JM8gpmsJh8I+Vx9pSy+H7cFzzT+BDJjPw7FJFsQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745195; c=relaxed/simple; bh=7fe8b1Q8Pk/pmk9PSJwbpwxLZnOxvrkFTJnvVqloIGo=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=EyhtS6YytKdK3GObEofa0ABRCsi0xeswsRXHVJ3CD7upApet/bLq3LTIN+7Zgn5o/rnkjYpjf3ZFeNtiXqmkx3hct0B0UDHzg3rM7S42VZelSnIH5sDbQ48LQnAc0iM5Cd1VYEAM9/o/Vckgztc0yHEFtW/87Vzc+CWP3Ocym68= 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=C+EeCTDG; arc=none smtp.client-ip=209.85.214.169 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="C+EeCTDG" Received: by mail-pl1-f169.google.com with SMTP id d9443c01a7336-1fc587361b6so42733645ad.2 for ; Tue, 23 Jul 2024 07:33:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721745193; x=1722349993; 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=ylQ+xgFjJ2e2nKDrWOjwE4C50vKRhEy7qTSwCzeQ9JE=; b=C+EeCTDGQ/NPbUsaFHADVU0v7bUV+A7ojxXP8HHpVSpTYdnOcKoUaxEW/yXwogsL/Q FUYcU23kQPSEwK1hcfzrz9jbabp9e/3gLmEL4ZFeV4LTFsJFqByLx0WRjV+QVHa1Cy3P RWfP9J9d4wXrE/toDra2heWHG6T0ExKPEB59+tp2oyk5iz2irOXrRK1Z78DuLdmg/SCU F29jtcQvccw1ugIpnla/QcY/SK/i0t/3rBHMOn5UIJ7L8Rz4E5K7/w2R/Dk+NgZ9faW4 4eTNIMaK8OemDZx5LZ54pK3GyK51077NHmnrRHYhuqn3hb43ngfP8pDzCruhK/Nw0mvK u/8w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721745193; x=1722349993; 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=ylQ+xgFjJ2e2nKDrWOjwE4C50vKRhEy7qTSwCzeQ9JE=; b=cViVAXhThZt+h6AlqWKu8ZtgGVk1L5Z4eYDr+sKbVdicndPvl8np7tqFNcw6WRCcLS wU/ZatmcFgkCfnI+fo2mM9i0xOjiM9GMiholuclXO+8ku5oSi9K6k+uCy1kRcYzilQN5 WuMvzgNIg3bgis/TlH2Q/oWRAc7Zazpi6dvXQ7dVP0/wYeB5DcrnbXhPkGyirJ7QkpZB 053tSQwYJfFxDGjO5Pt2w8IOSvJ8i6Fpdxf8UkW3JJLefi0RS0u7wuZsblrlklWs90Hf UzWFlIZY4Lkm0+otUZ0AiwBRncey6Cl0ta8lBWsF3gskv5sh17bm1SMBQlQ/maewpY1P 7qUQ== X-Gm-Message-State: AOJu0YzqTFvRCt9fvgBo3rrPvvgciDZJEBfVwSemgqJjmbMR+ydri8If GD27FcQ+rZ9wvMexGNsuwjMzK1rIlPGHsa76XHdjlpL1NHBpm8WDQ93kzRo2lxs= X-Google-Smtp-Source: AGHT+IGpjsTS53f5y0dBNEp7Ibn7+9Rx9W20Yq9/cGb+Mt4nE5plpWtRMHbWvqDfjpkz1AwITDduZg== X-Received: by 2002:a17:903:32cf:b0:1fc:327a:1f48 with SMTP id d9443c01a7336-1fd74573663mr85086945ad.12.1721745193123; Tue, 23 Jul 2024 07:33:13 -0700 (PDT) Received: from Ubuntu.. ([223.176.63.81]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1fd6f256c09sm75301305ad.2.2024.07.23.07.33.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Jul 2024 07:33:12 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v5 2/7] reftable: change the type of array indices to 'size_t' in reftable/pq.c Date: Tue, 23 Jul 2024 19:47:12 +0530 Message-ID: <20240723143032.4261-3-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240723143032.4261-1-chandrapratap3519@gmail.com> References: <20240614095136.12052-1-chandrapratap3519@gmail.com> <20240723143032.4261-1-chandrapratap3519@gmail.com> Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 The variables 'i', 'j', 'k' and 'min' are used as indices for 'pq->heap', which is an array. Additionally, 'pq->len' is of type 'size_t' and is often used to assign values to these variables. Hence, change the type of these variables from 'int' to 'size_t'. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- reftable/pq.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/reftable/pq.c b/reftable/pq.c index 1a180c5fa6..2b5b7d1c0e 100644 --- a/reftable/pq.c +++ b/reftable/pq.c @@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b) struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq) { - int i = 0; + size_t i = 0; struct pq_entry e = pq->heap[0]; pq->heap[0] = pq->heap[pq->len - 1]; pq->len--; while (i < pq->len) { - int min = i; - int j = 2 * i + 1; - int k = 2 * i + 2; + size_t min = i; + size_t j = 2 * i + 1; + size_t k = 2 * i + 2; 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])) @@ -46,14 +46,14 @@ 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; + size_t 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; + size_t j = (i - 1) / 2; if (pq_less(&pq->heap[j], &pq->heap[i])) break; SWAP(pq->heap[j], pq->heap[i]); From patchwork Tue Jul 23 14:17:13 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13740133 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 984FD139D1A for ; Tue, 23 Jul 2024 14:33:17 +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=1721745199; cv=none; b=SbzUfGsUIeCIx7h9733mxjXuUS2GIXaC/C5qa2uADDbHXCvIYHEynn6eG+iEXWR9j5fLO7o3KvGNEU2TyiTaEAFet1SN3ZqRSGjH0MJFBt/+qLYht1equRXRWIXRgAzKlGHrj55FCQ4l6Lg5vkgDqfv7IZrnIQtRr8Cf7C8M9WU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745199; c=relaxed/simple; bh=3maJGZLQFy6uzTGwfimpdYlYH7mPuIRSv6/kGJ2VmP4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=UYftAFCdnhsJhp74qK7QyWOtiRDphcbiOUS9vj7t88wPs5e/kaQgcCFsb97Nbu/TMc/OQCufTNyP7tfCjVovPG6ehPu/jxrDpFL6Tom0Lyv3Ajv7VO5GRL1LG5Db2PydzQ/TmDp+fBx+IGxSXtT45rw8H7GwHyghiObC3sQxavY= 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=Aorehlh8; 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="Aorehlh8" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-1fc4fcbb131so6029745ad.3 for ; Tue, 23 Jul 2024 07:33:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721745196; x=1722349996; 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=gWFYUT0nNbkUmcoynWmQbbaLqTcO6uJXhtAvh7Z3QKs=; b=Aorehlh818ZYBpE7CPZ8DsY67g4A7/8Y8upcWUk1IDKPsD2nWG2il/cOm6F314MU+I mU1/73zqU3bgmnqdzyhvlfxai8vamaaTM5tOh5TAmV12UVdStV1gdjiVwM7jd1BSAInD 5XMiUyJCNu0QddXPzD425i7YbsC0dMkF6YxYCYDT9MPPuIeZpu8nMeTEcSJ6hNA4h2eB aoLfU3fDTWSEJqeVBTsqJttFsjkyN40WLz8cn2t8lN5+JbWWRf8X7dNftvrsi+FjRNCb vV6TgXsLJDNBvjXItPHzN8AloZZVXaS3UhzZhfoFIpzCrlptqYt3a5eRa8b0DpaBt0/4 GsgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721745196; x=1722349996; 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=gWFYUT0nNbkUmcoynWmQbbaLqTcO6uJXhtAvh7Z3QKs=; b=jr3uZx5WSo/vak0CdbIe8EAhLRckTrTg5ncMgUKJGnrfir3Pvin5oNpb58hsMPlfeP XMtV/CKkK1f1YQFXLKKmISR+q4FKyOuh/bEoFNEnJhSGH2v3wsn69MTJanHZjxQp5/7A M9ufYXukUBcfKg17dKmqfbI1otHE/k9KzbTLjcgdxIDvZBYOhK/pcyRwrTshZK7xxxKj 8PZwQlrWm1JntFobZCNJjVz5m83SADCIyUjqwAGZwweikqSnMYlyC351RNLYPq09ZO29 QG8UONjKSF6icalei0Hb2LksyfGxzBqUU4e+DSwPL0ybVyLV1+Uw3VbNqi2spSeBbZm/ EmkQ== X-Gm-Message-State: AOJu0YzPUkEhXhIM411VVKWXItjNsJvtog99Dij5GEiazbLgW3CORRmM 0uVfuq4FFR9jZH8wR8QvyD9bN1xILu+PLz4sL5O0sNZgAkxJZNyPhSUKlMnPpZE= X-Google-Smtp-Source: AGHT+IHVQgHK4nYSKAwTKFnE/j5GCdAfaSfwjZtmf32o5H2vwguHvcqnZ2Ucb4PEclIqmIHTXBj/gg== X-Received: by 2002:a17:902:ecd0:b0:1fc:3daa:52 with SMTP id d9443c01a7336-1fd74532fd5mr105513815ad.11.1721745196425; Tue, 23 Jul 2024 07:33:16 -0700 (PDT) Received: from Ubuntu.. ([223.176.63.81]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1fd6f256c09sm75301305ad.2.2024.07.23.07.33.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Jul 2024 07:33:15 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v5 3/7] t: move reftable/pq_test.c to the unit testing framework Date: Tue, 23 Jul 2024 19:47:13 +0530 Message-ID: <20240723143032.4261-4-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240723143032.4261-1-chandrapratap3519@gmail.com> References: <20240614095136.12052-1-chandrapratap3519@gmail.com> <20240723143032.4261-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, and renaming the tests to align with unit-tests' standards. Mentored-by: Patrick Steinhardt Mentored-by: Christian Couder Signed-off-by: Chandra Pratap --- Makefile | 2 +- reftable/reftable-tests.h | 1 - t/helper/test-reftable.c | 1 - .../pq_test.c => t/unit-tests/t-reftable-pq.c | 39 ++++++++----------- 4 files changed, 17 insertions(+), 26 deletions(-) rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (61%) diff --git a/Makefile b/Makefile index d6479092a0..1ee83e98dc 100644 --- a/Makefile +++ b/Makefile @@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-oidmap UNIT_TEST_PROGRAMS += t-oidtree UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics +UNIT_TEST_PROGRAMS += t-reftable-pq UNIT_TEST_PROGRAMS += t-reftable-record UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset @@ -2681,7 +2682,6 @@ REFTABLE_OBJS += reftable/writer.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/readwrite_test.o REFTABLE_TEST_OBJS += reftable/stack_test.o REFTABLE_TEST_OBJS += reftable/test_framework.o diff --git a/reftable/reftable-tests.h b/reftable/reftable-tests.h index 114cc3d053..67283faf06 100644 --- a/reftable/reftable-tests.h +++ b/reftable/reftable-tests.h @@ -12,7 +12,6 @@ license that can be found in the LICENSE file or at int basics_test_main(int argc, const char **argv); int block_test_main(int argc, const char **argv); int merged_test_main(int argc, const char **argv); -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); diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c index aa6538a8da..b808ad3e12 100644 --- a/t/helper/test-reftable.c +++ b/t/helper/test-reftable.c @@ -7,7 +7,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); 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 61% rename from reftable/pq_test.c rename to t/unit-tests/t-reftable-pq.c index b7d3c80cc7..a78aba9e71 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) +static void t_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(t_pq(), "pq works"); + + return test_done(); } From patchwork Tue Jul 23 14:17:14 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13740134 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 A6106139D1A for ; Tue, 23 Jul 2024 14:33:20 +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=1721745202; cv=none; b=ctjJw1Y7MGGAvjd16XNDXCxGT7ULhH9WPdr3ehHOqWdpzNpvfXnWN5wLmhP8RiDmppTVyEoZIS/0tsZyBjXWE9NXFAoQFO6Y8O7/mVof/K8nMc+68lASBN6FN4+cPz4n2y2h/H00kcj8fRPd57nMGkX5zo7tjGoaeEPqkqkspyM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745202; c=relaxed/simple; bh=/4OTsqp7/0XagHHoHG87U3Cq8P4orhehoCjdV+Ws0UE=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=PmQwoD+DHkU81hl4HEvu4qz36xxijCfF5myoNW/wRPj/bC3MRQXP+sawJPby+NFVBI2qlWWc4VECIrCVhCw08w0BJ2RVxyab9yH344/A5IYUfZgriRV4svL4pC6Wy6nhyzb3tf9MifBwOO9AqLdhqVY1Cy0beGIfXagyODBtfB0= 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=Me7Ui/Nv; 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="Me7Ui/Nv" Received: by mail-pl1-f177.google.com with SMTP id d9443c01a7336-1fb3b7d0d3aso4422225ad.2 for ; Tue, 23 Jul 2024 07:33:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721745199; x=1722349999; 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=0c6I6L2UI6Z07sVX/I4RZEpVOj4WiiO0O3zVyC+4ckQ=; b=Me7Ui/NvrQOqlIkdqJF+ZO2zRLKKIdCofOY+hj1MldVfjzP7xqkCROMBjBYhUHuYY/ 1ieWzIIdYS4ijDCIYTDz5nhqgdNv/TJw46taPuYXsvuunYGgZTz1CQDCdSVFqIHHE+Ee gqjw8RUbVQf087iPBFnufXercFx5BKq/UmIXgRcNrEtJMmaFjgtXC6YBlk2wutAeXHFF agP0MemQ0xr8+wVijrkvmiBjYaRyqUKyUn34ozJtjrGJI+Hg/OlEECeuCzQoriHSRLLX 4/ADkWpnXdqvuDpxG2/bH8uVmq1latiZzW1ublnf1r73MOBBWZN9EjT1vICzdkKP7Crn VcKA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721745199; x=1722349999; 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=0c6I6L2UI6Z07sVX/I4RZEpVOj4WiiO0O3zVyC+4ckQ=; b=Kyin+P0MbO1i/A3B1YyKCO0IORP80RK6RgNrzL408qx3LrfRP+YeQMmsUVRgqmfeyw Ol63XKUXleId+8Hw24IkiPB9yoHOd2mRBrztm3q2ZAe6QXe+rdQtIYJbQh1790Iib9p/ d7ipVx4Y3AtRx66MqlL9oH/6EmGKVsk4gGCh1OnR6A/kMzNiZQB2llV8zNLATTFgP9sa 3Z5qoXu3mSxC+OvkNBE8shoqzzCha8ANrltwe2u1e4ItM10pJTP1a484pquuDly6QA4a XCQFT2jE1lBXlnK5Ed/BxtReOhWX15MX1LYbeeCxc0lDFYjVVJGR5R9Cph+mnUXIEHT9 aaZA== X-Gm-Message-State: AOJu0Ywv8prcpQ9T70A9zoFMmS/Bvt+5K3t/lxbf06XQbx7zLHO0QZCL uZFssA6K5GEP7tNCh0ObjqhjiYc8Do9MgS24oGgcrD+XNoI9VMsfecoh7KwN1F0= X-Google-Smtp-Source: AGHT+IH3yDDroAWCO2nAn2bk/Xz30qlC/K7i0bmvzKJKdGa7i4LsCYjpCU2/5kn14jerTWm4UaKDhg== X-Received: by 2002:a17:903:2444:b0:1fd:69e0:a8e5 with SMTP id d9443c01a7336-1fd7462187amr109237625ad.41.1721745199437; Tue, 23 Jul 2024 07:33:19 -0700 (PDT) Received: from Ubuntu.. ([223.176.63.81]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1fd6f256c09sm75301305ad.2.2024.07.23.07.33.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Jul 2024 07:33:19 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v5 4/7] t-reftable-pq: make merged_iter_pqueue_check() static Date: Tue, 23 Jul 2024 19:47:14 +0530 Message-ID: <20240723143032.4261-5-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240723143032.4261-1-chandrapratap3519@gmail.com> References: <20240614095136.12052-1-chandrapratap3519@gmail.com> <20240723143032.4261-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 a78aba9e71..220e82be19 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 Tue Jul 23 14:17:15 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13740135 Received: from mail-pl1-f175.google.com (mail-pl1-f175.google.com [209.85.214.175]) (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 BFF7B15351B for ; Tue, 23 Jul 2024 14:33:23 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745205; cv=none; b=t3oFapFKJuK/00RuMb77qcmsFi4S06hRpk82YXUx+ll5kEqPVeCzM/qHrERZ60hHQU5RGtYjTx5UvWhuTzVu/zIBXa9FkADszoAX5Io3Ko5TG4WCF+PtDB10N3Gt0i+158w410svkwyMbBphYpYayZqLAKKf68Ym0uL0hEJ3QhM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745205; c=relaxed/simple; bh=lJ0cXIohnlHeDOyqRbU1Afyp/eEh9NcQnt1UB/p/M8I=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=IR4lRT3c6h4zdccx30ad7aE7Pm4f8RMtgFNQWfYUv/+FpUoCDapKzxkF07RJdmfXgY1Ek6e7KCjrCN/S5lX+3ukMIApCMq2nQtcB1kCf4U64os4vLIywIUJ3MdS9jNviLQJxVWV0T5eCYiQScrsxfC8MwRdJWTqjH8NoHQbFies= 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=PxlYofwP; arc=none smtp.client-ip=209.85.214.175 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="PxlYofwP" Received: by mail-pl1-f175.google.com with SMTP id d9443c01a7336-1fc6a017abdso26478095ad.0 for ; Tue, 23 Jul 2024 07:33:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721745203; x=1722350003; 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=C5Wp7fD3+IzmQYf4uzeVp+sx/sYc2G2N5WK5mg2pfmo=; b=PxlYofwPWsxVHF43BdMk+rWso/5z4AMXTEcPzJjtw7TysauFUBqFy/hCpaoIYOUpaf ZiDVLXVRvyPhJr2jnpqe9YOOCvsqIi+j4h4DLPP2rsSAMCJAXVr3T83UIsjqv/uc507E oD3c1pieVAgq0OTC7+q56pN+4GTxrh3P/djXlexkW6f1vMtNBiGRVB5y7oiQxLYDirRQ F7Ub+Ap2ncuSCB4sd7sWJMorQHWAc+YPwKsY4hmypzTbSi6PxK+glqUnczuTR6Fkj6l+ CqOzaS/yYOgPDX28aOLFb4P+1MAwyYkvgtulyArI/wjt6gNegs0mRY2xyqxQArDhXwsI 5Y0w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721745203; x=1722350003; 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=C5Wp7fD3+IzmQYf4uzeVp+sx/sYc2G2N5WK5mg2pfmo=; b=R2q41+ti2kKyj8Zo+6ZmuppZ9XP7eSKj/QtCfRaDLgSEbPHrP52sPvgv737xUSfOuT t9sCKi2x5qvcDzOdXy7CmwzupHoM2jCcyp+UaB+6INFIuQ1pEdXvLJOIVhaoavAv/+fA ZPYq+1CgPHr+qNsV/NT8hGXZCbBy22gDu1KIvKwH9lzESCCD3N8HePh/vFAc2YH/enwO yS2LtXeRP/U8f/Xczi1eYe7spxZXZZVtSJl4SCbvHssTNfV5kU9JFIBTHM8iLjlCxy7X AYS/Kd+wiimz+SjjwoCc59JTII1xmVSboK7M96wfGYxcQTdghWV0LzzBX98MMiph0SjQ LjQQ== X-Gm-Message-State: AOJu0YxFqpgZ2SA+sAhUNnceDJiP9kHbsz7sr3OhffkLMnmokUR/Zl2/ Sv4/kDAVpBXEk2WlG/0PI7vEFWrlHqR1W3XjjAyn01Fz5mYssxim2PsI8oUbXRQ= X-Google-Smtp-Source: AGHT+IHUHwY1yePncITm5Z/FaH+lMJ07ksAwnL4eWzNJW1JFpem8vzIzeoYiiNfy47wsa/m74ShfjQ== X-Received: by 2002:a17:902:ea0d:b0:1fb:1faa:96b7 with SMTP id d9443c01a7336-1fd74573a79mr79400725ad.9.1721745202619; Tue, 23 Jul 2024 07:33:22 -0700 (PDT) Received: from Ubuntu.. ([223.176.63.81]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1fd6f256c09sm75301305ad.2.2024.07.23.07.33.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Jul 2024 07:33:22 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v5 5/7] t-reftable-pq: make merged_iter_pqueue_check() callable by reference Date: Tue, 23 Jul 2024 19:47:15 +0530 Message-ID: <20240723143032.4261-6-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240723143032.4261-1-chandrapratap3519@gmail.com> References: <20240614095136.12052-1-chandrapratap3519@gmail.com> <20240723143032.4261-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 220e82be19..9230dd9b9e 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 t_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 Tue Jul 23 14:17:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13740136 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 BA16615351B for ; Tue, 23 Jul 2024 14:33: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=1721745208; cv=none; b=n1JGoeUhyptppjFoC8SPvzdR5BmSacbe0zNFtj0KZQHKp0b3QlurrL/rL9pnFvibOvQVQ1fCQRModv+/qHuqstOih+xkh54SWvvyOCY72w8EWYpyXvxYvSp+5eGW1M5muF7EIUKkqBGw/d9xJZ4/am+H/nyWX2QE9POhn47wvds= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745208; c=relaxed/simple; bh=R29cgDnjxTJhmO6Mv1rjS1yQqT5SrGF2kr1Lfatc/uc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=pD/cXzFM8SwGjnuj2pmWnFl4m6V4w7rKxQcGq/8egpuu/MOLoJ/VCSYOtxWvEE9sQXBdOBPPQm3+fiKE/oXzkxRn2NEmQtn1WT890A1Eeyq6hqAcTe+QCJ1I2lmLc8kRitR6iU/ZLWoaaFiGQpH1zkaXp2rtP+JhEufi7/S3eU4= 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=IQ366IiV; 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="IQ366IiV" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-1fc692abba4so7115285ad.2 for ; Tue, 23 Jul 2024 07:33:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721745206; x=1722350006; 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=d3WTk9ZUGTxWd0TmHrFF3eGJIwC1j72BS3dqj0Qqk6g=; b=IQ366IiVk3+s0GZYxU/Qz+coquDcq3uirR/Ndzqcwsc+z7Yw9BTOfhGtV8U7WICbTM b6H+bYSR7JG7SwPAeQ7qwQQ7KJ0TvavDhH2b5M+mOrb1nLbQlA8/SAPaNS/kM/sJa4Vt P1KmBMfPu+s28QrY6a9zrk6dJO9E4sF+x7JgDMTxbBXsp+0Ve1LFF99pSDfS1xyEEwkJ KWRmB2Plj0tV6lLhHc0XVhesCFZyEEBTFub9uhPQ9XLUwgLjHcrZJ+wuebEnT13BHwwz /06XlhbQOrmVwfykCaduGvgcbaaZJCQpjkKcyKXZBMnXAzZEZ1dOwqxiHoZWxZlMHjFv v56A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721745206; x=1722350006; 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=d3WTk9ZUGTxWd0TmHrFF3eGJIwC1j72BS3dqj0Qqk6g=; b=jXaNqau5H8X1kG9+X2xGsE7ER5KoIITsTS0FVDL67hklYJ2ZUyZMb/lIqRFWpJPmA3 yeL8mMttfA+5pGA8wY1J+SOcfgCsdpyoDeZQfAJNyARDO6bUF9BBfVjJ9/XiYY3tg3Qp INmLRIidGjhMPfk8zFXaQmoTVMkhwAasKNoe8JzzWD9KdNSwRM0LGbTB51+RtZhAK4/l VRztUg+n9ToKNn+kg97odtVzHoJaviGt/4rZ0r1QIDXfnYXO+zFCfC7kVgiC/24s6vJg NAy9Wxdi2VK8XEF7EbWnWBUCmqUCsgAoBunuODwGbRlwkxYvjTJFuIXtIKKgysd4TiOn s2OQ== X-Gm-Message-State: AOJu0Yzyn9zIHnOcoE3P2d1sq4LDmMO/L/d1cS6uBPnPh/l3xvfwMair mCUXuKypLoVE8lbIIFva1miWOwfBR/BBHFyLbCVa5XOQ3Zl2P0Bj+arC05+LZQI= X-Google-Smtp-Source: AGHT+IGPx2F1HxbXdI/yygMVq0/AOmiDL9ccWmwoeVosjByPawj0MOrkup2S4KOzToFgMp9fWzuPrw== X-Received: by 2002:a17:902:ec83:b0:1fd:acd1:b63a with SMTP id d9443c01a7336-1fdacd1b921mr40594495ad.50.1721745205668; Tue, 23 Jul 2024 07:33:25 -0700 (PDT) Received: from Ubuntu.. ([223.176.63.81]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1fd6f256c09sm75301305ad.2.2024.07.23.07.33.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Jul 2024 07:33:25 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v5 6/7] t-reftable-pq: add test for index based comparison Date: Tue, 23 Jul 2024 19:47:16 +0530 Message-ID: <20240723143032.4261-7-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240723143032.4261-1-chandrapratap3519@gmail.com> References: <20240614095136.12052-1-chandrapratap3519@gmail.com> <20240723143032.4261-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 9230dd9b9e..23c3f6888b 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 t_pq(void) +static void t_pq_record(void) { struct merged_iter_pqueue pq = { 0 }; struct reftable_record recs[54]; @@ -59,9 +59,48 @@ static void t_pq(void) merged_iter_pqueue_release(&pq); } +static void t_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(t_pq(), "pq works"); + TEST(t_pq_record(), "pq works with record-based comparison"); + TEST(t_pq_index(), "pq works with index-based comparison"); return test_done(); } From patchwork Tue Jul 23 14:17:17 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chandra Pratap X-Patchwork-Id: 13740137 Received: from mail-pl1-f174.google.com (mail-pl1-f174.google.com [209.85.214.174]) (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 BB3E615351B for ; Tue, 23 Jul 2024 14:33:29 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745211; cv=none; b=NZ65QlSOv34qTPUHSVj8AES8L3+5UZQtZN/rK6t1rmVmPoPFzIoBNASK7j1BTEu3WxDc0AEX6Re0jmkBD/XQEuYJciK+HVKxLdr2cwnNo2YrYr/GnvI5MGNlNsfAmXqauRHIOA/36zxzWLm4uC93S9sNqUfYzH6XVP2t9Om+4rs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1721745211; c=relaxed/simple; bh=MEGuSBUKeUzZpSZliSD/zkAMrhPHxdlWcalh5uHyUuc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=R04nZcjRYIL0aL0t5Xs+h3Ti94k7aIInoHClqoLzzkx+AORhvK+rqUbfroTD+Oj6BAAKSmxbpDbEXs6kvQftEauir5J7WWbIfTq/tbWnpUWK5pYxWX0KOgS4ECqBrB6eiwI3KmSRYR/+8xB/JhqC0jH4N+K/rXyA/UdLskhF0Oc= 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=idXV7BSB; arc=none smtp.client-ip=209.85.214.174 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="idXV7BSB" Received: by mail-pl1-f174.google.com with SMTP id d9443c01a7336-1fc4fcbb131so6031855ad.3 for ; Tue, 23 Jul 2024 07:33:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721745209; x=1722350009; 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=0zju0wvK7Njs4pPvHRfCkm9410+AWuCSnYT0D62v7q0=; b=idXV7BSBeb6LhGSSym7DL8R+orcSkM/nrlmTCkJRDcMc3eHjcpI4E4Qw+KG4zKcmit lVxpSt7jWOsNt8VVICXrY3W3jzHt0oetu+gFleN/4zR13rMPGzo8HTsavvp5hsaNQ0lc 1k2UdkguXOWxIPnNxu3bh7yHUiUr+ZTnyOmZnwDtHxJTZkiFwDqpreVZvFz4UrJIOtlW np7Wep55IfDOFG5RyHsnh8xC1R8IALGTbKYz+6V8Y1C5JN+vMioxm7hZBoWp/rrDkOKV nyv8wFvs6uM+qlocjF0XKYpVv74nr2/OFxCvhebPmZe2i2kjbhNUhw3+qse1KeRSopa2 IPlQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721745209; x=1722350009; 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=0zju0wvK7Njs4pPvHRfCkm9410+AWuCSnYT0D62v7q0=; b=SCbSus0mCsj0ToILxfResIHIiaivvXYhJkTnaobRuiVw/Sx3oxW1cCosT0wWYiWjkN uDOAiWz/krL8vN2+YAIsrhfTWPIkBMTfwoIAk+FohzoFUW2ZTZ08SxHigF3llnLteCgR 3BJqziaVU/2RaxKCB4gCCNfTCkAHU/ZNkuPxxYuwHP/XUPIhWI5U27KSE/p1P/EzwPOG 6ng2baddccrkVWsnlTVg6B0yWEctZRAdkNBFl9ReEGoHQcDaDIEx1ZhdDyk0Y6AWIH+Z UilUVsQ1XWuRngmyCS/SzAU47CZJXkzTbdZEeekNMGPKQgyVVRNsbXc4bWWZVk7KO+RX kMjQ== X-Gm-Message-State: AOJu0Yx6/vk4ekypZLccAII1hdzdcbE5imYkJAs/59eVDWa9t7RAagdx YN4dj9EFSqE6eqyM/QcJ1lU9b/Wzb/4VY9tdCRHRRSSqEjhAgBqIb58nhdfUL1w= X-Google-Smtp-Source: AGHT+IGHvRnSep0lx9VMzeRE/+PtDPSYlQscErNN9ugq1VrozK5bOA0QQ0k7bDn0PiyGUi+qEhxF/A== X-Received: by 2002:a17:902:e844:b0:1fc:544d:4e2b with SMTP id d9443c01a7336-1fd7457c94cmr89710865ad.33.1721745208653; Tue, 23 Jul 2024 07:33:28 -0700 (PDT) Received: from Ubuntu.. ([223.176.63.81]) by smtp.googlemail.com with ESMTPSA id d9443c01a7336-1fd6f256c09sm75301305ad.2.2024.07.23.07.33.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Jul 2024 07:33:28 -0700 (PDT) From: Chandra Pratap To: git@vger.kernel.org Cc: Chandra Pratap , Patrick Steinhardt , Christian Couder Subject: [PATCH v5 7/7] t-reftable-pq: add tests for merged_iter_pqueue_top() Date: Tue, 23 Jul 2024 19:47:17 +0530 Message-ID: <20240723143032.4261-8-chandrapratap3519@gmail.com> X-Mailer: git-send-email 2.45.GIT In-Reply-To: <20240723143032.4261-1-chandrapratap3519@gmail.com> References: <20240614095136.12052-1-chandrapratap3519@gmail.com> <20240723143032.4261-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 23c3f6888b..84b0a3b708 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 t_pq_record(void) { struct merged_iter_pqueue pq = { 0 }; @@ -45,9 +50,11 @@ static void t_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 t_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 t_pq_index(void) merged_iter_pqueue_release(&pq); } +static void t_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(t_pq_record(), "pq works with record-based comparison"); TEST(t_pq_index(), "pq works with index-based comparison"); + TEST(t_merged_iter_pqueue_top(), "merged_iter_pqueue_top works"); return test_done(); }