Home | History | Annotate | Download | only in safe_browsing 
      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 }
    132