Speed improvements to SubstringSetMatcher

extensions/common/matcher/substring_set_matcher.h

 // 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.
 
 #ifndef EXTENSIONS_COMMON_MATCHER_SUBSTRING_SET_MATCHER_H_
 #define EXTENSIONS_COMMON_MATCHER_SUBSTRING_SET_MATCHER_H_
 
+#include <limits>
 #include <map>
 #include <set>
 #include <string>
 #include <vector>
 
 #include "base/basictypes.h"
 #include "extensions/common/matcher/string_pattern.h"
 
 namespace extensions {
 
@@ skipping 55 matching lines @@
   // text[i + k] at depth k + 1, we follow a failure edge. This edge
   // corresponds to the longest proper suffix of text[i, ..., i + k - 1] that
   // is a prefix of any registered pattern.
   //
   // If your brain thinks "Forget it, let's go shopping.", don't worry.
   // Take a nap and read an introductory text on the Aho Corasick algorithm.
   // It will make sense. Eventually.
   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, uint32> Edges;
     typedef std::set<StringPattern::ID> Matches;
 
+    static const uint32 kNoSuchEdge;  // Represents an invalid node index.
+
     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);
+    uint32 GetEdge(char c) const;
+    void SetEdge(char c, uint32 node);
     const Edges& edges() const { return edges_; }
 
-    int failure() const { return failure_; }
-    void set_failure(int failure) { failure_ = failure; }
+    uint32 failure() const { return failure_; }
+    void set_failure(uint32 failure) { failure_ = failure; }
 
     void AddMatch(StringPattern::ID id);
     void AddMatches(const Matches& matches);
     const Matches& matches() const { return matches_; }
 
    private:
     // Outgoing edges of current node.
     Edges edges_;
 
     // Node index that failure edge leads to.
-    int failure_;
+    uint32 failure_;
 
     // Identifiers of matches.
     Matches matches_;
   };
 
-  void RebuildAhoCorasickTree();
+  typedef std::map<StringPattern::ID, const StringPattern*> SubstringPatternMap;
+  typedef std::vector<const StringPattern*> SubstringPatternVector;
+
+  // |sorted_patterns| is a copy of |patterns_| sorted by the pattern string.
+  void RebuildAhoCorasickTree(const SubstringPatternVector& sorted_patterns);
 
   // Inserts a path for |pattern->pattern()| into the tree and adds
   // |pattern->id()| to the set of matches. Ownership of |pattern| remains with
   // the caller.
   void InsertPatternIntoAhoCorasickTree(const StringPattern* pattern);
   void CreateFailureEdges();
 
   // Set of all registered StringPatterns. Used to regenerate the
   // Aho-Corasick tree in case patterns are registered or unregistered.
-  typedef std::map<StringPattern::ID, const StringPattern*>
-      SubstringPatternSet;
-  SubstringPatternSet patterns_;
+  SubstringPatternMap patterns_;
 
   // The nodes of a Aho-Corasick tree.
   std::vector<AhoCorasickNode> tree_;
 
   DISALLOW_COPY_AND_ASSIGN(SubstringSetMatcher);
 };
 
 }  // namespace extensions
 
 #endif  // EXTENSIONS_COMMON_MATCHER_SUBSTRING_SET_MATCHER_H_