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

components/safe_browsing_db/v4_store.cc

Index: components/safe_browsing_db/v4_store.cc
diff --git a/components/safe_browsing_db/v4_store.cc b/components/safe_browsing_db/v4_store.cc
index e6195767d0161575bb9f81d616a3f581bc318b3c..a2a45de684664b24b5d95274b3ce7430efb59ba5 100644
--- a/components/safe_browsing_db/v4_store.cc
+++ b/components/safe_browsing_db/v4_store.cc
@@ -192,17 +192,17 @@ ApplyUpdateResult V4Store::AddUnlumpedHashes(PrefixSize prefix_size,
 
 // static
 bool V4Store::GetNextSmallestPrefixSize(const HashPrefixMap& hash_prefix_map,
-                                        const CounterMap& counter_map,
+                                        const IteratorMap& iterator_map,
                                         PrefixSize* smallest_prefix_size) {
   HashPrefix smallest_prefix, current_prefix;
-  for (const auto& counter_pair : counter_map) {
-    PrefixSize prefix_size = counter_pair.first;
-    size_t index = counter_pair.second;
-    size_t sized_index = prefix_size * index;
+  for (const auto& iterator_pair : iterator_map) {
+    PrefixSize prefix_size = iterator_pair.first;
+    HashPrefixes::const_iterator start = iterator_pair.second;
+    HashPrefixes::const_iterator end = start + prefix_size;
 
     const HashPrefixes& hash_prefixes = hash_prefix_map.at(prefix_size);
-    if (sized_index < hash_prefixes.size()) {
-      current_prefix = hash_prefixes.substr(sized_index, prefix_size);
+    if (end <= hash_prefixes.end()) {
+      current_prefix = std::string(start, end);
       if (smallest_prefix.empty() || smallest_prefix > current_prefix) {
         smallest_prefix = current_prefix;

[Nathan Parker, 2016/07/14 22:09:32]

could do
smallest_prefix.swap(current_prefix)

[vakh (use Gerrit instead), 2016/07/14 23:10:41]

Done.

         *smallest_prefix_size = prefix_size;
@@ -213,10 +213,10 @@ bool V4Store::GetNextSmallestPrefixSize(const HashPrefixMap& hash_prefix_map,
 }
 
 // static
-void V4Store::InitializeCounterMap(const HashPrefixMap& hash_prefix_map,
-                                   CounterMap* counter_map) {
+void V4Store::InitializeIteratorMap(const HashPrefixMap& hash_prefix_map,
+                                    IteratorMap* iterator_map) {
   for (const auto& map_pair : hash_prefix_map) {
-    (*counter_map)[map_pair.first] = 0;
+    (*iterator_map)[map_pair.first] = map_pair.second.begin();
   }
 }
 
@@ -224,11 +224,10 @@ void V4Store::InitializeCounterMap(const HashPrefixMap& hash_prefix_map,
 HashPrefix V4Store::GetNextUnmergedPrefixForSize(
     PrefixSize prefix_size,
     const HashPrefixMap& hash_prefix_map,
-    const CounterMap& counter_map) {
-  const HashPrefixes& hash_prefixes = hash_prefix_map.at(prefix_size);
-  size_t index_within_list = counter_map.at(prefix_size);
-  size_t sized_index = prefix_size * index_within_list;
-  return hash_prefixes.substr(sized_index, prefix_size);
+    const IteratorMap& iterator_map) {
+  HashPrefixes::const_iterator start = iterator_map.at(prefix_size);
+  HashPrefixes::const_iterator end = start + prefix_size;
+  return std::string(start, end);

[Nathan Parker, 2016/07/14 22:09:32]

could add a dcheck that end <= hash_prefix_map.at(prefix_size).end().  Or...
remove hash_prefix_map from the function altogether.

[vakh (use Gerrit instead), 2016/07/14 23:10:41]

Even better. Removed the method entirely and made the MergeUpdate method
simpler.

 }
 
 // static
@@ -255,16 +254,16 @@ ApplyUpdateResult V4Store::MergeUpdate(const HashPrefixMap& old_prefixes_map,
   ReserveSpaceInPrefixMap(additions_map, &hash_prefix_map_);
 
   PrefixSize next_size_for_old;
-  CounterMap old_counter_map;
-  InitializeCounterMap(old_prefixes_map, &old_counter_map);
+  IteratorMap old_iterator_map;
+  InitializeIteratorMap(old_prefixes_map, &old_iterator_map);
   bool old_has_unmerged = GetNextSmallestPrefixSize(
-      old_prefixes_map, old_counter_map, &next_size_for_old);
+      old_prefixes_map, old_iterator_map, &next_size_for_old);
 
   PrefixSize next_size_for_additions;
-  CounterMap additions_counter_map;
-  InitializeCounterMap(additions_map, &additions_counter_map);
+  IteratorMap additions_iterator_map;
+  InitializeIteratorMap(additions_map, &additions_iterator_map);
   bool additions_has_unmerged = GetNextSmallestPrefixSize(
-      additions_map, additions_counter_map, &next_size_for_additions);
+      additions_map, additions_iterator_map, &next_size_for_additions);
 
   // Classical merge sort.
   // The two constructs to merge are maps: old_prefixes_map, additions_map.
@@ -277,7 +276,7 @@ ApplyUpdateResult V4Store::MergeUpdate(const HashPrefixMap& old_prefixes_map,
     if (old_has_unmerged) {
       // Get the lexographically smallest hash prefix from the old store.
       next_smallest_prefix_old = GetNextUnmergedPrefixForSize(
-          next_size_for_old, old_prefixes_map, old_counter_map);
+          next_size_for_old, old_prefixes_map, old_iterator_map);
     }
 
     // Additions map still has elements that need to be merged.
@@ -285,7 +284,7 @@ ApplyUpdateResult V4Store::MergeUpdate(const HashPrefixMap& old_prefixes_map,
       // Get the lexographically smallest hash prefix from the additions in the
       // latest update from the server.
       next_smallest_prefix_additions = GetNextUnmergedPrefixForSize(
-          next_size_for_additions, additions_map, additions_counter_map);
+          next_size_for_additions, additions_map, additions_iterator_map);
     }
 
     // If the same hash prefix appears in the existing store and the additions
@@ -305,24 +304,25 @@ ApplyUpdateResult V4Store::MergeUpdate(const HashPrefixMap& old_prefixes_map,
     if (pick_from_old) {
       hash_prefix_map_[next_size_for_old] += next_smallest_prefix_old;
 
-      // Update the counter map, which means that we have merged one hash
+      // Update the iterator map, which means that we have merged one hash
       // prefix of size |next_size_for_old| from the old store.
-      old_counter_map[next_size_for_old]++;
+      old_iterator_map[next_size_for_old] += next_size_for_old;
 
       // Find the next smallest unmerged element in the old store's map.
       old_has_unmerged = GetNextSmallestPrefixSize(
-          old_prefixes_map, old_counter_map, &next_size_for_old);
+          old_prefixes_map, old_iterator_map, &next_size_for_old);
     } else {
       hash_prefix_map_[next_size_for_additions] +=
           next_smallest_prefix_additions;
 
-      // Update the counter map, which means that we have merged one hash
+      // Update the iterator map, which means that we have merged one hash
       // prefix of size |next_size_for_additions| from the update.
-      additions_counter_map[next_size_for_additions]++;
+      additions_iterator_map[next_size_for_additions] +=
+          next_size_for_additions;
 
       // Find the next smallest unmerged element in the additions map.
       additions_has_unmerged = GetNextSmallestPrefixSize(
-          additions_map, additions_counter_map, &next_size_for_additions);
+          additions_map, additions_iterator_map, &next_size_for_additions);
     }
   }