ReactOS 0.4.15-dev-8127-g6338913
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  wine_rb_entry
 
struct  wine_rb_tree
 

Macros

#define WINE_RB_ENTRY_VALUE(element, type, field)    ((type *)((char *)(element) - offsetof(type, field)))
 
#define WINE_RB_FLAG_RED   0x1
 
#define WINE_RB_FOR_EACH(cursor, tree)    for ((cursor) = wine_rb_head((tree)->root); (cursor); (cursor) = wine_rb_next(cursor))
 
#define WINE_RB_FOR_EACH_ENTRY(elem, tree, type, field)
 
#define WINE_RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
 
#define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR(elem, elem2, tree, type, field)
 

Typedefs

typedef int(* wine_rb_compare_func_t) (const void *key, const struct wine_rb_entry *entry)
 
typedef void() wine_rb_traverse_func_t(struct wine_rb_entry *entry, void *context)
 

Functions

static int wine_rb_is_red (struct wine_rb_entry *entry)
 
static void wine_rb_rotate_left (struct wine_rb_tree *tree, struct wine_rb_entry *e)
 
static void wine_rb_rotate_right (struct wine_rb_tree *tree, struct wine_rb_entry *e)
 
static void wine_rb_flip_color (struct wine_rb_entry *entry)
 
static struct wine_rb_entrywine_rb_head (struct wine_rb_entry *iter)
 
static struct wine_rb_entrywine_rb_tail (struct wine_rb_entry *iter)
 
static struct wine_rb_entrywine_rb_next (struct wine_rb_entry *iter)
 
static struct wine_rb_entrywine_rb_prev (struct wine_rb_entry *iter)
 
static struct wine_rb_entrywine_rb_postorder_head (struct wine_rb_entry *iter)
 
static struct wine_rb_entrywine_rb_postorder_next (struct wine_rb_entry *iter)
 
static void wine_rb_postorder (struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 
static void wine_rb_init (struct wine_rb_tree *tree, wine_rb_compare_func_t compare)
 
static void wine_rb_for_each_entry (struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
 
static void wine_rb_clear (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 struct wine_rb_entrywine_rb_get (const struct wine_rb_tree *tree, const void *key)
 
static int wine_rb_put (struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
 
static void wine_rb_remove (struct wine_rb_tree *tree, struct wine_rb_entry *entry)
 
static void wine_rb_remove_key (struct wine_rb_tree *tree, const void *key)
 

Macro Definition Documentation

◆ WINE_RB_ENTRY_VALUE

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

Definition at line 31 of file rbtree.h.

◆ WINE_RB_FLAG_RED

#define WINE_RB_FLAG_RED   0x1

Definition at line 53 of file rbtree.h.

◆ WINE_RB_FOR_EACH

#define WINE_RB_FOR_EACH (   cursor,
  tree 
)     for ((cursor) = wine_rb_head((tree)->root); (cursor); (cursor) = wine_rb_next(cursor))

Definition at line 150 of file rbtree.h.

◆ WINE_RB_FOR_EACH_DESTRUCTOR

#define WINE_RB_FOR_EACH_DESTRUCTOR (   cursor,
  cursor2,
  tree 
)
Value:
(cursor) && (((cursor2) = wine_rb_postorder_next(cursor)) || 1); \
(cursor) = (cursor2))
const char cursor[]
Definition: icontest.c:13
static struct wine_rb_entry * wine_rb_postorder_next(struct wine_rb_entry *iter)
Definition: rbtree.h:142
static struct wine_rb_entry * wine_rb_postorder_head(struct wine_rb_entry *iter)
Definition: rbtree.h:131

Definition at line 160 of file rbtree.h.

◆ WINE_RB_FOR_EACH_ENTRY

#define WINE_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:68
#define WINE_RB_ENTRY_VALUE(element, type, field)
Definition: rbtree.h:31
static struct wine_rb_entry * wine_rb_head(struct wine_rb_entry *iter)
Definition: rbtree.h:103
static struct wine_rb_entry * wine_rb_next(struct wine_rb_entry *iter)
Definition: rbtree.h:117
Definition: parser.c:44

Definition at line 154 of file rbtree.h.

◆ WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR

#define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR (   elem,
  elem2,
  tree,
  type,
  field 
)
Value:

Definition at line 166 of file rbtree.h.

Typedef Documentation

◆ wine_rb_compare_func_t

typedef int(* wine_rb_compare_func_t) (const void *key, const struct wine_rb_entry *entry)

Definition at line 43 of file rbtree.h.

◆ wine_rb_traverse_func_t

typedef void() wine_rb_traverse_func_t(struct wine_rb_entry *entry, void *context)

Definition at line 51 of file rbtree.h.

Function Documentation

◆ wine_rb_clear()

static void wine_rb_clear ( struct wine_rb_tree tree,
wine_rb_traverse_func_t callback,
void context 
)
inlinestatic

Definition at line 191 of file rbtree.h.

192{
193 /* Note that we use postorder here because the callback will likely free the entry. */
195 tree->root = NULL;
196}
#define NULL
Definition: types.h:112
static IPrintDialogCallback callback
Definition: printdlg.c:326
static void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:173
struct _root * root
Definition: btrfs_drv.h:433
Definition: http.c:7252

Referenced by wine_rb_destroy(), wined3d_device_reset(), and wined3d_device_uninit_3d().

◆ wine_rb_destroy()

static void wine_rb_destroy ( struct wine_rb_tree tree,
wine_rb_traverse_func_t callback,
void context 
)
inlinestatic

Definition at line 198 of file rbtree.h.

199{
201}
static void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:191

Referenced by add_function_decl(), arbfp_blitter_destroy(), arbfp_free(), atifs_free(), device_init(), free_function(), glsl_fragment_pipe_free(), glsl_vertex_pipe_vp_free(), ID3DXFontImpl_Release(), reflection_cleanup(), shader_arb_free(), shader_glsl_free(), and wined3d_device_decref().

◆ wine_rb_flip_color()

static void wine_rb_flip_color ( struct wine_rb_entry entry)
inlinestatic

Definition at line 96 of file rbtree.h.

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}
uint32_t entry
Definition: isohybrid.c:63
#define WINE_RB_FLAG_RED
Definition: rbtree.h:53

Referenced by wine_rb_put().

◆ wine_rb_for_each_entry()

static void wine_rb_for_each_entry ( struct wine_rb_tree tree,
wine_rb_traverse_func_t callback,
void context 
)
inlinestatic

Definition at line 185 of file rbtree.h.

186{
187 struct wine_rb_entry *iter;
189}
#define WINE_RB_FOR_EACH(cursor, tree)
Definition: rbtree.h:150
Definition: rbtree.h:36

Referenced by shader_glsl_load_constants().

◆ wine_rb_get()

static struct wine_rb_entry * wine_rb_get ( const struct wine_rb_tree tree,
const void key 
)
inlinestatic

◆ wine_rb_head()

static struct wine_rb_entry * wine_rb_head ( struct wine_rb_entry iter)
inlinestatic

Definition at line 103 of file rbtree.h.

104{
105 if (!iter) return NULL;
106 while (iter->left) iter = iter->left;
107 return iter;
108}
struct wine_rb_entry * left
Definition: rbtree.h:38

Referenced by wine_rb_next().

◆ wine_rb_init()

◆ wine_rb_is_red()

static int wine_rb_is_red ( struct wine_rb_entry entry)
inlinestatic

Definition at line 55 of file rbtree.h.

56{
57 return entry && (entry->flags & WINE_RB_FLAG_RED);
58}

Referenced by wine_rb_put(), and wine_rb_remove().

◆ wine_rb_next()

static struct wine_rb_entry * wine_rb_next ( struct wine_rb_entry iter)
inlinestatic

Definition at line 117 of file rbtree.h.

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}
struct wine_rb_entry * right
Definition: rbtree.h:39
struct wine_rb_entry * parent
Definition: rbtree.h:37

◆ wine_rb_postorder()

static void wine_rb_postorder ( struct wine_rb_tree tree,
wine_rb_traverse_func_t callback,
void context 
)
inlinestatic

Definition at line 173 of file rbtree.h.

174{
175 struct wine_rb_entry *iter, *next;
177}
static unsigned __int64 next
Definition: rand_nt.c:6
#define WINE_RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
Definition: rbtree.h:160

Referenced by wine_rb_clear().

◆ wine_rb_postorder_head()

static struct wine_rb_entry * wine_rb_postorder_head ( struct wine_rb_entry iter)
inlinestatic

Definition at line 131 of file rbtree.h.

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}

Referenced by wine_rb_postorder_next().

◆ wine_rb_postorder_next()

static struct wine_rb_entry * wine_rb_postorder_next ( struct wine_rb_entry iter)
inlinestatic

Definition at line 142 of file rbtree.h.

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}

◆ wine_rb_prev()

static struct wine_rb_entry * wine_rb_prev ( struct wine_rb_entry iter)
inlinestatic

Definition at line 124 of file rbtree.h.

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}
static struct wine_rb_entry * wine_rb_tail(struct wine_rb_entry *iter)
Definition: rbtree.h:110

◆ wine_rb_put()

static int wine_rb_put ( struct wine_rb_tree tree,
const void key,
struct wine_rb_entry entry 
)
inlinestatic

Definition at line 215 of file rbtree.h.

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}
r parent
Definition: btrfs.c:3010
#define c
Definition: ke_i.h:80
static void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e)
Definition: rbtree.h:78
static int wine_rb_is_red(struct wine_rb_entry *entry)
Definition: rbtree.h:55
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

Referenced by add_ffp_frag_shader(), add_function_decl(), add_glsl_program_entry(), add_param_to_tree(), alloc_local(), arbfp_blit_set(), CreateComponentInfo(), find_input_signature(), get_reflection_type(), ID3DXFontImpl_PreloadGlyphs(), sampler(), shader_glsl_find_ffp_vertex_shader(), and source_new().

◆ wine_rb_remove()

static void wine_rb_remove ( struct wine_rb_tree tree,
struct wine_rb_entry entry 
)
inlinestatic

Definition at line 283 of file rbtree.h.

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}
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
static HWND child
Definition: cursoricon.c:298

Referenced by add_function_decl(), delete_glsl_program_entry(), and wine_rb_remove_key().

◆ wine_rb_remove_key()

static void wine_rb_remove_key ( struct wine_rb_tree tree,
const void key 
)
inlinestatic

Definition at line 392 of file rbtree.h.

393{
396}
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

◆ wine_rb_rotate_left()

static void wine_rb_rotate_left ( struct wine_rb_tree tree,
struct wine_rb_entry e 
)
inlinestatic

Definition at line 60 of file rbtree.h.

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}
GLdouble GLdouble right
Definition: glext.h:10859
#define e
Definition: ke_i.h:82

Referenced by wine_rb_put(), and wine_rb_remove().

◆ wine_rb_rotate_right()

static void wine_rb_rotate_right ( struct wine_rb_tree tree,
struct wine_rb_entry e 
)
inlinestatic

Definition at line 78 of file rbtree.h.

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}
GLint left
Definition: glext.h:7726

Referenced by wine_rb_put(), and wine_rb_remove().

◆ wine_rb_tail()

static struct wine_rb_entry * wine_rb_tail ( struct wine_rb_entry iter)
inlinestatic

Definition at line 110 of file rbtree.h.

111{
112 if (!iter) return NULL;
113 while (iter->right) iter = iter->right;
114 return iter;
115}

Referenced by wine_rb_prev().