diff options
Diffstat (limited to 'source/blender/blenlib/BLI_dlrbTree.h')
| -rw-r--r-- | source/blender/blenlib/BLI_dlrbTree.h | 138 |
1 files changed, 94 insertions, 44 deletions
diff --git a/source/blender/blenlib/BLI_dlrbTree.h b/source/blender/blenlib/BLI_dlrbTree.h index 03aab8d2895..72f18244d5b 100644 --- a/source/blender/blenlib/BLI_dlrbTree.h +++ b/source/blender/blenlib/BLI_dlrbTree.h @@ -21,23 +21,24 @@ /** \file * \ingroup bli - */ - -#ifdef __cplusplus -extern "C" { -#endif - -/* Double-Linked Red-Black Tree Implementation: + * + * Double-Linked Red-Black Tree Implementation: * * This is simply a Red-Black Tree implementation whose nodes can later * be arranged + retrieved as elements in a Double-Linked list (i.e. ListBase). * The Red-Black Tree implementation is based on the methods defined by Wikipedia. */ +#ifdef __cplusplus +extern "C" { +#endif + /* ********************************************** */ /* Data Types and Type Defines */ -/* Base Structs --------------------------------- */ +/* -------------------------------------------------------------------- */ +/** \name Base Structs + * \{ */ /* Basic Layout for a Node */ typedef struct DLRBT_Node { @@ -69,101 +70,150 @@ typedef struct DLRBT_Tree { void *root; /* this should be based on DLRBT_Node-s */ } DLRBT_Tree; -/* Callback Types --------------------------------- */ +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Callback Types + * \{ */ -/* Return -1, 0, 1 for whether the given data is less than, +/** + * Return -1, 0, 1 for whether the given data is less than, * equal to, or greater than the given node. - * - node: <DLRBT_Node> the node to compare to. - * - data: pointer to the relevant data or values stored in the bit-pattern. - * dependent on the function. + * \param node: <DLRBT_Node> the node to compare to. + * \param data: pointer to the relevant data or values stored in the bit-pattern. + * Dependent on the function. */ typedef short (*DLRBT_Comparator_FP)(void *node, void *data); -/* Return a new node instance wrapping the given data - * - data: Pointer to the relevant data to create a subclass of node from +/** + * Return a new node instance wrapping the given data + * - data: Pointer to the relevant data to create a subclass of node from. */ typedef DLRBT_Node *(*DLRBT_NAlloc_FP)(void *data); -/* Update an existing node instance accordingly to be in sync with the given data. - * - node: <DLRBT_Node> the node to update. - * - data: Pointer to the relevant data or values stored in the bit-pattern. - * dependent on the function. +/** + * Update an existing node instance accordingly to be in sync with the given data. + * \param node: <DLRBT_Node> the node to update. + * \param data: Pointer to the relevant data or values stored in the bit-pattern. + * Dependent on the function. */ typedef void (*DLRBT_NUpdate_FP)(void *node, void *data); /* ********************************************** */ /* Public API */ -/* ADT Management ------------------------------- */ +/** \} */ -/* Create a new tree, and initialize as necessary */ +/* -------------------------------------------------------------------- */ +/** \name ADT Management + * \{ */ + +/** + * Create a new tree, and initialize as necessary. + */ DLRBT_Tree *BLI_dlrbTree_new(void); -/* Initializes some given trees */ +/** + * Initializes some given trees. + * Just zero out the pointers used. + */ void BLI_dlrbTree_init(DLRBT_Tree *tree); -/* Free some tree */ +/** + * Free the given tree's data but not the tree itself. + */ void BLI_dlrbTree_free(DLRBT_Tree *tree); -/* Make sure the tree's Double-Linked list representation is valid */ +/** + * Make sure the tree's Double-Linked list representation is valid. + */ void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree); -/* Searching ------------------------------------ */ +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Tree Searching Utilities + * \{ */ -/* Find the node which matches or is the closest to the requested node */ +/** + * Find the node which matches or is the closest to the requested node. + */ DLRBT_Node *BLI_dlrbTree_search(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); -/* Find the node which exactly matches the required data */ +/** + * Find the node which exactly matches the required data. + */ DLRBT_Node *BLI_dlrbTree_search_exact(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); -/* Find the node which occurs immediately before the best matching node */ +/** + * Find the node which occurs immediately before the best matching node. + */ DLRBT_Node *BLI_dlrbTree_search_prev(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); -/* Find the node which occurs immediately after the best matching node */ +/** + * Find the node which occurs immediately after the best matching node. + */ DLRBT_Node *BLI_dlrbTree_search_next(const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); -/* Check whether there is a node matching the requested node */ +/** + * Check whether there is a node matching the requested node. + */ short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); -/* Node Operations (Managed) --------------------- */ -/* These methods automate the process of adding/removing nodes from the BST, - * using the supplied data and callbacks +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Node Operations (Managed) + * \{ */ + +/** + * These methods automate the process of adding/removing nodes from the BST, + * using the supplied data and callbacks. */ -/* Add the given data to the tree, and return the node added */ -/* NOTE: for duplicates, the update_cb is called (if available), - * and the existing node is returned. */ +/** + * Add the given data to the tree, and return the node added. + * \note for duplicates, the update_cb is called (if available), + * and the existing node is returned. + */ DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data); -/* Remove the given element from the tree and balance again */ -/* FIXME: this is not implemented yet... */ +/* FIXME: this is not implemented yet. */ +/** + * Remove the given element from the tree and balance again. + */ // void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node); -/* Node Operations (Manual) --------------------- */ -/* These methods require custom code for creating BST nodes and adding them to the +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Node Operations (Manual) + * + * These methods require custom code for creating BST nodes and adding them to the * tree in special ways, such that the node can then be balanced. * - * It is recommended that these methods are only used where the other method is too cumbersome... - */ + * It is recommended that these methods are only used where the other method is too cumbersome. + * \{ */ -/* Balance the tree after the given node has been added to it +/** + * Balance the tree after the given node has been added to it * (using custom code, in the Binary Tree way). */ void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node); -/* ********************************************** */ +/** \} */ #ifdef __cplusplus } |