/*****************************************************************************\
* xtree.h - functions used for tree data structure manament
*****************************************************************************
* Copyright (C) 2012 CEA/DAM/DIF
*
* This file is part of Slurm, a resource management program.
* For details, see .
* Please also read the included file: DISCLAIMER.
*
* Slurm is free software; you can redistribute it and/or modify it under
* the terms of the GNU General Public License as published by the Free
* Software Foundation; either version 2 of the License, or (at your option)
* any later version.
*
* In addition, as a special exception, the copyright holders give permission
* to link the code of portions of this program with the OpenSSL library under
* certain conditions as described in each individual source file, and
* distribute linked combinations including the two. You must obey the GNU
* General Public License in all respects for all of the code used other than
* OpenSSL. If you modify file(s) with this exception, you may extend this
* exception to your version of the file(s), but you are not obligated to do
* so. If you do not wish to do so, delete this exception statement from your
* version. If you delete this exception statement from all source files in
* the program, then also delete it here.
*
* Slurm is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
* details.
*
* You should have received a copy of the GNU General Public License along
* with Slurm; if not, write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
\*****************************************************************************/
#ifndef __XTREE_O7S7VY_INC__
#define __XTREE_O7S7VY_INC__
#include
/**
* The root node's parent must always be NULL (or browsing algorithm which
* stops at root when going up, will either crash or go to an infinite loop).
*/
typedef struct xtree_node_st {
void* data; /* data of the node */
struct xtree_node_st* parent; /* parent node, level up */
struct xtree_node_st* start; /* first node, level below */
struct xtree_node_st* end; /* last node, level below */
struct xtree_node_st* next; /* next node, same level */
struct xtree_node_st* previous; /* previous node, same level */
} xtree_node_t;
/* function prototype to deallocate data stored in tree nodes */
typedef void (*xtree_free_data_function_t)(xtree_node_t* node);
typedef struct xtree_st {
xtree_node_t* root; /* root node of the tree */
xtree_free_data_function_t free; /* frees nodes data or null */
uint32_t count; /* always: number of nodes */
uint32_t depth; /* cached depth */
uint32_t state; /* see XTREE_STATE_* */
} xtree_t;
/* free a complete tree whatever the `tree` entry point, it can be a leaf for
* example.
*
* The tree itself is freed but the `xtree_t` structure is not freed (since it
* can be stored on the stack).
*
* During freeing operation the tree is in a invalid state.
*
* @param tree is the tree entry point.
*/
void xtree_free(xtree_t* tree);
/**
* initialize a xtree_t structure with an empty tree
*
* @param freefunc is the function which will be used to free data associated
* with tree's nodes or NULL, freefunc must only desallocate
* node->data not the node itself, node is passed as a
* parameter if the user wants to do some processing according
* to the being-to-be-freed address of the node.
* @param tree is the structure to initialize
*
*/
void xtree_init(xtree_t* tree, xtree_free_data_function_t freefunc);
/**
* Sets the functions which will be used to free data member for each node or
* NULL to disable freeing. This function should not be used if nodes have
* already been added to the tree.
* @param freefunc is the freeing function.
*/
void xtree_set_freefunc(xtree_t* tree, xtree_free_data_function_t freefunc);
#define XTREE_STATE_DEPTHCACHED 1
#define XTREE_PREPEND 1 /** append to child list */
#define XTREE_APPEND 2 /** prepend to child list */
#define XTREE_REFRESH_DEPTH 4 /** default: don't refresh at insertion */
/** convenient function to get the parent of a node */
xtree_node_t* xtree_get_parent(xtree_t* tree, xtree_node_t* node);
#define xtree_node_get_data(node) ((node) ? (node)->data : NULL)
#define xtree_get_root(tree) ((tree) ? (tree)->root : NULL)
/** convenient function to get node count
* @returns the count of node inside the tree, constant time, or UINT32_MAX
* if tree is NULL.
*/
uint32_t xtree_get_count(xtree_t* tree);
/** Add a child to a node of a tree.
* @param tree the tree to manage, `parent` belongs to it.
* @param parent is the node where to add a child to.
* @param data is the data member associated with the new child.
* @param flags is a combination of the following :
* XTREE_APPEND: add the new node after `node` (mutually exclusive with
* PREPEND);
* XTREE_PREPEND: add the new node before `node` (mutually exclusive with
* APPEND);
* XTREE_REFRESH_DEPTH: refresh the cached depth of the tree.
* @returns the new child node added or NULL if parent is NULL but tree has
* root node. This function assumes a flag is given or abort o/w.
*/
xtree_node_t* xtree_add_child(xtree_t* tree,
xtree_node_t* parent,
void* data,
uint8_t flags);
/** Add a sibling to a node.
* @param tree is the tree to manage, NULL tree is illegal.
* @param node is the node next to which the new node should be added. When
* node is null, the function has the same behaviour as xtree_add_child.
* @param data is the data associated with the new node being added.
* @param flags is a combination of the following :
* XTREE_APPEND: add the new node after `node` (mutually exclusive with
* PREPEND);
* XTREE_PREPEND: add the new node before `node` (mutually exclusive with
* APPEND);
* XTREE_REFRESH_DEPTH: refresh the cached depth of the tree.
* @returns the new child node added or NULL for illegal parameter.
*/
xtree_node_t* xtree_add_sibling(xtree_t* tree,
xtree_node_t* node,
void* data,
uint8_t flags);
/** Calculate a tree depth by calling xtree_walk to browse the tree.
* This function browse the complete tree to determine the greatest depth of
* the tree.
* @param tree the tree to calculate depth from.
* @returns the depth of a given tree, a return value of 0 means the tree has
* no nodes, even not a root node, it is an empty tree.
*/
uint32_t xtree_depth_const(const xtree_t* tree);
/** Calculate depth starting from node (call xtree_walk).
* @param tree the tree to calculate depth from.
* @param node the starting point for calculating depth.
*/
uint32_t xtree_depth_const_node(const xtree_t* tree, const xtree_node_t* node);
/** Calculate a tree depth, caching its result inside the tree (call
* xtree_walk).
* @see xtree_depth_const
*/
uint32_t xtree_depth(xtree_t* tree);
/** Calculate tree depth with xtree_depth and cache it.
* @param tree is the tree to refresh.
*/
void xtree_refresh_depth(xtree_t* tree);
/** Convenient function which go upward to the root node to calculate node
* depth passed in argument.
*/
uint32_t xtree_node_depth(const xtree_node_t* node);
/** see function prototype for xtree_walk for description */
#define XTREE_PREORDER 1
#define XTREE_INORDER 2
#define XTREE_ENDORDER 4
#define XTREE_LEAF 8
#define XTREE_GROWING 16
#define XTREE_LEVEL_MAX UINT32_MAX
/** function prototype for walking through tree.
*
* @param node is the current node being parsed.
* @param which informs which visit is being done on the node,
* XTREE_PREORDER, XTREE_INORDER, XTREE_ENDORDER indicates this node
* is being visited before visiting the children, between visit of
* each children (if more than one), and after visiting the children.
* XTREE_LEAF indicates the node being visited is a leaf and receive
* consequently only one visit.
*
* XTREE_GROWING is called before any other calls, allowing a node to
* add childs.
*
* @param level is the current level, 0 being the root node.
* @param arg is the data assigned to xtree_walk then calling it.
* @returns 0 to indicate that xtree_walk do not need to continue to go
* through the tree, nonzero value continue the browsing.
*/
typedef uint8_t (*xtree_walk_function_t)(xtree_node_t* node,
uint8_t which,
uint32_t level,
void* arg);
/** Browse the tree depth-first, left-to-right. It mimics the C twalk
* function.
*
* You should not modify tree structure during traversal, since it can cause
* browsing errors or crash.
*
* @param tree is the tree you want to browse.
* @param node is the starting point or NULL (same as tree->root) to begin
* the traversal.
* @param min_level is the minimum level required to execute the action
* function, minimum being root node (=0).
* @param max_level is the maximum level to browse, the traversal's goes up
* again reaching this point, maximum being UINT32_MAX for
* all the tree's depth.
* @param action is the user function to execute for each node. See the
* typedef documentation.
* @param arg is the user data to pass unmodified to the user function.
* @returns the lastest node for which action was aborted or NULL.
*/
xtree_node_t* xtree_walk(xtree_t* tree,
xtree_node_t* node,
uint32_t min_level,
uint32_t max_level,
xtree_walk_function_t action,
void* arg);
/** @see xtree_find */
typedef uint8_t (*xtree_find_compare_t)(const void* node_data,
const void* arg);
/** Convenient function which calls xtree_walk to find a node according to
* a compare function.
*
* @param tree is the tree to search through.
* @param compare is a function returning 0 when the element correspond to
* search criterias, this function takes node_data for each
* node as first argument and arg as its second argument.
* @param arg is a function argument which can be the key or whatever data
* the user function needs to find the searched element.
* @returns the found node or NULL.
*/
xtree_node_t* xtree_find(xtree_t* tree,
xtree_find_compare_t compare,
const void* arg);
/** Deletes a node from the tree. You can use xtree_find or xtree_walk to
* find the wanted node. This function frees the node data thanks to the
* setted freefunc function of the tree. And recursively frees node childs
* too.
*
* @param tree is the tree to manage.
* @param node is the node to remove.
* @returns the parent node of the deleted node or NULL if bad argument/tree
* or the node was the tree's root node.
*/
xtree_node_t* xtree_delete(xtree_t* tree, xtree_node_t* node);
/** Gets recursive parents list from a node or NULL for bad tree/parameters
* or root node.
* User is responsible for `xfree`'ing the returned list.
* Parents lists starts from node's parent to root.
*
* @param tree the managed tree.
* @param node the node to start finding parents (not included itself in the
* list).
* @param size will be modified according to the number of parents in the
* returned list if the return value is not null.
* @returns the `xmalloc`ed parents array or NULL. Although size contains the
* array number of elements, the array is null terminated.
*/
xtree_node_t** xtree_get_parents(xtree_t* tree,
xtree_node_t* node,
uint32_t* size);
/** Get common ancestor of all given nodes.
* Example: 1 -> 2 -> 7, common ancestor of 2 and 7 is 1.
*
* @param tree is the managed tree.
* @param nodes is a node table which should have a common ancestor, an
* optionnal null node ends the list, else list stops at the
* (size - 1)th element.
* @param size is the number of elements the node table has, can be greather
* than the number of actual elements if list is null terminated
* (such as the UINT32_MAX value).
* @returns the common ancestor of all nodes or NULL if no such ancestors
* exists (if root node is listed, returns null since root node has
* no ancestor).
*/
xtree_node_t* xtree_common(xtree_t* tree,
const xtree_node_t* const* nodes,
uint32_t size);
/** Get recursive list of leaves starting from node.
* User is responsible for `xfree`'ing the returned list.
*
* @param tree the managed tree.
* @param node the node to start from.
* @param size will be modified according to the number of leaves in the
* retured list if the return value is not null.
* @returns the `xmalloc`ed leaves array starting from node or NULL if bogus
* tree or bad parameters. Although size contains the
* array number of elements, the array is null terminated.
*/
xtree_node_t** xtree_get_leaves(xtree_t* tree,
xtree_node_t* node,
uint32_t* size);
#endif