OLD | NEW |
(Empty) | |
| 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #include "chrome/browser/safe_browsing/prefix_set.h" |
| 6 |
| 7 #include <algorithm> |
| 8 |
| 9 #include "base/logging.h" |
| 10 #include "base/rand_util.h" |
| 11 #include "testing/gtest/include/gtest/gtest.h" |
| 12 |
| 13 namespace { |
| 14 |
| 15 SBPrefix GenPrefix() { |
| 16 return static_cast<SBPrefix>(base::RandUint64()); |
| 17 } |
| 18 |
| 19 // Test that a small sparse random input works. |
| 20 TEST(PrefixSetTest, Baseline) { |
| 21 std::vector<SBPrefix> prefixes; |
| 22 |
| 23 static const size_t kCount = 50000; |
| 24 |
| 25 for (size_t i = 0; i < kCount; ++i) { |
| 26 prefixes.push_back(GenPrefix()); |
| 27 } |
| 28 |
| 29 safe_browsing::PrefixSet prefix_set(prefixes); |
| 30 |
| 31 // Check that the set flags all of the inputs, and also check items |
| 32 // just above and below the inputs to make sure they aren't there. |
| 33 std::set<SBPrefix> check(prefixes.begin(), prefixes.end()); |
| 34 for (size_t i = 0; i < prefixes.size(); ++i) { |
| 35 EXPECT_TRUE(prefix_set.Exists(prefixes[i])); |
| 36 |
| 37 const SBPrefix left_sibling = prefixes[i] - 1; |
| 38 if (check.count(left_sibling) == 0) |
| 39 EXPECT_FALSE(prefix_set.Exists(left_sibling)); |
| 40 |
| 41 const SBPrefix right_sibling = prefixes[i] + 1; |
| 42 if (check.count(right_sibling) == 0) |
| 43 EXPECT_FALSE(prefix_set.Exists(right_sibling)); |
| 44 } |
| 45 } |
| 46 |
| 47 // Test that the empty set doesn't appear to have anything in it. |
| 48 TEST(PrefixSetTest, xEmpty) { |
| 49 std::vector<SBPrefix> prefixes; |
| 50 safe_browsing::PrefixSet prefix_set(prefixes); |
| 51 for (size_t i = 0; i < 500; ++i) { |
| 52 EXPECT_FALSE(prefix_set.Exists(GenPrefix())); |
| 53 } |
| 54 } |
| 55 |
| 56 // Use artificial inputs to test various edge cases in Exists(). |
| 57 // Items before the lowest item aren't present. Items after the |
| 58 // largest item aren't present. Create a sequence of items with |
| 59 // deltas above and below 2^16, and make sure they're all present. |
| 60 // Create a very long sequence with deltas below 2^16 to test crossing |
| 61 // |kMaxRun|. |
| 62 TEST(PrefixSetTest, EdgeCases) { |
| 63 std::vector<SBPrefix> prefixes; |
| 64 |
| 65 const SBPrefix kVeryPositive = 1000 * 1000 * 1000; |
| 66 const SBPrefix kVeryNegative = -kVeryPositive; |
| 67 |
| 68 // Put in a very negative prefix. |
| 69 SBPrefix prefix = kVeryNegative; |
| 70 prefixes.push_back(prefix); |
| 71 |
| 72 // Add a sequence with very large deltas. |
| 73 unsigned delta = 100 * 1000 * 1000; |
| 74 for (int i = 0; i < 10; ++i) { |
| 75 prefix += delta; |
| 76 prefixes.push_back(prefix); |
| 77 } |
| 78 |
| 79 // Add a sequence with deltas that start out smaller than the |
| 80 // maximum delta, and end up larger. Also include some duplicates. |
| 81 delta = 256 * 256 - 100; |
| 82 for (int i = 0; i < 200; ++i) { |
| 83 prefix += delta; |
| 84 prefixes.push_back(prefix); |
| 85 prefixes.push_back(prefix); |
| 86 delta++; |
| 87 } |
| 88 |
| 89 // Add a long sequence with deltas smaller than the maximum delta, |
| 90 // so a new index item will be injected. |
| 91 delta = 256 * 256 - 1; |
| 92 prefix = kVeryPositive - delta * 1000; |
| 93 prefixes.push_back(prefix); |
| 94 for (int i = 0; i < 1000; ++i) { |
| 95 prefix += delta; |
| 96 prefixes.push_back(prefix); |
| 97 delta--; |
| 98 } |
| 99 |
| 100 // Shuffle things up for giggles. |
| 101 std::random_shuffle(prefixes.begin(), prefixes.end()); |
| 102 |
| 103 safe_browsing::PrefixSet prefix_set(prefixes); |
| 104 |
| 105 // Items before and after the set are not present, and don't crash. |
| 106 EXPECT_FALSE(prefix_set.Exists(kVeryNegative - 100)); |
| 107 EXPECT_FALSE(prefix_set.Exists(kVeryPositive + 100)); |
| 108 |
| 109 // Check that the set correctly flags all of the inputs, and also |
| 110 // check items just above and below the inputs to make sure they |
| 111 // aren't present. |
| 112 for (size_t i = 0; i < prefixes.size(); ++i) { |
| 113 EXPECT_TRUE(prefix_set.Exists(prefixes[i])); |
| 114 |
| 115 EXPECT_FALSE(prefix_set.Exists(prefixes[i] - 1)); |
| 116 EXPECT_FALSE(prefix_set.Exists(prefixes[i] + 1)); |
| 117 } |
| 118 } |
| 119 |
| 120 } // namespace |
OLD | NEW |