BRL-CAD
rb_rotate.c
Go to the documentation of this file.
1 /* R B _ R O T A 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 void
32 rb_rot_left(struct bu_rb_node *x, int order)
33 {
34  struct bu_rb_node *y; /* x's child to pivot up */
35  struct bu_rb_node *beta; /* y's child in direction of rot. */
36  struct bu_rb_node *x_parent; /* x's parent */
37  struct bu_rb_tree *tree = x->rbn_tree; /* Tree where it all happens */
38 
39  /*
40  * Set y and check data types of both x and y
41  */
42  BU_CKMAG(x, BU_RB_NODE_MAGIC, "red-black node");
43  RB_CKORDER(x->rbn_tree, order);
44 
45  y = RB_RIGHT_CHILD(x, order);
46 
48  bu_log("rb_rot_left(<%p>, %d)...\n", (void*)x, order);
49 
50  RB_RIGHT_CHILD(x, order) = beta = RB_LEFT_CHILD(y, order);
51  if (beta != RB_NULL(tree))
52  RB_PARENT(beta, order) = x;
53  RB_PARENT(y, order) = x_parent = RB_PARENT(x, order);
54  if (x_parent == RB_NULL(tree))
55  RB_ROOT(tree, order) = y;
56  else if (x == RB_LEFT_CHILD(x_parent, order))
57  RB_LEFT_CHILD(x_parent, order) = y;
58  else
59  RB_RIGHT_CHILD(x_parent, order) = y;
60  RB_LEFT_CHILD(y, order) = x;
61  RB_PARENT(x, order) = y;
62 
63  RB_SIZE(y, order) = RB_SIZE(x, order);
64  RB_SIZE(x, order) =
65  RB_SIZE(RB_LEFT_CHILD(x, order), order) +
66  RB_SIZE(RB_RIGHT_CHILD(x, order), order) + 1;
67  if (UNLIKELY(tree->rbt_debug & BU_RB_DEBUG_OS))
68  bu_log("After rotation, size(%p, %d)=%d, size(%p, %d)=%d\n",
69  (void*)x, order, RB_SIZE(x, order), (void*)y, order, RB_SIZE(y, order));
70 }
71 
72 
73 void rb_rot_right (struct bu_rb_node *y, int order)
74 {
75  struct bu_rb_node *x; /* y's child to pivot up */
76  struct bu_rb_node *beta; /* x's child in direction of rot. */
77  struct bu_rb_node *y_parent; /* y's parent */
78  struct bu_rb_tree *tree = y->rbn_tree; /* Tree where it all happens */
79 
80  /*
81  * Set x and check data types of both x and y
82  */
83  BU_CKMAG(y, BU_RB_NODE_MAGIC, "red-black node");
84  RB_CKORDER(y->rbn_tree, order);
85 
86  x = RB_LEFT_CHILD(y, order);
87 
89  bu_log("rb_rot_right(<%p>, %d)...\n", (void*)y, order);
90 
91  RB_LEFT_CHILD(y, order) = beta = RB_RIGHT_CHILD(x, order);
92  if (beta != RB_NULL(tree))
93  RB_PARENT(beta, order) = y;
94  RB_PARENT(x, order) = y_parent = RB_PARENT(y, order);
95  if (y_parent == RB_NULL(tree))
96  RB_ROOT(tree, order) = x;
97  else if (y == RB_LEFT_CHILD(y_parent, order))
98  RB_LEFT_CHILD(y_parent, order) = x;
99  else
100  RB_RIGHT_CHILD(y_parent, order) = x;
101  RB_RIGHT_CHILD(x, order) = y;
102  RB_PARENT(y, order) = x;
103 
104  RB_SIZE(x, order) = RB_SIZE(y, order);
105  RB_SIZE(y, order) =
106  RB_SIZE(RB_LEFT_CHILD(y, order), order) +
107  RB_SIZE(RB_RIGHT_CHILD(y, order), order) + 1;
108  if (UNLIKELY(tree->rbt_debug & BU_RB_DEBUG_OS))
109  bu_log("After rotation, size(%p, %d)=%d, size(%p, %d)=%d\n",
110  (void*)x, order, RB_SIZE(x, order), (void*)y, order, RB_SIZE(y, order));
111 }
112 
113 /** @} */
114 
115 /*
116  * Local Variables:
117  * mode: C
118  * tab-width: 8
119  * indent-tabs-mode: t
120  * c-file-style: "stroustrup"
121  * End:
122  * ex: shiftwidth=4 tabstop=8
123  */
#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
Definition: rb.h:109
#define BU_CKMAG(_ptr, _magic, _str)
Definition: magic.h:233
Definition: rb.h:204
#define BU_RB_DEBUG_OS
Definition: rb.h:175
void rb_rot_left(struct bu_rb_node *x, int order)
Definition: rb_rotate.c:32
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_NODE_MAGIC
Definition: magic.h:61
struct bu_rb_tree * rbn_tree
Definition: rb.h:207
#define RB_CKORDER(t, o)
Definition: rb_internals.h:33
#define RB_ROOT(t, o)
Definition: rb_internals.h:46
void rb_rot_right(struct bu_rb_node *y, int order)
Definition: rb_rotate.c:73
#define BU_RB_DEBUG_ROTATE
Definition: rb.h:174
int rbt_debug
Definition: rb.h:116
#define RB_SIZE(n, o)
Definition: rb_internals.h:71
#define UNLIKELY(expression)
Definition: common.h:282