Replace O(n^2) set intersection test with O(n)

content/browser/indexed_db/indexed_db_transaction_coordinator.cc

 // Copyright (c) 2013 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 "content/browser/indexed_db/indexed_db_transaction_coordinator.h"
 
 #include "base/basictypes.h"
 #include "base/logging.h"
 #include "content/browser/indexed_db/indexed_db_transaction.h"
 
@@ skipping 87 matching lines @@
     IndexedDBTransaction* transaction = *it;
     ++it;
     if (CanRunTransaction(transaction)) {
       queued_transactions_.erase(transaction);
       started_transactions_.insert(transaction);
       transaction->Run();
     }
   }
 }
 
-static bool DoScopesOverlap(const std::set<int64>& scope1,
-                            const std::set<int64>& scope2) {
-  for (std::set<int64>::const_iterator it = scope1.begin(); it != scope1.end();
-       ++it) {
-    if (scope2.find(*it) != scope2.end())
+template<typename T>
+static bool DoSetsIntersect(const std::set<T>& set1,
+                            const std::set<T>& set2) {
+  typename std::set<T>::const_iterator it1 = set1.begin();
+  typename std::set<T>::const_iterator it2 = set2.begin();
+  while (it1 != set1.end() && it2 != set2.end()) {
+    if (*it1 < *it2)
+      ++it1;
+    else if (*it2 < *it1)
+      ++it2;
+    else
       return true;
   }
   return false;
 }
 
 bool IndexedDBTransactionCoordinator::CanRunTransaction(
     IndexedDBTransaction* transaction) {
   DCHECK(queued_transactions_.has(transaction));
   switch (transaction->mode()) {
     case indexed_db::TRANSACTION_VERSION_CHANGE:
       DCHECK_EQ(static_cast<size_t>(1), queued_transactions_.size());
       DCHECK(started_transactions_.empty());
       return true;
 
     case indexed_db::TRANSACTION_READ_ONLY:
       return true;
 
     case indexed_db::TRANSACTION_READ_WRITE:
       for (list_set<IndexedDBTransaction*>::const_iterator it =
                started_transactions_.begin();
            it != started_transactions_.end();
            ++it) {
         IndexedDBTransaction* other = *it;
         if (other->mode() == indexed_db::TRANSACTION_READ_WRITE &&
-            DoScopesOverlap(transaction->scope(), other->scope()))
+            DoSetsIntersect(transaction->scope(), other->scope()))
           return false;
       }
       for (list_set<IndexedDBTransaction*>::const_iterator it =
                queued_transactions_.begin();
            *it != transaction;
            ++it) {
         DCHECK(it != queued_transactions_.end());
         IndexedDBTransaction* other = *it;
         if (other->mode() == indexed_db::TRANSACTION_READ_WRITE &&
-            DoScopesOverlap(transaction->scope(), other->scope()))
+            DoSetsIntersect(transaction->scope(), other->scope()))
           return false;
       }
       return true;
   }
   NOTREACHED();
   return false;
 }
 
 }  // namespace content