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/09/15 19:01:44 UTC
cvs commit: xml-xerces/java/src/org/apache/xerces/dom AttrImpl.java ChildAndParentNode.java ChildNode.java DeferredDocumentImpl.java DocumentImpl.java EntityReferenceImpl.java NodeImpl.java ParentNode.java TextImpl.java
lehors 00/09/15 10:01:44
Modified: java/src/org/apache/xerces/parsers Tag: arraybased-dom
DOMParser.java
java/src/org/apache/xerces/dom Tag: arraybased-dom
AttrImpl.java ChildAndParentNode.java
ChildNode.java DeferredDocumentImpl.java
DocumentImpl.java EntityReferenceImpl.java
NodeImpl.java ParentNode.java TextImpl.java
Log:
This is an experiment at changing the internal DOM structure
from a linked list based structure to an array based structure.
The array based structure comes from Crimson.
This structure is inherently more compact, but the gain in memory can only
be achieved at the expense of a performance hit. Indeed, the problem with
arrays is that you never know what size to give them in the first place.
Crimson's implementation uses an original size of 5, and doubles this size
every time it reaches the limit. In addition, it provides for a method to be
called when additions to the node are finished to resize the array the size
actually needed. This is called for instance by the parser in the endElement
callback. But, if this leads to less memory waste it also means a bigger
performance hit.
At any rate, I was expecting quite a bit of improvement but the tests I've
run so far have been very disappointing. It is much slower, and it appears
to use more memory. I just don't understand what's going on. Nevertheless,
I'm checking this into a CVS branch so this work isn't completely lost and
can possibly be looked at further some other time.
Revision Changes Path
No revision
No revision
1.27.2.1 +4 -1 xml-xerces/java/src/org/apache/xerces/parsers/DOMParser.java
Index: DOMParser.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/parsers/DOMParser.java,v
retrieving revision 1.27
retrieving revision 1.27.2.1
diff -u -r1.27 -r1.27.2.1
--- DOMParser.java 2000/09/01 18:10:19 1.27
+++ DOMParser.java 2000/09/15 17:01:39 1.27.2.1
@@ -108,7 +108,7 @@
* DOMParser provides a parser which produces a W3C DOM tree as its output
*
*
- * @version $Id: DOMParser.java,v 1.27 2000/09/01 18:10:19 lehors Exp $
+ * @version $Id: DOMParser.java,v 1.27.2.1 2000/09/15 17:01:39 lehors Exp $
*/
public class DOMParser
extends XMLParser
@@ -1142,6 +1142,9 @@
else {
fCurrentElementNode = fCurrentElementNode.getParentNode();
fWithinElement = false;
+ if (fDocumentImpl != null) {
+ ((NodeImpl)fCurrentElementNode).reduceWaste();
+ }
}
} // endElement(QName)
No revision
No revision
1.21.2.1 +24 -31 xml-xerces/java/src/org/apache/xerces/dom/AttrImpl.java
Index: AttrImpl.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/AttrImpl.java,v
retrieving revision 1.21
retrieving revision 1.21.2.1
diff -u -r1.21 -r1.21.2.1
--- AttrImpl.java 2000/08/18 01:58:34 1.21
+++ AttrImpl.java 2000/09/15 17:01:40 1.21.2.1
@@ -237,19 +237,19 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- while(firstChild!=null)
- internalRemoveChild(firstChild,MUTATION_LOCAL);
+ while (length != 0)
+ internalRemoveChild(children[0], MUTATION_LOCAL);
}
else
{
// simply discard children
- if (firstChild != null) {
- // remove ref from first child to last child
- firstChild.previousSibling = null;
- firstChild.isFirstChild(false);
- // then remove ref to first child
- firstChild = null;
+ for (int i = 0; i < length; i++) {
+ // remove ref from every child to this node
+ children[i].ownerNode = ownerDocument;
+ children[i].isOwned(false);
+ children[i].parentIndex = -1;
}
+ length = 0;
needsSyncChildren(false);
}
@@ -283,17 +283,15 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- if (firstChild == null) {
+ if (length == 0) {
return "";
}
- ChildNode node = firstChild.nextSibling;
- if (node == null) {
- return firstChild.getNodeValue();
- }
- StringBuffer value = new StringBuffer(firstChild.getNodeValue());
- while (node != null) {
- value.append(node.getNodeValue());
- node = node.nextSibling;
+ if (length == 1) {
+ return children[0].getNodeValue();
+ }
+ StringBuffer value = new StringBuffer(children[0].getNodeValue());
+ for (int i = 1; i < length; i++) {
+ value.append(children[i].getNodeValue());
}
return value.toString();
@@ -353,20 +351,15 @@
public void normalize() {
Node kid, next;
- for (kid = firstChild; kid != null; kid = next) {
- next = kid.getNextSibling();
-
- // If kid and next are both Text nodes (but _not_ CDATASection,
- // which is a subclass of Text), they can be merged.
- if (next != null
- && kid.getNodeType() == Node.TEXT_NODE
- && next.getNodeType() == Node.TEXT_NODE)
- {
- ((Text)kid).appendData(next.getNodeValue());
- removeChild(next);
- next = kid; // Don't advance; there might be another.
- }
-
+ for (int i = 0; i < length; i++) {
+ // If kid and next are both Text nodes (but _not_ CDATASection,
+ // which is a subclass of Text), they can be merged.
+ if (i + 1 < length
+ && children[i].getNodeType() == Node.TEXT_NODE
+ && children[i + 1].getNodeType() == Node.TEXT_NODE) {
+ ((Text)children[i]).appendData(children[i + 1].getNodeValue());
+ removeChild(children[i + 1]);
+ }
}
} // normalize()
1.14.2.1 +156 -209 xml-xerces/java/src/org/apache/xerces/dom/ChildAndParentNode.java
Index: ChildAndParentNode.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/ChildAndParentNode.java,v
retrieving revision 1.14
retrieving revision 1.14.2.1
diff -u -r1.14 -r1.14.2.1
--- ChildAndParentNode.java 2000/08/29 18:48:12 1.14
+++ ChildAndParentNode.java 2000/09/15 17:01:41 1.14.2.1
@@ -1,4 +1,4 @@
-/* $Id: ChildAndParentNode.java,v 1.14 2000/08/29 18:48:12 lehors Exp $ */
+/* $Id: ChildAndParentNode.java,v 1.14.2.1 2000/09/15 17:01:41 lehors Exp $ */
/*
* The Apache Software License, Version 1.1
*
@@ -80,20 +80,9 @@
/** Owner document. */
protected DocumentImpl ownerDocument;
- /** First child. */
- protected ChildNode firstChild = null;
+ protected ChildNode children [];
+ protected int length;
- // transients
-
- /** Cached node list length. */
- protected transient int nodeListLength = -1;
-
- /** Last requested node. */
- protected transient ChildNode nodeListNode;
-
- /** Last requested node index. */
- protected transient int nodeListIndex = -1;
-
//
// Constructors
//
@@ -110,6 +99,53 @@
/** Constructor for serialization. */
public ChildAndParentNode() {}
+ /**
+ * Called to minimize space utilization. Affects only
+ * this node; children must be individually trimmed.
+ */
+ public void trimToSize ()
+ {
+ if (length == 0)
+ children = null;
+ else if (children.length != length) {
+ ChildNode temp [] = new ChildNode [length];
+
+ System.arraycopy (children, 0, temp, 0, length);
+ children = temp;
+ }
+ }
+
+ public void reduceWaste ()
+ {
+ if (children == null)
+ return;
+
+ //
+ // Arbitrary -- rather than paying trimToSize() costs
+ // on most elements, we routinely accept some waste but
+ // do try to reduce egregious waste. Interacts with
+ // the array allocation done in appendChild.
+ //
+ if ((children.length - length) > 6)
+ trimToSize ();
+ }
+
+ /**
+ * Returns the index of the node in the list of children, such
+ * that <em>item()</em> will return that child.
+ *
+ * @param maybeChild the node which may be a child of this one
+ * @return the index of the node in the set of children, or
+ * else -1 if that node is not a child
+ */
+ final protected int getIndexOf(Node maybeChild)
+ {
+ for (int i = 0; i < length; i++)
+ if (children[i] == maybeChild)
+ return i;
+ return -1;
+ }
+
//
// NodeList methods
//
@@ -145,18 +181,13 @@
}
// Need to break the association w/ original kids
- newnode.firstChild = null;
-
- // invalidate cache for children NodeList
- newnode.nodeListIndex = -1;
- newnode.nodeListLength = -1;
+ newnode.children = null;
+ newnode.length = 0;
// Then, if deep, clone the kids too.
if (deep) {
- for (Node child = firstChild;
- child != null;
- child = child.getNextSibling()) {
- newnode.appendChild(child.cloneNode(true));
+ for (int i = 0; i < length; i++) {
+ newnode.appendChild(children[i].cloneNode(true));
}
}
@@ -189,9 +220,9 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- for (Node child = firstChild;
- child != null; child = child.getNextSibling()) {
- ((NodeImpl) child).setOwnerDocument(doc);
+ ownerDocument = doc;
+ for (int i = 0; i < length; i++) {
+ children[i].setOwnerDocument(doc);
}
ownerDocument = doc;
}
@@ -204,7 +235,7 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- return firstChild != null;
+ return length > 0;
}
/**
@@ -236,7 +267,9 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- return firstChild;
+ if (length == 0)
+ return null;
+ return children[0];
} // getFirstChild():Node
@@ -246,20 +279,16 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- return lastChild();
+ if (length == 0)
+ return null;
+ return children[length - 1];
} // getLastChild():Node
final ChildNode lastChild() {
- // last child is stored as the previous sibling of first child
- return firstChild != null ? firstChild.previousSibling : null;
- }
-
- final void lastChild(ChildNode node) {
- // store lastChild as previous sibling of first child
- if (firstChild != null) {
- firstChild.previousSibling = node;
- }
+ if (length == 0)
+ return null;
+ return children[length - 1];
}
/**
@@ -357,11 +386,9 @@
// No need to check kids for right-document; if they weren't,
// they wouldn't be kids of that DocFrag.
- for (Node kid = newChild.getFirstChild(); // Prescan
- kid != null;
- kid = kid.getNextSibling()) {
-
- if (errorChecking && !ownerDocument.isKidOK(this, kid)) {
+ for (int i = 0; i < length; i++) { // Prescan
+ if (errorChecking &&
+ !ownerDocument.isKidOK(this, children[i])) {
throw new DOMExceptionImpl(
DOMException.HIERARCHY_REQUEST_ERR,
"DOM006 Hierarchy request error");
@@ -403,66 +430,53 @@
oldparent.removeChild(newInternal);
}
- // Convert to internal type, to avoid repeated casting
- ChildNode refInternal = (ChildNode)refChild;
+ if (refChild == null) { // append
- // Attach up
- newInternal.ownerNode = this;
- newInternal.isOwned(true);
-
- // Attach before and after
- // Note: firstChild.previousSibling == lastChild!!
- if (firstChild == null) {
- // this our first and only child
- firstChild = newInternal;
- newInternal.isFirstChild(true);
- newInternal.previousSibling = newInternal;
- } else {
- if (refInternal == null) {
- // this is an append
- ChildNode lastChild = firstChild.previousSibling;
- lastChild.nextSibling = newInternal;
- newInternal.previousSibling = lastChild;
- firstChild.previousSibling = newInternal;
- } else {
- // this is an insert
- if (refChild == firstChild) {
- // at the head of the list
- firstChild.isFirstChild(false);
- newInternal.nextSibling = firstChild;
- newInternal.previousSibling =
- firstChild.previousSibling;
- firstChild.previousSibling = newInternal;
- firstChild = newInternal;
- newInternal.isFirstChild(true);
- } else {
- // somewhere in the middle
- ChildNode prev = refInternal.previousSibling;
- newInternal.nextSibling = refInternal;
- prev.nextSibling = newInternal;
- refInternal.previousSibling = newInternal;
- newInternal.previousSibling = prev;
- }
+ // this is the only place this vector needs allocating,
+ // though it may also need to be grown in insertBefore.
+ // most elements have very few children
+ if (children == null)
+ children = new ChildNode [3];
+ else if (children.length == length) {
+ ChildNode temp [] = new ChildNode [length * 2];
+ System.arraycopy(children, 0, temp, 0, length);
+ children = temp;
}
- }
- changed();
+ // set parent
+ newInternal.ownerNode = this;
+ newInternal.isOwned(true);
+ newInternal.parentIndex = length;
+
+ children [length++] = newInternal;
+
+ } else {
- // update cached length if we have any
- if (nodeListLength != -1) {
- nodeListLength++;
- }
- if (nodeListIndex != -1) {
- // if we happen to insert just before the cached node, update
- // the cache to the new node to match the cached index
- if (nodeListNode == refInternal) {
- nodeListNode = newInternal;
- } else {
- // otherwise just invalidate the cache
- nodeListIndex = -1;
+ // grow array if needed
+ if (children.length == length) {
+ ChildNode temp [] = new ChildNode [length * 2];
+ System.arraycopy(children, 0, temp, 0, length);
+ children = temp;
}
+
+ for (int i = 0; i < length; i++) {
+ if (children [i] != refChild)
+ continue;
+
+ // set parent
+ newInternal.ownerNode = this;
+ newInternal.isOwned(true);
+ newInternal.parentIndex = i;
+
+ System.arraycopy(children, i, children, i + 1, length - i);
+ children [i] = newInternal;
+ length++;
+ break;
+ }
}
+ changed();
+
if(MUTATIONEVENTS && ownerDocument.mutationEvents)
{
// MUTATION POST-EVENTS:
@@ -632,50 +646,24 @@
}
} // End mutation preprocessing
- // update cached length if we have any
- if (nodeListLength != -1) {
- nodeListLength--;
- }
- if (nodeListIndex != -1) {
- // if the removed node is the cached node
- // move the cache to its (soon former) previous sibling
- if (nodeListNode == oldInternal) {
- nodeListIndex--;
- nodeListNode = oldInternal.previousSibling();
- } else {
- // otherwise just invalidate the cache
- nodeListIndex = -1;
+ // Patch tree past oldChild
+ for (int i = 0; i < length; i++) {
+ if (children [i] != oldInternal)
+ continue;
+ if ((i + 1) != length) {
+ System.arraycopy (children, i + 1, children, i,
+ (length - 1) - i);
}
- }
+ length--;
+ children[length] = null;
- // Patch linked list around oldChild
- // Note: lastChild == firstChild.previousSibling
- if (oldInternal == firstChild) {
- // removing first child
- oldInternal.isFirstChild(false);
- firstChild = oldInternal.nextSibling;
- if (firstChild != null) {
- firstChild.isFirstChild(true);
- firstChild.previousSibling = oldInternal.previousSibling;
- }
- } else {
- ChildNode prev = oldInternal.previousSibling;
- ChildNode next = oldInternal.nextSibling;
- prev.nextSibling = next;
- if (next == null) {
- // removing last child
- firstChild.previousSibling = prev;
- } else {
- // removing some other child in the middle
- next.previousSibling = prev;
- }
- }
+ break;
+ }
// Remove oldInternal's references to tree
oldInternal.ownerNode = ownerDocument;
oldInternal.isOwned(false);
- oldInternal.nextSibling = null;
- oldInternal.previousSibling = null;
+ oldInternal.parentIndex = -1;
changed();
@@ -755,24 +743,7 @@
* @return int
*/
public int getLength() {
-
- if (nodeListLength == -1) { // is the cached length invalid ?
- ChildNode node;
- // start from the cached node if we have one
- if (nodeListIndex != -1 && nodeListNode != null) {
- nodeListLength = nodeListIndex;
- node = nodeListNode;
- } else {
- node = firstChild;
- nodeListLength = 0;
- }
- for (; node != null; node = node.nextSibling) {
- nodeListLength++;
- }
- }
-
- return nodeListLength;
-
+ return length;
} // getLength():int
/**
@@ -782,32 +753,13 @@
* @param Index int
*/
public Node item(int index) {
- // short way
- if (nodeListIndex != -1 && nodeListNode != null) {
- if (nodeListIndex < index) {
- while (nodeListIndex < index && nodeListNode != null) {
- nodeListIndex++;
- nodeListNode = nodeListNode.nextSibling;
- }
- }
- else if (nodeListIndex > index) {
- while (nodeListIndex > index && nodeListNode != null) {
- nodeListIndex--;
- nodeListNode = nodeListNode.previousSibling();
- }
- }
- return nodeListNode;
- }
-
- // long way
- nodeListNode = firstChild;
- for (nodeListIndex = 0;
- nodeListIndex < index && nodeListNode != null;
- nodeListIndex++) {
- nodeListNode = nodeListNode.nextSibling;
- }
- return nodeListNode;
-
+ if (length == 0 || index >= length)
+ return null;
+ try {
+ return children[index];
+ } catch (ArrayIndexOutOfBoundsException e) {
+ return null;
+ }
} // item(int):Node
//
@@ -822,8 +774,8 @@
public void normalize() {
Node kid;
- for (kid = firstChild; kid != null; kid = kid.getNextSibling()) {
- kid.normalize();
+ for (int i = 0; i < length; i++) {
+ children[i].normalize();
}
}
@@ -850,11 +802,9 @@
}
// Recursively set kids
- for (ChildNode mykid = firstChild;
- mykid != null;
- mykid = mykid.nextSibling) {
- if(!(mykid instanceof EntityReference)) {
- mykid.setReadOnly(readOnly,true);
+ for (int i = 0; i < length; i++) {
+ if(!(children[i] instanceof EntityReference)) {
+ children[i].setReadOnly(readOnly,true);
}
}
}
@@ -893,28 +843,29 @@
// create children and link them as siblings
DeferredDocumentImpl ownerDocument =
(DeferredDocumentImpl)this.ownerDocument;
- ChildNode first = null;
- ChildNode last = null;
- for (int index = ownerDocument.getLastChild(nodeIndex);
+
+ // first count them
+ for (int index = ownerDocument.getLastChild(nodeIndex, false);
index != -1;
- index = ownerDocument.getPrevSibling(index)) {
+ index = ownerDocument.getPrevSibling(index, false)) {
+ length++;
+ }
- ChildNode node = (ChildNode)ownerDocument.getNodeObject(index);
- if (last == null) {
- last = node;
- }
- else {
- first.previousSibling = node;
- }
- node.ownerNode = this;
- node.isOwned(true);
- node.nextSibling = first;
- first = node;
- }
- if (last != null) {
- firstChild = first;
- first.isFirstChild(true);
- lastChild(last);
+ // then fluff them up
+ if (length > 0) {
+ children = new ChildNode [length];
+
+ int count = length;
+ for (int index = ownerDocument.getLastChild(nodeIndex);
+ index != -1;
+ index = ownerDocument.getPrevSibling(index)) {
+
+ ChildNode node = (ChildNode)ownerDocument.getNodeObject(index);
+ node.ownerNode = this;
+ node.isOwned(true);
+ node.parentIndex = --count;
+ children[count] = node;
+ }
}
// set mutation events flag back to its original value
@@ -949,10 +900,6 @@
// to try to synchildren when we just desealize object.
needsSyncChildren(false);
-
- // initialize transients
- nodeListLength = -1;
- nodeListIndex = -1;
} // readObject(ObjectInputStream)
1.3.2.1 +34 -16 xml-xerces/java/src/org/apache/xerces/dom/ChildNode.java
Index: ChildNode.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/ChildNode.java,v
retrieving revision 1.3
retrieving revision 1.3.2.1
diff -u -r1.3 -r1.3.2.1
--- ChildNode.java 2000/07/07 20:33:07 1.3
+++ ChildNode.java 2000/09/15 17:01:41 1.3.2.1
@@ -83,12 +83,8 @@
// Data
//
- /** Previous sibling. */
- protected ChildNode previousSibling;
+ int parentIndex = -1; // cache
- /** Next sibling. */
- protected ChildNode nextSibling;
-
//
// Constructors
//
@@ -137,10 +133,8 @@
ChildNode newnode = (ChildNode) super.cloneNode(deep);
- // Need to break the association w/ original kids
- newnode.previousSibling = null;
- newnode.nextSibling = null;
- newnode.isFirstChild(false);
+ // invalidate cache
+ newnode.parentIndex = -1;
return newnode;
@@ -166,23 +160,47 @@
/** The next child of this node's parent, or null if none */
public Node getNextSibling() {
- return nextSibling;
+ NodeImpl parent = parentNode();
+ if (parent == null)
+ return null;
+ if (parentIndex < 0 || parent.item(parentIndex) != this)
+ parentIndex = parent.getIndexOf(this);
+ return parent.item(parentIndex + 1);
}
/** The previous child of this node's parent, or null if none */
public Node getPreviousSibling() {
- // if we are the firstChild, previousSibling actually refers to our
- // parent's lastChild, but we hide that
- return isFirstChild() ? null : previousSibling;
+ NodeImpl parent = parentNode();
+ if (parent == null)
+ return null;
+ if (parentIndex < 0 || parent.item(parentIndex) != this)
+ parentIndex = parent.getIndexOf(this);
+ return parent.item(parentIndex - 1);
}
/*
* same as above but returns internal type
*/
final ChildNode previousSibling() {
- // if we are the firstChild, previousSibling actually refers to our
- // parent's lastChild, but we hide that
- return isFirstChild() ? null : previousSibling;
+ NodeImpl parent = parentNode();
+ if (parent == null)
+ return null;
+ if (parentIndex < 0 || parent.item(parentIndex) != this)
+ parentIndex = parent.getIndexOf(this);
+ return (ChildNode) parent.item(parentIndex - 1);
+ }
+
+ //
+ // Protected methods
+ //
+
+ /** Denotes that this node has changed. */
+ protected void changed() {
+ // ++changes; we just let the parent know
+ NodeImpl parentNode = parentNode();
+ if (parentNode != null) {
+ parentNode.changed();
+ }
}
} // class ChildNode
1.20.2.1 +13 -17 xml-xerces/java/src/org/apache/xerces/dom/DeferredDocumentImpl.java
Index: DeferredDocumentImpl.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/DeferredDocumentImpl.java,v
retrieving revision 1.20
retrieving revision 1.20.2.1
diff -u -r1.20 -r1.20.2.1
--- DeferredDocumentImpl.java 2000/08/18 01:58:34 1.20
+++ DeferredDocumentImpl.java 2000/09/15 17:01:41 1.20.2.1
@@ -1385,24 +1385,26 @@
getNodeType(0);
- // create children and link them as siblings
- ChildNode first = null;
- ChildNode last = null;
+ // first count children
+ for (int index = getLastChild(0, false);
+ index != -1;
+ index = getPrevSibling(index, false)) {
+ length++;
+ }
+
+ // then fluff them up
+ children = new ChildNode [length];
+
+ int count = length;
for (int index = getLastChild(0);
index != -1;
index = getPrevSibling(index)) {
ChildNode node = (ChildNode)getNodeObject(index);
- if (last == null) {
- last = node;
- }
- else {
- first.previousSibling = node;
- }
node.ownerNode = this;
node.isOwned(true);
- node.nextSibling = first;
- first = node;
+ node.parentIndex = --count;
+ children[count] = node;
// save doctype and document type
int type = node.getNodeType();
@@ -1412,12 +1414,6 @@
else if (type == Node.DOCUMENT_TYPE_NODE) {
docType = (DocumentTypeImpl)node;
}
- }
-
- if (first != null) {
- firstChild = first;
- first.isFirstChild(true);
- lastChild(last);
}
// set mutation events flag back to its original value
1.40.2.1 +2 -2 xml-xerces/java/src/org/apache/xerces/dom/DocumentImpl.java
Index: DocumentImpl.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/DocumentImpl.java,v
retrieving revision 1.40
retrieving revision 1.40.2.1
diff -u -r1.40 -r1.40.2.1
--- DocumentImpl.java 2000/08/30 00:22:28 1.40
+++ DocumentImpl.java 2000/09/15 17:01:41 1.40.2.1
@@ -294,8 +294,8 @@
}
if (deep) {
- for (ChildNode n = firstChild; n != null; n = n.nextSibling) {
- newdoc.appendChild(newdoc.importNode(n, true));
+ for (int i = 0; i < length; i++) {
+ newdoc.appendChild(newdoc.importNode(children[i], true));
}
}
1.9.2.1 +1 -1 xml-xerces/java/src/org/apache/xerces/dom/EntityReferenceImpl.java
Index: EntityReferenceImpl.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/EntityReferenceImpl.java,v
retrieving revision 1.9
retrieving revision 1.9.2.1
diff -u -r1.9 -r1.9.2.1
--- EntityReferenceImpl.java 2000/07/07 00:36:13 1.9
+++ EntityReferenceImpl.java 2000/09/15 17:01:41 1.9.2.1
@@ -233,7 +233,7 @@
* This doesn't really support editing the Entity though.
*/
protected void synchronize() {
- if (firstChild != null) {
+ if (length != 0) {
return;
}
DocumentType doctype;
1.33.2.1 +7 -0 xml-xerces/java/src/org/apache/xerces/dom/NodeImpl.java
Index: NodeImpl.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/NodeImpl.java,v
retrieving revision 1.33
retrieving revision 1.33.2.1
diff -u -r1.33 -r1.33.2.1
--- NodeImpl.java 2000/09/14 22:08:03 1.33
+++ NodeImpl.java 2000/09/15 17:01:41 1.33.2.1
@@ -338,6 +338,13 @@
return null; // default behavior, overriden in ChildNode
}
+ // overriden in subclasses ParentNode and ChildAndParentNode
+ public void reduceWaste () {}
+
+ protected int getIndexOf (Node maybeChild) {
+ return -1; // overridden by ParentNode
+ }
+
/**
* Return the collection of attributes associated with this node,
* or null if none. At this writing, Element is the only type of node
1.14.2.1 +156 -209 xml-xerces/java/src/org/apache/xerces/dom/ParentNode.java
Index: ParentNode.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/ParentNode.java,v
retrieving revision 1.14
retrieving revision 1.14.2.1
diff -u -r1.14 -r1.14.2.1
--- ParentNode.java 2000/08/29 18:48:12 1.14
+++ ParentNode.java 2000/09/15 17:01:41 1.14.2.1
@@ -1,4 +1,4 @@
-/* $Id: ParentNode.java,v 1.14 2000/08/29 18:48:12 lehors Exp $ */
+/* $Id: ParentNode.java,v 1.14.2.1 2000/09/15 17:01:41 lehors Exp $ */
/*
* The Apache Software License, Version 1.1
*
@@ -90,20 +90,9 @@
/** Owner document. */
protected DocumentImpl ownerDocument;
- /** First child. */
- protected ChildNode firstChild = null;
+ protected ChildNode children [];
+ protected int length;
- // transients
-
- /** Cached node list length. */
- protected transient int nodeListLength = -1;
-
- /** Last requested node. */
- protected transient ChildNode nodeListNode;
-
- /** Last requested node index. */
- protected transient int nodeListIndex = -1;
-
//
// Constructors
//
@@ -120,6 +109,53 @@
/** Constructor for serialization. */
public ParentNode() {}
+ /**
+ * Called to minimize space utilization. Affects only
+ * this node; children must be individually trimmed.
+ */
+ public void trimToSize ()
+ {
+ if (length == 0)
+ children = null;
+ else if (children.length != length) {
+ ChildNode temp [] = new ChildNode [length];
+
+ System.arraycopy (children, 0, temp, 0, length);
+ children = temp;
+ }
+ }
+
+ public void reduceWaste ()
+ {
+ if (children == null)
+ return;
+
+ //
+ // Arbitrary -- rather than paying trimToSize() costs
+ // on most elements, we routinely accept some waste but
+ // do try to reduce egregious waste. Interacts with
+ // the array allocation done in appendChild.
+ //
+ if ((children.length - length) > 6)
+ trimToSize ();
+ }
+
+ /**
+ * Returns the index of the node in the list of children, such
+ * that <em>item()</em> will return that child.
+ *
+ * @param maybeChild the node which may be a child of this one
+ * @return the index of the node in the set of children, or
+ * else -1 if that node is not a child
+ */
+ final protected int getIndexOf(Node maybeChild)
+ {
+ for (int i = 0; i < length; i++)
+ if (children[i] == maybeChild)
+ return i;
+ return -1;
+ }
+
//
// NodeList methods
//
@@ -155,18 +191,13 @@
}
// Need to break the association w/ original kids
- newnode.firstChild = null;
-
- // invalidate cache for children NodeList
- newnode.nodeListIndex = -1;
- newnode.nodeListLength = -1;
+ newnode.children = null;
+ newnode.length = 0;
// Then, if deep, clone the kids too.
if (deep) {
- for (Node child = firstChild;
- child != null;
- child = child.getNextSibling()) {
- newnode.appendChild(child.cloneNode(true));
+ for (int i = 0; i < length; i++) {
+ newnode.appendChild(children[i].cloneNode(true));
}
}
@@ -199,9 +230,9 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- for (Node child = firstChild;
- child != null; child = child.getNextSibling()) {
- ((NodeImpl) child).setOwnerDocument(doc);
+ ownerDocument = doc;
+ for (int i = 0; i < length; i++) {
+ children[i].setOwnerDocument(doc);
}
ownerDocument = doc;
}
@@ -214,7 +245,7 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- return firstChild != null;
+ return length > 0;
}
/**
@@ -246,7 +277,9 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- return firstChild;
+ if (length == 0)
+ return null;
+ return children[0];
} // getFirstChild():Node
@@ -256,20 +289,16 @@
if (needsSyncChildren()) {
synchronizeChildren();
}
- return lastChild();
+ if (length == 0)
+ return null;
+ return children[length - 1];
} // getLastChild():Node
final ChildNode lastChild() {
- // last child is stored as the previous sibling of first child
- return firstChild != null ? firstChild.previousSibling : null;
- }
-
- final void lastChild(ChildNode node) {
- // store lastChild as previous sibling of first child
- if (firstChild != null) {
- firstChild.previousSibling = node;
- }
+ if (length == 0)
+ return null;
+ return children[length - 1];
}
/**
@@ -367,11 +396,9 @@
// No need to check kids for right-document; if they weren't,
// they wouldn't be kids of that DocFrag.
- for (Node kid = newChild.getFirstChild(); // Prescan
- kid != null;
- kid = kid.getNextSibling()) {
-
- if (errorChecking && !ownerDocument.isKidOK(this, kid)) {
+ for (int i = 0; i < length; i++) { // Prescan
+ if (errorChecking &&
+ !ownerDocument.isKidOK(this, children[i])) {
throw new DOMExceptionImpl(
DOMException.HIERARCHY_REQUEST_ERR,
"DOM006 Hierarchy request error");
@@ -413,66 +440,53 @@
oldparent.removeChild(newInternal);
}
- // Convert to internal type, to avoid repeated casting
- ChildNode refInternal = (ChildNode)refChild;
+ if (refChild == null) { // append
- // Attach up
- newInternal.ownerNode = this;
- newInternal.isOwned(true);
-
- // Attach before and after
- // Note: firstChild.previousSibling == lastChild!!
- if (firstChild == null) {
- // this our first and only child
- firstChild = newInternal;
- newInternal.isFirstChild(true);
- newInternal.previousSibling = newInternal;
- } else {
- if (refInternal == null) {
- // this is an append
- ChildNode lastChild = firstChild.previousSibling;
- lastChild.nextSibling = newInternal;
- newInternal.previousSibling = lastChild;
- firstChild.previousSibling = newInternal;
- } else {
- // this is an insert
- if (refChild == firstChild) {
- // at the head of the list
- firstChild.isFirstChild(false);
- newInternal.nextSibling = firstChild;
- newInternal.previousSibling =
- firstChild.previousSibling;
- firstChild.previousSibling = newInternal;
- firstChild = newInternal;
- newInternal.isFirstChild(true);
- } else {
- // somewhere in the middle
- ChildNode prev = refInternal.previousSibling;
- newInternal.nextSibling = refInternal;
- prev.nextSibling = newInternal;
- refInternal.previousSibling = newInternal;
- newInternal.previousSibling = prev;
- }
+ // this is the only place this vector needs allocating,
+ // though it may also need to be grown in insertBefore.
+ // most elements have very few children
+ if (children == null)
+ children = new ChildNode [3];
+ else if (children.length == length) {
+ ChildNode temp [] = new ChildNode [length * 2];
+ System.arraycopy(children, 0, temp, 0, length);
+ children = temp;
}
- }
- changed();
+ // set parent
+ newInternal.ownerNode = this;
+ newInternal.isOwned(true);
+ newInternal.parentIndex = length;
+
+ children [length++] = newInternal;
+
+ } else {
- // update cached length if we have any
- if (nodeListLength != -1) {
- nodeListLength++;
- }
- if (nodeListIndex != -1) {
- // if we happen to insert just before the cached node, update
- // the cache to the new node to match the cached index
- if (nodeListNode == refInternal) {
- nodeListNode = newInternal;
- } else {
- // otherwise just invalidate the cache
- nodeListIndex = -1;
+ // grow array if needed
+ if (children.length == length) {
+ ChildNode temp [] = new ChildNode [length * 2];
+ System.arraycopy(children, 0, temp, 0, length);
+ children = temp;
}
+
+ for (int i = 0; i < length; i++) {
+ if (children [i] != refChild)
+ continue;
+
+ // set parent
+ newInternal.ownerNode = this;
+ newInternal.isOwned(true);
+ newInternal.parentIndex = i;
+
+ System.arraycopy(children, i, children, i + 1, length - i);
+ children [i] = newInternal;
+ length++;
+ break;
+ }
}
+ changed();
+
if(MUTATIONEVENTS && ownerDocument.mutationEvents)
{
// MUTATION POST-EVENTS:
@@ -642,50 +656,24 @@
}
} // End mutation preprocessing
- // update cached length if we have any
- if (nodeListLength != -1) {
- nodeListLength--;
- }
- if (nodeListIndex != -1) {
- // if the removed node is the cached node
- // move the cache to its (soon former) previous sibling
- if (nodeListNode == oldInternal) {
- nodeListIndex--;
- nodeListNode = oldInternal.previousSibling();
- } else {
- // otherwise just invalidate the cache
- nodeListIndex = -1;
+ // Patch tree past oldChild
+ for (int i = 0; i < length; i++) {
+ if (children [i] != oldInternal)
+ continue;
+ if ((i + 1) != length) {
+ System.arraycopy (children, i + 1, children, i,
+ (length - 1) - i);
}
- }
+ length--;
+ children[length] = null;
- // Patch linked list around oldChild
- // Note: lastChild == firstChild.previousSibling
- if (oldInternal == firstChild) {
- // removing first child
- oldInternal.isFirstChild(false);
- firstChild = oldInternal.nextSibling;
- if (firstChild != null) {
- firstChild.isFirstChild(true);
- firstChild.previousSibling = oldInternal.previousSibling;
- }
- } else {
- ChildNode prev = oldInternal.previousSibling;
- ChildNode next = oldInternal.nextSibling;
- prev.nextSibling = next;
- if (next == null) {
- // removing last child
- firstChild.previousSibling = prev;
- } else {
- // removing some other child in the middle
- next.previousSibling = prev;
- }
- }
+ break;
+ }
// Remove oldInternal's references to tree
oldInternal.ownerNode = ownerDocument;
oldInternal.isOwned(false);
- oldInternal.nextSibling = null;
- oldInternal.previousSibling = null;
+ oldInternal.parentIndex = -1;
changed();
@@ -765,24 +753,7 @@
* @return int
*/
public int getLength() {
-
- if (nodeListLength == -1) { // is the cached length invalid ?
- ChildNode node;
- // start from the cached node if we have one
- if (nodeListIndex != -1 && nodeListNode != null) {
- nodeListLength = nodeListIndex;
- node = nodeListNode;
- } else {
- node = firstChild;
- nodeListLength = 0;
- }
- for (; node != null; node = node.nextSibling) {
- nodeListLength++;
- }
- }
-
- return nodeListLength;
-
+ return length;
} // getLength():int
/**
@@ -792,32 +763,13 @@
* @param Index int
*/
public Node item(int index) {
- // short way
- if (nodeListIndex != -1 && nodeListNode != null) {
- if (nodeListIndex < index) {
- while (nodeListIndex < index && nodeListNode != null) {
- nodeListIndex++;
- nodeListNode = nodeListNode.nextSibling;
- }
- }
- else if (nodeListIndex > index) {
- while (nodeListIndex > index && nodeListNode != null) {
- nodeListIndex--;
- nodeListNode = nodeListNode.previousSibling();
- }
- }
- return nodeListNode;
- }
-
- // long way
- nodeListNode = firstChild;
- for (nodeListIndex = 0;
- nodeListIndex < index && nodeListNode != null;
- nodeListIndex++) {
- nodeListNode = nodeListNode.nextSibling;
- }
- return nodeListNode;
-
+ if (length == 0 || index >= length)
+ return null;
+ try {
+ return children[index];
+ } catch (ArrayIndexOutOfBoundsException e) {
+ return null;
+ }
} // item(int):Node
//
@@ -832,8 +784,8 @@
public void normalize() {
Node kid;
- for (kid = firstChild; kid != null; kid = kid.getNextSibling()) {
- kid.normalize();
+ for (int i = 0; i < length; i++) {
+ children[i].normalize();
}
}
@@ -860,11 +812,9 @@
}
// Recursively set kids
- for (ChildNode mykid = firstChild;
- mykid != null;
- mykid = mykid.nextSibling) {
- if(!(mykid instanceof EntityReference)) {
- mykid.setReadOnly(readOnly,true);
+ for (int i = 0; i < length; i++) {
+ if(!(children[i] instanceof EntityReference)) {
+ children[i].setReadOnly(readOnly,true);
}
}
}
@@ -903,28 +853,29 @@
// create children and link them as siblings
DeferredDocumentImpl ownerDocument =
(DeferredDocumentImpl)this.ownerDocument;
- ChildNode first = null;
- ChildNode last = null;
- for (int index = ownerDocument.getLastChild(nodeIndex);
+
+ // first count them
+ for (int index = ownerDocument.getLastChild(nodeIndex, false);
index != -1;
- index = ownerDocument.getPrevSibling(index)) {
+ index = ownerDocument.getPrevSibling(index, false)) {
+ length++;
+ }
- ChildNode node = (ChildNode)ownerDocument.getNodeObject(index);
- if (last == null) {
- last = node;
- }
- else {
- first.previousSibling = node;
- }
- node.ownerNode = this;
- node.isOwned(true);
- node.nextSibling = first;
- first = node;
- }
- if (last != null) {
- firstChild = first;
- first.isFirstChild(true);
- lastChild(last);
+ // then fluff them up
+ if (length > 0) {
+ children = new ChildNode [length];
+
+ int count = length;
+ for (int index = ownerDocument.getLastChild(nodeIndex);
+ index != -1;
+ index = ownerDocument.getPrevSibling(index)) {
+
+ ChildNode node = (ChildNode)ownerDocument.getNodeObject(index);
+ node.ownerNode = this;
+ node.isOwned(true);
+ node.parentIndex = --count;
+ children[count] = node;
+ }
}
// set mutation events flag back to its original value
@@ -959,10 +910,6 @@
// to try to synchildren when we just desealize object.
needsSyncChildren(false);
-
- // initialize transients
- nodeListLength = -1;
- nodeListIndex = -1;
} // readObject(ObjectInputStream)
1.7.2.1 +1 -1 xml-xerces/java/src/org/apache/xerces/dom/TextImpl.java
Index: TextImpl.java
===================================================================
RCS file: /home/cvs/xml-xerces/java/src/org/apache/xerces/dom/TextImpl.java,v
retrieving revision 1.7
retrieving revision 1.7.2.1
diff -u -r1.7 -r1.7.2.1
--- TextImpl.java 2000/07/07 00:36:15 1.7
+++ TextImpl.java 2000/09/15 17:01:42 1.7.2.1
@@ -182,7 +182,7 @@
// insert new text node
Node parentNode = getParentNode();
if (parentNode != null) {
- parentNode.insertBefore(newText, nextSibling);
+ parentNode.insertBefore(newText, getNextSibling());
}
return newText;