commit ce00828c89df3d4c40de7d715b1a032eb03c525c
author David Benjamin <davidben@google.com> Sun Sep 23 16:48:24 2018 -0500
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> Tue Oct 02 00:02:19 2018 +0000
tree a7c5fbed347888639047def084b25e1810893b81
parent fac6fb99dac7e7a0d14d20a22d26fc4225d24d74

Test the binary search more aggressively.

https://boringssl-review.googlesource.com/c/boringssl/+/32115/ wasn't
worth it, but we may as well keep the test.  Also add a comment about
the asymptotics in case it ever comes up.

Change-Id: Ic4773106f1003adc56b4ce36520a18d3ac2d6f13
Reviewed-on: https://boringssl-review.googlesource.com/32284
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: Adam Langley <agl@google.com>

crypto/stack/stack.c

diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c
index fe456fc..93b9d1b 100644
--- a/crypto/stack/stack.c
+++ b/crypto/stack/stack.c
@@ -287,7 +287,10 @@
     return 0;
   }
   size_t idx = ((void **)r) - sk->data;
-  // This function always returns the first result.
+  // This function always returns the first result. Note this logic is, in the
+  // worst case, O(N) rather than O(log(N)). If this ever becomes a problem,
+  // restore https://boringssl-review.googlesource.com/c/boringssl/+/32115/
+  // which integrates the preference into the binary search.
   while (idx > 0) {
     const void *elem = sk->data[idx - 1];
     if (call_cmp_func(sk->comp, &p, &elem) != 0) {

crypto/stack/stack_test.cc

diff --git a/crypto/stack/stack_test.cc b/crypto/stack/stack_test.cc
index 58b4192..8b26971 100644
--- a/crypto/stack/stack_test.cc
+++ b/crypto/stack/stack_test.cc
@@ -349,3 +349,46 @@
   ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, two));
   EXPECT_EQ(0u, index);
 }
+
+// Exhaustively test the binary search.
+TEST(StackTest, BinarySearch) {
+  static const size_t kCount = 100;
+  for (size_t i = 0; i < kCount; i++) {
+    SCOPED_TRACE(i);
+    for (size_t j = i; j <= kCount; j++) {
+      SCOPED_TRACE(j);
+      // Make a stack where [0, i) are below, [i, j) match, and [j, kCount) are
+      // above.
+      bssl::UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
+      ASSERT_TRUE(sk);
+      for (size_t k = 0; k < i; k++) {
+        auto value = TEST_INT_new(-1);
+        ASSERT_TRUE(value);
+        ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
+      }
+      for (size_t k = i; k < j; k++) {
+        auto value = TEST_INT_new(0);
+        ASSERT_TRUE(value);
+        ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
+      }
+      for (size_t k = j; k < kCount; k++) {
+        auto value = TEST_INT_new(1);
+        ASSERT_TRUE(value);
+        ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
+      }
+      sk_TEST_INT_sort(sk.get());
+
+      auto key = TEST_INT_new(0);
+      ASSERT_TRUE(key);
+
+      size_t idx;
+      int found = sk_TEST_INT_find(sk.get(), &idx, key.get());
+      if (i == j) {
+        EXPECT_FALSE(found);
+      } else {
+        ASSERT_TRUE(found);
+        EXPECT_EQ(i, idx);
+      }
+    }
+  }
+}