ReactOS 0.4.15-dev-7842-g558ab78
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 2 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 1 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 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;
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
265 if (old->rb_right)
267 goto color;
268 }
269
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
285color:
286 if (color == RB_BLACK)
288}
#define RB_BLACK
Definition: tree.h:306
#define NULL
Definition: types.h:112
r parent
Definition: btrfs.c:3010
#define rb_color(r)
Definition: rbtree.h:114
static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
Definition: rbtree.h:120
struct rb_node * rb_left
Definition: rbtree.h:4
#define rb_parent(r)
Definition: rbtree.h:113
GLuint color
Definition: glext.h:6243
GLint left
Definition: glext.h:7726
static HWND child
Definition: cursoricon.c:298
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root)
Definition: rbtree.c:137
Definition: rbtree.h:98
struct rb_node * rb_left
Definition: rbtree.h:103
ULONG_PTR rb_parent_color
Definition: rbtree.h:99
struct rb_node * rb_right
Definition: rbtree.h:102
uint32_t ULONG_PTR
Definition: typedefs.h:65
Definition: dlist.c:348

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

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

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_is_red(r)
Definition: rbtree.h:115
#define rb_set_red(r)
Definition: rbtree.h:117
#define rb_set_black(r)
Definition: rbtree.h:118
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

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}

◆ 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}
#define ULONG_PTR
Definition: config.h:101

Referenced by rb_insert().

◆ 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}

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}

◆ 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}

◆ 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}

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}
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 4 of file rbtree.h.

Referenced by rb_erase().

◆ rb_parent_color

ULONG_PTR rb_parent_color

Definition at line 0 of file rbtree.h.

◆ rb_right

struct rb_node* rb_right

Definition at line 3 of file rbtree.h.