PrefixSet as an alternate to BloomFilter for safe-browsing.

The safe-browsing prefix data is uniformly distributed across the
32-bit integer space.  When sorted, the average delta between items is
about 8,000, which can be encoded in a 16-bit integer.  PrefixSet
takes advantage of this to compress the prefixes into a structure
which is relatively efficient to query.

The current CL adds the new structure, but continues to use the bloom
filter to control things.  Histograms are logged to track differences
in results.

BUG=71832
TEST=none

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

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

1 files changed, 7 insertions, 0 deletions

diff --git a/chrome/browser/safe_browsing/safe_browsing_database.h b/chrome/browser/safe_browsing/safe_browsing_database.h
index 4b6890d..d233ec6 100644
--- a/chrome/browser/safe_browsing/safe_browsing_database.h
+++ b/chrome/browser/safe_browsing/safe_browsing_database.h
@@ -20,6 +20,10 @@ namespace base {
   class Time;
 }
 
+namespace safe_browsing {
+class PrefixSet;
+}
+
 class BloomFilter;
 class GURL;
 class MessageLoop;
@@ -276,6 +280,9 @@ class SafeBrowsingDatabaseNew : public SafeBrowsingDatabase {
   // Set to true if any chunks are added or deleted during an update.
   // Used to optimize away database update.
   bool change_detected_;
+
+  // Used to check if a prefix was in the database.
+  scoped_ptr<safe_browsing::PrefixSet> prefix_set_;
 };
 
 #endif  // CHROME_BROWSER_SAFE_BROWSING_SAFE_BROWSING_DATABASE_H_