ReactOS  0.4.15-dev-309-g7c8d563
rbtree.c File Reference
#include <linux/module.h>
Include dependency graph for rbtree.c:

Go to the source code of this file.

Functions

static void __rb_rotate_left (struct rb_node *node, struct rb_root *root)
 
static void __rb_rotate_right (struct rb_node *node, struct rb_root *root)
 
void rb_insert_color (struct rb_node *node, struct rb_root *root)
 
 EXPORT_SYMBOL (rb_insert_color)
 
static void __rb_erase_color (struct rb_node *node, struct rb_node *parent, struct rb_root *root)
 
void rb_erase (struct rb_node *node, struct rb_root *root)
 
 EXPORT_SYMBOL (rb_erase)
 
struct rb_noderb_first (struct rb_root *root)
 
 EXPORT_SYMBOL (rb_first)
 
struct rb_noderb_last (struct rb_root *root)
 
 EXPORT_SYMBOL (rb_last)
 
struct rb_noderb_next (struct rb_node *node)
 
 EXPORT_SYMBOL (rb_next)
 
struct rb_noderb_prev (struct rb_node *node)
 
 EXPORT_SYMBOL (rb_prev)
 
void rb_replace_node (struct rb_node *victim, struct rb_node *new, struct rb_root *root)
 
 EXPORT_SYMBOL (rb_replace_node)
 
void rb_insert (struct rb_root *root, struct rb_node *node, int(*cmp)(struct rb_node *, struct rb_node *))
 
 EXPORT_SYMBOL (rb_insert)
 

Function Documentation

◆ __rb_erase_color()

static void __rb_erase_color ( struct rb_node node,
struct rb_node parent,
struct rb_root root 
)
static

Definition at line 137 of file rbtree.c.

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 }
#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
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
Definition: rbtree.c:48
int other
Definition: msacm.c:1376
#define rb_set_black(r)
Definition: rbtree.h:118
#define rb_color(r)
Definition: rbtree.h:114
#define rb_is_red(r)
Definition: rbtree.h:115
r parent
Definition: btrfs.c:2944
#define rb_is_black(r)
Definition: rbtree.h:116
#define rb_set_red(r)
Definition: rbtree.h:117
Definition: rbtree.h:97
Definition: dlist.c:348

Referenced by rb_erase().

◆ __rb_rotate_left()

static void __rb_rotate_left ( struct rb_node node,
struct rb_root root 
)
static

Definition at line 25 of file rbtree.c.

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 }
#define rb_parent(r)
Definition: rbtree.h:113
struct node node
r parent
Definition: btrfs.c:2944
GLdouble GLdouble right
Definition: glext.h:10859
static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
Definition: rbtree.h:120
Definition: rbtree.h:97
Definition: dlist.c:348

Referenced by __rb_erase_color(), and rb_insert_color().

◆ __rb_rotate_right()

static void __rb_rotate_right ( struct rb_node node,
struct rb_root root 
)
static

Definition at line 48 of file rbtree.c.

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 }
#define rb_parent(r)
Definition: rbtree.h:113
struct node node
r parent
Definition: btrfs.c:2944
GLint left
Definition: glext.h:7726
static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
Definition: rbtree.h:120
Definition: rbtree.h:97
Definition: dlist.c:348

Referenced by __rb_erase_color(), and rb_insert_color().

◆ EXPORT_SYMBOL() [1/8]

EXPORT_SYMBOL ( rb_insert_color  )

◆ EXPORT_SYMBOL() [2/8]

EXPORT_SYMBOL ( rb_erase  )

◆ EXPORT_SYMBOL() [3/8]

EXPORT_SYMBOL ( rb_first  )

◆ EXPORT_SYMBOL() [4/8]

EXPORT_SYMBOL ( rb_last  )

◆ EXPORT_SYMBOL() [5/8]

EXPORT_SYMBOL ( rb_next  )

◆ EXPORT_SYMBOL() [6/8]

EXPORT_SYMBOL ( rb_prev  )

◆ EXPORT_SYMBOL() [7/8]

EXPORT_SYMBOL ( rb_replace_node  )

◆ EXPORT_SYMBOL() [8/8]

EXPORT_SYMBOL ( rb_insert  )

◆ rb_erase()

void rb_erase ( struct rb_node node,
struct rb_root root 
)

Definition at line 223 of file rbtree.c.

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 }
#define rb_parent(r)
Definition: rbtree.h:113
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root)
Definition: rbtree.c:137
struct rb_node * rb_left
Definition: rbtree.h:103
#define rb_color(r)
Definition: rbtree.h:114
static HWND child
Definition: cursoricon.c:298
uint32_t ULONG_PTR
Definition: typedefs.h:64
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:2944
struct rb_node * rb_left
Definition: rbtree.h:1139
#define RB_BLACK
Definition: tree.h:308
GLint left
Definition: glext.h:7726
static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
Definition: rbtree.h:120
Definition: rbtree.h:97
Definition: dlist.c:348
struct rb_node * rb_right
Definition: rbtree.h:102

Referenced by buffer_head_remove(), and ext4_xattr_item_remove().

◆ rb_first()

struct rb_node* rb_first ( struct rb_root root)

Definition at line 294 of file rbtree.c.

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 }
GLdouble n
Definition: glext.h:7729
smooth NULL
Definition: ftsmooth.c:416
Definition: rbtree.h:97

Referenced by Ext2FlushVcb(), and ext4_xattr_purge_items().

◆ rb_insert()

void rb_insert ( struct rb_root root,
struct rb_node node,
int(*)(struct rb_node *, struct rb_node *)  cmp 
)

Definition at line 392 of file rbtree.c.

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 }
void rb_insert_color(struct rb_node *node, struct rb_root *root)
Definition: rbtree.c:71
static void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)
Definition: rbtree.h:149
#define cmp(status, error)
Definition: error.c:114
smooth NULL
Definition: ftsmooth.c:416
r parent
Definition: btrfs.c:2944
Definition: rbtree.h:97
GLuint64EXT * result
Definition: glext.h:11304
Definition: dlist.c:348

Referenced by buffer_head_insert(), and ext4_xattr_item_insert().

◆ rb_insert_color()

void rb_insert_color ( struct rb_node node,
struct rb_root root 
)

Definition at line 71 of file rbtree.c.

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 }
#define rb_parent(r)
Definition: rbtree.h:113
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
Definition: rbtree.c:25
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
Definition: rbtree.c:48
struct rb_node * rb_left
Definition: rbtree.h:103
#define rb_set_black(r)
Definition: rbtree.h:118
#define rb_is_red(r)
Definition: rbtree.h:115
struct node node
r parent
Definition: btrfs.c:2944
#define rb_set_red(r)
Definition: rbtree.h:117
Definition: rbtree.h:97
Definition: dlist.c:348
struct rb_node * rb_right
Definition: rbtree.h:102

Referenced by rb_insert().

◆ rb_last()

struct rb_node* rb_last ( struct rb_root root)

Definition at line 307 of file rbtree.c.

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 }
GLdouble n
Definition: glext.h:7729
smooth NULL
Definition: ftsmooth.c:416
Definition: rbtree.h:97

◆ rb_next()

struct rb_node* rb_next ( struct rb_node node)

Definition at line 320 of file rbtree.c.

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 }
#define rb_parent(r)
Definition: rbtree.h:113
struct node node
r parent
Definition: btrfs.c:2944
Definition: rbtree.h:97
Definition: dlist.c:348

Referenced by Ext2FlushVcb(), ext4_xattr_purge_items(), and ext4_xattr_remove_item().

◆ rb_prev()

struct rb_node* rb_prev ( struct rb_node node)

Definition at line 346 of file rbtree.c.

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 }
#define rb_parent(r)
Definition: rbtree.h:113
struct node node
r parent
Definition: btrfs.c:2944
Definition: rbtree.h:97
Definition: dlist.c:348

◆ rb_replace_node()

void rb_replace_node ( struct rb_node victim,
struct rb_node new,
struct rb_root root 
)

Definition at line 368 of file rbtree.c.

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 }
#define rb_parent(r)
Definition: rbtree.h:113
struct rb_node * rb_left
Definition: rbtree.h:103
r parent
Definition: btrfs.c:2944
static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
Definition: rbtree.h:120
Definition: rbtree.h:97
struct rb_node * rb_right
Definition: rbtree.h:102