src/chrome/browser/safe_browsing/safe_browsing_store.cc

   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/safe_browsing_store.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/logging.h"
  10
  11 namespace {
  12
  13 // Return |true| if the range is sorted by the given comparator.
  14 template <typename CTI, typename LESS>
  15 bool sorted(CTI beg, CTI end, LESS less) {
  16   while ((end - beg) > 2) {
  17     CTI n = beg++;
  18     if (less(*beg, *n))
  19       return false;
  20   }
  21   return true;
  22 }
  23
  24 // Find items matching between |subs| and |adds|, and remove them.  To minimize
  25 // copies, the inputs are processing in parallel, so |subs| and |adds| should be
  26 // compatibly ordered (either by SBAddPrefixLess or SBAddPrefixHashLess).
  27 //
  28 // |predAddSub| provides add < sub, |predSubAdd| provides sub < add, for the
  29 // tightest compare appropriate (see calls in SBProcessSubs).
  30 template <typename SubsT, typename AddsT,
  31           typename PredAddSubT, typename PredSubAddT>
  32 void KnockoutSubs(SubsT* subs, AddsT* adds,
  33                   PredAddSubT predAddSub, PredSubAddT predSubAdd) {
  34   // Keep a pair of output iterators for writing kept items.  Due to
  35   // deletions, these may lag the main iterators.  Using erase() on
  36   // individual items would result in O(N^2) copies.  Using std::list
  37   // would work around that, at double or triple the memory cost.
  38   typename AddsT::iterator add_out = adds->begin();
  39   typename SubsT::iterator sub_out = subs->begin();
  40
  41   // Current location in containers.
  42   // TODO(shess): I want these to be const_iterator, but then
  43   // std::copy() gets confused.  Could snag a const_iterator add_end,
  44   // or write an inline std::copy(), but it seems like I'm doing
  45   // something wrong.
  46   typename AddsT::iterator add_iter = adds->begin();
  47   typename SubsT::iterator sub_iter = subs->begin();
  48
  49   while (add_iter != adds->end() && sub_iter != subs->end()) {
  50     // If |*sub_iter| < |*add_iter|, retain the sub.
  51     if (predSubAdd(*sub_iter, *add_iter)) {
  52       *sub_out = *sub_iter;
  53       ++sub_out;
  54       ++sub_iter;
  55
  56       // If |*add_iter| < |*sub_iter|, retain the add.
  57     } else if (predAddSub(*add_iter, *sub_iter)) {
  58       *add_out = *add_iter;
  59       ++add_out;
  60       ++add_iter;
  61
  62       // Drop equal items.
  63     } else {
  64       ++add_iter;
  65       ++sub_iter;
  66     }
  67   }
  68
  69   // Erase any leftover gap.
  70   adds->erase(add_out, add_iter);
  71   subs->erase(sub_out, sub_iter);
  72 }
  73
  74 // Remove deleted items (|chunk_id| in |del_set|) from the container.
  75 template <typename ItemsT>
  76 void RemoveDeleted(ItemsT* items, const base::hash_set<int32>& del_set) {
  77   DCHECK(items);
  78
  79   // Move items from |iter| to |end_iter|, skipping items in |del_set|.
  80   typename ItemsT::iterator end_iter = items->begin();
  81   for (typename ItemsT::iterator iter = end_iter;
  82        iter != items->end(); ++iter) {
  83     if (del_set.count(iter->chunk_id) == 0) {
  84       *end_iter = *iter;
  85       ++end_iter;
  86     }
  87   }
  88   items->erase(end_iter, items->end());
  89 }
  90
  91 }  // namespace
  92
  93 void SBProcessSubs(SBAddPrefixes* add_prefixes,
  94                    SBSubPrefixes* sub_prefixes,
  95                    std::vector<SBAddFullHash>* add_full_hashes,
  96                    std::vector<SBSubFullHash>* sub_full_hashes,
  97                    const base::hash_set<int32>& add_chunks_deleted,
  98                    const base::hash_set<int32>& sub_chunks_deleted) {
  99   // It is possible to structure templates and template
 100   // specializations such that the following calls work without having
 101   // to qualify things.  It becomes very arbitrary, though, and less
 102   // clear how things are working.
 103
 104   // Make sure things are sorted appropriately.
 105   DCHECK(sorted(add_prefixes->begin(), add_prefixes->end(),
 106                 SBAddPrefixLess<SBAddPrefix,SBAddPrefix>));
 107   DCHECK(sorted(sub_prefixes->begin(), sub_prefixes->end(),
 108                 SBAddPrefixLess<SBSubPrefix,SBSubPrefix>));
 109   DCHECK(sorted(add_full_hashes->begin(), add_full_hashes->end(),
 110                 SBAddPrefixHashLess<SBAddFullHash,SBAddFullHash>));
 111   DCHECK(sorted(sub_full_hashes->begin(), sub_full_hashes->end(),
 112                 SBAddPrefixHashLess<SBSubFullHash,SBSubFullHash>));
 113
 114   // Factor out the prefix subs.
 115   KnockoutSubs(sub_prefixes, add_prefixes,
 116                SBAddPrefixLess<SBAddPrefix,SBSubPrefix>,
 117                SBAddPrefixLess<SBSubPrefix,SBAddPrefix>);
 118
 119   // Factor out the full-hash subs.
 120   KnockoutSubs(sub_full_hashes, add_full_hashes,
 121                SBAddPrefixHashLess<SBAddFullHash,SBSubFullHash>,
 122                SBAddPrefixHashLess<SBSubFullHash,SBAddFullHash>);
 123
 124   // Remove items from the deleted chunks.  This is done after other
 125   // processing to allow subs to knock out adds (and be removed) even
 126   // if the add's chunk is deleted.
 127   RemoveDeleted(add_prefixes, add_chunks_deleted);
 128   RemoveDeleted(sub_prefixes, sub_chunks_deleted);
 129   RemoveDeleted(add_full_hashes, add_chunks_deleted);
 130   RemoveDeleted(sub_full_hashes, sub_chunks_deleted);
 131 }