Stop sorting StyleEngine::m_activeTreeScopes

Source/core/dom/StyleEngine.cpp

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  *           (C) 2006 Alexey Proskuryakov (ap@webkit.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (C) 2008, 2009, 2011, 2012 Google Inc. All rights reserved.
  * Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies)
  * Copyright (C) Research In Motion Limited 2010-2011. All rights reserved.
@@ skipping 95 matching lines @@
 inline Document* StyleEngine::master()
 {
     if (isMaster())
         return m_document;
     HTMLImportsController* import = document().importsController();
     if (!import) // Document::import() can return null while executing its destructor.
         return 0;
     return import->master();
 }
 
-void StyleEngine::OrderedTreeScopeSet::insert(TreeScope* treeScope)
-{
-    if (m_treeScopes.isEmpty()) {
-        m_treeScopes.append(treeScope);
-        m_hash.add(treeScope);
-        return;
-    }
-    if (m_hash.contains(treeScope))
-        return;
-
-    int end = m_treeScopes.size() - 1;
-    int start = 0;
-    int position = 0;
-    unsigned result = 0;
-
-    while (start <= end) {
-        position = (start + end) / 2;
-        result = m_treeScopes[position]->comparePosition(*treeScope);
-
-        if (result & Node::DOCUMENT_POSITION_PRECEDING) {
-            end = position - 1;
-        } else {
-            ASSERT(result & Node::DOCUMENT_POSITION_FOLLOWING);
-            start = position + 1;
-        }
-    }
-
-    if (result & Node::DOCUMENT_POSITION_FOLLOWING) {
-        ++position;
-        ASSERT(static_cast<size_t>(position) == m_treeScopes.size() || (m_treeScopes[position]->comparePosition(*treeScope) & Node::DOCUMENT_POSITION_PRECEDING));
-    }
-    m_treeScopes.insert(position, treeScope);
-    m_hash.add(treeScope);
-
-#if ENABLE(ASSERT)
-    // Check whether m_treeScopes is sorted in document order or not.
-    for (unsigned i = 0; i < m_treeScopes.size() - 1; ++i) {
-        unsigned result = m_treeScopes[i]->comparePosition(*m_treeScopes[i + 1]);
-        ASSERT(result & Node::DOCUMENT_POSITION_FOLLOWING);
-    }
-#endif
-}
-
-void StyleEngine::OrderedTreeScopeSet::remove(TreeScope* treeScope)
-{
-    if (!m_hash.contains(treeScope))
-        return;
-    size_t position = m_treeScopes.find(treeScope);
-    m_treeScopes.remove(position);
-    m_hash.remove(treeScope);
-}
-
-DEFINE_TRACE(StyleEngine::OrderedTreeScopeSet)
-{
-#if ENABLE(OILPAN)
-    visitor->trace(m_treeScopes);
-    visitor->trace(m_hash);
-#endif
-}
-
 TreeScopeStyleSheetCollection* StyleEngine::ensureStyleSheetCollectionFor(TreeScope& treeScope)
 {
     if (treeScope == m_document)
         return documentStyleSheetCollection();
 
     StyleSheetCollectionMap::AddResult result = m_styleSheetCollectionMap.add(&treeScope, nullptr);
     if (result.isNewEntry)
         result.storedValue->value = adoptPtrWillBeNoop(new ShadowTreeStyleSheetCollection(toShadowRoot(treeScope)));
     return result.storedValue->value.get();
 }
@@ skipping 93 matching lines @@
 
     TreeScope& treeScope = isStyleElement(*node) ? node->treeScope() : *m_document;
     ASSERT(isStyleElement(*node) || treeScope == m_document);
     ASSERT(!isXSLStyleSheet(*node));
     TreeScopeStyleSheetCollection* collection = ensureStyleSheetCollectionFor(treeScope);
     ASSERT(collection);
     collection->addStyleSheetCandidateNode(node, createdByParser);
 
     markTreeScopeDirty(treeScope);
     if (treeScope != m_document)
-        m_activeTreeScopes.insert(&treeScope);
+        m_activeTreeScopes.add(&treeScope);
 }
 
 void StyleEngine::removeStyleSheetCandidateNode(Node* node)
 {
     removeStyleSheetCandidateNode(node, *m_document);
 }
 
 void StyleEngine::removeStyleSheetCandidateNode(Node* node, TreeScope& treeScope)
 {
     ASSERT(isStyleElement(*node) || treeScope == m_document);
@@ skipping 22 matching lines @@
 bool StyleEngine::shouldUpdateDocumentStyleSheetCollection(StyleResolverUpdateMode updateMode) const
 {
     return m_documentScopeDirty || updateMode == FullStyleUpdate;
 }
 
 bool StyleEngine::shouldUpdateShadowTreeStyleSheetCollection(StyleResolverUpdateMode updateMode) const
 {
     return !m_dirtyTreeScopes.isEmpty() || updateMode == FullStyleUpdate;
 }
 
-void StyleEngine::clearMediaQueryRuleSetOnTreeScopeStyleSheets(UnorderedTreeScopeSet::iterator begin, UnorderedTreeScopeSet::iterator end)
+void StyleEngine::clearMediaQueryRuleSetOnTreeScopeStyleSheets(UnorderedTreeScopeSet& treeScopes)
 {
-    for (UnorderedTreeScopeSet::iterator it = begin; it != end; ++it) {
-        TreeScope& treeScope = **it;
+    for (TreeScope* treeScope : treeScopes) {
         ASSERT(treeScope != m_document);
-        ShadowTreeStyleSheetCollection* collection = static_cast<ShadowTreeStyleSheetCollection*>(styleSheetCollectionFor(treeScope));
+        ShadowTreeStyleSheetCollection* collection = static_cast<ShadowTreeStyleSheetCollection*>(styleSheetCollectionFor(*treeScope));
         ASSERT(collection);
         collection->clearMediaQueryRuleSetStyleSheets();
     }
 }
 
 void StyleEngine::clearMediaQueryRuleSetStyleSheets()
 {
     documentStyleSheetCollection()->clearMediaQueryRuleSetStyleSheets();
-    clearMediaQueryRuleSetOnTreeScopeStyleSheets(m_activeTreeScopes.beginUnordered(), m_activeTreeScopes.endUnordered());
-    clearMediaQueryRuleSetOnTreeScopeStyleSheets(m_dirtyTreeScopes.begin(), m_dirtyTreeScopes.end());
+    clearMediaQueryRuleSetOnTreeScopeStyleSheets(m_activeTreeScopes);
+    clearMediaQueryRuleSetOnTreeScopeStyleSheets(m_dirtyTreeScopes);
 }
 
 void StyleEngine::updateStyleSheetsInImport(DocumentStyleSheetCollector& parentCollector)
 {
     ASSERT(!isMaster());
     WillBeHeapVector<RefPtrWillBeMember<StyleSheet>> sheetsForList;
     ImportedDocumentStyleSheetCollector subcollector(parentCollector, sheetsForList);
     documentStyleSheetCollection()->collectStyleSheets(*this, subcollector);
     documentStyleSheetCollection()->swapSheetsForSheetList(sheetsForList);
 }
@@ skipping 20 matching lines @@
     if (!document().isActive())
         return;
 
     if (shouldUpdateDocumentStyleSheetCollection(updateMode))
         documentStyleSheetCollection()->updateActiveStyleSheets(*this, updateMode);
 
     if (shouldUpdateShadowTreeStyleSheetCollection(updateMode)) {
         UnorderedTreeScopeSet treeScopesRemoved;
 
         if (updateMode == FullStyleUpdate) {
-            for (unsigned i = 0; i < m_activeTreeScopes.size(); ++i)
-                updateActiveStyleSheetsInShadow(updateMode, m_activeTreeScopes[i], treeScopesRemoved);
+            for (TreeScope* treeScope : m_activeTreeScopes)
+                updateActiveStyleSheetsInShadow(updateMode, treeScope, treeScopesRemoved);
         } else {
-            for (UnorderedTreeScopeSet::iterator it = m_dirtyTreeScopes.begin(); it != m_dirtyTreeScopes.end(); ++it) {
-                updateActiveStyleSheetsInShadow(updateMode, *it, treeScopesRemoved);
-            }
+            for (TreeScope* treeScope : m_dirtyTreeScopes)
+                updateActiveStyleSheetsInShadow(updateMode, treeScope, treeScopesRemoved);
         }
-        for (UnorderedTreeScopeSet::iterator it = treeScopesRemoved.begin(); it != treeScopesRemoved.end(); ++it)
-            m_activeTreeScopes.remove(*it);
+        for (TreeScope* treeScope : treeScopesRemoved)
+            m_activeTreeScopes.remove(treeScope);
     }
 
     InspectorInstrumentation::activeStyleSheetsUpdated(m_document);
     m_usesRemUnits = documentStyleSheetCollection()->usesRemUnits();
 
     m_dirtyTreeScopes.clear();
     m_documentScopeDirty = false;
 }
 
 const WillBeHeapVector<RefPtrWillBeMember<CSSStyleSheet>> StyleEngine::activeStyleSheetsForInspector() const
 {
     if (m_activeTreeScopes.isEmpty())
         return documentStyleSheetCollection()->activeAuthorStyleSheets();
 
     WillBeHeapVector<RefPtrWillBeMember<CSSStyleSheet>> activeStyleSheets;
 
     activeStyleSheets.appendVector(documentStyleSheetCollection()->activeAuthorStyleSheets());
-    for (unsigned i = 0; i < m_activeTreeScopes.size(); ++i) {
-        TreeScope* treeScope = const_cast<TreeScope*>(m_activeTreeScopes[i]);
+    for (TreeScope* treeScope : m_activeTreeScopes) {
         if (TreeScopeStyleSheetCollection* collection = m_styleSheetCollectionMap.get(treeScope))
             activeStyleSheets.appendVector(collection->activeAuthorStyleSheets());
     }
 
     // FIXME: Inspector needs a vector which has all active stylesheets.
     // However, creating such a large vector might cause performance regression.
     // Need to implement some smarter solution.
     return activeStyleSheets;
 }
 
@@ skipping 15 matching lines @@
     m_styleSheetCollectionMap.remove(shadowRoot);
     m_activeTreeScopes.remove(shadowRoot);
     m_dirtyTreeScopes.remove(shadowRoot);
 }
 
 void StyleEngine::appendActiveAuthorStyleSheets()
 {
     ASSERT(isMaster());
 
     m_resolver->appendAuthorStyleSheets(documentStyleSheetCollection()->activeAuthorStyleSheets());
-    for (unsigned i = 0; i < m_activeTreeScopes.size(); ++i) {
-        if (TreeScopeStyleSheetCollection* collection = m_styleSheetCollectionMap.get(m_activeTreeScopes[i]))
+    for (TreeScope* treeScope : m_activeTreeScopes) {
+        if (TreeScopeStyleSheetCollection* collection = m_styleSheetCollectionMap.get(treeScope))
             m_resolver->appendAuthorStyleSheets(collection->activeAuthorStyleSheets());
     }
     m_resolver->finishAppendAuthorStyleSheets();
 }
 
 void StyleEngine::createResolver()
 {
     // It is a programming error to attempt to resolve style on a Document
     // which is not in a frame. Code which hits this should have checked
     // Document::isActive() before calling into code which could get here.
@@ skipping 14 matching lines @@
     ASSERT(isMaster() || !m_resolver);
 
     document().clearScopedStyleResolver();
     // StyleEngine::shadowRootRemovedFromDocument removes not-in-document
     // treescopes from activeTreeScopes. StyleEngine::didRemoveShadowRoot
     // removes treescopes which are being destroyed from activeTreeScopes.
     // So we need to clearScopedStyleResolver for treescopes which have been
     // just removed from document. If document is destroyed before invoking
     // updateActiveStyleSheets, the treescope has a scopedStyleResolver which
     // has destroyed StyleSheetContents.
-    for (UnorderedTreeScopeSet::iterator it = m_activeTreeScopes.beginUnordered(); it != m_activeTreeScopes.endUnordered(); ++it)
-        (*it)->clearScopedStyleResolver();
+    for (TreeScope* treeScope : m_activeTreeScopes)
+        treeScope->clearScopedStyleResolver();
 
     m_resolver.clear();
 }
 
 void StyleEngine::clearMasterResolver()
 {
     if (Document* master = this->master())
         master->styleEngine().clearResolver();
 }
 
@@ skipping 143 matching lines @@
 
     m_textToSheetCache.remove(it->value);
     m_sheetToTextCache.remove(contents);
 }
 
 void StyleEngine::collectScopedStyleFeaturesTo(RuleFeatureSet& features) const
 {
     HashSet<const StyleSheetContents*> visitedSharedStyleSheetContents;
     if (document().scopedStyleResolver())
         document().scopedStyleResolver()->collectFeaturesTo(features, visitedSharedStyleSheetContents);
-    for (unsigned i = 0; i < m_activeTreeScopes.size(); ++i) {
-        TreeScope* treeScope = const_cast<TreeScope*>(m_activeTreeScopes[i]);
+    for (TreeScope* treeScope : m_activeTreeScopes) {
         // When creating StyleResolver, dirty treescopes might not be processed.
         // So some active treescopes might not have a scoped style resolver.
         // In this case, we should skip collectFeatures for the treescopes without
         // scoped style resolvers. When invoking updateActiveStyleSheets,
         // the treescope's features will be processed.
         if (ScopedStyleResolver* resolver = treeScope->scopedStyleResolver())
             resolver->collectFeaturesTo(features, visitedSharedStyleSheetContents);
     }
 }
 
@@ skipping 117 matching lines @@
     visitor->trace(m_dirtyTreeScopes);
     visitor->trace(m_activeTreeScopes);
     visitor->trace(m_fontSelector);
     visitor->trace(m_textToSheetCache);
     visitor->trace(m_sheetToTextCache);
 #endif
     CSSFontSelectorClient::trace(visitor);
 }
 
 }