Lines Matching refs:link_ops
20 use crate::link_ops::{self, DefaultLinkOps};
42 pub unsafe trait RBTreeOps: link_ops::LinkOps {
193 ptr: <Self as link_ops::LinkOps>::LinkPtr, in set_parent_color()
194 parent: Option<<Self as link_ops::LinkOps>::LinkPtr>, in set_parent_color()
207 unsafe impl link_ops::LinkOps for LinkOps {
362 unsafe fn is_left_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr, parent: T::LinkPtr) -> bool { in is_left_child()
363 link_ops.left(parent) == Some(ptr) in is_left_child()
367 unsafe fn first_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> T::LinkPtr { in first_child()
369 while let Some(y) = link_ops.left(x) { in first_child()
376 unsafe fn last_child<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> T::LinkPtr { in last_child()
378 while let Some(y) = link_ops.right(x) { in last_child()
385 unsafe fn next<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> Option<T::LinkPtr> { in next()
386 if let Some(right) = link_ops.right(ptr) { in next()
387 Some(first_child(link_ops, right)) in next()
391 if let Some(parent) = link_ops.parent(x) { in next()
392 if is_left_child(link_ops, x, parent) { in next()
405 unsafe fn prev<T: RBTreeOps>(link_ops: &T, ptr: T::LinkPtr) -> Option<T::LinkPtr> { in prev()
406 if let Some(left) = link_ops.left(ptr) { in prev()
407 Some(last_child(link_ops, left)) in prev()
411 if let Some(parent) = link_ops.parent(x) { in prev()
412 if !is_left_child(link_ops, x, parent) { in prev()
426 link_ops: &mut T, in replace_with()
431 if let Some(parent) = link_ops.parent(ptr) { in replace_with()
432 if is_left_child(link_ops, ptr, parent) { in replace_with()
433 link_ops.set_left(parent, Some(new)); in replace_with()
435 link_ops.set_right(parent, Some(new)); in replace_with()
440 if let Some(left) = link_ops.left(ptr) { in replace_with()
441 link_ops.set_parent(left, Some(new)); in replace_with()
443 if let Some(right) = link_ops.right(ptr) { in replace_with()
444 link_ops.set_parent(right, Some(new)); in replace_with()
446 link_ops.set_left(new, link_ops.left(ptr)); in replace_with()
447 link_ops.set_right(new, link_ops.right(ptr)); in replace_with()
448 link_ops.set_parent(new, link_ops.parent(ptr)); in replace_with()
449 link_ops.set_color(new, link_ops.color(ptr)); in replace_with()
450 link_ops.release_link(ptr); in replace_with()
455 link_ops: &mut T, in insert_left()
460 link_ops.set_parent(new, Some(ptr)); in insert_left()
461 link_ops.set_color(new, Color::Red); in insert_left()
462 link_ops.set_left(new, None); in insert_left()
463 link_ops.set_right(new, None); in insert_left()
464 link_ops.set_left(ptr, Some(new)); in insert_left()
465 post_insert(link_ops, new, root); in insert_left()
470 link_ops: &mut T, in insert_right()
475 link_ops.set_parent(new, Some(ptr)); in insert_right()
476 link_ops.set_color(new, Color::Red); in insert_right()
477 link_ops.set_left(new, None); in insert_right()
478 link_ops.set_right(new, None); in insert_right()
479 link_ops.set_right(ptr, Some(new)); in insert_right()
480 post_insert(link_ops, new, root); in insert_right()
484 link_ops: &mut T, in rotate_left()
488 let y = link_ops.right(ptr).unwrap_unchecked(); in rotate_left()
489 link_ops.set_right(ptr, link_ops.left(y)); in rotate_left()
490 if let Some(right) = link_ops.right(ptr) { in rotate_left()
491 link_ops.set_parent(right, Some(ptr)); in rotate_left()
493 link_ops.set_parent(y, link_ops.parent(ptr)); in rotate_left()
494 if let Some(parent) = link_ops.parent(ptr) { in rotate_left()
495 if is_left_child(link_ops, ptr, parent) { in rotate_left()
496 link_ops.set_left(parent, Some(y)); in rotate_left()
498 link_ops.set_right(parent, Some(y)); in rotate_left()
503 link_ops.set_left(y, Some(ptr)); in rotate_left()
504 link_ops.set_parent(ptr, Some(y)); in rotate_left()
508 link_ops: &mut T, in rotate_right()
512 let y = link_ops.left(ptr).unwrap_unchecked(); in rotate_right()
513 link_ops.set_left(ptr, link_ops.right(y)); in rotate_right()
514 if let Some(left) = link_ops.left(ptr) { in rotate_right()
515 link_ops.set_parent(left, Some(ptr)); in rotate_right()
517 link_ops.set_parent(y, link_ops.parent(ptr)); in rotate_right()
518 if let Some(parent) = link_ops.parent(ptr) { in rotate_right()
519 if is_left_child(link_ops, ptr, parent) { in rotate_right()
520 link_ops.set_left(parent, Some(y)); in rotate_right()
522 link_ops.set_right(parent, Some(y)); in rotate_right()
527 link_ops.set_right(y, Some(ptr)); in rotate_right()
528 link_ops.set_parent(ptr, Some(y)); in rotate_right()
533 link_ops: &mut T, in post_insert()
538 while let Some(parent) = link_ops.parent(x) { in post_insert()
539 if link_ops.color(parent) != Color::Red { in post_insert()
543 let grandparent = link_ops.parent(parent).unwrap_unchecked(); in post_insert()
545 if is_left_child(link_ops, parent, grandparent) { in post_insert()
546 let y = link_ops.right(grandparent); in post_insert()
548 if link_ops.color(y) == Color::Red { in post_insert()
550 link_ops.set_color(x, Color::Black); in post_insert()
553 if link_ops.parent(x).is_none() { in post_insert()
554 link_ops.set_color(x, Color::Black); in post_insert()
556 link_ops.set_color(x, Color::Red); in post_insert()
558 link_ops.set_color(y, Color::Black); in post_insert()
562 if !is_left_child(link_ops, x, parent) { in post_insert()
564 rotate_left(link_ops, x, root); in post_insert()
566 x = link_ops.parent(x).unwrap_unchecked(); in post_insert()
567 link_ops.set_color(x, Color::Black); in post_insert()
568 x = link_ops.parent(x).unwrap_unchecked(); in post_insert()
569 link_ops.set_color(x, Color::Red); in post_insert()
570 rotate_right(link_ops, x, root); in post_insert()
573 let y = link_ops.left(grandparent); in post_insert()
575 if link_ops.color(y) == Color::Red { in post_insert()
577 link_ops.set_color(x, Color::Black); in post_insert()
579 if link_ops.parent(x).is_none() { in post_insert()
580 link_ops.set_color(x, Color::Black); in post_insert()
582 link_ops.set_color(x, Color::Red); in post_insert()
584 link_ops.set_color(y, Color::Black); in post_insert()
588 if is_left_child(link_ops, x, parent) { in post_insert()
590 rotate_right(link_ops, x, root); in post_insert()
592 x = link_ops.parent(x).unwrap_unchecked(); in post_insert()
593 link_ops.set_color(x, Color::Black); in post_insert()
594 x = link_ops.parent(x).unwrap_unchecked(); in post_insert()
595 link_ops.set_color(x, Color::Red); in post_insert()
596 rotate_left(link_ops, x, root); in post_insert()
603 unsafe fn remove<T: RBTreeOps>(link_ops: &mut T, ptr: T::LinkPtr, root: &mut Option<T::LinkPtr>) { in remove()
604 let y = if link_ops.left(ptr).is_none() || link_ops.right(ptr).is_none() { in remove()
607 next(link_ops, ptr).unwrap_unchecked() in remove()
609 let x = if link_ops.left(y).is_some() { in remove()
610 link_ops.left(y) in remove()
612 link_ops.right(y) in remove()
616 link_ops.set_parent(x, link_ops.parent(y)); in remove()
618 if let Some(y_parent) = link_ops.parent(y) { in remove()
619 if is_left_child(link_ops, y, y_parent) { in remove()
620 link_ops.set_left(y_parent, x); in remove()
621 w = link_ops.right(y_parent); in remove()
623 link_ops.set_right(y_parent, x); in remove()
624 w = link_ops.left(y_parent); in remove()
629 let removed_black = link_ops.color(y) == Color::Black; in remove()
631 if let Some(parent) = link_ops.parent(ptr) { in remove()
632 link_ops.set_parent(y, Some(parent)); in remove()
633 if is_left_child(link_ops, ptr, parent) { in remove()
634 link_ops.set_left(parent, Some(y)); in remove()
636 link_ops.set_right(parent, Some(y)); in remove()
639 link_ops.set_parent(y, None); in remove()
642 link_ops.set_left(y, link_ops.left(ptr)); in remove()
643 link_ops.set_parent(link_ops.left(y).unwrap_unchecked(), Some(y)); in remove()
644 link_ops.set_right(y, link_ops.right(ptr)); in remove()
645 if let Some(y_right) = link_ops.right(y) { in remove()
646 link_ops.set_parent(y_right, Some(y)); in remove()
648 link_ops.set_color(y, link_ops.color(ptr)); in remove()
652 link_ops.set_color(x, Color::Black); in remove()
656 let mut w_parent = link_ops.parent(w).unwrap_unchecked(); in remove()
657 if !is_left_child(link_ops, w, w_parent) { in remove()
658 if link_ops.color(w) == Color::Red { in remove()
659 link_ops.set_color(w, Color::Black); in remove()
660 link_ops.set_color(w_parent, Color::Red); in remove()
661 rotate_left(link_ops, w_parent, root); in remove()
662 w = link_ops in remove()
663 .right(link_ops.left(w).unwrap_unchecked()) in remove()
665 w_parent = link_ops.parent(w).unwrap_unchecked(); in remove()
668 let left_color = link_ops.left(w).map(|x| link_ops.color(x)); in remove()
669 let right_color = link_ops.right(w).map(|x| link_ops.color(x)); in remove()
671 link_ops.set_color(w, Color::Red); in remove()
672 if link_ops.parent(w_parent).is_none() in remove()
673 || link_ops.color(w_parent) == Color::Red in remove()
675 link_ops.set_color(w_parent, Color::Black); in remove()
678 let w_grandparent = link_ops.parent(w_parent).unwrap_unchecked(); in remove()
679 w = if is_left_child(link_ops, w_parent, w_grandparent) { in remove()
680 link_ops.right(w_grandparent).unwrap_unchecked() in remove()
682 link_ops.left(w_grandparent).unwrap_unchecked() in remove()
685 if link_ops.right(w).map(|x| link_ops.color(x)) != Some(Color::Red) { in remove()
686 link_ops.set_color(link_ops.left(w).unwrap_unchecked(), Color::Black); in remove()
687 link_ops.set_color(w, Color::Red); in remove()
688 rotate_right(link_ops, w, root); in remove()
689 w = link_ops.parent(w).unwrap_unchecked(); in remove()
690 w_parent = link_ops.parent(w).unwrap_unchecked(); in remove()
692 link_ops.set_color(w, link_ops.color(w_parent)); in remove()
693 link_ops.set_color(w_parent, Color::Black); in remove()
694 link_ops.set_color(link_ops.right(w).unwrap_unchecked(), Color::Black); in remove()
695 rotate_left(link_ops, w_parent, root); in remove()
699 if link_ops.color(w) == Color::Red { in remove()
700 link_ops.set_color(w, Color::Black); in remove()
701 link_ops.set_color(w_parent, Color::Red); in remove()
702 rotate_right(link_ops, w_parent, root); in remove()
703 w = link_ops in remove()
704 .left(link_ops.right(w).unwrap_unchecked()) in remove()
706 w_parent = link_ops.parent(w).unwrap_unchecked(); in remove()
708 let left_color = link_ops.left(w).map(|x| link_ops.color(x)); in remove()
709 let right_color = link_ops.right(w).map(|x| link_ops.color(x)); in remove()
711 link_ops.set_color(w, Color::Red); in remove()
712 if link_ops.parent(w_parent).is_none() in remove()
713 || link_ops.color(w_parent) == Color::Red in remove()
715 link_ops.set_color(w_parent, Color::Black); in remove()
719 link_ops, in remove()
721 link_ops.parent(w_parent).unwrap_unchecked(), in remove()
723 link_ops in remove()
724 .right(link_ops.parent(w_parent).unwrap_unchecked()) in remove()
727 link_ops in remove()
728 .left(link_ops.parent(w_parent).unwrap_unchecked()) in remove()
732 if link_ops.left(w).map(|x| link_ops.color(x)) != Some(Color::Red) { in remove()
733 link_ops.set_color(link_ops.right(w).unwrap_unchecked(), Color::Black); in remove()
734 link_ops.set_color(w, Color::Red); in remove()
735 rotate_left(link_ops, w, root); in remove()
736 w = link_ops.parent(w).unwrap_unchecked(); in remove()
737 w_parent = link_ops.parent(w).unwrap_unchecked(); in remove()
739 link_ops.set_color(w, link_ops.color(w_parent)); in remove()
740 link_ops.set_color(w_parent, Color::Black); in remove()
741 link_ops.set_color(link_ops.left(w).unwrap_unchecked(), Color::Black); in remove()
742 rotate_right(link_ops, w_parent, root); in remove()
749 link_ops.release_link(ptr); in remove()
761 current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
822 self.current = unsafe { next(self.tree.adapter.link_ops(), current) };
824 self.current = Some(unsafe { first_child(self.tree.adapter.link_ops(), root) });
838 self.current = unsafe { prev(self.tree.adapter.link_ops(), current) };
840 self.current = Some(unsafe { last_child(self.tree.adapter.link_ops(), root) });
876 current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
921 self.current = unsafe { next(self.tree.adapter.link_ops(), current) };
923 self.current = Some(unsafe { first_child(self.tree.adapter.link_ops(), root) });
937 self.current = unsafe { prev(self.tree.adapter.link_ops(), current) };
939 self.current = Some(unsafe { last_child(self.tree.adapter.link_ops(), root) });
980 let next = next(self.tree.adapter.link_ops(), current);
1064 let link_ops = self.tree.adapter.link_ops_mut(); localVariable
1068 if link_ops.right(current).is_some() {
1069 let next = next(link_ops, current).unwrap_unchecked();
1070 insert_left(link_ops, next, new, &mut self.tree.root);
1072 insert_right(link_ops, current, new, &mut self.tree.root);
1076 link_ops,
1077 first_child(link_ops, root),
1106 let link_ops = self.tree.adapter.link_ops_mut(); localVariable
1110 if link_ops.left(current).is_some() {
1111 let prev = prev(link_ops, current).unwrap_unchecked();
1112 insert_right(link_ops, prev, new, &mut self.tree.root);
1114 insert_left(link_ops, current, new, &mut self.tree.root);
1118 link_ops,
1119 last_child(link_ops, root),
1174 root: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1186 ) -> <A::LinkOps as link_ops::LinkOps>::LinkPtr {
1187 use link_ops::LinkOps;
1317 unsafe fn insert_root(&mut self, node: <A::LinkOps as link_ops::LinkOps>::LinkPtr) {
1328 let link_ops = self.adapter.link_ops(); localVariable
1332 head: Some(unsafe { first_child(link_ops, root) }),
1333 tail: Some(unsafe { last_child(link_ops, root) }),
1346 fn clear_recurse(&mut self, current: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>) {
1347 use link_ops::LinkOps;
1411 ) -> Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>
1416 let link_ops = self.adapter.link_ops(); localVariable
1422 Ordering::Less => tree = unsafe { link_ops.left(x) },
1424 Ordering::Greater => tree = unsafe { link_ops.right(x) },
1466 ) -> Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>
1471 let link_ops = self.adapter.link_ops(); localVariable
1484 tree = unsafe { link_ops.left(x) };
1486 tree = unsafe { link_ops.right(x) };
1524 ) -> Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>
1529 let link_ops = self.adapter.link_ops(); localVariable
1541 tree = unsafe { link_ops.left(x) };
1544 tree = unsafe { link_ops.right(x) };
1603 if let Some(left) = self.adapter.link_ops().left(tree) {
1610 if let Some(right) = self.adapter.link_ops().right(tree) {
1650 if let Some(left) = self.adapter.link_ops().left(tree) {
1667 if let Some(right) = self.adapter.link_ops().right(tree) {
1763 let link_ops = self.adapter.link_ops(); in into_iter() localVariable
1767 head: Some(unsafe { first_child(link_ops, root) }), in into_iter()
1768 tail: Some(unsafe { last_child(link_ops, root) }), in into_iter()
1823 parent: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1842 let link_ops = self.tree.adapter.link_ops_mut(); localVariable
1845 insert_left(link_ops, parent, new, &mut self.tree.root);
1847 insert_right(link_ops, parent, new, &mut self.tree.root);
1922 head: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1923 tail: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1940 self.head = unsafe { next(self.tree.adapter.link_ops(), head) };
1957 self.tail = unsafe { prev(self.tree.adapter.link_ops(), tail) };
1985 head: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1986 tail: Option<<A::LinkOps as link_ops::LinkOps>::LinkPtr>,
1997 use link_ops::LinkOps;
2000 let link_ops = self.tree.adapter.link_ops_mut(); localVariable
2006 if let Some(parent) = link_ops.parent(head) {
2007 link_ops.set_left(parent, link_ops.right(head));
2009 self.tree.root = link_ops.right(head);
2010 if link_ops.right(head).is_none() {
2014 if let Some(right) = link_ops.right(head) {
2015 link_ops.set_parent(right, link_ops.parent(head));
2016 self.head = Some(first_child(link_ops, right));
2018 self.head = link_ops.parent(head);
2020 link_ops.release_link(head);
2036 use link_ops::LinkOps;
2039 let link_ops = self.tree.adapter.link_ops_mut(); localVariable
2045 if let Some(parent) = link_ops.parent(tail) {
2046 link_ops.set_right(parent, link_ops.left(tail));
2048 self.tree.root = link_ops.left(tail);
2049 if link_ops.left(tail).is_none() {
2053 if let Some(left) = link_ops.left(tail) {
2054 link_ops.set_parent(left, link_ops.parent(tail));
2055 self.tail = Some(last_child(link_ops, left));
2057 self.tail = link_ops.parent(tail);
2059 link_ops.release_link(tail);