You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@xerces.apache.org by le...@locus.apache.org on 2000/10/19 19:10:30 UTC
cvs commit: xml-xerces/java/src/org/apache/xerces/dom RangeImpl.java
lehors 00/10/19 10:10:29
Modified: java/src/org/apache/xerces/dom RangeImpl.java
Log:
applied patch from Lynn Moson:
Performance problems
In some cases, compareBoundaryPoints() requires a partial walk of the DOM
tree. The existing Xerces code did this very inefficiently. For large
trees, or when large numbers of ranges are compared, this can be a
bottleneck. It was for us. Our new implementation maintains the same
semantics, but with a far more efficient implementation.
Revision Changes Path
1.8 +32 -11 xml-xerces/java/src/org/apache/xerces/dom/RangeImpl.java
Index: RangeImpl.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/RangeImpl.java,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- RangeImpl.java 2000/10/02 21:58:22 1.7
+++ RangeImpl.java 2000/10/19 17:10:29 1.8
@@ -415,18 +415,39 @@
}
}
// case 4: preorder traversal of context tree.
- Node ancestor = getCommonAncestorContainer();
- Node current = ancestor;
-
- do {
- if (current == endPointA) return -1;
- if (current == endPointB) return 1;
- current = nextNode(current, true);// REVIST this...
+ // Instead of literally walking the context tree in pre-order,
+ // we use relative node depth walking which is usually faster
+
+ int depthDiff = 0;
+ for ( Node n = endPointA; n != null; n = n.getParentNode() )
+ depthDiff++;
+ for ( Node n = endPointB; n != null; n = n.getParentNode() )
+ depthDiff--;
+ while (depthDiff > 0) {
+ endPointA = endPointA.getParentNode();
+ depthDiff--;
}
- while (current!=null && current!=ancestor);
-
- // REVISIT: this should never happen?!?!?!?
- return -2;
+ while (depthDiff < 0) {
+ endPointB = endPointB.getParentNode();
+ depthDiff++;
+ }
+ for (Node pA = endPointA.getParentNode(),
+ pB = endPointB.getParentNode();
+ pA != pB;
+ pA = pA.getParentNode(), pB = pB.getParentNode() )
+ {
+ endPointA = pA;
+ endPointB = pB;
+ }
+ for ( Node n = endPointA.getNextSibling();
+ n != null;
+ n = n.getNextSibling() )
+ {
+ if (n == endPointB) {
+ return -1;
+ }
+ }
+ return 1;
}
public void deleteContents()