Diff
Modified: trunk/Source/WebCore/ChangeLog (122517 => 122518)
--- trunk/Source/WebCore/ChangeLog 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/ChangeLog 2012-07-12 22:40:26 UTC (rev 122518)
@@ -1,3 +1,64 @@
+2012-07-12 Ryosuke Niwa <[email protected]>
+
+ 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 <[email protected]>
Row size/position is wrongly calculated when table having overlapping rowspan cell and colspan cell
Modified: trunk/Source/WebCore/dom/DynamicNodeList.h (122517 => 122518)
--- trunk/Source/WebCore/dom/DynamicNodeList.h 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/dom/DynamicNodeList.h 2012-07-12 22:40:26 UTC (rev 122518)
@@ -64,6 +64,7 @@
}
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;
m_isItemCacheValid = true;
Modified: trunk/Source/WebCore/html/HTMLCollection.cpp (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLCollection.cpp 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLCollection.cpp 2012-07-12 22:40:26 UTC (rev 122518)
@@ -180,8 +180,9 @@
return includeChildren ? node->traverseNextNode(base) : node->traverseNextSibling(base);
}
-Element* HTMLCollection::itemAfter(Node* previous) const
+Element* HTMLCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
{
+ ASSERT_UNUSED(offsetInArray, !offsetInArray);
Node* current;
if (!previous)
current = m_base->firstChild();
@@ -199,44 +200,29 @@
return 0;
}
-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();
-Node* HTMLCollection::item(unsigned index) const
-{
- invalidateCacheIfNeeded();
- if (isItemCacheValid() && cachedItemOffset() == index)
- return cachedItem();
- if (isLengthCacheValid() && cachedLength() <= index)
+ if (!isItemCacheValid() && !item(0)) {
+ ASSERT(isLengthCacheValid());
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();
+
+ ASSERT(isItemCacheValid());
+ ASSERT(cachedItem());
+ unsigned offset = cachedItemOffset();
+ do {
+ offset++;
+ } while (itemAfterCachedItem(offset));
+
+ setLengthCache(offset);
+ return offset;
}
-Node* HTMLCollectionWithArrayStorage::item(unsigned index) const
+Node* HTMLCollection::item(unsigned index) const
{
invalidateCacheIfNeeded();
if (isItemCacheValid() && cachedItemOffset() == index)
@@ -252,23 +238,33 @@
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;
}
}
@@ -314,19 +310,20 @@
// that are allowed a name attribute.
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;
}
i++;
}
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;
}
i++;
@@ -341,7 +338,8 @@
if (hasNameCache())
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;
HTMLElement* e = toHTMLElement(element);
Modified: trunk/Source/WebCore/html/HTMLCollection.h (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLCollection.h 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLCollection.h 2012-07-12 22:40:26 UTC (rev 122518)
@@ -63,7 +63,6 @@
m_hasNameCache = false;
}
- using DynamicNodeListCacheBase::setItemCache;
void setItemCache(Node* item, unsigned offset, unsigned elementsArrayOffset) const
{
setItemCache(item, offset);
@@ -89,6 +88,7 @@
using DynamicNodeListCacheBase::isRootedAtDocument;
using DynamicNodeListCacheBase::shouldInvalidateOnAttributeChange;
using DynamicNodeListCacheBase::clearCache;
+ using DynamicNodeListCacheBase::setItemCache;
mutable NodeCacheMap m_idCache;
mutable NodeCacheMap m_nameCache;
@@ -108,7 +108,7 @@
// 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&);
@@ -143,30 +143,17 @@
HTMLCollection(Node* base, CollectionType);
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;
RefPtr<Node> m_base;
};
-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
#endif
Modified: trunk/Source/WebCore/html/HTMLFormCollection.cpp (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLFormCollection.cpp 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLFormCollection.cpp 2012-07-12 22:40:26 UTC (rev 122518)
@@ -37,7 +37,7 @@
// calculation every time if anything has changed.
HTMLFormCollection::HTMLFormCollection(Element* base)
- : HTMLCollectionWithArrayStorage(base, FormControls)
+ : HTMLCollection(base, FormControls)
{
ASSERT(base->hasTagName(formTag) || base->hasTagName(fieldsetTag));
}
@@ -67,16 +67,8 @@
return static_cast<HTMLFormElement*>(base())->imageElements();
}
-unsigned HTMLFormCollection::calcLength() const
+Element* HTMLFormCollection::itemAfter(unsigned& offset, Element* previousItem) 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
-{
const Vector<FormAssociatedElement*>& elementsArray = formControlElements();
if (previousItem)
offset++;
Modified: trunk/Source/WebCore/html/HTMLFormCollection.h (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLFormCollection.h 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLFormCollection.h 2012-07-12 22:40:26 UTC (rev 122518)
@@ -34,7 +34,7 @@
// This class is just a big hack to find form elements even in malformed HTML elements.
// The famous <table><tr><form><td> problem.
-class HTMLFormCollection : public HTMLCollectionWithArrayStorage {
+class HTMLFormCollection : public HTMLCollection {
public:
static PassRefPtr<HTMLFormCollection> create(Element*);
@@ -46,11 +46,10 @@
HTMLFormCollection(Element*);
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;
};
} //namespace
Modified: trunk/Source/WebCore/html/HTMLNameCollection.cpp (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLNameCollection.cpp 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLNameCollection.cpp 2012-07-12 22:40:26 UTC (rev 122518)
@@ -49,8 +49,9 @@
static_cast<Document*>(base())->removeDocumentNamedItemCache(this, m_name);
}
-Element* HTMLNameCollection::itemAfter(Node* previous) const
+Element* HTMLNameCollection::itemAfter(unsigned& offsetInArray, Element* previous) const
{
+ ASSERT_UNUSED(offsetInArray, !offsetInArray);
ASSERT(previous != base());
Node* current;
Modified: trunk/Source/WebCore/html/HTMLNameCollection.h (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLNameCollection.h 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLNameCollection.h 2012-07-12 22:40:26 UTC (rev 122518)
@@ -43,7 +43,7 @@
private:
HTMLNameCollection(Document*, CollectionType, const AtomicString& name);
- virtual Element* itemAfter(Node*) const OVERRIDE;
+ virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
AtomicString m_name;
};
Modified: trunk/Source/WebCore/html/HTMLPropertiesCollection.cpp (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLPropertiesCollection.cpp 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLPropertiesCollection.cpp 2012-07-12 22:40:26 UTC (rev 122518)
@@ -51,7 +51,7 @@
}
HTMLPropertiesCollection::HTMLPropertiesCollection(Node* itemNode)
- : HTMLCollectionWithArrayStorage(itemNode, ItemProperties)
+ : HTMLCollection(itemNode, ItemProperties)
, m_hasPropertyNameCache(false)
, m_hasItemRefElements(false)
{
@@ -112,10 +112,10 @@
? node->traverseNextNode(base) : node->traverseNextSibling(base);
}
-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++;
previousItem = 0;
@@ -123,7 +123,7 @@
return 0;
}
-HTMLElement* HTMLPropertiesCollection::itemAfter(HTMLElement* base, HTMLElement* previous) const
+HTMLElement* HTMLPropertiesCollection::itemAfter(HTMLElement* base, Element* previous) const
{
Node* current;
current = previous ? nextNodeWithProperty(base, previous) : base;
@@ -140,19 +140,6 @@
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;
-}
-
void HTMLPropertiesCollection::updateNameCache() const
{
invalidateCacheIfNeeded();
Modified: trunk/Source/WebCore/html/HTMLPropertiesCollection.h (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLPropertiesCollection.h 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLPropertiesCollection.h 2012-07-12 22:40:26 UTC (rev 122518)
@@ -40,7 +40,7 @@
class DOMStringList;
-class HTMLPropertiesCollection : public HTMLCollectionWithArrayStorage {
+class HTMLPropertiesCollection : public HTMLCollection {
public:
static PassRefPtr<HTMLPropertiesCollection> create(Node*);
virtual ~HTMLPropertiesCollection();
@@ -63,13 +63,10 @@
private:
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;
Modified: trunk/Source/WebCore/html/HTMLTableRowsCollection.cpp (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLTableRowsCollection.cpp 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLTableRowsCollection.cpp 2012-07-12 22:40:26 UTC (rev 122518)
@@ -162,8 +162,9 @@
return adoptRef(new HTMLTableRowsCollection(table));
}
-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));
}
Modified: trunk/Source/WebCore/html/HTMLTableRowsCollection.h (122517 => 122518)
--- trunk/Source/WebCore/html/HTMLTableRowsCollection.h 2012-07-12 22:35:40 UTC (rev 122517)
+++ trunk/Source/WebCore/html/HTMLTableRowsCollection.h 2012-07-12 22:40:26 UTC (rev 122518)
@@ -46,7 +46,7 @@
private:
HTMLTableRowsCollection(Element*);
- virtual Element* itemAfter(Node*) const OVERRIDE;
+ virtual Element* itemAfter(unsigned& offsetInArray, Element*) const OVERRIDE;
};
} // namespace
