Blender
V3.3
|
Go to the source code of this file.
Classes | |
struct | DLRBT_Node |
struct | DLRBT_Tree |
Typedefs | |
Callback Types | |
typedef short(* | DLRBT_Comparator_FP) (void *node, void *data) |
typedef DLRBT_Node *(* | DLRBT_NAlloc_FP) (void *data) |
typedef void(* | DLRBT_NUpdate_FP) (void *node, void *data) |
typedef void(* | DLRBT_NFree_FP) (void *node) |
Functions | |
ADT Management | |
DLRBT_Tree * | BLI_dlrbTree_new (void) |
void | BLI_dlrbTree_init (DLRBT_Tree *tree) |
void | BLI_dlrbTree_free (DLRBT_Tree *tree, DLRBT_NFree_FP free_cb) |
void | BLI_dlrbTree_linkedlist_sync (DLRBT_Tree *tree) |
Tree Searching Utilities | |
DLRBT_Node * | BLI_dlrbTree_search (const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) |
DLRBT_Node * | BLI_dlrbTree_search_exact (const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) |
DLRBT_Node * | BLI_dlrbTree_search_prev (const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) |
DLRBT_Node * | BLI_dlrbTree_search_next (const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) |
short | BLI_dlrbTree_contains (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data) |
Node Operations (Managed) | |
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) |
Node Operations (Manual) | |
Remove the given element from the tree and balance again. 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. | |
void | BLI_dlrbTree_insert (DLRBT_Tree *tree, DLRBT_Node *node) |
Base Structs | |
enum | eDLRBT_Colors { DLRBT_BLACK = 0 , DLRBT_RED } |
typedef struct DLRBT_Node | DLRBT_Node |
typedef enum eDLRBT_Colors | eDLRBT_Colors |
typedef struct DLRBT_Tree | DLRBT_Tree |
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.
Definition in file BLI_dlrbTree.h.
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. |
Definition at line 70 of file BLI_dlrbTree.h.
typedef DLRBT_Node*(* DLRBT_NAlloc_FP) (void *data) |
Return a new node instance wrapping the given data
Definition at line 76 of file BLI_dlrbTree.h.
Free a node and the wrapped data.
node | <DLRBT_Node> the node to free. |
Definition at line 90 of file BLI_dlrbTree.h.
typedef struct DLRBT_Node DLRBT_Node |
Basic Layout for a Node.
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. |
Definition at line 84 of file BLI_dlrbTree.h.
typedef struct DLRBT_Tree DLRBT_Tree |
The Tree Data.
typedef enum eDLRBT_Colors eDLRBT_Colors |
Red/Black defines for tree_col.
enum eDLRBT_Colors |
Red/Black defines for tree_col.
Enumerator | |
---|---|
DLRBT_BLACK | |
DLRBT_RED |
Definition at line 41 of file BLI_dlrbTree.h.
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 | ||
) |
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.
Definition at line 526 of file DLRB_tree.c.
References BLI_dlrbTree_search(), data, DLRBT_RED, insert_check_1(), DLRBT_Node::left, node, NULL, DLRBT_Node::right, tree, and update_cb().
Referenced by update_cache_node_create_ex().
short BLI_dlrbTree_contains | ( | DLRBT_Tree * | tree, |
DLRBT_Comparator_FP | cmp_cb, | ||
void * | search_data | ||
) |
Check whether there is a node matching the requested node.
Definition at line 274 of file DLRB_tree.c.
References BLI_dlrbTree_search_exact(), NULL, and tree.
void BLI_dlrbTree_free | ( | DLRBT_Tree * | tree, |
DLRBT_NFree_FP | free_cb | ||
) |
Free the given tree's data but not the tree itself.
Definition at line 49 of file DLRB_tree.c.
References BLI_freelistN(), BLI_listbase_clear(), LISTBASE_FOREACH_MUTABLE, node, NULL, recursive_tree_free_nodes(), and tree.
Referenced by cache_node_update(), update_cache_free(), and update_cache_node_create_ex().
void BLI_dlrbTree_init | ( | DLRBT_Tree * | tree | ) |
Initializes some given trees. Just zero out the pointers used.
Definition at line 22 of file DLRB_tree.c.
void BLI_dlrbTree_insert | ( | DLRBT_Tree * | tree, |
DLRBT_Node * | node | ||
) |
Balance the tree after the given node has been added to it (using custom code, in the Binary Tree way).
Definition at line 510 of file DLRB_tree.c.
References DLRBT_RED, insert_check_1(), node, NULL, and tree.
void BLI_dlrbTree_linkedlist_sync | ( | DLRBT_Tree * | tree | ) |
Make sure the tree's Double-Linked list representation is valid.
Definition at line 103 of file DLRB_tree.c.
References linkedlist_sync_add_node(), NULL, and tree.
Referenced by update_cache_node_create_ex().
DLRBT_Tree* BLI_dlrbTree_new | ( | void | ) |
Create a new tree, and initialize as necessary.
Definition at line 16 of file DLRB_tree.c.
References MEM_callocN.
Referenced by update_cache_alloc().
DLRBT_Node* BLI_dlrbTree_search | ( | const DLRBT_Tree * | tree, |
DLRBT_Comparator_FP | cmp_cb, | ||
void * | search_data | ||
) |
Find the node which matches or is the closest to the requested node.
Definition at line 120 of file DLRB_tree.c.
References if(), node, NULL, and tree.
Referenced by BLI_dlrbTree_add(), BLI_dlrbTree_search_next(), and BLI_dlrbTree_search_prev().
DLRBT_Node* BLI_dlrbTree_search_exact | ( | const DLRBT_Tree * | tree, |
DLRBT_Comparator_FP | cmp_cb, | ||
void * | search_data | ||
) |
Find the node which exactly matches the required data.
Definition at line 167 of file DLRB_tree.c.
References if(), node, NULL, and tree.
Referenced by BLI_dlrbTree_contains().
DLRBT_Node* BLI_dlrbTree_search_next | ( | const DLRBT_Tree * | tree, |
DLRBT_Comparator_FP | cmp_cb, | ||
void * | search_data | ||
) |
Find the node which occurs immediately after the best matching node.
Definition at line 244 of file DLRB_tree.c.
References BLI_dlrbTree_search(), node, NULL, and tree.
DLRBT_Node* BLI_dlrbTree_search_prev | ( | const DLRBT_Tree * | tree, |
DLRBT_Comparator_FP | cmp_cb, | ||
void * | search_data | ||
) |
Find the node which occurs immediately before the best matching node.
Definition at line 214 of file DLRB_tree.c.
References BLI_dlrbTree_search(), node, NULL, and tree.