RedBlack trees
[libbu (utility functions)]

Collaboration diagram for RedBlack trees:


Files

file  redblack.h
 The data structures and constants for red-black trees.
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_internals.h
file  rb_order_stats.c
file  rb_rotate.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
struct  bu_observer
struct  bu_cmdtab

Defines

#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   ((bu_rb_tree *) 0)
#define BU_RB_TREE_MAGIC   0x72627472
#define BU_RB_DEBUG_INSERT   0x00000001
 Insertion process.
#define BU_RB_DEBUG_UNIQ   0x00000002
 Uniqueness of inserts.
#define BU_RB_DEBUG_ROTATE   0x00000004
 Rotation process.
#define BU_RB_DEBUG_OS   0x00000008
 Order-statistic operations.
#define BU_RB_DEBUG_DELETE   0x00000010
 Deletion process.
#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 PREORDER   0
#define INORDER   1
#define POSTORDER   2
#define BU_OBSERVER_NULL   ((struct bu_observer *)0)
#define bu_made_it()
#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 (*)()) 0)
#define bu_rb_free1(t, f)
#define bu_rb_is_uniq1(t)   bu_rb_is_uniq((t), 0)
#define bu_rb_uniq_off1(t)   bu_rb_uniq_off((t), 0)
#define bu_rb_uniq_on1(t)   bu_rb_uniq_on((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_INTERNALS_H   seen
#define BU_RB_CKMAG   BU_CKMAG
#define BU_RB_NODE_MAGIC   0x72626e6f
#define BU_RB_PKG_MAGIC   0x7262706b
#define BU_RB_LIST_MAGIC   0x72626c73
#define BU_RB_CKORDER(t, o)
#define bu_rb_order_func(t, o)   (((t) -> rbt_order)[o])
#define bu_rb_print(t, p)   (((t) -> rbt_print)((p) -> rbp_data))
#define bu_rb_root(t, o)   (((t) -> rbt_root)[o])
#define bu_rb_current(t)   ((t) -> rbt_current)
#define bu_rb_null(t)   ((t) -> rbt_empty_node)
#define bu_rb_get_uniqueness(t, o)
#define bu_rb_set_uniqueness(t, o, u)
#define bu_rb_parent(n, o)   (((n) -> rbn_parent)[o])
#define bu_rb_left_child(n, o)   (((n) -> rbn_left)[o])
#define bu_rb_right_child(n, o)   (((n) -> rbn_right)[o])
#define BU_RB_LEFT   0
#define BU_RB_RIGHT   1
#define bu_rb_child(n, o, d)
#define bu_rb_other_child(n, o, d)
#define bu_rb_size(n, o)   (((n) -> rbn_size)[o])
#define bu_rb_get_color(n, o)
#define bu_rb_set_color(n, o, c)
#define BU_RB_RED   0
#define BU_RB_BLACK   1
#define bu_rb_data(n, o)   (((n) -> rbn_package)[o] -> rbp_data)
#define WALK_NODES   0
#define WALK_DATA   1
#define bu_rb_rotate(n, o, d)
#define bu_rb_other_rotate(n, o, d)

Functions

bu_rb_tree * bu_rb_create (char *description, int nm_orders, int(**order_funcs)())
bu_rb_tree * bu_rb_create1 (char *description, int(*order_func)())
void bu_rb_delete (bu_rb_tree *tree, int order)
void bu_rb_diagnose_tree (bu_rb_tree *tree, int order, int trav_type)
void bu_rb_summarize_tree (bu_rb_tree *tree)
void * bu_rb_curr (bu_rb_tree *tree, int order)
void * bu_rb_extreme (bu_rb_tree *tree, int order, int sense)
void * bu_rb_neighbor (bu_rb_tree *tree, int order, int sense)
void bu_rb_free (bu_rb_tree *tree, void(*free_data)())
int bu_rb_insert (bu_rb_tree *tree, void *data)
int bu_rb_is_uniq (bu_rb_tree *tree, int order)
void bu_rb_set_uniqv (bu_rb_tree *tree, bitv_t vec)
void bu_rb_uniq_all_off (bu_rb_tree *tree)
void bu_rb_uniq_all_on (bu_rb_tree *tree)
int bu_rb_uniq_off (bu_rb_tree *tree, int order)
int bu_rb_uniq_on (bu_rb_tree *tree, int order)
int bu_rb_rank (bu_rb_tree *tree, int order)
void * bu_rb_select (bu_rb_tree *tree, int order, int k)
void * bu_rb_search (bu_rb_tree *tree, int order, void *data)
void bu_rb_walk (bu_rb_tree *tree, int order, void(*visit)(), int trav_type)
bu_rb_node * _rb_neighbor (struct bu_rb_node *node, int order, int sense)
void _rb_rot_left (struct bu_rb_node *x, int order)
void _rb_rot_right (struct bu_rb_node *y, int order)
void _rb_walk (bu_rb_tree *tree, int order, void(*visit)(), int what_to_visit, int trav_type)
void bu_rb_free_node (struct bu_rb_node *node)
void bu_rb_free_package (struct bu_rb_package *package)

Define Documentation

#define rbl_magic   l.magic
 

Definition at line 1497 of file bu.h.

#define rbl_node   rbl_u.rbl_n
 

Definition at line 1498 of file bu.h.

Referenced by bu_rb_free().

#define rbl_package   rbl_u.rbl_p
 

Definition at line 1499 of file bu.h.

#define BU_RB_LIST_NULL   ((struct bu_rb_list *) 0)
 

Definition at line 1500 of file bu.h.

#define BU_RB_TREE_NULL   ((bu_rb_tree *) 0)
 

Definition at line 1538 of file bu.h.

#define BU_RB_TREE_MAGIC   0x72627472
 

Definition at line 1539 of file bu.h.

Referenced by _rb_walk(), bu_identify_magic(), bu_rb_create(), bu_rb_curr(), bu_rb_delete(), bu_rb_diagnose_tree(), bu_rb_extreme(), bu_rb_free(), bu_rb_insert(), bu_rb_is_uniq(), bu_rb_neighbor(), bu_rb_rank(), bu_rb_search(), bu_rb_select(), bu_rb_set_uniqv(), bu_rb_summarize_tree(), and bu_rb_walk().

#define BU_RB_DEBUG_INSERT   0x00000001
 

Insertion process.

Definition at line 1544 of file bu.h.

#define BU_RB_DEBUG_UNIQ   0x00000002
 

Uniqueness of inserts.

Definition at line 1545 of file bu.h.

Referenced by bu_rb_insert().

#define BU_RB_DEBUG_ROTATE   0x00000004
 

Rotation process.

Definition at line 1546 of file bu.h.

Referenced by _rb_rot_left(), and _rb_rot_right().

#define BU_RB_DEBUG_OS   0x00000008
 

Order-statistic operations.

Definition at line 1547 of file bu.h.

Referenced by _rb_rot_left(), and _rb_rot_right().

#define BU_RB_DEBUG_DELETE   0x00000010
 

Deletion process.

Definition at line 1548 of file bu.h.

#define BU_RB_PKG_NULL   ((struct bu_rb_package *) 0)
 

Definition at line 1570 of file bu.h.

Referenced by bu_rb_create().

#define BU_RB_NODE_NULL   ((struct bu_rb_node *) 0)
 

Definition at line 1595 of file bu.h.

Referenced by bu_rb_create(), and bu_rb_summarize_tree().

#define SENSE_MIN   0
 

Definition at line 1600 of file bu.h.

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

#define SENSE_MAX   1
 

Definition at line 1601 of file bu.h.

Referenced by bu_rb_extreme(), and bu_rb_neighbor().

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

Definition at line 1602 of file bu.h.

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

Definition at line 1603 of file bu.h.

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

Definition at line 1604 of file bu.h.

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

Definition at line 1605 of file bu.h.

#define PREORDER   0
 

Definition at line 1610 of file bu.h.

Referenced by _rb_walk().

#define INORDER   1
 

Definition at line 1611 of file bu.h.

Referenced by _rb_walk().

#define POSTORDER   2
 

Definition at line 1612 of file bu.h.

Referenced by _rb_walk().

#define BU_OBSERVER_NULL   ((struct bu_observer *)0)
 

Definition at line 1624 of file bu.h.

 
#define bu_made_it (   ) 
 

Value:

bu_log("Made it to %s:%d\n",    \
                                        __FILE__, __LINE__)

Definition at line 1636 of file bu.h.

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

Definition at line 2201 of file bu.h.

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

Definition at line 2214 of file bu.h.

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

Definition at line 2227 of file bu.h.

#define bu_rb_free1 (  t,
f   ) 
 

Value:

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

Definition at line 2228 of file bu.h.

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

Definition at line 2242 of file bu.h.

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

Definition at line 2253 of file bu.h.

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

Definition at line 2257 of file bu.h.

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

Definition at line 2263 of file bu.h.

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

Definition at line 2268 of file bu.h.

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

Definition at line 2275 of file bu.h.

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

Definition at line 2283 of file bu.h.

#define BU_RB_INTERNALS_H   seen
 

Definition at line 45 of file rb_internals.h.

#define BU_RB_CKMAG   BU_CKMAG
 

B U _ R B _ C K M A G ( ) Check and validate a structure pointer

This macro has three parameters: a pointer, the magic number expected at that location, and a string describing the expected structure type.

Definition at line 54 of file rb_internals.h.

#define BU_RB_NODE_MAGIC   0x72626e6f
 

Definition at line 55 of file rb_internals.h.

Referenced by _rb_neighbor(), _rb_rot_left(), _rb_rot_right(), bu_identify_magic(), bu_rb_create(), and bu_rb_free_node().

#define BU_RB_PKG_MAGIC   0x7262706b
 

Definition at line 56 of file rb_internals.h.

Referenced by bu_identify_magic(), bu_rb_free(), and bu_rb_free_package().

#define BU_RB_LIST_MAGIC   0x72626c73
 

Definition at line 57 of file rb_internals.h.

Referenced by bu_rb_free(), bu_rb_free_node(), and bu_rb_free_package().

#define BU_RB_CKORDER (  t,
o   ) 
 

Value:

if (((o) < 0) || ((o) >= (t) -> rbt_nm_orders))         \
    {                                                           \
        bu_log(                                                 \
            "Error: Order %d outside 0..%d (nm_orders-1), file %s, line %d\n", \
            (o), (t) -> rbt_nm_orders - 1, __FILE__, __LINE__); \
        exit (0);                                               \
    }
B U _ R B _ C K O R D E R ( )

This macro has two parameters: a tree and an order number. It ensures that the order number is valid for the tree.

Definition at line 64 of file rb_internals.h.

Referenced by _rb_neighbor(), _rb_rot_left(), _rb_rot_right(), _rb_walk(), bu_rb_curr(), bu_rb_delete(), bu_rb_diagnose_tree(), bu_rb_extreme(), bu_rb_is_uniq(), bu_rb_neighbor(), bu_rb_rank(), bu_rb_search(), bu_rb_select(), and bu_rb_walk().

#define bu_rb_order_func (  t,
o   )     (((t) -> rbt_order)[o])
 

Definition at line 76 of file rb_internals.h.

Referenced by bu_rb_search(), and bu_rb_summarize_tree().

#define bu_rb_print (  t,
p   )     (((t) -> rbt_print)((p) -> rbp_data))
 

Definition at line 77 of file rb_internals.h.

#define bu_rb_root (  t,
o   )     (((t) -> rbt_root)[o])
 

Definition at line 78 of file rb_internals.h.

Referenced by _rb_rot_left(), _rb_rot_right(), _rb_walk(), bu_rb_create(), bu_rb_extreme(), bu_rb_rank(), bu_rb_search(), bu_rb_select(), and bu_rb_summarize_tree().

#define bu_rb_current (  t   )     ((t) -> rbt_current)
 

Definition at line 79 of file rb_internals.h.

Referenced by _rb_neighbor(), bu_rb_curr(), bu_rb_delete(), bu_rb_free_node(), bu_rb_neighbor(), bu_rb_rank(), and bu_rb_select().

#define bu_rb_null (  t   )     ((t) -> rbt_empty_node)
 

Definition at line 80 of file rb_internals.h.

Referenced by _rb_neighbor(), _rb_rot_left(), _rb_rot_right(), bu_rb_create(), bu_rb_curr(), bu_rb_delete(), bu_rb_extreme(), bu_rb_free_node(), bu_rb_neighbor(), bu_rb_rank(), bu_rb_search(), and bu_rb_select().

#define bu_rb_get_uniqueness (  t,
o   ) 
 

Value:

(                                                                       \
    (((t) -> rbt_unique)[(o)/8] & (0x1 << ((o) % 8))) ? 1 : 0           \
)

Definition at line 81 of file rb_internals.h.

Referenced by bu_rb_diagnose_tree(), bu_rb_insert(), bu_rb_is_uniq(), and bu_rb_summarize_tree().

#define bu_rb_set_uniqueness (  t,
o,
u   ) 
 

Value:

{                                                                       \
    int _b = (o) / 8;                                                   \
    int _p = (o) - _b * 8;                                              \
                                                                        \
    ((t) -> rbt_unique)[_b] &= ~(0x1 << _p);                            \
    ((t) -> rbt_unique)[_b] |= (u) << _p;                               \
}

Definition at line 85 of file rb_internals.h.

Referenced by bu_rb_set_uniqv().

#define bu_rb_parent (  n,
o   )     (((n) -> rbn_parent)[o])
 

Definition at line 97 of file rb_internals.h.

Referenced by _rb_neighbor(), _rb_rot_left(), _rb_rot_right(), bu_rb_create(), and bu_rb_rank().

#define bu_rb_left_child (  n,
o   )     (((n) -> rbn_left)[o])
 

Definition at line 98 of file rb_internals.h.

Referenced by _rb_neighbor(), _rb_rot_left(), _rb_rot_right(), bu_rb_create(), and bu_rb_rank().

#define bu_rb_right_child (  n,
o   )     (((n) -> rbn_right)[o])
 

Definition at line 99 of file rb_internals.h.

Referenced by _rb_neighbor(), _rb_rot_left(), _rb_rot_right(), bu_rb_create(), and bu_rb_rank().

#define BU_RB_LEFT   0
 

Definition at line 100 of file rb_internals.h.

#define BU_RB_RIGHT   1
 

Definition at line 101 of file rb_internals.h.

#define bu_rb_child (  n,
o,
d   ) 
 

Value:

(((d) == BU_RB_LEFT)            ?       \
                                    bu_rb_left_child((n), (o))  :       \
                                    bu_rb_right_child((n), (o)))

Definition at line 102 of file rb_internals.h.

Referenced by _rb_neighbor().

#define bu_rb_other_child (  n,
o,
d   ) 
 

Value:

(((d) == BU_RB_LEFT)            ?       \
                                    bu_rb_right_child((n), (o)) :       \
                                    bu_rb_left_child((n), (o)))

Definition at line 105 of file rb_internals.h.

#define bu_rb_size (  n,
o   )     (((n) -> rbn_size)[o])
 

Definition at line 108 of file rb_internals.h.

Referenced by _rb_rot_left(), _rb_rot_right(), bu_rb_create(), and bu_rb_rank().

#define bu_rb_get_color (  n,
o   ) 
 

Value:

(                                                                       \
    (((n) -> rbn_color)[(o)/8] & (0x1 << ((o) % 8))) ? 1 : 0            \
)

Definition at line 109 of file rb_internals.h.

#define bu_rb_set_color (  n,
o,
c   ) 
 

Value:

{                                                                       \
    int _b = (o) / 8;                                                   \
    int _p = (o) - _b * 8;                                              \
                                                                        \
    ((n) -> rbn_color)[_b] &= ~(0x1 << _p);                             \
    ((n) -> rbn_color)[_b] |= (c) << _p;                                \
}

Definition at line 113 of file rb_internals.h.

Referenced by bu_rb_create().

#define BU_RB_RED   0
 

Definition at line 121 of file rb_internals.h.

#define BU_RB_BLACK   1
 

Definition at line 122 of file rb_internals.h.

Referenced by bu_rb_create().

#define bu_rb_data (  n,
o   )     (((n) -> rbn_package)[o] -> rbp_data)
 

Definition at line 123 of file rb_internals.h.

Referenced by bu_rb_curr(), bu_rb_extreme(), bu_rb_neighbor(), bu_rb_search(), bu_rb_select(), and bu_rb_summarize_tree().

#define WALK_NODES   0
 

Interface to _rb_walk() (Valid values for the parameter what_to_walk)

Definition at line 129 of file rb_internals.h.

Referenced by _rb_walk(), and bu_rb_diagnose_tree().

#define WALK_DATA   1
 

Definition at line 130 of file rb_internals.h.

Referenced by _rb_walk(), and bu_rb_walk().

#define bu_rb_rotate (  n,
o,
d   ) 
 

Value:

(((d) == BU_RB_LEFT)            ?       \
                                    _rb_rot_left((n), (o))      :       \
                                    _rb_rot_right((n), (o)))
B U _ R B _ R O T A T E ( ) and B U _ R B _ O T H E R _ R O T A T E ( )

These macros have three parameters: the node about which to rotate, the order to be rotated, and the direction of rotation. They allow indirection in the use of _rb_rot_left() and _rb_rot_right().

Definition at line 141 of file rb_internals.h.

#define bu_rb_other_rotate (  n,
o,
d   ) 
 

Value:

(((d) == BU_RB_LEFT)    ?       \
                                    _rb_rot_right((n), (o))     :       \
                                    _rb_rot_left((n), (o)))

Definition at line 144 of file rb_internals.h.

Function Documentation

bu_rb_tree * bu_rb_create (  char *  description,
int  nm_orders,
int(**)()  order_funcs
) 
 

B U _ R B _ C R E A T E ( )

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

References BU_LIST_INIT, bu_malloc(), BU_RB_BLACK, bu_rb_left_child, BU_RB_NODE_MAGIC, BU_RB_NODE_NULL, bu_rb_null, bu_rb_parent, BU_RB_PKG_NULL, bu_rb_right_child, bu_rb_root, bu_rb_set_color, bu_rb_size, BU_RB_TREE_MAGIC, bu_rb_uniq_all_off(), bu_rb_node::rbn_color, bu_rb_node::rbn_left, bu_rb_node::rbn_package, bu_rb_node::rbn_parent, bu_rb_node::rbn_right, and bu_rb_node::rbn_size.

Referenced by bu_rb_create1().

Here is the call graph for this function:

bu_rb_tree * bu_rb_create1 (  char *  description,
int(*)()  order_func
) 
 

B U _ R B _ C R E A T E 1 ( )

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

References bu_malloc(), bu_rb_create(), and int.

Here is the call graph for this function:

void bu_rb_delete (  bu_rb_tree *  tree,
int  order
) 
 

B U _ R B _ D E L E T E ( )

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 184 of file rb_delete.c.

References bu_bomb(), BU_CKMAG, bu_free(), bu_log(), bu_malloc(), BU_RB_CKORDER, bu_rb_current, bu_rb_free_package(), bu_rb_null, and BU_RB_TREE_MAGIC.

Here is the call graph for this function:

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

B U _ R B _ D I A G N O S E _ T R E E ( )

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 103 of file rb_diag.c.

References _rb_walk(), BU_CKMAG, bu_log(), BU_RB_CKORDER, bu_rb_get_uniqueness, BU_RB_TREE_MAGIC, and WALK_NODES.

Here is the call graph for this function:

void bu_rb_summarize_tree (  bu_rb_tree *  tree  ) 
 

B U _ R B _ S U M M A R I Z E _ T R E E ( )

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 127 of file rb_diag.c.

References BU_CKMAG, bu_log(), bu_rb_data, bu_rb_get_uniqueness, BU_RB_NODE_NULL, bu_rb_order_func, bu_rb_root, and BU_RB_TREE_MAGIC.

Here is the call graph for this function:

void* bu_rb_curr (  bu_rb_tree *  tree,
int  order
) 
 

B U _ R B _ C U R R ( )

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 211 of file rb_extreme.c.

References BU_CKMAG, BU_RB_CKORDER, bu_rb_current, bu_rb_data, bu_rb_null, BU_RB_TREE_MAGIC, and NULL.

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

B U _ R B _ E X T R E M E ( )

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 99 of file rb_extreme.c.

References bu_bomb(), BU_CKMAG, bu_log(), BU_RB_CKORDER, bu_rb_data, bu_rb_null, bu_rb_root, BU_RB_TREE_MAGIC, NULL, SENSE_MAX, and SENSE_MIN.

Here is the call graph for this function:

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

B U _ R B _ N E I G H B O R ( )

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 175 of file rb_extreme.c.

References _rb_neighbor(), bu_bomb(), BU_CKMAG, bu_log(), BU_RB_CKORDER, bu_rb_current, bu_rb_data, bu_rb_null, BU_RB_TREE_MAGIC, NULL, SENSE_MAX, and SENSE_MIN.

Here is the call graph for this function:

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

B U _ R B _ F R E E ( )

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.

Definition at line 61 of file rb_free.c.

References BU_CKMAG, bu_free(), BU_LIST_WHILE, bu_rb_free_node(), bu_rb_free_package(), BU_RB_LIST_MAGIC, BU_RB_PKG_MAGIC, BU_RB_TREE_MAGIC, and rbl_node.

Here is the call graph for this function:

int bu_rb_insert (  bu_rb_tree *  tree,
void *  data
) 
 

B U _ R B _ I N S E R T ( )

Applications interface to _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 187 of file rb_insert.c.

References BU_CKMAG, bu_log(), BU_RB_DEBUG_UNIQ, bu_rb_get_uniqueness, bu_rb_search(), BU_RB_TREE_MAGIC, and NULL.

Here is the call graph for this function:

int bu_rb_is_uniq (  bu_rb_tree *  tree,
int  order
) 
 

B U _ R B _ I S _ U N I Q ( )

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 366 of file rb_insert.c.

References BU_CKMAG, BU_RB_CKORDER, bu_rb_get_uniqueness, and BU_RB_TREE_MAGIC.

void bu_rb_set_uniqv (  bu_rb_tree *  tree,
bitv_t  flag_rep
) 
 

B U _ R B _ S E T _ U N I Q V ( )

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 386 of file rb_insert.c.

References BU_CKMAG, bu_log(), bu_rb_set_uniqueness, and BU_RB_TREE_MAGIC.

Here is the call graph for this function:

void bu_rb_uniq_all_off (  bu_rb_tree *  tree  ) 
 

Definition at line 441 of file rb_insert.c.

Referenced by bu_rb_create().

void bu_rb_uniq_all_on (  bu_rb_tree *  tree  ) 
 

B U _ R B _ U N I Q _ A L L _ O N ( ) B U _ R B _ U N I Q _ A L L _ O F F ( )

Applications interface to _rb_set_uniq_all()

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

Definition at line 436 of file rb_insert.c.

int bu_rb_uniq_off (  bu_rb_tree *  tree,
int  order
) 
 

Definition at line 354 of file rb_insert.c.

int bu_rb_uniq_on (  bu_rb_tree *  tree,
int  order
) 
 

Definition at line 349 of file rb_insert.c.

int bu_rb_rank (  bu_rb_tree *  tree,
int  order
) 
 

B U _ R B _ R A N K ( )

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 124 of file rb_order_stats.c.

References BU_CKMAG, BU_RB_CKORDER, bu_rb_current, bu_rb_left_child, bu_rb_null, bu_rb_parent, bu_rb_right_child, bu_rb_root, bu_rb_size, and BU_RB_TREE_MAGIC.

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

B U _ R B _ S E L E C T ( )

Applications interface to _rb_select()

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 90 of file rb_order_stats.c.

References BU_CKMAG, bu_log(), BU_RB_CKORDER, bu_rb_current, bu_rb_data, bu_rb_null, bu_rb_root, BU_RB_TREE_MAGIC, and NULL.

Here is the call graph for this function:

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

B U _ R B _ S E A R C H ( )

Applications interface to _rb_search()

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 98 of file rb_search.c.

References BU_CKMAG, BU_RB_CKORDER, bu_rb_data, bu_rb_null, bu_rb_order_func, bu_rb_root, BU_RB_TREE_MAGIC, int, and NULL.

Referenced by bu_rb_insert().

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

B U _ R B _ W A L K ( )

Applications interface to _rb_walk()

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

Definition at line 227 of file rb_walk.c.

References _rb_walk(), BU_CKMAG, BU_RB_CKORDER, BU_RB_TREE_MAGIC, and WALK_DATA.

Here is the call graph for this function:

struct bu_rb_node* _rb_neighbor (  struct bu_rb_node *  node,
int  order,
int  sense
) 
 

_ R B _ N E I G H B O R ( )

Return a node adjacent to a given red-black node

This function has three parameters: the node of interest, the order on which to do the search, and the sense (min or max, which is to say predecessor or successor). _rb_neighbor() returns a pointer to the adjacent node. This function is modeled after the routine TREE-SUCCESSOR on p. 249 of Cormen et al.

Definition at line 133 of file rb_extreme.c.

References BU_CKMAG, bu_rb_child, BU_RB_CKORDER, bu_rb_current, bu_rb_left_child, BU_RB_NODE_MAGIC, bu_rb_null, bu_rb_parent, bu_rb_right_child, bu_rb_node::rbn_tree, and SENSE_MIN.

Referenced by bu_rb_neighbor().

void _rb_rot_left (  struct bu_rb_node *  x,
int  order
) 
 

_ R B _ R O T _ L E F T ( )

Perfrom left rotation on a red-black tree

This function has two parameters: the node about which to rotate and the order to be rotated. _rb_rot_left() is an implementation of the routine called LEFT-ROTATE on p. 266 of Cormen et al, with modification on p. 285.

Definition at line 62 of file rb_rotate.c.

References BU_CKMAG, bu_log(), BU_RB_CKORDER, BU_RB_DEBUG_OS, BU_RB_DEBUG_ROTATE, bu_rb_left_child, BU_RB_NODE_MAGIC, bu_rb_null, bu_rb_parent, bu_rb_right_child, bu_rb_root, bu_rb_size, and bu_rb_node::rbn_tree.

Here is the call graph for this function:

void _rb_rot_right (  struct bu_rb_node *  y,
int  order
) 
 

_ R B _ R O T _ R I G H T ( )

Perfrom right rotation on a red-black tree

This function has two parameters: the node about which to rotate and the order to be rotated. _rb_rot_right() is hacked from _rb_rot_left() above.

Definition at line 110 of file rb_rotate.c.

References BU_CKMAG, bu_log(), BU_RB_CKORDER, BU_RB_DEBUG_OS, BU_RB_DEBUG_ROTATE, bu_rb_left_child, BU_RB_NODE_MAGIC, bu_rb_null, bu_rb_parent, bu_rb_right_child, bu_rb_root, bu_rb_size, and bu_rb_node::rbn_tree.

Here is the call graph for this function:

void _rb_walk (  bu_rb_tree *  tree,
int  order,
void(*)()  visit,
int  what_to_visit,
int  trav_type
) 
 

_ R B _ W A L K ( )

Traverse a red-black tree

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

N.B. _rb_walk() is not declared static because it is called by bu_rb_diagnose_tree() in rb_diag.c.

Definition at line 183 of file rb_walk.c.

References bu_bomb(), BU_CKMAG, bu_log(), BU_RB_CKORDER, bu_rb_root, BU_RB_TREE_MAGIC, INORDER, POSTORDER, PREORDER, void(), WALK_DATA, and WALK_NODES.

Referenced by bu_rb_diagnose_tree(), and bu_rb_walk().

Here is the call graph for this function:

void bu_rb_free_node (  struct bu_rb_node *  node  ) 
 

B U _ R B _ F R E E _ N O D E ( )

Relinquish memory occupied by a red-black node

This function has one parameter: a node to free. bu_rb_free_node() frees the memory allocated for the various members of the node and then frees the memory allocated for the node itself.

Definition at line 118 of file rb_free.c.

References BU_CKMAG, bu_free(), BU_LIST_DEQUEUE, bu_rb_current, BU_RB_LIST_MAGIC, BU_RB_NODE_MAGIC, and bu_rb_null.

Referenced by bu_rb_free().

Here is the call graph for this function:

void bu_rb_free_package (  struct bu_rb_package *  package  ) 
 

B U _ R B _ F R E E _ P A C K A G E ( )

Relinquish memory occupied by a red-black package

This function has one parameter: a package to free. bu_rb_free_package() frees the memory allocated to point to the nodes that contained the package and then frees the memory allocated for the package itself.

Definition at line 153 of file rb_free.c.

References BU_CKMAG, bu_free(), BU_LIST_DEQUEUE, BU_RB_LIST_MAGIC, and BU_RB_PKG_MAGIC.

Referenced by bu_rb_delete(), and bu_rb_free().

Here is the call graph for this function:

Generated on Mon Sep 18 01:25:21 2006 for BRL-CAD by  doxygen 1.4.6