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_Tree *	BLI_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_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)
static DLRBT_Node *	get_grandparent (DLRBT_Node *node)
static DLRBT_Node *	get_sibling (DLRBT_Node *node)
static DLRBT_Node *	get_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_Node *	BLI_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 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.

get_grandparent()

static DLRBT_Node * get_grandparent ( DLRBT_Node * node )

static

Definition at line 285 of file DLRB_tree.c.

References NULL, and DLRBT_Node::parent.

Referenced by insert_check_2(), and insert_check_3().

get_sibling()

static DLRBT_Node * get_sibling ( DLRBT_Node * node )

static

Definition at line 294 of file DLRB_tree.c.

References DLRBT_Node::left, NULL, DLRBT_Node::parent, and DLRBT_Node::right.

Referenced by get_uncle().

get_uncle()

static DLRBT_Node * get_uncle ( DLRBT_Node * node )

static

Definition at line 308 of file DLRB_tree.c.

References get_sibling(), 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 415 of file DLRB_tree.c.

References DLRBT_BLACK, insert_check_2(), 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

Definition at line 429 of file DLRB_tree.c.

References DLRBT_BLACK, DLRBT_RED, get_grandparent(), get_uncle(), insert_check_1(), insert_check_3(), tree, and DLRBT_Node::tree_col.

Referenced by insert_check_1().

insert_check_3()

static void insert_check_3 ( DLRBT_Tree * tree, DLRBT_Node * node )

static

Definition at line 464 of file DLRB_tree.c.

References DLRBT_BLACK, DLRBT_RED, get_grandparent(), DLRBT_Node::left, DLRBT_Node::right, rotate_left(), rotate_right(), tree, and DLRBT_Node::tree_col.

Referenced by insert_check_2().

linkedlist_sync_add_node()

static void linkedlist_sync_add_node ( DLRBT_Tree * tree, DLRBT_Node * node )

static

Definition at line 83 of file DLRB_tree.c.

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

Referenced by BLI_dlrbTree_linkedlist_sync(), and linkedlist_sync_add_node().

recursive_tree_free_nodes()

static void recursive_tree_free_nodes ( DLRBT_Node * node, DLRBT_NFree_FP free_cb )

static

Definition at line 33 of file DLRB_tree.c.

References NULL, and recursive_tree_free_nodes().

Referenced by BLI_dlrbTree_free(), and recursive_tree_free_nodes().

rotate_left()

static void rotate_left ( DLRBT_Tree * tree, DLRBT_Node * root )

static

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

References DLRBT_Node::left, NULL, DLRBT_Node::parent, DLRBT_Node::right, and tree.

Referenced by insert_check_3().