nih/tree.c - chromiumos/third_party/libnih - Git at Google

 /* libnih
  *
  * tree.c - generic binary tree implementation
  *
  * 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.
  */

 #ifdef HAVE_CONFIG_H
 # include <config.h>
 #endif /* HAVE_CONFIG_H */


 #include <nih/macros.h>
 #include <nih/logging.h>
 #include <nih/alloc.h>

 #include "tree.h"


 /**
  * nih_tree_init:
  * @tree: tree node to be initialised.
  *
  * Initialise an already allocated tree node, once done it can be used
  * as the start of a new binary tree or added to an existing tree.
  **/
 void
 nih_tree_init (NihTree *tree)
 {
 	nih_assert (tree != NULL);

 	tree->parent = tree->left = tree->right = NULL;
 }

 /**
  * nih_tree_new:
  * @parent: parent object for new node.
  *
  * Allocates a new tree structure, usually used as the root of a new
  * binary tree.  You may prefer to allocate the NihTree structure statically
  * and use nih_tree_init() to initialise it instead.
  *
  * The structure is allocated using nih_alloc() so can be used as a context
  * to other allocations.
  *
  * If @parent is not NULL, it should be a pointer to another object which
  * will be used as a parent for the returned tree node.  When all parents
  * of the returned tree node are freed, the returned tree node will also be
  * freed.
  *
  * Returns: the new tree node or NULL if the allocation failed.
  **/
 NihTree *
 nih_tree_new (const void *parent)
 {
 	NihTree *tree;

 	tree = nih_new (parent, NihTree);
 	if (! tree)
 		return NULL;

 	nih_tree_init (tree);

 	nih_alloc_set_destructor (tree, nih_tree_destroy);

 	return tree;
 }

 /**
  * nih_tree_entry_new:
  * @parent: parent object for new entry.
  *
  * Allocates a new tree entry structure, leaving the caller to set the
  * data of the entry.
  *
  * The structure is allocated using nih_alloc() so can be used as a context
  * to other allocations.
  *
  * If @parent is not NULL, it should be a pointer to another object which
  * will be used as a parent for the returned tree entry.  When all parents
  * of the returned tree entry are freed, the returned tree entry will also be
  * freed.
  *
  * Returns: the new tree entry or NULL if the allocation failed.
  **/
 NihTreeEntry *
 nih_tree_entry_new (const void *parent)
 {
 	NihTreeEntry *tree;

 	tree = nih_new (parent, NihTreeEntry);
 	if (! tree)
 		return NULL;

 	nih_tree_init (&tree->node);

 	nih_alloc_set_destructor (tree, nih_tree_destroy);

 	tree->data = NULL;

 	return tree;
 }


 /**
  * nih_tree_add:
  * @tree: node in the destination tree,
  * @node: node to be added to the tree,
  * @where: where @node should be added.
  *
  * Adds @node to a new binary tree, either as a child of or, or replacing,
  * the existing node @tree.  The exact position is determined by @where,
  * which may be NIH_TREE_LEFT or NIH_TREE_RIGHT to indicate that @node
  * should be a child of @tree or NIH_TREE_HERE to indicate that @node
  * should replace @tree.
  *
  * If @node is already in another tree it is removed so there is no need
  * to call nih_tree_remove() before this function.  There is also no
  * requirement that the trees be different, so this can be used to reorder
  * a tree.
  *
  * Returns: node replaced by @node, normally NULL.
  **/
 NihTree *
 nih_tree_add (NihTree      *tree,
 	      NihTree      *node,
 	      NihTreeWhere  where)
 {
 	NihTree *replaced = NULL;

 	nih_assert (tree != NULL);

 	if (node)
 		nih_tree_remove (node);

 	if (where == NIH_TREE_LEFT) {
 		replaced = tree->left;
 		if (replaced)
 			replaced->parent = NULL;

 		tree->left = node;
 		if (node)
 			node->parent = tree;

 	} else if (where == NIH_TREE_RIGHT) {
 		replaced = tree->right;
 		if (replaced)
 			replaced->parent = NULL;

 		tree->right = node;
 		if (node)
 			node->parent = tree;

 	}

 	return replaced;
 }


 /**
  * nih_tree_remove:
  * @node: node to be removed.
  *
  * Removes @node and its children from the containing tree.  Neither the
  * node nor children are freed, and the children are not unlinked from the
  * node.  Instead the node is returned so that it can be added to another
  * tree (through there's no need to call nih_tree_remove() first if you
  * wanted to do that) or used as the root of a new tree.
  *
  * Returns: @node as a root node.
  **/
 NihTree *
 nih_tree_remove (NihTree *node)
 {
 	nih_assert (node != NULL);

 	if (node->parent) {
 		if (node->parent->left == node) {
 			node->parent->left = NULL;
 		} else if (node->parent->right == node) {
 			node->parent->right = NULL;
 		}

 		node->parent = NULL;
 	}

 	return node;
 }

 /**
  * nih_tree_unlink:
  * @node: node to be removed.
  *
  * Removes @node from its containing tree, as nih_tree_remove() does, but
  * also unlinks the node's children from itself so that they don't have
  * a dangling pointer.
  *
  * Returns: @node.
  **/
 NihTree *
 nih_tree_unlink (NihTree *node)
 {
 	nih_assert (node != NULL);

 	nih_tree_remove (node);

 	if (node->left)
 		node->left->parent = NULL;

 	if (node->right)
 		node->right->parent = NULL;

 	node->left = node->right = NULL;

 	return node;
 }

 /**
  * nih_tree_destroy:
  * @node: node to be removed.
  *
  * Removes @node from its containing tree.
  *
  * Normally used or called from an nih_alloc() destructor so that the list
  * item is automatically removed from its containing list when freed.
  *
  * Returns: zero.
  **/
 int
 nih_tree_destroy (NihTree *node)
 {
 	nih_assert (node != NULL);

 	nih_tree_unlink (node);

 	return 0;
 }


 /**
  * VISIT:
  * @_node: node to check.
  *
  * Macro to expand to check whether a node is set, and whether the filter is
  * either unset or says not to filter this node.
  **/
 #define VISIT(_node) ((_node) && ((! filter) || (! filter (data, (_node)))))

 /**
  * nih_tree_next_full:
  * @tree: tree to iterate,
  * @node: node just visited,
  * @filter: filter function to test each node,
  * @data: data pointer to pass to @filter.
  *
  * 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.
  *
  * 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.
  *
  * Returns: next in-order node within @tree or NULL if no further nodes.
  **/
 NihTree *
 nih_tree_next_full (NihTree       *tree,
 		    NihTree       *node,
 		    NihTreeFilter  filter,
 		    void          *data)
 {
 	NihTree *prev;

 	nih_assert (tree != NULL);

 	if (node) {
 		prev = node;
 		if (VISIT (node->right)) {
 			node = node->right;
 		} else {
 			if (node == tree)
 				return NULL;

 			node = node->parent;
 		}
 	} else {
 		prev = tree->parent;
 		node = tree;
 	}

 	for (;;) {
 		NihTree *tmp = node;

 		if ((prev == node->parent) && VISIT (node->left)) {
 			node = node->left;
 		} else if (VISIT (node->right) && (prev == node->right)) {
 			if (node == tree)
 				return NULL;

 			node = node->parent;
 		} else if (VISIT (node)) {
 			return node;
 		} else {
 			return NULL;
 		}

 		prev = tmp;
 	}
 }

 /**
  * nih_tree_prev_full:
  * @tree: tree to iterate,
  * @node: node just visited,
  * @filter: filter function to test each node,
  * @data: data pointer to pass to @filter.
  *
  * 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.
  *
  * 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.
  *
  * Returns: previous in-order node within @tree or NULL if no further nodes.
  **/
 NihTree *
 nih_tree_prev_full (NihTree       *tree,
 		    NihTree       *node,
 		    NihTreeFilter  filter,
 		    void          *data)
 {
 	NihTree *prev;

 	nih_assert (tree != NULL);

 	if (node) {
 		prev = node;
 		if (VISIT (node->left)) {
 			node = node->left;
 		} else {
 			if (node == tree)
 				return NULL;

 			node = node->parent;
 		}
 	} else {
 		prev = tree->parent;
 		node = tree;
 	}

 	for (;;) {
 		NihTree *tmp = node;

 		if ((prev == node->parent) && VISIT (node->right)) {
 			node = node->right;
 		} else if (VISIT (node->left) && (prev == node->left)) {
 			if (node == tree)
 				return NULL;

 			node = node->parent;
 		} else if (VISIT (node)) {
 			return node;
 		} else {
 			return NULL;
 		}

 		prev = tmp;
 	}

 	return NULL;
 }


 /**
  * nih_tree_next_pre_full:
  * @tree: tree to iterate,
  * @node: node just visited,
  * @filter: filter function to test each node,
  * @data: data pointer to pass to @filter.
  *
  * 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.
  *
  * 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.
  *
  * Returns: next in-order node within @tree or NULL if no further nodes.
  **/
 NihTree *
 nih_tree_next_pre_full (NihTree       *tree,
 			NihTree       *node,
 			NihTreeFilter  filter,
 			void          *data)
 {
 	NihTree *prev;

 	nih_assert (tree != NULL);

 	if (node) {
 		prev = node;
 		if (VISIT (node->left)) {
 			return node->left;
 		} else if (VISIT (node->right)) {
 			return node->right;
 		} else {
 			if (node == tree)
 				return NULL;

 			node = node->parent;
 		}
 	} else if (VISIT (tree)) {
 		return tree;
 	} else {
 		return NULL;
 	}

 	for (;;) {
 		NihTree *tmp = node;

 		if ((prev != node->right) && VISIT (node->right)) {
 			return node->right;
 		} else {
 			if (node == tree)
 				return NULL;

 			node = node->parent;
 		}

 		prev = tmp;
 	}
 }

 /**
  * nih_tree_prev_pre_full:
  * @tree: tree to iterate,
  * @node: node just visited,
  * @filter: filter function to test each node,
  * @data: data pointer to pass to @filter.
  *
  * 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.
  *
  * 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.
  *
  * Returns: previous in-order node within @tree or NULL if no further nodes.
  **/
 NihTree *
 nih_tree_prev_pre_full (NihTree       *tree,
 			NihTree       *node,
 			NihTreeFilter  filter,
 			void          *data)
 {
 	NihTree *prev;

 	nih_assert (tree != NULL);

 	if (node) {
 		prev = node;
 		if (node == tree)
 			return NULL;

 		node = node->parent;
 	} else {
 		prev = tree->parent;
 		node = tree;
 	}

 	for (;;) {
 		NihTree *tmp = node;

 		if ((prev == node->parent) && VISIT (node->right)) {
 			node = node->right;
 		} else if ((prev != node->left) && VISIT (node->left)) {
 			node = node->left;
 		} else if (VISIT (node)) {
 			return node;
 		} else {
 			return NULL;
 		}

 		prev = tmp;
 	}
 }


 /**
  * nih_tree_next_post_full:
  * @tree: tree to iterate,
  * @node: node just visited,
  * @filter: filter function to test each node,
  * @data: data pointer to pass to @filter.
  *
  * 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.
  *
  * 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.
  *
  * Returns: next in-order node within @tree or NULL if no further nodes.
  **/
 NihTree *
 nih_tree_next_post_full (NihTree       *tree,
 			 NihTree       *node,
 			 NihTreeFilter  filter,
 			 void          *data)
 {
 	NihTree *prev;

 	nih_assert (tree != NULL);

 	if (node) {
 		prev = node;
 		if (node == tree)
 			return NULL;

 		node = node->parent;
 	} else {
 		prev = tree->parent;
 		node = tree;
 	}

 	for (;;) {
 		NihTree *tmp = node;

 		if ((prev == node->parent) && VISIT (node->left)) {
 			node = node->left;
 		} else if ((prev != node->right) && VISIT (node->right)) {
 			node = node->right;
 		} else if (VISIT (node)) {
 			return node;
 		} else {
 			return NULL;
 		}

 		prev = tmp;
 	}
 }

 /**
  * nih_tree_prev_post_full:
  * @tree: tree to iterate,
  * @node: node just visited,
  * @filter: filter function to test each node,
  * @data: data pointer to pass to @filter.
  *
  * 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.
  *
  * 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.
  *
  * Returns: previous in-order node within @tree or NULL if no further nodes.
  **/
 NihTree *
 nih_tree_prev_post_full (NihTree       *tree,
 			 NihTree       *node,
 			 NihTreeFilter  filter,
 			 void          *data)
 {
 	NihTree *prev;

 	nih_assert (tree != NULL);

 	if (node) {
 		prev = node;
 		if (VISIT (node->right)) {
 			return node->right;
 		} else if (VISIT (node->left)) {
 			return node->left;
 		} else {
 			if (node == tree)
 				return NULL;

 			node = node->parent;
 		}
 	} else if (VISIT (tree)) {
 		return tree;
 	} else {
 		return NULL;
 	}

 	for (;;) {
 		NihTree *tmp = node;

 		if ((prev != node->left) && VISIT (node->left)) {
 			return node->left;
 		} else {
 			if (node == tree)
 				return NULL;

 			node = node->parent;
 		}

 		prev = tmp;
 	}
 }
	/* libnih
	*
	* tree.c - generic binary tree implementation
	*
	* 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.
	*/

	#ifdef HAVE_CONFIG_H
	# include <config.h>
	#endif /* HAVE_CONFIG_H */


	#include <nih/macros.h>
	#include <nih/logging.h>
	#include <nih/alloc.h>

	#include "tree.h"


	/**
	* nih_tree_init:
	* @tree: tree node to be initialised.
	*
	* Initialise an already allocated tree node, once done it can be used
	* as the start of a new binary tree or added to an existing tree.
	**/
	void
	nih_tree_init (NihTree *tree)
	{
	nih_assert (tree != NULL);

	tree->parent = tree->left = tree->right = NULL;
	}

	/**
	* nih_tree_new:
	* @parent: parent object for new node.
	*
	* Allocates a new tree structure, usually used as the root of a new
	* binary tree. You may prefer to allocate the NihTree structure statically
	* and use nih_tree_init() to initialise it instead.
	*
	* The structure is allocated using nih_alloc() so can be used as a context
	* to other allocations.
	*
	* If @parent is not NULL, it should be a pointer to another object which
	* will be used as a parent for the returned tree node. When all parents
	* of the returned tree node are freed, the returned tree node will also be
	* freed.
	*
	* Returns: the new tree node or NULL if the allocation failed.
	**/
	NihTree *
	nih_tree_new (const void *parent)
	{
	NihTree *tree;

	tree = nih_new (parent, NihTree);
	if (! tree)
	return NULL;

	nih_tree_init (tree);

	nih_alloc_set_destructor (tree, nih_tree_destroy);

	return tree;
	}

	/**
	* nih_tree_entry_new:
	* @parent: parent object for new entry.
	*
	* Allocates a new tree entry structure, leaving the caller to set the
	* data of the entry.
	*
	* The structure is allocated using nih_alloc() so can be used as a context
	* to other allocations.
	*
	* If @parent is not NULL, it should be a pointer to another object which
	* will be used as a parent for the returned tree entry. When all parents
	* of the returned tree entry are freed, the returned tree entry will also be
	* freed.
	*
	* Returns: the new tree entry or NULL if the allocation failed.
	**/
	NihTreeEntry *
	nih_tree_entry_new (const void *parent)
	{
	NihTreeEntry *tree;

	tree = nih_new (parent, NihTreeEntry);
	if (! tree)
	return NULL;

	nih_tree_init (&tree->node);

	nih_alloc_set_destructor (tree, nih_tree_destroy);

	tree->data = NULL;

	return tree;
	}


	/**
	* nih_tree_add:
	* @tree: node in the destination tree,
	* @node: node to be added to the tree,
	* @where: where @node should be added.
	*
	* Adds @node to a new binary tree, either as a child of or, or replacing,
	* the existing node @tree. The exact position is determined by @where,
	* which may be NIH_TREE_LEFT or NIH_TREE_RIGHT to indicate that @node
	* should be a child of @tree or NIH_TREE_HERE to indicate that @node
	* should replace @tree.
	*
	* If @node is already in another tree it is removed so there is no need
	* to call nih_tree_remove() before this function. There is also no
	* requirement that the trees be different, so this can be used to reorder
	* a tree.
	*
	* Returns: node replaced by @node, normally NULL.
	**/
	NihTree *
	nih_tree_add (NihTree *tree,
	NihTree *node,
	NihTreeWhere where)
	{
	NihTree *replaced = NULL;

	nih_assert (tree != NULL);

	if (node)
	nih_tree_remove (node);

	if (where == NIH_TREE_LEFT) {
	replaced = tree->left;
	if (replaced)
	replaced->parent = NULL;

	tree->left = node;
	if (node)
	node->parent = tree;

	} else if (where == NIH_TREE_RIGHT) {
	replaced = tree->right;
	if (replaced)
	replaced->parent = NULL;

	tree->right = node;
	if (node)
	node->parent = tree;

	}

	return replaced;
	}


	/**
	* nih_tree_remove:
	* @node: node to be removed.
	*
	* Removes @node and its children from the containing tree. Neither the
	* node nor children are freed, and the children are not unlinked from the
	* node. Instead the node is returned so that it can be added to another
	* tree (through there's no need to call nih_tree_remove() first if you
	* wanted to do that) or used as the root of a new tree.
	*
	* Returns: @node as a root node.
	**/
	NihTree *
	nih_tree_remove (NihTree *node)
	{
	nih_assert (node != NULL);

	if (node->parent) {
	if (node->parent->left == node) {
	node->parent->left = NULL;
	} else if (node->parent->right == node) {
	node->parent->right = NULL;
	}

	node->parent = NULL;
	}

	return node;
	}

	/**
	* nih_tree_unlink:
	* @node: node to be removed.
	*
	* Removes @node from its containing tree, as nih_tree_remove() does, but
	* also unlinks the node's children from itself so that they don't have
	* a dangling pointer.
	*
	* Returns: @node.
	**/
	NihTree *
	nih_tree_unlink (NihTree *node)
	{
	nih_assert (node != NULL);

	nih_tree_remove (node);

	if (node->left)
	node->left->parent = NULL;

	if (node->right)
	node->right->parent = NULL;

	node->left = node->right = NULL;

	return node;
	}

	/**
	* nih_tree_destroy:
	* @node: node to be removed.
	*
	* Removes @node from its containing tree.
	*
	* Normally used or called from an nih_alloc() destructor so that the list
	* item is automatically removed from its containing list when freed.
	*
	* Returns: zero.
	**/
	int
	nih_tree_destroy (NihTree *node)
	{
	nih_assert (node != NULL);

	nih_tree_unlink (node);

	return 0;
	}


	/**
	* VISIT:
	* @_node: node to check.
	*
	* Macro to expand to check whether a node is set, and whether the filter is
	* either unset or says not to filter this node.
	**/
	#define VISIT(_node) ((_node) && ((! filter) \|\| (! filter (data, (_node)))))

	/**
	* nih_tree_next_full:
	* @tree: tree to iterate,
	* @node: node just visited,
	* @filter: filter function to test each node,
	* @data: data pointer to pass to @filter.
	*
	* 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.
	*
	* 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.
	*
	* Returns: next in-order node within @tree or NULL if no further nodes.
	**/
	NihTree *
	nih_tree_next_full (NihTree *tree,
	NihTree *node,
	NihTreeFilter filter,
	void *data)
	{
	NihTree *prev;

	nih_assert (tree != NULL);

	if (node) {
	prev = node;
	if (VISIT (node->right)) {
	node = node->right;
	} else {
	if (node == tree)
	return NULL;

	node = node->parent;
	}
	} else {
	prev = tree->parent;
	node = tree;
	}

	for (;;) {
	NihTree *tmp = node;

	if ((prev == node->parent) && VISIT (node->left)) {
	node = node->left;
	} else if (VISIT (node->right) && (prev == node->right)) {
	if (node == tree)
	return NULL;

	node = node->parent;
	} else if (VISIT (node)) {
	return node;
	} else {
	return NULL;
	}

	prev = tmp;
	}
	}

	/**
	* nih_tree_prev_full:
	* @tree: tree to iterate,
	* @node: node just visited,
	* @filter: filter function to test each node,
	* @data: data pointer to pass to @filter.
	*
	* 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.
	*
	* 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.
	*
	* Returns: previous in-order node within @tree or NULL if no further nodes.
	**/
	NihTree *
	nih_tree_prev_full (NihTree *tree,
	NihTree *node,
	NihTreeFilter filter,
	void *data)
	{
	NihTree *prev;

	nih_assert (tree != NULL);

	if (node) {
	prev = node;
	if (VISIT (node->left)) {
	node = node->left;
	} else {
	if (node == tree)
	return NULL;

	node = node->parent;
	}
	} else {
	prev = tree->parent;
	node = tree;
	}

	for (;;) {
	NihTree *tmp = node;

	if ((prev == node->parent) && VISIT (node->right)) {
	node = node->right;
	} else if (VISIT (node->left) && (prev == node->left)) {
	if (node == tree)
	return NULL;

	node = node->parent;
	} else if (VISIT (node)) {
	return node;
	} else {
	return NULL;
	}

	prev = tmp;
	}

	return NULL;
	}


	/**
	* nih_tree_next_pre_full:
	* @tree: tree to iterate,
	* @node: node just visited,
	* @filter: filter function to test each node,
	* @data: data pointer to pass to @filter.
	*
	* 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.
	*
	* 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.
	*
	* Returns: next in-order node within @tree or NULL if no further nodes.
	**/
	NihTree *
	nih_tree_next_pre_full (NihTree *tree,
	NihTree *node,
	NihTreeFilter filter,
	void *data)
	{
	NihTree *prev;

	nih_assert (tree != NULL);

	if (node) {
	prev = node;
	if (VISIT (node->left)) {
	return node->left;
	} else if (VISIT (node->right)) {
	return node->right;
	} else {
	if (node == tree)
	return NULL;

	node = node->parent;
	}
	} else if (VISIT (tree)) {
	return tree;
	} else {
	return NULL;
	}

	for (;;) {
	NihTree *tmp = node;

	if ((prev != node->right) && VISIT (node->right)) {
	return node->right;
	} else {
	if (node == tree)
	return NULL;

	node = node->parent;
	}

	prev = tmp;
	}
	}

	/**
	* nih_tree_prev_pre_full:
	* @tree: tree to iterate,
	* @node: node just visited,
	* @filter: filter function to test each node,
	* @data: data pointer to pass to @filter.
	*
	* 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.
	*
	* 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.
	*
	* Returns: previous in-order node within @tree or NULL if no further nodes.
	**/
	NihTree *
	nih_tree_prev_pre_full (NihTree *tree,
	NihTree *node,
	NihTreeFilter filter,
	void *data)
	{
	NihTree *prev;

	nih_assert (tree != NULL);

	if (node) {
	prev = node;
	if (node == tree)
	return NULL;

	node = node->parent;
	} else {
	prev = tree->parent;
	node = tree;
	}

	for (;;) {
	NihTree *tmp = node;

	if ((prev == node->parent) && VISIT (node->right)) {
	node = node->right;
	} else if ((prev != node->left) && VISIT (node->left)) {
	node = node->left;
	} else if (VISIT (node)) {
	return node;
	} else {
	return NULL;
	}

	prev = tmp;
	}
	}


	/**
	* nih_tree_next_post_full:
	* @tree: tree to iterate,
	* @node: node just visited,
	* @filter: filter function to test each node,
	* @data: data pointer to pass to @filter.
	*
	* 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.
	*
	* 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.
	*
	* Returns: next in-order node within @tree or NULL if no further nodes.
	**/
	NihTree *
	nih_tree_next_post_full (NihTree *tree,
	NihTree *node,
	NihTreeFilter filter,
	void *data)
	{
	NihTree *prev;

	nih_assert (tree != NULL);

	if (node) {
	prev = node;
	if (node == tree)
	return NULL;

	node = node->parent;
	} else {
	prev = tree->parent;
	node = tree;
	}

	for (;;) {
	NihTree *tmp = node;

	if ((prev == node->parent) && VISIT (node->left)) {
	node = node->left;
	} else if ((prev != node->right) && VISIT (node->right)) {
	node = node->right;
	} else if (VISIT (node)) {
	return node;
	} else {
	return NULL;
	}

	prev = tmp;
	}
	}

	/**
	* nih_tree_prev_post_full:
	* @tree: tree to iterate,
	* @node: node just visited,
	* @filter: filter function to test each node,
	* @data: data pointer to pass to @filter.
	*
	* 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.
	*
	* 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.
	*
	* Returns: previous in-order node within @tree or NULL if no further nodes.
	**/
	NihTree *
	nih_tree_prev_post_full (NihTree *tree,
	NihTree *node,
	NihTreeFilter filter,
	void *data)
	{
	NihTree *prev;

	nih_assert (tree != NULL);

	if (node) {
	prev = node;
	if (VISIT (node->right)) {
	return node->right;
	} else if (VISIT (node->left)) {
	return node->left;
	} else {
	if (node == tree)
	return NULL;

	node = node->parent;
	}
	} else if (VISIT (tree)) {
	return tree;
	} else {
	return NULL;
	}

	for (;;) {
	NihTree *tmp = node;

	if ((prev != node->left) && VISIT (node->left)) {
	return node->left;
	} else {
	if (node == tree)
	return NULL;

	node = node->parent;
	}

	prev = tmp;
	}
	}