BRL-CAD
rb_internals.h File Reference
#include "common.h"
#include "bu/log.h"
#include "bu/malloc.h"
Include dependency graph for rb_internals.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define LIBBU_RB_INTERNALS_H   seen
 
#define RB_CKORDER(t, o)
 
#define RB_COMPARE_FUNC(t, o)   (((t)->rbt_compar)[o])
 
#define RB_PRINT(t, p)   (((t)->rbt_print)((p)->rbp_data))
 
#define RB_ROOT(t, o)   (((t)->rbt_root)[o])
 
#define RB_CURRENT(t)   ((t)->rbt_current)
 
#define RB_NULL(t)   ((t)->rbt_empty_node)
 
#define RB_GET_UNIQUENESS(t, o)   ((((t)->rbt_unique)[(o)/8] & (0x1 << ((o) % 8))) ? 1 : 0)
 
#define RB_SET_UNIQUENESS(t, o, u)
 
#define RB_PARENT(n, o)   (((n)->rbn_parent)[o])
 
#define RB_LEFT_CHILD(n, o)   (((n)->rbn_left)[o])
 
#define RB_RIGHT_CHILD(n, o)   (((n)->rbn_right)[o])
 
#define RB_LEFT   0
 
#define RB_RIGHT   1
 
#define RB_CHILD(n, o, d)
 
#define RB_OTHER_CHILD(n, o, d)
 
#define RB_SIZE(n, o)   (((n)->rbn_size)[o])
 
#define RB_GET_COLOR(n, o)   ((((n)->rbn_color)[(o)/8] & (0x1 << ((o) % 8))) ? 1 : 0)
 
#define RB_SET_COLOR(n, o, c)
 
#define RB_RED   0
 
#define RB_BLK   1
 
#define RB_DATA(n, o)   (((n)->rbn_package)[o]->rbp_data)
 
#define WALK_NODES   0
 
#define WALK_DATA   1
 
#define RB_ROTATE(n, o, d)
 
#define RB_OTHER_ROTATE(n, o, d)
 

Functions

struct bu_rb_noderb_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 (struct bu_rb_tree *tree, int order, void(*visit)(void), int what_to_visit, int trav_type)
 
void rb_free_node (struct bu_rb_node *node)
 
void rb_free_package (struct bu_rb_package *package)
 

Macro Definition Documentation

#define LIBBU_RB_INTERNALS_H   seen

Definition at line 24 of file rb_internals.h.

#define RB_CKORDER (   t,
 
)
Value:
if (UNLIKELY(((o) < 0) || ((o) >= (t)->rbt_nm_orders))) { \
char buf[128] = {0}; \
snprintf(buf, 128, "ERROR: Order %d outside 0..%d (nm_orders-1), file %s, line %d\n", \
(o), (t)->rbt_nm_orders - 1, __FILE__, __LINE__); \
bu_bomb(buf); \
}
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
#define UNLIKELY(expression)
Definition: common.h:282

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

Definition at line 33 of file rb_internals.h.

Referenced by _rb_delete(), _rb_describe_node(), _rb_extreme(), _rb_fixup(), _rb_insert(), _rb_search(), _rb_set_uniq(), 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(), bu_rb_walk(), inwalkdata(), inwalknodes(), postwalkdata(), postwalknodes(), prewalkdata(), prewalknodes(), rb_neighbor(), rb_rot_left(), rb_rot_right(), and rb_walk().

#define RB_COMPARE_FUNC (   t,
 
)    (((t)->rbt_compar)[o])

Definition at line 44 of file rb_internals.h.

Referenced by _rb_insert(), bu_rb_search(), and bu_rb_summarize_tree().

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

Definition at line 45 of file rb_internals.h.

#define RB_ROOT (   t,
 
)    (((t)->rbt_root)[o])
#define RB_CURRENT (   t)    ((t)->rbt_current)
#define RB_GET_UNIQUENESS (   t,
 
)    ((((t)->rbt_unique)[(o)/8] & (0x1 << ((o) % 8))) ? 1 : 0)
#define RB_SET_UNIQUENESS (   t,
  o,
 
)
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 50 of file rb_internals.h.

Referenced by _rb_set_uniq(), _rb_set_uniq_all(), and bu_rb_set_uniqv().

#define RB_PARENT (   n,
 
)    (((n)->rbn_parent)[o])
#define RB_LEFT   0

Definition at line 63 of file rb_internals.h.

Referenced by _rb_fixup(), and _rb_insert().

#define RB_RIGHT   1

Definition at line 64 of file rb_internals.h.

Referenced by _rb_fixup(), and _rb_insert().

#define RB_CHILD (   n,
  o,
 
)
Value:
(((d) == RB_LEFT) ? \
RB_LEFT_CHILD((n), (o)) : \
RB_RIGHT_CHILD((n), (o)))
#define RB_RIGHT_CHILD(n, o)
Definition: rb_internals.h:62
#define RB_LEFT
Definition: rb_internals.h:63
#define RB_LEFT_CHILD(n, o)
Definition: rb_internals.h:61

Definition at line 65 of file rb_internals.h.

Referenced by _rb_fixup(), and rb_neighbor().

#define RB_OTHER_CHILD (   n,
  o,
 
)
Value:
(((d) == RB_LEFT) ? \
RB_RIGHT_CHILD((n), (o)) : \
RB_LEFT_CHILD((n), (o)))
#define RB_RIGHT_CHILD(n, o)
Definition: rb_internals.h:62
#define RB_LEFT
Definition: rb_internals.h:63
#define RB_LEFT_CHILD(n, o)
Definition: rb_internals.h:61

Definition at line 68 of file rb_internals.h.

Referenced by _rb_fixup(), and _rb_insert().

#define RB_SIZE (   n,
 
)    (((n)->rbn_size)[o])
#define RB_GET_COLOR (   n,
 
)    ((((n)->rbn_color)[(o)/8] & (0x1 << ((o) % 8))) ? 1 : 0)

Definition at line 72 of file rb_internals.h.

Referenced by _rb_delete(), _rb_describe_node(), _rb_fixup(), and _rb_insert().

#define RB_SET_COLOR (   n,
  o,
 
)
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 74 of file rb_internals.h.

Referenced by _rb_fixup(), _rb_insert(), bu_rb_create(), and bu_rb_insert().

#define RB_RED   0

Definition at line 80 of file rb_internals.h.

Referenced by _rb_describe_node(), _rb_fixup(), and _rb_insert().

#define RB_BLK   1
#define RB_DATA (   n,
 
)    (((n)->rbn_package)[o]->rbp_data)
#define WALK_NODES   0

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

Definition at line 88 of file rb_internals.h.

Referenced by bu_rb_diagnose_tree(), and rb_walk().

#define WALK_DATA   1

Definition at line 89 of file rb_internals.h.

Referenced by bu_rb_walk(), and rb_walk().

#define RB_ROTATE (   n,
  o,
 
)
Value:
(((d) == RB_LEFT) ? \
rb_rot_left((n), (o)) : \
rb_rot_right((n), (o)))
void rb_rot_right(struct bu_rb_node *y, int order)
Definition: rb_rotate.c:73
#define RB_LEFT
Definition: rb_internals.h:63
void rb_rot_left(struct bu_rb_node *x, int order)
Definition: rb_rotate.c:32

This macro has 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 96 of file rb_internals.h.

Referenced by _rb_fixup(), and _rb_insert().

#define RB_OTHER_ROTATE (   n,
  o,
 
)
Value:
(((d) == RB_LEFT) ? \
rb_rot_right((n), (o)) : \
rb_rot_left((n), (o)))
void rb_rot_right(struct bu_rb_node *y, int order)
Definition: rb_rotate.c:73
#define RB_LEFT
Definition: rb_internals.h:63
void rb_rot_left(struct bu_rb_node *x, int order)
Definition: rb_rotate.c:32

This macro has 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 105 of file rb_internals.h.

Referenced by _rb_fixup(), and _rb_insert().

Function Documentation

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

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

References _rb_extreme(), BU_CKMAG, BU_RB_NODE_MAGIC, RB_CHILD, RB_CKORDER, RB_CURRENT, RB_LEFT_CHILD, RB_NULL, RB_PARENT, RB_RIGHT_CHILD, bu_rb_node::rbn_tree, and SENSE_MIN.

Referenced by _rb_delete(), and bu_rb_neighbor().

Here is the call graph for this function:

void rb_rot_left ( struct bu_rb_node x,
int  order 
)

Perform 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 32 of file rb_rotate.c.

References BU_CKMAG, bu_log(), BU_RB_DEBUG_OS, BU_RB_DEBUG_ROTATE, BU_RB_NODE_MAGIC, RB_CKORDER, RB_LEFT_CHILD, RB_NULL, RB_PARENT, RB_RIGHT_CHILD, RB_ROOT, RB_SIZE, bu_rb_node::rbn_tree, bu_rb_tree::rbt_debug, and UNLIKELY.

Here is the call graph for this function:

void rb_rot_right ( struct bu_rb_node y,
int  order 
)

Perform 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 73 of file rb_rotate.c.

References BU_CKMAG, bu_log(), BU_RB_DEBUG_OS, BU_RB_DEBUG_ROTATE, BU_RB_NODE_MAGIC, RB_CKORDER, RB_LEFT_CHILD, RB_NULL, RB_PARENT, RB_RIGHT_CHILD, RB_ROOT, RB_SIZE, bu_rb_node::rbn_tree, bu_rb_tree::rbt_debug, and UNLIKELY.

Here is the call graph for this function:

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

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 193 of file rb_walk.c.

References bu_bomb(), BU_CKMAG, bu_log(), BU_RB_TREE_MAGIC, BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG, BU_RB_WALK_FUNC_CAST_AS_FUNC_FUNC, BU_RB_WALK_FUNC_FUNC_DECL, BU_RB_WALK_INORDER, BU_RB_WALK_POSTORDER, BU_RB_WALK_PREORDER, inwalkdata(), inwalknodes(), postwalkdata(), postwalknodes(), prewalkdata(), prewalknodes(), RB_CKORDER, RB_ROOT, WALK_DATA, and WALK_NODES.

Referenced by bu_rb_diagnose_tree(), and bu_rb_walk().

Here is the call graph for this function:

void rb_free_node ( struct bu_rb_node node)

Relinquish memory occupied by a red-black node

This function has one parameter: a node to free. 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 81 of file rb_free.c.

References BU_CKMAG, bu_free(), BU_LIST_DEQUEUE, BU_RB_LIST_MAGIC, BU_RB_NODE_MAGIC, bu_rb_list::l, RB_CURRENT, RB_NULL, bu_rb_node::rbn_color, bu_rb_node::rbn_left, bu_rb_node::rbn_list_pos, bu_rb_node::rbn_package, bu_rb_node::rbn_parent, bu_rb_node::rbn_right, bu_rb_node::rbn_size, and bu_rb_node::rbn_tree.

Referenced by _rb_delete(), and bu_rb_free().

Here is the call graph for this function:

void rb_free_package ( struct bu_rb_package package)

Relinquish memory occupied by a red-black package

This function has one parameter: a package to free. 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 111 of file rb_free.c.

References BU_CKMAG, bu_free(), BU_LIST_DEQUEUE, BU_RB_LIST_MAGIC, BU_RB_PKG_MAGIC, bu_rb_list::l, bu_rb_package::rbp_list_pos, and bu_rb_package::rbp_node.

Referenced by bu_rb_delete(), and bu_rb_free().

Here is the call graph for this function: