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)
void	BLI_dlrbTree_free (DLRBT_Tree *tree)
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 (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
DLRBT_Node *	BLI_dlrbTree_search_exact (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
DLRBT_Node *	BLI_dlrbTree_search_prev (DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data)
DLRBT_Node *	BLI_dlrbTree_search_next (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
	)

Definition at line 545 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 add_bezt_to_keycolumns_list(), add_gpframe_to_keycolumns_list(), and add_masklay_to_keycolumns_list().

BLI_dlrbTree_contains()

short BLI_dlrbTree_contains	(	DLRBT_Tree *	tree,
		DLRBT_Comparator_FP	cmp_cb,
		void *	search_data
	)

Definition at line 287 of file DLRB_tree.c.

References BLI_dlrbTree_search_exact(), NULL, and tree.

BLI_dlrbTree_free()

void BLI_dlrbTree_free

(

DLRBT_Tree *

tree

)

Definition at line 66 of file DLRB_tree.c.

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

Referenced by actkeys_find_key_in_list_element(), animviz_calc_motionpaths(), draw_action_channel(), draw_agroup_channel(), draw_fcurve_channel(), draw_gpencil_channel(), draw_gpl_channel(), draw_masklay_channel(), draw_object_channel(), draw_scene_channel(), draw_summary_channel(), find_prev_next_keyframes(), keyframe_jump_exec(), motionpath_calculate_update_range(), motionpath_free_free_tree_data(), nla_action_draw_keyframes(), pose_propagate_get_boneHoldEndFrame(), pose_slide_exit(), and poselib_sanitize_exec().

BLI_dlrbTree_init()

void BLI_dlrbTree_init

(

DLRBT_Tree *

tree

)

Definition at line 40 of file DLRB_tree.c.

References NULL, and tree.

Referenced by actkeys_find_key_in_list_element(), animviz_calc_motionpaths(), draw_action_channel(), draw_agroup_channel(), draw_fcurve_channel(), draw_gpencil_channel(), draw_gpl_channel(), draw_masklay_channel(), draw_object_channel(), draw_scene_channel(), draw_summary_channel(), find_prev_next_keyframes(), keyframe_jump_exec(), motionpath_calculate_update_range(), nla_action_draw_keyframes(), pose_propagate_get_boneHoldEndFrame(), pose_slide_init(), and poselib_sanitize_exec().

BLI_dlrbTree_insert()

void BLI_dlrbTree_insert	(	DLRBT_Tree *	tree,
		DLRBT_Node *	node
	)

Definition at line 526 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

)

Definition at line 113 of file DLRB_tree.c.

References linkedlist_sync_add_node(), NULL, and tree.

Referenced by update_keyblocks().

BLI_dlrbTree_new()

DLRBT_Tree* BLI_dlrbTree_new

(

void

)

Definition at line 33 of file DLRB_tree.c.

References MEM_callocN.

BLI_dlrbTree_search()

DLRBT_Node* BLI_dlrbTree_search	(	DLRBT_Tree *	tree,
		DLRBT_Comparator_FP	cmp_cb,
		void *	search_data
	)

Definition at line 131 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	(	DLRBT_Tree *	tree,
		DLRBT_Comparator_FP	cmp_cb,
		void *	search_data
	)

Definition at line 177 of file DLRB_tree.c.

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

Referenced by add_bezt_to_keyblocks_list(), BLI_dlrbTree_contains(), motionpaths_calc_bake_targets(), pose_propagate_get_boneHoldEndFrame(), and pose_slide_invoke_common().

BLI_dlrbTree_search_next()

DLRBT_Node* BLI_dlrbTree_search_next	(	DLRBT_Tree *	tree,
		DLRBT_Comparator_FP	cmp_cb,
		void *	search_data
	)

Definition at line 256 of file DLRB_tree.c.

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

Referenced by find_prev_next_keyframes(), keyframe_jump_exec(), motionpath_get_next_keyframe(), pose_propagate_get_boneHoldEndFrame(), and pose_slide_invoke_common().

BLI_dlrbTree_search_prev()

DLRBT_Node* BLI_dlrbTree_search_prev	(	DLRBT_Tree *	tree,
		DLRBT_Comparator_FP	cmp_cb,
		void *	search_data
	)

Definition at line 225 of file DLRB_tree.c.

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

Referenced by find_prev_next_keyframes(), keyframe_jump_exec(), motionpath_get_prev_keyframe(), pose_propagate_get_boneHoldEndFrame(), and pose_slide_invoke_common().

get_grandparent()

static DLRBT_Node* get_grandparent ( DLRBT_Node *  node )

static

Definition at line 297 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 306 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 320 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 427 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

Definition at line 441 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().

insert_check_3()

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

static

Definition at line 476 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().

linkedlist_sync_add_node()

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

static

Definition at line 91 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 )

static

Definition at line 50 of file DLRB_tree.c.

References MEM_freeN, node, and NULL.

Referenced by BLI_dlrbTree_free().

rotate_left()

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

static

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

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

Referenced by insert_check_3().