1 /*
2 * =============================================================================
3 *
4 * Filename: rbtree.h
5 *
6 * Description: rbtree(Red-Black tree) implementation adapted from linux
7 * kernel thus can be used in userspace c program.
8 *
9 * Created: 09/02/2012 11:36:11 PM
10 *
11 * Author: Fu Haiping (forhappy), haipingf@gmail.com
12 * Company: ICT ( Institute Of Computing Technology, CAS )
13 *
14 * =============================================================================
15 */
16
17 /*
18 Red Black Trees
19 (C) 1999 Andrea Arcangeli <andrea@suse.de>
20
21 This program is free software; you can redistribute it and/or modify
22 it under the terms of the GNU General Public License as published by
23 the Free Software Foundation; either version 2 of the License, or
24 (at your option) any later version.
25
26 This program is distributed in the hope that it will be useful,
27 but WITHOUT ANY WARRANTY; without even the implied warranty of
28 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
29 GNU General Public License for more details.
30
31 You should have received a copy of the GNU General Public License
32 along with this program; if not, write to the Free Software
33 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
34
35 linux/include/linux/rbtree.h
36
37 To use rbtrees you'll have to implement your own insert and search cores.
38 This will avoid us to use callbacks and to drop drammatically performances.
39 I know it's not the cleaner way, but in C (not in C++) to get
40 performances and genericity...
41
42 Some example of insert and search follows here. The search is a plain
43 normal search over an ordered tree. The insert instead must be implemented
44 in two steps: First, the code must insert the element in order as a red leaf
45 in the tree, and then the support library function rb_insert_color() must
46 be called. Such function will do the not trivial work to rebalance the
47 rbtree, if necessary.
48
49 -----------------------------------------------------------------------
50 static inline struct page * rb_search_page_cache(struct inode * inode,
51 unsigned long offset)
52 {
53 struct rb_node * n = inode->i_rb_page_cache.rb_node;
54 struct page * page;
55
56 while (n)
57 {
58 page = rb_entry(n, struct page, rb_page_cache);
59
60 if (offset < page->offset)
61 n = n->rb_left;
62 else if (offset > page->offset)
63 n = n->rb_right;
64 else
65 return page;
66 }
67 return NULL;
68 }
69
70 static inline struct page * __rb_insert_page_cache(struct inode * inode,
71 unsigned long offset,
72 struct rb_node * node)
73 {
74 struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
75 struct rb_node * parent = NULL;
76 struct page * page;
77
78 while (*p)
79 {
80 parent = *p;
81 page = rb_entry(parent, struct page, rb_page_cache);
82
83 if (offset < page->offset)
84 p = &(*p)->rb_left;
85 else if (offset > page->offset)
86 p = &(*p)->rb_right;
87 else
88 return page;
89 }
90
91 rb_link_node(node, parent, p);
92
93 return NULL;
94 }
95
96 static inline struct page * rb_insert_page_cache(struct inode * inode,
97 unsigned long offset,
98 struct rb_node * node)
99 {
100 struct page * ret;
101 if ((ret = __rb_insert_page_cache(inode, offset, node)))
102 goto out;
103 rb_insert_color(node, &inode->i_rb_page_cache);
104 out:
105 return ret;
106 }
107 -----------------------------------------------------------------------
108 */
109
110 #ifndef CTAGS_MAIN_RBTREE_H
111 #define CTAGS_MAIN_RBTREE_H
112
113 #include "general.h"
114 #include "inline.h"
115 #include "gcc-attr.h"
116 #include <stdint.h>
117
118 #if defined(container_of)
119 #undef container_of
120 #if defined(HAVE_TYPEOF) && defined(HAVE_STATEMENT_EXPRESSION_EXT)
121 #define container_of(ptr, type, member) ({ \
122 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
123 (type *)( (char *)__mptr - offsetof(type,member) );})
124 #else
125 #define container_of(ptr, type, member) \
126 ((type *)( (char *)ptr - offsetof(type,member)))
127 #endif /* defined(HAVE_TYPEOF) && defined(HAVE_STATEMENT_EXPRESSION_EXT) */
128 #else
129 #if defined(HAVE_TYPEOF) && defined(HAVE_STATEMENT_EXPRESSION_EXT)
130 #define container_of(ptr, type, member) ({ \
131 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
132 (type *)( (char *)__mptr - offsetof(type,member) );})
133 #else
134 #define container_of(ptr, type, member) \
135 ((type *)( (char *)ptr - offsetof(type,member)))
136 #endif /* defined(HAVE_TYPEOF) && defined(HAVE_STATEMENT_EXPRESSION_EXT) */
137 #endif /* defined(container_of) */
138
139 #if defined(offsetof)
140 #undef offsetof
141 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
142 #else
143 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
144 #endif
145
146 #undef NULL
147 #if defined(__cplusplus)
148 #define NULL 0
149 #else
150 #define NULL ((void *)0)
151 #endif
152
153 struct rb_node
154 {
155 uintptr_t rb_parent_color;
156 #define RB_RED 0
157 #define RB_BLACK 1
158 struct rb_node *rb_right;
159 struct rb_node *rb_left;
160 } CTAGA_ATTR_ALIGNED(sizeof(long));
161 /* The alignment might seem pointless, but allegedly CRIS needs it */
162
163 struct rb_root
164 {
165 struct rb_node *rb_node;
166 };
167
168
169 #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
170 #define rb_color(r) ((r)->rb_parent_color & 1)
171 #define rb_is_red(r) (!rb_color(r))
172 #define rb_is_black(r) rb_color(r)
173 #define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
174 #define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
175
rb_set_parent(struct rb_node * rb,struct rb_node * p)176 CTAGS_INLINE void rb_set_parent(struct rb_node *rb, struct rb_node *p)
177 {
178 rb->rb_parent_color = (rb->rb_parent_color & 3) | (uintptr_t)p;
179 }
rb_set_color(struct rb_node * rb,int color)180 CTAGS_INLINE void rb_set_color(struct rb_node *rb, int color)
181 {
182 rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
183 }
184
185 #define RB_ROOT (struct rb_root) { NULL, }
186 #define rb_entry(ptr, type, member) container_of(ptr, type, member)
187
188 #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
189 #define RB_EMPTY_NODE(node) (rb_parent(node) == node)
190 #define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
191
rb_init_node(struct rb_node * rb)192 CTAGS_INLINE void rb_init_node(struct rb_node *rb)
193 {
194 rb->rb_parent_color = 0;
195 rb->rb_right = NULL;
196 rb->rb_left = NULL;
197 RB_CLEAR_NODE(rb);
198 }
199
200 extern void rb_insert_color(struct rb_node *, struct rb_root *);
201 extern void rb_erase(struct rb_node *, struct rb_root *);
202
203 typedef void (*rb_augment_f)(struct rb_node *node, void *data);
204
205 extern void rb_augment_insert(struct rb_node *node,
206 rb_augment_f func, void *data);
207 extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);
208 extern void rb_augment_erase_end(struct rb_node *node,
209 rb_augment_f func, void *data);
210
211 /* Find logical next and previous nodes in a tree */
212 extern struct rb_node *rb_next(const struct rb_node *);
213 extern struct rb_node *rb_prev(const struct rb_node *);
214 extern struct rb_node *rb_first(const struct rb_root *);
215 extern struct rb_node *rb_last(const struct rb_root *);
216
217 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
218 extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
219 struct rb_root *root);
220
rb_link_node(struct rb_node * node,struct rb_node * parent,struct rb_node ** rb_link)221 CTAGS_INLINE void rb_link_node(struct rb_node * node, struct rb_node * parent,
222 struct rb_node ** rb_link)
223 {
224 node->rb_parent_color = (uintptr_t)parent;
225 node->rb_left = node->rb_right = NULL;
226
227 *rb_link = node;
228 }
229
230 #endif /* CTAGS_MAIN_RBTREE_H */
231