1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_ 6 #define CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_ 7 #pragma once 8 9 #include <map> 10 #include <set> 11 #include <vector> 12 13 #include "base/basictypes.h" 14 #include "base/string16.h" 15 16 class BookmarkNode; 17 class Profile; 18 class QueryNode; 19 class QueryParser; 20 21 namespace bookmark_utils { 22 struct TitleMatch; 23 } 24 25 namespace history { 26 class URLDatabase; 27 } 28 29 // BookmarkIndex maintains an index of the titles of bookmarks for quick 30 // look up. BookmarkIndex is owned and maintained by BookmarkModel, you 31 // shouldn't need to interact directly with BookmarkIndex. 32 // 33 // BookmarkIndex maintains the index (index_) as a map of sets. The map (type 34 // Index) maps from a lower case string to the set (type NodeSet) of 35 // BookmarkNodes that contain that string in their title. 36 37 class BookmarkIndex { 38 public: 39 explicit BookmarkIndex(Profile* profile); 40 ~BookmarkIndex(); 41 42 // Invoked when a bookmark has been added to the model. 43 void Add(const BookmarkNode* node); 44 45 // Invoked when a bookmark has been removed from the model. 46 void Remove(const BookmarkNode* node); 47 48 // Returns up to |max_count| of bookmarks containing the text |query|. 49 void GetBookmarksWithTitlesMatching( 50 const string16& query, 51 size_t max_count, 52 std::vector<bookmark_utils::TitleMatch>* results); 53 54 private: 55 typedef std::set<const BookmarkNode*> NodeSet; 56 typedef std::map<string16, NodeSet> Index; 57 58 struct Match; 59 typedef std::vector<Match> Matches; 60 61 // Pairs BookmarkNodes and the number of times the nodes' URLs were typed. 62 // Used to sort Matches in decreasing order of typed count. 63 typedef std::pair<const BookmarkNode*, int> NodeTypedCountPair; 64 typedef std::vector<NodeTypedCountPair> NodeTypedCountPairs; 65 66 // Extracts |matches.nodes| into NodeTypedCountPairs and sorts the pairs in 67 // decreasing order of typed count. 68 void SortMatches(const Matches& matches, 69 NodeTypedCountPairs* node_typed_counts) const; 70 71 // Extracts BookmarkNodes from |match| and retrieves typed counts for each 72 // node from the in-memory database. Inserts pairs containing the node and 73 // typed count into the vector |node_typed_counts|. |node_typed_counts| is 74 // sorted in decreasing order of typed count. 75 void ExtractBookmarkNodePairs(history::URLDatabase* url_db, 76 const Match& match, 77 NodeTypedCountPairs* node_typed_counts) const; 78 79 // Sort function for NodeTypedCountPairs. We sort in decreasing order of typed 80 // count so that the best matches will always be added to the results. NodeTypedCountPairSortFunc(const NodeTypedCountPair & a,const NodeTypedCountPair & b)81 static bool NodeTypedCountPairSortFunc(const NodeTypedCountPair& a, 82 const NodeTypedCountPair& b) { 83 return a.second > b.second; 84 } 85 86 // Add |node| to |results| if the node matches the query. 87 void AddMatchToResults(const BookmarkNode* node, 88 QueryParser* parser, 89 const std::vector<QueryNode*>& query_nodes, 90 std::vector<bookmark_utils::TitleMatch>* results); 91 92 // Populates |matches| for the specified term. If |first_term| is true, this 93 // is the first term in the query. Returns true if there is at least one node 94 // matching the term. 95 bool GetBookmarksWithTitleMatchingTerm(const string16& term, 96 bool first_term, 97 Matches* matches); 98 99 // Iterates over |matches| updating each Match's nodes to contain the 100 // intersection of the Match's current nodes and the nodes at |index_i|. 101 // If the intersection is empty, the Match is removed. 102 // 103 // This is invoked from GetBookmarksWithTitleMatchingTerm. 104 void CombineMatchesInPlace(const Index::const_iterator& index_i, 105 Matches* matches); 106 107 // Iterates over |current_matches| calculating the intersection between the 108 // Match's nodes and the nodes at |index_i|. If the intersection between the 109 // two is non-empty, a new match is added to |result|. 110 // 111 // This differs from CombineMatchesInPlace in that if the intersection is 112 // non-empty the result is added to result, not combined in place. This 113 // variant is used for prefix matching. 114 // 115 // This is invoked from GetBookmarksWithTitleMatchingTerm. 116 void CombineMatches(const Index::const_iterator& index_i, 117 const Matches& current_matches, 118 Matches* result); 119 120 // Returns the set of query words from |query|. 121 std::vector<string16> ExtractQueryWords(const string16& query); 122 123 // Adds |node| to |index_|. 124 void RegisterNode(const string16& term, const BookmarkNode* node); 125 126 // Removes |node| from |index_|. 127 void UnregisterNode(const string16& term, const BookmarkNode* node); 128 129 Index index_; 130 131 Profile* profile_; 132 133 DISALLOW_COPY_AND_ASSIGN(BookmarkIndex); 134 }; 135 136 #endif // CHROME_BROWSER_BOOKMARKS_BOOKMARK_INDEX_H_ 137