Switching to flat_sets in HQP.

components/omnibox/browser/url_index_private_data.cc

 // Copyright (c) 2012 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.
 
 #include "components/omnibox/browser/url_index_private_data.h"
 
 #include <stdint.h>
 
 #include <functional>
 #include <iterator>
@@ skipping 465 matching lines @@
   HistoryIDVector history_ids;
   String16Vector words(unsorted_words);
   // Sort the words into the longest first as such are likely to narrow down
   // the results quicker. Also, single character words are the most expensive
   // to process so save them for last.
   std::sort(words.begin(), words.end(), LengthGreater);
 
   // TODO(dyaroshev): write a generic algorithm(crbug.com/696167).
   for (String16Vector::iterator iter = words.begin(); iter != words.end();
        ++iter) {
-    base::string16 uni_word = *iter;
-    HistoryIDSet term_history_set = HistoryIDsForTerm(uni_word);
+    HistoryIDSet term_history_set = HistoryIDsForTerm(*iter);
     if (term_history_set.empty()) {

[Peter Kasting, 2017/03/02 22:54:33]

Nit: No {}

-      history_ids.clear();
-      break;
+      return HistoryIDVector();
     }
     if (iter == words.begin()) {
       history_ids = {term_history_set.begin(), term_history_set.end()};
     } else {
       history_ids = base::STLSetIntersection<HistoryIDVector>(history_ids,
                                                               term_history_set);
     }
   }
   return history_ids;
 }
@@ skipping 80 matching lines @@
         return HistoryIDSet();
       }
       // Or there may not have been a prefix from which to start.
       word_id_set = prefix_chars.empty() ? std::move(leftover_set)
                                          : base::STLSetIntersection<WordIDSet>(
                                                word_id_set, leftover_set);
     }
 
     // We must filter the word list because the resulting word set surely
     // contains words which do not have the search term as a proper subset.
-    for (WordIDSet::iterator word_set_iter = word_id_set.begin();
-         word_set_iter != word_id_set.end(); ) {
-      if (word_list_[*word_set_iter].find(term) == base::string16::npos)
-        word_set_iter = word_id_set.erase(word_set_iter);
-      else
-        ++word_set_iter;
-    }
+    word_id_set.erase(std::remove_if(word_id_set.begin(), word_id_set.end(),
+                                     [&](WordID word_id) {
+                                       return word_list_[word_id].find(term) ==
+                                              base::string16::npos;
+                                     }),
+                      word_id_set.end());
   } else {
     word_id_set = WordIDSetForTermChars(Char16SetFromString16(term));
   }
 
   // If any words resulted then we can compose a set of history IDs by unioning
   // the sets from each word.
-  HistoryIDSet history_id_set;
+  // We use |buffer| because it's more efficient to collect everything and then
+  // construct a flat_set than to insert elements one by one.
+  HistoryIDVector buffer;
   for (WordID word_id : word_id_set) {
     WordIDHistoryMap::iterator word_iter = word_id_history_map_.find(word_id);
     if (word_iter != word_id_history_map_.end()) {
       HistoryIDSet& word_history_id_set(word_iter->second);
-      history_id_set.insert(word_history_id_set.begin(),
-                            word_history_id_set.end());
+      buffer.insert(buffer.end(), word_history_id_set.begin(),
+                    word_history_id_set.end());
     }
   }
+  HistoryIDSet history_id_set(buffer.begin(), buffer.end());
 
   // Record a new cache entry for this word if the term is longer than
   // a single character.
   if (term_length > 1)
     search_term_cache_[term] = SearchTermCacheItem(word_id_set, history_id_set);
 
   return history_id_set;
 }
 
 WordIDSet URLIndexPrivateData::WordIDSetForTermChars(
     const Char16Set& term_chars) {
   // TODO(dyaroshev): write a generic algorithm(crbug.com/696167).
 
   WordIDSet word_id_set;
   for (Char16Set::const_iterator c_iter = term_chars.begin();
        c_iter != term_chars.end(); ++c_iter) {
     CharWordIDMap::iterator char_iter = char_word_map_.find(*c_iter);
-    if (char_iter == char_word_map_.end()) {
-      // A character was not found so there are no matching results: bail.
-      word_id_set.clear();
-      break;
-    }
-    WordIDSet& char_word_id_set(char_iter->second);
+    // A character was not found so there are no matching results: bail.
+    if (char_iter == char_word_map_.end())
+      return WordIDSet();
+
+    const WordIDSet& char_word_id_set(char_iter->second);
     // It is possible for there to no longer be any words associated with
     // a particular character. Give up in that case.
-    if (char_word_id_set.empty()) {
-      word_id_set.clear();
-      break;
-    }
+    if (char_word_id_set.empty())
+      return WordIDSet();
 
     if (c_iter == term_chars.begin()) {
-      // First character results becomes base set of results.
       word_id_set = char_word_id_set;
     } else {
-      // Subsequent character results get intersected in.
       word_id_set =
           base::STLSetIntersection<WordIDSet>(word_id_set, char_word_id_set);
     }
   }
   return word_id_set;
 }
 
 void URLIndexPrivateData::HistoryIdsToScoredMatches(
     HistoryIDVector history_ids,
     const base::string16& lower_raw_string,
@@ skipping 44 matching lines @@
     const history::URLRow& hist_item = hist_pos->second.url_row;
     auto starts_pos = word_starts_map_.find(history_id);
     DCHECK(starts_pos != word_starts_map_.end());
     ScoredHistoryMatch new_scored_match(
         hist_item, hist_pos->second.visits, lower_raw_string, lower_raw_terms,
         lower_terms_to_word_starts_offsets, starts_pos->second,
         bookmark_model && bookmark_model->IsBookmarked(hist_item.url()),
         num_matches, now);
     // Filter new matches that ended up scoring 0. (These are usually matches
     // which didn't match the user's raw terms.)
-    if (new_scored_match.raw_score != 0)
+    if (new_scored_match.raw_score > 0)
       scored_items->push_back(std::move(new_scored_match));
   }
 }
 
 // static
 void URLIndexPrivateData::CalculateWordStartsOffsets(
     const String16Vector& lower_terms,
     WordStarts* lower_terms_to_word_starts_offsets) {
   // Calculate offsets for each term.  For instance, the offset for
   // ".net" should be 1, indicating that the actual word-part of the term
@@ skipping 558 matching lines @@
   // First cut: typed count, visit count, recency.
   // TODO(mrossetti): This is too simplistic. Consider an approach which ranks
   // recently visited (within the last 12/24 hours) as highly important. Get
   // input from mpearson.
   if (r1.typed_count() != r2.typed_count())
     return (r1.typed_count() > r2.typed_count());
   if (r1.visit_count() != r2.visit_count())
     return (r1.visit_count() > r2.visit_count());
   return (r1.last_visit() > r2.last_visit());
 }