{"thread":{"id":"37659","subject":"[PATCH v2 1/2] sha1-array: add test-sha1-array and basic tests","startedAt":"2014-10-01T15:00:33Z","lastAt":"2014-10-01T15:19:10Z","messageCount":3,"participants":["René Scharfe","Jeff King"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"250118","messageId":"542C1711.6080609@web.de","threadId":"37659","inReplyTo":null,"subject":"[PATCH v2 1/2] sha1-array: add test-sha1-array and basic tests","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-10-01T15:00:33Z","receivedAt":"2014-10-01T15:00:33Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Helped-by: Jeff King \nHelped-by: Eric Sunshine \nSigned-off-by: Rene Scharfe \n---\nAdded a test for looking up a non-existing entry in an array that\ncontains duplicates, as suggested by Jeff. Changed echo20() to add\na space after the prefix as needed, as suggested by Eric.\n\n .gitignore | 1 +\n Makefile | 1 +\n t/t0064-sha1-array.sh | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++\n test-sha1-array.c | 34 +++++++++++++++++++++++\n 4 files changed, 110 insertions(+)\n create mode 100755 t/t0064-sha1-array.sh\n create mode 100644 test-sha1-array.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 5bfb234..9ec40fa 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -199,6 +199,7 @@\n /test-revision-walking\n /test-run-command\n /test-sha1\n+/test-sha1-array\n /test-sigchain\n /test-string-list\n /test-subprocess\ndiff --git a/Makefile b/Makefile\nindex f34a2d4..356feb5 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -568,6 +568,7 @@ TEST_PROGRAMS_NEED_X += test-revision-walking\n TEST_PROGRAMS_NEED_X += test-run-command\n TEST_PROGRAMS_NEED_X += test-scrap-cache-tree\n TEST_PROGRAMS_NEED_X += test-sha1\n+TEST_PROGRAMS_NEED_X += test-sha1-array\n TEST_PROGRAMS_NEED_X += test-sigchain\n TEST_PROGRAMS_NEED_X += test-string-list\n TEST_PROGRAMS_NEED_X += test-subprocess\ndiff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh\nnew file mode 100755\nindex 0000000..3f26e11\n--- /dev/null\n+++ b/t/t0064-sha1-array.sh\n@@ -0,0 +1,74 @@\n+#!/bin/sh\n+\n+test_description='basic tests for the SHA1 array implementation'\n+. ./test-lib.sh\n+\n+echo20() {\n+\tprefix=\"${1:+$1 }\"\n+\tshift\n+\twhile test $# -gt 0\n+\tdo\n+\t\techo \"$prefix$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1\"\n+\t\tshift\n+\tdone\n+}\n+\n+test_expect_success 'ordered enumeration' '\n+\techo20 \"\" 44 55 88 aa >expect &&\n+\t{\n+\t\techo20 append 88 44 aa 55 &&\n+\t\techo for_each_unique\n+\t} | test-sha1-array >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'ordered enumeration with duplicate suppression' '\n+\techo20 \"\" 44 55 88 aa >expect &&\n+\t{\n+\t\techo20 append 88 44 aa 55 &&\n+\t\techo20 append 88 44 aa 55 &&\n+\t\techo for_each_unique\n+\t} | test-sha1-array >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'lookup' '\n+\t{\n+\t\techo20 append 88 44 aa 55 &&\n+\t\techo20 lookup 55\n+\t} | test-sha1-array >actual &&\n+\tn=$(cat actual) &&\n+\ttest \"$n\" -eq 1\n+'\n+\n+test_expect_success 'lookup non-existing entry' '\n+\t{\n+\t\techo20 append 88 44 aa 55 &&\n+\t\techo20 lookup 33\n+\t} | test-sha1-array >actual &&\n+\tn=$(cat actual) &&\n+\ttest \"$n\" -lt 0\n+'\n+\n+test_expect_success 'lookup with duplicates' '\n+\t{\n+\t\techo20 append 88 44 aa 55 &&\n+\t\techo20 append 88 44 aa 55 &&\n+\t\techo20 lookup 55\n+\t} | test-sha1-array >actual &&\n+\tn=$(cat actual) &&\n+\ttest \"$n\" -ge 2 &&\n+\ttest \"$n\" -le 3\n+'\n+\n+test_expect_success 'lookup non-existing entry with duplicates' '\n+\t{\n+\t\techo20 append 88 44 aa 55 &&\n+\t\techo20 append 88 44 aa 55 &&\n+\t\techo20 lookup 66\n+\t} | test-sha1-array >actual &&\n+\tn=$(cat actual) &&\n+\ttest \"$n\" -lt 0\n+'\n+\n+test_done\ndiff --git a/test-sha1-array.c b/test-sha1-array.c\nnew file mode 100644\nindex 0000000..ddc491e\n--- /dev/null\n+++ b/test-sha1-array.c\n@@ -0,0 +1,34 @@\n+#include \"cache.h\"\n+#include \"sha1-array.h\"\n+\n+static void print_sha1(const unsigned char sha1[20], void *data)\n+{\n+\tputs(sha1_to_hex(sha1));\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tstruct sha1_array array = SHA1_ARRAY_INIT;\n+\tstruct strbuf line = STRBUF_INIT;\n+\n+\twhile (strbuf_getline(&line, stdin, '\\n') != EOF) {\n+\t\tconst char *arg;\n+\t\tunsigned char sha1[20];\n+\n+\t\tif (skip_prefix(line.buf, \"append \", &arg)) {\n+\t\t\tif (get_sha1_hex(arg, sha1))\n+\t\t\t\tdie(\"not a hexadecimal SHA1: %s\", arg);\n+\t\t\tsha1_array_append(&array, sha1);\n+\t\t} else if (skip_prefix(line.buf, \"lookup \", &arg)) {\n+\t\t\tif (get_sha1_hex(arg, sha1))\n+\t\t\t\tdie(\"not a hexadecimal SHA1: %s\", arg);\n+\t\t\tprintf(\"%d\\n\", sha1_array_lookup(&array, sha1));\n+\t\t} else if (!strcmp(line.buf, \"clear\"))\n+\t\t\tsha1_array_clear(&array);\n+\t\telse if (!strcmp(line.buf, \"for_each_unique\"))\n+\t\t\tsha1_array_for_each_unique(&array, print_sha1, NULL);\n+\t\telse\n+\t\t\tdie(\"unknown command: %s\", line.buf);\n+\t}\n+\treturn 0;\n+}\n-- \n2.1.2\n"},{"id":"250119","messageId":"542C178D.6070302@web.de","threadId":"37659","inReplyTo":"542C1711.6080609@web.de","subject":"[PATCH v2 2/2] sha1-lookup: handle duplicates in sha1_pos()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2014-10-01T15:02:37Z","receivedAt":"2014-10-01T15:02:37Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"If the first 18 bytes of the SHA1's of all entries are the same then\nsha1_pos() dies and reports that the lower and upper limits of the\nbinary search were the same that this wasn't supposed to happen. This\nis wrong because the remaining two bytes could still differ.\n\nFurthermore: It wouldn't be a problem if they actually were the same,\ni.e. if all entries have the same SHA1. The code already handles\nduplicates just fine. Simply remove the erroneous check.\n\nSigned-off-by: Rene Scharfe \n---\n sha1-lookup.c | 2 --\n t/t0064-sha1-array.sh | 20 ++++++++++++++++++++\n 2 files changed, 20 insertions(+), 2 deletions(-)\n\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex 2dd8515..5f06921 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -84,8 +84,6 @@ int sha1_pos(const unsigned char *sha1, void *table, size_t nr,\n \t\t\t\tdie(\"BUG: assertion failed in binary search\");\n \t\t\t}\n \t\t}\n-\t\tif (18 <= ofs)\n-\t\t\tdie(\"cannot happen -- lo and hi are identical\");\n \t}\n \n \tdo {\ndiff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh\nindex 3f26e11..dbbe2e9 100755\n--- a/t/t0064-sha1-array.sh\n+++ b/t/t0064-sha1-array.sh\n@@ -71,4 +71,24 @@ test_expect_success 'lookup non-existing entry with duplicates' '\n \ttest \"$n\" -lt 0\n '\n \n+test_expect_success 'lookup with almost duplicate values' '\n+\t{\n+\t\techo \"append 5555555555555555555555555555555555555555\" &&\n+\t\techo \"append 555555555555555555555555555555555555555f\" &&\n+\t\techo20 lookup 55\n+\t} | test-sha1-array >actual &&\n+\tn=$(cat actual) &&\n+\ttest \"$n\" -eq 0\n+'\n+\n+test_expect_success 'lookup with single duplicate value' '\n+\t{\n+\t\techo20 append 55 55 &&\n+\t\techo20 lookup 55\n+\t} | test-sha1-array >actual &&\n+\tn=$(cat actual) &&\n+\ttest \"$n\" -ge 0 &&\n+\ttest \"$n\" -le 1\n+'\n+\n test_done\n-- \n2.1.2\n"},{"id":"250120","messageId":"20141001151910.GA20735@peff.net","threadId":"37659","inReplyTo":"542C1711.6080609@web.de","subject":"Re: [PATCH v2 1/2] sha1-array: add test-sha1-array and basic tests","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-10-01T15:19:10Z","receivedAt":"2014-10-01T15:19:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Oct 01, 2014 at 05:00:33PM +0200, René Scharfe wrote:\n\n> Helped-by: Jeff King \n> Helped-by: Eric Sunshine \n> Signed-off-by: Rene Scharfe \n> ---\n> Added a test for looking up a non-existing entry in an array that\n> contains duplicates, as suggested by Jeff. Changed echo20() to add\n> a space after the prefix as needed, as suggested by Eric.\n\nBoth patches look good to me.\n\n-Peff\n"}]}