PVer4: V4Store: Check whether a hash prefix exists for a full hash

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 b021cd270c933ab99ce26e23000c630cd3bacabc..b8acd3a59f8b8acb24a587741deb449113e7cd2f 100644
--- a/components/safe_browsing_db/v4_store.cc
+++ b/components/safe_browsing_db/v4_store.cc
@@ -213,7 +213,7 @@ bool V4Store::GetNextSmallestUnmergedPrefix(
     const HashPrefixes& hash_prefixes = hash_prefix_map.at(prefix_size);
     if (prefix_size <=
         static_cast<PrefixSize>(std::distance(start, hash_prefixes.end()))) {
-      current_hash_prefix = std::string(start, start + prefix_size);
+      current_hash_prefix = HashPrefix(start, start + prefix_size);
       if (!has_unmerged || *smallest_hash_prefix > current_hash_prefix) {
         has_unmerged = true;
         smallest_hash_prefix->swap(current_hash_prefix);
@@ -425,4 +425,41 @@ StoreWriteResult V4Store::WriteToDisk(
   return WRITE_SUCCESS;
 }
 
+HashPrefix V4Store::GetMatchingHashPrefix(const FullHash& full_hash) {
+  DCHECK_EQ(32u, full_hash.size());
+  for (const auto& pair : hash_prefix_map_) {
+    const PrefixSize& prefix_size = pair.first;
+    const HashPrefixes& hash_prefixes = pair.second;
+    const HashPrefix& hash_prefix = full_hash.substr(0, prefix_size);

[Nathan Parker, 2016/07/19 23:01:31]

This is a reference to a temporary... I'm not sure about the lifetime of that
here.  Might be safer to make it a non-reference, since there has to be a copy
anyway.

[vakh (use Gerrit instead), 2016/07/20 00:24:51]

Done.

+    if (HashPrefixMatches(hash_prefix, hash_prefixes.begin(),
+                          hash_prefixes.end())) {
+      return hash_prefix;
+    }
+  }
+  return HashPrefix();
+}
+
+// static
+bool V4Store::HashPrefixMatches(const HashPrefix& hash_prefix,
+                                const HashPrefixes::const_iterator& begin,
+                                const HashPrefixes::const_iterator& end) {
+  if (begin == end) {
+    return false;
+  }
+  size_t distance = std::distance(begin, end);
+  const PrefixSize& prefix_size = hash_prefix.length();

[Nathan Parker, 2016/07/19 23:01:31]

no need for reference, since it's just as cheap (cheaper, actually) to copy the
length than it is to copy a ptr to the length.  And this is a reference to a
temporary.

[vakh (use Gerrit instead), 2016/07/20 00:24:52]

Done.

+  DCHECK_EQ(0u, distance % prefix_size);
+  size_t mid_prefix_index = ((distance / prefix_size) / 2) * prefix_size;
+  HashPrefixes::const_iterator mid = begin + mid_prefix_index;
+  HashPrefix mid_prefix = HashPrefix(mid, mid + prefix_size);

[Nathan Parker, 2016/07/19 23:01:31]

This is making a copy, which I suppose would copy about log2(num_hashes) of the
prefixes.  To avoid it, you could switch to StringPiece.  I still thing
HashPrefix could be a StringPiece in most cases.

[vakh (use Gerrit instead), 2016/07/20 00:24:52]

It copies exactly prefix_size bytes.

+  if (mid_prefix == hash_prefix) {
+    return true;
+  }
+  if (hash_prefix < mid_prefix) {

[Nathan Parker, 2016/07/19 23:01:31]

You can avoid iterating over both strings twice (in most cases) by using
std::string::compare(..). It'll return <, =, or > 0 with at most one pass over
the strings.

In fact... it allows you to compare against a part of a string, which avoids the
copying above.

[vakh (use Gerrit instead), 2016/07/20 00:24:52]

Done.

+    return HashPrefixMatches(hash_prefix, begin, mid);
+  } else {
+    return HashPrefixMatches(hash_prefix, mid + prefix_size, end);
+  }
+}
+
 }  // namespace safe_browsing