Replace an O(n^2) algorithm in areCompatObjCQualInterfaces with

an O(n) algorithm by taking advantage of the fact that the
protocol qualifier list is already guaranteed sorted.



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@49312 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 26 insertions, 14 deletions

diff --git a/lib/AST/ASTContext.cpp b/lib/AST/ASTContext.cpp
index 5119cfb026..65c4e0567f 100644
--- a/lib/AST/ASTContext.cpp
+++ b/lib/AST/ASTContext.cpp
@@ -1478,21 +1478,33 @@ areCompatObjCQualInterfaces(const ObjCQualifiedInterfaceType *LHS,
   if (!LHS->getDecl()->isSuperClassOf(RHS->getDecl()))
     return false;
   
-  // All protocols in LHS must have a presence in RHS.
-  for (unsigned i = 0; i != LHS->getNumProtocols(); ++i) {
-    bool match = false;
-    ObjCProtocolDecl *lhsProto = LHS->getProtocols(i);
-    for (unsigned j = 0; j != RHS->getNumProtocols(); ++j) {
-      ObjCProtocolDecl *rhsProto = RHS->getProtocols(j);
-      if (lhsProto == rhsProto) {
-        match = true;
-        break;
-      }
-    }
-    if (!match)
-      return false;
+  // All protocols in LHS must have a presence in RHS.  Since the protocol lists
+  // are both sorted alphabetically and have no duplicates, we can scan RHS and
+  // LHS in a single parallel scan until we run out of elements in LHS.
+  ObjCQualifiedInterfaceType::qual_iterator LHSPI = LHS->qual_begin();
+  ObjCQualifiedInterfaceType::qual_iterator LHSPE = LHS->qual_end();
+  ObjCQualifiedInterfaceType::qual_iterator RHSPI = RHS->qual_begin();
+  ObjCQualifiedInterfaceType::qual_iterator RHSPE = RHS->qual_end();
+  
+  assert(LHSPI != LHSPE && "Empty LHS protocol list?");
+  ObjCProtocolDecl *LHSProto = *LHSPI;
+  
+  while (RHSPI != RHSPE) {
+    ObjCProtocolDecl *RHSProto = *RHSPI++;
+    // If the RHS has a protocol that the LHS doesn't, ignore it.
+    if (RHSProto != LHSProto)
+      continue;
+    
+    // Otherwise, the RHS does have this element.
+    ++LHSPI;
+    if (LHSPI == LHSPE)
+      return true;  // All protocols in LHS exist in RHS.
+    
+    LHSProto = *LHSPI;
   }
-  return true;
+  
+  // If we got here, we didn't find one of the LHS's protocols in the RHS list.
+  return false;
 }
 
 /// ProtocolCompatibleWithProtocol - return 'true' if 'lProto' is in the