BRL-CAD
rb_internals.h
Go to the documentation of this file.
1 /* R B _ I N T E R N A L S . H
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 #ifndef LIBBU_RB_INTERNALS_H
24 #define LIBBU_RB_INTERNALS_H seen
25 
26 #include "bu/log.h"
27 #include "bu/malloc.h"
28 
29 /**
30  * This internal macro has two parameters: a tree and an order number.
31  * It ensures that the order number is valid for the tree.
32  */
33 #define RB_CKORDER(t, o) \
34  if (UNLIKELY(((o) < 0) || ((o) >= (t)->rbt_nm_orders))) { \
35  char buf[128] = {0}; \
36  snprintf(buf, 128, "ERROR: Order %d outside 0..%d (nm_orders-1), file %s, line %d\n", \
37  (o), (t)->rbt_nm_orders - 1, __FILE__, __LINE__); \
38  bu_bomb(buf); \
39  }
40 
41 /*
42  * Access functions for fields of struct bu_rb_tree
43  */
44 #define RB_COMPARE_FUNC(t, o) (((t)->rbt_compar)[o])
45 #define RB_PRINT(t, p) (((t)->rbt_print)((p)->rbp_data))
46 #define RB_ROOT(t, o) (((t)->rbt_root)[o])
47 #define RB_CURRENT(t) ((t)->rbt_current)
48 #define RB_NULL(t) ((t)->rbt_empty_node)
49 #define RB_GET_UNIQUENESS(t, o) ((((t)->rbt_unique)[(o)/8] & (0x1 << ((o) % 8))) ? 1 : 0)
50 #define RB_SET_UNIQUENESS(t, o, u) { \
51  int _b = (o) / 8; \
52  int _p = (o) - _b * 8; \
53  ((t)->rbt_unique)[_b] &= ~(0x1 << _p); \
54  ((t)->rbt_unique)[_b] |= (u) << _p; \
55  }
56 
57 /*
58  * Access functions for fields of (struct bu_rb_node)
59  */
60 #define RB_PARENT(n, o) (((n)->rbn_parent)[o])
61 #define RB_LEFT_CHILD(n, o) (((n)->rbn_left)[o])
62 #define RB_RIGHT_CHILD(n, o) (((n)->rbn_right)[o])
63 #define RB_LEFT 0
64 #define RB_RIGHT 1
65 #define RB_CHILD(n, o, d) (((d) == RB_LEFT) ? \
66  RB_LEFT_CHILD((n), (o)) : \
67  RB_RIGHT_CHILD((n), (o)))
68 #define RB_OTHER_CHILD(n, o, d) (((d) == RB_LEFT) ? \
69  RB_RIGHT_CHILD((n), (o)) : \
70  RB_LEFT_CHILD((n), (o)))
71 #define RB_SIZE(n, o) (((n)->rbn_size)[o])
72 #define RB_GET_COLOR(n, o) \
73  ((((n)->rbn_color)[(o)/8] & (0x1 << ((o) % 8))) ? 1 : 0)
74 #define RB_SET_COLOR(n, o, c) { \
75  int _b = (o) / 8; \
76  int _p = (o) - _b * 8; \
77  ((n)->rbn_color)[_b] &= ~(0x1 << _p); \
78  ((n)->rbn_color)[_b] |= (c) << _p; \
79  }
80 #define RB_RED 0
81 #define RB_BLK 1
82 #define RB_DATA(n, o) (((n)->rbn_package)[o]->rbp_data)
83 
84 /**
85  * Interface to rb_walk()
86  * (Valid values for the parameter what_to_walk)
87  */
88 #define WALK_NODES 0
89 #define WALK_DATA 1
90 
91 /**
92  * This macro has three parameters: the node about which to rotate,
93  * the order to be rotated, and the direction of rotation. They allow
94  * indirection in the use of rb_rot_left() and rb_rot_right().
95  */
96 #define RB_ROTATE(n, o, d) (((d) == RB_LEFT) ? \
97  rb_rot_left((n), (o)) : \
98  rb_rot_right((n), (o)))
99 
100 /**
101  * This macro has three parameters: the node about which to rotate,
102  * the order to be rotated, and the direction of rotation. They allow
103  * indirection in the use of rb_rot_left() and rb_rot_right().
104  */
105 #define RB_OTHER_ROTATE(n, o, d) (((d) == RB_LEFT) ? \
106  rb_rot_right((n), (o)) : \
107  rb_rot_left((n), (o)))
108 
109 /*
110  * Functions internal to LIBREDBLACK
111  */
112 
113 /**
114  * Return a node adjacent to a given red-black node
115  *
116  * This function has three parameters: the node of interest, the order
117  * on which to do the search, and the sense (min or max, which is to
118  * say predecessor or successor). rb_neighbor() returns a pointer to
119  * the adjacent node. This function is modeled after the routine
120  * TREE-SUCCESSOR on p. 249 of Cormen et al.
121  */
122 extern struct bu_rb_node *rb_neighbor(struct bu_rb_node *node, int order, int sense);
123 
124 /** @file rb_rotate.c
125  *
126  * Routines to perform rotations on a red-black tree
127  *
128  */
129 
130 /**
131  * Perform left rotation on a red-black tree
132  *
133  * This function has two parameters: the node about which to rotate
134  * and the order to be rotated. rb_rot_left() is an implementation of
135  * the routine called LEFT-ROTATE on p. 266 of Cormen et al., with
136  * modification on p. 285.
137  */
138 extern void rb_rot_left(struct bu_rb_node *x, int order);
139 
140 /**
141  * Perform right rotation on a red-black tree
142  *
143  * This function has two parameters: the node about which to rotate
144  * and the order to be rotated. rb_rot_right() is hacked from
145  * rb_rot_left() above.
146  */
147 extern void rb_rot_right(struct bu_rb_node *y, int order);
148 
149 /**
150  * Traverse a red-black tree
151  *
152  * This function has five parameters: the tree to traverse, the order
153  * on which to do the walking, the function to apply to each node,
154  * whether to apply the function to the entire node (or just to its
155  * data), and the type of traversal (preorder, inorder, or postorder).
156  *
157  * N.B. rb_walk() is not declared static because it is called by
158  * bu_rb_diagnose_tree() in rb_diag.c.
159  */
160 extern void rb_walk(struct bu_rb_tree *tree, int order, void (*visit) (void), int what_to_visit, int trav_type);
161 
162 /**
163  * Relinquish memory occupied by a red-black node
164  *
165  * This function has one parameter: a node to free. rb_free_node()
166  * frees the memory allocated for the various members of the node and
167  * then frees the memory allocated for the node itself.
168  */
169 extern void rb_free_node(struct bu_rb_node *node);
170 
171 /**
172  * Relinquish memory occupied by a red-black package
173  *
174  * This function has one parameter: a package to free.
175  * rb_free_package() frees the memory allocated to point to the
176  * nodes that contained the package and then frees the memory
177  * allocated for the package itself.
178  */
179 extern void rb_free_package(struct bu_rb_package *package);
180 
181 #endif /* LIBBU_RB_INTERNALS_H */
182 
183 
184 /*
185  * Local Variables:
186  * mode: C
187  * tab-width: 8
188  * indent-tabs-mode: t
189  * c-file-style: "stroustrup"
190  * End:
191  * ex: shiftwidth=4 tabstop=8
192  */
void rb_rot_right(struct bu_rb_node *y, int order)
Definition: rb_rotate.c:73
Definition: rb.h:109
Definition: rb.h:204
Header file for the BRL-CAD common definitions.
struct bu_rb_node * rb_neighbor(struct bu_rb_node *node, int order, int sense)
Definition: rb_extreme.c:91
void rb_rot_left(struct bu_rb_node *x, int order)
Definition: rb_rotate.c:32
void rb_free_node(struct bu_rb_node *node)
Definition: rb_free.c:81
void rb_free_package(struct bu_rb_package *package)
Definition: rb_free.c:111
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