nih/tree.h

/* libnih
 *
 * Copyright © 2009 Scott James Remnant <scott@netsplit.com>.
 * Copyright © 2009 Canonical Ltd.
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef NIH_TREE_H
#define NIH_TREE_H

#include <nih/macros.h>

/**
 * Provides a generic binary tree implementation.  No assumption is
 * made about the structure of the tree, or its rules.  Instead when
 * you add a node to a tree, you must specify the parent node and whether
 * to add the new node to its left or right.
 *
 * Tree nodes may be created in one of two ways.  The most common is to
 * embed the NihTree structure as the first member of your own structure,
 * and initialise it with nih_tree_init() after allocating the structure.
 * Alternatively you may create NihTreeEntry structures with
 * nih_tree_entry_new() and point at your own data from them.
 *
 * If you need no data for the tree root, you may use NihTree itself and
 * allocate it with nih_tree_new().
 *
 * Nodes may be added to the tree with nih_tree_add(), passing the parent
 * node, the new node and whether to add to the left or right.
 *
 * To remove a node from the tree, and its children, use nih_tree_remove();
 * the node removed becomes the root of a new tree.
 *
 * Nodes may be moved between trees, or relocated within a tree, by simply
 * calling nih_tree_add() - there's no need to call nih_tree_remove() first.
 *
 * A node may also be removed from a tree and from its children using
 * nih_tree_unlink(); the node removed, and each of its children, become
 * the roots of new trees.
 *
 * Tree-iteration may be performed non-recursively in a pre-order, in-order
 * or post-order fashion; forwards or backwards.  The functions
 * nih_tree_next_full(), nih_tree_prev_full(), nih_tree_next_pre_full(),
 * nih_tree_prev_pre_full(), nih_tree_next_post_full() and
 * nih_tree_prev_post_full() all return the next or previous node, allowing
 * for filtering.  If you do not need to filter macros are provided that
 * pass NULL, named without the _full extension.
 *
 * These are almost always used in a for loop, so macros are provided that
 * expand to a for loop for each of the different orders;
 * NIH_TREE_FOREACH_FULL(), NIH_TREE_FOREACH_PRE_FULL() and
 * NIH_TREE_FOREACH_POST_FULL().  Versions which pass NULL for the filter
 * are provided without the _FULL extension.
 **/


/**
 * NihTreeWhere:
 *
 * These constants define a position for one node, relative to another;
 * usually for when adding a node to an existing tree.
 **/
typedef enum {
	NIH_TREE_LEFT  = -1,
	NIH_TREE_RIGHT =  1,
} NihTreeWhere;


/**
 * NihTree:
 * @parent: parent node in the tree,
 * @left: left child node,
 * @right: right child node.
 *
 * This structure can be used both to refer to a binary tree and can be
 * placed in your own structures to use them as tree nodes.
 *
 * A node without any parent (root node) has @parent set to NULL, nodes
 * without any children (leaf nodes) have @left and @right set to NULL.
 *
 * NihTree is most useful for implementing pure binary trees, where the
 * properties of that structure (such as simple location or traversal) are
 * desired.
 *
 * General trees (where each node may have zero or more nodes, beyond two)
 * can be implemented using binary trees as described by Knuth (fundamentally,
 * head right for siblings, left for children) or as lists of children in
 * each node (such as used by nih_alloc); pick whichever suits your data
 * best.
 **/
typedef struct nih_tree {
	struct nih_tree *parent, *left, *right;
} NihTree;

/**
 * NihTreeEntry:
 * @node: tree node,
 * @data: data pointer,
 * @str: string pointer,
 * @int_data: integer value.
 *
 * This structure can be used as a generic NihTree node that contains
 * a pointer to generic data, a string or contains an integer value.
 *
 * You should take care of setting the data yourself.
 **/
typedef struct nih_tree_entry {
	NihTree node;
	union {
		void *data;
		char *str;
		int   int_data;
	};
} NihTreeEntry;


/**
 * NihTreeFilter:
 * @data: data pointer,
 * @node: node to be visited.
 *
 * A tree filter is a function that is called when iterating a tree to
 * determine whether a particular node and its children should be ignored.
 *
 * Returns: TRUE if the node should be ignored, FALSE otherwise.
 **/
typedef int (*NihTreeFilter) (void *data, NihTree *node);


/**
 * NIH_TREE_FOREACH_FULL:
 * @tree: root of the tree to iterate,
 * @iter: name of iterator variable,
 * @filter: filter function to test each node,
 * @data: data pointer to pass to @filter.
 *
 * Expands to a for statement that in-order iterates over each node in @tree,
 * setting @iter to each node for the block within the loop.
 *
 * If @filter is given, it will be called for each node visited and must
 * return FALSE otherwise the node and its children will be ignored.
 *
 * You should not make changes to the structure of the tree while iterating,
 * since the order will be relatively unpredictable.
 **/
#define NIH_TREE_FOREACH_FULL(tree, iter, filter, data)			\
	for (NihTree *iter = nih_tree_next_full ((tree), NULL, (filter), (data)); \
	     iter != NULL;						\
	     iter = nih_tree_next_full ((tree), iter, (filter), (data)))

/**
 * NIH_TREE_FOREACH_PRE_FULL:
 * @tree: root of the tree to iterate,
 * @iter: name of iterator variable,
 * @filter: filter function to test each node,
 * @data: data pointer to pass to @filter.
 *
 * Expands to a for statement that pre-order iterates over each node in @tree,
 * setting @iter to each node for the block within the loop.
 *
 * If @filter is given, it will be called for each node visited and must
 * return FALSE otherwise the node and its children will be ignored.
 *
 * You should not make changes to the structure of the tree while iterating,
 * since the order will be relatively unpredictable.
 **/
#define NIH_TREE_FOREACH_PRE_FULL(tree, iter, filter, data)		\
	for (NihTree *iter = nih_tree_next_pre_full ((tree), NULL, (filter), (data)); \
	     iter != NULL;						\
	     iter = nih_tree_next_pre_full ((tree), iter, (filter), (data)))

/**
 * NIH_TREE_FOREACH_POST_FULL:
 * @tree: root of the tree to iterate,
 * @iter: name of iterator variable,
 * @filter: filter function to test each node,
 * @data: data pointer to pass to @filter.
 *
 * Expands to a for statement that post-order iterates over each node in @tree,
 * setting @iter to each node for the block within the loop.
 *
 * If @filter is given, it will be called for each node visited and must
 * return FALSE otherwise the node and its children will be ignored.
 *
 * You should not make changes to the structure of the tree while iterating,
 * since the order will be relatively unpredictable.
 **/
#define NIH_TREE_FOREACH_POST_FULL(tree, iter, filter, data)		\
	for (NihTree *iter = nih_tree_next_post_full ((tree), NULL, (filter), (data)); \
	     iter != NULL;						\
	     iter = nih_tree_next_post_full ((tree), iter, (filter), (data)))


/**
 * nih_tree_next:
 * @tree: tree to iterate,
 * @node: node just visited.
 *
 * Iterates the @tree in-order non-recursively; to obtain the first node,
 * @tree should be set to the root of the tree and @node should be NULL.
 * Then for subsequent nodes, @node should be the previous return value
 * from this function.
 *
 * Returns: next in-order node within @tree or NULL if no further nodes.
 **/
#define nih_tree_next(tree, node)			\
	nih_tree_next_full ((tree), (node), NULL, NULL)

/**
 * nih_tree_prev:
 * @tree: tree to iterate,
 * @node: node just visited.
 *
 * Reverse-iterates the @tree in-order non-recursively; to obtain the last
 * node, @tree should be set to the root of the tree and @node should be NULL.
 * Then for subsequent nodes, @node should be the previous return value
 * from this function.
 *
 * Returns: previous in-order node within @tree or NULL if no further nodes.
 **/
#define nih_tree_prev(tree, node)			\
	nih_tree_prev_full ((tree), (node), NULL, NULL)

/**
 * nih_tree_next_pre:
 * @tree: tree to iterate,
 * @node: node just visited.
 *
 * Iterates the @tree in-order non-recursively; to obtain the first node,
 * @tree should be set to the root of the tree and @node should be NULL.
 * Then for subsequent nodes, @node should be the previous return value
 * from this function.
 *
 * Returns: next in-order node within @tree or NULL if no further nodes.
 **/
#define nih_tree_next_pre(tree, node)				\
	nih_tree_next_pre_full ((tree), (node), NULL, NULL)

/**
 * nih_tree_prev_pre:
 * @tree: tree to iterate,
 * @node: node just visited.
 *
 * Reverse-iterates the @tree in-order non-recursively; to obtain the last
 * node, @tree should be set to the root of the tree and @node should be NULL.
 * Then for subsequent nodes, @node should be the previous return value
 * from this function.
 *
 * Returns: previous in-order node within @tree or NULL if no further nodes.
 **/
#define nih_tree_prev_pre(tree, node)				\
	nih_tree_prev_pre_full ((tree), (node), NULL, NULL)

/**
 * nih_tree_next_post:
 * @tree: tree to iterate,
 * @node: node just visited.
 *
 * Iterates the @tree in-order non-recursively; to obtain the first node,
 * @tree should be set to the root of the tree and @node should be NULL.
 * Then for subsequent nodes, @node should be the previous return value
 * from this function.
 *
 * Returns: next in-order node within @tree or NULL if no further nodes.
 **/
#define nih_tree_next_post(tree, node)				\
	nih_tree_next_post_full ((tree), (node), NULL, NULL)

/**
 * nih_tree_prev_post:
 * @tree: tree to iterate,
 * @node: node just visited.
 *
 * Reverse-iterates the @tree in-order non-recursively; to obtain the last
 * node, @tree should be set to the root of the tree and @node should be NULL.
 * Then for subsequent nodes, @node should be the previous return value
 * from this function.
 *
 * Returns: previous in-order node within @tree or NULL if no further nodes.
 **/
#define nih_tree_prev_post(tree, node)				\
	nih_tree_prev_post_full ((tree), (node), NULL, NULL)


/**
 * NIH_TREE_FOREACH:
 * @tree: root of the tree to iterate,
 * @iter: name of iterator variable.
 *
 * Expands to a for statement that in-order iterates over each node in @tree,
 * setting @iter to each node for the block within the loop.
 *
 * You should not make changes to the structure of the tree while iterating,
 * since the order will be relatively unpredictable.
 **/
#define NIH_TREE_FOREACH(tree, iter)					\
	for (NihTree *iter = nih_tree_next ((tree), NULL); iter != NULL; \
	     iter = nih_tree_next ((tree), iter))

/**
 * NIH_TREE_FOREACH_PRE:
 * @tree: root of the tree to iterate,
 * @iter: name of iterator variable.
 *
 * Expands to a for statement that pre-order iterates over each node in @tree,
 * setting @iter to each node for the block within the loop.
 *
 * You should not make changes to the structure of the tree while iterating,
 * since the order will be relatively unpredictable.
 **/
#define NIH_TREE_FOREACH_PRE(tree, iter)				\
	for (NihTree *iter = nih_tree_next_pre ((tree), NULL); iter != NULL; \
	     iter = nih_tree_next_pre ((tree), iter))

/**
 * NIH_TREE_FOREACH_POST:
 * @tree: root of the tree to iterate,
 * @iter: name of iterator variable.
 *
 * Expands to a for statement that post-order iterates over each node in @tree,
 * setting @iter to each node for the block within the loop.
 *
 * You should not make changes to the structure of the tree while iterating,
 * since the order will be relatively unpredictable.
 **/
#define NIH_TREE_FOREACH_POST(tree, iter)				\
	for (NihTree *iter = nih_tree_next_post ((tree), NULL); iter != NULL; \
	     iter = nih_tree_next_post ((tree), iter))


NIH_BEGIN_EXTERN

void          nih_tree_init           (NihTree *tree);
NihTree *     nih_tree_new            (const void *parent)
	__attribute__ ((warn_unused_result, malloc));
NihTreeEntry *nih_tree_entry_new      (const void *parent)
	__attribute__ ((warn_unused_result, malloc));

NihTree *     nih_tree_add            (NihTree *tree, NihTree *node,
				       NihTreeWhere where);

NihTree *     nih_tree_remove         (NihTree *node);
NihTree *     nih_tree_unlink         (NihTree *node);
int           nih_tree_destroy        (NihTree *node);

NihTree *     nih_tree_next_full      (NihTree *tree, NihTree *node,
				       NihTreeFilter filter, void *data);
NihTree *     nih_tree_prev_full      (NihTree *tree, NihTree *node,
				       NihTreeFilter filter, void *data);

NihTree *     nih_tree_next_pre_full  (NihTree *tree, NihTree *node,
				       NihTreeFilter filter, void *data);
NihTree *     nih_tree_prev_pre_full  (NihTree *tree, NihTree *node,
				       NihTreeFilter filter, void *data);

NihTree *     nih_tree_next_post_full (NihTree *tree, NihTree *node,
				       NihTreeFilter filter, void *data);
NihTree *     nih_tree_prev_post_full (NihTree *tree, NihTree *node,
				       NihTreeFilter filter, void *data);

NIH_END_EXTERN

#endif /* NIH_TREE_H */