Blender  V3.3
Functions
DLRB_tree.c File Reference
#include "MEM_guardedalloc.h"
#include "BLI_dlrbTree.h"
#include "BLI_listbase.h"

Go to the source code of this file.

Functions

DLRBT_TreeBLI_dlrbTree_new (void)
 
void BLI_dlrbTree_init (DLRBT_Tree *tree)
 
static void recursive_tree_free_nodes (DLRBT_Node *node, DLRBT_NFree_FP free_cb)
 
void BLI_dlrbTree_free (DLRBT_Tree *tree, DLRBT_NFree_FP free_cb)
 
static void linkedlist_sync_add_node (DLRBT_Tree *tree, DLRBT_Node *node)
 
void BLI_dlrbTree_linkedlist_sync (DLRBT_Tree *tree)
 
DLRBT_NodeBLI_dlrbTree_search (const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
 
DLRBT_NodeBLI_dlrbTree_search_exact (const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
 
DLRBT_NodeBLI_dlrbTree_search_prev (const DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
 
DLRBT_NodeBLI_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)
 
static DLRBT_Nodeget_grandparent (DLRBT_Node *node)
 
static DLRBT_Nodeget_sibling (DLRBT_Node *node)
 
static DLRBT_Nodeget_uncle (DLRBT_Node *node)
 
static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root)
 
static void rotate_right (DLRBT_Tree *tree, DLRBT_Node *root)
 
static void insert_check_1 (DLRBT_Tree *tree, DLRBT_Node *node)
 
static void insert_check_2 (DLRBT_Tree *tree, DLRBT_Node *node)
 
static void insert_check_3 (DLRBT_Tree *tree, DLRBT_Node *node)
 
void BLI_dlrbTree_insert (DLRBT_Tree *tree, DLRBT_Node *node)
 
DLRBT_NodeBLI_dlrbTree_add (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data)
 

Function Documentation

◆ BLI_dlrbTree_add()

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.

Note
for duplicates, the update_cb is called (if available), and the existing node is returned.

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().

◆ BLI_dlrbTree_contains()

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.

◆ BLI_dlrbTree_free()

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().

◆ BLI_dlrbTree_init()

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.

References NULL, and tree.

◆ BLI_dlrbTree_insert()

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.

◆ BLI_dlrbTree_linkedlist_sync()

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().

◆ BLI_dlrbTree_new()

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().

◆ BLI_dlrbTree_search()

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().

◆ BLI_dlrbTree_search_exact()

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().

◆ BLI_dlrbTree_search_next()

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.

◆ BLI_dlrbTree_search_prev()

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.

◆ get_grandparent()

static DLRBT_Node* get_grandparent ( DLRBT_Node node)
static

Definition at line 284 of file DLRB_tree.c.

References node, and NULL.

Referenced by insert_check_2(), and insert_check_3().

◆ get_sibling()

static DLRBT_Node* get_sibling ( DLRBT_Node node)
static

Definition at line 293 of file DLRB_tree.c.

References node, and NULL.

Referenced by get_uncle().

◆ get_uncle()

static DLRBT_Node* get_uncle ( DLRBT_Node node)
static

Definition at line 307 of file DLRB_tree.c.

References get_sibling(), node, and NULL.

Referenced by insert_check_2().

◆ insert_check_1()

static void insert_check_1 ( DLRBT_Tree tree,
DLRBT_Node node 
)
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().

◆ insert_check_2()

static void insert_check_2 ( DLRBT_Tree tree,
DLRBT_Node node 
)
static

◆ insert_check_3()

static void insert_check_3 ( DLRBT_Tree tree,
DLRBT_Node node 
)
static

◆ linkedlist_sync_add_node()

static void linkedlist_sync_add_node ( DLRBT_Tree tree,
DLRBT_Node node 
)
static

Definition at line 82 of file DLRB_tree.c.

References BLI_addtail(), node, NULL, and tree.

Referenced by BLI_dlrbTree_linkedlist_sync().

◆ recursive_tree_free_nodes()

static void recursive_tree_free_nodes ( DLRBT_Node node,
DLRBT_NFree_FP  free_cb 
)
static

Definition at line 32 of file DLRB_tree.c.

References node, and NULL.

Referenced by BLI_dlrbTree_free().

◆ rotate_left()

static void rotate_left ( DLRBT_Tree tree,
DLRBT_Node root 
)
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().

◆ rotate_right()

static void rotate_right ( DLRBT_Tree tree,
DLRBT_Node root 
)
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().