tree.h File Reference

Tree Base Class templates. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines
#define	ctl_tree(offset, multiple)   ppConcat4(ctl_tree_,ctlt_offset_name(offset),_,ctlt_multi_name(multiple))
	Build template naming from offset,multiple.
#define	ctl_tree_(offset, multiple, label)   ppConcat3(ctl_tree(offset,multiple),_,label)
	Build template function/data naming.
#define	ctl_tree_node_to_data(offset, multiple, tree, node)   ppConcat(ctl_tree_node_data_,offset)(offset,multiple, tree, node )
	Get data from node.
#define	ctl_tree_data_to_node(offset, multiple, tree, data)   ppConcat(ctl_tree_data_node_,offset)(offset,multiple, tree, data )
	Get node from from data.
#define	ctl_tree_node_init(offset, multiple, node)   { (node)->left = (node)->right = NULL; (node)->balance = 0; }
	Initialize a node to a clear state.
#define	ctl_tree_auto(offset, multiple, comparator, label)
	Initialize a tree on stack or as global Uses non-standard ANSI extension: non-const initializers.
#define	ctl_tree_init(offset, multiple, comparator, tree)   { (tree)->found = (tree)->root = NULL; (tree)->compare = (tree_compare)(comparator); (tree)->size = 0; ctlt_offset_for_relative(offset, (tree)->data_offset = ctlt_getoffset(offset,multiple);) }
	Initialize a tree tree.
#define	ctl_tree_size(offset, multiple,tree)   ((tree)->size)
	Get the count of members in this tree.
Typedefs
typedef int(*	tree_compare )(const void *left, const void *right)

---

Detailed Description

Tree Base Class templates.

Author:

David Mace There are two parameters to these templates: offset and multiple. The interface to the generated functions remains the same, but the data they operate on, and the way they operate differ.

The 'offset' parameter decides how the template code will find the data from links. It can be one of the following:

A 'ctlt_zero' offset means that the node is assumed to be equal to the data (i.e. always the first member). More useful for invasive trees with members that will not be linked with multiple trees. If you want it to be in two trees, one could be this sort of tree, while the other could be one of the invasive trees that supports multiple links.

A 'ctlt_after' offset means that the data is always after the node; (i.e. node+1 = data, (node*)data-1 = node). Most useful for non-invasive trees, where links/data are allocated from a pool, and link doesn't know much explicitly about tree; just that it's in one.

A 'ctlt_relative(off)' offset means the node is some fixed offset from the data (ala offsetof), according to the tree data. This requires a dereference that is not constant, so the code will be a bit slower, but it is also the most flexible; a single class of this can do the work of any of thes others. This is the most miserly type to base your invasive classes from. For this one, the 'off' parameter can be zero when the template is generated or referenced; it's only used when the template is initialized.

A 'ctlt_member(type,node)' offset has a parameter attached to constant describing a specific member of a type of data that is its node. This makes the bloatiest code possible, as a different set of functions for every type of object and member node is generated. Of course, if there are few, or this is a debug build, it might be worth it. Very easy to debug, as type is inserted into node references, so every node can be browsed and the data directly inspected and manipulated with a decent debugger.

The 'multiple' paramter can be one of the following:

If 'ctlt_multiple', a tree can contain multiple nodes of the same value; like std::multiset or std::multimap.

If 'ctlt_unique', each tree value is unique, like std::map or std::set.

Definition in file tree.h.

---

Typedef Documentation

typedef int(* tree_compare)(const void *left, const void *right)

Comparison typedef for all trees

Definition at line 71 of file tree.h.