Project Homepage of VTD-XML Logo

Sourceforge Home

Mailing Lists





3. Navigate XML

After the parser finishes processing XML, the processing model provides two views of the underlying XML data. The first is a flat view of all VTD records. Corresponding to all tokens in XML in document order, it can be thought of as a view of cached SAX events. The second is a hierarchical view enabled by a cursor-based navigation API allowing for DOM-like random access within the document. And the cursor always points to the VTD record of the current element. In this section, we first describe the important concepts and internal constructs of the navigation API, then demonstrates how everything works together to achieve the purpose of navigation.

3.1 Context Object

To navigate the element hierarchy represented by VTD and location caches, the processing model first creates an integer array (whose size equals the maximum depth M) we call Context Object (CO). Its primary purpose is to track, at any given moment of navigation, the position of the current cursor in the element hierarchy. We use the first entry (CO[0]) in the context object to indicate the current depth of the cursor. The rest of the array is laid out as follows: Assuming the current depth of the cursor is D (D <= Max_depth), we place the VTD indexes of the cursor and all its ancestors (except root index) into the context object according to their depth values (CO[1] ~ CO[D-1]), as shown in Fig. 4. Any unused entries are filled with -1.

Fig. 4. Mapping element hierarchy into Context Object.

Additionally, the context object maintains the necessary state when one wants to look up the namespace URL for a given prefix. This is done by a bottom-up search starting from the attribute tokens under the current element. If no match is found, move up one level and look for attribute tokens of the parent. Repeat this process until one finds the matching name space token and the URL value.

3.2 Element Indexing Strategy

While the context object maintains the necessary internal state for navigating the element hierarchy, it does not fully specify how to obtain those VTD indexes from the VTD buffer and LCs. Indeed, the element indexing strategy of the processing model strongly influences the internal behaviors of the navigation. We summarize those strategies and corresponding navigation behaviors below:

  • VTD scan without LCs- With this option, the processing model doesn't allocate or use LCs at all. Because a VTD record encapsulates both its depth and type, one simply obtains the VTD index of its sibling and children by directly scanning the VTD buffer. Scan backwards if one wants to find the previous sibling; scan forward for the next sibling, the first child and the last child. In fact, the processing model emulates the behavior of Xerces' nodeIterator by scanning VTD buffers for element tokens and simultaneously updating the content of Context Object. The performance is bound by the maximum bandwidth of the memory. For SOAP header processing purposes [6], this option provides an important capability that a SAX parser lacks by default, i.e. being able to go through the same content multiple times without reparsing.

  • Full element indexing- The processing model can choose to index all elements in XML, i.e. one LC per depth level up to the maximum document depth. In this case, VTD indexes are entirely looked up from LCs.

  • Proximity element indexing- For this, we can heuristically pick a depth level so that navigating below that level is by LC lookup; above that level, scan the VTD buffer. We find this strategy suitable in many situations for several reasons. First, full element indexing incurs the cost of allocating LCs and indexing element. Secondly, scanning the VTD buffer, effectively a large number of sequential memory reads, is precisely what the current generation of memory technologies (e.g. DDR SDRAM) are best at. For example, Micron's Samurai DDR chipset (64-bit data bus) [8] running at 133 MHz delivers maximum throughput of over 2GB/s. Furthermore, since one of our design goals is to move the processing model on chip (more discussion later), in order for custom hardware to process XML in a single pass, we find it much easier to hardcode levels of LCs in silicon. Full element indexing in hardware is difficult because the hardware is less flexible and lacks a priori knowledge of the depth of XML. Our initial software implementation employs this proximity indexing strategy with a pre-chosen value of 4.

3.3 An Example

In Fig. 5 we show the content of the context object during a typical navigation run. VTD records and their corresponding tokens are highlighted and labeled with their VTD indexes. We use green color to indicate the element tokens since the cursor only touches those during navigation. Initially, the cursor points to the root element. As it moves deeper into the hierarchy, the depth value and the corresponding entry (underscored ones in Fig. 5) are getting updated to reflect the position change of the cursor. To move up the hierarchy, we only need to update the depth value and the corresponding entry in the context object.

Fig.5. Navigating XML using VTD.

3.4 Important Methods

In our reference implementation, we organize various parsing and navigation functions into two classes: VTDGen and VTDNav. VTDGen takes as the input an in-memory byte array containing the XML document, and produces VTD records and location caches. VTDNav contains the member methods that navigate the hierarchy, compare tokens to strings, and convert tokens to strings or numerical data. In Table 1, we list some of the important member methods of VTDNav.

Method Name/Signature


Boolean toElement(int direction)

This is the primary function for element hierarchy navigation.

Boolean toElement(int direction, String elementName)

Same as last one, plus one needs to specify element  name

Int getText()

This function returns the VTD index for the text node of the current element

Int getAttributeValue(String attributeName)

This function returns the VTD index of an attribute

value for a given attribute name

Int parseInt(int index)

This function takes a VTD index and returns the integer value represented by the token content

Table 1. Selected Member Methods of VTDNav

VTD in 30 seconds

VTD+XML Format

User's Guide

Developer's Guide

VTD: A Technical Perspective

  0. Abstract

  1. Introduction

  2. A Processing Model Based on VTD

  3. Navigate XML

  4. A Closer Look

  5. Conclusion


Code Samples


Getting Involved

Articles and Presentations