Additional validation code for PrefixSet.

chrome/browser/safe_browsing/prefix_set.cc

 // 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 <math.h>
 
 #include "base/logging.h"
 #include "base/metrics/histogram.h"
 
 namespace {
 
 // For |std::upper_bound()| to find a prefix w/in a vector of pairs.
 bool PrefixLess(const std::pair<SBPrefix,size_t>& a,
                 const std::pair<SBPrefix,size_t>& b) {
   return a.first < b.first;
 }
 
 }  // namespace
 
 namespace safe_browsing {
 
 PrefixSet::PrefixSet(const std::vector<SBPrefix>& prefixes) {

[lzheng, 2011/03/03 22:30:07]

Do you want to call "prefixes" "sorted_prefixes" to make it clear a sorted list
is expected?

   if (prefixes.size()) {
-    std::vector<SBPrefix> sorted(prefixes.begin(), prefixes.end());
-    std::sort(sorted.begin(), sorted.end());
-
     // Lead with the first prefix.
-    SBPrefix prev_prefix = sorted[0];
+    SBPrefix prev_prefix = prefixes[0];
     size_t run_length = 0;
     index_.push_back(std::make_pair(prev_prefix, deltas_.size()));
 
-    for (size_t i = 1; i < sorted.size(); ++i) {
-      // Don't encode zero deltas.
-      if (sorted[i] == prev_prefix)
+    for (size_t i = 1; i < prefixes.size(); ++i) {
+      // Skip duplicates.
+      if (prefixes[i] == prev_prefix)
         continue;
 
       // Calculate the delta.  |unsigned| is mandatory, because the
       // prefixes could be more than INT_MAX apart.
-      unsigned delta = sorted[i] - prev_prefix;
+      DCHECK_GT(prefixes[i], prev_prefix);
+      unsigned delta = prefixes[i] - prev_prefix;
 
       // New index ref if the delta is too wide, or if too many
       // consecutive deltas have been encoded.  Note that
       // |kMaxDelta| cannot itself be encoded.
       if (delta >= kMaxDelta || run_length >= kMaxRun) {
-        index_.push_back(std::make_pair(sorted[i], deltas_.size()));
+        index_.push_back(std::make_pair(prefixes[i], deltas_.size()));
         run_length = 0;
       } else {
         // Continue the run of deltas.
         deltas_.push_back(static_cast<uint16>(delta));
         ++run_length;
       }
 
-      prev_prefix = sorted[i];
+      prev_prefix = prefixes[i];
     }
 
     // Send up some memory-usage stats.  Bits because fractional bytes
     // are weird.
     const size_t bits_used = index_.size() * sizeof(index_[0]) * CHAR_BIT +
         deltas_.size() * sizeof(deltas_[0]) * CHAR_BIT;
     const size_t unique_prefixes = index_.size() + deltas_.size();
     static const size_t kMaxBitsPerPrefix = sizeof(SBPrefix) * CHAR_BIT;
     UMA_HISTOGRAM_ENUMERATION("SB2.PrefixSetBitsPerPrefix",
                               bits_used / unique_prefixes,
@@ skipping 29 matching lines @@
     return true;
 
   // Scan forward accumulating deltas while a match is possible.
   for (size_t di = iter->second; di < bound && current < prefix; ++di) {
     current += deltas_[di];
   }
 
   return current == prefix;
 }
 
+void PrefixSet::GetPrefixes(std::vector<SBPrefix>* prefixes) {
+  for (size_t ii = 0; ii < index_.size(); ++ii) {
+    // The deltas for this |index_| entry run to the next index entry,
+    // or the end of the deltas.
+    const size_t deltas_end =
+        (ii + 1 < index_.size()) ? index_[ii + 1].second : deltas_.size();
+
+    SBPrefix current = index_[ii].first;
+    prefixes->push_back(current);
+    for (size_t di = index_[ii].second; di < deltas_end; ++di) {
+      current += deltas_[di];
+      prefixes->push_back(current);
+    }
+  }
+}
+
 }  // namespace safe_browsing