Merge the hash prefixes from the old store and the additions in the partial

components/safe_browsing_db/v4_store.h

Index: components/safe_browsing_db/v4_store.h
diff --git a/components/safe_browsing_db/v4_store.h b/components/safe_browsing_db/v4_store.h
index bbafbe73dfafe2f8f6957bceed821acc46e0101e..27b179875bb98eda0d3d90b79b8751b5e6a6edaf 100644
--- a/components/safe_browsing_db/v4_store.h
+++ b/components/safe_browsing_db/v4_store.h
@@ -18,6 +18,25 @@ class V4Store;
 typedef base::Callback<void(std::unique_ptr<V4Store>)>
     UpdatedStoreReadyCallback;
 
+// The size of the hash prefix, in bytes. It should be between 4 to 32 (full
+// hash).
+typedef size_t PrefixSize;
+
+// A hash prefix sent by the SafeBrowsing PVer4 service.
+typedef std::unique_ptr<char> HashPrefix;
+
+// The sorted list of hash prefixes.
+typedef std::vector<HashPrefix> 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
+// 3 hash prefixes of length 4, and 1 hash prefix of length 5.
+typedef base::hash_map<PrefixSize, size_t> CounterMap;
+
 // Enumerate different failure events while parsing the file read from disk for
 // histogramming purposes.  DO NOT CHANGE THE ORDERING OF THESE VALUES.
 enum StoreReadResult {
@@ -79,6 +98,24 @@ enum StoreWriteResult {
   STORE_WRITE_RESULT_MAX
 };
 
+// Enumerate different events while merging the update fetched fom the server
+// for histogramming purposes.
+// DO NOT CHANGE THE ORDERING OF THESE VALUES.
+enum MergeUpdateResult {
+  // No errors.
+  MERGE_SUCCESS = 0,
+
+  // Reserved for errors in parsing this enum.
+  UNEXPECTED_MERGE_FAILURE = 1,
+
+  // The number of bytes in additions isn't a multiple of prefix size.
+  ADDITIONS_SIZE_UNEXPECTED_FAILURE = 2,
+
+  // Memory space for histograms is determined by the max.  ALWAYS
+  // ADD NEW VALUES BEFORE THIS ONE.
+  MERGE_UPDATE_RESULT_MAX
+};
+
 // Factory for creating V4Store. Tests implement this factory to create fake
 // stores for testing.
 class V4StoreFactory {
@@ -127,6 +164,48 @@ class V4Store {
   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);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestMergeUpdates);
+
+  // Breaks down the |lumped_hashes|, which is a single string, into hash
+  // prefixes, each of size |prefix_size|. These prefixes are stored in a
+  // |prefix_map| as a vector, with |prefix_size| as key.
+  static MergeUpdateResult AddUnlumpedHashes(PrefixSize prefix_size,
+                                             const std::string& lumped_hashes,
+                                             HashPrefixMap* prefix_map);
+
+  // 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,
+      HashPrefixMap& hash_prefix_map,
+      const CounterMap& counter_map);
+
+  // Generates the HashPrefixMap for the additions received in the partial
+  // update from the seriver.
+  static HashPrefixMap GetHashPrefixMapFromAdditions(
+      const ::google::protobuf::RepeatedPtrField<ThreatEntrySet>& additions);
+
+  static CounterMap GetInitializedCounterMap(
+      const HashPrefixMap& hash_prefix_map);
+
+  static bool GetNextSmallestPrefixSize(const HashPrefixMap& hash_prefix_map,
+                                        const CounterMap& counter_map,
+                                        PrefixSize* smallest_prefix_size);
+
+  // Merges the prefix map from the old store and the update to populate the
+  // prefix map for the current store.
+  // TODO(vakh): Process removals also.
+  void MergeUpdate(HashPrefixMap& old_hash_prefix_map,
+                   HashPrefixMap& additions_map);
 
   // Reads the state of the store from the file on disk and returns the reason
   // for the failure or reports success.
@@ -140,6 +219,7 @@ class V4Store {
   // update response.
   std::string state_;
   const base::FilePath store_path_;
+  HashPrefixMap hash_prefix_map_;
   const scoped_refptr<base::SequencedTaskRunner> task_runner_;
 };