Orange Pi5 kernel

^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   1) /* SPDX-License-Identifier: GPL-2.0-or-later */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   3)   Red Black Trees
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   4)   (C) 1999  Andrea Arcangeli <andrea@suse.de>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   5)   (C) 2002  David Woodhouse <dwmw2@infradead.org>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   6)   (C) 2012  Michel Lespinasse <walken@google.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   7) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   8) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300   9)   tools/linux/include/linux/rbtree_augmented.h
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  10) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  11)   Copied from:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  12)   linux/include/linux/rbtree_augmented.h
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  13) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  14) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  15) #ifndef _TOOLS_LINUX_RBTREE_AUGMENTED_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  16) #define _TOOLS_LINUX_RBTREE_AUGMENTED_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  17) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  18) #include <linux/compiler.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  19) #include <linux/rbtree.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  20) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  21) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  22)  * Please note - only struct rb_augment_callbacks and the prototypes for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  23)  * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  24)  * The rest are implementation details you are not expected to depend on.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  25)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  26)  * See Documentation/core-api/rbtree.rst for documentation and samples.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  27)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  28) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  29) struct rb_augment_callbacks {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  30) 	void (*propagate)(struct rb_node *node, struct rb_node *stop);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  31) 	void (*copy)(struct rb_node *old, struct rb_node *new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  32) 	void (*rotate)(struct rb_node *old, struct rb_node *new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  33) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  34) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  35) extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  36) 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  37) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  38) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  39)  * Fixup the rbtree and update the augmented information when rebalancing.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  40)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  41)  * On insertion, the user must update the augmented information on the path
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  42)  * leading to the inserted node, then call rb_link_node() as usual and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  43)  * rb_insert_augmented() instead of the usual rb_insert_color() call.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  44)  * If rb_insert_augmented() rebalances the rbtree, it will callback into
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  45)  * a user provided function to update the augmented information on the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  46)  * affected subtrees.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  47)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  48) static inline void
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  49) rb_insert_augmented(struct rb_node *node, struct rb_root *root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  50) 		    const struct rb_augment_callbacks *augment)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  51) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  52) 	__rb_insert_augmented(node, root, augment->rotate);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  53) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  54) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  55) static inline void
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  56) rb_insert_augmented_cached(struct rb_node *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  57) 			   struct rb_root_cached *root, bool newleft,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  58) 			   const struct rb_augment_callbacks *augment)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  59) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  60) 	if (newleft)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  61) 		root->rb_leftmost = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  62) 	rb_insert_augmented(node, &root->rb_root, augment);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  63) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  64) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  65) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  66)  * Template for declaring augmented rbtree callbacks (generic case)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  67)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  68)  * RBSTATIC:    'static' or empty
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  69)  * RBNAME:      name of the rb_augment_callbacks structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  70)  * RBSTRUCT:    struct type of the tree nodes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  71)  * RBFIELD:     name of struct rb_node field within RBSTRUCT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  72)  * RBAUGMENTED: name of field within RBSTRUCT holding data for subtree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  73)  * RBCOMPUTE:   name of function that recomputes the RBAUGMENTED data
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  74)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  75) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  76) #define RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,				\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  77) 			     RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE)	\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  78) static inline void							\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  79) RBNAME ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  80) {									\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  81) 	while (rb != stop) {						\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  82) 		RBSTRUCT *node = rb_entry(rb, RBSTRUCT, RBFIELD);	\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  83) 		if (RBCOMPUTE(node, true))				\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  84) 			break;						\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  85) 		rb = rb_parent(&node->RBFIELD);				\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  86) 	}								\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  87) }									\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  88) static inline void							\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  89) RBNAME ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  90) {									\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  91) 	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  92) 	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  93) 	new->RBAUGMENTED = old->RBAUGMENTED;				\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  94) }									\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  95) static void								\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  96) RBNAME ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  97) {									\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  98) 	RBSTRUCT *old = rb_entry(rb_old, RBSTRUCT, RBFIELD);		\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300  99) 	RBSTRUCT *new = rb_entry(rb_new, RBSTRUCT, RBFIELD);		\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) 	new->RBAUGMENTED = old->RBAUGMENTED;				\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) 	RBCOMPUTE(old, false);						\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) }									\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) RBSTATIC const struct rb_augment_callbacks RBNAME = {			\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) 	.propagate = RBNAME ## _propagate,				\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) 	.copy = RBNAME ## _copy,					\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) 	.rotate = RBNAME ## _rotate					\
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110)  * Template for declaring augmented rbtree callbacks,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111)  * computing RBAUGMENTED scalar as max(RBCOMPUTE(node)) for all subtree nodes.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112)  *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113)  * RBSTATIC:    'static' or empty
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114)  * RBNAME:      name of the rb_augment_callbacks structure
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)  * RBSTRUCT:    struct type of the tree nodes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)  * RBFIELD:     name of struct rb_node field within RBSTRUCT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117)  * RBTYPE:      type of the RBAUGMENTED field
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118)  * RBAUGMENTED: name of RBTYPE field within RBSTRUCT holding data for subtree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)  * RBCOMPUTE:   name of function that returns the per-node RBTYPE scalar
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)  */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) #define RB_DECLARE_CALLBACKS_MAX(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD,	      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) 				 RBTYPE, RBAUGMENTED, RBCOMPUTE)	      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)	      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) {									      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) 	RBSTRUCT *child;						      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) 	RBTYPE max = RBCOMPUTE(node);					      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) 	if (node->RBFIELD.rb_left) {					      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) 		child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) 		if (child->RBAUGMENTED > max)				      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) 			max = child->RBAUGMENTED;			      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) 	}								      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) 	if (node->RBFIELD.rb_right) {					      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) 		child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) 		if (child->RBAUGMENTED > max)				      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) 			max = child->RBAUGMENTED;			      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) 	}								      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) 	if (exit && node->RBAUGMENTED == max)				      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) 		return true;						      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) 	node->RBAUGMENTED = max;					      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) 	return false;							      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) }									      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,					      \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) 		     RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) #define	RB_RED		0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) #define	RB_BLACK	1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) #define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) #define __rb_color(pc)     ((pc) & 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) #define __rb_is_black(pc)  __rb_color(pc)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) #define __rb_is_red(pc)    (!__rb_color(pc))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) #define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) 	rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) static inline void rb_set_parent_color(struct rb_node *rb,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) 				       struct rb_node *p, int color)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) 	rb->__rb_parent_color = (unsigned long)p | color;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) static inline void
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) __rb_change_child(struct rb_node *old, struct rb_node *new,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) 		  struct rb_node *parent, struct rb_root *root)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) 	if (parent) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) 		if (parent->rb_left == old)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) 			WRITE_ONCE(parent->rb_left, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) 		else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) 			WRITE_ONCE(parent->rb_right, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) 	} else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) 		WRITE_ONCE(root->rb_node, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) static __always_inline struct rb_node *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) 		     const struct rb_augment_callbacks *augment)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) 	struct rb_node *child = node->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) 	struct rb_node *tmp = node->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) 	struct rb_node *parent, *rebalance;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) 	unsigned long pc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) 	if (!tmp) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) 		/*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) 		 * Case 1: node to erase has no more than 1 child (easy!)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) 		 *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) 		 * Note that if there is one child it must be red due to 5)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) 		 * and node must be black due to 4). We adjust colors locally
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) 		 * so as to bypass __rb_erase_color() later on.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) 		 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) 		pc = node->__rb_parent_color;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) 		parent = __rb_parent(pc);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) 		__rb_change_child(node, child, parent, root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) 		if (child) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) 			child->__rb_parent_color = pc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) 			rebalance = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) 		} else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) 			rebalance = __rb_is_black(pc) ? parent : NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) 		tmp = parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) 	} else if (!child) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) 		/* Still case 1, but this time the child is node->rb_left */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) 		tmp->__rb_parent_color = pc = node->__rb_parent_color;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) 		parent = __rb_parent(pc);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) 		__rb_change_child(node, tmp, parent, root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) 		rebalance = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) 		tmp = parent;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) 	} else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) 		struct rb_node *successor = child, *child2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) 		tmp = child->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) 		if (!tmp) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) 			/*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) 			 * Case 2: node's successor is its right child
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) 			 *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) 			 *    (n)          (s)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) 			 *    / \          / \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) 			 *  (x) (s)  ->  (x) (c)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) 			 *        \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) 			 *        (c)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) 			 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) 			parent = successor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) 			child2 = successor->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) 			augment->copy(node, successor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) 		} else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) 			/*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) 			 * Case 3: node's successor is leftmost under
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) 			 * node's right child subtree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) 			 *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) 			 *    (n)          (s)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) 			 *    / \          / \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) 			 *  (x) (y)  ->  (x) (y)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) 			 *      /            /
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) 			 *    (p)          (p)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) 			 *    /            /
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) 			 *  (s)          (c)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) 			 *    \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) 			 *    (c)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) 			 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) 			do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) 				parent = successor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) 				successor = tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) 				tmp = tmp->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) 			} while (tmp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) 			child2 = successor->rb_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) 			WRITE_ONCE(parent->rb_left, child2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) 			WRITE_ONCE(successor->rb_right, child);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) 			rb_set_parent(child, successor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) 			augment->copy(node, successor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) 			augment->propagate(parent, successor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) 		}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) 		tmp = node->rb_left;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) 		WRITE_ONCE(successor->rb_left, tmp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) 		rb_set_parent(tmp, successor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) 		pc = node->__rb_parent_color;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) 		tmp = __rb_parent(pc);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) 		__rb_change_child(node, successor, tmp, root);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) 		if (child2) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) 			successor->__rb_parent_color = pc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) 			rb_set_parent_color(child2, parent, RB_BLACK);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) 			rebalance = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) 		} else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) 			unsigned long pc2 = successor->__rb_parent_color;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) 			successor->__rb_parent_color = pc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) 			rebalance = __rb_is_black(pc2) ? parent : NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) 		}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) 		tmp = successor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) 	}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) 	augment->propagate(tmp, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) 	return rebalance;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) static __always_inline void
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) rb_erase_augmented(struct rb_node *node, struct rb_root *root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) 		   const struct rb_augment_callbacks *augment)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) 	struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) 	if (rebalance)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) 		__rb_erase_color(rebalance, root, augment->rotate);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) static __always_inline void
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) 			  const struct rb_augment_callbacks *augment)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) 	if (root->rb_leftmost == node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) 		root->rb_leftmost = rb_next(node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) 	rb_erase_augmented(node, &root->rb_root, augment);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) 
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) #endif /* _TOOLS_LINUX_RBTREE_AUGMENTED_H */