+2004-11-18 Maciej Stachowiak <mjs@apple.com>
+
+ Reviewed by Ken.
+
+ - merged and cleaned up HTMLCollection and HTMLFormCollection speedups from konqueror
+
+ <rdar://problem/3822992> VIP: Program listings pages at directv.com take a really long time to load [HTMLCollection]
+ <rdar://problem/3701991> Safari unresponsive loading (www.maxim-ic.com) (HTMLCollection)
+
+ This is also a start on fixing 5 other bugs, but those need additional work to make
+ HTMLFormCollection fast.
+
+ * khtml/html/html_documentimpl.h:
+ (DOM::HTMLDocumentImpl::collectionInfo):
+ * khtml/html/html_formimpl.cpp:
+ (DOM::HTMLFormElementImpl::~HTMLFormElementImpl):
+ (DOM::HTMLFormElementImpl::isURLAttribute):
+ (DOM::HTMLFormElementImpl::registerImgElement):
+ (DOM::HTMLFormElementImpl::removeImgElement):
+ * khtml/html/html_formimpl.h:
+ * khtml/html/html_imageimpl.cpp:
+ (HTMLImageElementImpl::HTMLImageElementImpl):
+ (HTMLImageElementImpl::~HTMLImageElementImpl):
+ * khtml/html/html_imageimpl.h:
+ * khtml/html/html_miscimpl.cpp:
+ (HTMLCollectionImpl::HTMLCollectionImpl):
+ (HTMLCollectionImpl::~HTMLCollectionImpl):
+ (HTMLCollectionImpl::updateCollectionInfo):
+ (HTMLCollectionImpl::length):
+ (HTMLCollectionImpl::item):
+ (HTMLCollectionImpl::firstItem):
+ (HTMLCollectionImpl::nextItem):
+ (HTMLCollectionImpl::namedItem):
+ (HTMLCollectionImpl::nextNamedItemInternal):
+ (HTMLFormCollectionImpl::getNamedFormItem):
+ * khtml/html/html_miscimpl.h:
+ (DOM::HTMLCollectionImpl::):
+ (DOM::HTMLCollectionImpl::CollectionInfo::CollectionInfo):
+ * khtml/html/htmlparser.cpp:
+ (KHTMLParser::getElement):
+ * khtml/xml/dom_docimpl.cpp:
+ (DocumentImpl::DocumentImpl):
+ * khtml/xml/dom_docimpl.h:
+ (DOM::DocumentImpl::incDOMTreeVersion):
+ (DOM::DocumentImpl::domTreeVersion):
+ * khtml/xml/dom_nodeimpl.cpp:
+ (NodeImpl::attach):
+ (NodeImpl::detach):
+
2004-11-18 Kevin Decker <kdecker@apple.com>
Reviewed by Chris.
// -------------------------------------------------------------------------
#include "html/html_miscimpl.h"
#include "html/html_formimpl.h"
+#include "html/html_imageimpl.h"
+#include "html/html_documentimpl.h"
#include "misc/htmlhashes.h"
#include "dom/dom_node.h"
base = _base;
base->ref();
type = _type;
- currentItem = 0L;
idsDone = false;
+ info = base->isDocumentNode() ? static_cast<HTMLDocumentImpl*>(base->getDocument())->collectionInfo(type) : new CollectionInfo;
}
HTMLCollectionImpl::~HTMLCollectionImpl()
{
+ if (!base->isDocumentNode())
+ delete info;
base->deref();
}
+void HTMLCollectionImpl::resetCollectionInfo() const
+{
+ unsigned int docversion = static_cast<HTMLDocumentImpl*>(base->getDocument())->domTreeVersion();
+ if (info->version != docversion) {
+ version = 0;
+ current = 0;
+ position = 0;
+ length = 0;
+ hasLength = false;
+ info->version = docversion;
+ }
+}
+
unsigned long HTMLCollectionImpl::calcLength(NodeImpl *current) const
{
unsigned long len = 0;
// calculation every time...
unsigned long HTMLCollectionImpl::length() const
{
- return calcLength(base->firstChild());
+ resetCollectionInfo();
+ if (!info->haslength) {
+ info->length = calcLength(base->firstChild());
+ info->haslength = true;
+ }
+ return info->length;
}
NodeImpl *HTMLCollectionImpl::getItem(NodeImpl *current, int index, int &len) const
NodeImpl *HTMLCollectionImpl::item( unsigned long index ) const
{
- int pos = 0;
- return getItem(base->firstChild(), index, pos);
+ resetCollectionInfo();
+ if (info->current && info->position == index) {
+ return info->current;
+ }
+ if (info->haslength && info->length <= index) {
+ return 0;
+ }
+ if (!info->current || info->position > index) {
+ info->current = base->firstChild();
+ info->position = 0;
+ if (!info->current)
+ return 0;
+ }
+ int pos = (int) info->position;
+ NodeImpl *node = getItem(info->current, index, pos);
+ while (!node && info->current->parentNode() && info->current->parentNode() != base) {
+ info->current = info->current->parentNode();
+ if (info->current->nextSibling())
+ node = getItem(info->current->nextSibling(), index, pos);
+
+ }
+ info->current = node;
+ info->position = index;
+ return info->current;
}
NodeImpl *HTMLCollectionImpl::firstItem() const
{
- int pos = 0;
- currentItem = getItem(base->firstChild(), 0, pos);
- return currentItem;
+ return item(0);
}
NodeImpl *HTMLCollectionImpl::nextItem() const
{
- int pos = 0;
- // Look for the 'second' item. The first one is currentItem, already given back.
- NodeImpl *retval = getItem(currentItem, 1, pos);
- if (retval)
- {
- currentItem = retval;
- return retval;
- }
- // retval was 0, means we have to go up
- while( !retval && currentItem && currentItem->parentNode()
- && currentItem->parentNode() != base )
- {
- currentItem = currentItem->parentNode();
- if (currentItem->nextSibling())
- {
- // ... and to take the first one from there
- pos = 0;
- retval = getItem(currentItem->nextSibling(), 0, pos);
- }
- }
- currentItem = retval;
- return currentItem;
+ resetCollectionInfo();
+ int pos = 0;
+
+ info->position = ~0; // no position
+ // Look for the 'second' item. The first one is currentItem, already given back.
+ NodeImpl *retval = getItem(info->current, 1, pos);
+ if (retval)
+ {
+ info->current = retval;
+ return retval;
+ }
+ // retval was 0, means we have to go up
+ while( !retval && info->current->parentNode()
+ && info->current->parentNode() != base )
+ {
+ info->current = info->current->parentNode();
+ if (info->current->nextSibling())
+ {
+ // ... and to take the first one from there
+ pos = 0;
+ retval = getItem(info->current->nextSibling(), 0, pos);
+ }
+ }
+ info->current = retval;
+ return info->current;
}
NodeImpl *HTMLCollectionImpl::getNamedItem( NodeImpl *current, int attr_id,
// attribute. If a match is not found, the method then searches for an
// object with a matching name attribute, but only on those elements
// that are allowed a name attribute.
+ resetCollectionInfo();
+ info->position = ~0; // no position
idsDone = false;
- currentItem = getNamedItem(base->firstChild(), ATTR_ID, name, caseSensitive);
- if(currentItem)
- return currentItem;
+ info->current = getNamedItem(base->firstChild(), ATTR_ID, name);
+ if(info->current)
+ return info->current;
idsDone = true;
- currentItem = getNamedItem(base->firstChild(), ATTR_NAME, name, caseSensitive);
- return currentItem;
+ info->current = getNamedItem(base->firstChild(), ATTR_NAME, name);
+ return info->current;
}
NodeImpl *HTMLCollectionImpl::nextNamedItem( const DOMString &name ) const
NodeImpl *HTMLCollectionImpl::nextNamedItemInternal( const DOMString &name ) const
{
- //kdDebug() << "\nHTMLCollectionImpl::nextNamedItem starting at " << currentItem << endl;
+ resetCollectionInfo();
+ //kdDebug() << "\nHTMLCollectionImpl::nextNamedItem starting at " << info->current << endl;
// Go to next item first (to avoid returning the same)
- currentItem = nextItem();
- //kdDebug() << "*HTMLCollectionImpl::nextNamedItem next item is " << currentItem << endl;
+ nextItem(); // sets info->current and invalidates info->postion
+ //kdDebug() << "*HTMLCollectionImpl::nextNamedItem next item is " << info->current << endl;
- if ( currentItem )
+ if ( info->current )
{
// Then look for next matching named item
- NodeImpl *retval = getNamedItem(currentItem, idsDone ? ATTR_NAME : ATTR_ID, name);
+ NodeImpl *retval = getNamedItem(info->current, idsDone ? ATTR_NAME : ATTR_ID, name);
if ( retval )
{
//kdDebug() << "*HTMLCollectionImpl::nextNamedItem found " << retval << endl;
- currentItem = retval;
+ info->current = retval;
return retval;
}
// retval was 0, means we have to go up
- while( !retval && currentItem->parentNode()
- && currentItem->parentNode() != base )
+ while( !retval && info->current->parentNode()
+ && info->current->parentNode() != base )
{
- currentItem = currentItem->parentNode();
- if (currentItem->nextSibling())
+ info->current = info->current->parentNode();
+ if (info->current->nextSibling())
{
// ... and to take the first one from there
- retval = getNamedItem(currentItem->nextSibling(), idsDone ? ATTR_NAME : ATTR_ID, name);
+ retval = getNamedItem(info->current->nextSibling(), idsDone ? ATTR_NAME : ATTR_ID, name);
}
}
if ( retval )
{
//kdDebug() << "*HTMLCollectionImpl::nextNamedItem found after going up " << retval << endl;
- currentItem = retval;
- return currentItem;
+ info->current = retval;
+ return info->current;
}
}
// After doing all ATTR_ID, do ATTR_NAME
//kdDebug() << "*HTMLCollectionImpl::nextNamedItem going to ATTR_NAME now" << endl;
idsDone = true;
- currentItem = getNamedItem(base->firstChild(), ATTR_NAME, name);
- return currentItem;
+ info->current = getNamedItem(base->firstChild(), ATTR_NAME, name);
+ return info->current;
}
if(base->nodeType() == Node::ELEMENT_NODE)
{
HTMLElementImpl* e = static_cast<HTMLElementImpl*>(base);
+ bool foundInputElements = false;
if(e->id() == ID_FORM)
{
HTMLFormElementImpl* f = static_cast<HTMLFormElementImpl*>(e);
else
found = e->getAttribute(attr_id).domString().lower() == name.lower();
if (found) {
+ foundInputElements = true;
if (!duplicateNumber)
return e;
--duplicateNumber;
}
}
}
- NodeImpl* retval = getNamedImgItem( base->firstChild(), attr_id, name, duplicateNumber, caseSensitive );
- if ( retval )
- return retval;
- }
- return 0;
-}
-NodeImpl* HTMLFormCollectionImpl::getNamedImgItem(NodeImpl* current, int attr_id, const DOMString& name, int& duplicateNumber, bool caseSensitive) const
-{
- // strange case. IE and NS allow to get hold of <img> tags,
- // but they don't include them in the elements() collection.
- while ( current )
- {
- if(current->nodeType() == Node::ELEMENT_NODE)
+ if ( !foundInputElements )
{
- HTMLElementImpl *e = static_cast<HTMLElementImpl *>(current);
- if(e->id() == ID_IMG) {
+ HTMLFormElementImpl* f = static_cast<HTMLFormElementImpl*>(e);
+
+ for(HTMLImageElementImpl* e = f->imgElements.first(); e; e = f->imgElements.next())
+ {
bool found;
if (caseSensitive)
found = e->getAttribute(attr_id) == name;
else
found = e->getAttribute(attr_id).domString().lower() == name.lower();
- if (found)
- {
+ if (found) {
if (!duplicateNumber)
- return current;
+ return e;
--duplicateNumber;
}
}
- if(current->firstChild())
- {
- // The recursion here is the reason why this is a separate method
- NodeImpl *retval = getNamedImgItem(current->firstChild(), attr_id, name, duplicateNumber, caseSensitive);
- if(retval)
- {
- //kdDebug( 6030 ) << "got a return value " << retval << endl;
- return retval;
- }
- }
}
- current = current->nextSibling();
- } // while
+ }
return 0;
}
public:
enum Type {
// from HTMLDocument
- DOC_IMAGES, // all IMG elements in the document
+ DOC_IMAGES = 0, // all IMG elements in the document
DOC_APPLETS, // all OBJECT and APPLET elements
DOC_EMBEDS, // all EMBED elements
DOC_FORMS, // all FORMS
// from HTMLMap
MAP_AREAS,
DOC_ALL, // "all" elements (IE)
- NODE_CHILDREN // first-level children (IE)
+ NODE_CHILDREN, // first-level children (IE)
+ LAST_TYPE
};
HTMLCollectionImpl(NodeImpl *_base, int _tagId);
// In case of multiple items named the same way
NodeImpl *nextNamedItem( const DOMString &name ) const;
+ struct CollectionInfo {
+ CollectionInfo() : version(0), current(0), position(0), length(0), hasLength(false) {}
+ unsigned int version;
+ NodeImpl *current;
+ unsigned int position;
+ unsigned int length;
+ bool haslength;
+ };
+
protected:
virtual unsigned long calcLength(NodeImpl *current) const;
virtual NodeImpl *getItem(NodeImpl *current, int index, int &pos) const;
virtual NodeImpl *getNamedItem(NodeImpl *current, int attr_id, const DOMString &name, bool caseSensitive = true) const;
virtual NodeImpl *nextNamedItemInternal( const DOMString &name ) const;
+ void resetCollectionInfo() const;
// the base node, the collection refers to
NodeImpl *base;
// The collection list the following elements
int type;
+ mutable CollectionInfo *info;
- // ### add optimization, so that a linear loop through the
- // Collection [using item(i)] is O(n) and not O(n^2)!
- // But for that we need to get notified in case of changes in the dom structure...
- //NodeImpl *current;
- //int currentPos;
-
- // For firstItem()/nextItem()
- mutable NodeImpl *currentItem;
// For nextNamedItem()
mutable bool idsDone;
};
virtual NodeImpl *nextNamedItemInternal( const DOMString &name ) const;
private:
NodeImpl* getNamedFormItem(int attr_id, const DOMString& name, int duplicateNumber, bool caseSensitive) const;
- NodeImpl* getNamedImgItem(NodeImpl* current, int attr_id, const DOMString& name, int& duplicateNumber, bool caseSensitive) const;
mutable int currentPos;
};
git://git.webkit.org / WebKit-https.git / commitdiff