Take 2 at implementing activeTab.

chrome/common/extensions/url_pattern_set.cc

 // Copyright (c) 2011 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 "chrome/common/extensions/url_pattern_set.h"
 
 #include <algorithm>
 #include <iterator>
 
 #include "base/logging.h"
+#include "base/memory/linked_ptr.h"
 #include "base/values.h"
 #include "chrome/common/extensions/extension_error_utils.h"
 #include "chrome/common/extensions/url_pattern.h"
 #include "content/public/common/url_constants.h"
 #include "googleurl/src/gurl.h"
 
 namespace {
 
 const char kInvalidURLPatternError[] = "Invalid url pattern '*'";
 
@@ skipping 25 matching lines @@
 void URLPatternSet::CreateUnion(const URLPatternSet& set1,
                                 const URLPatternSet& set2,
                                 URLPatternSet* out) {
   out->ClearPatterns();
   std::set_union(set1.patterns_.begin(), set1.patterns_.end(),
                  set2.patterns_.begin(), set2.patterns_.end(),
                  std::inserter<std::set<URLPattern> >(
                      out->patterns_, out->patterns_.begin()));
 }
 
+// static
+void URLPatternSet::CreateUnion(const std::vector<URLPatternSet>& sets,
+                                URLPatternSet* out) {
+  out->ClearPatterns();
+  if (sets.empty())
+    return;
+
+  // N-way union algorithm is basic O(nlog(n)) merge algorithm.
+  //
+  // Do the first merge step into a working set so that we don't mutate any of
+  // the input.
+  std::vector<URLPatternSet> working;
+  for (size_t i = 0; i < sets.size(); i += 2) {
+    if (i + 1 < sets.size()) {
+      URLPatternSet u;
+      URLPatternSet::CreateUnion(sets[i], sets[i + 1], &u);
+      working.push_back(u);
+    } else {
+      working.push_back(sets[i]);
+    }
+  }
+
+  for (size_t skip = 1; skip < working.size(); skip *= 2) {
+    for (size_t i = 0; i < (working.size() - skip); i += skip) {
+      URLPatternSet u;
+      URLPatternSet::CreateUnion(working[i], working[i + skip], &u);
+      working[i].patterns_.swap(u.patterns_);
+    }
+  }
+
+  out->patterns_.swap(working[0].patterns_);
+}
+
 URLPatternSet::URLPatternSet() {}
 
 URLPatternSet::URLPatternSet(const URLPatternSet& rhs)
     : patterns_(rhs.patterns_) {}
 
 URLPatternSet::URLPatternSet(const std::set<URLPattern>& patterns)
     : patterns_(patterns) {}
 
 URLPatternSet::~URLPatternSet() {}
 
 URLPatternSet& URLPatternSet::operator=(const URLPatternSet& rhs) {
   patterns_ = rhs.patterns_;
   return *this;
 }
 
 bool URLPatternSet::operator==(const URLPatternSet& other) const {
   return patterns_ == other.patterns_;
 }
 
 bool URLPatternSet::is_empty() const {
   return patterns_.empty();
 }
 
+size_t URLPatternSet::size() const {
+  return patterns_.size();
+}
+
 void URLPatternSet::AddPattern(const URLPattern& pattern) {
   patterns_.insert(pattern);
 }
 
 void URLPatternSet::ClearPatterns() {
   patterns_.clear();
 }
 
 bool URLPatternSet::Contains(const URLPatternSet& set) const {
   return std::includes(patterns_.begin(), patterns_.end(),
@@ skipping 63 matching lines @@
       return false;
     }
     if (!allow_file_access && pattern.MatchesScheme(chrome::kFileScheme)) {
       pattern.SetValidSchemes(
           pattern.valid_schemes() & ~URLPattern::SCHEME_FILE);
     }
     AddPattern(pattern);
   }
   return true;
 }