---

Overview of the DataTree library

C_lang_v0.8_beta

Purpose

This library provides support for a hierarchical data structures, which can streamed to/from a flat file, or dynamically manipulated in-memory.

It is a convenent tool to support:

• as a format for saving application data in a human-readable form
• as a way to support flexible configuration files, and even scripting languages

In some ways, it can be seen as similar to XML, but it is a much more lightweight approach, and is not intended to be used as a text markup (just as XML wasn't designed for storing application data, or for readability of the text form by naive users).

This library is lightweight and modular, written in portable C. Its modularity means that it is very easy to implement support for new file formats, or even to replace the in-memory representation of a tree

• as long as the hierarchical data structure is preserved.

The structure of a datatree

A data tree is made of a hierarchy of nodes, which can be of 3 types:

• a leaf node -- containing raw data. To output readable text files, the data should typically be a string, but it may contain any binary data as well.
• an array node -- containing a sequence of sub-nodes.
• an record node -- containing a list of sub-nodes, each of which is associated with a key (a string identifier or any data). For those familiar with the PERL language, these tree node types closely match the 3 types of perl variables (scalars, arrays, and dictionnaries).

This tree-like structure can be represented and manipulated in two forms:

• as a flattened stream of data accessed sequentially. This is convenient for storing the data it a file, transmitting it. It also has a low memory footprint.
• as a tree loaded in memory, which can be randomly accessed and traversed.

These two representations are independently implemented, and can be independently replaced. This library currently provides one in-memory representation, and supports streaming to a single text file format.

In-memory representation.

When a datatree is loaded in memory, each node is represented as an instance of the dt_node_ base class -- an internally defined structure accessed through a pointer and a set of provided functions.

Three subclasses of dt_node implement the leaf, array and record nodes. They are instantiated using the dt_make_leaf(), dt_make_arr(), and dt_make_rec() functions.

See also:

dt_node.h

Streaming of a datatree

When a datatree is streamed, it is flattended by traversing the tree. The traversal starts from the root, reports when an array or record is entered or being left, and includes each leaf node data.
Each event that occurs during traversal is described in data structure of type dt_stream_step.

Tree traversal can happen either in pull or push mode, and is supported by the following objects:

• a dt_reader instance is called using dt_read() to query ("pull") the next step of a tree traversal.
• a dt_writer instance is called using dt_write() to send ("push") the next step of a tree traversal.

These objects are comparable to input/output ports. Utility functions can transfer data from a source to a destination, and can also validate the consistency of the transferred data (that is, check that record and array entry/exit events are properly paired). (See file dt_stream_util.h).

See also:

dt_stream.h

Overview of interfaces

The following headers provide the core C interface to this library:

• dt_node.h allows the creation and manipulation of an in-memory representation of a datatree.
• dt_stream.h provides the base class objects that can be used to traverse a datatree as a stream of data records, to allow writing, reading, and transmission of the tree.
• dt_stream_util.h provides high-level functions for streaming an in-memory datatree to/from a text file (saving/reloading a tree).
  Its functionality is implemented using lower-level features available in the following headers:
  • dt_stream_validator.h verifies the consistency of a datatree stream. It eases the development of parsers for datatree file formats, by taking charge of validating the structure of the stream.
  • dt_stream_tree.h allows to send an in-memory datatree to a stream, or to reconstruct an in-memory data tree from a stream.
  • dt_stream_text.h supports a standard text file format for writing and reloading a datatree from a human-readable text file.

Historical Notes

Earlier versions of this library have been in use since 1996, and were implemented in C++. It also had been ported to Delphi. For increased portability, this library has been ported to plain C in May 2003.

Author:

Ivan Vecerina -- http://www.post1.com/~ivec

---