ReactOS  0.4.13-dev-563-g0561610
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))
static struct wine_rb_entry * wine_rb_postorder_next(struct wine_rb_entry *iter)
Definition: rbtree.h:142
const char cursor[]
Definition: icontest.c:13
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
Definition: parser.c:43
#define WINE_RB_ENTRY_VALUE(element, type, field)
Definition: rbtree.h:31
static struct wine_rb_entry * wine_rb_next(struct wine_rb_entry *iter)
Definition: rbtree.h:117
static struct wine_rb_entry * wine_rb_head(struct wine_rb_entry *iter)
Definition: rbtree.h:103

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:
(elem) = (elem2))
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
static size_t elem
Definition: string.c:68
Definition: parser.c:43
#define WINE_RB_ENTRY_VALUE(element, type, field)
Definition: rbtree.h:31
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 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 }
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:423
Definition: http.c:6587
smooth NULL
Definition: ftsmooth.c:416
MmuTrapHandler callback[0x30]
Definition: mmuobject.c:44

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
Definition: http.c:6587
MmuTrapHandler callback[0x30]
Definition: mmuobject.c:44

Referenced by add_function_decl(), arbfp_blitter_destroy(), arbfp_free(), atifs_free(), device_init(), free_function(), glsl_blitter_destroy(), glsl_fragment_pipe_free(), glsl_vertex_pipe_vp_free(), parse_hlsl(), 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;
188  WINE_RB_FOR_EACH(iter, tree) callback(iter, context);
189 }
#define WINE_RB_FOR_EACH(cursor, tree)
Definition: rbtree.h:150
Definition: http.c:6587
MmuTrapHandler callback[0x30]
Definition: mmuobject.c:44
Definition: rbtree.h:35

Referenced by dump_function(), parse_hlsl(), and 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

Definition at line 203 of file rbtree.h.

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 }
struct _root * root
Definition: btrfs_drv.h:423
smooth NULL
Definition: ftsmooth.c:416
const GLubyte * c
Definition: glext.h:8905
uint32_t entry
Definition: isohybrid.c:63
Definition: rbtree.h:35
Definition: path.c:42

Referenced by add_function_decl(), arbfp_blit_set(), CreateComponentInfo(), find_ffp_frag_shader(), find_function(), find_input_signature(), find_local(), get_glsl_program_entry(), get_overloaded_func(), get_parameter_by_name(), get_reflection_type(), get_type(), glsl_blitter_get_program(), sampler(), shader_glsl_find_ffp_vertex_shader(), source_find(), and wine_rb_remove_key().

◆ 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
smooth NULL
Definition: ftsmooth.c:416

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

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

◆ 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 }
Definition: http.c:6587
#define WINE_RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
Definition: rbtree.h:160
MmuTrapHandler callback[0x30]
Definition: mmuobject.c:44
static unsigned __int64 next
Definition: rand_nt.c:6
Definition: rbtree.h:35

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 }
struct wine_rb_entry * right
Definition: rbtree.h:39
struct wine_rb_entry * left
Definition: rbtree.h:38
smooth NULL
Definition: ftsmooth.c:416

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 }
smooth NULL
Definition: ftsmooth.c:416
struct wine_rb_entry * parent
Definition: rbtree.h:37
static struct wine_rb_entry * wine_rb_postorder_head(struct wine_rb_entry *iter)
Definition: rbtree.h:131

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

◆ 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 }
struct _root * root
Definition: btrfs_drv.h:423
static void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
Definition: rbtree.h:60
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
smooth NULL
Definition: ftsmooth.c:416
r parent
Definition: btrfs.c:2708
const GLubyte * c
Definition: glext.h:8905
uint32_t entry
Definition: isohybrid.c:63
Definition: rbtree.h:35
#define WINE_RB_FLAG_RED
Definition: rbtree.h:53
#define c
Definition: ke_i.h:80
Definition: path.c:42

Referenced by add_ffp_frag_shader(), add_function_decl(), add_glsl_program_entry(), add_param_to_tree(), add_type_to_scope(), alloc_local(), arbfp_blit_set(), CreateComponentInfo(), find_input_signature(), get_reflection_type(), glsl_blitter_get_program(), 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 }
struct _root * root
Definition: btrfs_drv.h:423
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
struct wine_rb_entry * right
Definition: rbtree.h:39
struct wine_rb_entry * left
Definition: rbtree.h:38
static HWND child
Definition: cursoricon.c:298
static void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
Definition: rbtree.h:60
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
smooth NULL
Definition: ftsmooth.c:416
r parent
Definition: btrfs.c:2708
uint32_t entry
Definition: isohybrid.c:63
struct wine_rb_entry * parent
Definition: rbtree.h:37
Definition: rbtree.h:35
#define WINE_RB_FLAG_RED
Definition: rbtree.h:53

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 {
394  struct wine_rb_entry *entry = wine_rb_get(tree, key);
396 }
uint32_t entry
Definition: isohybrid.c:63
static void wine_rb_remove(struct wine_rb_tree *tree, struct wine_rb_entry *entry)
Definition: rbtree.h:283
Definition: rbtree.h:35
static struct wine_rb_entry * wine_rb_get(const struct wine_rb_tree *tree, const void *key)
Definition: rbtree.h:203
Definition: path.c:42

◆ 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 }
struct _root * root
Definition: btrfs_drv.h:423
#define e
Definition: ke_i.h:82
GLdouble GLdouble right
Definition: glext.h:10859
Definition: rbtree.h:35

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 }
struct _root * root
Definition: btrfs_drv.h:423
#define e
Definition: ke_i.h:82
GLint left
Definition: glext.h:7726
Definition: rbtree.h:35

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 }
struct wine_rb_entry * right
Definition: rbtree.h:39
smooth NULL
Definition: ftsmooth.c:416

Referenced by wine_rb_prev().