BRL-CAD
rb.h
Go to the documentation of this file.
1 /* R B . H
2  * BRL-CAD
3  *
4  * Copyright (c) 2004-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 /** @file rb.h
22  *
23  */
24 #ifndef BU_RB_H
25 #define BU_RB_H
26 
27 #include "common.h"
28 
29 #include "bu/defines.h"
30 #include "bu/magic.h"
31 #include "bu/list.h"
32 #include "bu/bitv.h"
33 
35 
36 /*----------------------------------------------------------------------*/
37 /** @addtogroup rb */
38 /** @{ */
39 /*
40  * The data structures and constants for red-black trees.
41  *
42  * Many of these routines are based on the algorithms in chapter 13 of
43  * Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest,
44  * "Introduction to Algorithms", MIT Press, Cambridge, MA, 1990.
45  *
46  * FIXME: check implementation given the following note:
47  *
48  * Note that the third edition was published in 2009 and the book
49  * has had significant updates since the first edition. Quoting the
50  * authors in the preface: "The way we delete a node from binary search
51  * trees (which includes red-black trees) now guarantees that the node
52  * requested for deletion is the node that is actually deleted. In the
53  * first two editions, in certain cases, some other node would be
54  * deleted, with its contents moving into the node passed to the
55  * deletion procedure. With our new way to delete nodes, if other
56  * components of a program maintain pointers to nodes in the tree, they
57  * will not mistakenly end up with stale pointers to nodes that have
58  * been deleted."
59  *
60  * This implementation of balanced binary red-black tree operations
61  * provides all the basic dynamic set operations (e.g., insertion,
62  * deletion, search, minimum, maximum, predecessor, and successor) and
63  * order-statistic operations (i.e., select and rank) with optimal
64  * O(log(n)) performance while sorting on multiple keys. Such an
65  * implementation is referred to as an "augmented red-black tree" and
66  * is discussed in Chapter 14 of the 2009 edition of "Introduction to
67  * Algorithms."
68  */
69 
70 /**
71  * List of nodes or packages.
72  *
73  * The red-black tree package uses this structure to maintain lists of
74  * all the nodes and all the packages in the tree. Applications
75  * should not muck with these things. They are maintained only to
76  * facilitate freeing bu_rb_trees.
77  *
78  * This is a PRIVATE structure.
79  */
80 struct bu_rb_list
81 {
82  struct bu_list l;
83  union
84  {
85  struct bu_rb_node *rbl_n;
87  } rbl_u;
88 };
89 #define rbl_magic l.magic
90 #define rbl_node rbl_u.rbl_n
91 #define rbl_package rbl_u.rbl_p
92 #define BU_RB_LIST_NULL ((struct bu_rb_list *) 0)
93 
94 
95 /**
96  * This is the only data structure used in the red-black tree package
97  * to which application software need make any explicit reference.
98  *
99  * The members of this structure are grouped into three classes:
100  *
101  * Class I: Reading is appropriate, when necessary,
102  * but applications should not modify.
103  * Class II: Reading and modifying are both appropriate,
104  * when necessary.
105  * Class III: All access should be through routines
106  * provided in the package. Touch these
107  * at your own risk!
108  */
109 struct bu_rb_tree {
110  /***** CLASS I - Applications may read directly. ****************/
111  uint32_t rbt_magic; /**< Magic no. for integrity check */
112  int rbt_nm_nodes; /**< Number of nodes */
113 
114  /**** CLASS II - Applications may read/write directly. **********/
115  void (*rbt_print)(void *); /**< Data pretty-print function */
116  int rbt_debug; /**< Debug bits */
117  const char *rbt_description; /**< Comment for diagnostics */
118 
119  /*** CLASS III - Applications should NOT manipulate directly. ***/
120  int rbt_nm_orders; /**< Number of simultaneous orders */
121  int (**rbt_compar)(const void *, const void *); /**< Comparison functions */
122  struct bu_rb_node **rbt_root; /**< The actual trees */
123  char *rbt_unique; /**< Uniqueness flags */
124  struct bu_rb_node *rbt_current; /**< Current node */
125  struct bu_rb_list rbt_nodes; /**< All nodes */
126  struct bu_rb_list rbt_packages; /**< All packages */
127  struct bu_rb_node *rbt_empty_node; /**< Sentinel representing nil */
128 };
129 typedef struct bu_rb_tree bu_rb_tree_t;
130 #define BU_RB_TREE_NULL ((struct bu_rb_tree *) 0)
131 
132 /**
133  * asserts the integrity of a bu_rb_tree struct.
134  */
135 #define BU_CK_RB_TREE(_rb) BU_CKMAG(_rb, BU_RB_TREE_MAGIC, "bu_rb_tree")
136 
137 /**
138  * initializes a bu_rb_tree struct without allocating any memory.
139  */
140 #define BU_RB_TREE_INIT(_rb) { \
141  (_rb)->rbt_magic = BU_RB_TREE_MAGIC; \
142  (_rb)->rbt_nm_nodes = 0; \
143  (_rb)->rbt_print = NULL; \
144  (_rb)->rbt_debug = 0; \
145  (_rb)->rbt_description = NULL; \
146  (_rb)->rbt_nm_orders = 0; \
147  (_rb)->rbt_compar = NULL; \
148  (_rb)->rbt_root = (_rb)->rbt_unique = (_rb)->rbt_current = NULL; \
149  BU_LIST_INIT(&(_rb)->rbt_nodes.l); \
150  (_rb)->rbt_nodes.rbl_u.rbl_n = (_rb)->rbt_nodes.rbl_u.rbl_p = NULL; \
151  BU_LIST_INIT(&(_rb)->rbt_packages.l); \
152  (_rb)->rbt_packages.rbl_u.rbl_n = (_rb)->rbt_packages.rbl_u.rbl_p = NULL; \
153  (_rb)->rbt_empty_node = NULL; \
154  }
155 
156 /**
157  * macro suitable for declaration statement initialization of a
158  * bu_rb_tree struct. does not allocate memory.
159  */
160 #define BU_RB_TREE_INIT_ZERO { BU_RB_TREE_MAGIC, 0, NULL, 0, NULL, 0, NULL, NULL, NULL, NULL, \
161  { BU_LIST_INIT_ZER0, {NULL, NULL} }, { BU_LIST_INIT_ZER0, {NULL, NULL} }, NULL, NULL, NULL }
162 
163 /**
164  * returns truthfully whether a bu_rb_tree has been initialized.
165  */
166 #define BU_RB_TREE_IS_INITIALIZED(_rb) (((struct bu_rb_tree *)(_rb) != BU_RB_TREE_NULL) && LIKELY((_rb)->rbt_magic == BU_RB_TREE_MAGIC))
167 
168 
169 /*
170  * Debug bit flags for member rbt_debug
171  */
172 #define BU_RB_DEBUG_INSERT 0x00000001 /**< Insertion process */
173 #define BU_RB_DEBUG_UNIQ 0x00000002 /**< Uniqueness of inserts */
174 #define BU_RB_DEBUG_ROTATE 0x00000004 /**< Rotation process */
175 #define BU_RB_DEBUG_OS 0x00000008 /**< Order-statistic operations */
176 #define BU_RB_DEBUG_DELETE 0x00000010 /**< Deletion process */
177 
178 /**
179  * Wrapper for application data.
180  *
181  * This structure provides a level of indirection between the
182  * application software's data and the red-black nodes in which the
183  * data is stored. It is necessary because of the algorithm for
184  * deletion, which generally shuffles data among nodes in the tree.
185  * The package structure allows the application data to remember which
186  * node "contains" it for each order.
187  */
189 {
190  uint32_t rbp_magic; /**< Magic no. for integrity check */
191  struct bu_rb_node **rbp_node; /**< Containing nodes */
192  struct bu_rb_list *rbp_list_pos; /**< Place in the list of all pkgs. */
193  void *rbp_data; /**< Application data */
194 };
195 #define BU_RB_PKG_NULL ((struct bu_rb_package *) 0)
196 
197 /**
198  * For the most part, there is a one-to-one correspondence between
199  * nodes and chunks of application data. When a node is created, all
200  * of its package pointers (one per order of the tree) point to the
201  * same chunk of data. However, subsequent deletions usually muddy
202  * this tidy state of affairs.
203  */
205 {
206  uint32_t rbn_magic; /**< Magic no. for integrity check */
207  struct bu_rb_tree *rbn_tree; /**< Tree containing this node */
208  struct bu_rb_node **rbn_parent; /**< Parents */
209  struct bu_rb_node **rbn_left; /**< Left subtrees */
210  struct bu_rb_node **rbn_right; /**< Right subtrees */
211  char *rbn_color; /**< Colors of this node */
212  int *rbn_size; /**< Sizes of subtrees rooted here */
213  struct bu_rb_package **rbn_package; /**< Contents of this node */
214  int rbn_pkg_refs; /**< How many orders are being used? */
215  struct bu_rb_list *rbn_list_pos; /**< Place in the list of all nodes */
216 };
217 #define BU_RB_NODE_NULL ((struct bu_rb_node *) 0)
218 
219 /*
220  * Applications interface to bu_rb_extreme()
221  */
222 #define SENSE_MIN 0
223 #define SENSE_MAX 1
224 #define bu_rb_min(t, o) bu_rb_extreme((t), (o), SENSE_MIN)
225 #define bu_rb_max(t, o) bu_rb_extreme((t), (o), SENSE_MAX)
226 #define bu_rb_pred(t, o) bu_rb_neighbor((t), (o), SENSE_MIN)
227 #define bu_rb_succ(t, o) bu_rb_neighbor((t), (o), SENSE_MAX)
228 
229 /*
230  * Applications interface to bu_rb_walk()
231  */
236 };
237 
238 /** @file libbu/rb_create.c
239  *
240  * Routines to create a red-black tree
241  *
242  */
243 
244 /**
245  * Create a red-black tree
246  *
247  * This function has three parameters: a comment describing the tree
248  * to create, the number of linear orders to maintain simultaneously,
249  * and the comparison functions (one per order). bu_rb_create()
250  * returns a pointer to the red-black tree header record.
251  */
252 BU_EXPORT extern struct bu_rb_tree *bu_rb_create(const char *description, int nm_orders, int (**compare_funcs)(const void *, const void *));
253 /* A macro for correct casting of a rb compare function for use a function argument: */
254 #define BU_RB_COMPARE_FUNC_CAST_AS_FUNC_ARG(_func) ((int (*)(void))_func)
255 
256 /**
257  * Create a single-order red-black tree
258  *
259  * This function has two parameters: a comment describing the tree to
260  * create and a comparison function. bu_rb_create1() builds an array
261  * of one function pointer and passes it to bu_rb_create().
262  * bu_rb_create1() returns a pointer to the red-black tree header
263  * record.
264  *
265  * N.B. - Since this function allocates storage for the array of
266  * function pointers, in order to avoid memory leaks on freeing the
267  * tree, applications should call bu_rb_free1(), NOT bu_rb_free().
268  */
269 BU_EXPORT extern struct bu_rb_tree *bu_rb_create1(const char *description, int (*compare_func)(void));
270 
271 /** @file libbu/rb_delete.c
272  *
273  * Routines to delete a node from a red-black tree
274  *
275  */
276 
277 /**
278  * Applications interface to _rb_delete()
279  *
280  * This function has two parameters: the tree and order from which to
281  * do the deleting. bu_rb_delete() removes the data block stored in
282  * the current node (in the position of the specified order) from
283  * every order in the tree.
284  */
285 BU_EXPORT extern void bu_rb_delete(struct bu_rb_tree *tree,
286  int order);
287 #define bu_rb_delete1(t) bu_rb_delete((t), 0)
288 
289 /** @file libbu/rb_diag.c
290  *
291  * Diagnostic routines for red-black tree maintenance
292  *
293  */
294 
295 /**
296  * Produce a diagnostic printout of a red-black tree
297  *
298  * This function has three parameters: the root and order of the tree
299  * to print out and the type of traversal (preorder, inorder, or
300  * postorder).
301  */
302 BU_EXPORT extern void bu_rb_diagnose_tree(struct bu_rb_tree *tree,
303  int order,
304  int trav_type);
305 
306 /**
307  * Describe a red-black tree
308  *
309  * This function has one parameter: a pointer to a red-black tree.
310  * bu_rb_summarize_tree() prints out the header information for the
311  * tree. It is intended for diagnostic purposes.
312  */
313 BU_EXPORT extern void bu_rb_summarize_tree(struct bu_rb_tree *tree);
314 
315 /** @file libbu/rb_extreme.c
316  *
317  * Routines to extract mins, maxes, adjacent, and current nodes
318  * from a red-black tree
319  *
320  */
321 
322 
323 /**
324  * Applications interface to rb_extreme()
325  *
326  * This function has three parameters: the tree in which to find an
327  * extreme node, the order on which to do the search, and the sense
328  * (min or max). On success, bu_rb_extreme() returns a pointer to the
329  * data in the extreme node. Otherwise it returns NULL.
330  */
331 BU_EXPORT extern void *bu_rb_extreme(struct bu_rb_tree *tree,
332  int order,
333  int sense);
334 
335 /**
336  * Return a node adjacent to the current red-black node
337  *
338  * This function has three parameters: the tree and order on which to
339  * do the search and the sense (min or max, which is to say
340  * predecessor or successor) of the search. bu_rb_neighbor() returns
341  * a pointer to the data in the node adjacent to the current node in
342  * the specified direction, if that node exists. Otherwise, it
343  * returns NULL.
344  */
345 BU_EXPORT extern void *bu_rb_neighbor(struct bu_rb_tree *tree,
346  int order,
347  int sense);
348 
349 /**
350  * Return the current red-black node
351  *
352  * This function has two parameters: the tree and order in which to
353  * find the current node. bu_rb_curr() returns a pointer to the data
354  * in the current node, if it exists. Otherwise, it returns NULL.
355  */
356 BU_EXPORT extern void *bu_rb_curr(struct bu_rb_tree *tree,
357  int order);
358 #define bu_rb_curr1(t) bu_rb_curr((t), 0)
359 
360 /** @file libbu/rb_free.c
361  *
362  * Routines to free a red-black tree
363  *
364  */
365 
366 /**
367  * Free a red-black tree
368  *
369  * This function has two parameters: the tree to free and a function
370  * to handle the application data. bu_rb_free() traverses tree's
371  * lists of nodes and packages, freeing each one in turn, and then
372  * frees tree itself. If free_data is non-NULL, then bu_rb_free()
373  * calls it just* before freeing each package, passing it the
374  * package's rbp_data member. Otherwise, the application data is left
375  * untouched.
376  */
377 BU_EXPORT extern void bu_rb_free(struct bu_rb_tree *tree, void (*free_data)(void *data));
378 #define BU_RB_RETAIN_DATA ((void (*)(void *data)) 0)
379 #define bu_rb_free1(t, f) \
380  { \
381  BU_CKMAG((t), BU_RB_TREE_MAGIC, "red-black tree"); \
382  bu_free((char *) ((t) -> rbt_compar), \
383  "red-black compare function"); \
384  bu_rb_free(t, f); \
385  }
386 
387 /** @file libbu/rb_insert.c
388  *
389  * Routines to insert into a red-black tree
390  *
391  */
392 
393 /**
394  * Applications interface to bu_rb_insert()
395  *
396  * This function has two parameters: the tree into which to insert the
397  * new node and the contents of the node. If a uniqueness requirement
398  * would be violated, bu_rb_insert() does nothing but return a number
399  * from the set {-1, -2, ..., -nm_orders} of which the absolute value
400  * is the first order for which a violation exists. Otherwise, it
401  * returns the number of orders for which the new node was equal to a
402  * node already in the tree.
403  */
404 BU_EXPORT extern int bu_rb_insert(struct bu_rb_tree *tree,
405  void *data);
406 
407 /**
408  * Query the uniqueness flag for one order of a red-black tree
409  *
410  * This function has two parameters: the tree and the order for which
411  * to query uniqueness.
412  */
413 BU_EXPORT extern int bu_rb_is_uniq(struct bu_rb_tree *tree,
414  int order);
415 #define bu_rb_is_uniq1(t) bu_rb_is_uniq((t), 0)
416 
417 /**
418  * Set the uniqueness flags for all the linear orders of a red-black
419  * tree
420  *
421  * This function has two parameters: the tree and a bitv_t encoding
422  * the flag values. bu_rb_set_uniqv() sets the flags according to the
423  * bits in flag_rep. For example, if flag_rep = 1011_2, then the
424  * first, second, and fourth orders are specified unique, and the
425  * third is specified not-necessarily unique.
426  */
427 BU_EXPORT extern void bu_rb_set_uniqv(struct bu_rb_tree *tree,
428  bitv_t vec);
429 
430 /**
431  * These functions have one parameter: the tree for which to
432  * require uniqueness/permit nonuniqueness.
433  */
434 BU_EXPORT extern void bu_rb_uniq_all_off(struct bu_rb_tree *tree);
435 
436 /**
437  * These functions have one parameter: the tree for which to
438  * require uniqueness/permit nonuniqueness.
439  */
440 BU_EXPORT extern void bu_rb_uniq_all_on(struct bu_rb_tree *tree);
441 
442 /**
443  * Has two parameters: the tree and the order for which to require
444  * uniqueness/permit nonuniqueness. Each sets the specified flag to
445  * the specified value and returns the previous value of the flag.
446  */
447 BU_EXPORT extern int bu_rb_uniq_on(struct bu_rb_tree *tree,
448  int order);
449 #define bu_rb_uniq_on1(t) bu_rb_uniq_on((t), 0)
450 
451 /**
452  * Has two parameters: the tree and the order for which to require
453  * uniqueness/permit nonuniqueness. Each sets the specified flag to
454  * the specified value and returns the previous value of the flag.
455  */
456 BU_EXPORT extern int bu_rb_uniq_off(struct bu_rb_tree *tree,
457  int order);
458 #define bu_rb_uniq_off1(t) bu_rb_uniq_off((t), 0)
459 
460 /** @file libbu/rb_order_stats.c
461  *
462  * Routines to support order-statistic operations for a red-black tree
463  *
464  */
465 
466 /**
467  * Determines the rank of a node in one order of a red-black tree.
468  *
469  * This function has two parameters: the tree in which to search and
470  * the order on which to do the searching. If the current node is
471  * null, bu_rb_rank() returns 0. Otherwise, it returns the rank of
472  * the current node in the specified order. bu_rb_rank() is an
473  * implementation of the routine OS-RANK on p. 283 of Cormen et al.
474  */
475 BU_EXPORT extern int bu_rb_rank(struct bu_rb_tree *tree,
476  int order);
477 #define bu_rb_rank1(t) bu_rb_rank1((t), 0)
478 
479 /**
480  * This function has three parameters: the tree in which to search,
481  * the order on which to do the searching, and the rank of interest.
482  * On success, bu_rb_select() returns a pointer to the data block in
483  * the discovered node. Otherwise, it returns NULL.
484  */
485 BU_EXPORT extern void *bu_rb_select(struct bu_rb_tree *tree,
486  int order,
487  int k);
488 #define bu_rb_select1(t, k) bu_rb_select((t), 0, (k))
489 
490 /** @file libbu/rb_search.c
491  *
492  * Routines to search for a node in a red-black tree
493  *
494  */
495 
496 /**
497  * This function has three parameters: the tree in which to search,
498  * the order on which to do the searching, and a data block containing
499  * the desired value of the key. On success, bu_rb_search() returns a
500  * pointer to the data block in the discovered node. Otherwise, it
501  * returns NULL.
502  */
503 BU_EXPORT extern void *bu_rb_search(struct bu_rb_tree *tree,
504  int order,
505  void *data);
506 #define bu_rb_search1(t, d) bu_rb_search((t), 0, (d))
507 
508 /** @file libbu/rb_walk.c
509  *
510  * Routines for traversal of red-black trees
511  *
512  * The function bu_rb_walk() is defined in terms of the function
513  * rb_walk(), which, in turn, calls any of the six functions
514  *
515  * @arg - static void prewalknodes()
516  * @arg - static void inwalknodes()
517  * @arg - static void postwalknodes()
518  * @arg - static void prewalkdata()
519  * @arg - static void inwalkdata()
520  * @arg - static void postwalkdata()
521  *
522  * depending on the type of traversal desired and the objects
523  * to be visited (nodes themselves, or merely the data stored
524  * in them). Each of these last six functions has four parameters:
525  * the root of the tree to traverse, the order on which to do the
526  * walking, the function to apply at each visit, and the current
527  * depth in the tree.
528  */
529 
530 /**
531  * This function has four parameters: the tree to traverse, the order
532  * on which to do the walking, the function to apply to each node, and
533  * the type of traversal (preorder, inorder, or postorder).
534  *
535  * Note the function to apply has the following signature ONLY when it
536  * is used as an argument:
537  *
538  * void (*visit)(void)
539  *
540  * When used as a function the pointer should be cast back to one of its real
541  * signatures depending on what it is operating on (node or data):
542  *
543  * node:
544  *
545  * void (*visit)((struct bu_rb_node *, int)
546  *
547  * data:
548  *
549  * void (*visit)((void *, int)
550  *
551  * Use the macros below to ensure accurate casting. See
552  * libbu/rb_diag.c and libbu/rb_walk.c for examples of their use.
553  *
554  */
555 BU_EXPORT extern void bu_rb_walk(struct bu_rb_tree *tree, int order, void (*visit)(void), int trav_type);
556 #define bu_rb_walk1(t, v, d) bu_rb_walk((t), 0, (v), (d))
557 
558 #define BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG(_func) ((void (*)(void))_func)
559 #define BU_RB_WALK_FUNC_CAST_AS_NODE_FUNC(_func) ((void (*)(struct bu_rb_node *, int))_func)
560 #define BU_RB_WALK_FUNC_CAST_AS_DATA_FUNC(_func) ((void (*)(void *, int))_func)
561 #define BU_RB_WALK_FUNC_CAST_AS_FUNC_FUNC(_func) ((void (*)(struct bu_rb_node *, int, void (*)(void), int))_func)
562 #define BU_RB_WALK_FUNC_NODE_DECL(_func) void (*_func)(struct bu_rb_node *, int)
563 #define BU_RB_WALK_FUNC_DATA_DECL(_func) void (*_func)(void *, int)
564 #define BU_RB_WALK_FUNC_FUNC_DECL(_func) void (*_func)(struct bu_rb_node *, int, void (*)(void), int)
565 
566 /** @} */
567 
569 
570 #endif /* BU_RB_H */
571 
572 /*
573  * Local Variables:
574  * mode: C
575  * tab-width: 8
576  * indent-tabs-mode: t
577  * c-file-style: "stroustrup"
578  * End:
579  * ex: shiftwidth=4 tabstop=8
580  */
struct bu_rb_node * rbl_n
Definition: rb.h:85
struct bu_rb_node ** rbn_parent
Definition: rb.h:208
void bu_rb_uniq_all_on(struct bu_rb_tree *tree)
Definition: rb_insert.c:367
struct bu_rb_list * rbn_list_pos
Definition: rb.h:215
void bu_rb_summarize_tree(struct bu_rb_tree *tree)
Definition: rb_diag.c:89
struct bu_rb_node ** rbn_left
Definition: rb.h:209
Definition: list.h:118
int rbn_pkg_refs
Definition: rb.h:214
Definition: rb.h:109
void * bu_rb_search(struct bu_rb_tree *tree, int order, void *data)
Definition: rb_search.c:67
Definition: rb.h:204
unsigned char bitv_t
Definition: bitv.h:59
struct bu_rb_tree * bu_rb_create1(const char *description, int(*compare_func)(void))
Definition: rb_create.c:102
struct bu_rb_node ** rbp_node
Definition: rb.h:191
struct bu_rb_list rbt_packages
Definition: rb.h:126
int bu_rb_uniq_off(struct bu_rb_tree *tree, int order)
Definition: rb_insert.c:307
struct bu_rb_list rbt_nodes
Definition: rb.h:125
int bu_rb_uniq_on(struct bu_rb_tree *tree, int order)
Definition: rb_insert.c:301
struct bu_rb_node * rbt_empty_node
Definition: rb.h:127
uint32_t rbt_magic
Definition: rb.h:111
Header file for the BRL-CAD common definitions.
int bu_rb_rank(struct bu_rb_tree *tree, int order)
void * bu_rb_extreme(struct bu_rb_tree *tree, int order, int sense)
Definition: rb_extreme.c:68
struct bu_rb_node * rbt_current
Definition: rb.h:124
uint32_t rbp_magic
Definition: rb.h:190
COMPLEX data[64]
Definition: fftest.c:34
int bu_rb_is_uniq(struct bu_rb_tree *tree, int order)
Definition: rb_insert.c:314
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
#define __BEGIN_DECLS
Definition: common.h:73
BU_RB_WALK_ORDER
Definition: rb.h:232
struct bu_rb_list * rbp_list_pos
Definition: rb.h:192
struct bu_rb_package * rbl_p
Definition: rb.h:86
void * bu_rb_curr(struct bu_rb_tree *tree, int order)
Definition: rb_extreme.c:150
struct bu_rb_tree * rbn_tree
Definition: rb.h:207
int * rbn_size
Definition: rb.h:212
void bu_rb_delete(struct bu_rb_tree *tree, int order)
Definition: rb_delete.c:149
void * rbp_data
Definition: rb.h:193
int rbt_nm_orders
Definition: rb.h:120
int(** rbt_compar)(const void *, const void *)
Definition: rb.h:121
void * bu_rb_select(struct bu_rb_tree *tree, int order, int k)
int rbt_nm_nodes
Definition: rb.h:112
struct bu_rb_tree * bu_rb_create(const char *description, int nm_orders, int(**compare_funcs)(const void *, const void *))
Definition: rb_create.c:30
void bu_rb_uniq_all_off(struct bu_rb_tree *tree)
Definition: rb_insert.c:373
char * rbn_color
Definition: rb.h:211
uint32_t rbn_magic
Definition: rb.h:206
char * rbt_unique
Definition: rb.h:123
struct bu_rb_package ** rbn_package
Definition: rb.h:213
#define __END_DECLS
Definition: common.h:74
void(* rbt_print)(void *)
Definition: rb.h:115
int bu_rb_insert(struct bu_rb_tree *tree, void *data)
Definition: rb_insert.c:150
void bu_rb_free(struct bu_rb_tree *tree, void(*free_data)(void *data))
struct bu_rb_node ** rbn_right
Definition: rb.h:210
struct bu_rb_node ** rbt_root
Definition: rb.h:122
struct bu_list l
Definition: rb.h:82
void bu_rb_set_uniqv(struct bu_rb_tree *tree, bitv_t vec)
Definition: rb_insert.c:324
union bu_rb_list::@0 rbl_u
void bu_rb_walk(struct bu_rb_tree *tree, int order, void(*visit)(void), int trav_type)
Definition: rb_walk.c:238
int rbt_debug
Definition: rb.h:116
Definition: rb.h:80
void * bu_rb_neighbor(struct bu_rb_tree *tree, int order, int sense)
Definition: rb_extreme.c:124