1 /*
2 * Copyright (c) 2015, 2017, Oracle and/or its affiliates. All rights reserved.
3 * @LastModified: Oct 2017
4 */
5 /*
6 * Licensed to the Apache Software Foundation (ASF) under one or more
7 * contributor license agreements. See the NOTICE file distributed with
8 * this work for additional information regarding copyright ownership.
9 * The ASF licenses this file to You under the Apache License, Version 2.0
10 * (the "License"); you may not use this file except in compliance with
11 * the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 */
21
22 package com.sun.org.apache.xerces.internal.dom;
23
24 import java.util.ArrayList;
25 import java.util.HashMap;
26 import java.util.List;
27 import org.w3c.dom.DOMImplementation;
28 import org.w3c.dom.Element;
29 import org.w3c.dom.Node;
30
31 /**
32 * The Document interface represents the entire HTML or XML document.
33 * Conceptually, it is the root of the document tree, and provides the
34 * primary access to the document's data.
35 * <P>
36 * Since elements, text nodes, comments, processing instructions,
37 * etc. cannot exist outside the context of a Document, the Document
38 * interface also contains the factory methods needed to create these
39 * objects. The Node objects created have a ownerDocument attribute
40 * which associates them with the Document within whose context they
41 * were created.
42 *
43 * @xerces.internal
44 *
45 * @since PR-DOM-Level-1-19980818.
46 */
47 public class DeferredDocumentImpl
48 extends DocumentImpl
49 implements DeferredNode {
50
51 //
52 // Constants
53 //
54
55 /** Serialization version. */
56 static final long serialVersionUID = 5186323580749626857L;
57
58 // debugging
59
60 /** To include code for printing the ref count tables. */
61 private static final boolean DEBUG_PRINT_REF_COUNTS = false;
62
63 /** To include code for printing the internal tables. */
64 private static final boolean DEBUG_PRINT_TABLES = false;
65
66 /** To debug identifiers set to true and recompile. */
67 private static final boolean DEBUG_IDS = false;
68
69 // protected
70
71 /** Chunk shift. */
72 protected static final int CHUNK_SHIFT = 8; // 2^8 = 256
73
74 /** Chunk size. */
75 protected static final int CHUNK_SIZE = (1 << CHUNK_SHIFT);
76
77 /** Chunk mask. */
78 protected static final int CHUNK_MASK = CHUNK_SIZE - 1;
79
80 /** Initial chunk size. */
81 protected static final int INITIAL_CHUNK_COUNT = (1 << (13 - CHUNK_SHIFT)); // 32
82
83 //
84 // Data
85 //
86
87 // lazy-eval information
88 // To maximize memory consumption the actual semantic of these fields vary
89 // depending on the node type.
90
91 /** Node count. */
92 protected transient int fNodeCount = 0;
93
94 /** Node types. */
95 protected transient int fNodeType[][];
96
97 /** Node names. */
98 protected transient Object fNodeName[][];
99
100 /** Node values. */
101 protected transient Object fNodeValue[][];
102
103 /** Node parents. */
104 protected transient int fNodeParent[][];
105
106 /** Node first children. */
107 protected transient int fNodeLastChild[][];
108
109 /** Node prev siblings. */
110 protected transient int fNodePrevSib[][];
111
112 /** Node namespace URI. */
113 protected transient Object fNodeURI[][];
114
115 /** Extra data. */
116 protected transient int fNodeExtra[][];
117
118 /** Identifier count. */
119 protected transient int fIdCount;
120
121 /** Identifier name indexes. */
122 protected transient String fIdName[];
123
124 /** Identifier element indexes. */
125 protected transient int fIdElement[];
126
127 /** DOM2: For namespace support in the deferred case.
128 */
129 // Implementation Note: The deferred element and attribute must know how to
130 // interpret the int representing the qname.
131 protected boolean fNamespacesEnabled = false;
132
133 //
134 // private data
135 //
136 private transient final StringBuilder fBufferStr = new StringBuilder();
137 private transient final List<String> fStrChunks = new ArrayList<>();
138
139 //
140 // Constructors
141 //
142
143 /**
144 * NON-DOM: Actually creating a Document is outside the DOM's spec,
145 * since it has to operate in terms of a particular implementation.
146 */
147 public DeferredDocumentImpl() {
148 this(false);
149 } // <init>()
150
151 /**
152 * NON-DOM: Actually creating a Document is outside the DOM's spec,
153 * since it has to operate in terms of a particular implementation.
154 */
155 public DeferredDocumentImpl(boolean namespacesEnabled) {
156 this(namespacesEnabled, false);
157 } // <init>(boolean)
158
159 /** Experimental constructor. */
160 public DeferredDocumentImpl(boolean namespaces, boolean grammarAccess) {
161 super(grammarAccess);
162
163 needsSyncData(true);
164 needsSyncChildren(true);
165
166 fNamespacesEnabled = namespaces;
167
168 } // <init>(boolean,boolean)
169
170 //
171 // Public methods
172 //
173
174 /**
175 * Retrieve information describing the abilities of this particular
176 * DOM implementation. Intended to support applications that may be
177 * using DOMs retrieved from several different sources, potentially
178 * with different underlying representations.
179 */
180 public DOMImplementation getImplementation() {
181 // Currently implemented as a singleton, since it's hardcoded
182 // information anyway.
183 return DeferredDOMImplementationImpl.getDOMImplementation();
184 }
185
186 /** Returns the cached parser.getNamespaces() value.*/
187 boolean getNamespacesEnabled() {
188 return fNamespacesEnabled;
189 }
190
191 void setNamespacesEnabled(boolean enable) {
192 fNamespacesEnabled = enable;
193 }
194
195 // internal factory methods
196
197 /** Creates a document node in the table. */
198 public int createDeferredDocument() {
199 int nodeIndex = createNode(Node.DOCUMENT_NODE);
200 return nodeIndex;
201 }
202
203 /** Creates a doctype. */
204 public int createDeferredDocumentType(String rootElementName,
205 String publicId, String systemId) {
206
207 // create node
208 int nodeIndex = createNode(Node.DOCUMENT_TYPE_NODE);
209 int chunk = nodeIndex >> CHUNK_SHIFT;
210 int index = nodeIndex & CHUNK_MASK;
211
212 // save name, public id, system id
213 setChunkValue(fNodeName, rootElementName, chunk, index);
214 setChunkValue(fNodeValue, publicId, chunk, index);
215 setChunkValue(fNodeURI, systemId, chunk, index);
216
217 // return node index
218 return nodeIndex;
219
220 } // createDeferredDocumentType(String,String,String):int
221
222 public void setInternalSubset(int doctypeIndex, String subset) {
223 int chunk = doctypeIndex >> CHUNK_SHIFT;
224 int index = doctypeIndex & CHUNK_MASK;
225
226 // create extra data node to store internal subset
227 int extraDataIndex = createNode(Node.DOCUMENT_TYPE_NODE);
228 int echunk = extraDataIndex >> CHUNK_SHIFT;
229 int eindex = extraDataIndex & CHUNK_MASK;
230 setChunkIndex(fNodeExtra, extraDataIndex, chunk, index);
231 setChunkValue(fNodeValue, subset, echunk, eindex);
232 }
233
234 /** Creates a notation in the table. */
235 public int createDeferredNotation(String notationName,
236 String publicId, String systemId, String baseURI) {
237
238 // create node
239 int nodeIndex = createNode(Node.NOTATION_NODE);
240 int chunk = nodeIndex >> CHUNK_SHIFT;
241 int index = nodeIndex & CHUNK_MASK;
242
243
244 // create extra data node
245 int extraDataIndex = createNode(Node.NOTATION_NODE);
246 int echunk = extraDataIndex >> CHUNK_SHIFT;
247 int eindex = extraDataIndex & CHUNK_MASK;
248
249 // save name, public id, system id, and notation name
250 setChunkValue(fNodeName, notationName, chunk, index);
251 setChunkValue(fNodeValue, publicId, chunk, index);
252 setChunkValue(fNodeURI, systemId, chunk, index);
253
254 // in extra data node set baseURI value
255 setChunkIndex(fNodeExtra, extraDataIndex, chunk, index);
256 setChunkValue(fNodeName, baseURI, echunk, eindex);
257
258 // return node index
259 return nodeIndex;
260
261 } // createDeferredNotation(String,String,String):int
262
263 /** Creates an entity in the table. */
264 public int createDeferredEntity(String entityName, String publicId,
265 String systemId, String notationName,
266 String baseURI) {
267 // create node
268 int nodeIndex = createNode(Node.ENTITY_NODE);
269 int chunk = nodeIndex >> CHUNK_SHIFT;
270 int index = nodeIndex & CHUNK_MASK;
271
272 // create extra data node
273 int extraDataIndex = createNode(Node.ENTITY_NODE);
274 int echunk = extraDataIndex >> CHUNK_SHIFT;
275 int eindex = extraDataIndex & CHUNK_MASK;
276
277 // save name, public id, system id, and notation name
278 setChunkValue(fNodeName, entityName, chunk, index);
279 setChunkValue(fNodeValue, publicId, chunk, index);
280 setChunkValue(fNodeURI, systemId, chunk, index);
281 setChunkIndex(fNodeExtra, extraDataIndex, chunk, index);
282 // set other values in the extra chunk
283 // notation
284 setChunkValue(fNodeName, notationName, echunk, eindex);
285 // version L3
286 setChunkValue(fNodeValue, null, echunk, eindex);
287 // encoding L3
288 setChunkValue(fNodeURI, null, echunk, eindex);
289
290
291 int extraDataIndex2 = createNode(Node.ENTITY_NODE);
292 int echunk2 = extraDataIndex2 >> CHUNK_SHIFT;
293 int eindex2 = extraDataIndex2 & CHUNK_MASK;
294
295 setChunkIndex(fNodeExtra, extraDataIndex2, echunk, eindex);
296
297 // baseURI
298 setChunkValue(fNodeName, baseURI, echunk2, eindex2);
299
300 // return node index
301 return nodeIndex;
302
303 } // createDeferredEntity(String,String,String,String):int
304
305 public String getDeferredEntityBaseURI (int entityIndex){
306 if (entityIndex != -1) {
307 int extraDataIndex = getNodeExtra(entityIndex, false);
308 extraDataIndex = getNodeExtra(extraDataIndex, false);
309 return getNodeName (extraDataIndex, false);
310 }
311 return null;
312 }
313
314 // DOM Level 3: setting encoding and version
315 public void setEntityInfo(int currentEntityDecl,
316 String version, String encoding){
317 int eNodeIndex = getNodeExtra(currentEntityDecl, false);
318 if (eNodeIndex !=-1) {
319 int echunk = eNodeIndex >> CHUNK_SHIFT;
320 int eindex = eNodeIndex & CHUNK_MASK;
321 setChunkValue(fNodeValue, version, echunk, eindex);
322 setChunkValue(fNodeURI, encoding, echunk, eindex);
323 }
324 }
325
326 // DOM Level 3: sets element TypeInfo
327 public void setTypeInfo(int elementNodeIndex, Object type) {
328 int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
329 int elementIndex = elementNodeIndex & CHUNK_MASK;
330 setChunkValue(fNodeValue, type, elementChunk, elementIndex);
331 }
332
333 /**
334 * DOM Internal
335 *
336 * An attribute specifying the actual encoding of this document. This is
337 * <code>null</code> otherwise.
338 * <br> This attribute represents the property [character encoding scheme]
339 * defined in .
340 */
341 public void setInputEncoding(int currentEntityDecl, String value){
342 // get first extra data chunk
343 int nodeIndex = getNodeExtra(currentEntityDecl, false);
344 // get second extra data chunk
345 int extraDataIndex = getNodeExtra(nodeIndex, false);
346
347 int echunk = extraDataIndex >> CHUNK_SHIFT;
348 int eindex = extraDataIndex & CHUNK_MASK;
349
350 setChunkValue(fNodeValue, value, echunk, eindex);
351
352 }
353
354 /** Creates an entity reference node in the table. */
355 public int createDeferredEntityReference(String name, String baseURI) {
356
357 // create node
358 int nodeIndex = createNode(Node.ENTITY_REFERENCE_NODE);
359 int chunk = nodeIndex >> CHUNK_SHIFT;
360 int index = nodeIndex & CHUNK_MASK;
361 setChunkValue(fNodeName, name, chunk, index);
362 setChunkValue(fNodeValue, baseURI, chunk, index);
363
364 // return node index
365 return nodeIndex;
366
367 } // createDeferredEntityReference(String):int
368
369
370 /**
371 * Creates an element node with a URI in the table and type information.
372 * @deprecated
373 */
374 @Deprecated
375 public int createDeferredElement(String elementURI, String elementName,
376 Object type) {
377
378 // create node
379 int elementNodeIndex = createNode(Node.ELEMENT_NODE);
380 int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
381 int elementIndex = elementNodeIndex & CHUNK_MASK;
382 setChunkValue(fNodeName, elementName, elementChunk, elementIndex);
383 setChunkValue(fNodeURI, elementURI, elementChunk, elementIndex);
384 setChunkValue(fNodeValue, type, elementChunk, elementIndex);
385
386 // return node index
387 return elementNodeIndex;
388
389 } // createDeferredElement(String,String,Object):int
390
391 /**
392 * Creates an element node in the table.
393 * @deprecated
394 */
395 @Deprecated
396 public int createDeferredElement(String elementName) {
397 return createDeferredElement(null, elementName);
398 }
399
400 /**
401 * Creates an element node with a URI in the table.
402 */
403 public int createDeferredElement(String elementURI, String elementName) {
404
405 // create node
406 int elementNodeIndex = createNode(Node.ELEMENT_NODE);
407 int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
408 int elementIndex = elementNodeIndex & CHUNK_MASK;
409 setChunkValue(fNodeName, elementName, elementChunk, elementIndex);
410 setChunkValue(fNodeURI, elementURI, elementChunk, elementIndex);
411
412 // return node index
413 return elementNodeIndex;
414
415 } // createDeferredElement(String,String):int
416
417
418 /**
419 * This method is used by the DOMParser to create attributes.
420 * @param elementNodeIndex
421 * @param attrName
422 * @param attrURI
423 * @param attrValue
424 * @param specified
425 * @param id
426 * @param type
427 * @return int
428 */
429 public int setDeferredAttribute(int elementNodeIndex,
430 String attrName,
431 String attrURI,
432 String attrValue,
433 boolean specified,
434 boolean id,
435 Object type) {
436
437 // create attribute
438 int attrNodeIndex = createDeferredAttribute(attrName, attrURI, attrValue, specified);
439 int attrChunk = attrNodeIndex >> CHUNK_SHIFT;
440 int attrIndex = attrNodeIndex & CHUNK_MASK;
441 // set attribute's parent to element
442 setChunkIndex(fNodeParent, elementNodeIndex, attrChunk, attrIndex);
443
444 int elementChunk = elementNodeIndex >> CHUNK_SHIFT;
445 int elementIndex = elementNodeIndex & CHUNK_MASK;
446
447 // get element's last attribute
448 int lastAttrNodeIndex = getChunkIndex(fNodeExtra, elementChunk, elementIndex);
449 if (lastAttrNodeIndex != 0) {
450 // add link from new attribute to last attribute
451 setChunkIndex(fNodePrevSib, lastAttrNodeIndex, attrChunk, attrIndex);
452 }
453 // add link from element to new last attribute
454 setChunkIndex(fNodeExtra, attrNodeIndex, elementChunk, elementIndex);
455
456 int extra = getChunkIndex(fNodeExtra, attrChunk, attrIndex);
457 if (id) {
458 extra = extra | ID;
459 setChunkIndex(fNodeExtra, extra, attrChunk, attrIndex);
460 String value = getChunkValue(fNodeValue, attrChunk, attrIndex);
461 putIdentifier(value, elementNodeIndex);
462 }
463 // store type information
464 if (type != null) {
465 int extraDataIndex = createNode(DeferredNode.TYPE_NODE);
466 int echunk = extraDataIndex >> CHUNK_SHIFT;
467 int eindex = extraDataIndex & CHUNK_MASK;
468
469 setChunkIndex(fNodeLastChild, extraDataIndex, attrChunk, attrIndex);
470 setChunkValue(fNodeValue, type, echunk, eindex);
471 }
472
473 // return node index
474 return attrNodeIndex;
475 }
476
477 /** Creates an attribute in the table. */
478 public int createDeferredAttribute(String attrName, String attrValue,
479 boolean specified) {
480 return createDeferredAttribute(attrName, null, attrValue, specified);
481 }
482
483 /** Creates an attribute with a URI in the table. */
484 public int createDeferredAttribute(String attrName, String attrURI,
485 String attrValue, boolean specified) {
486
487 // create node
488 int nodeIndex = createNode(NodeImpl.ATTRIBUTE_NODE);
489 int chunk = nodeIndex >> CHUNK_SHIFT;
490 int index = nodeIndex & CHUNK_MASK;
491 setChunkValue(fNodeName, attrName, chunk, index);
492 setChunkValue(fNodeURI, attrURI, chunk, index);
493 setChunkValue(fNodeValue, attrValue, chunk, index);
494 int extra = specified ? SPECIFIED : 0;
495 setChunkIndex(fNodeExtra, extra, chunk, index);
496
497 // return node index
498 return nodeIndex;
499
500 } // createDeferredAttribute(String,String,String,boolean):int
501
502 /** Creates an element definition in the table.*/
503 public int createDeferredElementDefinition(String elementName) {
504
505 // create node
506 int nodeIndex = createNode(NodeImpl.ELEMENT_DEFINITION_NODE);
507 int chunk = nodeIndex >> CHUNK_SHIFT;
508 int index = nodeIndex & CHUNK_MASK;
509 setChunkValue(fNodeName, elementName, chunk, index);
510
511 // return node index
512 return nodeIndex;
513
514 } // createDeferredElementDefinition(String):int
515
516 /** Creates a text node in the table. */
517 public int createDeferredTextNode(String data,
518 boolean ignorableWhitespace) {
519
520 // create node
521 int nodeIndex = createNode(Node.TEXT_NODE);
522 int chunk = nodeIndex >> CHUNK_SHIFT;
523 int index = nodeIndex & CHUNK_MASK;
524 setChunkValue(fNodeValue, data, chunk, index);
525 // use extra to store ignorableWhitespace info
526 setChunkIndex(fNodeExtra, ignorableWhitespace ? 1 : 0, chunk, index);
527
528 // return node index
529 return nodeIndex;
530
531 } // createDeferredTextNode(String,boolean):int
532
533 /** Creates a CDATA section node in the table. */
534 public int createDeferredCDATASection(String data) {
535
536 // create node
537 int nodeIndex = createNode(Node.CDATA_SECTION_NODE);
538 int chunk = nodeIndex >> CHUNK_SHIFT;
539 int index = nodeIndex & CHUNK_MASK;
540 setChunkValue(fNodeValue, data, chunk, index);
541
542 // return node index
543 return nodeIndex;
544
545 } // createDeferredCDATASection(String):int
546
547 /** Creates a processing instruction node in the table. */
548 public int createDeferredProcessingInstruction(String target,
549 String data) {
550 // create node
551 int nodeIndex = createNode(Node.PROCESSING_INSTRUCTION_NODE);
552 int chunk = nodeIndex >> CHUNK_SHIFT;
553 int index = nodeIndex & CHUNK_MASK;
554 setChunkValue(fNodeName, target, chunk, index);
555 setChunkValue(fNodeValue, data, chunk, index);
556 // return node index
557 return nodeIndex;
558
559 } // createDeferredProcessingInstruction(String,String):int
560
561 /** Creates a comment node in the table. */
562 public int createDeferredComment(String data) {
563
564 // create node
565 int nodeIndex = createNode(Node.COMMENT_NODE);
566 int chunk = nodeIndex >> CHUNK_SHIFT;
567 int index = nodeIndex & CHUNK_MASK;
568 setChunkValue(fNodeValue, data, chunk, index);
569
570 // return node index
571 return nodeIndex;
572
573 } // createDeferredComment(String):int
574
575 /** Creates a clone of the specified node. */
576 public int cloneNode(int nodeIndex, boolean deep) {
577
578 // clone immediate node
579
580 int nchunk = nodeIndex >> CHUNK_SHIFT;
581 int nindex = nodeIndex & CHUNK_MASK;
582 int nodeType = fNodeType[nchunk][nindex];
583 int cloneIndex = createNode((short)nodeType);
584 int cchunk = cloneIndex >> CHUNK_SHIFT;
585 int cindex = cloneIndex & CHUNK_MASK;
586 setChunkValue(fNodeName, fNodeName[nchunk][nindex], cchunk, cindex);
587 setChunkValue(fNodeValue, fNodeValue[nchunk][nindex], cchunk, cindex);
588 setChunkValue(fNodeURI, fNodeURI[nchunk][nindex], cchunk, cindex);
589 int extraIndex = fNodeExtra[nchunk][nindex];
590 if (extraIndex != -1) {
591 if (nodeType != Node.ATTRIBUTE_NODE && nodeType != Node.TEXT_NODE) {
592 extraIndex = cloneNode(extraIndex, false);
593 }
594 setChunkIndex(fNodeExtra, extraIndex, cchunk, cindex);
595 }
596
597 // clone and attach children
598 if (deep) {
599 int prevIndex = -1;
600 int childIndex = getLastChild(nodeIndex, false);
601 while (childIndex != -1) {
602 int clonedChildIndex = cloneNode(childIndex, deep);
603 insertBefore(cloneIndex, clonedChildIndex, prevIndex);
604 prevIndex = clonedChildIndex;
605 childIndex = getRealPrevSibling(childIndex, false);
606 }
607
608
609 }
610
611 // return cloned node index
612 return cloneIndex;
613
614 } // cloneNode(int,boolean):int
615
616 /** Appends a child to the specified parent in the table. */
617 public void appendChild(int parentIndex, int childIndex) {
618
619 // append parent index
620 int pchunk = parentIndex >> CHUNK_SHIFT;
621 int pindex = parentIndex & CHUNK_MASK;
622 int cchunk = childIndex >> CHUNK_SHIFT;
623 int cindex = childIndex & CHUNK_MASK;
624 setChunkIndex(fNodeParent, parentIndex, cchunk, cindex);
625
626 // set previous sibling of new child
627 int olast = getChunkIndex(fNodeLastChild, pchunk, pindex);
628 setChunkIndex(fNodePrevSib, olast, cchunk, cindex);
629
630 // update parent's last child
631 setChunkIndex(fNodeLastChild, childIndex, pchunk, pindex);
632
633 } // appendChild(int,int)
634
635 /** Adds an attribute node to the specified element. */
636 public int setAttributeNode(int elemIndex, int attrIndex) {
637
638 int echunk = elemIndex >> CHUNK_SHIFT;
639 int eindex = elemIndex & CHUNK_MASK;
640 int achunk = attrIndex >> CHUNK_SHIFT;
641 int aindex = attrIndex & CHUNK_MASK;
642
643 // see if this attribute is already here
644 String attrName = getChunkValue(fNodeName, achunk, aindex);
645 int oldAttrIndex = getChunkIndex(fNodeExtra, echunk, eindex);
646 int nextIndex = -1;
647 int oachunk = -1;
648 int oaindex = -1;
649 while (oldAttrIndex != -1) {
650 oachunk = oldAttrIndex >> CHUNK_SHIFT;
651 oaindex = oldAttrIndex & CHUNK_MASK;
652 String oldAttrName = getChunkValue(fNodeName, oachunk, oaindex);
653 if (oldAttrName.equals(attrName)) {
654 break;
655 }
656 nextIndex = oldAttrIndex;
657 oldAttrIndex = getChunkIndex(fNodePrevSib, oachunk, oaindex);
658 }
659
660 // remove old attribute
661 if (oldAttrIndex != -1) {
662
663 // patch links
664 int prevIndex = getChunkIndex(fNodePrevSib, oachunk, oaindex);
665 if (nextIndex == -1) {
666 setChunkIndex(fNodeExtra, prevIndex, echunk, eindex);
667 }
668 else {
669 int pchunk = nextIndex >> CHUNK_SHIFT;
670 int pindex = nextIndex & CHUNK_MASK;
671 setChunkIndex(fNodePrevSib, prevIndex, pchunk, pindex);
672 }
673
674 // remove connections to siblings
675 clearChunkIndex(fNodeType, oachunk, oaindex);
676 clearChunkValue(fNodeName, oachunk, oaindex);
677 clearChunkValue(fNodeValue, oachunk, oaindex);
678 clearChunkIndex(fNodeParent, oachunk, oaindex);
679 clearChunkIndex(fNodePrevSib, oachunk, oaindex);
680 int attrTextIndex =
681 clearChunkIndex(fNodeLastChild, oachunk, oaindex);
682 int atchunk = attrTextIndex >> CHUNK_SHIFT;
683 int atindex = attrTextIndex & CHUNK_MASK;
684 clearChunkIndex(fNodeType, atchunk, atindex);
685 clearChunkValue(fNodeValue, atchunk, atindex);
686 clearChunkIndex(fNodeParent, atchunk, atindex);
687 clearChunkIndex(fNodeLastChild, atchunk, atindex);
688 }
689
690 // add new attribute
691 int prevIndex = getChunkIndex(fNodeExtra, echunk, eindex);
692 setChunkIndex(fNodeExtra, attrIndex, echunk, eindex);
693 setChunkIndex(fNodePrevSib, prevIndex, achunk, aindex);
694
695 // return
696 return oldAttrIndex;
697
698 } // setAttributeNode(int,int):int
699
700
701 /** Adds an attribute node to the specified element. */
702 public void setIdAttributeNode(int elemIndex, int attrIndex) {
703
704 int chunk = attrIndex >> CHUNK_SHIFT;
705 int index = attrIndex & CHUNK_MASK;
706 int extra = getChunkIndex(fNodeExtra, chunk, index);
707 extra = extra | ID;
708 setChunkIndex(fNodeExtra, extra, chunk, index);
709
710 String value = getChunkValue(fNodeValue, chunk, index);
711 putIdentifier(value, elemIndex);
712 }
713
714
715 /** Sets type of attribute */
716 public void setIdAttribute(int attrIndex) {
717
718 int chunk = attrIndex >> CHUNK_SHIFT;
719 int index = attrIndex & CHUNK_MASK;
720 int extra = getChunkIndex(fNodeExtra, chunk, index);
721 extra = extra | ID;
722 setChunkIndex(fNodeExtra, extra, chunk, index);
723 }
724
725 /** Inserts a child before the specified node in the table. */
726 public int insertBefore(int parentIndex, int newChildIndex, int refChildIndex) {
727
728 if (refChildIndex == -1) {
729 appendChild(parentIndex, newChildIndex);
730 return newChildIndex;
731 }
732
733 int nchunk = newChildIndex >> CHUNK_SHIFT;
734 int nindex = newChildIndex & CHUNK_MASK;
735 int rchunk = refChildIndex >> CHUNK_SHIFT;
736 int rindex = refChildIndex & CHUNK_MASK;
737 int previousIndex = getChunkIndex(fNodePrevSib, rchunk, rindex);
738 setChunkIndex(fNodePrevSib, newChildIndex, rchunk, rindex);
739 setChunkIndex(fNodePrevSib, previousIndex, nchunk, nindex);
740
741 return newChildIndex;
742
743 } // insertBefore(int,int,int):int
744
745 /** Sets the last child of the parentIndex to childIndex. */
746 public void setAsLastChild(int parentIndex, int childIndex) {
747 int pchunk = parentIndex >> CHUNK_SHIFT;
748 int pindex = parentIndex & CHUNK_MASK;
749 setChunkIndex(fNodeLastChild, childIndex, pchunk, pindex);
750 } // setAsLastChild(int,int)
751
752 /**
753 * Returns the parent node of the given node.
754 * <em>Calling this method does not free the parent index.</em>
755 */
756 public int getParentNode(int nodeIndex) {
757 return getParentNode(nodeIndex, false);
758 }
759
760 /**
761 * Returns the parent node of the given node.
762 * @param free True to free parent node.
763 */
764 public int getParentNode(int nodeIndex, boolean free) {
765
766 if (nodeIndex == -1) {
767 return -1;
768 }
769
770 int chunk = nodeIndex >> CHUNK_SHIFT;
771 int index = nodeIndex & CHUNK_MASK;
772 return free ? clearChunkIndex(fNodeParent, chunk, index)
773 : getChunkIndex(fNodeParent, chunk, index);
774
775 } // getParentNode(int):int
776
777 /** Returns the last child of the given node. */
778 public int getLastChild(int nodeIndex) {
779 return getLastChild(nodeIndex, true);
780 }
781
782 /**
783 * Returns the last child of the given node.
784 * @param free True to free child index.
785 */
786 public int getLastChild(int nodeIndex, boolean free) {
787
788 if (nodeIndex == -1) {
789 return -1;
790 }
791
792 int chunk = nodeIndex >> CHUNK_SHIFT;
793 int index = nodeIndex & CHUNK_MASK;
794 return free ? clearChunkIndex(fNodeLastChild, chunk, index)
795 : getChunkIndex(fNodeLastChild, chunk, index);
796
797 } // getLastChild(int,boolean):int
798
799 /**
800 * Returns the prev sibling of the given node.
801 * This is post-normalization of Text Nodes.
802 */
803 public int getPrevSibling(int nodeIndex) {
804 return getPrevSibling(nodeIndex, true);
805 }
806
807 /**
808 * Returns the prev sibling of the given node.
809 * @param free True to free sibling index.
810 */
811 public int getPrevSibling(int nodeIndex, boolean free) {
812
813 if (nodeIndex == -1) {
814 return -1;
815 }
816
817 int chunk = nodeIndex >> CHUNK_SHIFT;
818 int index = nodeIndex & CHUNK_MASK;
819 int type = getChunkIndex(fNodeType, chunk, index);
820 if (type == Node.TEXT_NODE) {
821 do {
822 nodeIndex = getChunkIndex(fNodePrevSib, chunk, index);
823 if (nodeIndex == -1) {
824 break;
825 }
826 chunk = nodeIndex >> CHUNK_SHIFT;
827 index = nodeIndex & CHUNK_MASK;
828 type = getChunkIndex(fNodeType, chunk, index);
829 } while (type == Node.TEXT_NODE);
830 }
831 else {
832 nodeIndex = getChunkIndex(fNodePrevSib, chunk, index);
833 }
834
835 return nodeIndex;
836
837 } // getPrevSibling(int,boolean):int
838
839 /**
840 * Returns the <i>real</i> prev sibling of the given node,
841 * directly from the data structures. Used by TextImpl#getNodeValue()
842 * to normalize values.
843 */
844 public int getRealPrevSibling(int nodeIndex) {
845 return getRealPrevSibling(nodeIndex, true);
846 }
847
848 /**
849 * Returns the <i>real</i> prev sibling of the given node.
850 * @param free True to free sibling index.
851 */
852 public int getRealPrevSibling(int nodeIndex, boolean free) {
853
854 if (nodeIndex == -1) {
855 return -1;
856 }
857
858 int chunk = nodeIndex >> CHUNK_SHIFT;
859 int index = nodeIndex & CHUNK_MASK;
860 return free ? clearChunkIndex(fNodePrevSib, chunk, index)
861 : getChunkIndex(fNodePrevSib, chunk, index);
862
863 } // getReadPrevSibling(int,boolean):int
864
865 /**
866 * Returns the index of the element definition in the table
867 * with the specified name index, or -1 if no such definition
868 * exists.
869 */
870 public int lookupElementDefinition(String elementName) {
871
872 if (fNodeCount > 1) {
873
874 // find doctype
875 int docTypeIndex = -1;
876 int nchunk = 0;
877 int nindex = 0;
878 for (int index = getChunkIndex(fNodeLastChild, nchunk, nindex);
879 index != -1;
880 index = getChunkIndex(fNodePrevSib, nchunk, nindex)) {
881
882 nchunk = index >> CHUNK_SHIFT;
883 nindex = index & CHUNK_MASK;
884 if (getChunkIndex(fNodeType, nchunk, nindex) == Node.DOCUMENT_TYPE_NODE) {
885 docTypeIndex = index;
886 break;
887 }
888 }
889
890 // find element definition
891 if (docTypeIndex == -1) {
892 return -1;
893 }
894 nchunk = docTypeIndex >> CHUNK_SHIFT;
895 nindex = docTypeIndex & CHUNK_MASK;
896 for (int index = getChunkIndex(fNodeLastChild, nchunk, nindex);
897 index != -1;
898 index = getChunkIndex(fNodePrevSib, nchunk, nindex)) {
899
900 nchunk = index >> CHUNK_SHIFT;
901 nindex = index & CHUNK_MASK;
902 if (getChunkIndex(fNodeType, nchunk, nindex) ==
903 NodeImpl.ELEMENT_DEFINITION_NODE
904 && getChunkValue(fNodeName, nchunk, nindex) == elementName) {
905 return index;
906 }
907 }
908 }
909
910 return -1;
911
912 } // lookupElementDefinition(String):int
913
914 /** Instantiates the requested node object. */
915 public DeferredNode getNodeObject(int nodeIndex) {
916
917 // is there anything to do?
918 if (nodeIndex == -1) {
919 return null;
920 }
921
922 // get node type
923 int chunk = nodeIndex >> CHUNK_SHIFT;
924 int index = nodeIndex & CHUNK_MASK;
925 int type = getChunkIndex(fNodeType, chunk, index);
926 if (type != Node.TEXT_NODE && type != Node.CDATA_SECTION_NODE) {
927 clearChunkIndex(fNodeType, chunk, index);
928 }
929
930 // create new node
931 DeferredNode node = null;
932 switch (type) {
933
934 //
935 // Standard DOM node types
936 //
937
938 case Node.ATTRIBUTE_NODE: {
939 if (fNamespacesEnabled) {
940 node = new DeferredAttrNSImpl(this, nodeIndex);
941 } else {
942 node = new DeferredAttrImpl(this, nodeIndex);
943 }
944 break;
945 }
946
947 case Node.CDATA_SECTION_NODE: {
948 node = new DeferredCDATASectionImpl(this, nodeIndex);
949 break;
950 }
951
952 case Node.COMMENT_NODE: {
953 node = new DeferredCommentImpl(this, nodeIndex);
954 break;
955 }
956
957 // NOTE: Document fragments can never be "fast".
958 //
959 // The parser will never ask to create a document
960 // fragment during the parse. Document fragments
961 // are used by the application *after* the parse.
962 //
963 // case Node.DOCUMENT_FRAGMENT_NODE: { break; }
964 case Node.DOCUMENT_NODE: {
965 // this node is never "fast"
966 node = this;
967 break;
968 }
969
970 case Node.DOCUMENT_TYPE_NODE: {
971 node = new DeferredDocumentTypeImpl(this, nodeIndex);
972 // save the doctype node
973 docType = (DocumentTypeImpl)node;
974 break;
975 }
976
977 case Node.ELEMENT_NODE: {
978
979 if (DEBUG_IDS) {
980 System.out.println("getNodeObject(ELEMENT_NODE): "+nodeIndex);
981 }
982
983 // create node
984 if (fNamespacesEnabled) {
985 node = new DeferredElementNSImpl(this, nodeIndex);
986 } else {
987 node = new DeferredElementImpl(this, nodeIndex);
988 }
989
990 // check to see if this element needs to be
991 // registered for its ID attributes
992 if (fIdElement != null) {
993 int idIndex = binarySearch(fIdElement, 0,
994 fIdCount-1, nodeIndex);
995 while (idIndex != -1) {
996
997 if (DEBUG_IDS) {
998 System.out.println(" id index: "+idIndex);
999 System.out.println(" fIdName["+idIndex+
1000 "]: "+fIdName[idIndex]);
1001 }
1002
1003 // register ID
1004 String name = fIdName[idIndex];
1005 if (name != null) {
1006 if (DEBUG_IDS) {
1007 System.out.println(" name: "+name);
1008 System.out.print("getNodeObject()#");
1009 }
1010 putIdentifier0(name, (Element)node);
1011 fIdName[idIndex] = null;
1012 }
1013
1014 // continue if there are more IDs for
1015 // this element
1016 if (idIndex + 1 < fIdCount &&
1017 fIdElement[idIndex + 1] == nodeIndex) {
1018 idIndex++;
1019 }
1020 else {
1021 idIndex = -1;
1022 }
1023 }
1024 }
1025 break;
1026 }
1027
1028 case Node.ENTITY_NODE: {
1029 node = new DeferredEntityImpl(this, nodeIndex);
1030 break;
1031 }
1032
1033 case Node.ENTITY_REFERENCE_NODE: {
1034 node = new DeferredEntityReferenceImpl(this, nodeIndex);
1035 break;
1036 }
1037
1038 case Node.NOTATION_NODE: {
1039 node = new DeferredNotationImpl(this, nodeIndex);
1040 break;
1041 }
1042
1043 case Node.PROCESSING_INSTRUCTION_NODE: {
1044 node = new DeferredProcessingInstructionImpl(this, nodeIndex);
1045 break;
1046 }
1047
1048 case Node.TEXT_NODE: {
1049 node = new DeferredTextImpl(this, nodeIndex);
1050 break;
1051 }
1052
1053 //
1054 // non-standard DOM node types
1055 //
1056
1057 case NodeImpl.ELEMENT_DEFINITION_NODE: {
1058 node = new DeferredElementDefinitionImpl(this, nodeIndex);
1059 break;
1060 }
1061
1062 default: {
1063 throw new IllegalArgumentException("type: "+type);
1064 }
1065
1066 } // switch node type
1067
1068 // store and return
1069 if (node != null) {
1070 return node;
1071 }
1072
1073 // error
1074 throw new IllegalArgumentException();
1075
1076 } // createNodeObject(int):Node
1077
1078 /** Returns the name of the given node. */
1079 public String getNodeName(int nodeIndex) {
1080 return getNodeName(nodeIndex, true);
1081 } // getNodeNameString(int):String
1082
1083 /**
1084 * Returns the name of the given node.
1085 * @param free True to free the string index.
1086 */
1087 public String getNodeName(int nodeIndex, boolean free) {
1088
1089 if (nodeIndex == -1) {
1090 return null;
1091 }
1092
1093 int chunk = nodeIndex >> CHUNK_SHIFT;
1094 int index = nodeIndex & CHUNK_MASK;
1095 return free ? clearChunkValue(fNodeName, chunk, index)
1096 : getChunkValue(fNodeName, chunk, index);
1097
1098 } // getNodeName(int,boolean):String
1099
1100 /** Returns the real value of the given node. */
1101 public String getNodeValueString(int nodeIndex) {
1102 return getNodeValueString(nodeIndex, true);
1103 } // getNodeValueString(int):String
1104
1105 /**
1106 * Returns the real value of the given node.
1107 * @param free True to free the string index.
1108 */
1109 public String getNodeValueString(int nodeIndex, boolean free) {
1110
1111 if (nodeIndex == -1) {
1112 return null;
1113 }
1114
1115 int chunk = nodeIndex >> CHUNK_SHIFT;
1116 int index = nodeIndex & CHUNK_MASK;
1117 String value = free ? clearChunkValue(fNodeValue, chunk, index)
1118 : getChunkValue(fNodeValue, chunk, index);
1119 if (value == null) {
1120 return null;
1121 }
1122
1123 int type = getChunkIndex(fNodeType, chunk, index);
1124 if (type == Node.TEXT_NODE) {
1125 int prevSib = getRealPrevSibling(nodeIndex);
1126 if (prevSib != -1 &&
1127 getNodeType(prevSib, false) == Node.TEXT_NODE) {
1128 // append data that is stored in fNodeValue
1129 // REVISIT: for text nodes it works differently than for CDATA
1130 // nodes.
1131 fStrChunks.add(value);
1132 do {
1133 // go in reverse order: find last child, then
1134 // its previous sibling, etc
1135 chunk = prevSib >> CHUNK_SHIFT;
1136 index = prevSib & CHUNK_MASK;
1137 value = getChunkValue(fNodeValue, chunk, index);
1138 fStrChunks.add(value);
1139 prevSib = getChunkIndex(fNodePrevSib, chunk, index);
1140 if (prevSib == -1) {
1141 break;
1142 }
1143 } while (getNodeType(prevSib, false) == Node.TEXT_NODE);
1144
1145 int chunkCount = fStrChunks.size();
1146
1147 // add to the buffer in the correct order.
1148 for (int i = chunkCount - 1; i >= 0; i--) {
1149 fBufferStr.append(fStrChunks.get(i));
1150 }
1151
1152 value = fBufferStr.toString();
1153 fStrChunks.clear();
1154 fBufferStr.setLength(0);
1155 return value;
1156 }
1157 }
1158 else if (type == Node.CDATA_SECTION_NODE) {
1159 // find if any other data stored in children
1160 int child = getLastChild(nodeIndex, false);
1161 if (child !=-1) {
1162 // append data that is stored in fNodeValue
1163 fBufferStr.append(value);
1164 while (child !=-1) {
1165 // go in reverse order: find last child, then
1166 // its previous sibling, etc
1167 chunk = child >> CHUNK_SHIFT;
1168 index = child & CHUNK_MASK;
1169 value = getChunkValue(fNodeValue, chunk, index);
1170 fStrChunks.add(value);
1171 child = getChunkIndex(fNodePrevSib, chunk, index);
1172 }
1173 // add to the buffer in the correct order.
1174 for (int i=fStrChunks.size()-1; i>=0; i--) {
1175 fBufferStr.append(fStrChunks.get(i));
1176 }
1177
1178 value = fBufferStr.toString();
1179 fStrChunks.clear();
1180 fBufferStr.setLength(0);
1181 return value;
1182 }
1183 }
1184
1185 return value;
1186
1187 } // getNodeValueString(int,boolean):String
1188
1189 /**
1190 * Returns the value of the given node.
1191 */
1192 public String getNodeValue(int nodeIndex) {
1193 return getNodeValue(nodeIndex, true);
1194 }
1195
1196 /**
1197 * Clears the type info that is stored in the fNodeValue array
1198 * @param nodeIndex
1199 * @return Object - type information for the attribute/element node
1200 */
1201 public Object getTypeInfo(int nodeIndex) {
1202 if (nodeIndex == -1) {
1203 return null;
1204 }
1205
1206 int chunk = nodeIndex >> CHUNK_SHIFT;
1207 int index = nodeIndex & CHUNK_MASK;
1208
1209
1210 Object value = fNodeValue[chunk] != null ? fNodeValue[chunk][index] : null;
1211 if (value != null) {
1212 fNodeValue[chunk][index] = null;
1213 RefCount c = (RefCount) fNodeValue[chunk][CHUNK_SIZE];
1214 c.fCount--;
1215 if (c.fCount == 0) {
1216 fNodeValue[chunk] = null;
1217 }
1218 }
1219 return value;
1220 }
1221
1222 /**
1223 * Returns the value of the given node.
1224 * @param free True to free the value index.
1225 */
1226 public String getNodeValue(int nodeIndex, boolean free) {
1227
1228 if (nodeIndex == -1) {
1229 return null;
1230 }
1231
1232 int chunk = nodeIndex >> CHUNK_SHIFT;
1233 int index = nodeIndex & CHUNK_MASK;
1234 return free ? clearChunkValue(fNodeValue, chunk, index)
1235 : getChunkValue(fNodeValue, chunk, index);
1236
1237 } // getNodeValue(int,boolean):String
1238
1239 /**
1240 * Returns the extra info of the given node.
1241 * Used by AttrImpl to store specified value (1 == true).
1242 */
1243 public int getNodeExtra(int nodeIndex) {
1244 return getNodeExtra(nodeIndex, true);
1245 }
1246
1247 /**
1248 * Returns the extra info of the given node.
1249 * @param free True to free the value index.
1250 */
1251 public int getNodeExtra(int nodeIndex, boolean free) {
1252
1253 if (nodeIndex == -1) {
1254 return -1;
1255 }
1256
1257 int chunk = nodeIndex >> CHUNK_SHIFT;
1258 int index = nodeIndex & CHUNK_MASK;
1259 return free ? clearChunkIndex(fNodeExtra, chunk, index)
1260 : getChunkIndex(fNodeExtra, chunk, index);
1261
1262 } // getNodeExtra(int,boolean):int
1263
1264 /** Returns the type of the given node. */
1265 public short getNodeType(int nodeIndex) {
1266 return getNodeType(nodeIndex, true);
1267 }
1268
1269 /**
1270 * Returns the type of the given node.
1271 * @param free True to free type index.
1272 */
1273 public short getNodeType(int nodeIndex, boolean free) {
1274
1275 if (nodeIndex == -1) {
1276 return -1;
1277 }
1278
1279 int chunk = nodeIndex >> CHUNK_SHIFT;
1280 int index = nodeIndex & CHUNK_MASK;
1281 return free ? (short)clearChunkIndex(fNodeType, chunk, index)
1282 : (short)getChunkIndex(fNodeType, chunk, index);
1283
1284 } // getNodeType(int):int
1285
1286 /** Returns the attribute value of the given name. */
1287 public String getAttribute(int elemIndex, String name) {
1288 if (elemIndex == -1 || name == null) {
1289 return null;
1290 }
1291 int echunk = elemIndex >> CHUNK_SHIFT;
1292 int eindex = elemIndex & CHUNK_MASK;
1293 int attrIndex = getChunkIndex(fNodeExtra, echunk, eindex);
1294 while (attrIndex != -1) {
1295 int achunk = attrIndex >> CHUNK_SHIFT;
1296 int aindex = attrIndex & CHUNK_MASK;
1297 if (getChunkValue(fNodeName, achunk, aindex) == name) {
1298 return getChunkValue(fNodeValue, achunk, aindex);
1299 }
1300 attrIndex = getChunkIndex(fNodePrevSib, achunk, aindex);
1301 }
1302 return null;
1303 }
1304
1305 /** Returns the URI of the given node. */
1306 public String getNodeURI(int nodeIndex) {
1307 return getNodeURI(nodeIndex, true);
1308 }
1309
1310 /**
1311 * Returns the URI of the given node.
1312 * @param free True to free URI index.
1313 */
1314 public String getNodeURI(int nodeIndex, boolean free) {
1315
1316 if (nodeIndex == -1) {
1317 return null;
1318 }
1319
1320 int chunk = nodeIndex >> CHUNK_SHIFT;
1321 int index = nodeIndex & CHUNK_MASK;
1322 return free ? clearChunkValue(fNodeURI, chunk, index)
1323 : getChunkValue(fNodeURI, chunk, index);
1324
1325 } // getNodeURI(int,int):String
1326
1327 // identifier maintenance
1328
1329 /** Registers an identifier name with a specified element node. */
1330 public void putIdentifier(String name, int elementNodeIndex) {
1331
1332 if (DEBUG_IDS) {
1333 System.out.println("putIdentifier(" + name + ", "
1334 + elementNodeIndex + ')' + " // " +
1335 getChunkValue(fNodeName,
1336 elementNodeIndex >> CHUNK_SHIFT,
1337 elementNodeIndex & CHUNK_MASK));
1338 }
1339
1340 // initialize arrays
1341 if (fIdName == null) {
1342 fIdName = new String[64];
1343 fIdElement = new int[64];
1344 }
1345
1346 // resize arrays
1347 if (fIdCount == fIdName.length) {
1348 String idName[] = new String[fIdCount * 2];
1349 System.arraycopy(fIdName, 0, idName, 0, fIdCount);
1350 fIdName = idName;
1351
1352 int idElement[] = new int[idName.length];
1353 System.arraycopy(fIdElement, 0, idElement, 0, fIdCount);
1354 fIdElement = idElement;
1355 }
1356
1357 // store identifier
1358 fIdName[fIdCount] = name;
1359 fIdElement[fIdCount] = elementNodeIndex;
1360 fIdCount++;
1361
1362 } // putIdentifier(String,int)
1363
1364 //
1365 // DEBUG
1366 //
1367
1368 /** Prints out the tables. */
1369 public void print() {
1370
1371 if (DEBUG_PRINT_REF_COUNTS) {
1372 System.out.print("num\t");
1373 System.out.print("type\t");
1374 System.out.print("name\t");
1375 System.out.print("val\t");
1376 System.out.print("par\t");
1377 System.out.print("lch\t");
1378 System.out.print("psib");
1379 System.out.println();
1380 for (int i = 0; i < fNodeType.length; i++) {
1381 if (fNodeType[i] != null) {
1382 // separator
1383 System.out.print("--------");
1384 System.out.print("--------");
1385 System.out.print("--------");
1386 System.out.print("--------");
1387 System.out.print("--------");
1388 System.out.print("--------");
1389 System.out.print("--------");
1390 System.out.println();
1391
1392 // ref count
1393 System.out.print(i);
1394 System.out.print('\t');
1395 switch (fNodeType[i][CHUNK_SIZE]) {
1396 case DocumentImpl.ELEMENT_DEFINITION_NODE: { System.out.print("EDef"); break; }
1397 case Node.DOCUMENT_NODE: { System.out.print("Doc"); break; }
1398 case Node.DOCUMENT_TYPE_NODE: { System.out.print("DType"); break; }
1399 case Node.COMMENT_NODE: { System.out.print("Com"); break; }
1400 case Node.PROCESSING_INSTRUCTION_NODE: { System.out.print("PI"); break; }
1401 case Node.ELEMENT_NODE: { System.out.print("Elem"); break; }
1402 case Node.ENTITY_NODE: { System.out.print("Ent"); break; }
1403 case Node.ENTITY_REFERENCE_NODE: { System.out.print("ERef"); break; }
1404 case Node.TEXT_NODE: { System.out.print("Text"); break; }
1405 case Node.ATTRIBUTE_NODE: { System.out.print("Attr"); break; }
1406 case DeferredNode.TYPE_NODE: { System.out.print("TypeInfo"); break; }
1407 default: { System.out.print("?"+fNodeType[i][CHUNK_SIZE]); }
1408 }
1409 System.out.print('\t');
1410 System.out.print(fNodeName[i][CHUNK_SIZE]);
1411 System.out.print('\t');
1412 System.out.print(fNodeValue[i][CHUNK_SIZE]);
1413 System.out.print('\t');
1414 System.out.print(fNodeURI[i][CHUNK_SIZE]);
1415 System.out.print('\t');
1416 System.out.print(fNodeParent[i][CHUNK_SIZE]);
1417 System.out.print('\t');
1418 System.out.print(fNodeLastChild[i][CHUNK_SIZE]);
1419 System.out.print('\t');
1420 System.out.print(fNodePrevSib[i][CHUNK_SIZE]);
1421 System.out.print('\t');
1422 System.out.print(fNodeExtra[i][CHUNK_SIZE]);
1423 System.out.println();
1424 }
1425 }
1426 }
1427
1428 if (DEBUG_PRINT_TABLES) {
1429 // This assumes that the document is small
1430 System.out.println("# start table");
1431 for (int i = 0; i < fNodeCount; i++) {
1432 int chunk = i >> CHUNK_SHIFT;
1433 int index = i & CHUNK_MASK;
1434 if (i % 10 == 0) {
1435 System.out.print("num\t");
1436 System.out.print("type\t");
1437 System.out.print("name\t");
1438 System.out.print("val\t");
1439 System.out.print("uri\t");
1440 System.out.print("par\t");
1441 System.out.print("lch\t");
1442 System.out.print("psib\t");
1443 System.out.print("xtra");
1444 System.out.println();
1445 }
1446 System.out.print(i);
1447 System.out.print('\t');
1448 switch (getChunkIndex(fNodeType, chunk, index)) {
1449 case DocumentImpl.ELEMENT_DEFINITION_NODE: { System.out.print("EDef"); break; }
1450 case Node.DOCUMENT_NODE: { System.out.print("Doc"); break; }
1451 case Node.DOCUMENT_TYPE_NODE: { System.out.print("DType"); break; }
1452 case Node.COMMENT_NODE: { System.out.print("Com"); break; }
1453 case Node.PROCESSING_INSTRUCTION_NODE: { System.out.print("PI"); break; }
1454 case Node.ELEMENT_NODE: { System.out.print("Elem"); break; }
1455 case Node.ENTITY_NODE: { System.out.print("Ent"); break; }
1456 case Node.ENTITY_REFERENCE_NODE: { System.out.print("ERef"); break; }
1457 case Node.TEXT_NODE: { System.out.print("Text"); break; }
1458 case Node.ATTRIBUTE_NODE: { System.out.print("Attr"); break; }
1459 case DeferredNode.TYPE_NODE: { System.out.print("TypeInfo"); break; }
1460 default: { System.out.print("?"+getChunkIndex(fNodeType, chunk, index)); }
1461 }
1462 System.out.print('\t');
1463 System.out.print(getChunkValue(fNodeName, chunk, index));
1464 System.out.print('\t');
1465 System.out.print(getNodeValue(chunk, index));
1466 System.out.print('\t');
1467 System.out.print(getChunkValue(fNodeURI, chunk, index));
1468 System.out.print('\t');
1469 System.out.print(getChunkIndex(fNodeParent, chunk, index));
1470 System.out.print('\t');
1471 System.out.print(getChunkIndex(fNodeLastChild, chunk, index));
1472 System.out.print('\t');
1473 System.out.print(getChunkIndex(fNodePrevSib, chunk, index));
1474 System.out.print('\t');
1475 System.out.print(getChunkIndex(fNodeExtra, chunk, index));
1476 System.out.println();
1477 }
1478 System.out.println("# end table");
1479 }
1480
1481 } // print()
1482
1483 //
1484 // DeferredNode methods
1485 //
1486
1487 /** Returns the node index. */
1488 public int getNodeIndex() {
1489 return 0;
1490 }
1491
1492 //
1493 // Protected methods
1494 //
1495
1496 /** Synchronizes the node's data. */
1497 protected void synchronizeData() {
1498
1499 // no need to sync in the future
1500 needsSyncData(false);
1501
1502 // fluff up enough nodes to fill identifiers hash
1503 if (fIdElement != null) {
1504
1505 // REVISIT: There has to be a more efficient way of
1506 // doing this. But keep in mind that the
1507 // tree can have been altered and re-ordered
1508 // before all of the element nodes with ID
1509 // attributes have been registered. For now
1510 // this is reasonable and safe. -Ac
1511
1512 IntVector path = new IntVector();
1513 for (int i = 0; i < fIdCount; i++) {
1514
1515 // ignore if it's already been registered
1516 int elementNodeIndex = fIdElement[i];
1517 String idName = fIdName[i];
1518 if (idName == null) {
1519 continue;
1520 }
1521
1522 // find path from this element to the root
1523 path.removeAllElements();
1524 int index = elementNodeIndex;
1525 do {
1526 path.addElement(index);
1527 int pchunk = index >> CHUNK_SHIFT;
1528 int pindex = index & CHUNK_MASK;
1529 index = getChunkIndex(fNodeParent, pchunk, pindex);
1530 } while (index != -1);
1531
1532 // Traverse path (backwards), fluffing the elements
1533 // along the way. When this loop finishes, "place"
1534 // will contain the reference to the element node
1535 // we're interested in. -Ac
1536 Node place = this;
1537 for (int j = path.size() - 2; j >= 0; j--) {
1538 index = path.elementAt(j);
1539 Node child = place.getLastChild();
1540 while (child != null) {
1541 if (child instanceof DeferredNode) {
1542 int nodeIndex =
1543 ((DeferredNode)child).getNodeIndex();
1544 if (nodeIndex == index) {
1545 place = child;
1546 break;
1547 }
1548 }
1549 child = child.getPreviousSibling();
1550 }
1551 }
1552
1553 // register the element
1554 Element element = (Element)place;
1555 putIdentifier0(idName, element);
1556 fIdName[i] = null;
1557
1558 // see if there are more IDs on this element
1559 while (i + 1 < fIdCount &&
1560 fIdElement[i + 1] == elementNodeIndex) {
1561 idName = fIdName[++i];
1562 if (idName == null) {
1563 continue;
1564 }
1565 putIdentifier0(idName, element);
1566 }
1567 }
1568
1569 } // if identifiers
1570
1571 } // synchronizeData()
1572
1573 /**
1574 * Synchronizes the node's children with the internal structure.
1575 * Fluffing the children at once solves a lot of work to keep
1576 * the two structures in sync. The problem gets worse when
1577 * editing the tree -- this makes it a lot easier.
1578 */
1579 protected void synchronizeChildren() {
1580
1581 if (needsSyncData()) {
1582 synchronizeData();
1583 /*
1584 * when we have elements with IDs this method is being recursively
1585 * called from synchronizeData, in which case we've already gone
1586 * through the following and we can now simply stop here.
1587 */
1588 if (!needsSyncChildren()) {
1589 return;
1590 }
1591 }
1592
1593 // we don't want to generate any event for this so turn them off
1594 boolean orig = mutationEvents;
1595 mutationEvents = false;
1596
1597 // no need to sync in the future
1598 needsSyncChildren(false);
1599
1600 getNodeType(0);
1601
1602 // create children and link them as siblings
1603 ChildNode first = null;
1604 ChildNode last = null;
1605 for (int index = getLastChild(0);
1606 index != -1;
1607 index = getPrevSibling(index)) {
1608
1609 ChildNode node = (ChildNode)getNodeObject(index);
1610 if (last == null) {
1611 last = node;
1612 }
1613 else {
1614 first.previousSibling = node;
1615 }
1616 node.ownerNode = this;
1617 node.isOwned(true);
1618 node.nextSibling = first;
1619 first = node;
1620
1621 // save doctype and document type
1622 int type = node.getNodeType();
1623 if (type == Node.ELEMENT_NODE) {
1624 docElement = (ElementImpl)node;
1625 }
1626 else if (type == Node.DOCUMENT_TYPE_NODE) {
1627 docType = (DocumentTypeImpl)node;
1628 }
1629 }
1630
1631 if (first != null) {
1632 firstChild = first;
1633 first.isFirstChild(true);
1634 lastChild(last);
1635 }
1636
1637 // set mutation events flag back to its original value
1638 mutationEvents = orig;
1639
1640 } // synchronizeChildren()
1641
1642 /**
1643 * Synchronizes the node's children with the internal structure.
1644 * Fluffing the children at once solves a lot of work to keep
1645 * the two structures in sync. The problem gets worse when
1646 * editing the tree -- this makes it a lot easier.
1647 * This is not directly used in this class but this method is
1648 * here so that it can be shared by all deferred subclasses of AttrImpl.
1649 */
1650 protected final void synchronizeChildren(AttrImpl a, int nodeIndex) {
1651
1652 // we don't want to generate any event for this so turn them off
1653 boolean orig = getMutationEvents();
1654 setMutationEvents(false);
1655
1656 // no need to sync in the future
1657 a.needsSyncChildren(false);
1658
1659 // create children and link them as siblings or simply store the value
1660 // as a String if all we have is one piece of text
1661 int last = getLastChild(nodeIndex);
1662 int prev = getPrevSibling(last);
1663 if (prev == -1) {
1664 a.value = getNodeValueString(nodeIndex);
1665 a.hasStringValue(true);
1666 }
1667 else {
1668 ChildNode firstNode = null;
1669 ChildNode lastNode = null;
1670 for (int index = last; index != -1;
1671 index = getPrevSibling(index)) {
1672
1673 ChildNode node = (ChildNode) getNodeObject(index);
1674 if (lastNode == null) {
1675 lastNode = node;
1676 }
1677 else {
1678 firstNode.previousSibling = node;
1679 }
1680 node.ownerNode = a;
1681 node.isOwned(true);
1682 node.nextSibling = firstNode;
1683 firstNode = node;
1684 }
1685 if (lastNode != null) {
1686 a.value = firstNode; // firstChild = firstNode
1687 firstNode.isFirstChild(true);
1688 a.lastChild(lastNode);
1689 }
1690 a.hasStringValue(false);
1691 }
1692
1693 // set mutation events flag back to its original value
1694 setMutationEvents(orig);
1695
1696 } // synchronizeChildren(AttrImpl,int):void
1697
1698
1699 /**
1700 * Synchronizes the node's children with the internal structure.
1701 * Fluffing the children at once solves a lot of work to keep
1702 * the two structures in sync. The problem gets worse when
1703 * editing the tree -- this makes it a lot easier.
1704 * This is not directly used in this class but this method is
1705 * here so that it can be shared by all deferred subclasses of ParentNode.
1706 */
1707 protected final void synchronizeChildren(ParentNode p, int nodeIndex) {
1708
1709 // we don't want to generate any event for this so turn them off
1710 boolean orig = getMutationEvents();
1711 setMutationEvents(false);
1712
1713 // no need to sync in the future
1714 p.needsSyncChildren(false);
1715
1716 // create children and link them as siblings
1717 ChildNode firstNode = null;
1718 ChildNode lastNode = null;
1719 for (int index = getLastChild(nodeIndex);
1720 index != -1;
1721 index = getPrevSibling(index)) {
1722
1723 ChildNode node = (ChildNode) getNodeObject(index);
1724 if (lastNode == null) {
1725 lastNode = node;
1726 }
1727 else {
1728 firstNode.previousSibling = node;
1729 }
1730 node.ownerNode = p;
1731 node.isOwned(true);
1732 node.nextSibling = firstNode;
1733 firstNode = node;
1734 }
1735 if (lastNode != null) {
1736 p.firstChild = firstNode;
1737 firstNode.isFirstChild(true);
1738 p.lastChild(lastNode);
1739 }
1740
1741 // set mutation events flag back to its original value
1742 setMutationEvents(orig);
1743
1744 } // synchronizeChildren(ParentNode,int):void
1745
1746 // utility methods
1747
1748 /** Ensures that the internal tables are large enough. */
1749 protected void ensureCapacity(int chunk) {
1750 if (fNodeType == null) {
1751 // create buffers
1752 fNodeType = new int[INITIAL_CHUNK_COUNT][];
1753 fNodeName = new Object[INITIAL_CHUNK_COUNT][];
1754 fNodeValue = new Object[INITIAL_CHUNK_COUNT][];
1755 fNodeParent = new int[INITIAL_CHUNK_COUNT][];
1756 fNodeLastChild = new int[INITIAL_CHUNK_COUNT][];
1757 fNodePrevSib = new int[INITIAL_CHUNK_COUNT][];
1758 fNodeURI = new Object[INITIAL_CHUNK_COUNT][];
1759 fNodeExtra = new int[INITIAL_CHUNK_COUNT][];
1760 }
1761 else if (fNodeType.length <= chunk) {
1762 // resize the tables
1763 int newsize = chunk * 2;
1764
1765 int[][] newArray = new int[newsize][];
1766 System.arraycopy(fNodeType, 0, newArray, 0, chunk);
1767 fNodeType = newArray;
1768
1769 Object[][] newStrArray = new Object[newsize][];
1770 System.arraycopy(fNodeName, 0, newStrArray, 0, chunk);
1771 fNodeName = newStrArray;
1772
1773 newStrArray = new Object[newsize][];
1774 System.arraycopy(fNodeValue, 0, newStrArray, 0, chunk);
1775 fNodeValue = newStrArray;
1776
1777 newArray = new int[newsize][];
1778 System.arraycopy(fNodeParent, 0, newArray, 0, chunk);
1779 fNodeParent = newArray;
1780
1781 newArray = new int[newsize][];
1782 System.arraycopy(fNodeLastChild, 0, newArray, 0, chunk);
1783 fNodeLastChild = newArray;
1784
1785 newArray = new int[newsize][];
1786 System.arraycopy(fNodePrevSib, 0, newArray, 0, chunk);
1787 fNodePrevSib = newArray;
1788
1789 newStrArray = new Object[newsize][];
1790 System.arraycopy(fNodeURI, 0, newStrArray, 0, chunk);
1791 fNodeURI = newStrArray;
1792
1793 newArray = new int[newsize][];
1794 System.arraycopy(fNodeExtra, 0, newArray, 0, chunk);
1795 fNodeExtra = newArray;
1796 }
1797 else if (fNodeType[chunk] != null) {
1798 // Done - there's sufficient capacity
1799 return;
1800 }
1801
1802 // create new chunks
1803 createChunk(fNodeType, chunk);
1804 createChunk(fNodeName, chunk);
1805 createChunk(fNodeValue, chunk);
1806 createChunk(fNodeParent, chunk);
1807 createChunk(fNodeLastChild, chunk);
1808 createChunk(fNodePrevSib, chunk);
1809 createChunk(fNodeURI, chunk);
1810 createChunk(fNodeExtra, chunk);
1811
1812 // Done
1813 return;
1814
1815 } // ensureCapacity(int,int)
1816
1817 /** Creates a node of the specified type. */
1818 protected int createNode(short nodeType) {
1819 // ensure tables are large enough
1820 int chunk = fNodeCount >> CHUNK_SHIFT;
1821 int index = fNodeCount & CHUNK_MASK;
1822 ensureCapacity(chunk);
1823
1824 // initialize node
1825 setChunkIndex(fNodeType, nodeType, chunk, index);
1826
1827 // return node index number
1828 return fNodeCount++;
1829
1830 } // createNode(short):int
1831
1832 /**
1833 * Performs a binary search for a target value in an array of
1834 * values. The array of values must be in ascending sorted order
1835 * before calling this method and all array values must be
1836 * non-negative.
1837 *
1838 * @param values The array of values to search.
1839 * @param start The starting offset of the search.
1840 * @param end The ending offset of the search.
1841 * @param target The target value.
1842 *
1843 * @return This function will return the <i>first</i> occurrence
1844 * of the target value, or -1 if the target value cannot
1845 * be found.
1846 */
1847 protected static int binarySearch(final int values[],
1848 int start, int end, int target) {
1849
1850 if (DEBUG_IDS) {
1851 System.out.println("binarySearch(), target: "+target);
1852 }
1853
1854 // look for target value
1855 while (start <= end) {
1856
1857 // is this the one we're looking for?
1858 int middle = (start + end) >>> 1;
1859 int value = values[middle];
1860 if (DEBUG_IDS) {
1861 System.out.print(" value: "+value+", target: "+target+" // ");
1862 print(values, start, end, middle, target);
1863 }
1864 if (value == target) {
1865 while (middle > 0 && values[middle - 1] == target) {
1866 middle--;
1867 }
1868 if (DEBUG_IDS) {
1869 System.out.println("FOUND AT "+middle);
1870 }
1871 return middle;
1872 }
1873
1874 // is this point higher or lower?
1875 if (value > target) {
1876 end = middle - 1;
1877 }
1878 else {
1879 start = middle + 1;
1880 }
1881
1882 } // while
1883
1884 // not found
1885 if (DEBUG_IDS) {
1886 System.out.println("NOT FOUND!");
1887 }
1888 return -1;
1889
1890 } // binarySearch(int[],int,int,int):int
1891
1892 //
1893 // Private methods
1894 //
1895 private static final int[] INIT_ARRAY = new int[CHUNK_SIZE + 1];
1896 static {
1897 for (int i = 0; i < CHUNK_SIZE; i++) {
1898 INIT_ARRAY[i] = -1;
1899 }
1900 }
1901 /** Creates the specified chunk in the given array of chunks. */
1902 private final void createChunk(int data[][], int chunk) {
1903 data[chunk] = new int[CHUNK_SIZE + 1];
1904 System.arraycopy(INIT_ARRAY, 0, data[chunk], 0, CHUNK_SIZE);
1905 }
1906
1907 static final class RefCount {
1908 int fCount;
1909 }
1910
1911 private final void createChunk(Object data[][], int chunk) {
1912 data[chunk] = new Object[CHUNK_SIZE + 1];
1913 data[chunk][CHUNK_SIZE] = new RefCount();
1914 }
1915
1916 /**
1917 * Sets the specified value in the given of data at the chunk and index.
1918 *
1919 * @return Returns the old value.
1920 */
1921 private final int setChunkIndex(int data[][], int value,
1922 int chunk, int index) {
1923 if (value == -1) {
1924 return clearChunkIndex(data, chunk, index);
1925 }
1926 int [] dataChunk = data[chunk];
1927 // Re-create chunk if it was deleted.
1928 if (dataChunk == null) {
1929 createChunk(data, chunk);
1930 dataChunk = data[chunk];
1931 }
1932 int ovalue = dataChunk[index];
1933 if (ovalue == -1) {
1934 dataChunk[CHUNK_SIZE]++;
1935 }
1936 dataChunk[index] = value;
1937 return ovalue;
1938 }
1939 private final String setChunkValue(Object data[][], Object value,
1940 int chunk, int index) {
1941 if (value == null) {
1942 return clearChunkValue(data, chunk, index);
1943 }
1944 Object [] dataChunk = data[chunk];
1945 // Re-create chunk if it was deleted.
1946 if (dataChunk == null) {
1947 createChunk(data, chunk);
1948 dataChunk = data[chunk];
1949 }
1950 String ovalue = (String) dataChunk[index];
1951 if (ovalue == null) {
1952 RefCount c = (RefCount) dataChunk[CHUNK_SIZE];
1953 c.fCount++;
1954 }
1955 dataChunk[index] = value;
1956 return ovalue;
1957 }
1958
1959 /**
1960 * Returns the specified value in the given data at the chunk and index.
1961 */
1962 private final int getChunkIndex(int data[][], int chunk, int index) {
1963 return data[chunk] != null ? data[chunk][index] : -1;
1964 }
1965 private final String getChunkValue(Object data[][], int chunk, int index) {
1966 return data[chunk] != null ? (String) data[chunk][index] : null;
1967 }
1968 private final String getNodeValue(int chunk, int index) {
1969 Object data = fNodeValue[chunk][index];
1970 if (data == null){
1971 return null;
1972 }
1973 else if (data instanceof String){
1974 return (String)data;
1975 }
1976 else {
1977 // type information
1978 return data.toString();
1979 }
1980 }
1981
1982
1983 /**
1984 * Clears the specified value in the given data at the chunk and index.
1985 * Note that this method will clear the given chunk if the reference
1986 * count becomes zero.
1987 *
1988 * @return Returns the old value.
1989 */
1990 private final int clearChunkIndex(int data[][], int chunk, int index) {
1991 int value = data[chunk] != null ? data[chunk][index] : -1;
1992 if (value != -1) {
1993 data[chunk][CHUNK_SIZE]--;
1994 data[chunk][index] = -1;
1995 if (data[chunk][CHUNK_SIZE] == 0) {
1996 data[chunk] = null;
1997 }
1998 }
1999 return value;
2000 }
2001 private final String clearChunkValue(Object data[][],
2002 int chunk, int index) {
2003 String value = data[chunk] != null ? (String)data[chunk][index] : null;
2004 if (value != null) {
2005 data[chunk][index] = null;
2006 RefCount c = (RefCount) data[chunk][CHUNK_SIZE];
2007 c.fCount--;
2008 if (c.fCount == 0) {
2009 data[chunk] = null;
2010 }
2011 }
2012 return value;
2013 }
2014
2015 /**
2016 * This version of putIdentifier is needed to avoid fluffing
2017 * all of the paths to ID attributes when a node object is
2018 * created that contains an ID attribute.
2019 */
2020 private final void putIdentifier0(String idName, Element element) {
2021
2022 if (DEBUG_IDS) {
2023 System.out.println("putIdentifier0("+
2024 idName+", "+
2025 element+')');
2026 }
2027
2028 // create Map
2029 if (identifiers == null) {
2030 identifiers = new HashMap<>();
2031 }
2032
2033 // save ID and its associated element
2034 identifiers.put(idName, element);
2035
2036 } // putIdentifier0(String,Element)
2037
2038 /** Prints the ID array. */
2039 private static void print(int values[], int start, int end,
2040 int middle, int target) {
2041
2042 if (DEBUG_IDS) {
2043 System.out.print(start);
2044 System.out.print(" [");
2045 for (int i = start; i < end; i++) {
2046 if (middle == i) {
2047 System.out.print("!");
2048 }
2049 System.out.print(values[i]);
2050 if (values[i] == target) {
2051 System.out.print("*");
2052 }
2053 if (i < end - 1) {
2054 System.out.print(" ");
2055 }
2056 }
2057 System.out.println("] "+end);
2058 }
2059
2060 } // print(int[],int,int,int,int)
2061
2062 //
2063 // Classes
2064 //
2065
2066 /**
2067 * A simple integer vector.
2068 */
2069 static final class IntVector {
2070
2071 //
2072 // Data
2073 //
2074
2075 /** Data. */
2076 private int data[];
2077
2078 /** Size. */
2079 private int size;
2080
2081 //
2082 // Public methods
2083 //
2084
2085 /** Returns the length of this vector. */
2086 public int size() {
2087 return size;
2088 }
2089
2090 /** Returns the element at the specified index. */
2091 public int elementAt(int index) {
2092 return data[index];
2093 }
2094
2095 /** Appends an element to the end of the vector. */
2096 public void addElement(int element) {
2097 ensureCapacity(size + 1);
2098 data[size++] = element;
2099 }
2100
2101 /** Clears the vector. */
2102 public void removeAllElements() {
2103 size = 0;
2104 }
2105
2106 //
2107 // Private methods
2108 //
2109
2110 /** Makes sure that there is enough storage. */
2111 private void ensureCapacity(int newsize) {
2112
2113 if (data == null) {
2114 data = new int[newsize + 15];
2115 }
2116 else if (newsize > data.length) {
2117 int newdata[] = new int[newsize + 15];
2118 System.arraycopy(data, 0, newdata, 0, data.length);
2119 data = newdata;
2120 }
2121
2122 } // ensureCapacity(int)
2123
2124 } // class IntVector
2125
2126 } // class DeferredDocumentImpl