1 /*
2   Red Black Trees
3   (C) 1999  Andrea Arcangeli <andrea@suse.de>
4   (C) 2002  David Woodhouse <dwmw2@infradead.org>
5   (C) 2012  Michel Lespinasse <walken@google.com>
6 
7   This program is free software; you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by
9   the Free Software Foundation; either version 2 of the License, or
10   (at your option) any later version.
11 
12   This program is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16 
17   You should have received a copy of the GNU General Public License
18   along with this program; if not, write to the Free Software
19   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20 
21   linux/include/linux/rbtree_augmented.h
22 */
23 
24 #ifndef _LINUX_RBTREE_AUGMENTED_H
25 #define _LINUX_RBTREE_AUGMENTED_H
26 
27 #include <linux/compiler.h>
28 #include <linux/rbtree.h>
29 
30 /*
31  * Please note - only struct rb_augment_callbacks and the prototypes for
32  * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
33  * The rest are implementation details you are not expected to depend on.
34  *
35  * See Documentation/rbtree.txt for documentation and samples.
36  */
37 
38 struct rb_augment_callbacks {
39 	void (*propagate)(struct rb_node *node, struct rb_node *stop);
40 	void (*copy)(struct rb_node *old, struct rb_node *new);
41 	void (*rotate)(struct rb_node *old, struct rb_node *new);
42 };
43 
44 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
45 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
46 /*
47  * Fixup the rbtree and update the augmented information when rebalancing.
48  *
49  * On insertion, the user must update the augmented information on the path
50  * leading to the inserted node, then call rb_link_node() as usual and
51  * rb_augment_inserted() instead of the usual rb_insert_color() call.
52  * If rb_augment_inserted() rebalances the rbtree, it will callback into
53  * a user provided function to update the augmented information on the
54  * affected subtrees.
55  */
56 static inline void
57 rb_insert_augmented(struct rb_node *node, struct rb_root *root,
58 		    const struct rb_augment_callbacks *augment)
59 {
60 	__rb_insert_augmented(node, root, augment->rotate);
61 }
62 
63 #define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,	\
64 			     rbtype, rbaugmented, rbcompute)		\
65 static inline void							\
66 rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
67 {									\
68 	while (rb != stop) {						\
69 		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
70 		rbtype augmented = rbcompute(node);			\
71 		if (node->rbaugmented == augmented)			\
72 			break;						\
73 		node->rbaugmented = augmented;				\
74 		rb = rb_parent(&node->rbfield);				\
75 	}								\
76 }									\
77 static inline void							\
78 rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
79 {									\
80 	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
81 	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
82 	new->rbaugmented = old->rbaugmented;				\
83 }									\
84 static void								\
85 rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
86 {									\
87 	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
88 	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
89 	new->rbaugmented = old->rbaugmented;				\
90 	old->rbaugmented = rbcompute(old);				\
91 }									\
92 rbstatic const struct rb_augment_callbacks rbname = {			\
93 	rbname ## _propagate, rbname ## _copy, rbname ## _rotate	\
94 };
95 
96 
97 #define	RB_RED		0
98 #define	RB_BLACK	1
99 
100 #define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
101 
102 #define __rb_color(pc)     ((pc) & 1)
103 #define __rb_is_black(pc)  __rb_color(pc)
104 #define __rb_is_red(pc)    (!__rb_color(pc))
105 #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
106 #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
107 #define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
108 
109 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
110 {
111 	rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
112 }
113 
114 static inline void rb_set_parent_color(struct rb_node *rb,
115 				       struct rb_node *p, int color)
116 {
117 	rb->__rb_parent_color = (unsigned long)p | color;
118 }
119 
120 static inline void
121 __rb_change_child(struct rb_node *old, struct rb_node *new,
122 		  struct rb_node *parent, struct rb_root *root)
123 {
124 	if (parent) {
125 		if (parent->rb_left == old)
126 			parent->rb_left = new;
127 		else
128 			parent->rb_right = new;
129 	} else
130 		root->rb_node = new;
131 }
132 
133 extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
134 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
135 
136 static __always_inline struct rb_node *
137 __rb_erase_augmented(struct rb_node *node, struct rb_root *root,
138 		     const struct rb_augment_callbacks *augment)
139 {
140 	struct rb_node *child = node->rb_right, *tmp = node->rb_left;
141 	struct rb_node *parent, *rebalance;
142 	unsigned long pc;
143 
144 	if (!tmp) {
145 		/*
146 		 * Case 1: node to erase has no more than 1 child (easy!)
147 		 *
148 		 * Note that if there is one child it must be red due to 5)
149 		 * and node must be black due to 4). We adjust colors locally
150 		 * so as to bypass __rb_erase_color() later on.
151 		 */
152 		pc = node->__rb_parent_color;
153 		parent = __rb_parent(pc);
154 		__rb_change_child(node, child, parent, root);
155 		if (child) {
156 			child->__rb_parent_color = pc;
157 			rebalance = NULL;
158 		} else
159 			rebalance = __rb_is_black(pc) ? parent : NULL;
160 		tmp = parent;
161 	} else if (!child) {
162 		/* Still case 1, but this time the child is node->rb_left */
163 		tmp->__rb_parent_color = pc = node->__rb_parent_color;
164 		parent = __rb_parent(pc);
165 		__rb_change_child(node, tmp, parent, root);
166 		rebalance = NULL;
167 		tmp = parent;
168 	} else {
169 		struct rb_node *successor = child, *child2;
170 		tmp = child->rb_left;
171 		if (!tmp) {
172 			/*
173 			 * Case 2: node's successor is its right child
174 			 *
175 			 *    (n)          (s)
176 			 *    / \          / \
177 			 *  (x) (s)  ->  (x) (c)
178 			 *        \
179 			 *        (c)
180 			 */
181 			parent = successor;
182 			child2 = successor->rb_right;
183 			augment->copy(node, successor);
184 		} else {
185 			/*
186 			 * Case 3: node's successor is leftmost under
187 			 * node's right child subtree
188 			 *
189 			 *    (n)          (s)
190 			 *    / \          / \
191 			 *  (x) (y)  ->  (x) (y)
192 			 *      /            /
193 			 *    (p)          (p)
194 			 *    /            /
195 			 *  (s)          (c)
196 			 *    \
197 			 *    (c)
198 			 */
199 			do {
200 				parent = successor;
201 				successor = tmp;
202 				tmp = tmp->rb_left;
203 			} while (tmp);
204 			parent->rb_left = child2 = successor->rb_right;
205 			successor->rb_right = child;
206 			rb_set_parent(child, successor);
207 			augment->copy(node, successor);
208 			augment->propagate(parent, successor);
209 		}
210 
211 		successor->rb_left = tmp = node->rb_left;
212 		rb_set_parent(tmp, successor);
213 
214 		pc = node->__rb_parent_color;
215 		tmp = __rb_parent(pc);
216 		__rb_change_child(node, successor, tmp, root);
217 		if (child2) {
218 			successor->__rb_parent_color = pc;
219 			rb_set_parent_color(child2, parent, RB_BLACK);
220 			rebalance = NULL;
221 		} else {
222 			unsigned long pc2 = successor->__rb_parent_color;
223 			successor->__rb_parent_color = pc;
224 			rebalance = __rb_is_black(pc2) ? parent : NULL;
225 		}
226 		tmp = successor;
227 	}
228 
229 	augment->propagate(tmp, NULL);
230 	return rebalance;
231 }
232 
233 static __always_inline void
234 rb_erase_augmented(struct rb_node *node, struct rb_root *root,
235 		   const struct rb_augment_callbacks *augment)
236 {
237 	struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
238 	if (rebalance)
239 		__rb_erase_color(rebalance, root, augment->rotate);
240 }
241 
242 #endif	/* _LINUX_RBTREE_AUGMENTED_H */
243