## Package com.icl.saxon.tinytree

This package is an implementation of the Saxon internal tree structure, designed to minimize memory usage, and the costs of allocating and garbage-collecting Java objects.

See:
Description

Class Summary
TinyBuilder: The TinyBuilder class is responsible for taking a stream of SAX events and constructing a Document tree, using the "TinyTree" implementation.
TinyDocumentImpl: A node in the XML parse tree representing the Document itself (or equivalently, the root node of the Document).

## Package com.icl.saxon.tinytree Description

This package is an implementation of the Saxon internal tree structure, designed to minimize memory usage, and the costs of allocating and garbage-collecting Java objects.

The data structure consists of a set of arrays, held in the TinyDocumentImpl object. These are in three groups.

The principal group of arrays contain one entry for each node other than namespace and attribute nodes. These arrays are in document order. The following information is maintained for each node: the depth in the tree, the name, an "offset" and a "length". The meaning of "offset" and "length" depends on the node type. For text nodes, comment nodes, and processing instructions these fields index into a StringBuffer holding the text. For element nodes, "offset" is an index into the attributes table, and "length" is an offset into the namespaces table. Either of these may be set to -1 if there are no attributes/namespaces.

The attribute group holds the following information for each attribute node: parent element, prefix, local-name, uri, attribute type, and attribute value. Attributes for the same element are adjacent.

The namespace group holds one entry per namespace declaration (not one per namespace node). The following information is held: pointer to the element on which the namespace was declared, namespace prefix, and namespace URI.

The data structure contains no pointers, apart from the links between elements and attributes/namespaces. All navigation is done by serial traversal of the arrays, using the node depth as a guide. Arguably a "next sibling" and/or a "parent" pointer could be justified, and it would be easy to add them, but it seems to work quite fast without them.

When the tree is navigated, transient ("flyweight") nodes are created as Java objects. These disappear as soon as they are no longer needed. Note that to compare two nodes for identity, you can use either the isSameNode() method, or compare the results of getSequentialKey(). Comparing the Java objects using "==" is incorrect.

Michael H. Kay
11 October 2000