3 * Copyright (C) 1999 Andrea Arcangeli <andrea@suse.de>
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
28 uintptr_t __rb_parent_color;
29 struct rb_node *rb_right;
30 struct rb_node *rb_left;
34 struct rb_node *rb_node;
37 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
39 #define RB_ROOT (struct rb_root) { NULL, }
42 rb_empty_root(const struct rb_root *root)
44 return root->rb_node == NULL;
47 static inline struct rb_node *
48 rb_parent(const struct rb_node *node)
50 return (struct rb_node *)(node->__rb_parent_color & ~1);
53 /* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
55 rb_empty_node(const struct rb_node *node)
57 return node->__rb_parent_color == (uintptr_t)node;
61 rb_clear_node(struct rb_node *node)
63 node->__rb_parent_color = (uintptr_t)node;
67 rb_insert_color(struct rb_node *node, struct rb_root *root);
70 rb_erase(struct rb_node *node, struct rb_root *root);
72 extern struct rb_node *
73 rb_first(const struct rb_root *root);
75 extern struct rb_node *
76 rb_first_postorder(const struct rb_root *root);
78 extern struct rb_node *
79 rb_next(const struct rb_node *node);
81 extern struct rb_node *
82 rb_next_postorder(const struct rb_node *node, const struct rb_node *parent);
85 rb_link_node(struct rb_node *node, struct rb_node *parent,
86 struct rb_node **rb_link)
88 node->__rb_parent_color = (uintptr_t)parent;
89 node->rb_left = node->rb_right = NULL;
93 #endif /* _RBTREE_H */