huwcampbell.com
Reactos
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#define RB_ENTRY_VALUE(element, type, field) \
27 ((type *)((char *)(element) - offsetof(type, field)))
28
29struct rb_entry
30{
31 struct rb_entry *parent;
32 struct rb_entry *left;
33 struct rb_entry *right;
34 unsigned int flags;
35};
36
37typedef int (*rb_compare_func_t)(const void *key, const struct rb_entry *entry);
38
39struct rb_tree
40{
41 rb_compare_func_t compare;
42 struct rb_entry *root;
43};
44
45typedef void (rb_traverse_func_t)(struct rb_entry *entry, void *context);
46
47#define RB_FLAG_RED 0x1
48
49static inline int rb_is_red(struct rb_entry *entry)
50{
51 return entry && (entry->flags & RB_FLAG_RED);
52}
53
54static inline void rb_rotate_left(struct rb_tree *tree, struct rb_entry *e)
55{
56 struct rb_entry *right = e->right;
57
58 if (!e->parent)
59 tree->root = right;
60 else if (e->parent->left == e)
61 e->parent->left = right;
62 else
63 e->parent->right = right;
64
65 e->right = right->left;
66 if (e->right) e->right->parent = e;
67 right->left = e;
68 right->parent = e->parent;
69 e->parent = right;
70}
71
72static inline void rb_rotate_right(struct rb_tree *tree, struct rb_entry *e)
73{
74 struct rb_entry *left = e->left;
75
76 if (!e->parent)
77 tree->root = left;
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;
85 left->right = e;
86 left->parent = e->parent;
87 e->parent = left;
88}
89
90static inline void rb_flip_color(struct rb_entry *entry)
91{
92 entry->flags ^= RB_FLAG_RED;
93 entry->left->flags ^= RB_FLAG_RED;
94 entry->right->flags ^= RB_FLAG_RED;
95}
96
97static inline struct rb_entry *rb_head(struct rb_entry *iter)
98{
99 if (!iter) return NULL;
100 while (iter->left) iter = iter->left;
101 return iter;
102}
103
104static inline struct rb_entry *rb_tail(struct rb_entry *iter)
105{
106 if (!iter) return NULL;
107 while (iter->right) iter = iter->right;
108 return iter;
109}
110
111static inline struct rb_entry *rb_next(struct rb_entry *iter)
112{
113 if (iter->right) return rb_head(iter->right);
114 while (iter->parent && iter->parent->right == iter) iter = iter->parent;
115 return iter->parent;
116}
117
118static inline struct rb_entry *rb_prev(struct rb_entry *iter)
119{
120 if (iter->left) return rb_tail(iter->left);
121 while (iter->parent && iter->parent->left == iter) iter = iter->parent;
122 return iter->parent;
123}
124
125static inline struct rb_entry *rb_postorder_head(struct rb_entry *iter)
126{
127 if (!iter) return NULL;
128
129 for (;;) {
130 while (iter->left) iter = iter->left;
131 if (!iter->right) return iter;
132 iter = iter->right;
133 }
134}
135
136static inline struct rb_entry *rb_postorder_next(struct rb_entry *iter)
137{
138 if (!iter->parent) return NULL;
139 if (iter == iter->parent->right || !iter->parent->right) return iter->parent;
140 return rb_postorder_head(iter->parent->right);
141}
142
143/* iterate through the tree */
144#define RB_FOR_EACH(cursor, tree) \
145 for ((cursor) = rb_head((tree)->root); (cursor); (cursor) = rb_next(cursor))
146
147/* iterate through the tree using a tree entry */
148#define RB_FOR_EACH_ENTRY(elem, tree, type, field) \
149 for ((elem) = RB_ENTRY_VALUE(rb_head((tree)->root), type, field); \
150 (elem) != RB_ENTRY_VALUE(0, type, field); \
151 (elem) = RB_ENTRY_VALUE(rb_next(&elem->field), type, field))
152
153/* iterate through the tree using using postorder, making it safe to free the entry */
154#define RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree) \
155 for ((cursor) = rb_postorder_head((tree)->root); \
156 (cursor) && (((cursor2) = rb_postorder_next(cursor)) || 1); \
157 (cursor) = (cursor2))
158
159/* iterate through the tree using a tree entry and postorder, making it safe to free the entry */
160#define RB_FOR_EACH_ENTRY_DESTRUCTOR(elem, elem2, tree, type, field) \
161 for ((elem) = RB_ENTRY_VALUE(rb_postorder_head((tree)->root), type, field); \
162 (elem) != RB_ENTRY_VALUE(0, type, field) \
163 && (((elem2) = RB_ENTRY_VALUE(rb_postorder_next(&(elem)->field), type, field)) || 1); \
164 (elem) = (elem2))
165
166
167static inline void rb_postorder(struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
168{
169 struct rb_entry *iter, *next;
170 RB_FOR_EACH_DESTRUCTOR(iter, next, tree) callback(iter, context);
171}
172
173static inline void rb_init(struct rb_tree *tree, rb_compare_func_t compare)
174{
175 tree->compare = compare;
176 tree->root = NULL;
177}
178
179static inline void rb_for_each_entry(struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
180{
181 struct rb_entry *iter;
182 RB_FOR_EACH(iter, tree) callback(iter, context);
183}
184
185static inline void rb_destroy(struct rb_tree *tree, rb_traverse_func_t *callback, void *context)
186{
187 /* Note that we use postorder here because the callback will likely free the entry. */
188 if (callback) rb_postorder(tree, callback, context);
189 tree->root = NULL;
190}
191
192static inline struct rb_entry *rb_get(const struct rb_tree *tree, const void *key)
193{
194 struct rb_entry *entry = tree->root;
195 while (entry)
196 {
197 int c = tree->compare(key, entry);
198 if (!c) return entry;
199 entry = c < 0 ? entry->left : entry->right;
200 }
201 return NULL;
202}
203
204static inline int rb_put(struct rb_tree *tree, const void *key, struct rb_entry *entry)
205{
206 struct rb_entry **iter = &tree->root, *parent = tree->root;
207
208 while (*iter)
209 {
210 int c;
211
212 parent = *iter;
213 c = tree->compare(key, parent);
214 if (!c) return -1;
215 else if (c < 0) iter = &parent->left;
216 else iter = &parent->right;
217 }
218
219 entry->flags = RB_FLAG_RED;
220 entry->parent = parent;
221 entry->left = NULL;
222 entry->right = NULL;
223 *iter = entry;
224
225 while (rb_is_red(entry->parent))
226 {
227 if (entry->parent == entry->parent->parent->left)
228 {
229 if (rb_is_red(entry->parent->parent->right))
230 {
231 rb_flip_color(entry->parent->parent);
232 entry = entry->parent->parent;
233 }
234 else
235 {
236 if (entry == entry->parent->right)
237 {
238 entry = entry->parent;
239 rb_rotate_left(tree, entry);
240 }
241 entry->parent->flags &= ~RB_FLAG_RED;
242 entry->parent->parent->flags |= RB_FLAG_RED;
243 rb_rotate_right(tree, entry->parent->parent);
244 }
245 }
246 else
247 {
248 if (rb_is_red(entry->parent->parent->left))
249 {
250 rb_flip_color(entry->parent->parent);
251 entry = entry->parent->parent;
252 }
253 else
254 {
255 if (entry == entry->parent->left)
256 {
257 entry = entry->parent;
258 rb_rotate_right(tree, entry);
259 }
260 entry->parent->flags &= ~RB_FLAG_RED;
261 entry->parent->parent->flags |= RB_FLAG_RED;
262 rb_rotate_left(tree, entry->parent->parent);
263 }
264 }
265 }
266
267 tree->root->flags &= ~RB_FLAG_RED;
268
269 return 0;
270}
271
272static inline void rb_remove(struct rb_tree *tree, struct rb_entry *entry)
273{
274 struct rb_entry *iter, *child, *parent, *w;
275 int need_fixup;
276
277 if (entry->right && entry->left)
278 for(iter = entry->right; iter->left; iter = iter->left);
279 else
280 iter = entry;
281
282 child = iter->left ? iter->left : iter->right;
283
284 if (!iter->parent)
285 tree->root = child;
286 else if (iter == iter->parent->left)
287 iter->parent->left = child;
288 else
289 iter->parent->right = child;
290
291 if (child) child->parent = iter->parent;
292 parent = iter->parent;
293
294 need_fixup = !rb_is_red(iter);
295
296 if (entry != iter)
297 {
298 *iter = *entry;
299 if (!iter->parent)
300 tree->root = iter;
301 else if (entry == iter->parent->left)
302 iter->parent->left = iter;
303 else
304 iter->parent->right = iter;
305
306 if (iter->right) iter->right->parent = iter;
307 if (iter->left) iter->left->parent = iter;
308 if (parent == entry) parent = iter;
309 }
310
311 if (need_fixup)
312 {
313 while (parent && !rb_is_red(child))
314 {
315 if (child == parent->left)
316 {
317 w = parent->right;
318 if (rb_is_red(w))
319 {
320 w->flags &= ~RB_FLAG_RED;
321 parent->flags |= RB_FLAG_RED;
322 rb_rotate_left(tree, parent);
323 w = parent->right;
324 }
325 if (rb_is_red(w->left) || rb_is_red(w->right))
326 {
327 if (!rb_is_red(w->right))
328 {
329 w->left->flags &= ~RB_FLAG_RED;
330 w->flags |= RB_FLAG_RED;
331 rb_rotate_right(tree, w);
332 w = parent->right;
333 }
334 w->flags = (w->flags & ~RB_FLAG_RED) | (parent->flags & RB_FLAG_RED);
335 parent->flags &= ~RB_FLAG_RED;
336 if (w->right)
337 w->right->flags &= ~RB_FLAG_RED;
338 rb_rotate_left(tree, parent);
339 child = NULL;
340 break;
341 }
342 }
343 else
344 {
345 w = parent->left;
346 if (rb_is_red(w))
347 {
348 w->flags &= ~RB_FLAG_RED;
349 parent->flags |= RB_FLAG_RED;
350 rb_rotate_right(tree, parent);
351 w = parent->left;
352 }
353 if (rb_is_red(w->left) || rb_is_red(w->right))
354 {
355 if (!rb_is_red(w->left))
356 {
357 w->right->flags &= ~RB_FLAG_RED;
358 w->flags |= RB_FLAG_RED;
359 rb_rotate_left(tree, w);
360 w = parent->left;
361 }
362 w->flags = (w->flags & ~RB_FLAG_RED) | (parent->flags & RB_FLAG_RED);
363 parent->flags &= ~RB_FLAG_RED;
364 if (w->left)
365 w->left->flags &= ~RB_FLAG_RED;
366 rb_rotate_right(tree, parent);
367 child = NULL;
368 break;
369 }
370 }
371 w->flags |= RB_FLAG_RED;
372 child = parent;
373 parent = child->parent;
374 }
375 if (child) child->flags &= ~RB_FLAG_RED;
376 }
377
378 if (tree->root) tree->root->flags &= ~RB_FLAG_RED;
379}
380
381static inline void rb_remove_key(struct rb_tree *tree, const void *key)
382{
383 struct rb_entry *entry = rb_get(tree, key);
384 if (entry) rb_remove(tree, entry);
385}
386
387static inline void rb_replace(struct rb_tree *tree, struct rb_entry *dst, struct rb_entry *src)
388{
389 if (!(src->parent = dst->parent))
390 tree->root = src;
391 else if (dst->parent->left == dst)
392 dst->parent->left = src;
393 else
394 dst->parent->right = src;
395
396 if ((src->left = dst->left))
397 src->left->parent = src;
398 if ((src->right = dst->right))
399 src->right->parent = src;
400 src->flags = dst->flags;
401}
402
403/* old names for backwards compatibility */
404#define wine_rb_entry rb_entry
405#define wine_rb_tree rb_tree
406#define wine_rb_init rb_init
407#define wine_rb_for_each_entry rb_for_each_entry
408#define wine_rb_destroy rb_destroy
409#define wine_rb_get rb_get
410#define wine_rb_put rb_put
411#define wine_rb_remove rb_remove
412#define wine_rb_remove_key rb_remove_key
413#define wine_rb_replace rb_replace
414#define WINE_RB_ENTRY_VALUE RB_ENTRY_VALUE
415#define WINE_RB_FOR_EACH_ENTRY RB_FOR_EACH_ENTRY
416#define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR RB_FOR_EACH_ENTRY_DESTRUCTOR
417#ifdef __REACTOS__
418#define wine_rb_clear rb_destroy
419#endif
420
421#endif /* __WINE_WINE_RBTREE_H */