BRL-CAD
rb_extreme.c
Go to the documentation of this file.
1 /* R B _ E X T R E M 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  * Find the minimum or maximum node in one order of a red-black tree
33  *
34  * This function has four parameters: the root of the tree, the
35  * order, the sense (min or max), and the address to be understood
36  * as the nil node pointer. rb_extreme() returns a pointer to the
37  * extreme node.
38  */
39 HIDDEN struct bu_rb_node *
40 _rb_extreme(struct bu_rb_node *root, int order, int sense, struct bu_rb_node *empty_node)
41 {
42  struct bu_rb_node *child;
43  struct bu_rb_tree *tree;
44 
45  if (root == empty_node)
46  return root;
47 
48  while (1) {
49  BU_CKMAG(root, BU_RB_NODE_MAGIC, "red-black node");
50  tree = root->rbn_tree;
51  RB_CKORDER(tree, order);
52 
53  child = (sense == SENSE_MIN) ? RB_LEFT_CHILD(root, order) :
54  RB_RIGHT_CHILD(root, order);
55  if (child == empty_node)
56  break;
57  root = child;
58  }
59 
60  /* Record the node with which we've been working */
61  RB_CURRENT(tree) = root;
62 
63  return root;
64 }
65 
66 
67 void *
68 bu_rb_extreme(struct bu_rb_tree *tree, int order, int sense)
69 {
70  struct bu_rb_node *node;
71 
72  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
73  RB_CKORDER(tree, order);
74 
75  if (UNLIKELY((sense != SENSE_MIN) && (sense != SENSE_MAX))) {
76  bu_log("ERROR: bu_rb_extreme(): invalid sense %d, file %s, line %d\n", sense, __FILE__, __LINE__);
77  return NULL;
78  }
79 
80  /* Wade through the tree */
81  node = _rb_extreme(RB_ROOT(tree, order), order, sense, RB_NULL(tree));
82 
83  if (node == RB_NULL(tree))
84  return NULL;
85  else
86  return RB_DATA(node, order);
87 }
88 
89 
90 struct bu_rb_node *
91 rb_neighbor(struct bu_rb_node *node, int order, int sense)
92 {
93  struct bu_rb_node *child;
94  struct bu_rb_node *parent;
95  struct bu_rb_tree *tree;
96  struct bu_rb_node *empty_node;
97 
98  BU_CKMAG(node, BU_RB_NODE_MAGIC, "red-black node");
99  tree = node->rbn_tree;
100  RB_CKORDER(tree, order);
101 
102  empty_node = RB_NULL(tree);
103 
104  child = (sense == SENSE_MIN) ? RB_LEFT_CHILD(node, order) :
105  RB_RIGHT_CHILD(node, order);
106  if (child != empty_node)
107  return _rb_extreme(child, order, 1 - sense, empty_node);
108  parent = RB_PARENT(node, order);
109  while ((parent != empty_node) &&
110  (node == RB_CHILD(parent, order, sense)))
111  {
112  node = parent;
113  parent = RB_PARENT(parent, order);
114  }
115 
116  /* Record the node with which we've been working */
117  RB_CURRENT(tree) = parent;
118 
119  return parent;
120 }
121 
122 
123 void *
124 bu_rb_neighbor(struct bu_rb_tree *tree, int order, int sense)
125 {
126  struct bu_rb_node *node;
127 
128  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
129  RB_CKORDER(tree, order);
130 
131  if (UNLIKELY((sense != SENSE_MIN) && (sense != SENSE_MAX))) {
132  bu_log("ERROR: bu_rb_neighbor(): invalid sense %d, file %s, line %d\n", sense, __FILE__, __LINE__);
133  return NULL;
134  }
135 
136  /* Wade through the tree */
137  node = rb_neighbor(RB_CURRENT(tree), order, sense);
138 
139  if (node == RB_NULL(tree)) {
140  return NULL;
141  } else {
142  /* Record the node with which we've been working */
143  RB_CURRENT(tree) = node;
144  return RB_DATA(node, order);
145  }
146 }
147 
148 
149 void *
150 bu_rb_curr(struct bu_rb_tree *tree, int order)
151 {
152  BU_CKMAG(tree, BU_RB_TREE_MAGIC, "red-black tree");
153  RB_CKORDER(tree, order);
154 
155  if (RB_CURRENT(tree) == RB_NULL(tree))
156  return NULL;
157  else
158  return RB_DATA(RB_CURRENT(tree), order);
159 }
160 
161 
162 /*
163  * Local Variables:
164  * mode: C
165  * tab-width: 8
166  * indent-tabs-mode: t
167  * c-file-style: "stroustrup"
168  * End:
169  * ex: shiftwidth=4 tabstop=8
170  */
#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
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
void * bu_rb_extreme(struct bu_rb_tree *tree, int order, int sense)
Definition: rb_extreme.c:68
#define HIDDEN
Definition: common.h:86
#define BU_RB_NODE_MAGIC
Definition: magic.h:61
struct bu_rb_node * rb_neighbor(struct bu_rb_node *node, int order, int sense)
Definition: rb_extreme.c:91
#define RB_CURRENT(t)
Definition: rb_internals.h:47
#define SENSE_MIN
Definition: rb.h:222
#define BU_RB_TREE_MAGIC
Definition: magic.h:63
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
#define RB_CKORDER(t, o)
Definition: rb_internals.h:33
#define RB_ROOT(t, o)
Definition: rb_internals.h:46
#define SENSE_MAX
Definition: rb.h:223
HIDDEN struct bu_rb_node * _rb_extreme(struct bu_rb_node *root, int order, int sense, struct bu_rb_node *empty_node)
Definition: rb_extreme.c:40
#define RB_DATA(n, o)
Definition: rb_internals.h:82
#define RB_CHILD(n, o, d)
Definition: rb_internals.h:65
void * bu_rb_neighbor(struct bu_rb_tree *tree, int order, int sense)
Definition: rb_extreme.c:124
#define UNLIKELY(expression)
Definition: common.h:282