Merge branch 'rs/sha1-array-test'

* rs/sha1-array-test:
sha1-lookup: handle duplicates in sha1_pos()
sha1-array: add test-sha1-array and basic tests

diff --git a/.gitignore b/.gitignore
index 5bfb234591a63446d9fccf7665e442f02d1c76b5..9ec40fa9fbc645532c9bc36b65521e6771d14324 100644 (file)
--- a/.gitignore
+++ b/.gitignore
@@ -199,6 +199,7 @@
 /test-revision-walking
 /test-run-command
 /test-sha1
+/test-sha1-array
 /test-sigchain
 /test-string-list
 /test-subprocess

diff --git a/Makefile b/Makefile
index f34a2d4cb82a907c2a1a9a8d760cfd3a1788f6e3..356feb5c86023d00a41ac8bca7d44f9779c39ad0 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -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

diff --git a/sha1-lookup.c b/sha1-lookup.c
index 2dd851598a9d1444fe479d149ee3c2cb93e8cba9..5f069214d9060da8ceb001e6c037607c1d0096bf 100644 (file)
--- a/sha1-lookup.c
+++ b/sha1-lookup.c
@@ -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 {

diff --git a/t/t0064-sha1-array.sh b/t/t0064-sha1-array.sh
new file mode 100755 (executable)
index 0000000..50b31ff
--- /dev/null
+++ b/t/t0064-sha1-array.sh
@@ -0,0 +1,94 @@
+#!/bin/sh
+
+test_description='basic tests for the SHA1 array implementation'
+. ./test-lib.sh
+
+echo20 () {
+       prefix="${1:+$1 }"
+       shift
+       while test $# -gt 0
+       do
+               echo "$prefix$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1$1"
+               shift
+       done
+}
+
+test_expect_success 'ordered enumeration' '
+       echo20 "" 44 55 88 aa >expect &&
+       {
+               echo20 append 88 44 aa 55 &&
+               echo for_each_unique
+       } | test-sha1-array >actual &&
+       test_cmp expect actual
+'
+
+test_expect_success 'ordered enumeration with duplicate suppression' '
+       echo20 "" 44 55 88 aa >expect &&
+       {
+               echo20 append 88 44 aa 55 &&
+               echo20 append 88 44 aa 55 &&
+               echo for_each_unique
+       } | test-sha1-array >actual &&
+       test_cmp expect actual
+'
+
+test_expect_success 'lookup' '
+       {
+               echo20 append 88 44 aa 55 &&
+               echo20 lookup 55
+       } | test-sha1-array >actual &&
+       n=$(cat actual) &&
+       test "$n" -eq 1
+'
+
+test_expect_success 'lookup non-existing entry' '
+       {
+               echo20 append 88 44 aa 55 &&
+               echo20 lookup 33
+       } | test-sha1-array >actual &&
+       n=$(cat actual) &&
+       test "$n" -lt 0
+'
+
+test_expect_success 'lookup with duplicates' '
+       {
+               echo20 append 88 44 aa 55 &&
+               echo20 append 88 44 aa 55 &&
+               echo20 lookup 55
+       } | test-sha1-array >actual &&
+       n=$(cat actual) &&
+       test "$n" -ge 2 &&
+       test "$n" -le 3
+'
+
+test_expect_success 'lookup non-existing entry with duplicates' '
+       {
+               echo20 append 88 44 aa 55 &&
+               echo20 append 88 44 aa 55 &&
+               echo20 lookup 66
+       } | test-sha1-array >actual &&
+       n=$(cat actual) &&
+       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

diff --git a/test-sha1-array.c b/test-sha1-array.c
new file mode 100644 (file)
index 0000000..ddc491e
--- /dev/null
+++ b/test-sha1-array.c
@@ -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;
+}