23#ifndef __WINE_WINE_RBTREE_H
24#define __WINE_WINE_RBTREE_H
27# define WINE_RB_ENTRY_VALUE(element, type, field) ({ \
28 const typeof(((type *)0)->field) *__ptr = (element); \
29 (type *)((char *)__ptr - offsetof(type, field)); })
31# define WINE_RB_ENTRY_VALUE(element, type, field) \
32 ((type *)((char *)(element) - offsetof(type, field)))
53#define WINE_RB_FLAG_RED 0x1
66 else if (
e->parent->left ==
e)
72 if (
e->right)
e->right->parent =
e;
84 else if (
e->parent->left ==
e)
85 e->parent->left =
left;
87 e->parent->right =
left;
89 e->left =
left->right;
90 if (
e->left)
e->left->parent =
e;
92 left->parent =
e->parent;
105 if (!iter)
return NULL;
106 while (iter->
left) iter = iter->
left;
112 if (!iter)
return NULL;
133 if (!iter)
return NULL;
136 while (iter->
left) iter = iter->
left;
137 if (!iter->
right)
return iter;
150#define WINE_RB_FOR_EACH(cursor, tree) \
151 for ((cursor) = wine_rb_head((tree)->root); (cursor); (cursor) = wine_rb_next(cursor))
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))
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))
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); \
226 else if (
c < 0) iter = &
parent->left;
227 else iter = &
parent->right;
238 if (
entry->parent ==
entry->parent->parent->left)
252 entry->parent->flags &= ~WINE_RB_FLAG_RED;
271 entry->parent->flags &= ~WINE_RB_FLAG_RED;
278 tree->
root->flags &= ~WINE_RB_FLAG_RED;
297 else if (iter == iter->
parent->left)
313 iter->
parent->left = iter;
315 iter->
parent->right = iter;
318 if (iter->
left) iter->
left->parent = iter;
331 w->flags &= ~WINE_RB_FLAG_RED;
340 w->left->flags &= ~WINE_RB_FLAG_RED;
346 parent->flags &= ~WINE_RB_FLAG_RED;
348 w->right->flags &= ~WINE_RB_FLAG_RED;
359 w->flags &= ~WINE_RB_FLAG_RED;
368 w->right->flags &= ~WINE_RB_FLAG_RED;
374 parent->flags &= ~WINE_RB_FLAG_RED;
376 w->left->flags &= ~WINE_RB_FLAG_RED;
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
GLubyte GLubyte GLubyte GLubyte w
static IPrintDialogCallback callback
static unsigned __int64 next
static void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
static void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
static void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
#define WINE_RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
static struct wine_rb_entry * wine_rb_prev(struct wine_rb_entry *iter)
static struct wine_rb_entry * wine_rb_postorder_next(struct wine_rb_entry *iter)
static void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e)
static struct wine_rb_entry * wine_rb_get(const struct wine_rb_tree *tree, const void *key)
static void wine_rb_remove(struct wine_rb_tree *tree, struct wine_rb_entry *entry)
int(* wine_rb_compare_func_t)(const void *key, const struct wine_rb_entry *entry)
static struct wine_rb_entry * wine_rb_head(struct wine_rb_entry *iter)
void() wine_rb_traverse_func_t(struct wine_rb_entry *entry, void *context)
static void wine_rb_remove_key(struct wine_rb_tree *tree, const void *key)
static struct wine_rb_entry * wine_rb_tail(struct wine_rb_entry *iter)
static struct wine_rb_entry * wine_rb_postorder_head(struct wine_rb_entry *iter)
static void wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t compare)
static void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
static struct wine_rb_entry * wine_rb_next(struct wine_rb_entry *iter)
static int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
static int wine_rb_is_red(struct wine_rb_entry *entry)
#define WINE_RB_FOR_EACH(cursor, tree)
static void wine_rb_flip_color(struct wine_rb_entry *entry)
static void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
struct wine_rb_entry * left
struct wine_rb_entry * right
struct wine_rb_entry * parent
struct wine_rb_entry * root
wine_rb_compare_func_t compare