Safe-browsing SBAddPrefix from vector to deque.

During updates, a large vector of SBAddPrefix is used to make things
more efficient.  This may also be leading to memory fragmentation,
because the vector for most users will be around 5MB.

This converts std::vector<SBAddPrefix> uses to std::deque<SBAddPrefix>.
SBAddPrefixContainer is used to make this indirect.  The major bits of
this are:
 - safe_browsing_store.cc helper functions templated on abstract
   containers rather than vectors of abstract items.
 - safe_browsing_store_file.cc I/O functions generalized to abstract
   containers rather than vectors of abstract items.  [It also works
   for sets!]
 - Convert appropriate cases of iteration-by-index to iterators.

Also revert the following two debuggin changes:
r104974: Histogram large realloc in safe-browsing update.
r105419: Precalculate total size for safe-browsing add_prefixes.

BUG=99056
TEST=Tests, and monitor crash server.


Review URL: http://codereview.chromium.org/8349018

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@107415 0039d316-1c4b-4281-b951-d872f2087c98

8 files changed, 160 insertions, 218 deletions

diff --git a/chrome/browser/safe_browsing/safe_browsing_database.cc b/chrome/browser/safe_browsing/safe_browsing_database.cc
index 5210a66..e5ac9ea 100644
--- a/chrome/browser/safe_browsing/safe_browsing_database.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_database.cc
@@ -264,15 +264,16 @@ void RecordPrefixSetInfo(PrefixSetEvent event_type) {
 // PREFIX_SET_EVENT_BLOOM_MISS_PREFIX_HIT_INVALID histogram in
 // ContainsBrowseUrl() can be trustworthy.
 safe_browsing::PrefixSet* PrefixSetFromAddPrefixes(
-    const std::vector<SBAddPrefix>& add_prefixes) {
+    const SBAddPrefixes& add_prefixes) {
   // TODO(shess): If |add_prefixes| were sorted by the prefix, it
   // could be passed directly to |PrefixSet()|, removing the need for
   // |prefixes|.  For now, |prefixes| is useful while debugging
   // things.
   std::vector<SBPrefix> prefixes;
   prefixes.reserve(add_prefixes.size());
-  for (size_t i = 0; i < add_prefixes.size(); ++i) {
-    prefixes.push_back(add_prefixes[i].prefix);
+  for (SBAddPrefixes::const_iterator iter = add_prefixes.begin();
+       iter != add_prefixes.end(); ++iter) {
+    prefixes.push_back(iter->prefix);
   }
 
   std::sort(prefixes.begin(), prefixes.end());
@@ -708,13 +709,14 @@ bool SafeBrowsingDatabaseNew::MatchDownloadAddPrefixes(
     std::vector<SBPrefix>* prefix_hits) {
   prefix_hits->clear();
 
-  std::vector<SBAddPrefix> add_prefixes;
+  SBAddPrefixes add_prefixes;
   download_store_->GetAddPrefixes(&add_prefixes);
-  for (size_t i = 0; i < add_prefixes.size(); ++i) {
+  for (SBAddPrefixes::const_iterator iter = add_prefixes.begin();
+       iter != add_prefixes.end(); ++iter) {
     for (size_t j = 0; j < prefixes.size(); ++j) {
       const SBPrefix& prefix = prefixes[j];
-      if (prefix == add_prefixes[i].prefix &&
-          GetListIdBit(add_prefixes[i].chunk_id) == list_bit) {
+      if (prefix == iter->prefix &&
+          GetListIdBit(iter->chunk_id) == list_bit) {
         prefix_hits->push_back(prefix);
       }
     }
@@ -1138,7 +1140,7 @@ void SafeBrowsingDatabaseNew::UpdateWhitelistStore(
 
   // Note: prefixes will not be empty.  The current data store implementation
   // stores all full-length hashes as both full and prefix hashes.
-  std::vector<SBAddPrefix> prefixes;
+  SBAddPrefixes prefixes;
   std::vector<SBAddFullHash> full_hashes;
   if (!store->FinishUpdate(empty_add_hashes, empty_miss_cache, &prefixes,
                            &full_hashes)) {
@@ -1168,7 +1170,7 @@ void SafeBrowsingDatabaseNew::UpdateDownloadStore() {
 
   // These results are not used after this call. Simply ignore the
   // returned value after FinishUpdate(...).
-  std::vector<SBAddPrefix> add_prefixes_result;
+  SBAddPrefixes add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   if (!download_store_->FinishUpdate(empty_add_hashes,
@@ -1218,7 +1220,7 @@ void SafeBrowsingDatabaseNew::UpdateBrowseStore() {
 
   const base::Time before = base::Time::Now();
 
-  std::vector<SBAddPrefix> add_prefixes;
+  SBAddPrefixes add_prefixes;
   std::vector<SBAddFullHash> add_full_hashes;
   if (!browse_store_->FinishUpdate(pending_add_hashes, prefix_miss_cache_,
                                    &add_prefixes, &add_full_hashes)) {
@@ -1232,8 +1234,9 @@ void SafeBrowsingDatabaseNew::UpdateBrowseStore() {
   const int filter_size =
       BloomFilter::FilterSizeForKeyCount(add_prefixes.size());
   scoped_refptr<BloomFilter> filter(new BloomFilter(filter_size));
-  for (size_t i = 0; i < add_prefixes.size(); ++i) {
-    filter->Insert(add_prefixes[i].prefix);
+  for (SBAddPrefixes::const_iterator iter = add_prefixes.begin();
+       iter != add_prefixes.end(); ++iter) {
+    filter->Insert(iter->prefix);
   }
 
   scoped_ptr<safe_browsing::PrefixSet>
@@ -1345,7 +1348,7 @@ void SafeBrowsingDatabaseNew::LoadBloomFilter() {
 
   // Manually re-generate the prefix set from the main database.
   // TODO(shess): Write/read for prefix set.
-  std::vector<SBAddPrefix> add_prefixes;
+  SBAddPrefixes add_prefixes;
   browse_store_->GetAddPrefixes(&add_prefixes);
   prefix_set_.reset(PrefixSetFromAddPrefixes(add_prefixes));
 }
diff --git a/chrome/browser/safe_browsing/safe_browsing_store.cc b/chrome/browser/safe_browsing/safe_browsing_store.cc
index c699c13..447998b 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -16,37 +16,37 @@ namespace {
 // should be compatibly ordered (either by SBAddPrefixLess or
 // SBAddPrefixHashLess).
 //
-// |predAS| provides add < sub, |predSA| provides sub < add, for the
-// tightest compare appropriate (see calls in SBProcessSubs).
-template <class S, class A, typename PredAS, typename PredSA>
-void KnockoutSubs(std::vector<S>* subs,
-                  std::vector<A>* adds,
-                  PredAS predAS, PredSA predSA,
-                  std::vector<A>* adds_removed) {
+// |predAddSub| provides add < sub, |predSubAdd| provides sub < add,
+// for the tightest compare appropriate (see calls in SBProcessSubs).
+template <typename SubsT, typename AddsT,
+          typename PredAddSubT, typename PredSubAddT>
+void KnockoutSubs(SubsT* subs, AddsT* adds,
+                  PredAddSubT predAddSub, PredSubAddT predSubAdd,
+                  AddsT* adds_removed) {
   // Keep a pair of output iterators for writing kept items.  Due to
   // deletions, these may lag the main iterators.  Using erase() on
   // individual items would result in O(N^2) copies.  Using std::list
   // would work around that, at double or triple the memory cost.
-  typename std::vector<A>::iterator add_out = adds->begin();
-  typename std::vector<S>::iterator sub_out = subs->begin();
+  typename AddsT::iterator add_out = adds->begin();
+  typename SubsT::iterator sub_out = subs->begin();
 
-  // Current location in vectors.
+  // Current location in containers.
   // TODO(shess): I want these to be const_iterator, but then
   // std::copy() gets confused.  Could snag a const_iterator add_end,
   // or write an inline std::copy(), but it seems like I'm doing
   // something wrong.
-  typename std::vector<A>::iterator add_iter = adds->begin();
-  typename std::vector<S>::iterator sub_iter = subs->begin();
+  typename AddsT::iterator add_iter = adds->begin();
+  typename SubsT::iterator sub_iter = subs->begin();
 
   while (add_iter != adds->end() && sub_iter != subs->end()) {
     // If |*sub_iter| < |*add_iter|, retain the sub.
-    if (predSA(*sub_iter, *add_iter)) {
+    if (predSubAdd(*sub_iter, *add_iter)) {
       *sub_out = *sub_iter;
       ++sub_out;
       ++sub_iter;
 
       // If |*add_iter| < |*sub_iter|, retain the add.
-    } else if (predAS(*add_iter, *sub_iter)) {
+    } else if (predAddSub(*add_iter, *sub_iter)) {
       *add_out = *add_iter;
       ++add_out;
       ++add_iter;
@@ -66,18 +66,17 @@ void KnockoutSubs(std::vector<S>* subs,
 
 // Remove items in |removes| from |full_hashes|.  |full_hashes| and
 // |removes| should be ordered by SBAddPrefix component.
-template <class T>
-void RemoveMatchingPrefixes(const std::vector<SBAddPrefix>& removes,
-                            std::vector<T>* full_hashes) {
+template <typename HashesT, typename AddsT>
+void RemoveMatchingPrefixes(const AddsT& removes, HashesT* full_hashes) {
   // This is basically an inline of std::set_difference().
   // Unfortunately, that algorithm requires that the two iterator
   // pairs use the same value types.
 
   // Where to store kept items.
-  typename std::vector<T>::iterator out = full_hashes->begin();
+  typename HashesT::iterator out = full_hashes->begin();
 
-  typename std::vector<T>::iterator hash_iter = full_hashes->begin();
-  std::vector<SBAddPrefix>::const_iterator remove_iter = removes.begin();
+  typename HashesT::iterator hash_iter = full_hashes->begin();
+  typename AddsT::const_iterator remove_iter = removes.begin();
 
   while (hash_iter != full_hashes->end() && remove_iter != removes.end()) {
     // Keep items less than |*remove_iter|.
@@ -104,21 +103,21 @@ void RemoveMatchingPrefixes(const std::vector<SBAddPrefix>& removes,
   full_hashes->erase(out, hash_iter);
 }
 
-// Remove deleted items (|chunk_id| in |del_set|) from the vector.
-template <class T>
-void RemoveDeleted(std::vector<T>* vec, const base::hash_set<int32>& del_set) {
-  DCHECK(vec);
+// Remove deleted items (|chunk_id| in |del_set|) from the container.
+template <typename ItemsT>
+void RemoveDeleted(ItemsT* items, const base::hash_set<int32>& del_set) {
+  DCHECK(items);
 
-  // Scan through the items read, dropping the items in |del_set|.
-  typename std::vector<T>::iterator add_iter = vec->begin();
-  for (typename std::vector<T>::iterator iter = add_iter;
-       iter != vec->end(); ++iter) {
+  // Move items from |iter| to |end_iter|, skipping items in |del_set|.
+  typename ItemsT::iterator end_iter = items->begin();
+  for (typename ItemsT::iterator iter = end_iter;
+       iter != items->end(); ++iter) {
     if (del_set.count(iter->chunk_id) == 0) {
-      *add_iter = *iter;
-      ++add_iter;
+      *end_iter = *iter;
+      ++end_iter;
     }
   }
-  vec->erase(add_iter, vec->end());
+  items->erase(end_iter, items->end());
 }
 
 enum MissTypes {
@@ -131,7 +130,7 @@ enum MissTypes {
 
 }  // namespace
 
-void SBCheckPrefixMisses(const std::vector<SBAddPrefix>& add_prefixes,
+void SBCheckPrefixMisses(const SBAddPrefixes& add_prefixes,
                          const std::set<SBPrefix>& prefix_misses) {
   if (prefix_misses.empty())
     return;
@@ -148,9 +147,10 @@ void SBCheckPrefixMisses(const std::vector<SBAddPrefix>& add_prefixes,
   // prefix, it is not sufficient to count the number of elements
   // present in both collections.
   std::set<SBPrefix> false_misses(prefix_misses.begin(), prefix_misses.end());
-  for (size_t i = 0; i < add_prefixes.size(); ++i) {
+  for (SBAddPrefixes::const_iterator iter = add_prefixes.begin();
+       iter != add_prefixes.end(); ++iter) {
     // |erase()| on an absent element should cost like |find()|.
-    false_misses.erase(add_prefixes[i].prefix);
+    false_misses.erase(iter->prefix);
   }
 
   // Record a hit for prefixes which we shouldn't have sent in the
@@ -164,7 +164,7 @@ void SBCheckPrefixMisses(const std::vector<SBAddPrefix>& add_prefixes,
   // bloom-filter false-positive rate.
 }
 
-void SBProcessSubs(std::vector<SBAddPrefix>* add_prefixes,
+void SBProcessSubs(SBAddPrefixes* add_prefixes,
                    std::vector<SBSubPrefix>* sub_prefixes,
                    std::vector<SBAddFullHash>* add_full_hashes,
                    std::vector<SBSubFullHash>* sub_full_hashes,
@@ -186,7 +186,7 @@ void SBProcessSubs(std::vector<SBAddPrefix>* add_prefixes,
             SBAddPrefixHashLess<SBSubFullHash,SBSubFullHash>);
 
   // Factor out the prefix subs.
-  std::vector<SBAddPrefix> removed_adds;
+  SBAddPrefixes removed_adds;
   KnockoutSubs(sub_prefixes, add_prefixes,
                SBAddPrefixLess<SBAddPrefix,SBSubPrefix>,
                SBAddPrefixLess<SBSubPrefix,SBAddPrefix>,
diff --git a/chrome/browser/safe_browsing/safe_browsing_store.h b/chrome/browser/safe_browsing/safe_browsing_store.h
index 9463b1c..f7aed5e 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store.h
+++ b/chrome/browser/safe_browsing/safe_browsing_store.h
@@ -51,6 +51,8 @@ struct SBAddPrefix {
   SBPrefix GetAddPrefix() const { return prefix; }
 };
 
+typedef std::deque<SBAddPrefix> SBAddPrefixes;
+
 struct SBSubPrefix {
   int32 chunk_id;
   int32 add_chunk_id;
@@ -138,7 +140,7 @@ bool SBAddPrefixHashLess(const T& a, const U& b) {
 // TODO(shess): The original code did not process |sub_full_hashes|
 // for matches in |add_full_hashes|, so this code doesn't, either.  I
 // think this is probably a bug.
-void SBProcessSubs(std::vector<SBAddPrefix>* add_prefixes,
+void SBProcessSubs(SBAddPrefixes* add_prefixes,
                    std::vector<SBSubPrefix>* sub_prefixes,
                    std::vector<SBAddFullHash>* add_full_hashes,
                    std::vector<SBSubFullHash>* sub_full_hashes,
@@ -147,7 +149,7 @@ void SBProcessSubs(std::vector<SBAddPrefix>* add_prefixes,
 
 // Records a histogram of the number of items in |prefix_misses| which
 // are not in |add_prefixes|.
-void SBCheckPrefixMisses(const std::vector<SBAddPrefix>& add_prefixes,
+void SBCheckPrefixMisses(const SBAddPrefixes& add_prefixes,
                          const std::set<SBPrefix>& prefix_misses);
 
 // TODO(shess): This uses int32 rather than int because it's writing
@@ -174,7 +176,7 @@ class SafeBrowsingStore {
   virtual bool Delete() = 0;
 
   // Get all Add prefixes out from the store.
-  virtual bool GetAddPrefixes(std::vector<SBAddPrefix>* add_prefixes) = 0;
+  virtual bool GetAddPrefixes(SBAddPrefixes* add_prefixes) = 0;
 
   // Get all add full-length hashes.
   virtual bool GetAddFullHashes(
@@ -230,7 +232,7 @@ class SafeBrowsingStore {
   virtual bool FinishUpdate(
       const std::vector<SBAddFullHash>& pending_adds,
       const std::set<SBPrefix>& prefix_misses,
-      std::vector<SBAddPrefix>* add_prefixes_result,
+      SBAddPrefixes* add_prefixes_result,
       std::vector<SBAddFullHash>* add_full_hashes_result) = 0;
 
   // Cancel the update in process and remove any temporary disk
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_file.cc b/chrome/browser/safe_browsing/safe_browsing_store_file.cc
index 5e1b853..7f1924d 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_file.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_file.cc
@@ -48,63 +48,55 @@ bool FileSkip(size_t bytes, FILE* fp) {
   return rv == 0;
 }
 
-// Read an array of |nmemb| items from |fp| into |ptr|, and fold the
-// input data into the checksum in |context|, if non-NULL.  Return
-// true on success.
+// Read from |fp| into |item|, and fold the input data into the
+// checksum in |context|, if non-NULL.  Return true on success.
 template <class T>
-bool ReadArray(T* ptr, size_t nmemb, FILE* fp, base::MD5Context* context) {
-  const size_t ret = fread(ptr, sizeof(T), nmemb, fp);
-  if (ret != nmemb)
+bool ReadItem(T* item, FILE* fp, base::MD5Context* context) {
+  const size_t ret = fread(item, sizeof(T), 1, fp);
+  if (ret != 1)
     return false;
 
   if (context) {
     base::MD5Update(context,
-                    base::StringPiece(reinterpret_cast<char*>(ptr),
-                                      sizeof(T) * nmemb));
+                    base::StringPiece(reinterpret_cast<char*>(item),
+                                      sizeof(T)));
   }
   return true;
 }
 
-// Write an array of |nmemb| items from |ptr| to |fp|, and fold the
-// output data into the checksum in |context|, if non-NULL.  Return
-// true on success.
+// Write |item| to |fp|, and fold the output data into the checksum in
+// |context|, if non-NULL.  Return true on success.
 template <class T>
-bool WriteArray(const T* ptr, size_t nmemb, FILE* fp,
-                base::MD5Context* context) {
-  const size_t ret = fwrite(ptr, sizeof(T), nmemb, fp);
-  if (ret != nmemb)
+bool WriteItem(const T& item, FILE* fp, base::MD5Context* context) {
+  const size_t ret = fwrite(&item, sizeof(T), 1, fp);
+  if (ret != 1)
     return false;
 
   if (context) {
     base::MD5Update(context,
-                    base::StringPiece(reinterpret_cast<const char*>(ptr),
-                                      sizeof(T) * nmemb));
+                    base::StringPiece(reinterpret_cast<const char*>(&item),
+                                      sizeof(T)));
   }
 
   return true;
 }
 
-// Expand |values| to fit |count| new items, read those items from
-// |fp| and fold them into the checksum in |context|.  Returns true on
-// success.
-template <class T>
-bool ReadToVector(std::vector<T>* values, size_t count, FILE* fp,
-                  base::MD5Context* context) {
-  // Pointers into an empty vector may not be valid.
+// Read |count| items into |values| from |fp|, and fold them into the
+// checksum in |context|.  Returns true on success.
+template <typename CT>
+bool ReadToContainer(CT* values, size_t count, FILE* fp,
+                     base::MD5Context* context) {
   if (!count)
     return true;
 
-  // Grab the size for purposes of finding where to read to.  The
-  // resize could invalidate any iterator captured here.
-  const size_t original_size = values->size();
-  values->resize(original_size + count);
+  for (size_t i = 0; i < count; ++i) {
+    typename CT::value_type value;
+    if (!ReadItem(&value, fp, context))
+      return false;
 
-  // Sayeth Herb Sutter: Vectors are guaranteed to be contiguous.  So
-  // get a pointer to where to read the data to.
-  T* ptr = &((*values)[original_size]);
-  if (!ReadArray(ptr, count, fp, context)) {
-    values->resize(original_size);
-    return false;
+    // push_back() is more obvious, but coded this way std::set can
+    // also be read.
+    values->insert(values->end(), value);
   }
 
   return true;
@@ -112,43 +104,18 @@ bool ReadToVector(std::vector<T>* values, size_t count, FILE* fp,
 
 // Write all of |values| to |fp|, and fold the data into the checksum
 // in |context|, if non-NULL.  Returns true on succsess.
-template <class T>
-bool WriteVector(const std::vector<T>& values, FILE* fp,
-                 base::MD5Context* context) {
-  // Pointers into empty vectors may not be valid.
-  if (values.empty())
-    return true;
-
-  // Sayeth Herb Sutter: Vectors are guaranteed to be contiguous.  So
-  // get a pointer to where to write from.
-  const T* ptr = &(values[0]);
-  return WriteArray(ptr, values.size(), fp, context);
-}
-
-// Read an array of |count| integers and add them to |values|.
-// Returns true on success.
-bool ReadToChunkSet(std::set<int32>* values, size_t count, FILE* fp,
+template <typename CT>
+bool WriteContainer(const CT& values, FILE* fp,
                     base::MD5Context* context) {
-  if (!count)
-    return true;
-
-  std::vector<int32> flat_values;
-  if (!ReadToVector(&flat_values, count, fp, context))
-    return false;
-
-  values->insert(flat_values.begin(), flat_values.end());
-  return true;
-}
-
-// Write the contents of |values| as an array of integers.  Returns
-// true on success.
-bool WriteChunkSet(const std::set<int32>& values, FILE* fp,
-                   base::MD5Context* context) {
   if (values.empty())
     return true;
 
-  const std::vector<int32> flat_values(values.begin(), values.end());
-  return WriteVector(flat_values, fp, context);
+  for (typename CT::const_iterator iter = values.begin();
+       iter != values.end(); ++iter) {
+    if (!WriteItem(*iter, fp, context))
+      return false;
+  }
+  return true;
 }
 
 // Delete the chunks in |deleted| from |chunks|.
@@ -191,7 +158,7 @@ bool ReadAndVerifyHeader(const FilePath& filename,
                          FILE* fp,
                          FileHeader* header,
                          base::MD5Context* context) {
-  if (!ReadArray(header, 1, fp, context))
+  if (!ReadItem(header, fp, context))
     return false;
   if (header->magic != kFileMagic || header->version != kFileVersion)
     return false;
@@ -293,8 +260,7 @@ bool SafeBrowsingStoreFile::WriteAddPrefix(int32 chunk_id, SBPrefix prefix) {
   return true;
 }
 
-bool SafeBrowsingStoreFile::GetAddPrefixes(
-   std::vector<SBAddPrefix>* add_prefixes) {
+bool SafeBrowsingStoreFile::GetAddPrefixes(SBAddPrefixes* add_prefixes) {
   add_prefixes->clear();
 
   file_util::ScopedFILE file(file_util::OpenFile(filename_, "rb"));
@@ -309,7 +275,7 @@ bool SafeBrowsingStoreFile::GetAddPrefixes(
   if (!FileSkip(add_prefix_offset, file.get()))
     return false;
 
-  if (!ReadToVector(add_prefixes, header.add_prefix_count, file.get(), NULL))
+  if (!ReadToContainer(add_prefixes, header.add_prefix_count, file.get(), NULL))
     return false;
 
   return true;
@@ -334,10 +300,10 @@ bool SafeBrowsingStoreFile::GetAddFullHashes(
   if (!FileSkip(offset, file.get()))
     return false;
 
-  return ReadToVector(add_full_hashes,
-                      header.add_hash_count,
-                      file.get(),
-                      NULL);
+  return ReadToContainer(add_full_hashes,
+                         header.add_hash_count,
+                         file.get(),
+                         NULL);
 }
 
 bool SafeBrowsingStoreFile::WriteAddHash(int32 chunk_id,
@@ -393,7 +359,6 @@ bool SafeBrowsingStoreFile::BeginUpdate() {
   DCHECK(add_hashes_.empty());
   DCHECK(sub_hashes_.empty());
   DCHECK_EQ(chunks_written_, 0);
-  add_prefixes_added_ = 0;
 
   // Since the following code will already hit the profile looking for
   // database files, this is a reasonable to time delete any old
@@ -420,7 +385,7 @@ bool SafeBrowsingStoreFile::BeginUpdate() {
   }
 
   FileHeader header;
-  if (!ReadArray(&header, 1, file.get(), NULL))
+  if (!ReadItem(&header, file.get(), NULL))
       return OnCorruptDatabase();
 
   if (header.magic != kFileMagic || header.version != kFileVersion) {
@@ -444,10 +409,10 @@ bool SafeBrowsingStoreFile::BeginUpdate() {
   // Pull in the chunks-seen data for purposes of implementing
   // |GetAddChunks()| and |GetSubChunks()|.  This data is sent up to
   // the server at the beginning of an update.
-  if (!ReadToChunkSet(&add_chunks_cache_, header.add_chunk_count,
-                      file.get(), NULL) ||
-      !ReadToChunkSet(&sub_chunks_cache_, header.sub_chunk_count,
-                      file.get(), NULL))
+  if (!ReadToContainer(&add_chunks_cache_, header.add_chunk_count,
+                       file.get(), NULL) ||
+      !ReadToContainer(&sub_chunks_cache_, header.sub_chunk_count,
+                       file.get(), NULL))
     return OnCorruptDatabase();
 
   file_.swap(file);
@@ -465,17 +430,16 @@ bool SafeBrowsingStoreFile::FinishChunk() {
   header.sub_prefix_count = sub_prefixes_.size();
   header.add_hash_count = add_hashes_.size();
   header.sub_hash_count = sub_hashes_.size();
-  if (!WriteArray(&header, 1, new_file_.get(), NULL))
+  if (!WriteItem(header, new_file_.get(), NULL))
     return false;
 
-  if (!WriteVector(add_prefixes_, new_file_.get(), NULL) ||
-      !WriteVector(sub_prefixes_, new_file_.get(), NULL) ||
-      !WriteVector(add_hashes_, new_file_.get(), NULL) ||
-      !WriteVector(sub_hashes_, new_file_.get(), NULL))
+  if (!WriteContainer(add_prefixes_, new_file_.get(), NULL) ||
+      !WriteContainer(sub_prefixes_, new_file_.get(), NULL) ||
+      !WriteContainer(add_hashes_, new_file_.get(), NULL) ||
+      !WriteContainer(sub_hashes_, new_file_.get(), NULL))
     return false;
 
   ++chunks_written_;
-  add_prefixes_added_ += add_prefixes_.size();
 
   // Clear everything to save memory.
   return ClearChunkBuffers();
@@ -484,14 +448,14 @@ bool SafeBrowsingStoreFile::FinishChunk() {
 bool SafeBrowsingStoreFile::DoUpdate(
     const std::vector<SBAddFullHash>& pending_adds,
     const std::set<SBPrefix>& prefix_misses,
-    std::vector<SBAddPrefix>* add_prefixes_result,
+    SBAddPrefixes* add_prefixes_result,
     std::vector<SBAddFullHash>* add_full_hashes_result) {
   DCHECK(file_.get() || empty_);
   DCHECK(new_file_.get());
   CHECK(add_prefixes_result);
   CHECK(add_full_hashes_result);
 
-  std::vector<SBAddPrefix> add_prefixes;
+  SBAddPrefixes add_prefixes;
   std::vector<SBSubPrefix> sub_prefixes;
   std::vector<SBAddFullHash> add_full_hashes;
   std::vector<SBSubFullHash> sub_full_hashes;
@@ -514,22 +478,20 @@ bool SafeBrowsingStoreFile::DoUpdate(
     // Re-read the chunks-seen data to get to the later data in the
     // file and calculate the checksum.  No new elements should be
     // added to the sets.
-    if (!ReadToChunkSet(&add_chunks_cache_, header.add_chunk_count,
-                        file_.get(), &context) ||
-        !ReadToChunkSet(&sub_chunks_cache_, header.sub_chunk_count,
-                        file_.get(), &context))
+    if (!ReadToContainer(&add_chunks_cache_, header.add_chunk_count,
+                         file_.get(), &context) ||
+        !ReadToContainer(&sub_chunks_cache_, header.sub_chunk_count,
+                         file_.get(), &context))
       return OnCorruptDatabase();
 
-    add_prefixes.reserve(header.add_prefix_count + add_prefixes_added_);
-
-    if (!ReadToVector(&add_prefixes, header.add_prefix_count,
-                      file_.get(), &context) ||
-        !ReadToVector(&sub_prefixes, header.sub_prefix_count,
-                      file_.get(), &context) ||
-        !ReadToVector(&add_full_hashes, header.add_hash_count,
-                      file_.get(), &context) ||
-        !ReadToVector(&sub_full_hashes, header.sub_hash_count,
-                      file_.get(), &context))
+    if (!ReadToContainer(&add_prefixes, header.add_prefix_count,
+                         file_.get(), &context) ||
+        !ReadToContainer(&sub_prefixes, header.sub_prefix_count,
+                         file_.get(), &context) ||
+        !ReadToContainer(&add_full_hashes, header.add_hash_count,
+                         file_.get(), &context) ||
+        !ReadToContainer(&sub_full_hashes, header.sub_hash_count,
+                         file_.get(), &context))
       return OnCorruptDatabase();
 
     // Calculate the digest to this point.
@@ -538,7 +500,7 @@ bool SafeBrowsingStoreFile::DoUpdate(
 
     // Read the stored checksum and verify it.
     base::MD5Digest file_digest;
-    if (!ReadArray(&file_digest, 1, file_.get(), NULL))
+    if (!ReadItem(&file_digest, file_.get(), NULL))
       return OnCorruptDatabase();
 
     if (0 != memcmp(&file_digest, &calculated_digest, sizeof(file_digest)))
@@ -546,8 +508,6 @@ bool SafeBrowsingStoreFile::DoUpdate(
 
     // Close the file so we can later rename over it.
     file_.reset();
-  } else {
-    add_prefixes.reserve(add_prefixes_added_);
   }
   DCHECK(!file_.get());
 
@@ -566,9 +526,6 @@ bool SafeBrowsingStoreFile::DoUpdate(
   UMA_HISTOGRAM_COUNTS("SB2.DatabaseUpdateKilobytes",
                        std::max(static_cast<int>(size / 1024), 1));
 
-  // TODO(shess): For SB2.AddPrefixesReallocs histogram.
-  int add_prefixes_reallocs = 0;
-
   // Append the accumulated chunks onto the vectors read from |file_|.
   for (int i = 0; i < chunks_written_; ++i) {
     ChunkHeader header;
@@ -577,7 +534,7 @@ bool SafeBrowsingStoreFile::DoUpdate(
     if (ofs == -1)
       return false;
 
-    if (!ReadArray(&header, 1, new_file_.get(), NULL))
+    if (!ReadItem(&header, new_file_.get(), NULL))
       return false;
 
     // As a safety measure, make sure that the header describes a sane
@@ -590,10 +547,6 @@ bool SafeBrowsingStoreFile::DoUpdate(
     if (expected_size > size)
       return false;
 
-    // TODO(shess): For SB2.AddPrefixesReallocs histogram.
-    SBAddPrefix* add_prefixes_old_start =
-        (add_prefixes.size() ? &add_prefixes[0] : NULL);
-
     // TODO(shess): If the vectors were kept sorted, then this code
     // could use std::inplace_merge() to merge everything together in
     // sorted order.  That might still be slower than just sorting at
@@ -601,29 +554,17 @@ bool SafeBrowsingStoreFile::DoUpdate(
     // some sort of recursive binary merge might be in order (merge
     // chunks pairwise, merge those chunks pairwise, and so on, then
     // merge the result with the main list).
-    if (!ReadToVector(&add_prefixes, header.add_prefix_count,
-                      new_file_.get(), NULL) ||
-        !ReadToVector(&sub_prefixes, header.sub_prefix_count,
-                      new_file_.get(), NULL) ||
-        !ReadToVector(&add_full_hashes, header.add_hash_count,
-                      new_file_.get(), NULL) ||
-        !ReadToVector(&sub_full_hashes, header.sub_hash_count,
-                      new_file_.get(), NULL))
+    if (!ReadToContainer(&add_prefixes, header.add_prefix_count,
+                         new_file_.get(), NULL) ||
+        !ReadToContainer(&sub_prefixes, header.sub_prefix_count,
+                         new_file_.get(), NULL) ||
+        !ReadToContainer(&add_full_hashes, header.add_hash_count,
+                         new_file_.get(), NULL) ||
+        !ReadToContainer(&sub_full_hashes, header.sub_hash_count,
+                         new_file_.get(), NULL))
       return false;
-
-    // Determine if the vector data moved to a new location.  This
-    // won't track cases where the malloc library was able to expand
-    // the storage in place, but those cases shouldn't cause memory
-    // fragmentation anyhow.
-    SBAddPrefix* add_prefixes_new_start =
-        (add_prefixes.size() ? &add_prefixes[0] : NULL);
-    if (add_prefixes_old_start != add_prefixes_new_start)
-      ++add_prefixes_reallocs;
   }
 
-  // Track the number of times this number of re-allocations occurred.
-  UMA_HISTOGRAM_COUNTS_100("SB2.AddPrefixesReallocs", add_prefixes_reallocs);
-
   // Append items from |pending_adds|.
   add_full_hashes.insert(add_full_hashes.end(),
                          pending_adds.begin(), pending_adds.end());
@@ -658,22 +599,22 @@ bool SafeBrowsingStoreFile::DoUpdate(
   header.sub_prefix_count = sub_prefixes.size();
   header.add_hash_count = add_full_hashes.size();
   header.sub_hash_count = sub_full_hashes.size();
-  if (!WriteArray(&header, 1, new_file_.get(), &context))
+  if (!WriteItem(header, new_file_.get(), &context))
     return false;
 
   // Write all the chunk data.
-  if (!WriteChunkSet(add_chunks_cache_, new_file_.get(), &context) ||
-      !WriteChunkSet(sub_chunks_cache_, new_file_.get(), &context) ||
-      !WriteVector(add_prefixes, new_file_.get(), &context) ||
-      !WriteVector(sub_prefixes, new_file_.get(), &context) ||
-      !WriteVector(add_full_hashes, new_file_.get(), &context) ||
-      !WriteVector(sub_full_hashes, new_file_.get(), &context))
+  if (!WriteContainer(add_chunks_cache_, new_file_.get(), &context) ||
+      !WriteContainer(sub_chunks_cache_, new_file_.get(), &context) ||
+      !WriteContainer(add_prefixes, new_file_.get(), &context) ||
+      !WriteContainer(sub_prefixes, new_file_.get(), &context) ||
+      !WriteContainer(add_full_hashes, new_file_.get(), &context) ||
+      !WriteContainer(sub_full_hashes, new_file_.get(), &context))
     return false;
 
   // Write the checksum at the end.
   base::MD5Digest digest;
   base::MD5Final(&digest, &context);
-  if (!WriteArray(&digest, 1, new_file_.get(), NULL))
+  if (!WriteItem(digest, new_file_.get(), NULL))
     return false;
 
   // Trim any excess left over from the temporary chunk data.
@@ -704,7 +645,7 @@ bool SafeBrowsingStoreFile::DoUpdate(
 bool SafeBrowsingStoreFile::FinishUpdate(
     const std::vector<SBAddFullHash>& pending_adds,
     const std::set<SBPrefix>& prefix_misses,
-    std::vector<SBAddPrefix>* add_prefixes_result,
+    SBAddPrefixes* add_prefixes_result,
     std::vector<SBAddFullHash>* add_full_hashes_result) {
   DCHECK(add_prefixes_result);
   DCHECK(add_full_hashes_result);
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_file.h b/chrome/browser/safe_browsing/safe_browsing_store_file.h
index 452f2de..f515d60 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_file.h
+++ b/chrome/browser/safe_browsing/safe_browsing_store_file.h
@@ -116,7 +116,7 @@ class SafeBrowsingStoreFile : public SafeBrowsingStore {
 
   // Get all add hash prefixes and full-length hashes, respectively, from
   // the store.
-  virtual bool GetAddPrefixes(std::vector<SBAddPrefix>* add_prefixes) OVERRIDE;
+  virtual bool GetAddPrefixes(SBAddPrefixes* add_prefixes) OVERRIDE;
   virtual bool GetAddFullHashes(
       std::vector<SBAddFullHash>* add_full_hashes) OVERRIDE;
 
@@ -138,7 +138,7 @@ class SafeBrowsingStoreFile : public SafeBrowsingStore {
   virtual bool FinishUpdate(
       const std::vector<SBAddFullHash>& pending_adds,
       const std::set<SBPrefix>& prefix_misses,
-      std::vector<SBAddPrefix>* add_prefixes_result,
+      SBAddPrefixes* add_prefixes_result,
       std::vector<SBAddFullHash>* add_full_hashes_result) OVERRIDE;
   virtual bool CancelUpdate() OVERRIDE;
 
@@ -162,7 +162,7 @@ class SafeBrowsingStoreFile : public SafeBrowsingStore {
   // Update store file with pending full hashes.
   virtual bool DoUpdate(const std::vector<SBAddFullHash>& pending_adds,
                         const std::set<SBPrefix>& prefix_misses,
-                        std::vector<SBAddPrefix>* add_prefixes_result,
+                        SBAddPrefixes* add_prefixes_result,
                         std::vector<SBAddFullHash>* add_full_hashes_result);
 
   // Enumerate different format-change events for histogramming
@@ -222,7 +222,7 @@ class SafeBrowsingStoreFile : public SafeBrowsingStore {
     // TODO(shess): Figure out if this is overkill.  Some amount of
     // pre-reserved space is probably reasonable between each chunk
     // collected.
-    std::vector<SBAddPrefix>().swap(add_prefixes_);
+    SBAddPrefixes().swap(add_prefixes_);
     std::vector<SBSubPrefix>().swap(sub_prefixes_);
     std::vector<SBAddFullHash>().swap(add_hashes_);
     std::vector<SBSubFullHash>().swap(sub_hashes_);
@@ -241,7 +241,7 @@ class SafeBrowsingStoreFile : public SafeBrowsingStore {
 
   // Buffers for collecting data between BeginChunk() and
   // FinishChunk().
-  std::vector<SBAddPrefix> add_prefixes_;
+  SBAddPrefixes add_prefixes_;
   std::vector<SBSubPrefix> sub_prefixes_;
   std::vector<SBAddFullHash> add_hashes_;
   std::vector<SBSubFullHash> sub_hashes_;
@@ -271,10 +271,6 @@ class SafeBrowsingStoreFile : public SafeBrowsingStore {
   base::hash_set<int32> add_del_cache_;
   base::hash_set<int32> sub_del_cache_;
 
-  // Count number of add_prefix items added during the course of an
-  // update, for purposes of optimizing vector sizing at commit time.
-  size_t add_prefixes_added_;
-
   base::Closure corruption_callback_;
 
   // Tracks whether corruption has already been seen in the current
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc b/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
index 324015b..f62b261 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_file_unittest.cc
@@ -89,7 +89,7 @@ TEST_F(SafeBrowsingStoreFileTest, DetectsCorruption) {
   // Can successfully open and read the store.
   std::vector<SBAddFullHash> pending_adds;
   std::set<SBPrefix> prefix_misses;
-  std::vector<SBAddPrefix> orig_prefixes;
+  SBAddPrefixes orig_prefixes;
   std::vector<SBAddFullHash> orig_hashes;
   EXPECT_TRUE(test_store.BeginUpdate());
   EXPECT_TRUE(test_store.FinishUpdate(pending_adds, prefix_misses,
@@ -111,7 +111,7 @@ TEST_F(SafeBrowsingStoreFileTest, DetectsCorruption) {
   file.reset();
 
   // Update fails and corruption callback is called.
-  std::vector<SBAddPrefix> add_prefixes;
+  SBAddPrefixes add_prefixes;
   std::vector<SBAddFullHash> add_hashes;
   corruption_detected_ = false;
   EXPECT_TRUE(test_store.BeginUpdate());
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc b/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc
index 4284625..81d7159 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_unittest.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -112,7 +112,7 @@ TEST(SafeBrowsingStoreTest, SBSubFullHashLess) {
 // SBProcessSubs does a lot of iteration, run through empty just to
 // make sure degenerate cases work.
 TEST(SafeBrowsingStoreTest, SBProcessSubsEmpty) {
-  std::vector<SBAddPrefix> add_prefixes;
+  SBAddPrefixes add_prefixes;
   std::vector<SBAddFullHash> add_hashes;
   std::vector<SBSubPrefix> sub_prefixes;
   std::vector<SBSubFullHash> sub_hashes;
@@ -143,7 +143,7 @@ TEST(SafeBrowsingStoreTest, SBProcessSubsKnockout) {
   SBFullHash kHash1mod3 = kHash1mod2;
   kHash1mod3.full_hash[sizeof(kHash1mod3.full_hash) - 1] ++;
 
-  std::vector<SBAddPrefix> add_prefixes;
+  SBAddPrefixes add_prefixes;
   std::vector<SBAddFullHash> add_hashes;
   std::vector<SBSubPrefix> sub_prefixes;
   std::vector<SBSubFullHash> sub_hashes;
@@ -206,7 +206,7 @@ TEST(SafeBrowsingStoreTest, SBProcessSubsDeleteChunk) {
   SBFullHash kHash1mod3 = kHash1mod2;
   kHash1mod3.full_hash[sizeof(kHash1mod3.full_hash) - 1] ++;
 
-  std::vector<SBAddPrefix> add_prefixes;
+  SBAddPrefixes add_prefixes;
   std::vector<SBAddFullHash> add_hashes;
   std::vector<SBSubPrefix> sub_prefixes;
   std::vector<SBSubFullHash> sub_hashes;
diff --git a/chrome/browser/safe_browsing/safe_browsing_store_unittest_helper.cc b/chrome/browser/safe_browsing/safe_browsing_store_unittest_helper.cc
index b88efe7..82af040 100644
--- a/chrome/browser/safe_browsing/safe_browsing_store_unittest_helper.cc
+++ b/chrome/browser/safe_browsing/safe_browsing_store_unittest_helper.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2010 The Chromium Authors. All rights reserved.
+// 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.
 
@@ -45,7 +45,7 @@ void SafeBrowsingStoreTestEmpty(SafeBrowsingStore* store) {
 
   std::vector<SBAddFullHash> pending_adds;
   std::set<SBPrefix> prefix_misses;
-  std::vector<SBAddPrefix> add_prefixes_result;
+  SBAddPrefixes add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
@@ -90,7 +90,7 @@ void SafeBrowsingStoreTestStorePrefix(SafeBrowsingStore* store) {
 
   std::vector<SBAddFullHash> pending_adds;
   std::set<SBPrefix> prefix_misses;
-  std::vector<SBAddPrefix> add_prefixes_result;
+  SBAddPrefixes add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
@@ -163,7 +163,7 @@ void SafeBrowsingStoreTestSubKnockout(SafeBrowsingStore* store) {
 
   std::vector<SBAddFullHash> pending_adds;
   std::set<SBPrefix> prefix_misses;
-  std::vector<SBAddPrefix> add_prefixes_result;
+  SBAddPrefixes add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
@@ -267,7 +267,7 @@ void SafeBrowsingStoreTestDeleteChunks(SafeBrowsingStore* store) {
 
   std::vector<SBAddFullHash> pending_adds;
   std::set<SBPrefix> prefix_misses;
-  std::vector<SBAddPrefix> add_prefixes_result;
+  SBAddPrefixes add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,
@@ -337,7 +337,7 @@ void SafeBrowsingStoreTestDelete(SafeBrowsingStore* store,
 
   std::vector<SBAddFullHash> pending_adds;
   std::set<SBPrefix> prefix_misses;
-  std::vector<SBAddPrefix> add_prefixes_result;
+  SBAddPrefixes add_prefixes_result;
   std::vector<SBAddFullHash> add_full_hashes_result;
 
   EXPECT_TRUE(store->FinishUpdate(pending_adds,