BRL-CAD
#include "common.h"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "bu/rb.h"
#include "./rb_internals.h"
Include dependency graph for rb_walk.c:

Go to the source code of this file.

Functions

HIDDEN void prewalknodes (struct bu_rb_node *root, int order, void(*visit)(void), int depth)
 
HIDDEN void inwalknodes (struct bu_rb_node *root, int order, void(*visit)(void), int depth)
 
HIDDEN void postwalknodes (struct bu_rb_node *root, int order, void(*visit)(void), int depth)
 
HIDDEN void prewalkdata (struct bu_rb_node *root, int order, void(*visit)(void), int depth)
 
HIDDEN void inwalkdata (struct bu_rb_node *root, int order, void(*visit)(void), int depth)
 
HIDDEN void postwalkdata (struct bu_rb_node *root, int order, void(*visit)(void), int depth)
 
void rb_walk (struct bu_rb_tree *tree, int order, void(*visit)(void), int what_to_visit, int trav_type)
 
void bu_rb_walk (struct bu_rb_tree *tree, int order, void(*visit)(void), int trav_type)
 

Detailed Description

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

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.

Definition in file rb_walk.c.

Function Documentation

HIDDEN void prewalknodes ( struct bu_rb_node root,
int  order,
void(*)(void)  visit,
int  depth 
)

Perform a preorder traversal of a red-black tree

Definition at line 35 of file rb_walk.c.

References BU_CKMAG, BU_RB_NODE_MAGIC, BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC, BU_RB_WALK_FUNC_NODE_DECL, RB_CKORDER, RB_LEFT_CHILD, RB_NULL, RB_RIGHT_CHILD, and bu_rb_node::rbn_tree.

Referenced by rb_walk().

HIDDEN void inwalknodes ( struct bu_rb_node root,
int  order,
void(*)(void)  visit,
int  depth 
)

Perform an inorder traversal of a red-black tree

Definition at line 62 of file rb_walk.c.

References BU_CKMAG, BU_RB_NODE_MAGIC, BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC, BU_RB_WALK_FUNC_NODE_DECL, RB_CKORDER, RB_LEFT_CHILD, RB_NULL, RB_RIGHT_CHILD, and bu_rb_node::rbn_tree.

Referenced by rb_walk().

HIDDEN void postwalknodes ( struct bu_rb_node root,
int  order,
void(*)(void)  visit,
int  depth 
)

Perform a postorder traversal of a red-black tree

Definition at line 89 of file rb_walk.c.

References BU_CKMAG, BU_RB_NODE_MAGIC, BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC, BU_RB_WALK_FUNC_NODE_DECL, RB_CKORDER, RB_LEFT_CHILD, RB_NULL, RB_RIGHT_CHILD, and bu_rb_node::rbn_tree.

Referenced by rb_walk().

HIDDEN void prewalkdata ( struct bu_rb_node root,
int  order,
void(*)(void)  visit,
int  depth 
)

Perform a preorder traversal of a red-black tree

Definition at line 116 of file rb_walk.c.

References BU_CKMAG, BU_RB_NODE_MAGIC, BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC, BU_RB_WALK_FUNC_DATA_DECL, RB_CKORDER, RB_DATA, RB_LEFT_CHILD, RB_NULL, RB_RIGHT_CHILD, and bu_rb_node::rbn_tree.

Referenced by rb_walk().

HIDDEN void inwalkdata ( struct bu_rb_node root,
int  order,
void(*)(void)  visit,
int  depth 
)

Perform an inorder traversal of a red-black tree

Definition at line 143 of file rb_walk.c.

References BU_CKMAG, BU_RB_NODE_MAGIC, BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC, BU_RB_WALK_FUNC_DATA_DECL, RB_CKORDER, RB_DATA, RB_LEFT_CHILD, RB_NULL, RB_RIGHT_CHILD, and bu_rb_node::rbn_tree.

Referenced by rb_walk().

HIDDEN void postwalkdata ( struct bu_rb_node root,
int  order,
void(*)(void)  visit,
int  depth 
)

Perform a postorder traversal of a red-black tree

Definition at line 170 of file rb_walk.c.

References BU_CKMAG, BU_RB_NODE_MAGIC, BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC, BU_RB_WALK_FUNC_DATA_DECL, RB_CKORDER, RB_DATA, RB_LEFT_CHILD, RB_NULL, RB_RIGHT_CHILD, and bu_rb_node::rbn_tree.

Referenced by rb_walk().

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: