BRL-CAD
Collaboration diagram for Red-Black Trees:

Files

file  rb_create.c
 
file  rb_delete.c
 
file  rb_diag.c
 
file  rb_extreme.c
 
file  rb_free.c
 
file  rb_insert.c
 
file  rb_order_stats.c
 
file  rb_search.c
 
file  rb_walk.c
 

Data Structures

struct  bu_rb_list
 
struct  bu_rb_tree
 
struct  bu_rb_package
 
struct  bu_rb_node
 

Macros

#define rbl_magic   l.magic
 
#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_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_COMPARE_FUNC_CAST_AS_FUNC_ARG(_func)   ((int (*)(void))_func)
 
#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
 

Enumerations

enum  BU_RB_WALK_ORDER { BU_RB_WALK_PREORDER, BU_RB_WALK_INORDER, BU_RB_WALK_POSTORDER }
 

Functions

struct bu_rb_treebu_rb_create (const char *description, int nm_orders, int(**compare_funcs)(const void *, const void *))
 
struct bu_rb_treebu_rb_create1 (const char *description, int(*compare_func)(void))
 
void bu_rb_delete (struct bu_rb_tree *tree, int order)
 
void bu_rb_diagnose_tree (struct bu_rb_tree *tree, int order, int trav_type)
 
void bu_rb_summarize_tree (struct bu_rb_tree *tree)
 
void * bu_rb_extreme (struct bu_rb_tree *tree, int order, int sense)
 
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))
 
int bu_rb_insert (struct bu_rb_tree *tree, void *data)
 
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)
 
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)
 
void bu_rb_walk (struct bu_rb_tree *tree, int order, void(*visit)(void), int trav_type)
 

Detailed Description

Macro Definition Documentation

#define rbl_magic   l.magic

Definition at line 89 of file rb.h.

#define rbl_node   rbl_u.rbl_n

Definition at line 90 of file rb.h.

#define rbl_package   rbl_u.rbl_p

Definition at line 91 of file rb.h.

#define BU_RB_LIST_NULL   ((struct bu_rb_list *) 0)

Definition at line 92 of file rb.h.

#define BU_RB_TREE_NULL   ((struct bu_rb_tree *) 0)

Definition at line 130 of file rb.h.

#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 135 of file rb.h.

#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; \
BU_LIST_INIT(&(_rb)->rbt_nodes.l); \
(_rb)->rbt_nodes.rbl_u.rbl_n = (_rb)->rbt_nodes.rbl_u.rbl_p = NULL; \
BU_LIST_INIT(&(_rb)->rbt_packages.l); \
(_rb)->rbt_packages.rbl_u.rbl_n = (_rb)->rbt_packages.rbl_u.rbl_p = NULL; \
(_rb)->rbt_empty_node = NULL; \
}
#define BU_RB_TREE_MAGIC
Definition: magic.h:63
#define BU_LIST_INIT(_hp)
Definition: list.h:148

initializes a bu_rb_tree struct without allocating any memory.

Definition at line 140 of file rb.h.

#define BU_RB_TREE_INIT_ZERO
Value:
{ BU_RB_TREE_MAGIC, 0, NULL, 0, NULL, 0, NULL, NULL, NULL, NULL, \
{ BU_LIST_INIT_ZER0, {NULL, NULL} }, { BU_LIST_INIT_ZER0, {NULL, NULL} }, NULL, NULL, NULL }
#define BU_RB_TREE_MAGIC
Definition: magic.h:63

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

Definition at line 160 of file rb.h.

#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 166 of file rb.h.

#define BU_RB_DEBUG_INSERT   0x00000001

Insertion process

Definition at line 172 of file rb.h.

Referenced by _rb_insert().

#define BU_RB_DEBUG_UNIQ   0x00000002

Uniqueness of inserts

Definition at line 173 of file rb.h.

Referenced by bu_rb_insert().

#define BU_RB_DEBUG_ROTATE   0x00000004

Rotation process

Definition at line 174 of file rb.h.

Referenced by rb_rot_left(), and rb_rot_right().

#define BU_RB_DEBUG_OS   0x00000008

Order-statistic operations

Definition at line 175 of file rb.h.

Referenced by _rb_insert(), _rb_select(), bu_rb_insert(), bu_rb_select(), rb_rot_left(), and rb_rot_right().

#define BU_RB_DEBUG_DELETE   0x00000010

Deletion process

Definition at line 176 of file rb.h.

Referenced by _rb_delete().

#define BU_RB_PKG_NULL   ((struct bu_rb_package *) 0)

Definition at line 195 of file rb.h.

Referenced by _rb_describe_node(), and bu_rb_create().

#define BU_RB_NODE_NULL   ((struct bu_rb_node *) 0)

Definition at line 217 of file rb.h.

Referenced by bu_rb_create(), and bu_rb_summarize_tree().

#define SENSE_MIN   0

Definition at line 222 of file rb.h.

Referenced by _rb_extreme(), bu_rb_extreme(), bu_rb_neighbor(), and rb_neighbor().

#define SENSE_MAX   1

Definition at line 223 of file rb.h.

Referenced by _rb_delete(), bu_rb_extreme(), and bu_rb_neighbor().

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

Definition at line 224 of file rb.h.

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

Definition at line 225 of file rb.h.

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

Definition at line 226 of file rb.h.

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

Definition at line 227 of file rb.h.

#define BU_RB_COMPARE_FUNC_CAST_AS_FUNC_ARG (   _func)    ((int (*)(void))_func)

Definition at line 254 of file rb.h.

Referenced by main().

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

Definition at line 287 of file rb.h.

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

Definition at line 358 of file rb.h.

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

Definition at line 378 of file rb.h.

#define bu_rb_free1 (   t,
 
)
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); \
}
#define BU_CKMAG(_ptr, _magic, _str)
Definition: magic.h:233
#define BU_RB_TREE_MAGIC
Definition: magic.h:63
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
void bu_rb_free(struct bu_rb_tree *tree, void(*free_data)(void *data))

Definition at line 379 of file rb.h.

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

Definition at line 415 of file rb.h.

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

Definition at line 449 of file rb.h.

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

Definition at line 458 of file rb.h.

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

Definition at line 477 of file rb.h.

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

Definition at line 488 of file rb.h.

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

Definition at line 506 of file rb.h.

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

Definition at line 556 of file rb.h.

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

Definition at line 558 of file rb.h.

Referenced by bu_rb_diagnose_tree(), main(), and rb_walk().

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

Definition at line 559 of file rb.h.

Referenced by inwalknodes(), postwalknodes(), and prewalknodes().

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

Definition at line 560 of file rb.h.

Referenced by inwalkdata(), postwalkdata(), and prewalkdata().

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

Definition at line 561 of file rb.h.

Referenced by rb_walk().

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

Definition at line 562 of file rb.h.

Referenced by inwalknodes(), postwalknodes(), and prewalknodes().

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

Definition at line 563 of file rb.h.

Referenced by inwalkdata(), postwalkdata(), and prewalkdata().

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

Definition at line 564 of file rb.h.

Referenced by rb_walk().

Typedef Documentation

typedef struct bu_rb_tree bu_rb_tree_t

Definition at line 129 of file rb.h.

Enumeration Type Documentation

Enumerator
BU_RB_WALK_PREORDER 
BU_RB_WALK_INORDER 
BU_RB_WALK_POSTORDER 

Definition at line 232 of file rb.h.

Function Documentation

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

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 30 of file rb_create.c.

References BU_ALLOC, BU_LIST_INIT, bu_malloc(), BU_RB_NODE_MAGIC, BU_RB_NODE_NULL, BU_RB_PKG_NULL, BU_RB_TREE_MAGIC, bu_rb_uniq_all_off(), bu_rb_list::l, RB_BLK, RB_LEFT_CHILD, RB_NULL, RB_PARENT, RB_RIGHT_CHILD, RB_ROOT, RB_SET_COLOR, RB_SIZE, bu_rb_tree::rbt_compar, bu_rb_tree::rbt_current, bu_rb_tree::rbt_debug, bu_rb_tree::rbt_description, bu_rb_tree::rbt_magic, bu_rb_tree::rbt_nm_orders, bu_rb_tree::rbt_nodes, bu_rb_tree::rbt_packages, bu_rb_tree::rbt_print, bu_rb_tree::rbt_root, and bu_rb_tree::rbt_unique.

Referenced by bu_rb_create1().

Here is the call graph for this function:

struct bu_rb_tree* bu_rb_create1 ( const char *  description,
int(*)(void)  compare_func 
)

Create a single-order red-black tree

This function has two parameters: a comment describing the tree to create and a comparison function. bu_rb_create1() builds an array of one function pointer and passes it to bu_rb_create(). bu_rb_create1() returns a pointer to the red-black tree header record.

N.B. - Since this function allocates storage for the array of function pointers, in order to avoid memory leaks on freeing the tree, applications should call bu_rb_free1(), NOT bu_rb_free().

Definition at line 102 of file rb_create.c.

References bu_malloc(), and bu_rb_create().

Referenced by main().

Here is the call graph for this function:

void bu_rb_delete ( struct bu_rb_tree tree,
int  order 
)

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.

Definition at line 149 of file rb_delete.c.

References _rb_delete(), bu_bomb(), BU_CKMAG, bu_free(), bu_log(), bu_malloc(), BU_RB_TREE_MAGIC, RB_CKORDER, RB_CURRENT, rb_free_package(), RB_NULL, bu_rb_package::rbp_node, bu_rb_tree::rbt_nm_nodes, bu_rb_tree::rbt_nm_orders, and UNLIKELY.

Referenced by main().

Here is the call graph for this function:

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

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).

Definition at line 71 of file rb_diag.c.

References _rb_describe_node(), BU_CKMAG, bu_log(), BU_RB_TREE_MAGIC, BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG, RB_CKORDER, RB_GET_UNIQUENESS, rb_walk(), bu_rb_tree::rbt_current, bu_rb_tree::rbt_description, bu_rb_tree::rbt_empty_node, bu_rb_tree::rbt_nm_orders, and WALK_NODES.

Referenced by main().

Here is the call graph for this function:

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.

Definition at line 89 of file rb_diag.c.

References BU_CKMAG, bu_log(), BU_RB_NODE_NULL, BU_RB_TREE_MAGIC, RB_COMPARE_FUNC, RB_DATA, RB_GET_UNIQUENESS, RB_ROOT, bu_rb_tree::rbt_current, bu_rb_tree::rbt_debug, bu_rb_tree::rbt_description, bu_rb_tree::rbt_empty_node, bu_rb_tree::rbt_nm_nodes, and bu_rb_tree::rbt_nm_orders.

Here is the call graph for this function:

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

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.

Definition at line 68 of file rb_extreme.c.

References _rb_extreme(), BU_CKMAG, bu_log(), BU_RB_TREE_MAGIC, RB_CKORDER, RB_DATA, RB_NULL, RB_ROOT, SENSE_MAX, SENSE_MIN, and UNLIKELY.

Here is the call graph for this function:

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.

Definition at line 124 of file rb_extreme.c.

References BU_CKMAG, bu_log(), BU_RB_TREE_MAGIC, RB_CKORDER, RB_CURRENT, RB_DATA, rb_neighbor(), RB_NULL, SENSE_MAX, SENSE_MIN, and UNLIKELY.

Here is the call graph for this function:

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.

Definition at line 150 of file rb_extreme.c.

References BU_CKMAG, BU_RB_TREE_MAGIC, RB_CKORDER, RB_CURRENT, RB_DATA, and RB_NULL.

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

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.

int bu_rb_insert ( struct bu_rb_tree tree,
void *  data 
)

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.

Definition at line 150 of file rb_insert.c.

References _rb_insert(), BU_ALLOC, BU_CKMAG, BU_LIST_PUSH, bu_log(), bu_malloc(), BU_RB_DEBUG_OS, BU_RB_DEBUG_UNIQ, BU_RB_LIST_MAGIC, BU_RB_NODE_MAGIC, BU_RB_PKG_MAGIC, bu_rb_search(), BU_RB_TREE_MAGIC, data, bu_rb_list::l, RB_BLK, RB_CURRENT, RB_GET_UNIQUENESS, RB_LEFT_CHILD, RB_NULL, RB_PARENT, RB_RIGHT_CHILD, RB_ROOT, RB_SET_COLOR, RB_SIZE, bu_rb_node::rbn_color, bu_rb_node::rbn_left, bu_rb_node::rbn_list_pos, bu_rb_node::rbn_magic, bu_rb_node::rbn_package, bu_rb_node::rbn_parent, bu_rb_node::rbn_pkg_refs, bu_rb_node::rbn_right, bu_rb_node::rbn_size, bu_rb_node::rbn_tree, bu_rb_package::rbp_data, bu_rb_package::rbp_list_pos, bu_rb_package::rbp_magic, bu_rb_package::rbp_node, bu_rb_tree::rbt_debug, bu_rb_tree::rbt_nm_nodes, bu_rb_tree::rbt_nm_orders, bu_rb_tree::rbt_nodes, bu_rb_tree::rbt_packages, and UNLIKELY.

Referenced by main().

Here is the call graph for this function:

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.

Definition at line 314 of file rb_insert.c.

References BU_CKMAG, BU_RB_TREE_MAGIC, RB_CKORDER, and RB_GET_UNIQUENESS.

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.

Definition at line 324 of file rb_insert.c.

References BU_CKMAG, bu_log(), BU_RB_TREE_MAGIC, RB_SET_UNIQUENESS, bu_rb_tree::rbt_nm_orders, and UNLIKELY.

Here is the call graph for this function:

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.

Definition at line 373 of file rb_insert.c.

References _rb_set_uniq_all().

Referenced by bu_rb_create().

Here is the call graph for this function:

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.

Definition at line 367 of file rb_insert.c.

References _rb_set_uniq_all().

Here is the call graph for this function:

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.

Definition at line 301 of file rb_insert.c.

References _rb_set_uniq().

Here is the call graph for this function:

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.

Definition at line 307 of file rb_insert.c.

References _rb_set_uniq().

Here is the call graph for this function:

int bu_rb_rank ( struct bu_rb_tree tree,
int  order 
)

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.

Definition at line 86 of file rb_order_stats.c.

References BU_CKMAG, BU_RB_TREE_MAGIC, RB_CKORDER, RB_CURRENT, RB_LEFT_CHILD, RB_NULL, RB_PARENT, RB_RIGHT_CHILD, RB_ROOT, and RB_SIZE.

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.

Definition at line 62 of file rb_order_stats.c.

References _rb_select(), BU_CKMAG, bu_log(), BU_RB_DEBUG_OS, BU_RB_TREE_MAGIC, RB_CKORDER, RB_CURRENT, RB_DATA, RB_NULL, RB_ROOT, bu_rb_tree::rbt_debug, bu_rb_tree::rbt_nm_nodes, and UNLIKELY.

Here is the call graph for this function:

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

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.

Definition at line 67 of file rb_search.c.

References _rb_search(), BU_CKMAG, BU_RB_TREE_MAGIC, RB_CKORDER, RB_COMPARE_FUNC, RB_DATA, RB_NULL, and RB_ROOT.

Referenced by bu_rb_insert(), and main().

Here is the call graph for this function:

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

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.

Definition at line 238 of file rb_walk.c.

References BU_CKMAG, BU_RB_TREE_MAGIC, RB_CKORDER, rb_walk(), and WALK_DATA.

Referenced by main().

Here is the call graph for this function: