BRL-CAD
db_walk.c
Go to the documentation of this file.
1 /* D B _ W A L K . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1988-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 /** @addtogroup dbio */
21 /** @{ */
22 /** @file librt/db_walk.c
23  *
24  * No-frills tree-walker.
25  *
26  */
27 
28 #include "common.h"
29 
30 #include <string.h>
31 #include "bio.h"
32 
33 #include "vmath.h"
34 #include "db.h"
35 #include "raytrace.h"
36 
37 
38 /**
39  * A generic traversal function.
40  */
41 void
43  void (*traverse_func) (struct directory *, struct db_traverse *),
44  struct db_traverse *dtp)
45 {
46  struct directory *dp;
47 
48  if (!tp)
49  return;
50 
51  RT_CK_DB_TRAVERSE(dtp);
52  RT_CHECK_DBI(dtp->dbip);
53  RT_CK_TREE(tp);
54  if (dtp->resp) {
55  RT_CK_RESOURCE(dtp->resp);
56  }
57 
58  switch (tp->tr_op) {
59 
60  case OP_DB_LEAF:
61  if ((dp=db_lookup(dtp->dbip, tp->tr_l.tl_name, LOOKUP_NOISY)) == RT_DIR_NULL)
62  return;
63  traverse_func(dp, dtp);
64  break;
65 
66  case OP_UNION:
67  case OP_INTERSECT:
68  case OP_SUBTRACT:
69  case OP_XOR:
70  db_traverse_subtree(tp->tr_b.tb_left, traverse_func, dtp);
71  db_traverse_subtree(tp->tr_b.tb_right, traverse_func, dtp);
72  break;
73  default:
74  bu_log("db_functree_subtree: unrecognized operator %d\n", tp->tr_op);
75  bu_bomb("db_functree_subtree: unrecognized operator\n");
76  }
77 }
78 
79 
80 /*
81  * This subroutine is called for a no-frills tree-walk,
82  * with the provided subroutines being called when entering and
83  * exiting combinations and at leaf (solid) nodes.
84  *
85  * This routine is recursive, so no variables may be declared static.
86  *
87  */
88 void
90  struct db_traverse *dtp)
91 {
92  register size_t i;
93  RT_CK_DB_TRAVERSE(dtp);
94  RT_CK_DBI(dtp->dbip);
95  if (dtp->resp) {
96  RT_CK_RESOURCE(dtp->resp);
97  }
98 
99  if (RT_G_DEBUG & DEBUG_DB)
100  bu_log("db_preorder_traverse(%s) %p, %p, comb_enter=%lx, comb_exit=%lx, leaf=%lx, client_data=%p\n",
101  dp->d_namep,
102  (void *)dtp->dbip, (void *)dp,
103  (long unsigned int)dtp->comb_enter_func, (long unsigned int)dtp->comb_exit_func, (long unsigned int)dtp->leaf_func,
104  dtp->client_data);
105 
106  if (dp->d_flags & RT_DIR_COMB) {
107  /* entering region */
108  if (dtp->comb_enter_func)
109  dtp->comb_enter_func(dtp->dbip, dp, dtp->client_data);
110  if (db_version(dtp->dbip) < 5) {
111  register union record *rp;
112  register struct directory *mdp;
113  /*
114  * Load the combination into local record buffer
115  * This is in external v4 format.
116  */
117  if ((rp = db_getmrec(dtp->dbip, dp)) == (union record *)0)
118  return;
119  /* recurse */
120  for (i=1; i < dp->d_len; i++) {
121  if ((mdp = db_lookup(dtp->dbip, rp[i].M.m_instname,
123  continue;
124  db_preorder_traverse(mdp, dtp);
125  }
126  bu_free((char *)rp, "db_preorder_traverse[]");
127  } else {
128  struct rt_db_internal in;
129  struct rt_comb_internal *comb;
130 
131  if (rt_db_get_internal5(&in, dp, dtp->dbip, NULL, dtp->resp) < 0)
132  return;
133 
134  comb = (struct rt_comb_internal *)in.idb_ptr;
135 
137 
138  rt_db_free_internal(&in);
139  }
140  /* exiting region */
141  if (dtp->comb_exit_func)
142  dtp->comb_exit_func(dtp->dbip, dp, dtp->client_data);
143  } else if (dp->d_flags & RT_DIR_SOLID || dp->d_major_type & DB5_MAJORTYPE_BINARY_MASK) {
144  /* at leaf */
145  if (dtp->leaf_func)
146  dtp->leaf_func(dtp->dbip, dp, dtp->client_data);
147  } else {
148  bu_log("db_preorder_traverse: %s is neither COMB nor SOLID?\n",
149  dp->d_namep);
150  }
151 }
152 
153 
154 /*
155  * The only reason for this to be broken out is that
156  * 2 separate locations in db_functree() call it.
157  */
158 void
160  union tree *tp,
161  void (*comb_func) (struct db_i *, struct directory *, void *),
162  void (*leaf_func) (struct db_i *, struct directory *, void *),
163  struct resource *resp,
164  void *client_data)
165 {
166  struct directory *dp;
167 
168  if (!tp)
169  return;
170 
171  RT_CHECK_DBI(dbip);
172  RT_CK_TREE(tp);
173  if (resp) {
174  RT_CK_RESOURCE(resp);
175  }
176 
177  switch (tp->tr_op) {
178 
179  case OP_DB_LEAF:
180  if ((dp=db_lookup(dbip, tp->tr_l.tl_name, LOOKUP_NOISY)) == RT_DIR_NULL)
181  return;
182  db_functree(dbip, dp, comb_func, leaf_func, resp, client_data);
183  break;
184 
185  case OP_UNION:
186  case OP_INTERSECT:
187  case OP_SUBTRACT:
188  case OP_XOR:
189  db_functree_subtree(dbip, tp->tr_b.tb_left, comb_func, leaf_func, resp, client_data);
190  db_functree_subtree(dbip, tp->tr_b.tb_right, comb_func, leaf_func, resp, client_data);
191  break;
192  default:
193  bu_log("db_functree_subtree: unrecognized operator %d\n", tp->tr_op);
194  bu_bomb("db_functree_subtree: unrecognized operator\n");
195  }
196 }
197 
198 void
199 db_functree(struct db_i *dbip,
200  struct directory *dp,
201  void (*comb_func) (struct db_i *, struct directory *, void *),
202  void (*leaf_func) (struct db_i *, struct directory *, void *),
203  struct resource *resp,
204  void *client_data)
205 {
206  register size_t i;
207 
208  RT_CK_DBI(dbip);
209  if (resp) {
210  RT_CK_RESOURCE(resp);
211  }
212 
213  if ((!dp) || (!comb_func && !leaf_func)) {
214  return; /* nothing to do */
215  }
216 
217  if (RT_G_DEBUG&DEBUG_DB) {
218  bu_log("db_functree(%s) %p, %p, comb=%lx, leaf=%lx, client_data=%p\n",
219  dp->d_namep, (void *)dbip, (void *)dp,
220  (long unsigned int)comb_func, (long unsigned int)leaf_func,
221  client_data);
222  }
223 
224  if (dp->d_flags & RT_DIR_COMB) {
225  if (db_version(dbip) < 5) {
226  register union record *rp;
227  register struct directory *mdp;
228  /*
229  * Load the combination into local record buffer
230  * This is in external v4 format.
231  */
232  if ((rp = db_getmrec(dbip, dp)) == (union record *)0)
233  return;
234 
235  /* recurse */
236  for (i=1; i < dp->d_len; i++) {
237  if ((mdp = db_lookup(dbip, rp[i].M.m_instname, LOOKUP_NOISY)) == RT_DIR_NULL)
238  continue;
239  db_functree(dbip, mdp, comb_func, leaf_func, resp, client_data);
240  }
241  bu_free((char *)rp, "db_functree record[]");
242  } else {
243  struct rt_db_internal in;
244  struct rt_comb_internal *comb;
245 
246  if (rt_db_get_internal5(&in, dp, dbip, NULL, resp) < 0)
247  return;
248 
249  comb = (struct rt_comb_internal *)in.idb_ptr;
250  db_functree_subtree(dbip, comb->tree, comb_func, leaf_func, resp, client_data);
251  rt_db_free_internal(&in);
252  }
253 
254  /* Finally, the combination itself */
255  if (comb_func)
256  comb_func(dbip, dp, client_data);
257 
258  } else if (dp->d_flags & RT_DIR_SOLID || dp->d_major_type & DB5_MAJORTYPE_BINARY_MASK) {
259  if (leaf_func)
260  leaf_func(dbip, dp, client_data);
261  } else {
262  bu_log("db_functree: %s is neither COMB nor SOLID?\n",
263  dp->d_namep);
264  }
265 }
266 
267 
268 /** @} */
269 /*
270  * Local Variables:
271  * mode: C
272  * tab-width: 8
273  * indent-tabs-mode: t
274  * c-file-style: "stroustrup"
275  * End:
276  * ex: shiftwidth=4 tabstop=8
277  */
char * d_namep
pointer to name string
Definition: raytrace.h:859
Definition: raytrace.h:800
unsigned char d_major_type
object major type
Definition: raytrace.h:870
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
void(* comb_enter_func)(struct db_i *, struct directory *, void *)
Definition: raytrace.h:1093
#define RT_CHECK_DBI(_p)
Definition: raytrace.h:828
size_t d_len
of db granules used
Definition: raytrace.h:867
#define OP_XOR
Binary: L xor R, not both.
Definition: raytrace.h:1130
struct directory * db_lookup(const struct db_i *, const char *name, int noisy)
Definition: db_lookup.c:153
int db_version(struct db_i *dbip)
Definition: db5_scan.c:414
void * client_data
Definition: raytrace.h:1106
Header file for the BRL-CAD common definitions.
union tree * tb_left
Definition: raytrace.h:1149
#define OP_SUBTRACT
Binary: L subtract R.
Definition: raytrace.h:1129
#define OP_INTERSECT
Binary: L intersect R.
Definition: raytrace.h:1128
#define RT_G_DEBUG
Definition: raytrace.h:1718
#define OP_DB_LEAF
Leaf of combination, db fmt.
Definition: raytrace.h:1139
#define RT_DIR_SOLID
this name is a solid
Definition: raytrace.h:883
char * tl_name
Name of this leaf (bu_strdup'ed)
Definition: raytrace.h:1174
struct tree::tree_node tr_b
struct db_i * dbip
Definition: raytrace.h:1092
void db_preorder_traverse(struct directory *dp, struct db_traverse *dtp)
Definition: db_walk.c:89
void db_traverse_subtree(union tree *tp, void(*traverse_func)(struct directory *, struct db_traverse *), struct db_traverse *dtp)
Definition: db_walk.c:42
void(* comb_exit_func)(struct db_i *, struct directory *, void *)
Definition: raytrace.h:1097
#define RT_CK_DBI(_p)
Definition: raytrace.h:829
struct tree::tree_db_leaf tr_l
union tree * tb_right
Definition: raytrace.h:1150
void * idb_ptr
Definition: raytrace.h:195
#define RT_DIR_COMB
combination
Definition: raytrace.h:884
#define DEBUG_DB
5 Database debugging
Definition: raytrace.h:88
#define RT_CK_RESOURCE(_p)
Definition: raytrace.h:1490
union tree * tree
Leading to tree_db_leaf leaves.
Definition: raytrace.h:938
#define RT_DIR_NULL
Definition: raytrace.h:875
#define LOOKUP_NOISY
Definition: raytrace.h:892
#define RT_CK_DB_TRAVERSE(_p)
Definition: raytrace.h:1112
int rt_db_get_internal5(struct rt_db_internal *ip, const struct directory *dp, const struct db_i *dbip, const mat_t mat, struct resource *resp)
Definition: db5_io.c:961
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define RT_CK_TREE(_p)
Definition: raytrace.h:1182
struct resource * resp
Definition: raytrace.h:1105
union record * db_getmrec(const struct db_i *, const struct directory *dp)
Definition: db_io.c:97
void(* leaf_func)(struct db_i *, struct directory *, void *)
Definition: raytrace.h:1101
int d_flags
flags
Definition: raytrace.h:869
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
void db_functree(struct db_i *dbip, struct directory *dp, void(*comb_func)(struct db_i *, struct directory *, void *), void(*leaf_func)(struct db_i *, struct directory *, void *), struct resource *resp, void *client_data)
Definition: db_walk.c:199
#define OP_UNION
Binary: L union R.
Definition: raytrace.h:1127
void rt_db_free_internal(struct rt_db_internal *ip)
Definition: dir.c:216
#define M
Definition: msr.c:52
void db_functree_subtree(struct db_i *dbip, union tree *tp, void(*comb_func)(struct db_i *, struct directory *, void *), void(*leaf_func)(struct db_i *, struct directory *, void *), struct resource *resp, void *client_data)
Definition: db_walk.c:159