Blender
V3.3
|
Go to the source code of this file.
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.
|
static |
Definition at line 284 of file DLRB_tree.c.
Referenced by insert_check_2(), and insert_check_3().
|
static |
|
static |
Definition at line 307 of file DLRB_tree.c.
References get_sibling(), node, and NULL.
Referenced by insert_check_2().
|
static |
Definition at line 414 of file DLRB_tree.c.
References DLRBT_BLACK, insert_check_2(), node, NULL, and tree.
Referenced by BLI_dlrbTree_add(), BLI_dlrbTree_insert(), and insert_check_2().
|
static |
Definition at line 428 of file DLRB_tree.c.
References DLRBT_BLACK, DLRBT_RED, get_grandparent(), get_uncle(), insert_check_1(), insert_check_3(), node, tree, and DLRBT_Node::tree_col.
Referenced by insert_check_1().
|
static |
Definition at line 463 of file DLRB_tree.c.
References DLRBT_BLACK, DLRBT_RED, get_grandparent(), DLRBT_Node::left, node, DLRBT_Node::right, rotate_left(), rotate_right(), tree, and DLRBT_Node::tree_col.
Referenced by insert_check_2().
|
static |
Definition at line 82 of file DLRB_tree.c.
References BLI_addtail(), node, NULL, and tree.
Referenced by BLI_dlrbTree_linkedlist_sync().
|
static |
Definition at line 32 of file DLRB_tree.c.
Referenced by BLI_dlrbTree_free().
|
static |
Definition at line 322 of file DLRB_tree.c.
References DLRBT_Node::left, NULL, DLRBT_Node::parent, DLRBT_Node::right, and tree.
Referenced by insert_check_3().
|
static |
Definition at line 363 of file DLRB_tree.c.
References DLRBT_Node::left, NULL, DLRBT_Node::parent, DLRBT_Node::right, and tree.
Referenced by insert_check_3().