Tree routines.

Overview

Trees are recursive objects which have an attached list of named attributes. More…

// typedefs

typedef struct te_tree te_tree;

typedef te_errno te_tree_traverse_fn(
    const te_tree *tree,
    void *data
    );

typedef te_errno te_tree_map_fn(
    const te_kvpair_h *src,
    te_kvpair_h *dst,
    void *data
    );

// global functions

te_errno te_tree_get_int_attr(const te_tree* tree, const char* attr, intmax_t* result);
te_errno te_tree_get_float_attr(const te_tree* tree, const char* attr, double* result);
te_errno te_tree_get_bool_attr(const te_tree* tree, const char* attr, bool* result);
te_tree* te_tree_alloc(void);
void te_tree_free(te_tree* tree);
te_errno te_tree_add_attr_va(te_tree* tree, const char* attr, const char* value_fmt, va_list va);
te_errno te_tree_add_attr(te_tree* tree, const char* attr, const char* value_fmt, ...);
te_errno te_tree_add_attrs(te_tree* tree, const te_kvpair_h* attrs);
void te_tree_add_child(te_tree* tree, te_tree* child);
void te_tree_add_kvpair_children(te_tree* tree, const te_kvpair_h* kvpair);
te_tree* te_tree_make_typed(const char* name, const char* type, ...);
const char* te_tree_get_attr(const te_tree* tree, const char* attr);
const char* te_tree_get_type(const te_tree* tree);
bool te_tree_has_attr(const te_tree* tree, const char* attr, const char* value);
bool te_tree_has_attrs(const te_tree* tree, const te_kvpair_h* attrs);
const te_kvpair_h* te_tree_attrs(const te_tree* tree);
const te_tree* te_tree_parent(const te_tree* tree);
const te_tree* te_tree_root(const te_tree* tree);
unsigned int te_tree_level(const te_tree* tree);
const te_tree* te_tree_first_child(const te_tree* tree);
const te_tree* te_tree_last_child(const te_tree* tree);
unsigned int te_tree_count_children(const te_tree* tree);
const te_tree* te_tree_next(const te_tree* tree);
const te_tree* te_tree_prev(const te_tree* tree);
unsigned int te_tree_position(const te_tree* tree);
const te_tree* te_tree_leftmost_leaf(const te_tree* tree);
const te_tree* te_tree_rightmost_leaf(const te_tree* tree);
const te_tree* te_tree_left(const te_tree* tree);
const te_tree* te_tree_right(const te_tree* tree);
const te_tree* te_tree_left_leaf(const te_tree* tree);
const te_tree* te_tree_right_leaf(const te_tree* tree);
const te_tree* te_tree_nth_child(const te_tree* tree, unsigned int nth);
const te_tree* te_tree_child_by_attr(const te_tree* tree, const char* attr, const char* value);
const te_tree* te_tree_child_by_attrs(const te_tree* tree, const te_kvpair_h* attrs);
te_errno te_tree_traverse(const te_tree* tree, unsigned int minlevel, unsigned int maxlevel, te_tree_traverse_fn* pre_cb, te_tree_traverse_fn* post_cb, void* data);
te_tree* te_tree_map(const te_tree* tree, te_tree_map_fn* fn, void* data);
bool te_tree_validate_types(const te_tree* tree, bool allow_unknown, const te_tree** bad_node);

// macros

#define TE_TREE_ATTR_NAME
#define TE_TREE_ATTR_TYPE
#define TE_TREE_ATTR_TYPE_ANNOTATION
#define TE_TREE_ATTR_TYPE_ARRAY
#define TE_TREE_ATTR_TYPE_AUTO
#define TE_TREE_ATTR_TYPE_BOOL
#define TE_TREE_ATTR_TYPE_DICT
#define TE_TREE_ATTR_TYPE_FLOAT
#define TE_TREE_ATTR_TYPE_INT
#define TE_TREE_ATTR_TYPE_NULL
#define TE_TREE_ATTR_TYPE_STRING
#define TE_TREE_ATTR_VALUE

Detailed Documentation

Trees are recursive objects which have an attached list of named attributes.

Attributes are just strings, but some attributes may have special meaning for various functions, in particular defining

the name of a given subtree;
its textual value;
its type.

Trees are mostly immutable: there are functions to build them incrementally, but once a tree is complete, it is not meant to change.

Trees cannot be shared: if a tree is added as a child of some other tree, it cannot be later added as a child of yet another tree.

The linear ordering of nodes is defined as follows:

all children follow their parent;
siblings follow each other.

This means that if a node has children, its immediate successor will be its first child, otherwise its next sibling if there is one, otherwise the next sibling of its parent and so on. In the same way, the immediate predecessor of a node will be the rightmost leaf node of its previous sibling, if any, otherwise its parent.

Typedefs

typedef struct te_tree te_tree

An opaque object representing trees.

typedef te_errno te_tree_traverse_fn(
    const te_tree *tree,
    void *data
    )

Function type for tree traversal.

If the function returns non-zero, the traversal stops immediately, but a value of TE_EOK is returned as zero from te_tree_traverse().

In a pre-callback TE_ESKIP may be returned to prevent descending into the tree children.

Parameters:

tree	current (sub)tree
data	user data
TE_EOK	Stop traversing and report success to the caller.
TE_ESKIP	Do not descend into the children.

Returns:

status code

typedef te_errno te_tree_map_fn(
    const te_kvpair_h *src,
    te_kvpair_h *dst,
    void *data
    )

Attribute mapping function type.

dst is empty upon entry to this function, so it must do copying itself, if needed.

Parameters:

src	source mapping
dst	destination mapping
data	user data

Returns:

status code

Global Functions

te_errno te_tree_get_int_attr(const te_tree* tree, const char* attr, intmax_t* result)

Get an integral value of an attribute of a tree.

Parameters:

tree	tree
attr	attribute name
result	resulting value
TE_ENOENT	No attribute `attr` in `tree`.
TE_ERANGE	The value does not fit into `intmax_t`.
TE_EINVAL	The value is not a valid integer in any base.

Returns:

status code

te_errno te_tree_get_float_attr(const te_tree* tree, const char* attr, double* result)

Get a floating-point value of an attribute of a tree.

Parameters:

tree	tree
attr	attribute name
result	resulting value
TE_ENOENT	No attribute `attr` in `tree`.
TE_ERANGE	The value does not fit into `double`
TE_EINVAL	The value is not a valid floating-point representation.

Returns:

status code

te_errno te_tree_get_bool_attr(const te_tree* tree, const char* attr, bool* result)

Get a boolean value of an attribute of a tree.

All “natural” way of representing booleans are supported:

true, true, True, T, t, YES, yes, Yes, Y, y, 1 all map to true
false, false, False, F, f, NO, no,
No, N, @xc n, 0 and empty string all map to false.

Parameters:

tree	tree
attr	attribute name
result	resulting value
TE_ENOENT	No attribute `attr` in `tree`.
TE_EINVAL	The value is not a valid boolean representation.

Returns:

status code

te_tree* te_tree_alloc(void)

Allocate an empty tree object.

Returns:

a dynamically allocated empty tree (should be freed with te_tree_free())

void te_tree_free(te_tree* tree)

Deallocate tree and all its subtrees.

The function must only be called on a root tree, i.e. the one that is not attached to any parent.

Parameters:

tree	root tree to deallocate

te_errno te_tree_add_attr_va(te_tree* tree, const char* attr, const char* value_fmt, va_list va)

Add an attribute to a tree.

Parameters:

tree	tree to modify
attr	attribute name
value_fmt	attribute value format @oaram va variadic list
TE_EEXIST	`attr` already exists in `tree`

Returns:

status code

te_errno te_tree_add_attr(te_tree* tree, const char* attr, const char* value_fmt, ...)

Add an attribute to a tree.

Parameters:

tree	tree to modify
attr	attribute name
value_fmt	attribute value format @oaram … variadic arguments
TE_EEXIST	`attr` already exists in `tree`

Returns:

status code

te_errno te_tree_add_attrs(te_tree* tree, const te_kvpair_h* attrs)

Add attributes from the kvpair attrs.

If the function returns TE_EEXIST code, all attributes from attrs that were not in tree, are still added to it.

Parameters:

tree	tree to modify
attrs	list of attributes
TE_EEXIST	some attributes from `attrs` were already in `tree`

Returns:

status code

void te_tree_add_child(te_tree* tree, te_tree* child)

Add a child to a tree.

child becomes the last child of tree.

child must not be already added to any other tree and it must not be deallocated by the caller after it has been added.

Parameters:

tree	tree to modify
child	child to add

void te_tree_add_kvpair_children(te_tree* tree, const te_kvpair_h* kvpair)

Convert a key-value mapping to children of tree.

All key-value pairs from kvpair are converted to elementary trees each having two attributes: TE_TREE_ATTR_NAME holding the key and TE_TREE_ATTR_VALUE holding the value. These trees are appended as children to tree in the order of keys in kvpair.

Parameters:

tree	tree to modify
kvpair	list of child descriptions

te_tree* te_tree_make_typed(const char* name, const char* type, ...)

Create a tree with a name and a typed value.

name becomes TE_TREE_ATTR_NAME, type become TE_TREE_ATTR_TYPE, and the value is determined from the type and variadic arguments:

TE_TREE_ATTR_TYPE_AUTO is not supported;
TE_TREE_ATTR_TYPE_NULL accepts no additional arguments;
TE_TREE_ATTR_TYPE_STRING should have a single string argument;
TE_TREE_ATTR_TYPE_INT should have a single int argument;
TE_TREE_ATTR_TYPE_FLOAT should have a single double argument;
TE_TREE_ATTR_TYPE_BOOL should have a single int argument treated as boolean;
TE_TREE_ATTR_TYPE_ARRAY should have a NULL-terminated sequence of subtrees, none of which must have a TE_TREE_ATTR_NAME;
TE_TREE_ATTR_TYPE_DICT should have a NULL-terminated sequence of pairs - name/subtree. Names will be added to subtrees as TE_TREE_ATTR_NAME attributes;
TE_TREE_ATTR_TYPE_ANNOTATION is not supported.

If name is NULL, the resulting tree is unnamed.

In most other places TE_TREE_ATTR_TYPE_INT values are represented by intmax_t. However, here a plain int argument is expected, since it should be a more common usecase.

te_tree_make_typed("node0", TE_TREE_ATTR_TYPE_NULL);
te_tree_make_typed("node1", TE_TREE_ATTR_TYPE_STRING,
                   "string value");
te_tree_make_typed("node2", TE_TREE_ATTR_TYPE_INT, 42);
te_tree_make_typed("node3", TE_TREE_ATTR_TYPE_FLOAT, 42.0);
te_tree_make_typed("node4", TE_TREE_ATTR_TYPE_BOOL, true);
te_tree_make_typed("node6", TE_TREE_ATTR_TYPE_ARRAY,
                   item1, item2, item3, NULL);
te_tree_make_typed("node7", TE_TREE_ATTR_TYPE_DICT,
                   "subnode1", subnode1, "subnode2", subnode2, NULL);

Parameters:

name	name of a tree (may be `NULL`)
type	type of its value
…	variadic arguments defining value

Returns:

a fresh tree or NULL if there are any inconsistencies

const char* te_tree_get_attr(const te_tree* tree, const char* attr)

Get a value of an attribute of a tree.

Parameters:

tree	tree
attr	attribute name

Returns:

attribute value or NULL if no such attribute

const char* te_tree_get_type(const te_tree* tree)

Get the type of a tree.

If the tree has TE_TREE_ATTR_TYPE attribute and its value is not TE_TREE_ATTR_TYPE_AUTO, it is returned.

Otherwise:

if it has TE_TREE_ATTR_VALUE and no children, the type is assumed to be TE_TREE_ATTR_TYPE_STRING;
otherwise if if has at least one child with a TE_TREE_ATTR_NAME which is not of TE_TREE_ATTR_TYPE_ANNOTATION type, the type is TE_TREE_ATTR_TYPE_DICT;
otherwise the type is TE_TREE_ATTR_TYPE_ARRAY; in particular, if a node has no TE_TREE_ATTR_VALUE and no children, it is assumed to represent an empty array.

All scalar nodes without explicit type are detected as TE_TREE_ATTR_TYPE_STRING, even if the value matches some more specific type such as an integer.

Parameters:

tree	tree to inspect

Returns:

type label of tree (never NULL)

bool te_tree_has_attr(const te_tree* tree, const char* attr, const char* value)

Test whether a tree has an attribute with a given name and value.

The presence of the attribute is checked by te_kvpairs_has_kv(), so both key and value may be NULL, meaning “any string”.

Parameters:

tree	tree
attr	attribute name (may be `NULL`)
value	attribute value (may be `NULL`)

Returns:

true if there is an attribute with a given name and value

bool te_tree_has_attrs(const te_tree* tree, const te_kvpair_h* attrs)

Test whether a tree has all attributes specified by attrs.

Parameters:

tree	tree
attrs	list of name-value pairs

Returns:

true if all attributes from attrs have matching values in tree

const te_kvpair_h* te_tree_attrs(const te_tree* tree)

Get an immutable attribute list.

Parameters:

tree

Returns:

a list of attribute name-value pairs

const te_tree* te_tree_parent(const te_tree* tree)

Get the parent of a tree.

Parameters:

tree

Returns:

the parent of tree or NULL

const te_tree* te_tree_root(const te_tree* tree)

Get the root of a tree.

Parameters:

tree

Returns:

the root of tree (never NULL)

unsigned int te_tree_level(const te_tree* tree)

Get the level of a tree.

The level is the length of a path from the root to a given subtree. If the tree is the root, the level is 0.

Parameters:

tree

Returns:

the level of tree

const te_tree* te_tree_first_child(const te_tree* tree)

Get the first (leftmost) child of a tree.

Parameters:

tree

Returns:

the first child of tree (NULL if none)

const te_tree* te_tree_last_child(const te_tree* tree)

Get the last (rightmost) child of a tree.

Parameters:

tree

Returns:

the first child of tree (NULL if none)

unsigned int te_tree_count_children(const te_tree* tree)

Count the number of children of a tree.

Parameters:

tree

Returns:

the number of children of tree

const te_tree* te_tree_next(const te_tree* tree)

Get the next sibling of tree.

Parameters:

tree

Returns:

the next sibling of tree or NULL

const te_tree* te_tree_prev(const te_tree* tree)

Get the previous sibling of tree.

Parameters:

tree

Returns:

the previous sibling of tree or NULL

unsigned int te_tree_position(const te_tree* tree)

Get the position of a tree.

The position is the ordinal number of a tree among its siblings. The first child of its parent has a position 0.

Parameters:

tree

Returns:

the position of tree

const te_tree* te_tree_leftmost_leaf(const te_tree* tree)

Get the leftmost leaf descendant of tree.

Parameters:

tree

Returns:

the leftmost leaf of tree (never NULL)

const te_tree* te_tree_rightmost_leaf(const te_tree* tree)

Get the rightmost leaf descendant of tree.

Parameters:

tree

Returns:

the leftmost leaf of tree (never NULL)

const te_tree* te_tree_left(const te_tree* tree)

Get the tree immediately preceding tree in linear order.

Parameters:

tree

Returns:

the tree immediately preceding tree or NULL

const te_tree* te_tree_right(const te_tree* tree)

Get the tree immediately following tree in linear order.

Parameters:

tree

Returns:

the tree immediately following tree or NULL

const te_tree* te_tree_left_leaf(const te_tree* tree)

Get the nearest leaf following tree in linear order.

Parameters:

tree

Returns:

the leaf following tree or NULL

const te_tree* te_tree_right_leaf(const te_tree* tree)

Get the nearest leaf preceding tree in linear order.

Parameters:

tree

Returns:

the leaf preceding tree or NULL

const te_tree* te_tree_nth_child(const te_tree* tree, unsigned int nth)

Get the nth child of tree.

Parameters:

tree	tree
nth	0-based index

Returns:

the nth child of tree or NULL

const te_tree* te_tree_child_by_attr(const te_tree* tree, const char* attr, const char* value)

Get the first child with a given attribute.

The check is performed by te_tree_has_attr().

Parameters:

tree	tree
attr	attribute name (may be `NULL`)
value	attribute name (may be `NULL`)

Returns:

the first matching child or NULL

const te_tree* te_tree_child_by_attrs(const te_tree* tree, const te_kvpair_h* attrs)

Get the first child with given attributes.

The check is performed by te_tree_has_attrs().

Parameters:

tree	tree
attr	attribute name (may be `NULL`)
value	attribute name (may be `NULL`)

Returns:

the first matching child or NULL

te_errno te_tree_traverse(const te_tree* tree, unsigned int minlevel, unsigned int maxlevel, te_tree_traverse_fn* pre_cb, te_tree_traverse_fn* post_cb, void* data)

Traverse the tree.

Callbacks are only called for subtrees that are at least minlevel below tree, and the traversal does not go deeper than maxlevel below tree. So for example to process only direct children of tree, one may use:

te_tree_traverse(tree, 1, 1, child_cb, NULL, userdata);

Parameters:

tree	tree to traverse
minlevel	minimum level to call callbacks on
maxlevel	maximum level to descend
pre_cb	preorder callback (may be `NULL`)
post_cb	postorder callback (may be `NULL`)

Returns:

status code

te_tree* te_tree_map(const te_tree* tree, te_tree_map_fn* fn, void* data)

Construct a new tree from an old one converting attributes.

If the conversion function fn ever returns non-zero, the new tree is destroyed and NULL is returned.

No attributes of the tree are automatically copied, the mapping function should use te_kvpairs_copy() or te_kvpairs_copy_key() to copy the needed attributes.

Parameters:

tree	source tree
fn	attribute translation function
data	user data

Returns:

a fresh translated tree or NULL

bool te_tree_validate_types(const te_tree* tree, bool allow_unknown, const te_tree** bad_node)

Check that all subtrees have correct types and values.

The type of each node is detected by te_tree_get_type() and then the following constraints apply:

if the type is TE_TREE_ATTR_TYPE_NULL, the node must have no TE_TREE_ATTR_VALUE and no children;
if the type is scalar (one of TE_TREE_ATTR_TYPE_STRING, TE_TREE_ATTR_TYPE_BOOL, TE_TREE_ATTR_TYPE_INT, TE_TREE_ATTR_TYPE_FLOAT) it must have a TE_TREE_ATTR_VALUE and no children;
if the type is TE_TREE_ATTR_TYPE_BOOL, the value must be valid as per te_tree_get_bool_attr();
if the type is TE_TREE_ATTR_TYPE_INT, the value must be valid as per te_tree_get_int_attr();
if the type is TE_TREE_ATTR_TYPE_FLOAT, the value must be valid as per te_tree_get_float_attr();
if the type is TE_TREE_ATTR_TYPE_ARRAY, all children that are not annotations must have no names;
if the type is TE_TREE_ATTR_TYPE_DICT, all children that are not annotations must have names;
if the type is unknown and allow_unknown is true, the node itself is always considered valid; children are recursively checked; otherwise the node is invalid;
if the type is TE_TREE_ATTR_TYPE_ANNOTATION, the node is considered valid and no children are further checked.

Parameters:

tree	tree to check
allow_unknown	allow unknown types for tree nodes
bad_node	location for a pointer to the first detected bad node

Returns:

true if the tree is valid

Macros

#define TE_TREE_ATTR_NAME

Tree name.

#define TE_TREE_ATTR_TYPE

Tree value type.

#define TE_TREE_ATTR_TYPE_ANNOTATION

A node with metadata that should not be serialized in-band.

#define TE_TREE_ATTR_TYPE_ARRAY

Linear array.

#define TE_TREE_ATTR_TYPE_AUTO

Auto-detect type (the default if no type attribute).

#define TE_TREE_ATTR_TYPE_BOOL

Boolean type.

#define TE_TREE_ATTR_TYPE_DICT

Dictionary (an associative array).

#define TE_TREE_ATTR_TYPE_FLOAT

Floating-point type.

#define TE_TREE_ATTR_TYPE_INT

Integer type.

#define TE_TREE_ATTR_TYPE_NULL

Null type.

#define TE_TREE_ATTR_TYPE_STRING

String type.

#define TE_TREE_ATTR_VALUE

Tree value.