tools/lib/rbtree.c

230 	struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
240 		sibling = parent->rb_right;
241 		if (node != sibling) {	/* node == parent->rb_left */
242 			if (rb_is_red(sibling)) {
252 				tmp1 = sibling->rb_left;
254 				WRITE_ONCE(sibling->rb_left, parent);
256 				__rb_rotate_set_parents(parent, sibling, root,
258 				augment_rotate(parent, sibling);
259 				sibling = tmp1;
261 			tmp1 = sibling->rb_right;
263 				tmp2 = sibling->rb_left;
266 					 * Case 2 - sibling color flip
280 					rb_set_parent_color(sibling, parent,
293 				 * Case 3 - right rotate at sibling
320 				WRITE_ONCE(sibling->rb_left, tmp1);
321 				WRITE_ONCE(tmp2->rb_right, sibling);
324 					rb_set_parent_color(tmp1, sibling,
326 				augment_rotate(sibling, tmp2);
327 				tmp1 = sibling;
328 				sibling = tmp2;
342 			tmp2 = sibling->rb_left;
344 			WRITE_ONCE(sibling->rb_left, parent);
345 			rb_set_parent_color(tmp1, sibling, RB_BLACK);
348 			__rb_rotate_set_parents(parent, sibling, root,
350 			augment_rotate(parent, sibling);
353 			sibling = parent->rb_left;
354 			if (rb_is_red(sibling)) {
356 				tmp1 = sibling->rb_right;
358 				WRITE_ONCE(sibling->rb_right, parent);
360 				__rb_rotate_set_parents(parent, sibling, root,
362 				augment_rotate(parent, sibling);
363 				sibling = tmp1;
365 			tmp1 = sibling->rb_left;
367 				tmp2 = sibling->rb_right;
369 					/* Case 2 - sibling color flip */
370 					rb_set_parent_color(sibling, parent,
382 				/* Case 3 - left rotate at sibling */
384 				WRITE_ONCE(sibling->rb_right, tmp1);
385 				WRITE_ONCE(tmp2->rb_left, sibling);
388 					rb_set_parent_color(tmp1, sibling,
390 				augment_rotate(sibling, tmp2);
391 				tmp1 = sibling;
392 				sibling = tmp2;
395 			tmp2 = sibling->rb_right;
397 			WRITE_ONCE(sibling->rb_right, parent);
398 			rb_set_parent_color(tmp1, sibling, RB_BLACK);
401 			__rb_rotate_set_parents(parent, sibling, root,
403 			augment_rotate(parent, sibling);