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

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.
data	pointer to the relevant data or values stored in the bit-pattern. Dependent on the function.

Definition at line 71 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 77 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 91 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.
data	Pointer to the relevant data or values stored in the bit-pattern. Dependent on the function.

Definition at line 85 of file BLI_dlrbTree.h.

◆ DLRBT_Tree

typedef struct DLRBT_Tree DLRBT_Tree

The Tree Data.

◆ eDLRBT_Colors

typedef enum eDLRBT_Colors eDLRBT_Colors

Red/Black defines for tree_col.

Enumeration Type Documentation

◆ eDLRBT_Colors

enum eDLRBT_Colors

Red/Black defines for tree_col.

Enumerator
DLRBT_BLACK
DLRBT_RED

Definition at line 42 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 527 of file DLRB_tree.c.

References BLI_dlrbTree_search(), DLRBT_RED, insert_check_1(), DLRBT_Node::left, node, NULL, DLRBT_Node::parent, DLRBT_Node::right, and tree.

◆ 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 275 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 50 of file DLRB_tree.c.

References BLI_freelistN(), BLI_listbase_clear(), LISTBASE_FOREACH_MUTABLE, NULL, recursive_tree_free_nodes(), and tree.

Referenced by update_cache_free().

◆ BLI_dlrbTree_init()

void BLI_dlrbTree_init ( DLRBT_Tree * tree )

Initializes some given trees. Just zero out the pointers used.

Definition at line 23 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 511 of file DLRB_tree.c.

References DLRBT_RED, insert_check_1(), 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 104 of file DLRB_tree.c.

References linkedlist_sync_add_node(), NULL, and tree.

◆ BLI_dlrbTree_new()

DLRBT_Tree * BLI_dlrbTree_new ( void )

Create a new tree, and initialize as necessary.

Definition at line 17 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 121 of file DLRB_tree.c.

References 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 168 of file DLRB_tree.c.

References 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 245 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 215 of file DLRB_tree.c.

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

Classes

Typedefs

Functions

Base Structs

Detailed Description

Typedef Documentation

◆ DLRBT_Comparator_FP

◆ DLRBT_NAlloc_FP

◆ DLRBT_NFree_FP

◆ DLRBT_Node

◆ DLRBT_NUpdate_FP

◆ DLRBT_Tree

◆ eDLRBT_Colors

Enumeration Type Documentation

◆ eDLRBT_Colors

Function Documentation

◆ BLI_dlrbTree_add()

◆ BLI_dlrbTree_contains()

◆ BLI_dlrbTree_free()

◆ BLI_dlrbTree_init()

◆ BLI_dlrbTree_insert()

◆ BLI_dlrbTree_linkedlist_sync()

◆ BLI_dlrbTree_new()

◆ BLI_dlrbTree_search()

◆ BLI_dlrbTree_search_exact()

◆ BLI_dlrbTree_search_next()

◆ BLI_dlrbTree_search_prev()