/* 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; | |

} | |

} |