ReactOS  0.4.13-dev-482-ge57f103
rbtree.h
Go to the documentation of this file.
1 /*
2  * Red-black search tree support
3  *
4  * Copyright 2009 Henri Verbeet
5  * Copyright 2009 Andrew Riedi
6  * Copyright 2016 Jacek Caban for CodeWeavers
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2.1 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  * Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with this library; if not, write to the Free Software
20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
21  */
22 
23 #ifndef __WINE_WINE_RBTREE_H
24 #define __WINE_WINE_RBTREE_H
25 
26 #ifdef __GNUC__
27 # define WINE_RB_ENTRY_VALUE(element, type, field) ({ \
28  const typeof(((type *)0)->field) *__ptr = (element); \
29  (type *)((char *)__ptr - offsetof(type, field)); })
30 #else
31 # define WINE_RB_ENTRY_VALUE(element, type, field) \
32  ((type *)((char *)(element) - offsetof(type, field)))
33 #endif
34 
36 {
40  unsigned int flags;
41 };
42 
43 typedef int (*wine_rb_compare_func_t)(const void *key, const struct wine_rb_entry *entry);
44 
46 {
49 };
50 
52 
53 #define WINE_RB_FLAG_RED 0x1
54 
55 static inline int wine_rb_is_red(struct wine_rb_entry *entry)
56 {
57  return entry && (entry->flags & WINE_RB_FLAG_RED);
58 }
59 
60 static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
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 }
77 
78 static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e)
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 }
95 
96 static inline void wine_rb_flip_color(struct wine_rb_entry *entry)
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 }
102 
103 static inline struct wine_rb_entry *wine_rb_head(struct wine_rb_entry *iter)
104 {
105  if (!iter) return NULL;
106  while (iter->left) iter = iter->left;
107  return iter;
108 }
109 
110 static inline struct wine_rb_entry *wine_rb_tail(struct wine_rb_entry *iter)
111 {
112  if (!iter) return NULL;
113  while (iter->right) iter = iter->right;
114  return iter;
115 }
116 
117 static inline struct wine_rb_entry *wine_rb_next(struct wine_rb_entry *iter)
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 }
123 
124 static inline struct wine_rb_entry *wine_rb_prev(struct wine_rb_entry *iter)
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 }
130 
131 static inline struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter)
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 }
141 
142 static inline struct wine_rb_entry *wine_rb_postorder_next(struct wine_rb_entry *iter)
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 }
148 
149 /* iterate through the tree */
150 #define WINE_RB_FOR_EACH(cursor, tree) \
151  for ((cursor) = wine_rb_head((tree)->root); (cursor); (cursor) = wine_rb_next(cursor))
152 
153 /* iterate through the tree using a tree entry */
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))
158 
159 /* iterate through the tree using using postorder, making it safe to free the entry */
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))
164 
165 /* iterate through the tree using a tree entry and postorder, making it safe to free the entry */
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); \
170  (elem) = (elem2))
171 
172 
174 {
175  struct wine_rb_entry *iter, *next;
177 }
178 
180 {
181  tree->compare = compare;
182  tree->root = NULL;
183 }
184 
186 {
187  struct wine_rb_entry *iter;
188  WINE_RB_FOR_EACH(iter, tree) callback(iter, context);
189 }
190 
192 {
193  /* Note that we use postorder here because the callback will likely free the entry. */
195  tree->root = NULL;
196 }
197 
199 {
201 }
202 
203 static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)
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 }
214 
215 static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
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 }
282 
283 static inline void wine_rb_remove(struct wine_rb_tree *tree, struct wine_rb_entry *entry)
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 }
391 
392 static inline void wine_rb_remove_key(struct wine_rb_tree *tree, const void *key)
393 {
394  struct wine_rb_entry *entry = wine_rb_get(tree, key);
396 }
397 
398 #endif /* __WINE_WINE_RBTREE_H */
Definition: bug.cpp:7
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
static void wine_rb_clear(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:191
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
struct png_info_def **typedef void(__cdecl typeof(png_destroy_read_struct))(struct png_struct_def **
Definition: typeof.h:49
#define WINE_RB_FOR_EACH(cursor, tree)
Definition: rbtree.h:150
Definition: http.c:6587
struct wine_rb_entry * right
Definition: rbtree.h:39
struct wine_rb_entry * root
Definition: rbtree.h:48
struct wine_rb_entry * left
Definition: rbtree.h:38
wine_rb_compare_func_t compare
Definition: rbtree.h:47
int(* wine_rb_compare_func_t)(const void *key, const struct wine_rb_entry *entry)
Definition: rbtree.h:43
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
#define WINE_RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree)
Definition: rbtree.h:160
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
#define e
Definition: ke_i.h:82
static void wine_rb_flip_color(struct wine_rb_entry *entry)
Definition: rbtree.h:96
smooth NULL
Definition: ftsmooth.c:416
static void wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t compare)
Definition: rbtree.h:179
MmuTrapHandler callback[0x30]
Definition: mmuobject.c:44
static void wine_rb_remove_key(struct wine_rb_tree *tree, const void *key)
Definition: rbtree.h:392
r parent
Definition: btrfs.c:2708
const GLubyte * c
Definition: glext.h:8905
static struct wine_rb_entry * wine_rb_tail(struct wine_rb_entry *iter)
Definition: rbtree.h:110
GLint left
Definition: glext.h:7726
GLdouble GLdouble right
Definition: glext.h:10859
static struct wine_rb_entry * wine_rb_postorder_next(struct wine_rb_entry *iter)
Definition: rbtree.h:142
static void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:198
HKEY key
Definition: reg.c:42
uint32_t entry
Definition: isohybrid.c:63
struct wine_rb_entry * parent
Definition: rbtree.h:37
static void wine_rb_remove(struct wine_rb_tree *tree, struct wine_rb_entry *entry)
Definition: rbtree.h:283
static void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
Definition: rbtree.h:185
void() wine_rb_traverse_func_t(struct wine_rb_entry *entry, void *context)
Definition: rbtree.h:51
static unsigned __int64 next
Definition: rand_nt.c:6
unsigned int flags
Definition: rbtree.h:40
Definition: rbtree.h:35
#define WINE_RB_FLAG_RED
Definition: rbtree.h:53
static int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
Definition: rbtree.h:215
static struct wine_rb_entry * wine_rb_get(const struct wine_rb_tree *tree, const void *key)
Definition: rbtree.h:203
#define compare
#define c
Definition: ke_i.h:80
static struct wine_rb_entry * wine_rb_prev(struct wine_rb_entry *iter)
Definition: rbtree.h:124
static struct wine_rb_entry * wine_rb_next(struct wine_rb_entry *iter)
Definition: rbtree.h:117
Definition: path.c:42
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
static struct wine_rb_entry * wine_rb_postorder_head(struct wine_rb_entry *iter)
Definition: rbtree.h:131
static struct wine_rb_entry * wine_rb_head(struct wine_rb_entry *iter)
Definition: rbtree.h:103