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.
git-svn-id: https://svn.apache.org/repos/asf/xerces/java/branches/arraybased-dom@316103 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/src/org/apache/xerces/dom/AttrImpl.java b/src/org/apache/xerces/dom/AttrImpl.java
index 1db5f1e..15bbbf9 100644
--- a/src/org/apache/xerces/dom/AttrImpl.java
+++ b/src/org/apache/xerces/dom/AttrImpl.java
@@ -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();
+ if (length == 1) {
+ return children[0].getNodeValue();
}
- StringBuffer value = new StringBuffer(firstChild.getNodeValue());
- while (node != null) {
- value.append(node.getNodeValue());
- node = node.nextSibling;
+ 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()
diff --git a/src/org/apache/xerces/dom/ChildAndParentNode.java b/src/org/apache/xerces/dom/ChildAndParentNode.java
index e5fd5c4..306a2ae 100644
--- a/src/org/apache/xerces/dom/ChildAndParentNode.java
+++ b/src/org/apache/xerces/dom/ChildAndParentNode.java
@@ -80,19 +80,8 @@
/** Owner document. */
protected DocumentImpl ownerDocument;
- /** First child. */
- protected ChildNode firstChild = null;
-
- // 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;
+ protected ChildNode children [];
+ protected int length;
//
// 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);
+ // 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;
+ }
- // 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;
+ // set parent
+ newInternal.ownerNode = this;
+ newInternal.isOwned(true);
+ newInternal.parentIndex = length;
+
+ children [length++] = 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;
- }
+
+ // 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();
- // 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;
- }
- }
-
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);
- index != -1;
- index = ownerDocument.getPrevSibling(index)) {
- 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;
+ // first count them
+ for (int index = ownerDocument.getLastChild(nodeIndex, false);
+ index != -1;
+ index = ownerDocument.getPrevSibling(index, false)) {
+ length++;
}
- 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
@@ -950,10 +901,6 @@
needsSyncChildren(false);
- // initialize transients
- nodeListLength = -1;
- nodeListIndex = -1;
-
} // readObject(ObjectInputStream)
} // class ChildAndParentNode
diff --git a/src/org/apache/xerces/dom/ChildNode.java b/src/org/apache/xerces/dom/ChildNode.java
index 6378d2f..f1857fe 100644
--- a/src/org/apache/xerces/dom/ChildNode.java
+++ b/src/org/apache/xerces/dom/ChildNode.java
@@ -83,11 +83,7 @@
// Data
//
- /** Previous sibling. */
- protected ChildNode previousSibling;
-
- /** Next sibling. */
- protected ChildNode nextSibling;
+ int parentIndex = -1; // cache
//
// 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
diff --git a/src/org/apache/xerces/dom/DeferredDocumentImpl.java b/src/org/apache/xerces/dom/DeferredDocumentImpl.java
index 4a6f950..b617191 100644
--- a/src/org/apache/xerces/dom/DeferredDocumentImpl.java
+++ b/src/org/apache/xerces/dom/DeferredDocumentImpl.java
@@ -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();
@@ -1414,12 +1416,6 @@
}
}
- if (first != null) {
- firstChild = first;
- first.isFirstChild(true);
- lastChild(last);
- }
-
// set mutation events flag back to its original value
mutationEvents = orig;
diff --git a/src/org/apache/xerces/dom/DocumentImpl.java b/src/org/apache/xerces/dom/DocumentImpl.java
index df52762..7a87423 100644
--- a/src/org/apache/xerces/dom/DocumentImpl.java
+++ b/src/org/apache/xerces/dom/DocumentImpl.java
@@ -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));
}
}
diff --git a/src/org/apache/xerces/dom/EntityReferenceImpl.java b/src/org/apache/xerces/dom/EntityReferenceImpl.java
index 2279eae..f4e5597 100644
--- a/src/org/apache/xerces/dom/EntityReferenceImpl.java
+++ b/src/org/apache/xerces/dom/EntityReferenceImpl.java
@@ -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;
diff --git a/src/org/apache/xerces/dom/NodeImpl.java b/src/org/apache/xerces/dom/NodeImpl.java
index 539c7b7..b4c25ff 100644
--- a/src/org/apache/xerces/dom/NodeImpl.java
+++ b/src/org/apache/xerces/dom/NodeImpl.java
@@ -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
diff --git a/src/org/apache/xerces/dom/ParentNode.java b/src/org/apache/xerces/dom/ParentNode.java
index 3feb284..fae4e46 100644
--- a/src/org/apache/xerces/dom/ParentNode.java
+++ b/src/org/apache/xerces/dom/ParentNode.java
@@ -90,19 +90,8 @@
/** Owner document. */
protected DocumentImpl ownerDocument;
- /** First child. */
- protected ChildNode firstChild = null;
-
- // 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;
+ protected ChildNode children [];
+ protected int length;
//
// 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);
+ // 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;
+ }
- // 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;
+ // set parent
+ newInternal.ownerNode = this;
+ newInternal.isOwned(true);
+ newInternal.parentIndex = length;
+
+ children [length++] = 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;
- }
+
+ // 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();
- // 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;
- }
- }
-
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);
- index != -1;
- index = ownerDocument.getPrevSibling(index)) {
- 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;
+ // first count them
+ for (int index = ownerDocument.getLastChild(nodeIndex, false);
+ index != -1;
+ index = ownerDocument.getPrevSibling(index, false)) {
+ length++;
}
- 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
@@ -960,10 +911,6 @@
needsSyncChildren(false);
- // initialize transients
- nodeListLength = -1;
- nodeListIndex = -1;
-
} // readObject(ObjectInputStream)
} // class ParentNode
diff --git a/src/org/apache/xerces/dom/TextImpl.java b/src/org/apache/xerces/dom/TextImpl.java
index 82e803a..be31eaa 100644
--- a/src/org/apache/xerces/dom/TextImpl.java
+++ b/src/org/apache/xerces/dom/TextImpl.java
@@ -182,7 +182,7 @@
// insert new text node
Node parentNode = getParentNode();
if (parentNode != null) {
- parentNode.insertBefore(newText, nextSibling);
+ parentNode.insertBefore(newText, getNextSibling());
}
return newText;
diff --git a/src/org/apache/xerces/parsers/DOMParser.java b/src/org/apache/xerces/parsers/DOMParser.java
index 3be40f6..d4f5c70 100644
--- a/src/org/apache/xerces/parsers/DOMParser.java
+++ b/src/org/apache/xerces/parsers/DOMParser.java
@@ -1142,6 +1142,9 @@
else {
fCurrentElementNode = fCurrentElementNode.getParentNode();
fWithinElement = false;
+ if (fDocumentImpl != null) {
+ ((NodeImpl)fCurrentElementNode).reduceWaste();
+ }
}
} // endElement(QName)
