PVer4: Keep track of the smallest hashes not their sizes. Replace counters with iterators.

components/safe_browsing_db/v4_store.h

 // Copyright 2016 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.
 
 #ifndef COMPONENTS_SAFE_BROWSING_DB_V4_STORE_H_
 #define COMPONENTS_SAFE_BROWSING_DB_V4_STORE_H_
 
 #include "base/files/file_path.h"
 #include "base/memory/ref_counted.h"
 #include "base/sequenced_task_runner.h"
@@ skipping 14 matching lines @@
 // A hash prefix sent by the SafeBrowsing PVer4 service.
 typedef std::string HashPrefix;
 
 // The sorted list of hash prefixes.
 typedef std::string HashPrefixes;
 
 // Stores the list of sorted hash prefixes, by size.
 // For instance: {4: ["abcd", "bcde", "cdef", "gggg"], 5: ["fffff"]}
 typedef base::hash_map<PrefixSize, HashPrefixes> HashPrefixMap;
 
-// Stores the index of the last element merged from the HashPrefixMap for a
-// given prefix size. For instance: {4:3, 5:1} means that we have already merged
+// Stores the iterator to the last element merged from the HashPrefixMap for a
+// given prefix size.
+// For instance: {4:iter(3), 5:iter(1)} means that we have already merged
 // 3 hash prefixes of length 4, and 1 hash prefix of length 5.
-typedef base::hash_map<PrefixSize, size_t> CounterMap;
+typedef base::hash_map<PrefixSize, HashPrefixes::const_iterator> IteratorMap;
 
 // Enumerate different failure events while parsing the file read from disk for
 // histogramming purposes.  DO NOT CHANGE THE ORDERING OF THESE VALUES.
 enum StoreReadResult {
   // No errors.
   READ_SUCCESS = 0,
 
   // Reserved for errors in parsing this enum.
   UNEXPECTED_READ_FAILURE = 1,
 
@@ skipping 129 matching lines @@
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestReadFromNoHashPrefixesFile);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestWriteNoResponseType);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestWritePartialResponseType);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestWriteFullResponseType);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestReadFromFileWithUnknownProto);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestAddUnlumpedHashesWithInvalidAddition);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestAddUnlumpedHashes);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestAddUnlumpedHashesWithEmptyString);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
-                           TestGetNextSmallestPrefixSizeWithEmptyPrefixMap);
-  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestGetNextSmallestPrefixSize);
-  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestGetNextUnmergedPrefix);
+                           TestGetNextSmallestUnmergedPrefixWithEmptyPrefixMap);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestGetNextSmallestUnmergedPrefix);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestMergeUpdatesWithSameSizesInEachMap);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestMergeUpdatesWithDifferentSizesInEachMap);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestMergeUpdatesOldMapRunsOutFirst);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestMergeUpdatesAdditionsMapRunsOutFirst);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestMergeUpdatesFailsForRepeatedHashPrefix);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestReadFullResponseWithValidHashPrefixMap);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestReadFullResponseWithInvalidHashPrefixMap);
 
   // If |prefix_size| is within expected range, and |raw_hashes| is not invalid,
   // then it sets |raw_hashes| as the value at key |prefix_size| in
   // |additions_map|
   static ApplyUpdateResult AddUnlumpedHashes(PrefixSize prefix_size,
                                              const std::string& raw_hashes,
                                              HashPrefixMap* additions_map);
 
-  // Get the size of the next unmerged hash prefix in dictionary order from
-  // |hash_prefix_map|. |counter_map| is used to determine which hash prefixes
+  // Get the next unmerged hash prefix in dictionary order from
+  // |hash_prefix_map|. |iterator_map| is used to determine which hash prefixes
   // have been merged already. Returns true if there are any unmerged hash
   // prefixes in the list.
-  static bool GetNextSmallestPrefixSize(const HashPrefixMap& hash_prefix_map,
-                                        const CounterMap& counter_map,
-                                        PrefixSize* smallest_prefix_size);
+  static bool GetNextSmallestUnmergedPrefix(
+      const HashPrefixMap& hash_prefix_map,
+      const IteratorMap& iterator_map,
+      HashPrefix* smallest_hash_prefix);
 
-  // Returns the next hash prefix of length |prefix_size| from |hash_prefix_map|
-  // that hasn't been merged already. |counter_map| is used to determine the
-  // index of the next prefix of size |prefix_size| to merge.
-  static HashPrefix GetNextUnmergedPrefixForSize(
-      PrefixSize prefix_size,
-      const HashPrefixMap& hash_prefix_map,
-      const CounterMap& counter_map);
-
-  // Sets a value of 0 in |counter_map| for all keys in |hash_prefix_map|.
-  static void InitializeCounterMap(const HashPrefixMap& hash_prefix_map,
-                                   CounterMap* counter_map);
+  // Sets a value of 0 in |iterator_map| for all keys in |hash_prefix_map|.

[Nathan Parker, 2016/07/15 00:39:48]

This isn't zero, since it's an iterator, ya?

+  static void InitializeIteratorMap(const HashPrefixMap& hash_prefix_map,
+                                    IteratorMap* iterator_map);
 
   // Reserve the appropriate string size so that the string size of the merged
   // list is exact. This ignores the space that would otherwise be released by
   // deletions specified in the update because it is non-trivial to calculate
   // those deletions upfront. This isn't so bad since deletions are supposed to
   // be small and infrequent.
   static void ReserveSpaceInPrefixMap(const HashPrefixMap& other_prefixes_map,
                                       HashPrefixMap* prefix_map_to_update);
 
   // Updates the |additions_map| with the additions received in the partial
@@ skipping 22 matching lines @@
   const base::FilePath store_path_;
   HashPrefixMap hash_prefix_map_;
   const scoped_refptr<base::SequencedTaskRunner> task_runner_;
 };
 
 std::ostream& operator<<(std::ostream& os, const V4Store& store);
 
 }  // namespace safe_browsing
 
 #endif  // COMPONENTS_SAFE_BROWSING_DB_V4_STORE_H_