ReactOS 0.4.16-dev-306-g647d351
rbtree.h
Go to the documentation of this file.
1/*
2 * Red-black search tree support
3 *
4 * Copyright 2009 Henri Verbeet
5 * Copyright 2009 Andrew Riedi
6 * Copyright 2016 Jacek Caban for CodeWeavers
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
21 */
22
23#ifndef __WINE_WINE_RBTREE_H
24#define __WINE_WINE_RBTREE_H
25
26#ifdef __GNUC__
27# define WINE_RB_ENTRY_VALUE(element, type, field) ({ \
28 const typeof(((type *)0)->field) *__ptr = (element); \
29 (type *)((char *)__ptr - offsetof(type, field)); })
30#else
31# define WINE_RB_ENTRY_VALUE(element, type, field) \
32 ((type *)((char *)(element) - offsetof(type, field)))
33#endif
34
36{
40 unsigned int flags;
41};
42
43typedef int (*wine_rb_compare_func_t)(const void *key, const struct wine_rb_entry *entry);
44
46{
49};
50
52
53#define WINE_RB_FLAG_RED 0x1
54
55static inline int wine_rb_is_red(struct wine_rb_entry *entry)
56{
57 return entry && (entry->flags & WINE_RB_FLAG_RED);
58}
59
60static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
61{
62 struct wine_rb_entry *right = e->right;
63
64 if (!e->parent)
65 tree->root = right;
66 else if (e->parent->left == e)
67 e->parent->left = right;
68 else
69 e->parent->right = right;
70
71 e->right = right->left;
72 if (e->right) e->right->parent = e;
73 right->left = e;
74 right->parent = e->parent;
75 e->parent = right;
76}
77
78static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e)
79{
80 struct wine_rb_entry *left = e->left;
81
82 if (!e->parent)
83 tree->root = left;
84 else if (e->parent->left == e)
85 e->parent->left = left;
86 else
87 e->parent->right = left;
88
89 e->left = left->right;
90 if (e->left) e->left->parent = e;
91 left->right = e;
92 left->parent = e->parent;
93 e->parent = left;
94}
95
96static inline void wine_rb_flip_color(struct wine_rb_entry *entry)
97{
98 entry->flags ^= WINE_RB_FLAG_RED;
99 entry->left->flags ^= WINE_RB_FLAG_RED;
100 entry->right->flags ^= WINE_RB_FLAG_RED;
101}
102
103static inline struct wine_rb_entry *wine_rb_head(struct wine_rb_entry *iter)
104{
105 if (!iter) return NULL;
106 while (iter->left) iter = iter->left;
107 return iter;
108}
109
110static inline struct wine_rb_entry *wine_rb_tail(struct wine_rb_entry *iter)
111{
112 if (!iter) return NULL;
113 while (iter->right) iter = iter->right;
114 return iter;
115}
116
117static inline struct wine_rb_entry *wine_rb_next(struct wine_rb_entry *iter)
118{
119 if (iter->right) return wine_rb_head(iter->right);
120 while (iter->parent && iter->parent->right == iter) iter = iter->parent;
121 return iter->parent;
122}
123
124static inline struct wine_rb_entry *wine_rb_prev(struct wine_rb_entry *iter)
125{
126 if (iter->left) return wine_rb_tail(iter->left);
127 while (iter->parent && iter->parent->left == iter) iter = iter->parent;
128 return iter->parent;
129}
130
131static inline struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter)
132{
133 if (!iter) return NULL;
134
135 for (;;) {
136 while (iter->left) iter = iter->left;
137 if (!iter->right) return iter;
138 iter = iter->right;
139 }
140}
141
142static inline struct wine_rb_entry *wine_rb_postorder_next(struct wine_rb_entry *iter)
143{
144 if (!iter->parent) return NULL;
145 if (iter == iter->parent->right || !iter->parent->right) return iter->parent;
146 return wine_rb_postorder_head(iter->parent->right);
147}
148
149/* iterate through the tree */
150#define WINE_RB_FOR_EACH(cursor, tree) \
151 for ((cursor) = wine_rb_head((tree)->root); (cursor); (cursor) = wine_rb_next(cursor))
152
153/* iterate through the tree using a tree entry */
154#define WINE_RB_FOR_EACH_ENTRY(elem, tree, type, field) \
155 for ((elem) = WINE_RB_ENTRY_VALUE(wine_rb_head((tree)->root), type, field); \
156 (elem) != WINE_RB_ENTRY_VALUE(0, type, field); \
157 (elem) = WINE_RB_ENTRY_VALUE(wine_rb_next(&elem->field), type, field))
158
159/* iterate through the tree using using postorder, making it safe to free the entry */
160#define WINE_RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree) \
161 for ((cursor) = wine_rb_postorder_head((tree)->root); \
162 (cursor) && (((cursor2) = wine_rb_postorder_next(cursor)) || 1); \
163 (cursor) = (cursor2))
164
165/* iterate through the tree using a tree entry and postorder, making it safe to free the entry */
166#define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR(elem, elem2, tree, type, field) \
167 for ((elem) = WINE_RB_ENTRY_VALUE(wine_rb_postorder_head((tree)->root), type, field); \
168 (elem) != WINE_RB_ENTRY_VALUE(0, type, field) \
169 && (((elem2) = WINE_RB_ENTRY_VALUE(wine_rb_postorder_next(&(elem)->field), type, field)) || 1); \
170 (elem) = (elem2))
171
172
174{
175 struct wine_rb_entry *iter, *next;
177}
178
180{
181 tree->compare = compare;
182 tree->root = NULL;
183}
184
186{
187 struct wine_rb_entry *iter;
189}
190
192{
193 /* Note that we use postorder here because the callback will likely free the entry. */
195 tree->root = NULL;
196}
197
199{
201}
202
203static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)
204{
205 struct wine_rb_entry *entry = tree->root;
206 while (entry)
207 {
208 int c = tree->compare(key, entry);
209 if (!c) return entry;
210 entry = c < 0 ? entry->left : entry->right;
211 }
212 return NULL;
213}
214
215static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
216{
217 struct wine_rb_entry **iter = &tree->root, *parent = tree->root;
218
219 while (*iter)
220 {
221 int c;
222
223 parent = *iter;
224 c = tree->compare(key, parent);
225 if (!c) return -1;
226 else if (c < 0) iter = &parent->left;
227 else iter = &parent->right;
228 }
229
230 entry->flags = WINE_RB_FLAG_RED;
231 entry->parent = parent;
232 entry->left = NULL;
233 entry->right = NULL;
234 *iter = entry;
235
236 while (wine_rb_is_red(entry->parent))
237 {
238 if (entry->parent == entry->parent->parent->left)
239 {
240 if (wine_rb_is_red(entry->parent->parent->right))
241 {
242 wine_rb_flip_color(entry->parent->parent);
243 entry = entry->parent->parent;
244 }
245 else
246 {
247 if (entry == entry->parent->right)
248 {
249 entry = entry->parent;
251 }
252 entry->parent->flags &= ~WINE_RB_FLAG_RED;
253 entry->parent->parent->flags |= WINE_RB_FLAG_RED;
254 wine_rb_rotate_right(tree, entry->parent->parent);
255 }
256 }
257 else
258 {
259 if (wine_rb_is_red(entry->parent->parent->left))
260 {
261 wine_rb_flip_color(entry->parent->parent);
262 entry = entry->parent->parent;
263 }
264 else
265 {
266 if (entry == entry->parent->left)
267 {
268 entry = entry->parent;
270 }
271 entry->parent->flags &= ~WINE_RB_FLAG_RED;
272 entry->parent->parent->flags |= WINE_RB_FLAG_RED;
273 wine_rb_rotate_left(tree, entry->parent->parent);
274 }
275 }
276 }
277
278 tree->root->flags &= ~WINE_RB_FLAG_RED;
279
280 return 0;
281}
282
283static inline void wine_rb_remove(struct wine_rb_tree *tree, struct wine_rb_entry *entry)
284{
285 struct wine_rb_entry *iter, *child, *parent, *w;
286 int need_fixup;
287
288 if (entry->right && entry->left)
289 for(iter = entry->right; iter->left; iter = iter->left);
290 else
291 iter = entry;
292
293 child = iter->left ? iter->left : iter->right;
294
295 if (!iter->parent)
296 tree->root = child;
297 else if (iter == iter->parent->left)
298 iter->parent->left = child;
299 else
300 iter->parent->right = child;
301
302 if (child) child->parent = iter->parent;
303 parent = iter->parent;
304
305 need_fixup = !wine_rb_is_red(iter);
306
307 if (entry != iter)
308 {
309 *iter = *entry;
310 if (!iter->parent)
311 tree->root = iter;
312 else if (entry == iter->parent->left)
313 iter->parent->left = iter;
314 else
315 iter->parent->right = iter;
316
317 if (iter->right) iter->right->parent = iter;
318 if (iter->left) iter->left->parent = iter;
319 if (parent == entry) parent = iter;
320 }
321
322 if (need_fixup)
323 {
324 while (parent && !wine_rb_is_red(child))
325 {
326 if (child == parent->left)
327 {
328 w = parent->right;
329 if (wine_rb_is_red(w))
330 {
331 w->flags &= ~WINE_RB_FLAG_RED;
332 parent->flags |= WINE_RB_FLAG_RED;
334 w = parent->right;
335 }
336 if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
337 {
338 if (!wine_rb_is_red(w->right))
339 {
340 w->left->flags &= ~WINE_RB_FLAG_RED;
341 w->flags |= WINE_RB_FLAG_RED;
343 w = parent->right;
344 }
345 w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
346 parent->flags &= ~WINE_RB_FLAG_RED;
347 if (w->right)
348 w->right->flags &= ~WINE_RB_FLAG_RED;
350 child = NULL;
351 break;
352 }
353 }
354 else
355 {
356 w = parent->left;
357 if (wine_rb_is_red(w))
358 {
359 w->flags &= ~WINE_RB_FLAG_RED;
360 parent->flags |= WINE_RB_FLAG_RED;
362 w = parent->left;
363 }
364 if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
365 {
366 if (!wine_rb_is_red(w->left))
367 {
368 w->right->flags &= ~WINE_RB_FLAG_RED;
369 w->flags |= WINE_RB_FLAG_RED;
371 w = parent->left;
372 }
373 w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
374 parent->flags &= ~WINE_RB_FLAG_RED;
375 if (w->left)
376 w->left->flags &= ~WINE_RB_FLAG_RED;
378 child = NULL;
379 break;
380 }
381 }
382 w->flags |= WINE_RB_FLAG_RED;
383 child = parent;
384 parent = child->parent;
385 }
386 if (child) child->flags &= ~WINE_RB_FLAG_RED;
387 }
388
389 if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
390}
391
392static inline void wine_rb_remove_key(struct wine_rb_tree *tree, const void *key)
393{
396}
397
398#endif /* __WINE_WINE_RBTREE_H */
#define compare
#define NULL
Definition: types.h:112
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
r parent
Definition: btrfs.c:3010
const GLubyte * c
Definition: glext.h:8905
GLdouble GLdouble right
Definition: glext.h:10859
GLint left
Definition: glext.h:7726
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
uint32_t entry
Definition: isohybrid.c:63
#define e
Definition: ke_i.h:82
#define c
Definition: ke_i.h:80
static IPrintDialogCallback callback
Definition: printdlg.c:326
static HWND child
Definition: cursoricon.c:298
static unsigned __int64 next
Definition: rand_nt.c:6
static void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:173
static void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:198
static void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:185
#define WINE_RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
Definition: rbtree.h:160
static struct wine_rb_entry * wine_rb_prev(struct wine_rb_entry *iter)
Definition: rbtree.h:124
static struct wine_rb_entry * wine_rb_postorder_next(struct wine_rb_entry *iter)
Definition: rbtree.h:142
static void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e)
Definition: rbtree.h:78
static struct wine_rb_entry * wine_rb_get(const struct wine_rb_tree *tree, const void *key)
Definition: rbtree.h:203
static void wine_rb_remove(struct wine_rb_tree *tree, struct wine_rb_entry *entry)
Definition: rbtree.h:283
int(* wine_rb_compare_func_t)(const void *key, const struct wine_rb_entry *entry)
Definition: rbtree.h:43
#define WINE_RB_FLAG_RED
Definition: rbtree.h:53
static struct wine_rb_entry * wine_rb_head(struct wine_rb_entry *iter)
Definition: rbtree.h:103
void() wine_rb_traverse_func_t(struct wine_rb_entry *entry, void *context)
Definition: rbtree.h:51
static void wine_rb_remove_key(struct wine_rb_tree *tree, const void *key)
Definition: rbtree.h:392
static struct wine_rb_entry * wine_rb_tail(struct wine_rb_entry *iter)
Definition: rbtree.h:110
static struct wine_rb_entry * wine_rb_postorder_head(struct wine_rb_entry *iter)
Definition: rbtree.h:131
static void wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t compare)
Definition: rbtree.h:179
static void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:191
static struct wine_rb_entry * wine_rb_next(struct wine_rb_entry *iter)
Definition: rbtree.h:117
static int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
Definition: rbtree.h:215
static int wine_rb_is_red(struct wine_rb_entry *entry)
Definition: rbtree.h:55
#define WINE_RB_FOR_EACH(cursor, tree)
Definition: rbtree.h:150
static void wine_rb_flip_color(struct wine_rb_entry *entry)
Definition: rbtree.h:96
static void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
Definition: rbtree.h:60
struct _root * root
Definition: btrfs_drv.h:433
Definition: bug.cpp:8
Definition: http.c:7252
Definition: copy.c:22
Definition: rbtree.h:36
unsigned int flags
Definition: rbtree.h:40
struct wine_rb_entry * left
Definition: rbtree.h:38
struct wine_rb_entry * right
Definition: rbtree.h:39
struct wine_rb_entry * parent
Definition: rbtree.h:37
struct wine_rb_entry * root
Definition: rbtree.h:48
wine_rb_compare_func_t compare
Definition: rbtree.h:47