Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(349)

Side by Side Diff: components/url_matcher/substring_set_matcher.h

Issue 1549993003: Switch to standard integer types in components/, part 4 of 4. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Created 4 years, 12 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
1 // Copyright 2013 The Chromium Authors. All rights reserved. 1 // Copyright 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #ifndef COMPONENTS_URL_MATCHER_SUBSTRING_SET_MATCHER_H_ 5 #ifndef COMPONENTS_URL_MATCHER_SUBSTRING_SET_MATCHER_H_
6 #define COMPONENTS_URL_MATCHER_SUBSTRING_SET_MATCHER_H_ 6 #define COMPONENTS_URL_MATCHER_SUBSTRING_SET_MATCHER_H_
7 7
8 #include <stdint.h>
9
8 #include <limits> 10 #include <limits>
9 #include <map> 11 #include <map>
10 #include <set> 12 #include <set>
11 #include <string> 13 #include <string>
12 #include <vector> 14 #include <vector>
13 15
14 #include "base/basictypes.h" 16 #include "base/macros.h"
15 #include "components/url_matcher/string_pattern.h" 17 #include "components/url_matcher/string_pattern.h"
16 #include "components/url_matcher/url_matcher_export.h" 18 #include "components/url_matcher/url_matcher_export.h"
17 19
18 namespace url_matcher { 20 namespace url_matcher {
19 21
20 // Class that store a set of string patterns and can find for a string S, 22 // Class that store a set of string patterns and can find for a string S,
21 // which string patterns occur in S. 23 // which string patterns occur in S.
22 class URL_MATCHER_EXPORT SubstringSetMatcher { 24 class URL_MATCHER_EXPORT SubstringSetMatcher {
23 public: 25 public:
24 SubstringSetMatcher(); 26 SubstringSetMatcher();
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after
75 // text[i + k] at depth k + 1, we follow a failure edge. This edge 77 // text[i + k] at depth k + 1, we follow a failure edge. This edge
76 // corresponds to the longest proper suffix of text[i, ..., i + k - 1] that 78 // corresponds to the longest proper suffix of text[i, ..., i + k - 1] that
77 // is a prefix of any registered pattern. 79 // is a prefix of any registered pattern.
78 // 80 //
79 // If your brain thinks "Forget it, let's go shopping.", don't worry. 81 // If your brain thinks "Forget it, let's go shopping.", don't worry.
80 // Take a nap and read an introductory text on the Aho Corasick algorithm. 82 // Take a nap and read an introductory text on the Aho Corasick algorithm.
81 // It will make sense. Eventually. 83 // It will make sense. Eventually.
82 class AhoCorasickNode { 84 class AhoCorasickNode {
83 public: 85 public:
84 // Key: label of the edge, value: node index in |tree_| of parent class. 86 // Key: label of the edge, value: node index in |tree_| of parent class.
85 typedef std::map<char, uint32> Edges; 87 typedef std::map<char, uint32_t> Edges;
86 typedef std::set<StringPattern::ID> Matches; 88 typedef std::set<StringPattern::ID> Matches;
87 89
88 static const uint32 kNoSuchEdge; // Represents an invalid node index. 90 static const uint32_t kNoSuchEdge; // Represents an invalid node index.
89 91
90 AhoCorasickNode(); 92 AhoCorasickNode();
91 ~AhoCorasickNode(); 93 ~AhoCorasickNode();
92 AhoCorasickNode(const AhoCorasickNode& other); 94 AhoCorasickNode(const AhoCorasickNode& other);
93 AhoCorasickNode& operator=(const AhoCorasickNode& other); 95 AhoCorasickNode& operator=(const AhoCorasickNode& other);
94 96
95 uint32 GetEdge(char c) const; 97 uint32_t GetEdge(char c) const;
96 void SetEdge(char c, uint32 node); 98 void SetEdge(char c, uint32_t node);
97 const Edges& edges() const { return edges_; } 99 const Edges& edges() const { return edges_; }
98 100
99 uint32 failure() const { return failure_; } 101 uint32_t failure() const { return failure_; }
100 void set_failure(uint32 failure) { failure_ = failure; } 102 void set_failure(uint32_t failure) { failure_ = failure; }
101 103
102 void AddMatch(StringPattern::ID id); 104 void AddMatch(StringPattern::ID id);
103 void AddMatches(const Matches& matches); 105 void AddMatches(const Matches& matches);
104 const Matches& matches() const { return matches_; } 106 const Matches& matches() const { return matches_; }
105 107
106 private: 108 private:
107 // Outgoing edges of current node. 109 // Outgoing edges of current node.
108 Edges edges_; 110 Edges edges_;
109 111
110 // Node index that failure edge leads to. 112 // Node index that failure edge leads to.
111 uint32 failure_; 113 uint32_t failure_;
112 114
113 // Identifiers of matches. 115 // Identifiers of matches.
114 Matches matches_; 116 Matches matches_;
115 }; 117 };
116 118
117 typedef std::map<StringPattern::ID, const StringPattern*> SubstringPatternMap; 119 typedef std::map<StringPattern::ID, const StringPattern*> SubstringPatternMap;
118 typedef std::vector<const StringPattern*> SubstringPatternVector; 120 typedef std::vector<const StringPattern*> SubstringPatternVector;
119 121
120 // |sorted_patterns| is a copy of |patterns_| sorted by the pattern string. 122 // |sorted_patterns| is a copy of |patterns_| sorted by the pattern string.
121 void RebuildAhoCorasickTree(const SubstringPatternVector& sorted_patterns); 123 void RebuildAhoCorasickTree(const SubstringPatternVector& sorted_patterns);
(...skipping 10 matching lines...) Expand all
132 134
133 // The nodes of a Aho-Corasick tree. 135 // The nodes of a Aho-Corasick tree.
134 std::vector<AhoCorasickNode> tree_; 136 std::vector<AhoCorasickNode> tree_;
135 137
136 DISALLOW_COPY_AND_ASSIGN(SubstringSetMatcher); 138 DISALLOW_COPY_AND_ASSIGN(SubstringSetMatcher);
137 }; 139 };
138 140
139 } // namespace url_matcher 141 } // namespace url_matcher
140 142
141 #endif // COMPONENTS_URL_MATCHER_SUBSTRING_SET_MATCHER_H_ 143 #endif // COMPONENTS_URL_MATCHER_SUBSTRING_SET_MATCHER_H_
OLDNEW
« no previous file with comments | « components/url_matcher/string_pattern.h ('k') | components/url_matcher/substring_set_matcher.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698