Replace style sharing cousin list search with LRU

Source/core/css/resolver/StyleResolver.h

 /*
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
@@ skipping 18 matching lines @@
 #include "core/css/RuleFeature.h"
 #include "core/css/RuleSet.h"
 #include "core/css/SelectorChecker.h"
 #include "core/css/SelectorFilter.h"
 #include "core/css/SiblingTraversalStrategies.h"
 #include "core/css/resolver/MatchedPropertiesCache.h"
 #include "core/css/resolver/ScopedStyleResolver.h"
 #include "core/css/resolver/StyleBuilder.h"
 #include "core/css/resolver/StyleResolverState.h"
 #include "core/css/resolver/StyleResourceLoader.h"
+#include "wtf/Deque.h"
 #include "wtf/HashMap.h"
 #include "wtf/HashSet.h"
 #include "wtf/RefPtr.h"
 #include "wtf/Vector.h"
 
 namespace WebCore {
 
 class CSSAnimationUpdate;
 class CSSFontSelector;
 class CSSRuleList;
@@ skipping 29 matching lines @@
 
 // MatchOnlyUserAgentRules is used in media queries, where relative units
 // are interpreted according to the document root element style, and styled only
 // from the User Agent Stylesheet rules.
 enum RuleMatchingBehavior {
     MatchAllRules,
     MatchAllRulesExcludingSMIL,
     MatchOnlyUserAgentRules,
 };
 
+const unsigned styleSharingListSize = 40;
+typedef WTF::Deque<RefPtr<Element>, styleSharingListSize> StyleSharingList;
+
 #undef STYLE_STATS
 
 #ifdef STYLE_STATS
 struct StyleSharingStats {
     void addSearch() { ++m_searches; ++m_totalSearches; }
     void addElementEligibleForSharing() { ++m_elementsEligibleForSharing; ++m_totalElementsEligibleForSharing; }
     void addStyleShared() { ++m_stylesShared; ++m_totalStylesShared; }
     void addSearchFoundSiblingForSharing() { ++m_searchFoundSiblingForSharing; ++m_totalSearchFoundSiblingForSharing; }
     void addSearchMissedSharing() { ++m_searchesMissedSharing; ++m_totalSearchesMissedSharing; }
     void addMatchedPropertiesSearch() { ++m_matchedPropertiesSearches; ++m_totalMatchedPropertiesSearches; }
@@ skipping 168 matching lines @@
     InspectorCSSOMWrappers& inspectorCSSOMWrappers() { return m_inspectorCSSOMWrappers; }
 
     enum ViewportOrigin { UserAgentOrigin, AuthorOrigin };
 
     // Exposed for ScopedStyleResolver.
     // FIXME: Likely belongs on viewportStyleResolver.
     void collectViewportRules(RuleSet*, ViewportOrigin);
 
     const RuleFeatureSet& ruleFeatureSet() const { return m_features; }
 
+    StyleSharingList& styleSharingList() { return m_styleSharingList; }
+
+    bool supportsStyleSharing(Element*);
+
+    void addToStyleSharingList(Element*);
+    void clearStyleSharingList();
+
 #ifdef STYLE_STATS
     ALWAYS_INLINE static StyleSharingStats& styleSharingStats() { return m_styleSharingStats; }
 #endif
 private:
     // FIXME: This should probably go away, folded into FontBuilder.
     void updateFont(StyleResolverState&);
 
     void matchUARules(ElementRuleCollector&, RuleSet*);
     void matchAuthorRules(Element*, ElementRuleCollector&, bool includeEmptyRules);
     void matchShadowDistributedRules(ElementRuleCollector&, bool includeEmptyRules);
@@ skipping 63 matching lines @@
     // FIXME: The entire logic of collecting features on StyleResolver, as well astransferring them
     // between various parts of machinery smells wrong. This needs to be better somehow.
     RuleFeatureSet m_features;
     OwnPtr<RuleSet> m_siblingRuleSet;
     OwnPtr<RuleSet> m_uncommonAttributeRuleSet;
 
     InspectorCSSOMWrappers m_inspectorCSSOMWrappers;
 
     StyleResourceLoader m_styleResourceLoader;
 
+    StyleSharingList m_styleSharingList;
+
 #ifdef STYLE_STATS
     static StyleSharingStats m_styleSharingStats;
 #endif
 };
 
 inline bool checkRegionSelector(const CSSSelector* regionSelector, Element* regionElement)
 {
     if (!regionSelector || !regionElement)
         return false;
 
     SelectorChecker selectorChecker(regionElement->document(), SelectorChecker::QueryingRules);
     for (const CSSSelector* s = regionSelector; s; s = CSSSelectorList::next(s)) {
         SelectorChecker::SelectorCheckingContext selectorCheckingContext(s, regionElement, SelectorChecker::VisitedMatchDisabled);
         PseudoId ignoreDynamicPseudo = NOPSEUDO;
         if (selectorChecker.match(selectorCheckingContext, ignoreDynamicPseudo, DOMSiblingTraversalStrategy()) == SelectorChecker::SelectorMatches)
             return true;
     }
     return false;
 }
 
 } // namespace WebCore
 
 #endif // StyleResolver_h