Warning: The internal details of this class are subject to change. SAX2DTM should generally be accessed only through published interface methods in in the DTM and DTMManager classes. However, the following information is provided to aid in an understanding of how this class currently works, for debugging purposes and to help guide DTM's further evolution.
This implementation of DTM stores information about each node in a series of tables. Conceptually, these tables can be thought of as arrays and vectors, though they are generally implemented using some internal classes (for various reasons, including more efficient incremental growth, reduced memory use, and efficient content-based access).
Note that SAX2DTM inherits a great deal of its structure and behavior from DTMDefaultBase, and that XNI2DTM in turn inherits from SAX2DTM.
Document Table Model (DTM) node addressing occurs at two levels.
The public DTM APIs currently use Node Handles. These integers encapsulate information which -- with the help of a DTMManager object -- can be expanded into a pointer to a DTM object and a Node Identifier integer.
The Node Identifier specifies which node we are addressing within a given DTM. You can think of it as the "row number" in the DTM's tables, where each row represents a single Node.
In SAX2DTM (and in most DTM implementations), Node Identifiers are assigned sequentially in document order as the DTM model is built, and we take advantage of that in some of the code. However, this is strictly an implementation detail, and other DTMs may assign Identifiers in other orders.
These are indexed by the Node Identifier integer. You can think of all values in this chart addressed by the same Node Identity as forming a single Node record; separate arrays were used primarily because Java didn't offer us a good mixed-type array representation.
Note that if we were coding in C, we'd have used a single table of Structs. Unfortunately the closest Java can come to that is Objects, and objects have a lot of overhead -- which is a large part of why we switched to DTM. One downside of this approach is that we've lost some locality-of-reference; different properties of the same node are no longer located near each other in memory, which may have adverse effects on the computer's memory cache.
Also note that our use of arrays (either directly or within other wrappers) forces us to accept some unnecessary overhead, since Java insists on range-checking all array accesses. Again, DTM would be more "comfortable" if coded in a language such as C.
| Array Name | Array Type | Contents |
|---|---|---|
m_firstCh |
int | Node-tree relationships; the
integer index of the node bearing this relationship to the current
node. If no such node exists, these are set to DTM.NULL (-1).
Note that there isn't a column for first namespace declaration, or first attribute node. These are currently stored in SAX2DTM (and in the "native core" DTMDefaultBase) as immediate successors to the element node on which they appear, with namespace declarations ordered before attributes. The first child (if any) will immediately follow the namespaces and attributes (if any). (Example: If the element has Node ID 17, and its first child has Node ID 20, then nodes 18 and 19 will be Namespace and/or and Attribute nodes for this element. The attribute/namespace access methods scan across this group, checking node types to separate it into its two categories.) |
m_exptype |
int | An integer representing the node's
"Expanded Type". For some kinds of node, this is the same as the DOM
Node type. Namespace declaration nodes, which didn't have a node type
before DOM Level 3, have been assigned a new value. For nodes which
have a QName (elements and attributes in particular), we generate a
unique value for each combination of DOM Node type, namespace URI, and
Local Name. m_exptype indexes into a table which maps
the Expanded Type number to the three subfields it summarizes.
This approach both reduces storage and turns the common three-field test "Is this node an Element with this specific namespace/localname pair" into a single equality comparison, at the cost of making less-specific tests more expensive. NOTE: It might be worth changing this column from integers to pointers-to-records within the Expanded Type table, speeding up retrieval of the Expanded Type's subfields. |
m_dataOrQName |
int | OVERLOADED COLUMN: An index into either m_data or m_valuesOrPrefixes, as explained below. |
m_namespaceDeclSetElements
with m_namespaceDeclSets |
Complicated but yields int[] | SPARSE COLUMN: Finding the
"in scope" namespaces on a node is expensive, since they may be
inherited from any ancestor and may have gone through multiple stages
of redefinition. We currently precalculate these sets, maintaining a
sparse table of the places in the document where the sets actually
change and taking advantage of the fact that node identifiers are
assigned in document order to quickly find the set which applies for
any given node.
The set is returned as the node handles of the Xalan namespace declaration nodes which are in scope at this point. The parent of a namespace declaration node (and its node ordering) places it immediately following the Element it originally appeared on. Note that the last point is a deliberate divergence from the XPath 1.0 Data Model spec. They make the mistake of saying that every node has an independent set of its own Namespace Nodes, which see it as their parent. Everyone agrees that this was a blatantly bad decision; it's impossible to implement efficiently, Namespace nodes are extremely rarely accessed, and nobody but a testcase author seems to care what a Namespace's parent actually is. At this time, XPath 2.0 is planning to deprecate the entire concept of Namespace Nodes and only let folks retrieve the in-scope namespaces as name/value pairs; our solution is fully compatible with that approach. |
| SAX2DTM has three "optional" columns, allocated only
when the user explicitly enables this feature, which support a
SAX-style "locator" describing the node's physical position in its
source file. These is used by some IDE and debugging tools. It might
be better to instead generate simple XPaths to the nodes (which can be
done directly from the DTM model), and have the tools interpret those;
this approach would avoid the storage overhead, would be meaningful
even when the source-file information is not available (e.g., accessing
a DOM2DTM or a Result Tree Fragment), and would have all the other
benefits associated with XPaths, but would also have computational
costs.
Of course, if the user didn't request locator support, the DTM recognizes that these columns are absent and the location accessors return their "not known" values. |
||
m_sourceSystemID |
String | URI this node was loaded from, if known. (Base URI at this point in the document/entity.) |
m_sourceLine |
int | Line within text file/stream that this node was loaded from, if known. |
m_sourceColumn |
int | Character position on source line within text file/stream that this node was loaded from, if known. |
| In XNI2DTM, which is a schema-type-aware derivative of SAX2DTM, there is an additional column: | ||
m_schemaTypeOverride |
(Schema type object reference) | SPARSE COLUMN: If this node is an element/attribute whose Schema Type does not precisely match that normally bound to its Expanded Type (see below), the actual type will be recorded here. If there is no entry,, the "default" Schema Type can be retrieved from the Expanded Type table. |
As a space-saving measure, the m_dataOrQName column is
overloaded, and used for several different purposes depending on the
Expanded Node Type. Sometimes m_dataOrQName is a direct index into
m_valuesOrPrefixes, and sometimes it goes through m_data (where,
again, it may be interpreted different ways in different cases).
The best thing I can say about this solution is that it works and does reduce memory usage.
Note that m_data is actually treated as
an array of pairs of integers. If we were coding in
C, we'd use an array of structs, or array of int[2]. Java doesn't have
an efficient version of that concept, so instead we use a single array
of integers and simply address every second position. This
microoptimization reduces the cost of expanding the storage for this
table, when that's necessary ... but it would have been cleaner to
simply use two arrays together as a two-column table, as we did in the
Main Node Description chart above.
| Node Type (from m_expType) | m_dataOrQName |
m_data |
|---|---|---|
| Attr (namespaced or not) |
In A Namespace: a negative number, the absolute value of which is an index
into m_data.
No namespace: an index into
|
index: an int containing the index into
m_valuesOrPrefixes for the Attr QName.
index+1: an int
containing the index into |
| Comment | index into m_valuesOrPrefixes
for comment text. |
unused |
| Document | 0 | unused |
| Element (namespaced or not) |
In A Namespace: an index into
m_valuesOrPrefixes pointing to the Element QName.No namespace: 0 (unused?) |
unused |
| Text | an index into m_data. |
index: an int containing starting subscript in
m_chars for the text.
index+1: an int containing the length of the text. |
| Processing Instruction | index into m_valuesOrPrefixes
for PI data. |
unused |
| Namespace Node | index into
m_valuesOrPrefixes pointing to the namespace URI being bound to a prefix. |
unused |
The following arrays are indexed by, and expand upon, information from the other tables. This indirection is done either because the integer can be directly used as an efficient stand-in for a larger or more complicated value, or because we're overloading a field in the main tables and need someplace to store the additional information, or because we used to be using shift-and-mask to combine several values in a single column of those tables... or some combination of these.
(Early versions of DTM were somewhat biased toward storing data as integers, since they used a lot of shift-and-mask subaddressing to pack multiple values directly into a single array. In fact, the original DTM prototype managed to squeeze the essential information about a node into just four words of storage -- not counting text content, of course. Performance issues caused us to retire that design.)
| Array Name | Array Type | Contents |
|---|---|---|
m_expandedNameTable |
ExtendedType object (yes, we're inconsistent about whether it's "expanded" or "extended") | An entry in this table summarizes the "semantic role" of a node, combining its XPath Node Type, its namespace URI (if any), and its local name (if any). A single slot is assigned for each unique combination of these values; thus, comparing offsets in this table combines testing all three values, which improves XPath execution efficiency.
If schema types are being recorded (XNI2DTM), this table also records
a default Schema Datatype for this semantic role. This isn't currently
being optimized; the datatype stored is just the first one we see
associated with this Expanded Type combination. Since local type
overrides are uncommon, this will generally be correct; when it isn't,
it may be overridden on a per-node basis by | .
m_valuesOrPrefixes | String | This "string pool" collects unique (typically small) Strings which we expect may be used many times -- specifically, QNames and attribute values. A single copy of each unique string will be stored, and all references to the same value are pointed to that one instance. |
m_data |
int[2] (actually consecutive in single array) | Addressed -- sometimes -- from m_dataOrQName. This may be an offset/length pair specifying a portion of m_chars, or a pair of indexes into m_valuesOrPrefixes. See Data Column Overloading. |
m_chars |
char | Contiguous pool of characters. Chunks of this are allocated as needed to represent text-string values, and addressed using starting offset and length within m_chars. This approach avoids paying the substantial overhead involved in allocating a Java String object for each name or value string, and should offer better performance than the standard Java StringBuffer class since it has been tuned for our needs. |
| Table Name | Table Type | Contents |
|---|---|---|
m_entities |
String[4] (actually consecutive in single array) | DTD information: Descriptions of Unparsed Entities referenced by this document, accessed by entity name. Supports typed attributes. |
m_idAttributes |
int | Lookup table for IDs, addressed by string value. Returns the node number of the attribute which asserted that unique ID. Supports typed attributes. |