Performance optimization of SubstringSetMatcher::InsertPatternIntoAhoCorasickTree

extensions/common/matcher/substring_set_matcher.cc

 // 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.
 
 #include "extensions/common/matcher/substring_set_matcher.h"
 
 #include <queue>
 
 #include "base/logging.h"
 #include "base/stl_util.h"
@@ skipping 83 matching lines @@
        i != patterns_.end(); ++i) {
     InsertPatternIntoAhoCorasickTree(i->second);
   }
 
   CreateFailureEdges();
 }
 
 void SubstringSetMatcher::InsertPatternIntoAhoCorasickTree(
     const StringPattern* pattern) {
   const std::string& text = pattern->pattern();
-  size_t text_length = text.length();
+  const std::string::const_iterator text_end = text.end();
 
-  // Iterators on the tree and the text.
+  std::string::const_iterator text_iter = text.begin();
   int current_node = 0;
-  size_t text_pos = 0;
 
   // Follow existing paths for as long as possible.
-  while (text_pos < text_length &&
-         tree_[current_node].HasEdge(text[text_pos])) {
-    current_node = tree_[current_node].GetEdge(text[text_pos]);
-    ++text_pos;
+  int edge_to;
+  while (text_iter != text_end &&
+         (edge_to = tree_[current_node].GetEdge(*text_iter)) != -1) {
+    current_node = edge_to;
+    ++text_iter;
   }
 
   // Create new nodes if necessary.
-  while (text_pos < text_length) {
-    AhoCorasickNode new_node;
-    tree_.push_back(new_node);
-    tree_[current_node].SetEdge(text[text_pos], tree_.size() - 1);
-    current_node = tree_.size() - 1;
-    ++text_pos;
+  int new_node_position = tree_.size();
+  while (text_iter != text_end) {
+    tree_.push_back(AhoCorasickNode());
+    tree_[current_node].SetEdge(*text_iter, new_node_position);
+    current_node = new_node_position;
+    ++text_iter;
+    ++new_node_position;
   }
 
   // Register match.
   tree_[current_node].AddMatch(pattern->id());
 }
 
 void SubstringSetMatcher::CreateFailureEdges() {
   typedef AhoCorasickNode::Edges Edges;
 
   std::queue<int> queue;
@@ skipping 65 matching lines @@
 void SubstringSetMatcher::AhoCorasickNode::AddMatch(StringPattern::ID id) {
   matches_.insert(id);
 }
 
 void SubstringSetMatcher::AhoCorasickNode::AddMatches(
     const SubstringSetMatcher::AhoCorasickNode::Matches& matches) {
   matches_.insert(matches.begin(), matches.end());
 }
 
 }  // namespace extensions