Lines Matching full:parent
53 * rank-difference as an attribute of each pointer from parent to child.
353 #define RB_SET(elm, parent, field) do { \ argument
354 _RB_UP(elm, field) = parent; \
394 * The parent-child relationship between elm and its former parent is not
527 struct type *parent, struct type *elm) \
530 * Initially, elm is a leaf. Either its parent was previously \
534 * possibility of two red null children for the initial parent. \
545 gpar = _RB_UP(parent, field); \
546 elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
548 /* shorten the parent-elm edge to rebalance */ \
549 _RB_BITSUP(parent, field) ^= elmdir; \
554 _RB_BITSUP(parent, field) ^= sibdir; \
556 /* both edges now short, retry from parent */ \
558 elm = parent; \
561 _RB_UP(parent, field) = gpar = _RB_PTR(gpar); \
566 * direction as the edge from parent to elm, \
568 * parent to z was shortened above. Shorten \
586 _RB_BITSUP(parent, field) ^= elmdir; \
600 * in the direction of 'parent'. Rotate to make \
601 * 'parent' a child of 'child', then make both edges \
612 RB_ROTATE(parent, child, sibdir, field); \
614 RB_SWAP_CHILD(head, gpar, parent, child, field); \
621 (void)RB_AUGMENT_CHECK(parent); \
623 } while ((parent = gpar) != NULL); \
630 * 'parent' with one higher rank, and then reduces its rank if 'parent' has
631 * become a leaf. This implementation always has the parent in its new position
641 struct type *parent, struct type *elm) \
646 if (RB_RIGHT(parent, field) == elm && \
647 RB_LEFT(parent, field) == elm) { \
650 _RB_UP(parent, field) = _RB_PTR(_RB_UP(parent, field)); \
651 elm = parent; \
652 if ((parent = _RB_UP(elm, field)) == NULL) \
657 gpar = _RB_UP(parent, field); \
658 elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
661 /* lengthen the parent-elm edge to rebalance */ \
662 _RB_UP(parent, field) = gpar; \
666 /* shorten other edge, retry from parent */ \
668 _RB_UP(parent, field) = gpar; \
673 sib = _RB_LINK(parent, sibdir, field); \
684 * 'parent' is long. The short edge descending \
685 * from 'sib' toward 'parent' points to 'elm*' \
706 _RB_BITSUP(parent, field) ^= \
714 /* if parent does not become a leaf, \
715 do not demote parent yet. */ \
716 _RB_BITSUP(parent, field) ^= sibdir; \
719 /* demote parent. */ \
720 _RB_BITSUP(parent, field) ^= elmdir; \
728 * The edge descending from 'elm' away from 'parent' \
729 * is short. Rotate to make 'parent' a child of 'elm', \
731 * 'parent' and 'elm' to rebalance. \
742 RB_ROTATE(parent, elm, elmdir, field); \
744 RB_SWAP_CHILD(head, gpar, parent, elm, field); \
752 return (parent); \
753 } while (elm = parent, (parent = gpar) != NULL); \
768 struct type *child, *in, *opar, *parent; \
775 parent = opar = _RB_PTR(opar); \
777 parent = in; \
783 if (parent != in) { \
784 RB_SET_PARENT(parent, in, field); \
785 RB_RIGHT(in, field) = parent; \
786 parent = RB_PARENT(in, field); \
787 RB_LEFT(parent, field) = child; \
794 _RB_UP(child, field) = parent; \
795 if (parent != NULL) { \
796 opar = name##_RB_REMOVE_COLOR(head, parent, child); \
797 /* if rotation has made 'parent' the root of the same \
799 if (parent == in && RB_LEFT(parent, field) == NULL) { \
801 parent = RB_PARENT(parent, field); \
803 _RB_AUGMENT_WALK(parent, opar, field); \
820 name##_RB_INSERT_FINISH(struct name *head, struct type *parent, \
825 RB_SET(elm, parent, field); \
827 if (parent != NULL) \
828 tmp = name##_RB_INSERT_COLOR(head, parent, elm); \
847 struct type *parent = NULL; \
850 parent = tmp; \
851 __typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \
853 tmpp = &RB_LEFT(parent, field); \
855 tmpp = &RB_RIGHT(parent, field); \
857 return (parent); \
859 return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm)); \
990 struct type *parent = NULL; \
992 parent = tmp; \
998 return (parent); \