Skip to contentSkip to conversation

sha1-array: add test-sha1-array and basic tests

PATCH In review René Scharfe 2 participants 3 messages Jun 15, 2016 Kbuild

lore
Share & tools
lore

René Scharfe

author
#0 lore raw

PATCH v2 1/2 sha1-array: add test-sha1-array and basic tests

Helped-by Jeff King <[email protected]>
Helped-by Eric Sunshine <[email protected]>
Signed-off-by Rene Scharfe <[email protected]>

---
Added a test for looking up a non-existing entry in an array that contains duplicates, as suggested by Jeff. Changed echo20() to add a space after the prefix as needed, as suggested by Eric.

 .gitignore            |  1 +
 Makefile              |  1 +
 t/t0064-sha1-array.sh | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++
 test-sha1-array.c     | 34 +++++++++++++++++++++++
 4 files changed, 110 insertions(+)
 create mode 100755 t/t0064-sha1-array.sh
 create mode 100644 test-sha1-array.c
.gitignore +1 -0
index 5bfb234..9ec40fa 100644
@@ -199,6 +199,7 @@
 /test-revision-walking
 /test-run-command
 /test-sha1
+/test-sha1-array
 /test-sigchain
 /test-string-list
 /test-subprocess
Makefile +1 -0
index f34a2d4..356feb5 100644
@@ -568,6 +568,7 @@ TEST_PROGRAMS_NEED_X += test-revision-walking
 TEST_PROGRAMS_NEED_X += test-run-command
 TEST_PROGRAMS_NEED_X += test-scrap-cache-tree
 TEST_PROGRAMS_NEED_X += test-sha1
+TEST_PROGRAMS_NEED_X += test-sha1-array
 TEST_PROGRAMS_NEED_X += test-sigchain
 TEST_PROGRAMS_NEED_X += test-string-list
 TEST_PROGRAMS_NEED_X += test-subprocess
t/t0064-sha1-array.sh new file +74 -0

74 lines not on this page · raw message

test-sha1-array.c new file +34 -0
new file mode 100644
index 0000000..ddc491e
@@ -0,0 +1,34 @@
+#include "cache.h"
+#include "sha1-array.h"
+
+static void print_sha1(const unsigned char sha1[20], void *data)
+{
+	puts(sha1_to_hex(sha1));
+}
+
+int main(int argc, char **argv)
+{
+	struct sha1_array array = SHA1_ARRAY_INIT;
+	struct strbuf line = STRBUF_INIT;
+
+	while (strbuf_getline(&line, stdin, '\n') != EOF) {
+		const char *arg;
+		unsigned char sha1[20];
+
+		if (skip_prefix(line.buf, "append ", &arg)) {
+			if (get_sha1_hex(arg, sha1))
+				die("not a hexadecimal SHA1: %s", arg);
+			sha1_array_append(&array, sha1);
+		} else if (skip_prefix(line.buf, "lookup ", &arg)) {
+			if (get_sha1_hex(arg, sha1))
+				die("not a hexadecimal SHA1: %s", arg);
+			printf("%d\n", sha1_array_lookup(&array, sha1));
+		} else if (!strcmp(line.buf, "clear"))
+			sha1_array_clear(&array);
+		else if (!strcmp(line.buf, "for_each_unique"))
+			sha1_array_for_each_unique(&array, print_sha1, NULL);
+		else
+			die("unknown command: %s", line.buf);
+	}
+	return 0;
+}
Signature · 1 line
2.1.2
author
#2 lore raw

PATCH v2 2/2 sha1-lookup: handle duplicates in sha1_pos()

In reply to René Scharfe

If the first 18 bytes of the SHA1's of all entries are the same then sha1_pos() dies and reports that the lower and upper limits of the binary search were the same that this wasn't supposed to happen. This is wrong because the remaining two bytes could still differ.

Furthermore: It wouldn't be a problem if they actually were the same, i.e. if all entries have the same SHA1. The code already handles duplicates just fine. Simply remove the erroneous check.

Signed-off-by Rene Scharfe <[email protected]>
---
 sha1-lookup.c         |  2 --
 t/t0064-sha1-array.sh | 20 ++++++++++++++++++++
 2 files changed, 20 insertions(+), 2 deletions(-)
sha1-lookup.c +0 -2
index 2dd8515..5f06921 100644
@@ -84,8 +84,6 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,
 				die("BUG: assertion failed in binary search");
 			}
 		}
-		if (18 <= ofs)
-			die("cannot happen -- lo and hi are identical");
 	}
 
 	do {
t/t0064-sha1-array.sh +20 -0
index 3f26e11..dbbe2e9 100755
@@ -71,4 +71,24 @@ test_expect_success 'lookup non-existing entry with duplicates' '
 	test "$n" -lt 0
 '
 
+test_expect_success 'lookup with almost duplicate values' '
+	{
+		echo "append 5555555555555555555555555555555555555555" &&
+		echo "append 555555555555555555555555555555555555555f" &&
+		echo20 lookup 55
+	} | test-sha1-array >actual &&
+	n=$(cat actual) &&
+	test "$n" -eq 0
+'
+
+test_expect_success 'lookup with single duplicate value' '
+	{
+		echo20 append 55 55 &&
+		echo20 lookup 55
+	} | test-sha1-array >actual &&
+	n=$(cat actual) &&
+	test "$n" -ge 0 &&
+	test "$n" -le 1
+'
+
 test_done
Signature · 1 line
2.1.2