git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: sxenos@google.com
To: git@vger.kernel.org
Cc: Stefan Xenos <sxenos@gmail.com>
Subject: [PATCH 2/8] evolve: Implement oid_array_contains_nondestructive
Date: Mon, 21 Jan 2019 14:32:10 -0800	[thread overview]
Message-ID: <20190121223216.66659-2-sxenos@google.com> (raw)
In-Reply-To: <20190121223216.66659-1-sxenos@google.com>

From: Stefan Xenos <sxenos@gmail.com>

Implement a "contains_nondestructive" 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.
---
 sha1-array.c               | 15 +++++++++++++++
 sha1-array.h               |  2 ++
 t/helper/test-sha1-array.c |  6 ++++++
 t/t0064-sha1-array.sh      | 22 ++++++++++++++++++++++
 4 files changed, 45 insertions(+)

diff --git a/sha1-array.c b/sha1-array.c
index b94e0ec0f5..466937d73d 100644
--- a/sha1-array.c
+++ b/sha1-array.c
@@ -26,6 +26,21 @@ static const unsigned char *sha1_access(size_t index, void *table)
 	return array[index].hash;
 }
 
+int oid_array_contains_nondestructive(const struct oid_array* array,
+	const struct object_id* oid)
+{
+	int i;
+	if (array->sorted) {
+		return sha1_pos(oid->hash, array->oid, array->nr, sha1_access) >= 0;
+	}
+	for (i = 0; i < array->nr; i++) {
+		if (hashcmp(array->oid[i].hash, oid->hash) == 0) {
+			return 1;
+		}
+	}
+	return 0;
+}
+
 int oid_array_lookup(struct oid_array *array, const struct object_id *oid)
 {
 	if (!array->sorted)
diff --git a/sha1-array.h b/sha1-array.h
index 232bf95017..a887e7e4eb 100644
--- a/sha1-array.h
+++ b/sha1-array.h
@@ -13,6 +13,8 @@ struct oid_array {
 void oid_array_append(struct oid_array *array, const struct object_id *oid);
 int oid_array_lookup(struct oid_array *array, const struct object_id *oid);
 void oid_array_clear(struct oid_array *array);
+int oid_array_contains_nondestructive(const struct oid_array* array,
+	const struct object_id* oid);
 
 typedef int (*for_each_oid_fn)(const struct object_id *oid,
 			       void *data);
diff --git a/t/helper/test-sha1-array.c b/t/helper/test-sha1-array.c
index ad5e69f9d3..127a4c0b51 100644
--- a/t/helper/test-sha1-array.c
+++ b/t/helper/test-sha1-array.c
@@ -25,10 +25,16 @@ int cmd__sha1_array(int argc, const char **argv)
 			if (get_oid_hex(arg, &oid))
 				die("not a hexadecimal SHA1: %s", arg);
 			printf("%d\n", oid_array_lookup(&array, &oid));
+		} else if (skip_prefix(line.buf, "contains_nondestructive ", &arg)) {
+			if (get_oid_hex(arg, &oid))
+				die("not a hexadecimal SHA1: %s", arg);
+			printf("%d\n", oid_array_contains_nondestructive(&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-sha1-array.sh b/t/t0064-sha1-array.sh
index 5dda570b9a..05512b0461 100755
--- a/t/t0064-sha1-array.sh
+++ b/t/t0064-sha1-array.sh
@@ -32,6 +32,28 @@ test_expect_success 'ordered enumeration with duplicate suppression' '
 	test_cmp expect actual
 '
 
+test_expect_success 'contains_nondestructive finds existing' '
+	echo 1 > expect &&
+	echoid "" 88 44 aa 55 >> expect &&
+	{
+		echoid append 88 44 aa 55 &&
+		echoid contains_nondestructive 55 &&
+		echo for_each
+	} | test-tool sha1-array >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'contains_nondestructive non-existing query' '
+	echo 0 > expect &&
+	echoid "" 88 44 aa 55 >> expect &&
+	{
+		echoid append 88 44 aa 55 &&
+		echoid contains_nondestructive 33 &&
+		echo for_each
+	} | test-tool sha1-array >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success 'lookup' '
 	{
 		echoid append 88 44 aa 55 &&
-- 
2.20.1.321.g9e740568ce-goog


  reply	other threads:[~2019-01-21 22:32 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-01-21 22:32 [PATCH 1/8] technical doc: add a design doc for the evolve command sxenos
2019-01-21 22:32 ` sxenos [this message]
2019-01-22 19:51   ` [PATCH 2/8] evolve: Implement oid_array_contains_nondestructive Stefan Beller
2019-01-27 19:08     ` Stefan Xenos
2019-01-21 22:32 ` [PATCH 3/8] evlove: Add the metas namespace to ref-filter sxenos
2019-01-21 22:32 ` [PATCH 4/8] evolve: Add support for parsing metacommits sxenos
2019-01-21 22:32 ` [PATCH 5/8] evolve: Add the change-table structure sxenos
2019-01-21 22:32 ` [PATCH 6/8] evolve: Add support for writing metacommits sxenos
2019-01-21 22:32 ` [PATCH 7/8] evolve: Implement the git change update command sxenos
2019-01-21 22:32 ` [PATCH 8/8] evolve: Add the git change list command sxenos

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=20190121223216.66659-2-sxenos@google.com \
    --to=sxenos@google.com \
    --cc=git@vger.kernel.org \
    --cc=sxenos@gmail.com \
    --subject='Re: [PATCH 2/8] evolve: Implement oid_array_contains_nondestructive' \
    /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

Code repositories for project(s) associated with this 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).