linux-master/lib/rbtree.c

19  *  2) The root is black
22  *  5) Every simple path from root to leaves contains the same number
76 			struct rb_root *root, int color)
81 	__rb_change_child(old, new, parent, root);
85 __rb_insert(struct rb_node *node, struct rb_root *root,
96 			 * The inserted node is root. Either this is the
107 		 * per 4), we don't want a red root or two
180 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
215 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
227 ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
236 		 * - node is not the root (parent is not NULL)
256 				__rb_rotate_set_parents(parent, sibling, root,
348 			__rb_rotate_set_parents(parent, sibling, root,
360 				__rb_rotate_set_parents(parent, sibling, root,
401 			__rb_rotate_set_parents(parent, sibling, root,
410 void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
413 	____rb_erase_color(parent, root, augment_rotate);
434 void rb_insert_color(struct rb_node *node, struct rb_root *root)
436 	__rb_insert(node, root, dummy_rotate);
440 void rb_erase(struct rb_node *node, struct rb_root *root)
443 	rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
445 		____rb_erase_color(rebalance, root, dummy_rotate);
456 void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
459 	__rb_insert(node, root, augment_rotate);
466 struct rb_node *rb_first(const struct rb_root *root)
470 	n = root->rb_node;
479 struct rb_node *rb_last(const struct rb_root *root)
483 	n = root->rb_node;
554 		     struct rb_root *root)
566 	__rb_change_child(victim, new, parent, root);
571 			 struct rb_root *root)
588 	__rb_change_child_rcu(victim, new, parent, root);
623 struct rb_node *rb_first_postorder(const struct rb_root *root)
625 	if (!root->rb_node)
628 	return rb_left_deepest_node(root->rb_node);