Reserve space before building potentially large vectors in safe-browsing.

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/file_util.h"
@@ skipping 24 matching lines @@
   return a.first < b.first;
 }
 
 }  // namespace
 
 namespace safe_browsing {
 
 PrefixSet::PrefixSet(const std::vector<SBPrefix>& sorted_prefixes)
     : checksum_(0) {
   if (sorted_prefixes.size()) {
+    // Estimate the resulting vector sizes.  There will be strictly
+    // more than |min_runs| entries in |index_|, but there generally
+    // aren't many forced breaks.
+    const size_t min_runs = sorted_prefixes.size() / kMaxRun;
+    index_.reserve(min_runs);
+    deltas_.reserve(sorted_prefixes.size() - min_runs);
+
     // Lead with the first prefix.
     SBPrefix prev_prefix = sorted_prefixes[0];
     size_t run_length = 0;
     index_.push_back(std::make_pair(prev_prefix, deltas_.size()));
 
     // Used to build a checksum from the data used to construct the
     // structures.  Since the data is a bunch of uniform hashes, it
     // seems reasonable to just xor most of it in, rather than trying
     // to use a more complicated algorithm.
     uint32 checksum = static_cast<uint32>(sorted_prefixes[0]);
@@ skipping 79 matching lines @@
 
   // 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) const {
+  prefixes->reserve(index_.size() + deltas_.size());
+
   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];
@@ skipping 197 matching lines @@
   }
 
   for (size_t di = 0; di < deltas_.size(); ++di) {
     checksum ^= static_cast<uint32>(deltas_[di]);
   }
 
   return checksum == checksum_;
 }
 
 }  // namespace safe_browsing