ReactOS  0.4.14-dev-315-gbb6fece
rbtree.c
Go to the documentation of this file.
1 /*
2  Red Black Trees
3  (C) 1999 Andrea Arcangeli <andrea@suse.de>
4  (C) 2002 David Woodhouse <dwmw2@infradead.org>
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation; either version 2 of the License, or
9  (at your option) any later version.
10 
11  This program is distributed in the hope that it will be useful,
12  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  GNU General Public License for more details.
15 
16  You should have received a copy of the GNU General Public License
17  along with this program; if not, write to the Free Software
18  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 
20  linux/lib/rbtree.c
21 */
22 
23 #include <linux/module.h>
24 
25 static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
26 {
27  struct rb_node *right = node->rb_right;
28  struct rb_node *parent = rb_parent(node);
29 
30  if ((node->rb_right = right->rb_left))
31  rb_set_parent(right->rb_left, node);
32  right->rb_left = node;
33 
35 
36  if (parent)
37  {
38  if (node == parent->rb_left)
39  parent->rb_left = right;
40  else
41  parent->rb_right = right;
42  }
43  else
44  root->rb_node = right;
46 }
47 
48 static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
49 {
50  struct rb_node *left = node->rb_left;
51  struct rb_node *parent = rb_parent(node);
52 
53  if ((node->rb_left = left->rb_right))
54  rb_set_parent(left->rb_right, node);
55  left->rb_right = node;
56 
58 
59  if (parent)
60  {
61  if (node == parent->rb_right)
62  parent->rb_right = left;
63  else
64  parent->rb_left = left;
65  }
66  else
67  root->rb_node = left;
69 }
70 
71 void rb_insert_color(struct rb_node *node, struct rb_root *root)
72 {
73  struct rb_node *parent, *gparent;
74 
75  while ((parent = rb_parent(node)) && rb_is_red(parent))
76  {
77  gparent = rb_parent(parent);
78 
79  if (parent == gparent->rb_left)
80  {
81  {
82  register struct rb_node *uncle = gparent->rb_right;
83  if (uncle && rb_is_red(uncle))
84  {
85  rb_set_black(uncle);
87  rb_set_red(gparent);
88  node = gparent;
89  continue;
90  }
91  }
92 
93  if (parent->rb_right == node)
94  {
95  register struct rb_node *tmp;
97  tmp = parent;
98  parent = node;
99  node = tmp;
100  }
101 
103  rb_set_red(gparent);
104  __rb_rotate_right(gparent, root);
105  } else {
106  {
107  register struct rb_node *uncle = gparent->rb_left;
108  if (uncle && rb_is_red(uncle))
109  {
110  rb_set_black(uncle);
112  rb_set_red(gparent);
113  node = gparent;
114  continue;
115  }
116  }
117 
118  if (parent->rb_left == node)
119  {
120  register struct rb_node *tmp;
122  tmp = parent;
123  parent = node;
124  node = tmp;
125  }
126 
128  rb_set_red(gparent);
129  __rb_rotate_left(gparent, root);
130  }
131  }
132 
133  rb_set_black(root->rb_node);
134 }
136 
137 static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
138  struct rb_root *root)
139 {
140  struct rb_node *other;
141 
142  while ((!node || rb_is_black(node)) && node != root->rb_node)
143  {
144  if (parent->rb_left == node)
145  {
146  other = parent->rb_right;
147  if (rb_is_red(other))
148  {
152  other = parent->rb_right;
153  }
154  if ((!other->rb_left || rb_is_black(other->rb_left)) &&
155  (!other->rb_right || rb_is_black(other->rb_right)))
156  {
157  rb_set_red(other);
158  node = parent;
159  parent = rb_parent(node);
160  }
161  else
162  {
163  if (!other->rb_right || rb_is_black(other->rb_right))
164  {
165  struct rb_node *o_left;
166  if ((o_left = other->rb_left))
167  rb_set_black(o_left);
168  rb_set_red(other);
170  other = parent->rb_right;
171  }
174  if (other->rb_right)
175  rb_set_black(other->rb_right);
177  node = root->rb_node;
178  break;
179  }
180  }
181  else
182  {
183  other = parent->rb_left;
184  if (rb_is_red(other))
185  {
189  other = parent->rb_left;
190  }
191  if ((!other->rb_left || rb_is_black(other->rb_left)) &&
192  (!other->rb_right || rb_is_black(other->rb_right)))
193  {
194  rb_set_red(other);
195  node = parent;
196  parent = rb_parent(node);
197  }
198  else
199  {
200  if (!other->rb_left || rb_is_black(other->rb_left))
201  {
202  register struct rb_node *o_right;
203  if ((o_right = other->rb_right))
204  rb_set_black(o_right);
205  rb_set_red(other);
207  other = parent->rb_left;
208  }
211  if (other->rb_left)
212  rb_set_black(other->rb_left);
214  node = root->rb_node;
215  break;
216  }
217  }
218  }
219  if (node)
221 }
222 
223 void rb_erase(struct rb_node *node, struct rb_root *root)
224 {
225  struct rb_node *child, *parent;
227 
228  if (!node->rb_left)
229  child = node->rb_right;
230  else if (!node->rb_right)
231  child = node->rb_left;
232  else
233  {
234  struct rb_node *old = node, *left;
235 
236  node = node->rb_right;
237  while ((left = node->rb_left) != NULL)
238  node = left;
239  child = node->rb_right;
240  parent = rb_parent(node);
241  color = rb_color(node);
242 
243  if (child)
245  if (parent == old) {
246  parent->rb_right = child;
247  parent = node;
248  } else
249  parent->rb_left = child;
250 
251  node->rb_parent_color = old->rb_parent_color;
252  node->rb_right = old->rb_right;
253  node->rb_left = old->rb_left;
254 
255  if (rb_parent(old))
256  {
257  if (rb_parent(old)->rb_left == old)
258  rb_parent(old)->rb_left = node;
259  else
260  rb_parent(old)->rb_right = node;
261  } else
262  root->rb_node = node;
263 
264  rb_set_parent(old->rb_left, node);
265  if (old->rb_right)
266  rb_set_parent(old->rb_right, node);
267  goto color;
268  }
269 
270  parent = rb_parent(node);
271  color = rb_color(node);
272 
273  if (child)
275  if (parent)
276  {
277  if (parent->rb_left == node)
278  parent->rb_left = child;
279  else
280  parent->rb_right = child;
281  }
282  else
283  root->rb_node = child;
284 
285 color:
286  if (color == RB_BLACK)
288 }
290 
291 /*
292  * This function returns the first node (in sort order) of the tree.
293  */
294 struct rb_node *rb_first(struct rb_root *root)
295 {
296  struct rb_node *n;
297 
298  n = root->rb_node;
299  if (!n)
300  return NULL;
301  while (n->rb_left)
302  n = n->rb_left;
303  return n;
304 }
306 
307 struct rb_node *rb_last(struct rb_root *root)
308 {
309  struct rb_node *n;
310 
311  n = root->rb_node;
312  if (!n)
313  return NULL;
314  while (n->rb_right)
315  n = n->rb_right;
316  return n;
317 }
319 
320 struct rb_node *rb_next(struct rb_node *node)
321 {
322  struct rb_node *parent;
323 
324  /* If we have a right-hand child, go down and then left as far
325  as we can. */
326  if (node->rb_right) {
327  node = node->rb_right;
328  while (node->rb_left)
329  node=node->rb_left;
330  return node;
331  }
332 
333  /* No right-hand children. Everything down and left is
334  smaller than us, so any 'next' node must be in the general
335  direction of our parent. Go up the tree; any time the
336  ancestor is a right-hand child of its parent, keep going
337  up. First time it's a left-hand child of its parent, said
338  parent is our 'next' node. */
339  while ((parent = rb_parent(node)) && node == parent->rb_right)
340  node = parent;
341 
342  return parent;
343 }
345 
346 struct rb_node *rb_prev(struct rb_node *node)
347 {
348  struct rb_node *parent;
349 
350  /* If we have a left-hand child, go down and then right as far
351  as we can. */
352  if (node->rb_left) {
353  node = node->rb_left;
354  while (node->rb_right)
355  node=node->rb_right;
356  return node;
357  }
358 
359  /* No left-hand children. Go up till we find an ancestor which
360  is a right-hand child of its parent */
361  while ((parent = rb_parent(node)) && node == parent->rb_left)
362  node = parent;
363 
364  return parent;
365 }
367 
368 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
369  struct rb_root *root)
370 {
371  struct rb_node *parent = rb_parent(victim);
372 
373  /* Set the surrounding nodes to point to the replacement */
374  if (parent) {
375  if (victim == parent->rb_left)
376  parent->rb_left = new;
377  else
378  parent->rb_right = new;
379  } else {
380  root->rb_node = new;
381  }
382  if (victim->rb_left)
383  rb_set_parent(victim->rb_left, new);
384  if (victim->rb_right)
385  rb_set_parent(victim->rb_right, new);
386 
387  /* Copy the pointers/colour from the victim to the replacement */
388  *new = *victim;
389 }
391 
392 void rb_insert(struct rb_root *root, struct rb_node *node,
393  int (*cmp)(struct rb_node *, struct rb_node *))
394 {
395  struct rb_node **new = &(root->rb_node), *parent = NULL;
396 
397  /* Figure out where to put new node */
398  while (*new) {
399  int result = cmp(node, *new);
400 
401  parent = *new;
402  if (result < 0)
403  new = &((*new)->rb_left);
404  else if (result > 0)
405  new = &((*new)->rb_right);
406  else
407  return;
408 
409  }
410 
411  /* Add new node and rebalance tree. */
412  rb_link_node(node, parent, new);
414 }
#define rb_parent(r)
Definition: rbtree.h:113
static void rb_set_color(struct rb_node *rb, ULONG_PTR color)
Definition: rbtree.h:124
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
Definition: rbtree.c:25
EXPORT_SYMBOL(rb_insert_color)
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root)
Definition: rbtree.c:137
void rb_insert(struct rb_root *root, struct rb_node *node, int(*cmp)(struct rb_node *, struct rb_node *))
Definition: rbtree.c:392
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
Definition: rbtree.c:48
void rb_insert_color(struct rb_node *node, struct rb_root *root)
Definition: rbtree.c:71
void rb_erase(struct rb_node *node, struct rb_root *root)
Definition: rbtree.c:223
static void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)
Definition: rbtree.h:149
struct rb_node * rb_left
Definition: rbtree.h:103
int other
Definition: msacm.c:1376
#define rb_set_black(r)
Definition: rbtree.h:118
GLdouble n
Definition: glext.h:7729
struct rb_node * rb_last(struct rb_root *root)
Definition: rbtree.c:307
#define rb_color(r)
Definition: rbtree.h:114
#define cmp(status, error)
Definition: error.c:114
#define rb_is_red(r)
Definition: rbtree.h:115
static HWND child
Definition: cursoricon.c:298
uint32_t ULONG_PTR
Definition: typedefs.h:63
struct rb_node * rb_first(struct rb_root *root)
Definition: rbtree.c:294
struct node node
GLuint color
Definition: glext.h:6243
smooth NULL
Definition: ftsmooth.c:416
ULONG_PTR rb_parent_color
Definition: rbtree.h:99
r parent
Definition: btrfs.c:2869
struct rb_node * rb_left
Definition: rbtree.h:1139
#define RB_BLACK
Definition: tree.h:308
GLint left
Definition: glext.h:7726
struct rb_node * rb_prev(struct rb_node *node)
Definition: rbtree.c:346
GLdouble GLdouble right
Definition: glext.h:10859
struct rb_node * rb_next(struct rb_node *node)
Definition: rbtree.c:320
void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root)
Definition: rbtree.c:368
static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
Definition: rbtree.h:120
#define rb_is_black(r)
Definition: rbtree.h:116
#define rb_set_red(r)
Definition: rbtree.h:117
Definition: rbtree.h:97
GLuint64EXT * result
Definition: glext.h:11304
Definition: dlist.c:348
struct rb_node * rb_right
Definition: rbtree.h:102