You are viewing a plain text version of this content. The canonical link for it is here.
Posted to c-dev@xerces.apache.org by bu...@apache.org on 2002/08/07 04:10:26 UTC
DO NOT REPLY [Bug 11515] New: -
Exponential time using DOMTreeWalker
DO NOT REPLY TO THIS EMAIL, BUT PLEASE POST YOUR BUG
RELATED COMMENTS THROUGH THE WEB INTERFACE AVAILABLE AT
<http://nagoya.apache.org/bugzilla/show_bug.cgi?id=11515>.
ANY REPLY MADE TO THIS MESSAGE WILL NOT BE COLLECTED AND
INSERTED IN THE BUG DATABASE.
http://nagoya.apache.org/bugzilla/show_bug.cgi?id=11515
Exponential time using DOMTreeWalker
Summary: Exponential time using DOMTreeWalker
Product: Xerces-C++
Version: 2.0.0
Platform: All
OS/Version: All
Status: NEW
Severity: Major
Priority: Other
Component: DOM
AssignedTo: xerces-c-dev@xml.apache.org
ReportedBy: benjamin.piwowarski@lip6.fr
Problem with DOMTreeWalker :
When calling lastChild(...) or firstChild(...), the algorithm used can be
exponential as already explored paths can be explored again (and again).
Example:
Take the document
<a>
<b2><c2></c2></c2>
<b1><c1></c1></b1>
<b0><c0></c0></b0>
</a>
and configure the DOMTreeWalker so as to skip all nodes but "a".
With a call to lastChild(a), we will get the following algorithm
lastChild(a)
[1] -> getLastChild(b0)
[2] --> getPreviousSibling(c0)
[3] ---> getPreviousSibling(b0)
[4] ----> getLastChild(b1)
[5] -----> getPreviousSibling(c1)
[6] ------> getPreviousSibling(b1)
[7] -------> getLastChild(b2)
[8] --------> getPreviousSibling(c2)
[9] ---------> getPreviousSibling(b2) [ returns 0 to getPreviousSibling(b1) ]
[7] -------> getPreviousSibling(b2) [ we've been there, returns 0 to
getPreviousSibling(b0) ]
[4] ----> getPreviousSibing(b1) [wc've been there]
[5] -----> getPreviousSibling(b2) [we've been there, returns 0 to
getPreviousSibling(b0) ]
[4] ----> getPreviousSibling(b1)
[5] -----> getLastChild(b2) [ we've been there ]
...
The solution to avoid this, is to make getPreviousSibling avoid to call
getPreviousSibling for a previous sibling node N2 whenever this node has a child
(because getLastChild will call getPreviousSibling N2 if (1) it has a child (2)
All its children are skipped).
Modifications :
in DOMTreeWalkerImpl.cpp
...
DOMNode* DOMTreeWalkerImpl::getNextSibling (DOMNode* node) {
...
[line 363, v2.0.0] if (!fChild && !newNode->hasChildNodes()) {
...
[line 405, v2.0.0] DOMNode* DOMTreeWalkerImpl::getPreviousSibling (DOMNode* node) {
...
if (!fChild && !newNode->hasChildNodes()) {
...
---------------------------------------------------------------------
To unsubscribe, e-mail: xerces-c-dev-unsubscribe@xml.apache.org
For additional commands, e-mail: xerces-c-dev-help@xml.apache.org