[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-commits
Subject:    KDE/kdelibs/khtml/css
From:       Viacheslav Tokarev <tsjoker () gmail ! com>
Date:       2008-11-23 19:37:44
Message-ID: 1227469064.628360.10596.nullmailer () svn ! kde ! org
[Download RAW message or body]

SVN commit 888104 by vtokarev:

Use O(M+N) algorithm instead of O(M*N) for collecting selectors list
on some heavy sites, like youtube, it could save 100-300ms

 M  +31 -0     css_base.h  
 M  +17 -19    cssstyleselector.cpp  


--- trunk/KDE/kdelibs/khtml/css/css_base.h #888103:888104
@@ -273,6 +273,37 @@
 
     KDE_NO_EXPORT int getPropertyID(const char *tagStr, int len);
     KDE_NO_EXPORT int getValueID(const char *tagStr, int len);
+
+    struct SelectorHash
+    {
+        static unsigned hash(CSSSelector* selector)
+        {
+            unsigned result = 0;
+            while (selector) {
+                result ^= (unsigned)selector->value.impl();
+                result ^= (selector->attrLocalName.id() << 3);
+                result ^= (selector->attrNamespace.id() << 7);
+                result ^= (selector->tagLocalName.id() << 10);
+                result ^= (selector->tagNamespace.id() << 13);
+                result ^= (selector->relation << 17);
+                result ^= (selector->match << 20);
+                result ^= result << 5;
+                selector = selector->tagHistory;
+            }
+            return result;
+        }
+        static bool equal(CSSSelector* a, CSSSelector* b) { return a == b || *a == \
*b; } +        static const bool safeToCompareToEmptyOrDeleted = false;
+    };
+
 }
 
+namespace WTF
+{
+    template<typename T> struct DefaultHash;
+    template<> struct DefaultHash<DOM::CSSSelector*> {
+        typedef DOM::SelectorHash Hash;
+    };
+}
+
 #endif
--- trunk/KDE/kdelibs/khtml/css/cssstyleselector.cpp #888103:888104
@@ -68,6 +68,8 @@
 #include <assert.h>
 #include <stdlib.h>
 
+#include <wtf/HashMap.h>
+
 // keep in sync with html4.css'
 #define KHTML_STYLE_VERSION 1
 
@@ -1990,33 +1992,29 @@
     }
 }
 
-
 void CSSStyleSelectorList::collect( QList<CSSSelector*> *selectorList, \
CSSOrderedPropertyList *propList,  Source regular, Source important )
 {
     CSSOrderedRule *r;
     QListIterator<CSSOrderedRule*> tIt(*this);
-    CSSSelector *sel;
 
+    WTF::HashMap<CSSSelector*, int> cache;
+    QListIterator<CSSSelector*> it(*selectorList);
+    int pos = 0;
+    while (it.hasNext())
+        cache.set(it.next(), pos++);
+
     while( tIt.hasNext() ) {
         r = tIt.next();
-	int selectorNum = 0;
-	sel = 0;
-        bool found = false;
-        // already in list?
-	QListIterator<CSSSelector*> it(*selectorList);
-	while( it.hasNext() ) {
-	    sel = it.next();
-	    if ( *sel == *(r->selector) ) {
-	        found = true;
-		break;
-            }
-	    selectorNum++;
-	}
-	if ( !found )
-	    // nope.
-	    selectorList->append( r->selector );
-	propList->append(r->rule->declaration(), selectorNum, r->selector->specificity(), \
regular, important ); +        WTF::HashMap<CSSSelector*, int>::iterator \
cacheIterator = cache.find(r->selector); +        int selectorNum;
+        if (cacheIterator == cache.end()) {
+            selectorNum = cache.size();
+            cache.set(r->selector, selectorNum);
+            selectorList->append(r->selector);
+        } else
+            selectorNum = cacheIterator->second;
+        propList->append(r->rule->declaration(), selectorNum, \
r->selector->specificity(), regular, important );  }
 }
 


[prev in list] [next in list] [prev in thread] [next in thread]