BRL-CAD
rb_walk.c
Go to the documentation of this file.
1 /* R B _ W A L K . 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 /**
32  * Perform a preorder traversal of a red-black tree
33  */
34 HIDDEN void
35 prewalknodes(struct bu_rb_node *root,
36  int order,
37  void (*visit)(void),
38  int depth)
39 {
40  /* need function pointer for recasting visit for actual use as a function */
42  /* make the cast */
43  _visit = BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC(visit);
44 
45  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
46  RB_CKORDER(root->rbn_tree, order);
47 
48  if (root == RB_NULL(root->rbn_tree))
49  return;
50 
51  _visit(root, depth);
52 
53  prewalknodes(RB_LEFT_CHILD(root, order), order, visit, depth + 1);
54  prewalknodes(RB_RIGHT_CHILD(root, order), order, visit, depth + 1);
55 }
56 
57 
58 /**
59  * Perform an inorder traversal of a red-black tree
60  */
61 HIDDEN void
62 inwalknodes(struct bu_rb_node *root,
63  int order,
64  void (*visit)(void),
65  int depth)
66 {
67  /* need function pointer for recasting visit for actual use as a function */
69  /* make the cast */
70  _visit = BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC(visit);
71 
72  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
73  RB_CKORDER(root->rbn_tree, order);
74 
75  if (root == RB_NULL(root->rbn_tree))
76  return;
77  inwalknodes(RB_LEFT_CHILD(root, order), order, visit, depth + 1);
78 
79  _visit(root, depth);
80 
81  inwalknodes(RB_RIGHT_CHILD(root, order), order, visit, depth + 1);
82 }
83 
84 
85 /**
86  * Perform a postorder traversal of a red-black tree
87  */
88 HIDDEN void
90  int order,
91  void (*visit)(void),
92  int depth)
93 {
94  /* need function pointer for recasting visit for actual use as a function */
96  /* make the cast */
97  _visit = BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC(visit);
98 
99  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
100  RB_CKORDER(root->rbn_tree, order);
101 
102  if (root == RB_NULL(root->rbn_tree))
103  return;
104 
105  postwalknodes(RB_LEFT_CHILD(root, order), order, visit, depth + 1);
106  postwalknodes(RB_RIGHT_CHILD(root, order), order, visit, depth + 1);
107 
108  _visit(root, depth);
109 }
110 
111 
112 /**
113  * Perform a preorder traversal of a red-black tree
114  */
115 HIDDEN void
116 prewalkdata(struct bu_rb_node *root,
117  int order,
118  void (*visit)(void),
119  int depth)
120 {
121  /* need function pointer for recasting visit for actual use as a function */
123  /* make the cast */
124  _visit = BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC(visit);
125 
126  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
127  RB_CKORDER(root->rbn_tree, order);
128 
129  if (root == RB_NULL(root->rbn_tree))
130  return;
131 
132  _visit(RB_DATA(root, order), depth);
133 
134  prewalkdata(RB_LEFT_CHILD(root, order), order, visit, depth + 1);
135  prewalkdata(RB_RIGHT_CHILD(root, order), order, visit, depth + 1);
136 }
137 
138 
139 /**
140  * Perform an inorder traversal of a red-black tree
141  */
142 HIDDEN void
143 inwalkdata(struct bu_rb_node *root,
144  int order,
145  void (*visit)(void),
146  int depth)
147 {
148  /* need function pointer for recasting visit for actual use as a function */
150  /* make the cast */
151  _visit = BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC(visit);
152 
153  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
154  RB_CKORDER(root->rbn_tree, order);
155 
156  if (root == RB_NULL(root->rbn_tree))
157  return;
158  inwalkdata(RB_LEFT_CHILD(root, order), order, visit, depth + 1);
159 
160  _visit(RB_DATA(root, order), depth);
161 
162  inwalkdata(RB_RIGHT_CHILD(root, order), order, visit, depth + 1);
163 }
164 
165 
166 /**
167  * Perform a postorder traversal of a red-black tree
168  */
169 HIDDEN void
171  int order,
172  void (*visit)(void),
173  int depth)
174 {
175  /* need function pointer for recasting visit for actual use as a function */
177  /* make the cast */
178  _visit = BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC(visit);
179 
180  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
181  RB_CKORDER(root->rbn_tree, order);
182 
183  if (root == RB_NULL(root->rbn_tree))
184  return;
185  postwalkdata(RB_LEFT_CHILD(root, order), order, visit, depth + 1);
186  postwalkdata(RB_RIGHT_CHILD(root, order), order, visit, depth + 1);
187 
188  _visit(RB_DATA(root, order), depth);
189 }
190 
191 
192 void
194  int order,
195  void (*visit)(void),
196  int what_to_visit,
197  int trav_type)
198 {
199  static void (*walk[][3])(void) = {
203  },
207  }
208  };
209 
210  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
211  RB_CKORDER(tree, order);
212  switch (trav_type) {
213  case BU_RB_WALK_PREORDER:
214  case BU_RB_WALK_INORDER:
216  switch (what_to_visit) {
217  case WALK_NODES:
218  case WALK_DATA: {
219  BU_RB_WALK_FUNC_FUNC_DECL(_walk_func);
220  _walk_func = BU_RB_WALK_FUNC_CAST_AS_FUNC_FUNC(walk[what_to_visit][trav_type]);
221  _walk_func(RB_ROOT(tree, order), order, visit, 0);
222  }
223  break;
224  default:
225  bu_log("ERROR: rb_walk(): Illegal visitation object: %d\n",
226  what_to_visit);
227  bu_bomb("");
228  }
229  break;
230  default:
231  bu_log("ERROR: rb_walk(): Illegal traversal type: %d\n",
232  trav_type);
233  bu_bomb("");
234  }
235 }
236 
237 void
238 bu_rb_walk(struct bu_rb_tree *tree,
239  int order,
240  void (*visit)(void),
241  int trav_type)
242 {
243  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
244  RB_CKORDER(tree, order);
245 
246  rb_walk(tree, order, visit, WALK_DATA, trav_type);
247 }
248 
249 
250 /*
251  * Local Variables:
252  * mode: C
253  * tab-width: 8
254  * indent-tabs-mode: t
255  * c-file-style: "stroustrup"
256  * End:
257  * ex: shiftwidth=4 tabstop=8
258  */
#define RB_RIGHT_CHILD(n, o)
Definition: rb_internals.h:62
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
#define WALK_DATA
Definition: rb_internals.h:89
Definition: rb.h:109
#define BU_CKMAG(_ptr, _magic, _str)
Definition: magic.h:233
#define BU_RB_WALK_FUNC_NODE_DECL(_func)
Definition: rb.h:562
Definition: rb.h:204
#define BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG(_func)
Definition: rb.h:558
HIDDEN void inwalkdata(struct bu_rb_node *root, int order, void(*visit)(void), int depth)
Definition: rb_walk.c:143
Header file for the BRL-CAD common definitions.
#define RB_LEFT_CHILD(n, o)
Definition: rb_internals.h:61
#define RB_NULL(t)
Definition: rb_internals.h:48
#define BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC(_func)
Definition: rb.h:559
#define HIDDEN
Definition: common.h:86
#define BU_RB_NODE_MAGIC
Definition: magic.h:61
#define BU_RB_WALK_FUNC_DATA_DECL(_func)
Definition: rb.h:563
#define BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC(_func)
Definition: rb.h:560
#define WALK_NODES
Definition: rb_internals.h:88
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 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
#define BU_RB_WALK_FUNC_FUNC_DECL(_func)
Definition: rb.h:564
HIDDEN void inwalknodes(struct bu_rb_node *root, int order, void(*visit)(void), int depth)
Definition: rb_walk.c:62
#define BU_RB_WALK_FUNC_CAST_AS_FUNC_FUNC(_func)
Definition: rb.h:561
HIDDEN void postwalknodes(struct bu_rb_node *root, int order, void(*visit)(void), int depth)
Definition: rb_walk.c:89
#define RB_DATA(n, o)
Definition: rb_internals.h:82
HIDDEN void prewalkdata(struct bu_rb_node *root, int order, void(*visit)(void), int depth)
Definition: rb_walk.c:116
HIDDEN void postwalkdata(struct bu_rb_node *root, int order, void(*visit)(void), int depth)
Definition: rb_walk.c:170
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
void bu_rb_walk(struct bu_rb_tree *tree, int order, void(*visit)(void), int trav_type)
Definition: rb_walk.c:238
HIDDEN void prewalknodes(struct bu_rb_node *root, int order, void(*visit)(void), int depth)
Definition: rb_walk.c:35