linux-master/lib/rbtree.c

59 static inline void rb_set_black(struct rb_node *rb)
64 static inline struct rb_node *rb_red_parent(struct rb_node *red)
66 	return (struct rb_node *)red->__rb_parent_color;
75 __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
78 	struct rb_node *parent = rb_parent(old);
85 __rb_insert(struct rb_node *node, struct rb_root *root,
86 	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
88 	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
227 ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
228 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
230 	struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
410 void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
411 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
424 static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
425 static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
426 static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
434 void rb_insert_color(struct rb_node *node, struct rb_root *root)
440 void rb_erase(struct rb_node *node, struct rb_root *root)
442 	struct rb_node *rebalance;
456 void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
457 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
466 struct rb_node *rb_first(const struct rb_root *root)
468 	struct rb_node	*n;
470 	n = root->rb_node;
479 struct rb_node *rb_last(const struct rb_root *root)
481 	struct rb_node	*n;
483 	n = root->rb_node;
492 struct rb_node *rb_next(const struct rb_node *node)
494 	struct rb_node *parent;
507 		return (struct rb_node *)node;
524 struct rb_node *rb_prev(const struct rb_node *node)
526 	struct rb_node *parent;
539 		return (struct rb_node *)node;
553 void rb_replace_node(struct rb_node *victim, struct rb_node *new,
556 	struct rb_node *parent = rb_parent(victim);
570 void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
573 	struct rb_node *parent = rb_parent(victim);
592 static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
600 			return (struct rb_node *)node;
604 struct rb_node *rb_next_postorder(const struct rb_node *node)
606 	const struct rb_node *parent;
619 		return (struct rb_node *)parent;
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);