geany  1.38
About: Geany is a text editor (using GTK2) with basic features of an integrated development environment (syntax highlighting, code folding, symbol name auto-completion, ...). F: office T: editor programming GTK+ IDE
  Fossies Dox: geany-1.38.tar.bz2  ("unofficial" and yet experimental doxygen-generated source code documentation)  

rbtree.h
Go to the documentation of this file.
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-----------------------------------------------------------------------
50static 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
70static 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
96static 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
154{
156#define RB_RED 0
157#define RB_BLACK 1
160} CTAGA_ATTR_ALIGNED(sizeof(long));
161 /* The alignment might seem pointless, but allegedly CRIS needs it */
162
164{
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
176CTAGS_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}
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
193{
194 rb->rb_parent_color = 0;
195 rb->rb_right = NULL;
196 rb->rb_left = NULL;
197 RB_CLEAR_NODE(rb);
198}
199
200extern void rb_insert_color(struct rb_node *, struct rb_root *);
201extern void rb_erase(struct rb_node *, struct rb_root *);
202
203typedef void (*rb_augment_f)(struct rb_node *node, void *data);
204
205extern void rb_augment_insert(struct rb_node *node,
206 rb_augment_f func, void *data);
207extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);
208extern 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 */
212extern struct rb_node *rb_next(const struct rb_node *);
213extern struct rb_node *rb_prev(const struct rb_node *);
214extern struct rb_node *rb_first(const struct rb_root *);
215extern struct rb_node *rb_last(const struct rb_root *);
216
217/* Fast replacement of a single node without remove/rebalance/add/rebalance */
218extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
219 struct rb_root *root);
220
221CTAGS_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 */
GdkColor color
Definition: document.c:3220
#define CTAGA_ATTR_ALIGNED(X)
Definition: gcc-attr.h:24
#define CTAGS_INLINE
Definition: inline.h:23
struct rb_node * rb_augment_erase_begin(struct rb_node *node)
Definition: rbtree.c:337
#define NULL
Definition: rbtree.h:150
static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
Definition: rbtree.h:176
void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
Definition: rbtree.c:323
void(* rb_augment_f)(struct rb_node *node, void *data)
Definition: rbtree.h:203
static void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)
Definition: rbtree.h:221
static void rb_set_color(struct rb_node *rb, int color)
Definition: rbtree.h:180
struct rb_node * rb_next(const struct rb_node *)
Definition: rbtree.c:395
void rb_insert_color(struct rb_node *, struct rb_root *)
Definition: rbtree.c:88
void rb_erase(struct rb_node *, struct rb_root *)
Definition: rbtree.c:233
static void rb_init_node(struct rb_node *rb)
Definition: rbtree.h:192
struct rb_node * rb_first(const struct rb_root *)
Definition: rbtree.c:371
struct rb_node * rb_prev(const struct rb_node *)
Definition: rbtree.c:423
struct rb_node * rb_last(const struct rb_root *)
Definition: rbtree.c:383
void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
Definition: rbtree.c:362
void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root)
Definition: rbtree.c:447
#define RB_CLEAR_NODE(node)
Definition: rbtree.h:190
struct rb_node * rb_left
Definition: rbtree.h:159
uintptr_t rb_parent_color
Definition: rbtree.h:155
struct rb_node * rb_right
Definition: rbtree.h:158
struct rb_node * rb_node
Definition: rbtree.h:165