BRL-CAD
rb_delete.c
Go to the documentation of this file.
1 /* R B _ D E L E T E . 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  * Restore the red-black properties of a red-black tree after the
33  * splicing out of a node
34  *
35  * This function has three parameters: the tree to be fixed up, the
36  * node where the trouble occurs, and the order. _rb_fixup() is an
37  * implementation of the routine RB-DELETE-FIXUP on p. 274 of Cormen
38  * et al. (p. 326 in the paperback version of the 2009 edition).
39  */
40 HIDDEN void
41 _rb_fixup(struct bu_rb_tree *tree, struct bu_rb_node *node, int order)
42 {
43  int direction;
44  struct bu_rb_node *parent;
45  struct bu_rb_node *w;
46 
47  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
48  BU_CKMAG(node, BU_RB_NODE_MAGIC, "red-black node");
49  RB_CKORDER(tree, order);
50 
51  while ((node != RB_ROOT(tree, order))
52  && (RB_GET_COLOR(node, order) == RB_BLK))
53  {
54  parent = RB_PARENT(node, order);
55  if (node == RB_LEFT_CHILD(parent, order))
56  direction = RB_LEFT;
57  else
58  direction = RB_RIGHT;
59 
60  w = RB_OTHER_CHILD(parent, order, direction);
61  if (RB_GET_COLOR(w, order) == RB_RED) {
62  RB_SET_COLOR(w, order, RB_BLK);
63  RB_SET_COLOR(parent, order, RB_RED);
64  RB_ROTATE(parent, order, direction);
65  w = RB_OTHER_CHILD(parent, order, direction);
66  }
67  if ((RB_GET_COLOR(RB_CHILD(w, order, direction), order) == RB_BLK)
68  && (RB_GET_COLOR(RB_OTHER_CHILD(w, order, direction), order) == RB_BLK))
69  {
70  RB_SET_COLOR(w, order, RB_RED);
71  node = parent;
72  } else {
73  if (RB_GET_COLOR(RB_OTHER_CHILD(w, order, direction), order) == RB_BLK) {
74  RB_SET_COLOR(RB_CHILD(w, order, direction), order, RB_BLK);
75  RB_SET_COLOR(w, order, RB_RED);
76  RB_OTHER_ROTATE(w, order, direction);
77  w = RB_OTHER_CHILD(parent, order, direction);
78  }
79  RB_SET_COLOR(w, order, RB_GET_COLOR(parent, order));
80  RB_SET_COLOR(parent, order, RB_BLK);
81  RB_SET_COLOR(RB_OTHER_CHILD(w, order, direction),
82  order, RB_BLK);
83  RB_ROTATE(parent, order, direction);
84  node = RB_ROOT(tree, order);
85  }
86  }
87  RB_SET_COLOR(node, order, RB_BLK);
88 }
89 
90 /**
91  * Delete a node from one order of a red-black tree
92  *
93  * This function has three parameters: a tree, the node to delete, and
94  * the order from which to delete it. _rb_delete() is an
95  * implementation of the routine RB-DELETE on p. 273 of Cormen et
96  * al. (p. 324 in the paperback version of the 2009 edition).
97  */
98 HIDDEN void
99 _rb_delete(struct bu_rb_tree *tree, struct bu_rb_node *node, int order)
100 {
101  struct bu_rb_node *y; /* The node to splice out */
102  struct bu_rb_node *parent;
103  struct bu_rb_node *only_child;
104 
105  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
106  BU_CKMAG(node, BU_RB_NODE_MAGIC, "red-black node");
107  RB_CKORDER(tree, order);
108 
110  bu_log("_rb_delete(%p, %p, %d): data=%p\n",
111  (void*)tree, (void*)node, order, RB_DATA(node, order));
112 
113  if ((RB_LEFT_CHILD(node, order) == RB_NULL(tree))
114  || (RB_RIGHT_CHILD(node, order) == RB_NULL(tree)))
115  y = node;
116  else
117  y = rb_neighbor(node, order, SENSE_MAX);
118 
119  if (RB_LEFT_CHILD(y, order) == RB_NULL(tree))
120  only_child = RB_RIGHT_CHILD(y, order);
121  else
122  only_child = RB_LEFT_CHILD(y, order);
123 
124  parent = RB_PARENT(only_child, order) = RB_PARENT(y, order);
125  if (parent == RB_NULL(tree))
126  RB_ROOT(tree, order) = only_child;
127  else if (y == RB_LEFT_CHILD(parent, order))
128  RB_LEFT_CHILD(parent, order) = only_child;
129  else
130  RB_RIGHT_CHILD(parent, order) = only_child;
131 
132  /*
133  * Splice y out if it's not node
134  */
135  if (y != node) {
136  (node->rbn_package)[order] = (y->rbn_package)[order];
137  ((node->rbn_package)[order]->rbp_node)[order] = node;
138  }
139 
140  if (RB_GET_COLOR(y, order) == RB_BLK)
141  _rb_fixup(tree, only_child, order);
142 
143  if (--(y->rbn_pkg_refs) == 0)
144  rb_free_node(y);
145 }
146 
147 
148 void
149 bu_rb_delete(struct bu_rb_tree *tree, int order)
150 {
151  int nm_orders;
152  struct bu_rb_node **node; /* Nodes containing data */
153  struct bu_rb_package *package;
154 
155  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
156  RB_CKORDER(tree, order);
157 
158  if (UNLIKELY(tree->rbt_nm_nodes <= 0)) {
159  bu_log("ERROR: Attempt to delete from tree with %d nodes\n",
160  tree->rbt_nm_nodes);
161  bu_bomb("");
162  }
163  if (UNLIKELY(RB_CURRENT(tree) == RB_NULL(tree))) {
164  bu_log("Warning: bu_rb_delete(): current node is undefined\n");
165  return;
166  }
167 
168  nm_orders = tree->rbt_nm_orders;
169  package = (RB_CURRENT(tree)->rbn_package)[order];
170 
171  node = (struct bu_rb_node **)
172  bu_malloc(nm_orders * sizeof(struct bu_rb_node *), "node list");
173 
174  for (order = 0; order < nm_orders; ++order)
175  node[order] = (package->rbp_node)[order];
176 
177  /*
178  * Do the deletion from each order
179  */
180  for (order = 0; order < nm_orders; ++order)
181  _rb_delete(tree, node[order], order);
182 
183  --(tree->rbt_nm_nodes);
184  rb_free_package(package);
185  bu_free((void *) node, "node list");
186 }
187 
188 
189 /*
190  * Local Variables:
191  * mode: C
192  * tab-width: 8
193  * indent-tabs-mode: t
194  * c-file-style: "stroustrup"
195  * End:
196  * ex: shiftwidth=4 tabstop=8
197  */
#define RB_PARENT(n, o)
Definition: rb_internals.h:60
#define RB_RIGHT_CHILD(n, o)
Definition: rb_internals.h:62
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
int rbn_pkg_refs
Definition: rb.h:214
Definition: rb.h:109
#define BU_CKMAG(_ptr, _magic, _str)
Definition: magic.h:233
Definition: rb.h:204
#define RB_LEFT
Definition: rb_internals.h:63
void rb_free_package(struct bu_rb_package *package)
Definition: rb_free.c:111
struct bu_rb_node ** rbp_node
Definition: rb.h:191
#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
HIDDEN void _rb_delete(struct bu_rb_tree *tree, struct bu_rb_node *node, int order)
Definition: rb_delete.c:99
#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
struct bu_rb_node * rb_neighbor(struct bu_rb_node *node, int order, int sense)
Definition: rb_extreme.c:91
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
#define RB_OTHER_CHILD(n, o, d)
Definition: rb_internals.h:68
#define RB_GET_COLOR(n, o)
Definition: rb_internals.h:72
#define RB_CURRENT(t)
Definition: rb_internals.h:47
#define RB_RIGHT
Definition: rb_internals.h:64
#define BU_RB_TREE_MAGIC
Definition: magic.h:63
#define RB_CKORDER(t, o)
Definition: rb_internals.h:33
void bu_rb_delete(struct bu_rb_tree *tree, int order)
Definition: rb_delete.c:149
#define RB_ROOT(t, o)
Definition: rb_internals.h:46
void rb_free_node(struct bu_rb_node *node)
Definition: rb_free.c:81
int rbt_nm_orders
Definition: rb.h:120
HIDDEN void _rb_fixup(struct bu_rb_tree *tree, struct bu_rb_node *node, int order)
Definition: rb_delete.c:41
int rbt_nm_nodes
Definition: rb.h:112
#define RB_BLK
Definition: rb_internals.h:81
struct bu_rb_package ** rbn_package
Definition: rb.h:213
#define BU_RB_DEBUG_DELETE
Definition: rb.h:176
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define RB_OTHER_ROTATE(n, o, d)
Definition: rb_internals.h:105
#define SENSE_MAX
Definition: rb.h:223
#define RB_DATA(n, o)
Definition: rb_internals.h:82
#define RB_CHILD(n, o, d)
Definition: rb_internals.h:65
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
int rbt_debug
Definition: rb.h:116
#define UNLIKELY(expression)
Definition: common.h:282