BRL-CAD
rb_insert.c
Go to the documentation of this file.
1 /* R B _ I N S E R T . 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  * Insert a node into one linear order of a red-black tree
33  *
34  * This function has three parameters: the tree and linear order into
35  * which to insert the new node and the new node itself. If the node
36  * is equal (modulo the linear order) to a node already in the tree,
37  * _rb_insert() returns 1. Otherwise, it returns 0.
38  */
39 HIDDEN int
40 _rb_insert(struct bu_rb_tree *tree, int order, struct bu_rb_node *new_node)
41 {
42  struct bu_rb_node *node;
43  struct bu_rb_node *parent;
44  struct bu_rb_node *grand_parent;
45  struct bu_rb_node *y;
46  int (*compare)(const void *, const void *);
47  int comparison = 0xdeadbeef;
48  int direction;
49  int result = 0;
50 
51 
52  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
53  RB_CKORDER(tree, order);
54  BU_CKMAG(new_node, BU_RB_NODE_MAGIC, "red-black node");
55 
56  /*
57  * Initialize the new node
58  */
59  RB_PARENT(new_node, order) =
60  RB_LEFT_CHILD(new_node, order) =
61  RB_RIGHT_CHILD(new_node, order) = RB_NULL(tree);
62  RB_SIZE(new_node, order) = 1;
63  if (UNLIKELY(tree->rbt_debug & BU_RB_DEBUG_OS))
64  bu_log("_rb_insert(%p): size(%p, %d)=%d\n",
65  (void*)new_node, (void*)new_node, order, RB_SIZE(new_node, order));
66 
67  /*
68  * Perform vanilla-flavored binary-tree insertion
69  */
70  parent = RB_NULL(tree);
71  node = RB_ROOT(tree, order);
72  compare = RB_COMPARE_FUNC(tree, order);
73  while (node != RB_NULL(tree)) {
74  parent = node;
75  ++RB_SIZE(parent, order);
76  if (UNLIKELY(tree->rbt_debug & BU_RB_DEBUG_OS))
77  bu_log("_rb_insert(%p): size(%p, %d)=%d\n",
78  (void*)new_node, (void*)parent, order, RB_SIZE(parent, order));
79  comparison = compare(RB_DATA(new_node, order),
80  RB_DATA(node, order));
81  if (comparison < 0) {
83  bu_log("_rb_insert(%p): <_%d <%p>, going left\n",
84  (void*)new_node, order, (void*)node);
85  node = RB_LEFT_CHILD(node, order);
86  } else {
88  bu_log("_rb_insert(%p): >=_%d <%p>, going right\n",
89  (void*)new_node, order, (void*)node);
90  node = RB_RIGHT_CHILD(node, order);
91  if (comparison == 0)
92  result = 1;
93  }
94  }
95  RB_PARENT(new_node, order) = parent;
96  if (parent == RB_NULL(tree))
97  RB_ROOT(tree, order) = new_node;
98  else if ((compare(RB_DATA(new_node, order),
99  RB_DATA(parent, order))) < 0)
100  RB_LEFT_CHILD(parent, order) = new_node;
101  else
102  RB_RIGHT_CHILD(parent, order) = new_node;
103 
104  /*
105  * Reestablish the red-black properties, as necessary
106  */
107  RB_SET_COLOR(new_node, order, RB_RED);
108  node = new_node;
109  parent = RB_PARENT(node, order);
110  grand_parent = RB_PARENT(parent, order);
111  while ((node != RB_ROOT(tree, order))
112  && (RB_GET_COLOR(parent, order) == RB_RED))
113  {
114  if (parent == RB_LEFT_CHILD(grand_parent, order))
115  direction = RB_LEFT;
116  else
117  direction = RB_RIGHT;
118 
119  y = RB_OTHER_CHILD(grand_parent, order, direction);
120  if (RB_GET_COLOR(y, order) == RB_RED) {
121  RB_SET_COLOR(parent, order, RB_BLK);
122  RB_SET_COLOR(y, order, RB_BLK);
123  RB_SET_COLOR(grand_parent, order, RB_RED);
124  node = grand_parent;
125  parent = RB_PARENT(node, order);
126  grand_parent = RB_PARENT(parent, order);
127  } else {
128  if (node == RB_OTHER_CHILD(parent, order, direction)) {
129  node = parent;
130  RB_ROTATE(node, order, direction);
131  parent = RB_PARENT(node, order);
132  grand_parent = RB_PARENT(parent, order);
133  }
134  RB_SET_COLOR(parent, order, RB_BLK);
135  RB_SET_COLOR(grand_parent, order, RB_RED);
136  RB_OTHER_ROTATE(grand_parent, order, direction);
137  }
138  }
139  RB_SET_COLOR(RB_ROOT(tree, order), order, RB_BLK);
140 
142  bu_log("_rb_insert(%p): comparison = %d, returning %d\n",
143  (void*)new_node, comparison, result);
144 
145  return result;
146 }
147 
148 
149 int
151 {
152  int nm_orders;
153  int order;
154  int result = 0;
155  struct bu_rb_node *node;
156  struct bu_rb_package *package;
157  struct bu_rb_list *rblp;
158 
159  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
160 
161  nm_orders = tree->rbt_nm_orders;
162 
163  /*
164  * Enforce uniqueness
165  *
166  * NOTE: The approach is that for each order that requires
167  * uniqueness, we look for a match. This is not the most
168  * efficient way to do things, since _rb_insert() is just going to
169  * turn around and search the tree all over again.
170  */
171  for (order = 0; order < nm_orders; ++order) {
172  if (RB_GET_UNIQUENESS(tree, order) &&
173  (bu_rb_search(tree, order, data) != NULL))
174  {
175  if (UNLIKELY(tree->rbt_debug & BU_RB_DEBUG_UNIQ))
176  bu_log("bu_rb_insert(<%p>, <%p>, TBD) will return %d\n",
177  (void*)tree, (void*)data, -(order + 1));
178  return -(order + 1);
179  }
180  }
181 
182  /*
183  * Make a new package and add it to the list of all packages.
184  */
185  BU_ALLOC(package, struct bu_rb_package);
186  package->rbp_node = (struct bu_rb_node **)
187  bu_malloc(nm_orders * sizeof(struct bu_rb_node *),
188  "red-black package nodes");
189 
190  BU_ALLOC(rblp, struct bu_rb_list);
191  rblp->rbl_magic = BU_RB_LIST_MAGIC;
192  rblp->rbl_package = package;
193 
194  BU_LIST_PUSH(&(tree->rbt_packages.l), rblp);
195  package->rbp_list_pos = rblp;
196 
197  /*
198  * Make a new node and add it to the list of all nodes.
199  */
200  node = (struct bu_rb_node *)
201  bu_malloc(sizeof(struct bu_rb_node), "red-black node");
202  node->rbn_parent = (struct bu_rb_node **)
203  bu_malloc(nm_orders * sizeof(struct bu_rb_node *),
204  "red-black parents");
205  node->rbn_left = (struct bu_rb_node **)
206  bu_malloc(nm_orders * sizeof(struct bu_rb_node *),
207  "red-black left children");
208  node->rbn_right = (struct bu_rb_node **)
209  bu_malloc(nm_orders * sizeof(struct bu_rb_node *),
210  "red-black right children");
211  node->rbn_color = (char *)
212  bu_malloc((size_t) lrint(ceil((double) (nm_orders / 8.0))),
213  "red-black colors");
214  node->rbn_size = (int *)
215  bu_malloc(nm_orders * sizeof(int),
216  "red-black subtree sizes");
217  node->rbn_package = (struct bu_rb_package **)
218  bu_malloc(nm_orders * sizeof(struct bu_rb_package *),
219  "red-black packages");
220 
221  BU_ALLOC(rblp, struct bu_rb_list);
222  rblp->rbl_magic = BU_RB_LIST_MAGIC;
223  rblp->rbl_node = node;
224 
225  BU_LIST_PUSH(&(tree->rbt_nodes.l), rblp);
226  node->rbn_list_pos = rblp;
227 
228  /*
229  * Fill in the package
230  */
231  package->rbp_magic = BU_RB_PKG_MAGIC;
232  package->rbp_data = data;
233  for (order = 0; order < nm_orders; ++order)
234  (package->rbp_node)[order] = node;
235 
236  /*
237  * Fill in the node
238  */
239  node->rbn_magic = BU_RB_NODE_MAGIC;
240  node->rbn_tree = tree;
241  for (order = 0; order < nm_orders; ++order)
242  (node->rbn_package)[order] = package;
243  node->rbn_pkg_refs = nm_orders;
244 
245  /*
246  * If the tree was empty, install this node as the root and give
247  * it a null parent and null children
248  */
249  if (RB_ROOT(tree, 0) == RB_NULL(tree)) {
250  for (order = 0; order < nm_orders; ++order) {
251  RB_ROOT(tree, order) = node;
252  RB_PARENT(node, order) =
253  RB_LEFT_CHILD(node, order) =
254  RB_RIGHT_CHILD(node, order) = RB_NULL(tree);
255  RB_SET_COLOR(node, order, RB_BLK);
256  RB_SIZE(node, order) = 1;
257  if (UNLIKELY(tree->rbt_debug & BU_RB_DEBUG_OS))
258  bu_log("bu_rb_insert(<%p>, <%p>, <%p>): size(%p, %d)=%d\n",
259  (void*)tree, (void*)data, (void*)node, (void*)node, order, RB_SIZE(node, order));
260  }
261  } else {
262  /* Otherwise, insert the node into the tree */
263  for (order = 0; order < nm_orders; ++order)
264  result += _rb_insert(tree, order, node);
265  if (UNLIKELY(tree->rbt_debug & BU_RB_DEBUG_UNIQ))
266  bu_log("bu_rb_insert(<%p>, <%p>, <%p>) will return %d\n",
267  (void*)tree, (void*)data, (void*)node, result);
268  }
269 
270  ++(tree->rbt_nm_nodes);
271  RB_CURRENT(tree) = node;
272  return result;
273 }
274 
275 
276 /**
277  * Raise or lower the uniqueness flag for one linear order of a
278  * red-black tree
279  *
280  * This function has three parameters: the tree, the order for which
281  * to modify the flag, and the new value for the flag. _rb_set_uniq()
282  * sets the specified flag to the specified value and returns the
283  * previous value of the flag.
284  */
285 HIDDEN int
286 _rb_set_uniq(struct bu_rb_tree *tree, int order, int new_value)
287 {
288  int prev_value;
289 
290  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
291  RB_CKORDER(tree, order);
292  new_value = (new_value != 0);
293 
294  prev_value = RB_GET_UNIQUENESS(tree, order);
295  RB_SET_UNIQUENESS(tree, order, new_value);
296  return prev_value;
297 }
298 
299 
300 int
301 bu_rb_uniq_on(struct bu_rb_tree *tree, int order)
302 {
303  return _rb_set_uniq(tree, order, 1);
304 }
305 
306 int
307 bu_rb_uniq_off(struct bu_rb_tree *tree, int order)
308 {
309  return _rb_set_uniq(tree, order, 0);
310 }
311 
312 
313 int
314 bu_rb_is_uniq(struct bu_rb_tree *tree, int order)
315 {
316  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
317  RB_CKORDER(tree, order);
318 
319  return RB_GET_UNIQUENESS(tree, order);
320 }
321 
322 
323 void
325 {
326  int nm_orders;
327  int order;
328 
329  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
330 
331  nm_orders = tree->rbt_nm_orders;
332  for (order = 0; order < nm_orders; ++order)
333  RB_SET_UNIQUENESS(tree, order, 0);
334 
335  for (order = 0; (flag_rep != 0) && (order < nm_orders); flag_rep >>= 1,
336  ++order)
337  if (flag_rep & 0x1)
338  RB_SET_UNIQUENESS(tree, order, 1);
339 
340  if (UNLIKELY(flag_rep != 0))
341  bu_log("bu_rb_set_uniqv(): Ignoring bits beyond rightmost %d\n", nm_orders);
342 }
343 
344 
345 /**
346  * Raise or lower the uniqueness flags for all the linear orders of a
347  * red-black tree
348  *
349  * This function has two parameters: the tree, and the new value for
350  * all the flags.
351  */
352 HIDDEN void
353 _rb_set_uniq_all(struct bu_rb_tree *tree, int new_value)
354 {
355  int nm_orders;
356  int order;
357 
358  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
359  new_value = (new_value != 0);
360 
361  nm_orders = tree->rbt_nm_orders;
362  for (order = 0; order < nm_orders; ++order)
363  RB_SET_UNIQUENESS(tree, order, new_value);
364 }
365 
366 
368 {
369  _rb_set_uniq_all(tree, 1);
370 }
371 
372 
374 {
375  _rb_set_uniq_all(tree, 0);
376 }
377 
378 
379 /*
380  * Local Variables:
381  * mode: C
382  * tab-width: 8
383  * indent-tabs-mode: t
384  * c-file-style: "stroustrup"
385  * End:
386  * ex: shiftwidth=4 tabstop=8
387  */
#define BU_RB_DEBUG_INSERT
Definition: rb.h:172
#define RB_PARENT(n, o)
Definition: rb_internals.h:60
struct bu_rb_node ** rbn_parent
Definition: rb.h:208
#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_uniq_all_on(struct bu_rb_tree *tree)
Definition: rb_insert.c:367
struct bu_rb_list * rbn_list_pos
Definition: rb.h:215
struct bu_rb_node ** rbn_left
Definition: rb.h:209
int rbn_pkg_refs
Definition: rb.h:214
Definition: rb.h:109
#define BU_CKMAG(_ptr, _magic, _str)
Definition: magic.h:233
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
#define RB_LEFT
Definition: rb_internals.h:63
#define BU_RB_DEBUG_OS
Definition: rb.h:175
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
#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
#define RB_NULL(t)
Definition: rb_internals.h:48
#define BU_RB_DEBUG_UNIQ
Definition: rb.h:173
uint32_t rbp_magic
Definition: rb.h:190
#define HIDDEN
Definition: common.h:86
#define RB_SET_COLOR(n, o, c)
Definition: rb_internals.h:74
#define BU_RB_NODE_MAGIC
Definition: magic.h:61
#define RB_ROTATE(n, o, d)
Definition: rb_internals.h:96
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
HIDDEN void _rb_set_uniq_all(struct bu_rb_tree *tree, int new_value)
Definition: rb_insert.c:353
#define RB_OTHER_CHILD(n, o, d)
Definition: rb_internals.h:68
#define RB_GET_COLOR(n, o)
Definition: rb_internals.h:72
COMPLEX data[64]
Definition: fftest.c:34
#define RB_CURRENT(t)
Definition: rb_internals.h:47
int bu_rb_is_uniq(struct bu_rb_tree *tree, int order)
Definition: rb_insert.c:314
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
struct bu_rb_list * rbp_list_pos
Definition: rb.h:192
#define RB_RIGHT
Definition: rb_internals.h:64
#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
int * rbn_size
Definition: rb.h:212
#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_LIST_PUSH(hp, p)
Definition: list.h:246
#define RB_COMPARE_FUNC(t, o)
Definition: rb_internals.h:44
int rbt_nm_nodes
Definition: rb.h:112
HIDDEN int _rb_set_uniq(struct bu_rb_tree *tree, int order, int new_value)
Definition: rb_insert.c:286
void bu_rb_uniq_all_off(struct bu_rb_tree *tree)
Definition: rb_insert.c:373
char * rbn_color
Definition: rb.h:211
HIDDEN int _rb_insert(struct bu_rb_tree *tree, int order, struct bu_rb_node *new_node)
Definition: rb_insert.c:40
uint32_t rbn_magic
Definition: rb.h:206
#define RB_BLK
Definition: rb_internals.h:81
#define BU_RB_PKG_MAGIC
Definition: magic.h:62
struct bu_rb_package ** rbn_package
Definition: rb.h:213
int bu_rb_insert(struct bu_rb_tree *tree, void *data)
Definition: rb_insert.c:150
#define RB_OTHER_ROTATE(n, o, d)
Definition: rb_internals.h:105
#define RB_GET_UNIQUENESS(t, o)
Definition: rb_internals.h:49
struct bu_rb_node ** rbn_right
Definition: rb.h:210
#define RB_DATA(n, o)
Definition: rb_internals.h:82
struct bu_list l
Definition: rb.h:82
#define RB_SET_UNIQUENESS(t, o, u)
Definition: rb_internals.h:50
void bu_rb_set_uniqv(struct bu_rb_tree *tree, bitv_t flag_rep)
Definition: rb_insert.c:324
#define BU_RB_LIST_MAGIC
Definition: magic.h:60
int rbt_debug
Definition: rb.h:116
Definition: rb.h:80
#define RB_SIZE(n, o)
Definition: rb_internals.h:71
#define UNLIKELY(expression)
Definition: common.h:282