Go to the source code of this file.
|
#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 |
|
|
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_entry * | rb_head (struct rb_entry *iter) |
|
static struct rb_entry * | rb_tail (struct rb_entry *iter) |
|
static struct rb_entry * | rb_next (struct rb_entry *iter) |
|
static struct rb_entry * | rb_prev (struct rb_entry *iter) |
|
static struct rb_entry * | rb_postorder_head (struct rb_entry *iter) |
|
static struct rb_entry * | rb_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_entry * | rb_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) |
|
◆ RB_ENTRY_VALUE
◆ RB_FLAG_RED
◆ RB_FOR_EACH
◆ RB_FOR_EACH_DESTRUCTOR
Value:
static struct rb_entry * rb_postorder_next(struct rb_entry *iter)
static struct rb_entry * rb_postorder_head(struct rb_entry *iter)
Definition at line 154 of file rbtree.h.
◆ RB_FOR_EACH_ENTRY
Value:
GLuint GLuint GLsizei GLenum type
#define RB_ENTRY_VALUE(element, type, field)
static struct rb_entry * rb_head(struct rb_entry *iter)
static struct rb_entry * rb_next(struct rb_entry *iter)
Definition at line 148 of file rbtree.h.
◆ RB_FOR_EACH_ENTRY_DESTRUCTOR
◆ wine_rb_destroy
◆ wine_rb_entry
◆ WINE_RB_ENTRY_VALUE
◆ wine_rb_for_each_entry
◆ WINE_RB_FOR_EACH_ENTRY
◆ WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR
◆ wine_rb_get
◆ wine_rb_init
◆ wine_rb_put
◆ wine_rb_remove
◆ wine_rb_remove_key
◆ wine_rb_replace
◆ wine_rb_tree
◆ rb_compare_func_t
◆ rb_traverse_func_t
◆ rb_destroy()
Definition at line 185 of file rbtree.h.
186{
187
190}
static IPrintDialogCallback callback
static void rb_postorder(struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
◆ rb_flip_color()
◆ rb_for_each_entry()
Definition at line 179 of file rbtree.h.
180{
183}
#define RB_FOR_EACH(cursor, tree)
◆ rb_get()
◆ rb_head()
◆ rb_init()
◆ rb_is_red()
◆ rb_next()
◆ rb_postorder()
Definition at line 167 of file rbtree.h.
168{
171}
static unsigned __int64 next
#define RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
Referenced by rb_destroy().
◆ rb_postorder_head()
◆ rb_postorder_next()
◆ rb_prev()
Definition at line 118 of file rbtree.h.
119{
123}
static struct rb_entry * rb_tail(struct rb_entry *iter)
◆ rb_put()
Definition at line 204 of file rbtree.h.
205{
207
208 while (*iter)
209 {
211
215 else if (
c < 0) iter = &
parent->left;
216 else iter = &
parent->right;
217 }
218
224
226 {
227 if (
entry->parent ==
entry->parent->parent->left)
228 {
230 {
233 }
234 else
235 {
237 {
240 }
241 entry->parent->flags &= ~RB_FLAG_RED;
244 }
245 }
246 else
247 {
249 {
252 }
253 else
254 {
256 {
259 }
260 entry->parent->flags &= ~RB_FLAG_RED;
263 }
264 }
265 }
266
268
269 return 0;
270}
static void rb_rotate_right(struct rb_tree *tree, struct rb_entry *e)
static void rb_rotate_left(struct rb_tree *tree, struct rb_entry *e)
static void rb_flip_color(struct rb_entry *entry)
◆ rb_remove()
Definition at line 272 of file rbtree.h.
273{
275 int need_fixup;
276
279 else
281
283
286 else if (iter == iter->
parent->left)
288 else
290
293
295
297 {
302 iter->
parent->left = iter;
303 else
304 iter->
parent->right = iter;
305
307 if (iter->
left) iter->
left->parent = iter;
309 }
310
311 if (need_fixup)
312 {
314 {
316 {
319 {
320 w->flags &= ~RB_FLAG_RED;
324 }
326 {
328 {
329 w->left->flags &= ~RB_FLAG_RED;
333 }
335 parent->flags &= ~RB_FLAG_RED;
337 w->right->flags &= ~RB_FLAG_RED;
340 break;
341 }
342 }
343 else
344 {
347 {
348 w->flags &= ~RB_FLAG_RED;
352 }
354 {
356 {
357 w->right->flags &= ~RB_FLAG_RED;
361 }
363 parent->flags &= ~RB_FLAG_RED;
365 w->left->flags &= ~RB_FLAG_RED;
368 break;
369 }
370 }
374 }
376 }
377
379}
GLubyte GLubyte GLubyte GLubyte w
Referenced by rb_remove_key().
◆ rb_remove_key()
Definition at line 381 of file rbtree.h.
382{
385}
static struct rb_entry * rb_get(const struct rb_tree *tree, const void *key)
static void rb_remove(struct rb_tree *tree, struct rb_entry *entry)
◆ rb_replace()
Definition at line 387 of file rbtree.h.
388{
389 if (!(
src->parent =
dst->parent))
391 else if (
dst->parent->left ==
dst)
393 else
395
396 if ((
src->left =
dst->left))
398 if ((
src->right =
dst->right))
401}
◆ rb_rotate_left()
Definition at line 54 of file rbtree.h.
55{
57
60 else if (
e->parent->left ==
e)
62 else
64
66 if (
e->right)
e->right->parent =
e;
70}
Referenced by rb_put(), and rb_remove().
◆ rb_rotate_right()
Definition at line 72 of file rbtree.h.
73{
75
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;
86 left->parent =
e->parent;
88}
Referenced by rb_put(), and rb_remove().
◆ rb_tail()
Definition at line 104 of file rbtree.h.
105{
106 if (!iter)
return NULL;
108 return iter;
109}
Referenced by rb_prev().