Changeset 122518 in webkit

Timestamp:

Jul 12, 2012 3:40:26 PM (12 years ago)

Author:

rniwa@webkit.org

Message:

Merge HTMLCollectionWithArrayStorage into HTMLCollection
​https://bugs.webkit.org/show_bug.cgi?id=91144

Reviewed by Anders Carlsson.

Merged HTMLCollectionWithArrayStorage::item into HTMLCollection::item and got rid of
HTMLCollectionWithArrayStorage. Also de-virtualized HTMLCollection::item and HTMLCollection::length
and merged itemInArrayAfter and itemAfter.

In addition, improved the algorithm in HTMLCollection::length to take advantage of item cache.
Instead of always computing the length from the beginning, we start the search from the cached item
so that if we're near end of the collection, we avoid significant portion of the node traversal.

Furthermore, made HTMLCollection always call setItemCache with a non-null item and HTMLCollection::item
set the length cache when it reaches the end of the collection to avoid redundant length calculations.

• dom/DynamicNodeList.h:

(WebCore::DynamicNodeListCacheBase::setItemCache): Add a FIXME.

• html/HTMLCollection.cpp:

(WebCore::HTMLCollection::itemAfter): Regular HTMLCollection doesn't have uses elements array so
assert that offsetInArray is always 0.
(WebCore): Removed calcLength.
(WebCore::HTMLCollection::length): Rewritten. The algorithm is as follows:
When there is no item cache, we look for the first item by calling item(0). If item(0) returns null,
then it must have set the length cache so bail out. If the previous step didn't bail out, then
the item cache is valid and not null (see above), so count the number of remaining items in collection
starting at the cached item's offset + 1.
(WebCore::HTMLCollection::item): Avoid calling setItemCache with null. When the first item is null,
set the length cache instead.
(WebCore::HTMLCollection::itemAfterCachedItem): Extracted from HTMLCollectionWithArrayStorage::item.
(WebCore::HTMLCollection::namedItem): Pass in arrayOffset to itemAfter. Note this variable is never
used since only HTMLFormCollection and HTMLPropertiesCollection use array offsets but they override
this function.
(WebCore::HTMLCollection::updateNameCache): Ditto.

• html/HTMLCollection.h:

(HTMLCollection):
(WebCore):

• html/HTMLFormCollection.cpp: Removed calcLength(). Even though this function didn't iterate over

the collection directly, HTMLFormElement::length and HTMLFieldSetElement::length did so we're not
regressing any performance here.
(WebCore::HTMLFormCollection::HTMLFormCollection):
(WebCore::HTMLFormCollection::itemAfter):

• html/HTMLFormCollection.h:

(HTMLFormCollection):

• html/HTMLNameCollection.cpp:

(WebCore::HTMLNameCollection::itemAfter):

• html/HTMLNameCollection.h:

(HTMLNameCollection):

• html/HTMLPropertiesCollection.cpp: Removed calcLength().

(WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
(WebCore::HTMLPropertiesCollection::itemAfter):
(WebCore):

• html/HTMLPropertiesCollection.h:

(HTMLPropertiesCollection):

• html/HTMLTableRowsCollection.cpp:

(WebCore::HTMLTableRowsCollection::itemAfter):

• html/HTMLTableRowsCollection.h:

(HTMLTableRowsCollection):

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• dom/DynamicNodeList.h (modified) (1 diff)
• html/HTMLCollection.cpp (modified) (6 diffs)
• html/HTMLCollection.h (modified) (5 diffs)
• html/HTMLFormCollection.cpp (modified) (2 diffs)
• html/HTMLFormCollection.h (modified) (2 diffs)
• html/HTMLNameCollection.cpp (modified) (1 diff)
• html/HTMLNameCollection.h (modified) (1 diff)
• html/HTMLPropertiesCollection.cpp (modified) (4 diffs)
• html/HTMLPropertiesCollection.h (modified) (2 diffs)
• html/HTMLTableRowsCollection.cpp (modified) (1 diff)
• html/HTMLTableRowsCollection.h (modified) (1 diff)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2012-07-12  Ryosuke Niwa  <rniwa@webkit.org>
+
+        Merge HTMLCollectionWithArrayStorage into HTMLCollection
+        https://bugs.webkit.org/show_bug.cgi?id=91144
+
+        Reviewed by Anders Carlsson.
+
+        Merged HTMLCollectionWithArrayStorage::item into HTMLCollection::item and got rid of
+        HTMLCollectionWithArrayStorage. Also de-virtualized HTMLCollection::item and HTMLCollection::length
+        and merged itemInArrayAfter and itemAfter.
+
+        In addition, improved the algorithm in HTMLCollection::length to take advantage of item cache.
+        Instead of always computing the length from the beginning, we start the search from the cached item
+        so that if we're near end of the collection, we avoid significant portion of the node traversal.
+
+        Furthermore, made HTMLCollection always call setItemCache with a non-null item and HTMLCollection::item
+        set the length cache when it reaches the end of the collection to avoid redundant length calculations.
+
+        * dom/DynamicNodeList.h:
+        (WebCore::DynamicNodeListCacheBase::setItemCache): Add a FIXME.
+        * html/HTMLCollection.cpp:
+        (WebCore::HTMLCollection::itemAfter): Regular HTMLCollection doesn't have uses elements array so
+        assert that offsetInArray is always 0.
+        (WebCore): Removed calcLength.
+        (WebCore::HTMLCollection::length): Rewritten. The algorithm is as follows:
+        When there is no item cache, we look for the first item by calling item(0). If item(0) returns null,
+        then it must have set the length cache so bail out. If the previous step didn't bail out, then
+        the item cache is valid and not null (see above), so count the number of remaining items in collection
+        starting at the cached item's offset + 1.
+        (WebCore::HTMLCollection::item): Avoid calling setItemCache with null. When the first item is null,
+        set the length cache instead.
+        (WebCore::HTMLCollection::itemAfterCachedItem): Extracted from HTMLCollectionWithArrayStorage::item.
+        (WebCore::HTMLCollection::namedItem): Pass in arrayOffset to itemAfter. Note this variable is never
+        used since only HTMLFormCollection and HTMLPropertiesCollection use array offsets but they override
+        this function.
+        (WebCore::HTMLCollection::updateNameCache): Ditto.
+        * html/HTMLCollection.h:
+        (HTMLCollection):
+        (WebCore):
+        * html/HTMLFormCollection.cpp: Removed calcLength(). Even though this function didn't iterate over
+        the collection directly, HTMLFormElement::length and HTMLFieldSetElement::length did so we're not
+        regressing any performance here.
+        (WebCore::HTMLFormCollection::HTMLFormCollection):
+        (WebCore::HTMLFormCollection::itemAfter):
+        * html/HTMLFormCollection.h:
+        (HTMLFormCollection):
+        * html/HTMLNameCollection.cpp:
+        (WebCore::HTMLNameCollection::itemAfter):
+        * html/HTMLNameCollection.h:
+        (HTMLNameCollection):
+        * html/HTMLPropertiesCollection.cpp: Removed calcLength().
+        (WebCore::HTMLPropertiesCollection::HTMLPropertiesCollection):
+        (WebCore::HTMLPropertiesCollection::itemAfter):
+        (WebCore):
+        * html/HTMLPropertiesCollection.h:
+        (HTMLPropertiesCollection):
+        * html/HTMLTableRowsCollection.cpp:
+        (WebCore::HTMLTableRowsCollection::itemAfter):
+        * html/HTMLTableRowsCollection.h:
+        (HTMLTableRowsCollection):
+
 2012-07-12  Pravin D  <pravind.2k4@gmail.com>
 

trunk/Source/WebCore/dom/DynamicNodeList.h

@@ -65 +65 @@
     ALWAYS_INLINE void setItemCache(Node* item, unsigned offset) const
     {
+        // FIXME: Assert that item is not null once we've updated DynamicNodeList.
         m_cachedItem = item;
         m_cachedItemOffset = offset;

trunk/Source/WebCore/html/HTMLCollection.cpp

@@ -181 +181 @@
 }
 
-Element* HTMLCollection::itemAfter(Node* previous) const
-{
+Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
+{
+    ASSERT_UNUSED(offsetInArray, !offsetInArray);
     Node* current;
     if (!previous)
@@ -200 +201 @@
 }
 
-unsigned HTMLCollection::calcLength() const
-{
-    unsigned len = 0;
-    for (Element* current = itemAfter(0); current; current = itemAfter(current))
-        ++len;
-    return len;
-}
-
-// since the collections are to be "live", we have to do the
-// calculation every time if anything has changed
 unsigned HTMLCollection::length() const
 {
     invalidateCacheIfNeeded();
-    if (!isLengthCacheValid())
-        setLengthCache(calcLength());
-    return cachedLength();
+    if (isLengthCacheValid())
+        return cachedLength();
+
+    if (!isItemCacheValid() && !item(0)) {
+        ASSERT(isLengthCacheValid());
+        return 0;
+    }
+
+    ASSERT(isItemCacheValid());
+    ASSERT(cachedItem());
+    unsigned offset = cachedItemOffset();
+    do {
+        offset++;
+    } while (itemAfterCachedItem(offset));
+
+    setLengthCache(offset);
+    return offset;
 }
 
 Node* HTMLCollection::item(unsigned index) const
-{
-    invalidateCacheIfNeeded();
-    if (isItemCacheValid() && cachedItemOffset() == index)
-        return cachedItem();
-    if (isLengthCacheValid() && cachedLength() <= index)
-        return 0;
-    if (!isItemCacheValid() || cachedItemOffset() > index) {
-        setItemCache(itemAfter(0), 0);
-        if (!cachedItem())
-            return 0;
-    }
-    Node* e = cachedItem();
-    for (unsigned pos = cachedItemOffset(); e && pos < index; pos++)
-        e = itemAfter(e);
-    setItemCache(e, index);
-    return cachedItem();
-}
-
-Node* HTMLCollectionWithArrayStorage::item(unsigned index) const
 {
     invalidateCacheIfNeeded();
@@ -253 +239 @@
     if (!isItemCacheValid() || cachedItemOffset() > index) {
         unsigned offsetInArray = 0;
-        setItemCache(itemInArrayAfter(offsetInArray, 0), 0, 0);
-        ASSERT(isItemCacheValid());
-        if (!cachedItem() || cachedItemOffset() == index)
+        Node* firstItem = itemAfter(offsetInArray, 0);
+        if (!firstItem) {
+            setLengthCache(0);
+            return 0;
+        }
+        setItemCache(firstItem, 0, offsetInArray);
+        ASSERT(!cachedItemOffset());
+        if (!index)
             return cachedItem();
     }
 
+    return itemAfterCachedItem(index);
+}
+
+Element* HTMLCollection::itemAfterCachedItem(unsigned index) const
+{
     unsigned currentIndex = cachedItemOffset();
-    ASSERT(cachedItem()->isHTMLElement());
-    HTMLElement* currentItem = toHTMLElement(cachedItem());
+    ASSERT(cachedItem()->isElementNode());
+    Element* currentItem = toElement(cachedItem());
     ASSERT(currentIndex < index);
 
     unsigned offsetInArray = cachedElementsArrayOffset();
-    while ((currentItem = itemInArrayAfter(offsetInArray, currentItem))) {
+    while ((currentItem = itemAfter(offsetInArray, currentItem))) {
         currentIndex++;
         if (currentIndex == index) {
             setItemCache(currentItem, currentIndex, offsetInArray);
-            return cachedItem();
+            return currentItem;
         }
     }
@@ -315 +311 @@
     invalidateCacheIfNeeded();
 
+    unsigned arrayOffset = 0;
     unsigned i = 0;
-    for (Element* e = itemAfter(0); e; e = itemAfter(e)) {
+    for (Element* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
         if (checkForNameMatch(e, /* checkName */ false, name)) {
-            setItemCache(e, i);
+            setItemCache(e, i, arrayOffset);
             return e;
         }
@@ -325 +322 @@
 
     i = 0;
-    for (Element* e = itemAfter(0); e; e = itemAfter(e)) {
+    for (Element* e = itemAfter(arrayOffset, 0); e; e = itemAfter(arrayOffset, e)) {
         if (checkForNameMatch(e, /* checkName */ true, name)) {
-            setItemCache(e, i);
+            setItemCache(e, i, arrayOffset);
             return e;
         }
@@ -342 +339 @@
         return;
 
-    for (Element* element = itemAfter(0); element; element = itemAfter(element)) {
+    unsigned arrayOffset = 0;
+    for (Element* element = itemAfter(arrayOffset, 0); element; element = itemAfter(arrayOffset, element)) {
         if (!element->isHTMLElement())
             continue;

trunk/Source/WebCore/html/HTMLCollection.h

@@ -64 +64 @@
     }
 
-    using DynamicNodeListCacheBase::setItemCache;
     void setItemCache(Node* item, unsigned offset, unsigned elementsArrayOffset) const
     {
@@ -90 +89 @@
     using DynamicNodeListCacheBase::shouldInvalidateOnAttributeChange;
     using DynamicNodeListCacheBase::clearCache;
+    using DynamicNodeListCacheBase::setItemCache;
 
     mutable NodeCacheMap m_idCache;
@@ -109 +109 @@
     // DOM API
     unsigned length() const;
-    virtual Node* item(unsigned index) const;
+    Node* item(unsigned index) const;
     virtual Node* namedItem(const AtomicString& name) const;
     PassRefPtr<NodeList> tags(const String&);
@@ -144 +144 @@
 
     virtual void updateNameCache() const;
-    virtual Element* itemAfter(Node*) const;
+    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const;
 
 private:
     bool checkForNameMatch(Element*, bool checkName, const AtomicString& name) const;
 
-    virtual unsigned calcLength() const;
-
+    Element* itemAfterCachedItem(unsigned) const;
     bool isAcceptableElement(Element*) const;
 
@@ -156 +155 @@
 };
 
-class HTMLCollectionWithArrayStorage : public HTMLCollection {
-public:
-    HTMLCollectionWithArrayStorage(Node* base, CollectionType type)
-        : HTMLCollection(base, type)
-    { }
-
-    virtual Node* item(unsigned index) const OVERRIDE;
-
-private:
-    virtual HTMLElement* itemInArrayAfter(unsigned& offsetInArray, HTMLElement* previousItem) const = 0;
-};
-
 } // namespace
 

trunk/Source/WebCore/html/HTMLFormCollection.cpp

@@ -38 +38 @@
 
 HTMLFormCollection::HTMLFormCollection(Element* base)
-    : HTMLCollectionWithArrayStorage(base, FormControls)
+    : HTMLCollection(base, FormControls)
 {
     ASSERT(base->hasTagName(formTag) || base->hasTagName(fieldsetTag));
@@ -68 +68 @@
 }
 
-unsigned HTMLFormCollection::calcLength() const
-{
-    ASSERT(base()->hasTagName(formTag) || base()->hasTagName(fieldsetTag));
-    if (base()->hasTagName(formTag))
-        return static_cast<HTMLFormElement*>(base())->length();
-    return static_cast<HTMLFieldSetElement*>(base())->length();
-}
-
-HTMLElement* HTMLFormCollection::itemInArrayAfter(unsigned& offset, HTMLElement* previousItem) const
+Element* HTMLFormCollection::itemAfter(unsigned& offset, Element* previousItem) const
 {
     const Vector<FormAssociatedElement*>& elementsArray = formControlElements();

trunk/Source/WebCore/html/HTMLFormCollection.h

@@ -35 +35 @@
 // The famous <table><tr><form><td> problem.
 
-class HTMLFormCollection : public HTMLCollectionWithArrayStorage {
+class HTMLFormCollection : public HTMLCollection {
 public:
     static PassRefPtr<HTMLFormCollection> create(Element*);
@@ -47 +47 @@
 
     virtual void updateNameCache() const;
-    virtual unsigned calcLength() const;
 
     const Vector<FormAssociatedElement*>& formControlElements() const;
     const Vector<HTMLImageElement*>& formImageElements() const;
-    HTMLElement* itemInArrayAfter(unsigned& offset, HTMLElement* previousItem) const OVERRIDE;
+    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
 };
 

trunk/Source/WebCore/html/HTMLNameCollection.cpp

@@ -50 +50 @@
 }
 
-Element* HTMLNameCollection::itemAfter(Node* previous) const
+Element* HTMLNameCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
 {
+    ASSERT_UNUSED(offsetInArray, !offsetInArray);
     ASSERT(previous != base());
 

trunk/Source/WebCore/html/HTMLNameCollection.h

@@ -44 +44 @@
     HTMLNameCollection(Document*, CollectionType, const AtomicString& name);
 
-    virtual Element* itemAfter(Node*) const OVERRIDE;
+    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
 
     AtomicString m_name;

trunk/Source/WebCore/html/HTMLPropertiesCollection.cpp

@@ -52 +52 @@
 
 HTMLPropertiesCollection::HTMLPropertiesCollection(Node* itemNode)
-    : HTMLCollectionWithArrayStorage(itemNode, ItemProperties)
+    : HTMLCollection(itemNode, ItemProperties)
     , m_hasPropertyNameCache(false)
     , m_hasItemRefElements(false)
@@ -113 +113 @@
 }
 
-HTMLElement* HTMLPropertiesCollection::itemInArrayAfter(unsigned& offsetInArray, HTMLElement* previousItem) const
+Element* HTMLPropertiesCollection::itemAfter(unsigned& offsetInArray, Element* previousItem) const
 {
     while (offsetInArray < m_itemRefElements.size()) {
-        if (HTMLElement* next = itemAfter(m_itemRefElements[offsetInArray], previousItem))
+        if (Element* next = itemAfter(m_itemRefElements[offsetInArray], previousItem))
             return next;
         offsetInArray++;
@@ -124 +124 @@
 }
 
-HTMLElement* HTMLPropertiesCollection::itemAfter(HTMLElement* base, HTMLElement* previous) const
+HTMLElement* HTMLPropertiesCollection::itemAfter(HTMLElement* base, Element* previous) const
 {
     Node* current;
@@ -139 +139 @@
 
     return 0;
-}
-
-unsigned HTMLPropertiesCollection::calcLength() const
-{
-    unsigned length = 0;
-    updateRefElements();
-
-    for (unsigned i = 0; i < m_itemRefElements.size(); ++i) {
-        for (HTMLElement* element = itemAfter(m_itemRefElements[i], 0); element; element = itemAfter(m_itemRefElements[i], element))
-            ++length;
-    }
-
-    return length;
 }
 

trunk/Source/WebCore/html/HTMLPropertiesCollection.h

@@ -41 +41 @@
 class DOMStringList;
 
-class HTMLPropertiesCollection : public HTMLCollectionWithArrayStorage {
+class HTMLPropertiesCollection : public HTMLCollection {
 public:
     static PassRefPtr<HTMLPropertiesCollection> create(Node*);
@@ -64 +64 @@
     HTMLPropertiesCollection(Node*);
 
-    virtual unsigned calcLength() const OVERRIDE;
-
     Node* findRefElements(Node* previous) const;
 
-    void cacheFirstItem() const;
-    virtual HTMLElement* itemInArrayAfter(unsigned& offsetInArray, HTMLElement* previousItemInSameArrayElement) const OVERRIDE;
-    HTMLElement* itemAfter(HTMLElement* base, HTMLElement* previous) const;
+    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
+    HTMLElement* itemAfter(HTMLElement* base, Element* previous) const;
 
     void updateNameCache() const;

trunk/Source/WebCore/html/HTMLTableRowsCollection.cpp

@@ -163 +163 @@
 }
 
-Element* HTMLTableRowsCollection::itemAfter(Node* previous) const
+Element* HTMLTableRowsCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
 {
+    ASSERT_UNUSED(offsetInArray, !offsetInArray);
     ASSERT(!previous || (previous->isHTMLElement() && toHTMLElement(previous)->hasLocalName(trTag)));
     return rowAfter(static_cast<HTMLTableElement*>(base()), static_cast<HTMLTableRowElement*>(previous));

trunk/Source/WebCore/html/HTMLTableRowsCollection.h

@@ -47 +47 @@
     HTMLTableRowsCollection(Element*);
 
-    virtual Element* itemAfter(Node*) const OVERRIDE;
+    virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
 };