ReactOS  0.4.13-dev-479-gec9c8fd
rbtree.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  rb_node
 
struct  rb_root
 

Macros

#define RB_RED   0
 
#define RB_BLACK   1
 
#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
 
#define rb_color(r)   ((r)->rb_parent_color & 1)
 
#define rb_is_red(r)   (!rb_color(r))
 
#define rb_is_black(r)   rb_color(r)
 
#define rb_set_red(r)   do { (r)->rb_parent_color &= ~1; } while (0)
 
#define rb_set_black(r)   do { (r)->rb_parent_color |= 1; } while (0)
 
#define RB_ROOT   (struct rb_root) { NULL, }
 
#define rb_entry(ptr, type, member)   container_of(ptr, type, member)
 
#define RB_EMPTY_ROOT(root)   ((root)->rb_node == NULL)
 
#define RB_EMPTY_NODE(node)   (rb_parent(node) != node)
 
#define RB_CLEAR_NODE(node)   (rb_set_parent(node, node))
 

Functions

struct rb_node __attribute__ ((aligned(sizeof(long))))
 
static void rb_set_parent (struct rb_node *rb, struct rb_node *p)
 
static void rb_set_color (struct rb_node *rb, ULONG_PTR color)
 
void rb_insert_color (struct rb_node *, struct rb_root *)
 
void rb_erase (struct rb_node *, struct rb_root *)
 
struct rb_noderb_next (struct rb_node *)
 
struct rb_noderb_prev (struct rb_node *)
 
struct rb_noderb_first (struct rb_root *)
 
struct rb_noderb_last (struct rb_root *)
 
void rb_replace_node (struct rb_node *victim, struct rb_node *new, struct rb_root *root)
 
static void rb_link_node (struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)
 
void rb_insert (struct rb_root *root, struct rb_node *node, int(*cmp)(struct rb_node *, struct rb_node *))
 

Variables

ULONG_PTR rb_parent_color
 
struct rb_noderb_right
 
struct rb_noderb_left
 
struct rb_root __attribute__
 

Macro Definition Documentation

◆ RB_BLACK

#define RB_BLACK   1

Definition at line 1137 of file rbtree.h.

◆ RB_CLEAR_NODE

#define RB_CLEAR_NODE (   node)    (rb_set_parent(node, node))

Definition at line 134 of file rbtree.h.

◆ rb_color

#define rb_color (   r)    ((r)->rb_parent_color & 1)

Definition at line 114 of file rbtree.h.

◆ RB_EMPTY_NODE

#define RB_EMPTY_NODE (   node)    (rb_parent(node) != node)

Definition at line 133 of file rbtree.h.

◆ RB_EMPTY_ROOT

#define RB_EMPTY_ROOT (   root)    ((root)->rb_node == NULL)

Definition at line 132 of file rbtree.h.

◆ rb_entry

#define rb_entry (   ptr,
  type,
  member 
)    container_of(ptr, type, member)

Definition at line 130 of file rbtree.h.

◆ rb_is_black

#define rb_is_black (   r)    rb_color(r)

Definition at line 116 of file rbtree.h.

◆ rb_is_red

#define rb_is_red (   r)    (!rb_color(r))

Definition at line 115 of file rbtree.h.

◆ rb_parent

#define rb_parent (   r)    ((struct rb_node *)((r)->rb_parent_color & ~3))

Definition at line 113 of file rbtree.h.

◆ RB_RED

#define RB_RED   0

Definition at line 1136 of file rbtree.h.

◆ RB_ROOT

#define RB_ROOT   (struct rb_root) { NULL, }

Definition at line 129 of file rbtree.h.

◆ rb_set_black

#define rb_set_black (   r)    do { (r)->rb_parent_color |= 1; } while (0)

Definition at line 118 of file rbtree.h.

◆ rb_set_red

#define rb_set_red (   r)    do { (r)->rb_parent_color &= ~1; } while (0)

Definition at line 117 of file rbtree.h.

Function Documentation

◆ __attribute__()

◆ rb_erase()

void rb_erase ( struct rb_node ,
struct rb_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:63
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:2708
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 )

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:2708
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 ,
struct rb_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:2708
#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 )

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_link_node()

static void rb_link_node ( struct rb_node node,
struct rb_node parent,
struct rb_node **  rb_link 
)
inlinestatic

Definition at line 149 of file rbtree.h.

151 {
152  node->rb_parent_color = (ULONG_PTR )parent;
153  node->rb_left = node->rb_right = NULL;
154 
155  *rb_link = node;
156 }
struct node node
smooth NULL
Definition: ftsmooth.c:416
r parent
Definition: btrfs.c:2708
#define ULONG_PTR
Definition: config.h:101
Definition: dlist.c:348

Referenced by rb_insert().

◆ rb_next()

struct rb_node* rb_next ( struct rb_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:2708
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 )

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:2708
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:2708
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

◆ rb_set_color()

static void rb_set_color ( struct rb_node rb,
ULONG_PTR  color 
)
inlinestatic

Definition at line 124 of file rbtree.h.

125 {
126  rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
127 }
GLuint color
Definition: glext.h:6243
ULONG_PTR rb_parent_color
Definition: rbtree.h:99

Referenced by __rb_erase_color().

◆ rb_set_parent()

static void rb_set_parent ( struct rb_node rb,
struct rb_node p 
)
inlinestatic

Definition at line 120 of file rbtree.h.

121 {
122  rb->rb_parent_color = (rb->rb_parent_color & 3) | (ULONG_PTR)p;
123 }
uint32_t ULONG_PTR
Definition: typedefs.h:63
ULONG_PTR rb_parent_color
Definition: rbtree.h:99
GLfloat GLfloat p
Definition: glext.h:8902

Referenced by __rb_rotate_left(), __rb_rotate_right(), rb_erase(), and rb_replace_node().

Variable Documentation

◆ __attribute__

◆ rb_left

struct rb_node* rb_left

Definition at line 1139 of file rbtree.h.

Referenced by rb_erase().

◆ rb_parent_color

ULONG_PTR rb_parent_color

Definition at line 1135 of file rbtree.h.

◆ rb_right

struct rb_node* rb_right

Definition at line 1138 of file rbtree.h.