1c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Copyright (c) 2010 The Chromium Authors. All rights reserved. 2c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// found in the LICENSE file. 4c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 5c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "chrome/browser/safe_browsing/safe_browsing_store.h" 6c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 73345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick#include <algorithm> 83345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 921d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen#include "base/metrics/histogram.h" 1021d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen 11c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochnamespace { 12c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 13c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Find items matching between |subs| and |adds|, and remove them, 14c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// recording the item from |adds| in |adds_removed|. To minimize 15c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// copies, the inputs are processing in parallel, so |subs| and |adds| 16c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// should be compatibly ordered (either by SBAddPrefixLess or 17c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// SBAddPrefixHashLess). 18c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// 19c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// |predAS| provides add < sub, |predSA| provides sub < add, for the 20c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// tightest compare appropriate (see calls in SBProcessSubs). 21c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochtemplate <class S, class A, typename PredAS, typename PredSA> 22c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid KnockoutSubs(std::vector<S>* subs, 23c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::vector<A>* adds, 24c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch PredAS predAS, PredSA predSA, 25c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::vector<A>* adds_removed) { 26c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Keep a pair of output iterators for writing kept items. Due to 27c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // deletions, these may lag the main iterators. Using erase() on 28c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // individual items would result in O(N^2) copies. Using std::list 29c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // would work around that, at double or triple the memory cost. 30c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch typename std::vector<A>::iterator add_out = adds->begin(); 31c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch typename std::vector<S>::iterator sub_out = subs->begin(); 32c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 33c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Current location in vectors. 34c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // TODO(shess): I want these to be const_iterator, but then 35c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // std::copy() gets confused. Could snag a const_iterator add_end, 36c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // or write an inline std::copy(), but it seems like I'm doing 37c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // something wrong. 38c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch typename std::vector<A>::iterator add_iter = adds->begin(); 39c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch typename std::vector<S>::iterator sub_iter = subs->begin(); 40c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 41c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch while (add_iter != adds->end() && sub_iter != subs->end()) { 42c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // If |*sub_iter| < |*add_iter|, retain the sub. 43c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (predSA(*sub_iter, *add_iter)) { 44c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch *sub_out = *sub_iter; 45c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++sub_out; 46c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++sub_iter; 47c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 48c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // If |*add_iter| < |*sub_iter|, retain the add. 49c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } else if (predAS(*add_iter, *sub_iter)) { 50c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch *add_out = *add_iter; 51c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++add_out; 52c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++add_iter; 53c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 54c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Record equal items and drop them. 55c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } else { 56c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch adds_removed->push_back(*add_iter); 57c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++add_iter; 58c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++sub_iter; 59c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 60c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 61c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 62c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Erase any leftover gap. 63c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch adds->erase(add_out, add_iter); 64c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch subs->erase(sub_out, sub_iter); 65c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 66c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 67c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Remove items in |removes| from |full_hashes|. |full_hashes| and 68c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// |removes| should be ordered by SBAddPrefix component. 69c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochtemplate <class T> 70c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid RemoveMatchingPrefixes(const std::vector<SBAddPrefix>& removes, 71c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::vector<T>* full_hashes) { 72c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // This is basically an inline of std::set_difference(). 73c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Unfortunately, that algorithm requires that the two iterator 74c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // pairs use the same value types. 75c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 76c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Where to store kept items. 77c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch typename std::vector<T>::iterator out = full_hashes->begin(); 78c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 79c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch typename std::vector<T>::iterator hash_iter = full_hashes->begin(); 80c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::vector<SBAddPrefix>::const_iterator remove_iter = removes.begin(); 81c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 82c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch while (hash_iter != full_hashes->end() && remove_iter != removes.end()) { 83c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Keep items less than |*remove_iter|. 84c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (SBAddPrefixLess(*hash_iter, *remove_iter)) { 85c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch *out = *hash_iter; 86c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++out; 87c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++hash_iter; 88c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 89c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // No hit for |*remove_iter|, bump it forward. 90c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } else if (SBAddPrefixLess(*remove_iter, *hash_iter)) { 91c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++remove_iter; 92c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 93c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Drop equal items, there may be multiple hits. 94c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } else { 95c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch do { 96c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++hash_iter; 97c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } while (hash_iter != full_hashes->end() && 98c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch !SBAddPrefixLess(*remove_iter, *hash_iter)); 99c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch ++remove_iter; 100c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 101c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 102c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 103c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Erase any leftover gap. 104c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch full_hashes->erase(out, hash_iter); 105c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 106c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 1073345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick// Remove deleted items (|chunk_id| in |del_set|) from the vector. 1083345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merricktemplate <class T> 1093345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrickvoid RemoveDeleted(std::vector<T>* vec, const base::hash_set<int32>& del_set) { 1103345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick DCHECK(vec); 1113345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 1123345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick // Scan through the items read, dropping the items in |del_set|. 1133345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick typename std::vector<T>::iterator add_iter = vec->begin(); 1143345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick for (typename std::vector<T>::iterator iter = add_iter; 1153345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick iter != vec->end(); ++iter) { 1163345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick if (del_set.count(iter->chunk_id) == 0) { 1173345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick *add_iter = *iter; 1183345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick ++add_iter; 1193345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick } 1203345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick } 1213345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick vec->erase(add_iter, vec->end()); 1223345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick} 1233345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 12421d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsenenum MissTypes { 12521d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen MISS_TYPE_ALL, 12621d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen MISS_TYPE_FALSE, 12721d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen 12821d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // Always at the end. 12921d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen MISS_TYPE_MAX 13021d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen}; 13121d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen 132c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} // namespace 133c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 13421d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsenvoid SBCheckPrefixMisses(const std::vector<SBAddPrefix>& add_prefixes, 13521d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen const std::set<SBPrefix>& prefix_misses) { 13621d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen if (prefix_misses.empty()) 13721d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen return; 13821d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen 13921d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // Record a hit for all prefixes which missed when sent to the 14021d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // server. 14121d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen for (size_t i = 0; i < prefix_misses.size(); ++i) { 14221d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen UMA_HISTOGRAM_ENUMERATION("SB2.BloomFilterFalsePositives", 14321d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen MISS_TYPE_ALL, MISS_TYPE_MAX); 14421d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen } 14521d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen 14621d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // Collect the misses which are not present in |add_prefixes|. 14721d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // Since |add_prefixes| can contain multiple copies of the same 14821d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // prefix, it is not sufficient to count the number of elements 14921d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // present in both collections. 15021d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen std::set<SBPrefix> false_misses(prefix_misses.begin(), prefix_misses.end()); 15121d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen for (size_t i = 0; i < add_prefixes.size(); ++i) { 15221d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // |erase()| on an absent element should cost like |find()|. 15321d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen false_misses.erase(add_prefixes[i].prefix); 15421d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen } 15521d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen 15621d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // Record a hit for prefixes which we shouldn't have sent in the 15721d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // first place. 15821d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen for (size_t i = 0; i < false_misses.size(); ++i) { 15921d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen UMA_HISTOGRAM_ENUMERATION("SB2.BloomFilterFalsePositives", 16021d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen MISS_TYPE_FALSE, MISS_TYPE_MAX); 16121d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen } 16221d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen 16321d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // Divide |MISS_TYPE_FALSE| by |MISS_TYPE_ALL| to get the 16421d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen // bloom-filter false-positive rate. 16521d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen} 16621d179b334e59e9a3bfcaed4c4430bef1bc5759dKristian Monsen 167c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochvoid SBProcessSubs(std::vector<SBAddPrefix>* add_prefixes, 168c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::vector<SBSubPrefix>* sub_prefixes, 169c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::vector<SBAddFullHash>* add_full_hashes, 1703345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick std::vector<SBSubFullHash>* sub_full_hashes, 1713345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick const base::hash_set<int32>& add_chunks_deleted, 1723345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick const base::hash_set<int32>& sub_chunks_deleted) { 173c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // It is possible to structure templates and template 174c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // specializations such that the following calls work without having 175c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // to qualify things. It becomes very arbitrary, though, and less 176c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // clear how things are working. 177c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 178c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Sort the inputs by the SBAddPrefix bits. 179c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::sort(add_prefixes->begin(), add_prefixes->end(), 180c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch SBAddPrefixLess<SBAddPrefix,SBAddPrefix>); 181c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::sort(sub_prefixes->begin(), sub_prefixes->end(), 182c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch SBAddPrefixLess<SBSubPrefix,SBSubPrefix>); 183c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::sort(add_full_hashes->begin(), add_full_hashes->end(), 184c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch SBAddPrefixHashLess<SBAddFullHash,SBAddFullHash>); 185c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::sort(sub_full_hashes->begin(), sub_full_hashes->end(), 186c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch SBAddPrefixHashLess<SBSubFullHash,SBSubFullHash>); 187c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 188c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Factor out the prefix subs. 189c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::vector<SBAddPrefix> removed_adds; 190c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch KnockoutSubs(sub_prefixes, add_prefixes, 191c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch SBAddPrefixLess<SBAddPrefix,SBSubPrefix>, 192c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch SBAddPrefixLess<SBSubPrefix,SBAddPrefix>, 193c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch &removed_adds); 194c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 195c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Remove the full-hashes corrosponding to the adds which 196c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // KnockoutSubs() removed. Processing these w/in KnockoutSubs() 197c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // would make the code more complicated, and they are very small 198c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // relative to the prefix lists so the gain would be modest. 199c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch RemoveMatchingPrefixes(removed_adds, add_full_hashes); 200c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch RemoveMatchingPrefixes(removed_adds, sub_full_hashes); 201c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 2023345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick // http://crbug.com/52385 203c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // TODO(shess): AFAICT this pass is not done on the trunk. I 204c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // believe that's a bug, but it may not matter because full-hash 205c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // subs almost never happen (I think you'd need multiple collisions 206c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // where one of the sites stopped being flagged?). Enable this once 207c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // everything is in. [if(0) instead of #ifdef 0 to make sure it 208c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // compiles.] 209c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch if (0) { 210c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch // Factor out the full-hash subs. 211c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch std::vector<SBAddFullHash> removed_full_adds; 212c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch KnockoutSubs(sub_full_hashes, add_full_hashes, 213c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch SBAddPrefixHashLess<SBAddFullHash,SBSubFullHash>, 214c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch SBAddPrefixHashLess<SBSubFullHash,SBAddFullHash>, 215c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch &removed_full_adds); 216c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch } 2173345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 2183345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick // Remove items from the deleted chunks. This is done after other 2193345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick // processing to allow subs to knock out adds (and be removed) even 2203345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick // if the add's chunk is deleted. 2213345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick RemoveDeleted(add_prefixes, add_chunks_deleted); 2223345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick RemoveDeleted(sub_prefixes, sub_chunks_deleted); 2233345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick RemoveDeleted(add_full_hashes, add_chunks_deleted); 2243345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick RemoveDeleted(sub_full_hashes, sub_chunks_deleted); 225c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 226