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
diff --git a/lib/AST/ASTContext.cpp b/lib/AST/ASTContext.cpp
index 5119cfb..65c4e05 100644
--- a/lib/AST/ASTContext.cpp
+++ b/lib/AST/ASTContext.cpp
@@ -1478,21 +1478,33 @@
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