PrefixSet as an alternate to BloomFilter for safe-browsing.

chrome/browser/safe_browsing/prefix_set_unittest.cc

Index: chrome/browser/safe_browsing/prefix_set_unittest.cc
diff --git a/chrome/browser/safe_browsing/prefix_set_unittest.cc b/chrome/browser/safe_browsing/prefix_set_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..9328b77ef2dca54dd4604a3f128f2c21ce0a2f40
--- /dev/null
+++ b/chrome/browser/safe_browsing/prefix_set_unittest.cc
@@ -0,0 +1,120 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "chrome/browser/safe_browsing/prefix_set.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+#include "base/rand_util.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace {
+
+SBPrefix GenPrefix() {
+  return static_cast<SBPrefix>(base::RandUint64());
+}
+
+// Test that a small sparse random input works.
+TEST(PrefixSetTest, Baseline) {
+  std::vector<SBPrefix> prefixes;
+
+  static const size_t kCount = 50000;
+
+  for (size_t i = 0; i < kCount; ++i) {
+    prefixes.push_back(GenPrefix());
+  }
+
+  safe_browsing::PrefixSet prefix_set(prefixes);
+
+  // Check that the set flags all of the inputs, and also check items
+  // just above and below the inputs to make sure they aren't there.
+  std::set<SBPrefix> check(prefixes.begin(), prefixes.end());
+  for (size_t i = 0; i < prefixes.size(); ++i) {
+    EXPECT_TRUE(prefix_set.Exists(prefixes[i]));
+
+    const SBPrefix left_sibling = prefixes[i] - 1;
+    if (check.count(left_sibling) == 0)
+      EXPECT_FALSE(prefix_set.Exists(left_sibling));
+
+    const SBPrefix right_sibling = prefixes[i] + 1;
+    if (check.count(right_sibling) == 0)
+      EXPECT_FALSE(prefix_set.Exists(right_sibling));
+  }
+}
+
+// Test that the empty set doesn't appear to have anything in it.
+TEST(PrefixSetTest, xEmpty) {
+  std::vector<SBPrefix> prefixes;
+  safe_browsing::PrefixSet prefix_set(prefixes);
+  for (size_t i = 0; i < 500; ++i) {
+    EXPECT_FALSE(prefix_set.Exists(GenPrefix()));
+  }
+}
+
+// Use artificial inputs to test various edge cases in Exists().
+// Items before the lowest item aren't present.  Items after the
+// largest item aren't present.  Create a sequence of items with
+// deltas above and below 2^16, and make sure they're all present.
+// Create a very long sequence with deltas below 2^16 to test crossing
+// |kMaxRun|.
+TEST(PrefixSetTest, EdgeCases) {
+  std::vector<SBPrefix> prefixes;
+
+  const SBPrefix kVeryPositive = 1000 * 1000 * 1000;
+  const SBPrefix kVeryNegative = -kVeryPositive;
+
+  // Put in a very negative prefix.
+  SBPrefix prefix = kVeryNegative;
+  prefixes.push_back(prefix);
+
+  // Add a sequence with very large deltas.
+  unsigned delta = 100 * 1000 * 1000;
+  for (int i = 0; i < 10; ++i) {
+    prefix += delta;
+    prefixes.push_back(prefix);
+  }
+
+  // Add a sequence with deltas that start out smaller than the
+  // maximum delta, and end up larger.  Also include some duplicates.
+  delta = 256 * 256 - 100;
+  for (int i = 0; i < 200; ++i) {
+    prefix += delta;
+    prefixes.push_back(prefix);
+    prefixes.push_back(prefix);
+    delta++;
+  }
+
+  // Add a long sequence with deltas smaller than the maximum delta,
+  // so a new index item will be injected.
+  delta = 256 * 256 - 1;
+  prefix = kVeryPositive - delta * 1000;
+  prefixes.push_back(prefix);
+  for (int i = 0; i < 1000; ++i) {
+    prefix += delta;
+    prefixes.push_back(prefix);
+    delta--;
+  }
+
+  // Shuffle things up for giggles.
+  std::random_shuffle(prefixes.begin(), prefixes.end());
+
+  safe_browsing::PrefixSet prefix_set(prefixes);
+
+  // Items before and after the set are not present, and don't crash.
+  EXPECT_FALSE(prefix_set.Exists(kVeryNegative - 100));
+  EXPECT_FALSE(prefix_set.Exists(kVeryPositive + 100));
+
+  // Check that the set correctly flags all of the inputs, and also
+  // check items just above and below the inputs to make sure they
+  // aren't present.
+  for (size_t i = 0; i < prefixes.size(); ++i) {
+    EXPECT_TRUE(prefix_set.Exists(prefixes[i]));
+
+    EXPECT_FALSE(prefix_set.Exists(prefixes[i] - 1));
+    EXPECT_FALSE(prefix_set.Exists(prefixes[i] + 1));
+  }
+}
+
+}  // namespace