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