Lines Matching refs:rbe
55 rb_e2n(const struct rb_type *t, struct rb_entry *rbe) in rb_e2n() argument
57 unsigned long addr = (unsigned long)rbe; in rb_e2n()
70 rbe_set(struct rb_entry *rbe, struct rb_entry *parent) in rbe_set() argument
72 RBE_PARENT(rbe) = parent; in rbe_set()
73 RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL; in rbe_set()
74 RBE_COLOR(rbe) = RB_RED; in rbe_set()
85 rbe_augment(const struct rb_type *t, struct rb_entry *rbe) in rbe_augment() argument
87 (*t->t_augment)(rb_e2n(t, rbe)); in rbe_augment()
91 rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe) in rbe_if_augment() argument
94 rbe_augment(t, rbe); in rbe_if_augment()
99 struct rb_entry *rbe) in rbe_rotate_left() argument
104 tmp = RBE_RIGHT(rbe); in rbe_rotate_left()
105 RBE_RIGHT(rbe) = RBE_LEFT(tmp); in rbe_rotate_left()
106 if (RBE_RIGHT(rbe) != NULL) in rbe_rotate_left()
107 RBE_PARENT(RBE_LEFT(tmp)) = rbe; in rbe_rotate_left()
109 parent = RBE_PARENT(rbe); in rbe_rotate_left()
112 if (rbe == RBE_LEFT(parent)) in rbe_rotate_left()
119 RBE_LEFT(tmp) = rbe; in rbe_rotate_left()
120 RBE_PARENT(rbe) = tmp; in rbe_rotate_left()
123 rbe_augment(t, rbe); in rbe_rotate_left()
133 struct rb_entry *rbe) in rbe_rotate_right() argument
138 tmp = RBE_LEFT(rbe); in rbe_rotate_right()
139 RBE_LEFT(rbe) = RBE_RIGHT(tmp); in rbe_rotate_right()
140 if (RBE_LEFT(rbe) != NULL) in rbe_rotate_right()
141 RBE_PARENT(RBE_RIGHT(tmp)) = rbe; in rbe_rotate_right()
143 parent = RBE_PARENT(rbe); in rbe_rotate_right()
146 if (rbe == RBE_LEFT(parent)) in rbe_rotate_right()
153 RBE_RIGHT(tmp) = rbe; in rbe_rotate_right()
154 RBE_PARENT(rbe) = tmp; in rbe_rotate_right()
157 rbe_augment(t, rbe); in rbe_rotate_right()
167 struct rb_entry *rbe) in rbe_insert_color() argument
171 while ((parent = RBE_PARENT(rbe)) != NULL && in rbe_insert_color()
180 rbe = gparent; in rbe_insert_color()
184 if (RBE_RIGHT(parent) == rbe) { in rbe_insert_color()
187 parent = rbe; in rbe_insert_color()
188 rbe = tmp; in rbe_insert_color()
198 rbe = gparent; in rbe_insert_color()
202 if (RBE_LEFT(parent) == rbe) { in rbe_insert_color()
205 parent = rbe; in rbe_insert_color()
206 rbe = tmp; in rbe_insert_color()
219 struct rb_entry *parent, struct rb_entry *rbe) in rbe_remove_color() argument
223 while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) && in rbe_remove_color()
224 rbe != RBH_ROOT(rbt)) { in rbe_remove_color()
225 if (RBE_LEFT(parent) == rbe) { in rbe_remove_color()
237 rbe = parent; in rbe_remove_color()
238 parent = RBE_PARENT(rbe); in rbe_remove_color()
259 rbe = RBH_ROOT(rbt); in rbe_remove_color()
275 rbe = parent; in rbe_remove_color()
276 parent = RBE_PARENT(rbe); in rbe_remove_color()
297 rbe = RBH_ROOT(rbt); in rbe_remove_color()
303 if (rbe != NULL) in rbe_remove_color()
304 RBE_COLOR(rbe) = RB_BLACK; in rbe_remove_color()
308 rbe_remove(const struct rb_type *t, struct rb_tree *rbt, struct rb_entry *rbe) in rbe_remove() argument
310 struct rb_entry *child, *parent, *old = rbe; in rbe_remove()
313 if (RBE_LEFT(rbe) == NULL) in rbe_remove()
314 child = RBE_RIGHT(rbe); in rbe_remove()
315 else if (RBE_RIGHT(rbe) == NULL) in rbe_remove()
316 child = RBE_LEFT(rbe); in rbe_remove()
320 rbe = RBE_RIGHT(rbe); in rbe_remove()
321 while ((tmp = RBE_LEFT(rbe)) != NULL) in rbe_remove()
322 rbe = tmp; in rbe_remove()
324 child = RBE_RIGHT(rbe); in rbe_remove()
325 parent = RBE_PARENT(rbe); in rbe_remove()
326 color = RBE_COLOR(rbe); in rbe_remove()
330 if (RBE_LEFT(parent) == rbe) in rbe_remove()
338 if (RBE_PARENT(rbe) == old) in rbe_remove()
339 parent = rbe; in rbe_remove()
340 *rbe = *old; in rbe_remove()
345 RBE_LEFT(tmp) = rbe; in rbe_remove()
347 RBE_RIGHT(tmp) = rbe; in rbe_remove()
351 RBH_ROOT(rbt) = rbe; in rbe_remove()
353 RBE_PARENT(RBE_LEFT(old)) = rbe; in rbe_remove()
355 RBE_PARENT(RBE_RIGHT(old)) = rbe; in rbe_remove()
368 parent = RBE_PARENT(rbe); in rbe_remove()
369 color = RBE_COLOR(rbe); in rbe_remove()
374 if (RBE_LEFT(parent) == rbe) in rbe_remove()
392 struct rb_entry *rbe = rb_n2e(t, elm); in _rb_remove() local
395 old = rbe_remove(t, rbt, rbe); in _rb_remove()
403 struct rb_entry *rbe = rb_n2e(t, elm); in _rb_insert() local
423 rbe_set(rbe, parent); in _rb_insert()
427 RBE_LEFT(parent) = rbe; in _rb_insert()
429 RBE_RIGHT(parent) = rbe; in _rb_insert()
433 RBH_ROOT(rbt) = rbe; in _rb_insert()
435 rbe_insert_color(t, rbt, rbe); in _rb_insert()
489 struct rb_entry *rbe = rb_n2e(t, elm); in _rb_next() local
491 if (RBE_RIGHT(rbe) != NULL) { in _rb_next()
492 rbe = RBE_RIGHT(rbe); in _rb_next()
493 while (RBE_LEFT(rbe) != NULL) in _rb_next()
494 rbe = RBE_LEFT(rbe); in _rb_next()
496 if (RBE_PARENT(rbe) && in _rb_next()
497 (rbe == RBE_LEFT(RBE_PARENT(rbe)))) in _rb_next()
498 rbe = RBE_PARENT(rbe); in _rb_next()
500 while (RBE_PARENT(rbe) && in _rb_next()
501 (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) in _rb_next()
502 rbe = RBE_PARENT(rbe); in _rb_next()
503 rbe = RBE_PARENT(rbe); in _rb_next()
507 return (rbe == NULL ? NULL : rb_e2n(t, rbe)); in _rb_next()
513 struct rb_entry *rbe = rb_n2e(t, elm); in _rb_prev() local
515 if (RBE_LEFT(rbe)) { in _rb_prev()
516 rbe = RBE_LEFT(rbe); in _rb_prev()
517 while (RBE_RIGHT(rbe)) in _rb_prev()
518 rbe = RBE_RIGHT(rbe); in _rb_prev()
520 if (RBE_PARENT(rbe) && in _rb_prev()
521 (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) in _rb_prev()
522 rbe = RBE_PARENT(rbe); in _rb_prev()
524 while (RBE_PARENT(rbe) && in _rb_prev()
525 (rbe == RBE_LEFT(RBE_PARENT(rbe)))) in _rb_prev()
526 rbe = RBE_PARENT(rbe); in _rb_prev()
527 rbe = RBE_PARENT(rbe); in _rb_prev()
531 return (rbe == NULL ? NULL : rb_e2n(t, rbe)); in _rb_prev()
537 struct rb_entry *rbe = RBH_ROOT(rbt); in _rb_root() local
539 return (rbe == NULL ? rbe : rb_e2n(t, rbe)); in _rb_root()
545 struct rb_entry *rbe = RBH_ROOT(rbt); in _rb_min() local
548 while (rbe != NULL) { in _rb_min()
549 parent = rbe; in _rb_min()
550 rbe = RBE_LEFT(rbe); in _rb_min()
559 struct rb_entry *rbe = RBH_ROOT(rbt); in _rb_max() local
562 while (rbe != NULL) { in _rb_max()
563 parent = rbe; in _rb_max()
564 rbe = RBE_RIGHT(rbe); in _rb_max()
573 struct rb_entry *rbe = rb_n2e(t, node); in _rb_left() local
574 rbe = RBE_LEFT(rbe); in _rb_left()
575 return (rbe == NULL ? NULL : rb_e2n(t, rbe)); in _rb_left()
581 struct rb_entry *rbe = rb_n2e(t, node); in _rb_right() local
582 rbe = RBE_RIGHT(rbe); in _rb_right()
583 return (rbe == NULL ? NULL : rb_e2n(t, rbe)); in _rb_right()
589 struct rb_entry *rbe = rb_n2e(t, node); in _rb_parent() local
590 rbe = RBE_PARENT(rbe); in _rb_parent()
591 return (rbe == NULL ? NULL : rb_e2n(t, rbe)); in _rb_parent()
597 struct rb_entry *rbe = rb_n2e(t, node); in _rb_set_left() local
600 RBE_LEFT(rbe) = rbl; in _rb_set_left()
606 struct rb_entry *rbe = rb_n2e(t, node); in _rb_set_right() local
609 RBE_RIGHT(rbe) = rbr; in _rb_set_right()
615 struct rb_entry *rbe = rb_n2e(t, node); in _rb_set_parent() local
618 RBE_PARENT(rbe) = rbp; in _rb_set_parent()
624 struct rb_entry *rbe = rb_n2e(t, node); in _rb_poison() local
626 RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) = in _rb_poison()
633 struct rb_entry *rbe = rb_n2e(t, node); in _rb_check() local
635 return ((unsigned long)RBE_PARENT(rbe) == poison && in _rb_check()
636 (unsigned long)RBE_LEFT(rbe) == poison && in _rb_check()
637 (unsigned long)RBE_RIGHT(rbe) == poison); in _rb_check()