Speed improvements to SubstringSetMatcher

extensions/common/matcher/substring_set_matcher.h

Index: extensions/common/matcher/substring_set_matcher.h
diff --git a/extensions/common/matcher/substring_set_matcher.h b/extensions/common/matcher/substring_set_matcher.h
index 4ba8ec3acc364413a3f6dc16c25e9ed5db7f57b9..8d60ec07c1918b3c9fed35dcb2bf03eb1a5daefb 100644
--- a/extensions/common/matcher/substring_set_matcher.h
+++ b/extensions/common/matcher/substring_set_matcher.h
@@ -5,6 +5,7 @@
 #ifndef EXTENSIONS_COMMON_MATCHER_SUBSTRING_SET_MATCHER_H_
 #define EXTENSIONS_COMMON_MATCHER_SUBSTRING_SET_MATCHER_H_
 
+#include <limits>
 #include <map>
 #include <set>
 #include <string>
@@ -80,21 +81,22 @@ class SubstringSetMatcher {
   class AhoCorasickNode {
    public:
     // Key: label of the edge, value: node index in |tree_| of parent class.
-    typedef std::map<char, int> Edges;
+    typedef std::map<char, unsigned> Edges;

[vabr (Chromium), 2013/05/03 20:37:27]

The Chromium style guide explicitly says that unsigned numbers should be used
for vector indices.

[battre, 2013/05/03 21:59:12]

I think this should be size_t though.

[vabr (Chromium), 2013/05/05 23:36:49]

I went with unsigned for performance reasons (please see my other comment).

     typedef std::set<StringPattern::ID> Matches;
 
+    static const unsigned kInvalidIndex = std::numeric_limits<unsigned>::max();

[battre, 2013/05/03 21:59:12]

I think this does not compile on Windows.

How about renaming this to kNoSuchEdge?

[vabr (Chromium), 2013/05/05 23:36:49]

Done.

+
     AhoCorasickNode();
     ~AhoCorasickNode();
     AhoCorasickNode(const AhoCorasickNode& other);
     AhoCorasickNode& operator=(const AhoCorasickNode& other);
 
-    bool HasEdge(char c) const;
-    int GetEdge(char c) const;
-    void SetEdge(char c, int node);
+    unsigned GetEdge(char c) const;
+    void SetEdge(char c, unsigned node);
     const Edges& edges() const { return edges_; }
 
-    int failure() const { return failure_; }
-    void set_failure(int failure) { failure_ = failure; }
+    unsigned failure() const { return failure_; }
+    void set_failure(unsigned failure) { failure_ = failure; }
 
     void AddMatch(StringPattern::ID id);
     void AddMatches(const Matches& matches);
@@ -105,7 +107,7 @@ class SubstringSetMatcher {
     Edges edges_;
 
     // Node index that failure edge leads to.
-    int failure_;
+    unsigned failure_;
 
     // Identifiers of matches.
     Matches matches_;