ReactOS 0.4.16-dev-1360-g66b782d
rbtree.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  rb_entry
 
struct  rb_tree
 

Macros

#define RB_ENTRY_VALUE(element, type, field)    ((type *)((char *)(element) - offsetof(type, field)))
 
#define RB_FLAG_RED   0x1
 
#define RB_FOR_EACH(cursor, tree)    for ((cursor) = rb_head((tree)->root); (cursor); (cursor) = rb_next(cursor))
 
#define RB_FOR_EACH_ENTRY(elem, tree, type, field)
 
#define RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
 
#define RB_FOR_EACH_ENTRY_DESTRUCTOR(elem, elem2, tree, type, field)
 
#define wine_rb_entry   rb_entry
 
#define wine_rb_tree   rb_tree
 
#define wine_rb_init   rb_init
 
#define wine_rb_for_each_entry   rb_for_each_entry
 
#define wine_rb_destroy   rb_destroy
 
#define wine_rb_get   rb_get
 
#define wine_rb_put   rb_put
 
#define wine_rb_remove   rb_remove
 
#define wine_rb_remove_key   rb_remove_key
 
#define wine_rb_replace   rb_replace
 
#define WINE_RB_ENTRY_VALUE   RB_ENTRY_VALUE
 
#define WINE_RB_FOR_EACH_ENTRY   RB_FOR_EACH_ENTRY
 
#define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR   RB_FOR_EACH_ENTRY_DESTRUCTOR
 

Typedefs

typedef int(* rb_compare_func_t) (const void *key, const struct rb_entry *entry)
 
typedef void() rb_traverse_func_t(struct rb_entry *entry, void *context)
 

Functions

static int rb_is_red (struct rb_entry *entry)
 
static void rb_rotate_left (struct rb_tree *tree, struct rb_entry *e)
 
static void rb_rotate_right (struct rb_tree *tree, struct rb_entry *e)
 
static void rb_flip_color (struct rb_entry *entry)
 
static struct rb_entryrb_head (struct rb_entry *iter)
 
static struct rb_entryrb_tail (struct rb_entry *iter)
 
static struct rb_entryrb_next (struct rb_entry *iter)
 
static struct rb_entryrb_prev (struct rb_entry *iter)
 
static struct rb_entryrb_postorder_head (struct rb_entry *iter)
 
static struct rb_entryrb_postorder_next (struct rb_entry *iter)
 
static void rb_postorder (struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
 
static void rb_init (struct rb_tree *tree, rb_compare_func_t compare)
 
static void rb_for_each_entry (struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
 
static void rb_destroy (struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
 
static struct rb_entryrb_get (const struct rb_tree *tree, const void *key)
 
static int rb_put (struct rb_tree *tree, const void *key, struct rb_entry *entry)
 
static void rb_remove (struct rb_tree *tree, struct rb_entry *entry)
 
static void rb_remove_key (struct rb_tree *tree, const void *key)
 
static void rb_replace (struct rb_tree *tree, struct rb_entry *dst, struct rb_entry *src)
 

Macro Definition Documentation

◆ RB_ENTRY_VALUE

#define RB_ENTRY_VALUE (   element,
  type,
  field 
)     ((type *)((char *)(element) - offsetof(type, field)))

Definition at line 26 of file rbtree.h.

◆ RB_FLAG_RED

#define RB_FLAG_RED   0x1

Definition at line 47 of file rbtree.h.

◆ RB_FOR_EACH

#define RB_FOR_EACH (   cursor,
  tree 
)     for ((cursor) = rb_head((tree)->root); (cursor); (cursor) = rb_next(cursor))

Definition at line 144 of file rbtree.h.

◆ RB_FOR_EACH_DESTRUCTOR

#define RB_FOR_EACH_DESTRUCTOR (   cursor,
  cursor2,
  tree 
)
Value:
(cursor) && (((cursor2) = rb_postorder_next(cursor)) || 1); \
(cursor) = (cursor2))
const char cursor[]
Definition: icontest.c:13
static struct rb_entry * rb_postorder_next(struct rb_entry *iter)
Definition: rbtree.h:136
static struct rb_entry * rb_postorder_head(struct rb_entry *iter)
Definition: rbtree.h:125

Definition at line 154 of file rbtree.h.

◆ RB_FOR_EACH_ENTRY

#define RB_FOR_EACH_ENTRY (   elem,
  tree,
  type,
  field 
)
Value:
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
static size_t elem
Definition: string.c:71
#define RB_ENTRY_VALUE(element, type, field)
Definition: rbtree.h:26
static struct rb_entry * rb_head(struct rb_entry *iter)
Definition: rbtree.h:97
static struct rb_entry * rb_next(struct rb_entry *iter)
Definition: rbtree.h:111
Definition: parser.c:44

Definition at line 148 of file rbtree.h.

◆ RB_FOR_EACH_ENTRY_DESTRUCTOR

#define RB_FOR_EACH_ENTRY_DESTRUCTOR (   elem,
  elem2,
  tree,
  type,
  field 
)
Value:
&& (((elem2) = RB_ENTRY_VALUE(rb_postorder_next(&(elem)->field), type, field)) || 1); \
(elem) = (elem2))

Definition at line 160 of file rbtree.h.

◆ wine_rb_destroy

#define wine_rb_destroy   rb_destroy

Definition at line 408 of file rbtree.h.

◆ wine_rb_entry

#define wine_rb_entry   rb_entry

Definition at line 404 of file rbtree.h.

◆ WINE_RB_ENTRY_VALUE

#define WINE_RB_ENTRY_VALUE   RB_ENTRY_VALUE

Definition at line 414 of file rbtree.h.

◆ wine_rb_for_each_entry

#define wine_rb_for_each_entry   rb_for_each_entry

Definition at line 407 of file rbtree.h.

◆ WINE_RB_FOR_EACH_ENTRY

#define WINE_RB_FOR_EACH_ENTRY   RB_FOR_EACH_ENTRY

Definition at line 415 of file rbtree.h.

◆ WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR

#define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR   RB_FOR_EACH_ENTRY_DESTRUCTOR

Definition at line 416 of file rbtree.h.

◆ wine_rb_get

#define wine_rb_get   rb_get

Definition at line 409 of file rbtree.h.

◆ wine_rb_init

#define wine_rb_init   rb_init

Definition at line 406 of file rbtree.h.

◆ wine_rb_put

#define wine_rb_put   rb_put

Definition at line 410 of file rbtree.h.

◆ wine_rb_remove

#define wine_rb_remove   rb_remove

Definition at line 411 of file rbtree.h.

◆ wine_rb_remove_key

#define wine_rb_remove_key   rb_remove_key

Definition at line 412 of file rbtree.h.

◆ wine_rb_replace

#define wine_rb_replace   rb_replace

Definition at line 413 of file rbtree.h.

◆ wine_rb_tree

#define wine_rb_tree   rb_tree

Definition at line 405 of file rbtree.h.

Typedef Documentation

◆ rb_compare_func_t

typedef int(* rb_compare_func_t) (const void *key, const struct rb_entry *entry)

Definition at line 37 of file rbtree.h.

◆ rb_traverse_func_t

typedef void() rb_traverse_func_t(struct rb_entry *entry, void *context)

Definition at line 45 of file rbtree.h.

Function Documentation

◆ rb_destroy()

static void rb_destroy ( struct rb_tree tree,
rb_traverse_func_t callback,
void context 
)
inlinestatic

Definition at line 185 of file rbtree.h.

186{
187 /* Note that we use postorder here because the callback will likely free the entry. */
189 tree->root = NULL;
190}
#define NULL
Definition: types.h:112
static IPrintDialogCallback callback
Definition: printdlg.c:326
static void rb_postorder(struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:167
struct _root * root
Definition: btrfs_drv.h:433
Definition: http.c:7252

◆ rb_flip_color()

static void rb_flip_color ( struct rb_entry entry)
inlinestatic

Definition at line 90 of file rbtree.h.

91{
92 entry->flags ^= RB_FLAG_RED;
93 entry->left->flags ^= RB_FLAG_RED;
94 entry->right->flags ^= RB_FLAG_RED;
95}
uint32_t entry
Definition: isohybrid.c:63
#define RB_FLAG_RED
Definition: rbtree.h:47

Referenced by rb_put().

◆ rb_for_each_entry()

static void rb_for_each_entry ( struct rb_tree tree,
rb_traverse_func_t callback,
void context 
)
inlinestatic

Definition at line 179 of file rbtree.h.

180{
181 struct rb_entry *iter;
182 RB_FOR_EACH(iter, tree) callback(iter, context);
183}
#define RB_FOR_EACH(cursor, tree)
Definition: rbtree.h:144
Definition: rbtree.h:30

◆ rb_get()

static struct rb_entry * rb_get ( const struct rb_tree tree,
const void key 
)
inlinestatic

Definition at line 192 of file rbtree.h.

193{
194 struct rb_entry *entry = tree->root;
195 while (entry)
196 {
197 int c = tree->compare(key, entry);
198 if (!c) return entry;
199 entry = c < 0 ? entry->left : entry->right;
200 }
201 return NULL;
202}
const GLubyte * c
Definition: glext.h:8905
Definition: copy.c:22

Referenced by rb_remove_key().

◆ rb_head()

static struct rb_entry * rb_head ( struct rb_entry iter)
inlinestatic

Definition at line 97 of file rbtree.h.

98{
99 if (!iter) return NULL;
100 while (iter->left) iter = iter->left;
101 return iter;
102}
struct rb_entry * left
Definition: rbtree.h:32

Referenced by rb_next(), and wrap_marked_paras_dc().

◆ rb_init()

static void rb_init ( struct rb_tree tree,
rb_compare_func_t  compare 
)
inlinestatic

Definition at line 173 of file rbtree.h.

174{
175 tree->compare = compare;
176 tree->root = NULL;
177}
#define compare

◆ rb_is_red()

static int rb_is_red ( struct rb_entry entry)
inlinestatic

Definition at line 49 of file rbtree.h.

50{
51 return entry && (entry->flags & RB_FLAG_RED);
52}

◆ rb_next()

static struct rb_entry * rb_next ( struct rb_entry iter)
inlinestatic

Definition at line 111 of file rbtree.h.

112{
113 if (iter->right) return rb_head(iter->right);
114 while (iter->parent && iter->parent->right == iter) iter = iter->parent;
115 return iter->parent;
116}
struct rb_entry * right
Definition: rbtree.h:33
struct rb_entry * parent
Definition: rbtree.h:31

◆ rb_postorder()

static void rb_postorder ( struct rb_tree tree,
rb_traverse_func_t callback,
void context 
)
inlinestatic

Definition at line 167 of file rbtree.h.

168{
169 struct rb_entry *iter, *next;
171}
static unsigned __int64 next
Definition: rand_nt.c:6
#define RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
Definition: rbtree.h:154

Referenced by rb_destroy().

◆ rb_postorder_head()

static struct rb_entry * rb_postorder_head ( struct rb_entry iter)
inlinestatic

Definition at line 125 of file rbtree.h.

126{
127 if (!iter) return NULL;
128
129 for (;;) {
130 while (iter->left) iter = iter->left;
131 if (!iter->right) return iter;
132 iter = iter->right;
133 }
134}

Referenced by rb_postorder_next().

◆ rb_postorder_next()

static struct rb_entry * rb_postorder_next ( struct rb_entry iter)
inlinestatic

Definition at line 136 of file rbtree.h.

137{
138 if (!iter->parent) return NULL;
139 if (iter == iter->parent->right || !iter->parent->right) return iter->parent;
140 return rb_postorder_head(iter->parent->right);
141}

◆ rb_prev()

static struct rb_entry * rb_prev ( struct rb_entry iter)
inlinestatic

Definition at line 118 of file rbtree.h.

119{
120 if (iter->left) return rb_tail(iter->left);
121 while (iter->parent && iter->parent->left == iter) iter = iter->parent;
122 return iter->parent;
123}
static struct rb_entry * rb_tail(struct rb_entry *iter)
Definition: rbtree.h:104

◆ rb_put()

static int rb_put ( struct rb_tree tree,
const void key,
struct rb_entry entry 
)
inlinestatic

Definition at line 204 of file rbtree.h.

205{
206 struct rb_entry **iter = &tree->root, *parent = tree->root;
207
208 while (*iter)
209 {
210 int c;
211
212 parent = *iter;
213 c = tree->compare(key, parent);
214 if (!c) return -1;
215 else if (c < 0) iter = &parent->left;
216 else iter = &parent->right;
217 }
218
219 entry->flags = RB_FLAG_RED;
220 entry->parent = parent;
221 entry->left = NULL;
222 entry->right = NULL;
223 *iter = entry;
224
225 while (rb_is_red(entry->parent))
226 {
227 if (entry->parent == entry->parent->parent->left)
228 {
229 if (rb_is_red(entry->parent->parent->right))
230 {
231 rb_flip_color(entry->parent->parent);
232 entry = entry->parent->parent;
233 }
234 else
235 {
236 if (entry == entry->parent->right)
237 {
238 entry = entry->parent;
240 }
241 entry->parent->flags &= ~RB_FLAG_RED;
242 entry->parent->parent->flags |= RB_FLAG_RED;
243 rb_rotate_right(tree, entry->parent->parent);
244 }
245 }
246 else
247 {
248 if (rb_is_red(entry->parent->parent->left))
249 {
250 rb_flip_color(entry->parent->parent);
251 entry = entry->parent->parent;
252 }
253 else
254 {
255 if (entry == entry->parent->left)
256 {
257 entry = entry->parent;
259 }
260 entry->parent->flags &= ~RB_FLAG_RED;
261 entry->parent->parent->flags |= RB_FLAG_RED;
262 rb_rotate_left(tree, entry->parent->parent);
263 }
264 }
265 }
266
267 tree->root->flags &= ~RB_FLAG_RED;
268
269 return 0;
270}
r parent
Definition: btrfs.c:3010
#define rb_is_red(r)
Definition: rbtree.h:115
#define c
Definition: ke_i.h:80
static void rb_rotate_right(struct rb_tree *tree, struct rb_entry *e)
Definition: rbtree.h:72
static void rb_rotate_left(struct rb_tree *tree, struct rb_entry *e)
Definition: rbtree.h:54
static void rb_flip_color(struct rb_entry *entry)
Definition: rbtree.h:90

◆ rb_remove()

static void rb_remove ( struct rb_tree tree,
struct rb_entry entry 
)
inlinestatic

Definition at line 272 of file rbtree.h.

273{
274 struct rb_entry *iter, *child, *parent, *w;
275 int need_fixup;
276
277 if (entry->right && entry->left)
278 for(iter = entry->right; iter->left; iter = iter->left);
279 else
280 iter = entry;
281
282 child = iter->left ? iter->left : iter->right;
283
284 if (!iter->parent)
285 tree->root = child;
286 else if (iter == iter->parent->left)
287 iter->parent->left = child;
288 else
289 iter->parent->right = child;
290
291 if (child) child->parent = iter->parent;
292 parent = iter->parent;
293
294 need_fixup = !rb_is_red(iter);
295
296 if (entry != iter)
297 {
298 *iter = *entry;
299 if (!iter->parent)
300 tree->root = iter;
301 else if (entry == iter->parent->left)
302 iter->parent->left = iter;
303 else
304 iter->parent->right = iter;
305
306 if (iter->right) iter->right->parent = iter;
307 if (iter->left) iter->left->parent = iter;
308 if (parent == entry) parent = iter;
309 }
310
311 if (need_fixup)
312 {
313 while (parent && !rb_is_red(child))
314 {
315 if (child == parent->left)
316 {
317 w = parent->right;
318 if (rb_is_red(w))
319 {
320 w->flags &= ~RB_FLAG_RED;
321 parent->flags |= RB_FLAG_RED;
323 w = parent->right;
324 }
325 if (rb_is_red(w->left) || rb_is_red(w->right))
326 {
327 if (!rb_is_red(w->right))
328 {
329 w->left->flags &= ~RB_FLAG_RED;
330 w->flags |= RB_FLAG_RED;
332 w = parent->right;
333 }
334 w->flags = (w->flags & ~RB_FLAG_RED) | (parent->flags & RB_FLAG_RED);
335 parent->flags &= ~RB_FLAG_RED;
336 if (w->right)
337 w->right->flags &= ~RB_FLAG_RED;
339 child = NULL;
340 break;
341 }
342 }
343 else
344 {
345 w = parent->left;
346 if (rb_is_red(w))
347 {
348 w->flags &= ~RB_FLAG_RED;
349 parent->flags |= RB_FLAG_RED;
351 w = parent->left;
352 }
353 if (rb_is_red(w->left) || rb_is_red(w->right))
354 {
355 if (!rb_is_red(w->left))
356 {
357 w->right->flags &= ~RB_FLAG_RED;
358 w->flags |= RB_FLAG_RED;
360 w = parent->left;
361 }
362 w->flags = (w->flags & ~RB_FLAG_RED) | (parent->flags & RB_FLAG_RED);
363 parent->flags &= ~RB_FLAG_RED;
364 if (w->left)
365 w->left->flags &= ~RB_FLAG_RED;
367 child = NULL;
368 break;
369 }
370 }
371 w->flags |= RB_FLAG_RED;
372 child = parent;
373 parent = child->parent;
374 }
375 if (child) child->flags &= ~RB_FLAG_RED;
376 }
377
378 if (tree->root) tree->root->flags &= ~RB_FLAG_RED;
379}
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
static HWND child
Definition: cursoricon.c:298

Referenced by rb_remove_key().

◆ rb_remove_key()

static void rb_remove_key ( struct rb_tree tree,
const void key 
)
inlinestatic

Definition at line 381 of file rbtree.h.

382{
383 struct rb_entry *entry = rb_get(tree, key);
384 if (entry) rb_remove(tree, entry);
385}
static struct rb_entry * rb_get(const struct rb_tree *tree, const void *key)
Definition: rbtree.h:192
static void rb_remove(struct rb_tree *tree, struct rb_entry *entry)
Definition: rbtree.h:272

◆ rb_replace()

static void rb_replace ( struct rb_tree tree,
struct rb_entry dst,
struct rb_entry src 
)
inlinestatic

Definition at line 387 of file rbtree.h.

388{
389 if (!(src->parent = dst->parent))
390 tree->root = src;
391 else if (dst->parent->left == dst)
392 dst->parent->left = src;
393 else
394 dst->parent->right = src;
395
396 if ((src->left = dst->left))
397 src->left->parent = src;
398 if ((src->right = dst->right))
399 src->right->parent = src;
400 src->flags = dst->flags;
401}
GLenum src
Definition: glext.h:6340
GLenum GLenum dst
Definition: glext.h:6340

◆ rb_rotate_left()

static void rb_rotate_left ( struct rb_tree tree,
struct rb_entry e 
)
inlinestatic

Definition at line 54 of file rbtree.h.

55{
56 struct rb_entry *right = e->right;
57
58 if (!e->parent)
59 tree->root = right;
60 else if (e->parent->left == e)
61 e->parent->left = right;
62 else
63 e->parent->right = right;
64
65 e->right = right->left;
66 if (e->right) e->right->parent = e;
67 right->left = e;
68 right->parent = e->parent;
69 e->parent = right;
70}
GLdouble GLdouble right
Definition: glext.h:10859
#define e
Definition: ke_i.h:82

Referenced by rb_put(), and rb_remove().

◆ rb_rotate_right()

static void rb_rotate_right ( struct rb_tree tree,
struct rb_entry e 
)
inlinestatic

Definition at line 72 of file rbtree.h.

73{
74 struct rb_entry *left = e->left;
75
76 if (!e->parent)
77 tree->root = left;
78 else if (e->parent->left == e)
79 e->parent->left = left;
80 else
81 e->parent->right = left;
82
83 e->left = left->right;
84 if (e->left) e->left->parent = e;
85 left->right = e;
86 left->parent = e->parent;
87 e->parent = left;
88}
GLint left
Definition: glext.h:7726

Referenced by rb_put(), and rb_remove().

◆ rb_tail()

static struct rb_entry * rb_tail ( struct rb_entry iter)
inlinestatic

Definition at line 104 of file rbtree.h.

105{
106 if (!iter) return NULL;
107 while (iter->right) iter = iter->right;
108 return iter;
109}

Referenced by rb_prev().