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