Explicit PrefixSet test prefix distribution.

chrome/browser/safe_browsing/prefix_set_unittest.cc

 // Copyright (c) 2012 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 <iterator>
 
 #include "base/file_util.h"
@@ skipping 11 matching lines @@
  protected:
   // Constants for the v1 format.
   static const size_t kMagicOffset = 0 * sizeof(uint32);
   static const size_t kVersionOffset = 1 * sizeof(uint32);
   static const size_t kIndexSizeOffset = 2 * sizeof(uint32);
   static const size_t kDeltasSizeOffset = 3 * sizeof(uint32);
   static const size_t kPayloadOffset = 4 * sizeof(uint32);
 
   // Generate a set of random prefixes to share between tests.  For
   // most tests this generation was a large fraction of the test time.
+  //
+  // The set should contain sparse areas where adjacent items are more
+  // than 2^16 apart, and dense areas where adjacent items are less
+  // than 2^16 apart.
   static void SetUpTestCase() {
-    for (size_t i = 0; i < 50000; ++i) {
+    // Distribute clusters of prefixes.
+    for (size_t i = 0; i < 250; ++i) {
+      // Unsigned for overflow characteristics.
+      const uint32 base = static_cast<uint32>(base::RandUint64());
+      for (size_t j = 0; j < 10; ++j) {
+        const uint32 delta = static_cast<uint32>(base::RandUint64() & 0xFFFF);
+        const SBPrefix prefix = static_cast<SBPrefix>(base + delta);
+        shared_prefixes_.push_back(prefix);
+      }
+    }
+
+    // Lay down a sparsely-distributed layer.
+    const size_t count = shared_prefixes_.size();
+    for (size_t i = 0; i < count; ++i) {
       const SBPrefix prefix = static_cast<SBPrefix>(base::RandUint64());
       shared_prefixes_.push_back(prefix);
     }
 
     // Sort for use with PrefixSet constructor.
     std::sort(shared_prefixes_.begin(), shared_prefixes_.end());
   }
 
   // Check that all elements of |prefixes| are in |prefix_set|, and
   // that nearby elements are not (for lack of a more sensible set of
@@ skipping 415 matching lines @@
   file_util::ScopedFILE file(file_util::OpenFile(filename, "ab"));
   const char buf[] = "im in ur base, killing ur d00dz.";
   ASSERT_EQ(strlen(buf), fwrite(buf, 1, strlen(buf), file.get()));
   file.reset();
   scoped_ptr<safe_browsing::PrefixSet>
       prefix_set(safe_browsing::PrefixSet::LoadFile(filename));
   ASSERT_FALSE(prefix_set.get());
 }
 
 }  // namespace