prefix_set_unittest.cc revision dc0f95d653279beabeb9817299e2902918ba123e 
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
13namespace {
14
15SBPrefix GenPrefix() {
16  return static_cast<SBPrefix>(base::RandUint64());
17}
18
19// Test that a small sparse random input works.
20TEST(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  std::sort(prefixes.begin(), prefixes.end());
30  safe_browsing::PrefixSet prefix_set(prefixes);
31
32  // Check that |GetPrefixes()| returns exactly the same set of
33  // prefixes as was passed in.
34  std::set<SBPrefix> check(prefixes.begin(), prefixes.end());
35  std::vector<SBPrefix> prefixes_copy;
36  prefix_set.GetPrefixes(&prefixes_copy);
37  EXPECT_EQ(prefixes_copy.size(), check.size());
38  EXPECT_TRUE(std::equal(check.begin(), check.end(), prefixes_copy.begin()));
39
40  // Check that the set flags all of the inputs, and also check items
41  // just above and below the inputs to make sure they aren't there.
42  for (size_t i = 0; i < prefixes.size(); ++i) {
43    EXPECT_TRUE(prefix_set.Exists(prefixes[i]));
44
45    const SBPrefix left_sibling = prefixes[i] - 1;
46    if (check.count(left_sibling) == 0)
47      EXPECT_FALSE(prefix_set.Exists(left_sibling));
48
49    const SBPrefix right_sibling = prefixes[i] + 1;
50    if (check.count(right_sibling) == 0)
51      EXPECT_FALSE(prefix_set.Exists(right_sibling));
52  }
53}
54
55// Test that the empty set doesn't appear to have anything in it.
56TEST(PrefixSetTest, Empty) {
57  std::vector<SBPrefix> prefixes;
58  safe_browsing::PrefixSet prefix_set(prefixes);
59  for (size_t i = 0; i < 500; ++i) {
60    EXPECT_FALSE(prefix_set.Exists(GenPrefix()));
61  }
62}
63
64// Use artificial inputs to test various edge cases in Exists().
65// Items before the lowest item aren't present.  Items after the
66// largest item aren't present.  Create a sequence of items with
67// deltas above and below 2^16, and make sure they're all present.
68// Create a very long sequence with deltas below 2^16 to test crossing
69// |kMaxRun|.
70TEST(PrefixSetTest, EdgeCases) {
71  std::vector<SBPrefix> prefixes;
72
73  const SBPrefix kVeryPositive = 1000 * 1000 * 1000;
74  const SBPrefix kVeryNegative = -kVeryPositive;
75
76  // Put in a very negative prefix.
77  SBPrefix prefix = kVeryNegative;
78  prefixes.push_back(prefix);
79
80  // Add a sequence with very large deltas.
81  unsigned delta = 100 * 1000 * 1000;
82  for (int i = 0; i < 10; ++i) {
83    prefix += delta;
84    prefixes.push_back(prefix);
85  }
86
87  // Add a sequence with deltas that start out smaller than the
88  // maximum delta, and end up larger.  Also include some duplicates.
89  delta = 256 * 256 - 100;
90  for (int i = 0; i < 200; ++i) {
91    prefix += delta;
92    prefixes.push_back(prefix);
93    prefixes.push_back(prefix);
94    delta++;
95  }
96
97  // Add a long sequence with deltas smaller than the maximum delta,
98  // so a new index item will be injected.
99  delta = 256 * 256 - 1;
100  prefix = kVeryPositive - delta * 1000;
101  prefixes.push_back(prefix);
102  for (int i = 0; i < 1000; ++i) {
103    prefix += delta;
104    prefixes.push_back(prefix);
105    delta--;
106  }
107
108  std::sort(prefixes.begin(), prefixes.end());
109  safe_browsing::PrefixSet prefix_set(prefixes);
110
111  // Check that |GetPrefixes()| returns the same set of prefixes as
112  // was passed in.
113  std::vector<SBPrefix> prefixes_copy;
114  prefix_set.GetPrefixes(&prefixes_copy);
115  prefixes.erase(std::unique(prefixes.begin(), prefixes.end()), prefixes.end());
116  EXPECT_EQ(prefixes_copy.size(), prefixes.size());
117  EXPECT_TRUE(std::equal(prefixes.begin(), prefixes.end(),
118                         prefixes_copy.begin()));
119
120  // Items before and after the set are not present, and don't crash.
121  EXPECT_FALSE(prefix_set.Exists(kVeryNegative - 100));
122  EXPECT_FALSE(prefix_set.Exists(kVeryPositive + 100));
123
124  // Check that the set correctly flags all of the inputs, and also
125  // check items just above and below the inputs to make sure they
126  // aren't present.
127  for (size_t i = 0; i < prefixes.size(); ++i) {
128    EXPECT_TRUE(prefix_set.Exists(prefixes[i]));
129
130    EXPECT_FALSE(prefix_set.Exists(prefixes[i] - 1));
131    EXPECT_FALSE(prefix_set.Exists(prefixes[i] + 1));
132  }
133}
134
135}  // namespace
136