Blender  V3.3
Classes
BLI_dlrbTree.h File Reference

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_TreeBLI_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_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)
 
Node Operations (Managed)
DLRBT_NodeBLI_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
 

Detailed Description

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.

Typedef Documentation

◆ DLRBT_Comparator_FP

typedef short(* DLRBT_Comparator_FP) (void *node, void *data)

Return -1, 0, 1 for whether the given data is less than, equal to, or greater than the given node.

Parameters
node<DLRBT_Node> the node to compare to.
datapointer to the relevant data or values stored in the bit-pattern. Dependent on the function.

Definition at line 70 of file BLI_dlrbTree.h.

◆ DLRBT_NAlloc_FP

typedef DLRBT_Node*(* DLRBT_NAlloc_FP) (void *data)

Return a new node instance wrapping the given data

  • data: Pointer to the relevant data to create a subclass of node from.

Definition at line 76 of file BLI_dlrbTree.h.

◆ DLRBT_NFree_FP

typedef void(* DLRBT_NFree_FP) (void *node)

Free a node and the wrapped data.

Parameters
node<DLRBT_Node> the node to free.

Definition at line 90 of file BLI_dlrbTree.h.

◆ DLRBT_Node

typedef struct DLRBT_Node DLRBT_Node

Basic Layout for a Node.

◆ DLRBT_NUpdate_FP

typedef void(* DLRBT_NUpdate_FP) (void *node, void *data)

Update an existing node instance accordingly to be in sync with the given data.

Parameters
node<DLRBT_Node> the node to update.
dataPointer to the relevant data or values stored in the bit-pattern. Dependent on the function.

Definition at line 84 of file BLI_dlrbTree.h.

◆ DLRBT_Tree

typedef struct DLRBT_Tree DLRBT_Tree

The Tree Data.

◆ eDLRBT_Colors

Red/Black defines for tree_col.

Enumeration Type Documentation

◆ eDLRBT_Colors

Red/Black defines for tree_col.

Enumerator
DLRBT_BLACK 
DLRBT_RED 

Definition at line 41 of file BLI_dlrbTree.h.

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.