git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: "Chris Poucet via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: Christophe Poucet <christophe.poucet@gmail.com>,
	Chris Poucet <poucet@google.com>
Subject: [PATCH 02/10] sha1-array: implement oid_array_readonly_contains
Date: Fri, 23 Sep 2022 18:55:16 +0000	[thread overview]
Message-ID: <84588312c1d4a62ff6c6211e85b4e58ab0563daa.1663959324.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.1356.git.1663959324.gitgitgadget@gmail.com>

From: Chris Poucet <poucet@google.com>

Implement a "readonly_contains" function for oid_array that won't
sort the array if it is unsorted. This can be used to test containment in
the rare situations where the array order matters.

The function has intentionally been given a name that is more cumbersome
than the "lookup" function, which is what most callers will will want
in most situations.

Signed-off-by: Chris Poucet <poucet@google.com>
---
 oid-array.c               | 12 ++++++++++++
 oid-array.h               |  7 +++++++
 t/helper/test-oid-array.c |  6 ++++++
 t/t0064-oid-array.sh      | 22 ++++++++++++++++++++++
 4 files changed, 47 insertions(+)

diff --git a/oid-array.c b/oid-array.c
index 73ba76e9e9a..1e12651d245 100644
--- a/oid-array.c
+++ b/oid-array.c
@@ -28,6 +28,18 @@ static const struct object_id *oid_access(size_t index, const void *table)
 	return &array[index];
 }
 
+int oid_array_readonly_contains(const struct oid_array *array,
+				const struct object_id* oid) {
+	int i;
+
+	if (array->sorted)
+		return oid_pos(oid, array->oid, array->nr, oid_access) >= 0;
+	for (i = 0; i < array->nr; i++)
+		if (oideq(&array->oid[i], oid))
+			return 1;
+	return 0;
+}
+
 int oid_array_lookup(struct oid_array *array, const struct object_id *oid)
 {
 	oid_array_sort(array);
diff --git a/oid-array.h b/oid-array.h
index f60f9af6741..e056eb61fa2 100644
--- a/oid-array.h
+++ b/oid-array.h
@@ -58,6 +58,13 @@ struct oid_array {
 
 #define OID_ARRAY_INIT { 0 }
 
+/**
+ * Sees whether an array contains an object ID. Optimized for when the array is
+ * sorted but does not require the array to be sorted.
+ */
+int oid_array_readonly_contains(const struct oid_array *array,
+				const struct object_id* oid);
+
 /**
  * Add an item to the set. The object ID will be placed at the end of the array
  * (but note that some operations below may lose this ordering).
diff --git a/t/helper/test-oid-array.c b/t/helper/test-oid-array.c
index d1324d086a2..0dbfc91ca8d 100644
--- a/t/helper/test-oid-array.c
+++ b/t/helper/test-oid-array.c
@@ -28,10 +28,16 @@ int cmd__oid_array(int argc, const char **argv)
 			if (get_oid_hex(arg, &oid))
 				die("not a hexadecimal oid: %s", arg);
 			printf("%d\n", oid_array_lookup(&array, &oid));
+		} else if (skip_prefix(line.buf, "readonly_contains ", &arg)) {
+			if (get_oid_hex(arg, &oid))
+				die("not a hexadecimal oid: %s", arg);
+			printf("%d\n", oid_array_readonly_contains(&array, &oid));
 		} else if (!strcmp(line.buf, "clear"))
 			oid_array_clear(&array);
 		else if (!strcmp(line.buf, "for_each_unique"))
 			oid_array_for_each_unique(&array, print_oid, NULL);
+		else if (!strcmp(line.buf, "for_each"))
+			oid_array_for_each(&array, print_oid, NULL);
 		else
 			die("unknown command: %s", line.buf);
 	}
diff --git a/t/t0064-oid-array.sh b/t/t0064-oid-array.sh
index 88c89e8f48a..aa677af132d 100755
--- a/t/t0064-oid-array.sh
+++ b/t/t0064-oid-array.sh
@@ -35,6 +35,28 @@ test_expect_success 'ordered enumeration with duplicate suppression' '
 	test_cmp expect actual
 '
 
+test_expect_success 'readonly_contains finds existing' '
+	echo 1 >expect &&
+	echoid "" 88 44 aa 55 >>expect &&
+	{
+		echoid append 88 44 aa 55 &&
+		echoid readonly_contains 55 &&
+		echo for_each
+	} | test-tool oid-array >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'readonly_contains non-existing query' '
+	echo 0 >expect &&
+	echoid "" 88 44 aa 55 >>expect &&
+	{
+		echoid append 88 44 aa 55 &&
+		echoid readonly_contains 33 &&
+		echo for_each
+	} | test-tool oid-array >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success 'lookup' '
 	{
 		echoid append 88 44 aa 55 &&
-- 
gitgitgadget


  parent reply	other threads:[~2022-09-23 18:56 UTC|newest]

Thread overview: 66+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-09-23 18:55 [PATCH 00/10] Add the Git Change command Christophe Poucet via GitGitGadget
2022-09-23 18:55 ` [PATCH 01/10] technical doc: add a design doc for the evolve command Stefan Xenos via GitGitGadget
2022-09-23 19:59   ` Jerry Zhang
2022-09-28 21:26   ` Junio C Hamano
2022-09-28 22:20   ` Junio C Hamano
2022-09-29  9:17     ` Phillip Wood
2022-09-29 19:57   ` Jonathan Tan
2022-09-23 18:55 ` Chris Poucet via GitGitGadget [this message]
2022-09-26 13:08   ` [PATCH 02/10] sha1-array: implement oid_array_readonly_contains Phillip Wood
2022-09-23 18:55 ` [PATCH 03/10] ref-filter: add the metas namespace to ref-filter Chris Poucet via GitGitGadget
2022-09-26 13:13   ` Phillip Wood
2022-10-04  9:50     ` Chris P
2022-09-23 18:55 ` [PATCH 04/10] evolve: add support for parsing metacommits Stefan Xenos via GitGitGadget
2022-09-26 13:27   ` Phillip Wood
2022-10-04 11:21     ` Chris P
2022-10-04 14:10       ` Phillip Wood
2022-09-23 18:55 ` [PATCH 05/10] evolve: add the change-table structure Stefan Xenos via GitGitGadget
2022-09-27 13:27   ` Phillip Wood
2022-09-27 13:50     ` Ævar Arnfjörð Bjarmason
2022-09-27 14:13       ` Phillip Wood
2022-09-27 15:28         ` Ævar Arnfjörð Bjarmason
2022-09-28 14:33           ` Phillip Wood
2022-09-28 15:14             ` Ævar Arnfjörð Bjarmason
2022-09-28 15:59             ` Junio C Hamano
2022-09-27 14:18     ` Phillip Wood
2022-10-04 14:48     ` Chris P
2022-09-23 18:55 ` [PATCH 06/10] evolve: add support for writing metacommits Stefan Xenos via GitGitGadget
2022-09-28 14:27   ` Phillip Wood
2022-10-05  9:40     ` Chris P
2022-10-05 11:09       ` Phillip Wood
2022-09-23 18:55 ` [PATCH 07/10] evolve: implement the git change command Stefan Xenos via GitGitGadget
2022-09-25  9:10   ` Phillip Wood
2022-09-26  8:23     ` Ævar Arnfjörð Bjarmason
2022-09-26  8:25   ` Ævar Arnfjörð Bjarmason
2022-10-05 12:30     ` Chris P
2022-09-23 18:55 ` [PATCH 08/10] evolve: add the git change list command Stefan Xenos via GitGitGadget
2022-09-23 18:55 ` [PATCH 09/10] evolve: add delete command Chris Poucet via GitGitGadget
2022-09-26  8:38   ` Ævar Arnfjörð Bjarmason
2022-09-26  9:10     ` Chris Poucet
2022-09-23 18:55 ` [PATCH 10/10] evolve: add documentation for `git change` Chris Poucet via GitGitGadget
2022-09-25  8:41   ` Phillip Wood
2022-09-25  8:39 ` [PATCH 00/10] Add the Git Change command Phillip Wood
2022-10-04  9:33   ` Chris P
2022-10-04 14:24 ` Phillip Wood
2022-10-04 15:19   ` Chris P
2022-10-04 15:55     ` Chris P
2022-10-04 16:00       ` Phillip Wood
2022-10-04 15:57     ` Phillip Wood
2022-10-05 14:59 ` [PATCH v2 00/10] RFC: Git Evolve / Change Christophe Poucet via GitGitGadget
2022-10-05 14:59   ` [PATCH v2 01/10] technical doc: add a design doc for the evolve command Stefan Xenos via GitGitGadget
2022-10-05 15:16     ` Chris Poucet
2022-10-06 20:53       ` Glen Choo
2022-10-10 19:35     ` Victoria Dye
2022-10-11  8:59       ` Phillip Wood
2022-10-11 16:59         ` Victoria Dye
2022-10-12 19:19           ` Phillip Wood
2022-10-05 14:59   ` [PATCH v2 02/10] sha1-array: implement oid_array_readonly_contains Chris Poucet via GitGitGadget
2022-10-05 14:59   ` [PATCH v2 03/10] ref-filter: add the metas namespace to ref-filter Chris Poucet via GitGitGadget
2022-10-05 14:59   ` [PATCH v2 04/10] evolve: add support for parsing metacommits Stefan Xenos via GitGitGadget
2022-10-05 14:59   ` [PATCH v2 05/10] evolve: add the change-table structure Stefan Xenos via GitGitGadget
2022-10-05 14:59   ` [PATCH v2 06/10] evolve: add support for writing metacommits Stefan Xenos via GitGitGadget
2022-10-05 14:59   ` [PATCH v2 07/10] evolve: implement the git change command Stefan Xenos via GitGitGadget
2022-10-05 14:59   ` [PATCH v2 08/10] evolve: add delete command Chris Poucet via GitGitGadget
2022-10-05 14:59   ` [PATCH v2 09/10] evolve: add documentation for `git change` Chris Poucet via GitGitGadget
2022-10-05 14:59   ` [PATCH v2 10/10] evolve: add tests for the git-change command Chris Poucet via GitGitGadget
2022-10-10  9:23   ` [PATCH v2 00/10] RFC: Git Evolve / Change Phillip Wood

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=84588312c1d4a62ff6c6211e85b4e58ab0563daa.1663959324.git.gitgitgadget@gmail.com \
    --to=gitgitgadget@gmail.com \
    --cc=christophe.poucet@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=poucet@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).