The data structures and constants for red-black trees. More...

Collaboration diagram for Red-Black Trees:

Files
file	redblack.h

Data Structures
struct	bu_rb_list

struct	bu_rb_tree

struct	bu_rb_package

struct	bu_rb_node

Macros
#define	rbl_node rbl_u.rbl_n

#define	rbl_package rbl_u.rbl_p

#define	BU_RB_LIST_NULL ((struct bu_rb_list *) 0)

#define	BU_RB_LIST_INIT(_l, _m)

#define	BU_RB_LIST_INIT_CAPACITY 4

#define	BU_RB_TREE_NULL ((struct bu_rb_tree *) 0)

#define	BU_CK_RB_TREE(_rb) BU_CKMAG(_rb, BU_RB_TREE_MAGIC, "bu_rb_tree")

#define	BU_RB_TREE_INIT(_rb)

#define	BU_RB_TREE_INIT_ZERO

#define	BU_RB_TREE_IS_INITIALIZED(_rb) (((struct bu_rb_tree *)(_rb) != BU_RB_TREE_NULL) && LIKELY((_rb)->rbt_magic == BU_RB_TREE_MAGIC))

#define	BU_RB_DEBUG_INSERT 0x00000001

#define	BU_RB_DEBUG_UNIQ 0x00000002

#define	BU_RB_DEBUG_ROTATE 0x00000004

#define	BU_RB_DEBUG_OS 0x00000008

#define	BU_RB_DEBUG_DELETE 0x00000010

#define	BU_RB_PKG_NULL ((struct bu_rb_package *) 0)

#define	BU_RB_NODE_NULL ((struct bu_rb_node *) 0)

#define	SENSE_MIN 0

#define	SENSE_MAX 1

#define	bu_rb_min(t, o) bu_rb_extreme((t), (o), SENSE_MIN)

#define	bu_rb_max(t, o) bu_rb_extreme((t), (o), SENSE_MAX)

#define	bu_rb_pred(t, o) bu_rb_neighbor((t), (o), SENSE_MIN)

#define	bu_rb_succ(t, o) bu_rb_neighbor((t), (o), SENSE_MAX)

#define	bu_rb_delete1(t) bu_rb_delete((t), 0)

#define	bu_rb_curr1(t) bu_rb_curr((t), 0)

#define	BU_RB_RETAIN_DATA ((void ()(void data)) 0)

#define	bu_rb_free1(t, f)

#define	bu_rb_is_uniq1(t) bu_rb_is_uniq((t), 0)

#define	bu_rb_uniq_on1(t) bu_rb_uniq_on((t), 0)

#define	bu_rb_uniq_off1(t) bu_rb_uniq_off((t), 0)

#define	bu_rb_rank1(t) bu_rb_rank1((t), 0)

#define	bu_rb_select1(t, k) bu_rb_select((t), 0, (k))

#define	bu_rb_search1(t, d) bu_rb_search((t), 0, (d))

#define	bu_rb_walk1(t, v, d) bu_rb_walk((t), 0, (v), (d))

#define	BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG(_func) ((void (*)(void))_func)

#define	BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC(_func) ((void ()(struct bu_rb_node , int))_func)

#define	BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC(_func) ((void ()(void , int))_func)

#define	BU_RB_WALK_FUNC_CAST_AS_FUNC_FUNC(_func) ((void ()(struct bu_rb_node , int, void (*)(void), int))_func)

#define	BU_RB_WALK_FUNC_NODE_DECL(_func) void (_func)(struct bu_rb_node , int)

#define	BU_RB_WALK_FUNC_DATA_DECL(_func) void (_func)(void , int)

#define	BU_RB_WALK_FUNC_FUNC_DECL(_func) void (_func)(struct bu_rb_node , int, void (*)(void), int)

Typedefs
typedef struct bu_rb_tree	bu_rb_tree_t

typedef int(*	bu_rb_cmp_t) (const void , const void )
	Routines to create a red-black tree. More...

Enumerations
enum	BU_RB_WALK_ORDER { BU_RB_WALK_PREORDER , BU_RB_WALK_INORDER , BU_RB_WALK_POSTORDER }

Functions
struct bu_rb_tree *	bu_rb_create (const char description, int nm_orders, bu_rb_cmp_t compare_funcs)

void	bu_rb_delete (struct bu_rb_tree *tree, int order)
	Routines to delete a node from a red-black tree. More...

void	bu_rb_diagnose_tree (struct bu_rb_tree *tree, int order, int trav_type)
	Diagnostic routines for red-black tree maintenance. More...

void	bu_rb_summarize_tree (struct bu_rb_tree *tree)

void *	bu_rb_extreme (struct bu_rb_tree *tree, int order, int sense)
	Routines to extract mins, maxes, adjacent, and current nodes from a red-black tree. More...

void *	bu_rb_neighbor (struct bu_rb_tree *tree, int order, int sense)

void *	bu_rb_curr (struct bu_rb_tree *tree, int order)

void	bu_rb_free (struct bu_rb_tree tree, void(free_data)(void *data))
	Routines to free a red-black tree. More...

int	bu_rb_insert (struct bu_rb_tree tree, void data)
	Routines to insert into a red-black tree. More...

int	bu_rb_is_uniq (struct bu_rb_tree *tree, int order)

void	bu_rb_set_uniqv (struct bu_rb_tree *tree, bitv_t vec)

void	bu_rb_uniq_all_off (struct bu_rb_tree *tree)

void	bu_rb_uniq_all_on (struct bu_rb_tree *tree)

int	bu_rb_uniq_on (struct bu_rb_tree *tree, int order)

int	bu_rb_uniq_off (struct bu_rb_tree *tree, int order)

int	bu_rb_rank (struct bu_rb_tree *tree, int order)
	Routines to support order-statistic operations for a red-black tree. More...

void *	bu_rb_select (struct bu_rb_tree *tree, int order, int k)

void *	bu_rb_search (struct bu_rb_tree tree, int order, void data)
	Routines to search for a node in a red-black tree. More...

void	bu_rb_walk (struct bu_rb_tree tree, int order, void(visit)(void), int trav_type)
	Routines for traversal of red-black trees. More...

Detailed Description

The data structures and constants for red-black trees.

Many of these routines are based on the algorithms in chapter 13 of Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, "Introduction to Algorithms", MIT Press, Cambridge, MA, 1990.

FIXME: check implementation given the following note:

Note that the third edition was published in 2009 and the book has had significant updates since the first edition. Quoting the authors in the preface: "The way we delete a node from binary search trees (which includes red-black trees) now guarantees that the node requested for deletion is the node that is actually deleted. In the first two editions, in certain cases, some other node would be deleted, with its contents moving into the node passed to the deletion procedure. With our new way to delete nodes, if other components of a program maintain pointers to nodes in the tree, they will not mistakenly end up with stale pointers to nodes that have been deleted."

This implementation of balanced binary red-black tree operations provides all the basic dynamic set operations (e.g., insertion, deletion, search, minimum, maximum, predecessor, and successor) and order-statistic operations (i.e., select and rank) with optimal O(log(n)) performance while sorting on multiple keys. Such an implementation is referred to as an "augmented red-black tree" and is discussed in Chapter 14 of the 2009 edition of "Introduction to Algorithms."

Macro Definition Documentation

◆ rbl_node

#define rbl_node rbl_u.rbl_n

Definition at line 88 of file redblack.h.

◆ rbl_package

#define rbl_package rbl_u.rbl_p

Definition at line 89 of file redblack.h.

◆ BU_RB_LIST_NULL

#define BU_RB_LIST_NULL ((struct bu_rb_list *) 0)

Definition at line 90 of file redblack.h.

◆ BU_RB_LIST_INIT

#define BU_RB_LIST_INIT	(	_l,
		_m
	)

Value:

        { \
        (_l).size = (_l).capacity = 0; \
        (_l)._m = NULL; \
    }

Definition at line 91 of file redblack.h.

◆ BU_RB_LIST_INIT_CAPACITY

#define BU_RB_LIST_INIT_CAPACITY 4

Definition at line 96 of file redblack.h.

◆ BU_RB_TREE_NULL

#define BU_RB_TREE_NULL ((struct bu_rb_tree *) 0)

Definition at line 134 of file redblack.h.

◆ BU_CK_RB_TREE

#define BU_CK_RB_TREE ( _rb ) BU_CKMAG(_rb, BU_RB_TREE_MAGIC, "bu_rb_tree")

asserts the integrity of a bu_rb_tree struct.

Definition at line 139 of file redblack.h.

◆ BU_RB_TREE_INIT

#define BU_RB_TREE_INIT ( _rb )

Value:

        { \
        (_rb)->rbt_magic = BU_RB_TREE_MAGIC; \
        (_rb)->rbt_nm_nodes = 0; \
        (_rb)->rbt_print = NULL; \
        (_rb)->rbt_debug = 0; \
        (_rb)->rbt_description = NULL; \
        (_rb)->rbt_nm_orders = 0; \
        (_rb)->rbt_compar = NULL; \
        (_rb)->rbt_root = (_rb)->rbt_unique = (_rb)->rbt_current = NULL; \
        (_rb)->rbt_nodes.rbl_u.rbl_n = (_rb)->rbt_nodes.rbl_u.rbl_p = NULL; \
        (_rb)->rbt_packages.rbl_u.rbl_n = (_rb)->rbt_packages.rbl_u.rbl_p = NULL; \
        (_rb)->rbt_empty_node = NULL; \
    }

initializes a bu_rb_tree struct without allocating any memory.

Definition at line 144 of file redblack.h.

◆ BU_RB_TREE_INIT_ZERO

#define BU_RB_TREE_INIT_ZERO

Value:

{ BU_RB_TREE_MAGIC, 0, NULL, 0, NULL, 0, NULL, NULL, NULL, NULL, \

{ 0, 0, NULL }, { 0, 0, NULL }, NULL, NULL, NULL }

macro suitable for declaration statement initialization of a bu_rb_tree struct. does not allocate memory.

Definition at line 162 of file redblack.h.

◆ BU_RB_TREE_IS_INITIALIZED

#define BU_RB_TREE_IS_INITIALIZED ( _rb ) (((struct bu_rb_tree *)(_rb) != BU_RB_TREE_NULL) && LIKELY((_rb)->rbt_magic == BU_RB_TREE_MAGIC))

returns truthfully whether a bu_rb_tree has been initialized.

Definition at line 168 of file redblack.h.

◆ BU_RB_DEBUG_INSERT

#define BU_RB_DEBUG_INSERT 0x00000001

Insertion process

Definition at line 174 of file redblack.h.

◆ BU_RB_DEBUG_UNIQ

#define BU_RB_DEBUG_UNIQ 0x00000002

Uniqueness of inserts

Definition at line 175 of file redblack.h.

◆ BU_RB_DEBUG_ROTATE

#define BU_RB_DEBUG_ROTATE 0x00000004

Rotation process

Definition at line 176 of file redblack.h.

◆ BU_RB_DEBUG_OS

#define BU_RB_DEBUG_OS 0x00000008

Order-statistic operations

Definition at line 177 of file redblack.h.

◆ BU_RB_DEBUG_DELETE

#define BU_RB_DEBUG_DELETE 0x00000010

Deletion process

Definition at line 178 of file redblack.h.

◆ BU_RB_PKG_NULL

#define BU_RB_PKG_NULL ((struct bu_rb_package *) 0)

Definition at line 197 of file redblack.h.

◆ BU_RB_NODE_NULL

#define BU_RB_NODE_NULL ((struct bu_rb_node *) 0)

Definition at line 219 of file redblack.h.

◆ SENSE_MIN

#define SENSE_MIN 0

Definition at line 224 of file redblack.h.

◆ SENSE_MAX

#define SENSE_MAX 1

Definition at line 225 of file redblack.h.

◆ bu_rb_min

#define bu_rb_min	(	t,
		o
	)	bu_rb_extreme((t), (o), SENSE_MIN)

Definition at line 226 of file redblack.h.

◆ bu_rb_max

#define bu_rb_max	(	t,
		o
	)	bu_rb_extreme((t), (o), SENSE_MAX)

Definition at line 227 of file redblack.h.

◆ bu_rb_pred

#define bu_rb_pred	(	t,
		o
	)	bu_rb_neighbor((t), (o), SENSE_MIN)

Definition at line 228 of file redblack.h.

◆ bu_rb_succ

#define bu_rb_succ	(	t,
		o
	)	bu_rb_neighbor((t), (o), SENSE_MAX)

Definition at line 229 of file redblack.h.

◆ bu_rb_delete1

#define bu_rb_delete1 ( t ) bu_rb_delete((t), 0)

Definition at line 265 of file redblack.h.

◆ bu_rb_curr1

#define bu_rb_curr1 ( t ) bu_rb_curr((t), 0)

Definition at line 326 of file redblack.h.

◆ BU_RB_RETAIN_DATA

#define BU_RB_RETAIN_DATA ((void (*)(void *data)) 0)

Definition at line 342 of file redblack.h.

◆ bu_rb_free1

#define bu_rb_free1	(	t,
		f
	)

Value:

    {                                                   \
        BU_CKMAG((t), BU_RB_TREE_MAGIC, "red-black tree");      \
        bu_free((char *) ((t) -> rbt_compar),           \
                "red-black compare function");          \
        bu_rb_free(t, f);                                       \
    }

Definition at line 343 of file redblack.h.

◆ bu_rb_is_uniq1

#define bu_rb_is_uniq1 ( t ) bu_rb_is_uniq((t), 0)

Definition at line 375 of file redblack.h.

◆ bu_rb_uniq_on1

#define bu_rb_uniq_on1 ( t ) bu_rb_uniq_on((t), 0)

Definition at line 409 of file redblack.h.

◆ bu_rb_uniq_off1

#define bu_rb_uniq_off1 ( t ) bu_rb_uniq_off((t), 0)

Definition at line 418 of file redblack.h.

◆ bu_rb_rank1

#define bu_rb_rank1 ( t ) bu_rb_rank1((t), 0)

Definition at line 433 of file redblack.h.

◆ bu_rb_select1

#define bu_rb_select1	(	t,
		k
	)	bu_rb_select((t), 0, (k))

Definition at line 444 of file redblack.h.

◆ bu_rb_search1

#define bu_rb_search1	(	t,
		d
	)	bu_rb_search((t), 0, (d))

Definition at line 458 of file redblack.h.

◆ bu_rb_walk1

#define bu_rb_walk1	(	t,
		v,
		d
	)	bu_rb_walk((t), 0, (v), (d))

Definition at line 505 of file redblack.h.

◆ BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG

#define BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG ( _func ) ((void (*)(void))_func)

Definition at line 507 of file redblack.h.

◆ BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC

#define BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC ( _func ) ((void (*)(struct bu_rb_node *, int))_func)

Definition at line 508 of file redblack.h.

◆ BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC

#define BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC ( _func ) ((void (*)(void *, int))_func)

Definition at line 509 of file redblack.h.

◆ BU_RB_WALK_FUNC_CAST_AS_FUNC_FUNC

#define BU_RB_WALK_FUNC_CAST_AS_FUNC_FUNC ( _func ) ((void (*)(struct bu_rb_node *, int, void (*)(void), int))_func)

Definition at line 510 of file redblack.h.

◆ BU_RB_WALK_FUNC_NODE_DECL

#define BU_RB_WALK_FUNC_NODE_DECL ( _func ) void (*_func)(struct bu_rb_node *, int)

Definition at line 511 of file redblack.h.

◆ BU_RB_WALK_FUNC_DATA_DECL

#define BU_RB_WALK_FUNC_DATA_DECL ( _func ) void (*_func)(void *, int)

Definition at line 512 of file redblack.h.

◆ BU_RB_WALK_FUNC_FUNC_DECL

#define BU_RB_WALK_FUNC_FUNC_DECL ( _func ) void (*_func)(struct bu_rb_node *, int, void (*)(void), int)

Definition at line 513 of file redblack.h.

Typedef Documentation

◆ bu_rb_tree_t

typedef struct bu_rb_tree bu_rb_tree_t

Definition at line 133 of file redblack.h.

◆ bu_rb_cmp_t

typedef int(* bu_rb_cmp_t) (const void *, const void *)

Routines to create a red-black tree.

Create a red-black tree

This function has three parameters: a comment describing the tree to create, the number of linear orders to maintain simultaneously, and the comparison functions (one per order). bu_rb_create() returns a pointer to the red-black tree header record.

Definition at line 250 of file redblack.h.

Enumeration Type Documentation

◆ BU_RB_WALK_ORDER

enum BU_RB_WALK_ORDER

Enumerator
BU_RB_WALK_PREORDER
BU_RB_WALK_INORDER
BU_RB_WALK_POSTORDER

Definition at line 234 of file redblack.h.

Function Documentation

◆ bu_rb_create()

struct bu_rb_tree * bu_rb_create	(	const char *	description,
		int	nm_orders,
		bu_rb_cmp_t *	compare_funcs
	)

◆ bu_rb_delete()

void bu_rb_delete	(	struct bu_rb_tree *	tree,
		int	order
	)

Routines to delete a node from a red-black tree.

Applications interface to _rb_delete()

This function has two parameters: the tree and order from which to do the deleting. bu_rb_delete() removes the data block stored in the current node (in the position of the specified order) from every order in the tree.

◆ bu_rb_diagnose_tree()

void bu_rb_diagnose_tree	(	struct bu_rb_tree *	tree,
		int	order,
		int	trav_type
	)

Diagnostic routines for red-black tree maintenance.

Produce a diagnostic printout of a red-black tree

This function has three parameters: the root and order of the tree to print out and the type of traversal (preorder, inorder, or postorder).

◆ bu_rb_summarize_tree()

void bu_rb_summarize_tree ( struct bu_rb_tree * tree )

Describe a red-black tree

This function has one parameter: a pointer to a red-black tree. bu_rb_summarize_tree() prints out the header information for the tree. It is intended for diagnostic purposes.

◆ bu_rb_extreme()

void * bu_rb_extreme	(	struct bu_rb_tree *	tree,
		int	order,
		int	sense
	)

Routines to extract mins, maxes, adjacent, and current nodes from a red-black tree.

Applications interface to rb_extreme()

This function has three parameters: the tree in which to find an extreme node, the order on which to do the search, and the sense (min or max). On success, bu_rb_extreme() returns a pointer to the data in the extreme node. Otherwise it returns NULL.

◆ bu_rb_neighbor()

void * bu_rb_neighbor	(	struct bu_rb_tree *	tree,
		int	order,
		int	sense
	)

Return a node adjacent to the current red-black node

This function has three parameters: the tree and order on which to do the search and the sense (min or max, which is to say predecessor or successor) of the search. bu_rb_neighbor() returns a pointer to the data in the node adjacent to the current node in the specified direction, if that node exists. Otherwise, it returns NULL.

◆ bu_rb_curr()

void * bu_rb_curr	(	struct bu_rb_tree *	tree,
		int	order
	)

Return the current red-black node

This function has two parameters: the tree and order in which to find the current node. bu_rb_curr() returns a pointer to the data in the current node, if it exists. Otherwise, it returns NULL.

◆ bu_rb_free()

void bu_rb_free	(	struct bu_rb_tree *	tree,
		void()(void data)	free_data
	)

Routines to free a red-black tree.

Free a red-black tree

This function has two parameters: the tree to free and a function to handle the application data. bu_rb_free() traverses tree's lists of nodes and packages, freeing each one in turn, and then frees tree itself. If free_data is non-NULL, then bu_rb_free() calls it just* before freeing each package, passing it the package's rbp_data member. Otherwise, the application data is left untouched.

◆ bu_rb_insert()

int bu_rb_insert	(	struct bu_rb_tree *	tree,
		void *	data
	)

Routines to insert into a red-black tree.

Applications interface to bu_rb_insert()

This function has two parameters: the tree into which to insert the new node and the contents of the node. If a uniqueness requirement would be violated, bu_rb_insert() does nothing but return a number from the set {-1, -2, ..., -nm_orders} of which the absolute value is the first order for which a violation exists. Otherwise, it returns the number of orders for which the new node was equal to a node already in the tree.

◆ bu_rb_is_uniq()

int bu_rb_is_uniq	(	struct bu_rb_tree *	tree,
		int	order
	)

Query the uniqueness flag for one order of a red-black tree

This function has two parameters: the tree and the order for which to query uniqueness.

◆ bu_rb_set_uniqv()

void bu_rb_set_uniqv	(	struct bu_rb_tree *	tree,
		bitv_t	vec
	)

Set the uniqueness flags for all the linear orders of a red-black tree

This function has two parameters: the tree and a bitv_t encoding the flag values. bu_rb_set_uniqv() sets the flags according to the bits in flag_rep. For example, if flag_rep = 1011_2, then the first, second, and fourth orders are specified unique, and the third is specified not-necessarily unique.

◆ bu_rb_uniq_all_off()

void bu_rb_uniq_all_off ( struct bu_rb_tree * tree )

These functions have one parameter: the tree for which to require uniqueness/permit nonuniqueness.

◆ bu_rb_uniq_all_on()

void bu_rb_uniq_all_on ( struct bu_rb_tree * tree )

These functions have one parameter: the tree for which to require uniqueness/permit nonuniqueness.

◆ bu_rb_uniq_on()

int bu_rb_uniq_on	(	struct bu_rb_tree *	tree,
		int	order
	)

Has two parameters: the tree and the order for which to require uniqueness/permit nonuniqueness. Each sets the specified flag to the specified value and returns the previous value of the flag.

◆ bu_rb_uniq_off()

int bu_rb_uniq_off	(	struct bu_rb_tree *	tree,
		int	order
	)

Has two parameters: the tree and the order for which to require uniqueness/permit nonuniqueness. Each sets the specified flag to the specified value and returns the previous value of the flag.

◆ bu_rb_rank()

int bu_rb_rank	(	struct bu_rb_tree *	tree,
		int	order
	)

Routines to support order-statistic operations for a red-black tree.

Determines the rank of a node in one order of a red-black tree.

This function has two parameters: the tree in which to search and the order on which to do the searching. If the current node is null, bu_rb_rank() returns 0. Otherwise, it returns the rank of the current node in the specified order. bu_rb_rank() is an implementation of the routine OS-RANK on p. 283 of Cormen et al.

◆ bu_rb_select()

void * bu_rb_select	(	struct bu_rb_tree *	tree,
		int	order,
		int	k
	)

This function has three parameters: the tree in which to search, the order on which to do the searching, and the rank of interest. On success, bu_rb_select() returns a pointer to the data block in the discovered node. Otherwise, it returns NULL.

◆ bu_rb_search()

void * bu_rb_search	(	struct bu_rb_tree *	tree,
		int	order,
		void *	data
	)

Routines to search for a node in a red-black tree.

This function has three parameters: the tree in which to search, the order on which to do the searching, and a data block containing the desired value of the key. On success, bu_rb_search() returns a pointer to the data block in the discovered node. Otherwise, it returns NULL.

◆ bu_rb_walk()

void bu_rb_walk	(	struct bu_rb_tree *	tree,
		int	order,
		void(*)(void)	visit,
		int	trav_type
	)

Routines for traversal of red-black trees.

The function bu_rb_walk() is defined in terms of the function rb_walk(), which, in turn, calls any of the six functions

- static void prewalknodes()
- static void inwalknodes()
- static void postwalknodes()
- static void prewalkdata()
- static void inwalkdata()
- static void postwalkdata()

depending on the type of traversal desired and the objects to be visited (nodes themselves, or merely the data stored in them). Each of these last six functions has four parameters: the root of the tree to traverse, the order on which to do the walking, the function to apply at each visit, and the current depth in the tree.

This function has four parameters: the tree to traverse, the order on which to do the walking, the function to apply to each node, and the type of traversal (preorder, inorder, or postorder).

Note the function to apply has the following signature ONLY when it is used as an argument:

void (*visit)(void)

When used as a function the pointer should be cast back to one of its real signatures depending on what it is operating on (node or data):

node:

void (*visit)((struct bu_rb_node *, int)

data:

void (*visit)((void *, int)

Use the macros below to ensure accurate casting. See libbu/rb_diag.c and libbu/rb_walk.c for examples of their use.

Files

Data Structures

Macros

Typedefs

Enumerations

Functions

Detailed Description

Macro Definition Documentation

◆ rbl_node

◆ rbl_package

◆ BU_RB_LIST_NULL

◆ BU_RB_LIST_INIT

◆ BU_RB_LIST_INIT_CAPACITY

◆ BU_RB_TREE_NULL

◆ BU_CK_RB_TREE

◆ BU_RB_TREE_INIT

◆ BU_RB_TREE_INIT_ZERO

◆ BU_RB_TREE_IS_INITIALIZED

◆ BU_RB_DEBUG_INSERT

◆ BU_RB_DEBUG_UNIQ

◆ BU_RB_DEBUG_ROTATE

◆ BU_RB_DEBUG_OS

◆ BU_RB_DEBUG_DELETE

◆ BU_RB_PKG_NULL

◆ BU_RB_NODE_NULL

◆ SENSE_MIN

◆ SENSE_MAX

◆ bu_rb_min

◆ bu_rb_max

◆ bu_rb_pred

◆ bu_rb_succ

◆ bu_rb_delete1

◆ bu_rb_curr1

◆ BU_RB_RETAIN_DATA

◆ bu_rb_free1

◆ bu_rb_is_uniq1

◆ bu_rb_uniq_on1

◆ bu_rb_uniq_off1

◆ bu_rb_rank1

◆ bu_rb_select1

◆ bu_rb_search1

◆ bu_rb_walk1

◆ BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG

◆ BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC

◆ BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC

◆ BU_RB_WALK_FUNC_CAST_AS_FUNC_FUNC

◆ BU_RB_WALK_FUNC_NODE_DECL

◆ BU_RB_WALK_FUNC_DATA_DECL

◆ BU_RB_WALK_FUNC_FUNC_DECL

Typedef Documentation

◆ bu_rb_tree_t

◆ bu_rb_cmp_t

Enumeration Type Documentation

◆ BU_RB_WALK_ORDER

Function Documentation

◆ bu_rb_create()

◆ bu_rb_delete()

◆ bu_rb_diagnose_tree()

◆ bu_rb_summarize_tree()

◆ bu_rb_extreme()

◆ bu_rb_neighbor()

◆ bu_rb_curr()

◆ bu_rb_free()

◆ bu_rb_insert()

◆ bu_rb_is_uniq()

◆ bu_rb_set_uniqv()

◆ bu_rb_uniq_all_off()

◆ bu_rb_uniq_all_on()

◆ bu_rb_uniq_on()

◆ bu_rb_uniq_off()

◆ bu_rb_rank()

◆ bu_rb_select()

◆ bu_rb_search()

◆ bu_rb_walk()