BRL-CAD
rb_diag.c
Go to the documentation of this file.
1 /* R B _ D I A G . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1998-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 #include "common.h"
22 
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <math.h>
26 
27 #include "bu/rb.h"
28 #include "./rb_internals.h"
29 
30 
31 static int d_order; /* Used by describe_node() */
32 
33 
34 /**
35  * Print out the contents of a red-black node
36  *
37  * This function has two parameters: the node to describe and its
38  * depth in the tree. _rb_describe_node() is intended to be called by
39  * bu_rb_diagnose_tree().
40  */
41 HIDDEN void
42 _rb_describe_node(struct bu_rb_node *node, int depth)
43 {
44  struct bu_rb_tree *tree;
45  struct bu_rb_package *package;
46  void (*pp)(void *, const int); /* Pretty print function */
47 
48  BU_CKMAG(node, BU_RB_NODE_MAGIC, "red-black node");
49  tree = node->rbn_tree;
50  RB_CKORDER(tree, d_order);
51 
52  package = (node->rbn_package)[d_order];
53  pp = (void (*)(void *, const int))tree->rbt_print;
54 
55  bu_log("%*snode <%p>...\n", depth * 2, "", (void*)node);
56  bu_log("%*s tree: <%p>\n", depth * 2, "", (void*)node->rbn_tree);
57  bu_log("%*s parent: <%p>\n", depth * 2, "", (void*)RB_PARENT(node, d_order));
58  bu_log("%*s left: <%p>\n", depth * 2, "", (void*)RB_LEFT_CHILD(node, d_order));
59  bu_log("%*s right: <%p>\n", depth * 2, "", (void*)RB_RIGHT_CHILD(node, d_order));
60  bu_log("%*s color: %s\n", depth * 2, "", (RB_GET_COLOR(node, d_order) == RB_RED) ? "RED" : (RB_GET_COLOR(node, d_order) == RB_BLK) ? "BLACK" : "Huh?");
61  bu_log("%*s package: <%p>\n", depth * 2, "", (void*)package);
62 
63  if ((pp != 0) && (package != BU_RB_PKG_NULL))
64  (*pp)(package->rbp_data, depth);
65  else
66  bu_log("\n");
67 }
68 
69 
70 void
71 bu_rb_diagnose_tree(struct bu_rb_tree *tree, int order, int trav_type)
72 {
73  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
74  RB_CKORDER(tree, order);
75 
76  bu_log("-------- Red-black tree <%p> contents --------\n", (void*)tree);
77  bu_log("Description: '%s'\n", tree->rbt_description);
78  bu_log("Order: %d of %d\n", order, tree->rbt_nm_orders);
79  bu_log("Current: <%p>\n", (void*)tree->rbt_current);
80  bu_log("Empty node: <%p>\n", (void*)tree->rbt_empty_node);
81  bu_log("Uniqueness?: %s\n", RB_GET_UNIQUENESS(tree, order) ? "Yes" : "No");
82  d_order = order;
84  WALK_NODES, trav_type);
85  bu_log("--------------------------------------------------\n");
86 }
87 
88 void
90 {
91  int i;
92 
93  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
94 
95  bu_log("-------- Red-black tree <%p> summary --------\n", (void*)tree);
96  bu_log("Description: '%s'\n", tree->rbt_description);
97  bu_log("Current: <%p>\n", (void*)tree->rbt_current);
98  bu_log("Empty node: <%p>\n", (void*)tree->rbt_empty_node);
99  bu_log("Size (in nodes): %d\n", tree->rbt_nm_nodes);
100  bu_log("Number of orders: %d\n", tree->rbt_nm_orders);
101  bu_log("Debug bits: <0x%X>\n", tree->rbt_debug);
102  if ((tree->rbt_nm_orders > 0) && (tree->rbt_nm_nodes > 0)) {
103  bu_log("\n");
104  bu_log(" Order Attributes\n");
105  bu_log("\n");
106  bu_log("+-------+------------------+-----------+--------------+--------------+--------------+\n");
107  bu_log("| Order | Compare Function | Unique? | Root | Package | Data |\n");
108  bu_log("+-------+------------------+-----------+--------------+--------------+--------------+\n");
109  for (i = 0; i < tree->rbt_nm_orders; ++i) {
110  bu_log("| %3d | <%010p> | %-3.3s | <%010p> | <%010p> | <%010p> |\n",
111  i,
112  RB_COMPARE_FUNC(tree, i),
113  RB_GET_UNIQUENESS(tree, i) ? "Yes" : "No",
114  (void *)RB_ROOT(tree, i),
115  (RB_ROOT(tree, i) == BU_RB_NODE_NULL) ? NULL : (void *)(RB_ROOT(tree, i)->rbn_package)[i],
116  (RB_ROOT(tree, i) == BU_RB_NODE_NULL) ? NULL : RB_DATA(RB_ROOT(tree, i), i));
117  }
118  bu_log("+-------+------------------+-----------+--------------+--------------+--------------+\n");
119  }
120  bu_log("\n");
121 }
122 
123 
124 /*
125  * Local Variables:
126  * mode: C
127  * tab-width: 8
128  * indent-tabs-mode: t
129  * c-file-style: "stroustrup"
130  * End:
131  * ex: shiftwidth=4 tabstop=8
132  */
#define RB_PARENT(n, o)
Definition: rb_internals.h:60
#define RB_RIGHT_CHILD(n, o)
Definition: rb_internals.h:62
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
void bu_rb_summarize_tree(struct bu_rb_tree *tree)
Definition: rb_diag.c:89
Definition: rb.h:109
#define BU_CKMAG(_ptr, _magic, _str)
Definition: magic.h:233
Definition: rb.h:204
#define BU_RB_NODE_NULL
Definition: rb.h:217
struct bu_rb_node * rbt_empty_node
Definition: rb.h:127
#define BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG(_func)
Definition: rb.h:558
#define RB_RED
Definition: rb_internals.h:80
Header file for the BRL-CAD common definitions.
#define RB_LEFT_CHILD(n, o)
Definition: rb_internals.h:61
struct bu_rb_node * rbt_current
Definition: rb.h:124
#define HIDDEN
Definition: common.h:86
#define BU_RB_NODE_MAGIC
Definition: magic.h:61
#define RB_GET_COLOR(n, o)
Definition: rb_internals.h:72
void bu_rb_diagnose_tree(struct bu_rb_tree *tree, int order, int trav_type)
Definition: rb_diag.c:71
const char * rbt_description
Definition: rb.h:117
HIDDEN void _rb_describe_node(struct bu_rb_node *node, int depth)
Definition: rb_diag.c:42
#define WALK_NODES
Definition: rb_internals.h:88
#define BU_RB_TREE_MAGIC
Definition: magic.h:63
struct bu_rb_tree * rbn_tree
Definition: rb.h:207
#define RB_CKORDER(t, o)
Definition: rb_internals.h:33
#define RB_ROOT(t, o)
Definition: rb_internals.h:46
void * rbp_data
Definition: rb.h:193
int rbt_nm_orders
Definition: rb.h:120
#define BU_RB_PKG_NULL
Definition: rb.h:195
#define RB_COMPARE_FUNC(t, o)
Definition: rb_internals.h:44
int rbt_nm_nodes
Definition: rb.h:112
#define RB_BLK
Definition: rb_internals.h:81
void(* rbt_print)(void *)
Definition: rb.h:115
#define RB_GET_UNIQUENESS(t, o)
Definition: rb_internals.h:49
void rb_walk(struct bu_rb_tree *tree, int order, void(*visit)(void), int what_to_visit, int trav_type)
Definition: rb_walk.c:193
#define RB_DATA(n, o)
Definition: rb_internals.h:82
int rbt_debug
Definition: rb.h:116