2 * Red-black search tree support
4 * Copyright 2009 Henri Verbeet
5 * Copyright 2009 Andrew Riedi
6 * Copyright 2016 Jacek Caban for CodeWeavers
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.
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.
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
23 #ifndef __WINE_WINE_RBTREE_H
24 #define __WINE_WINE_RBTREE_H
26 #define RB_ENTRY_VALUE(element, type, field) \
27 ((type *)((char *)(element) - offsetof(type, field)))
31 struct rb_entry
*parent
;
32 struct rb_entry
*left
;
33 struct rb_entry
*right
;
37 typedef int (*rb_compare_func
)(const void *key
, const struct rb_entry
*entry
);
41 rb_compare_func compare
;
42 struct rb_entry
*root
;
45 typedef void (rb_traverse_func
)(struct rb_entry
*entry
, void *context
);
47 #define RB_FLAG_RED 0x1
49 static inline int rb_is_red(struct rb_entry
*entry
)
51 return entry
&& (entry
->flags
& RB_FLAG_RED
);
54 static inline void rb_rotate_left(struct rb_tree
*tree
, struct rb_entry
*e
)
56 struct rb_entry
*right
= e
->right
;
60 else if (e
->parent
->left
== e
)
61 e
->parent
->left
= right
;
63 e
->parent
->right
= right
;
65 e
->right
= right
->left
;
66 if (e
->right
) e
->right
->parent
= e
;
68 right
->parent
= e
->parent
;
72 static inline void rb_rotate_right(struct rb_tree
*tree
, struct rb_entry
*e
)
74 struct rb_entry
*left
= e
->left
;
78 else if (e
->parent
->left
== e
)
79 e
->parent
->left
= left
;
81 e
->parent
->right
= left
;
83 e
->left
= left
->right
;
84 if (e
->left
) e
->left
->parent
= e
;
86 left
->parent
= e
->parent
;
90 static inline void rb_flip_color(struct rb_entry
*entry
)
92 entry
->flags
^= RB_FLAG_RED
;
93 entry
->left
->flags
^= RB_FLAG_RED
;
94 entry
->right
->flags
^= RB_FLAG_RED
;
97 static inline struct rb_entry
*rb_head(struct rb_entry
*iter
)
99 if (!iter
) return NULL
;
100 while (iter
->left
) iter
= iter
->left
;
104 static inline struct rb_entry
*rb_tail(struct rb_entry
*iter
)
106 if (!iter
) return NULL
;
107 while (iter
->right
) iter
= iter
->right
;
111 static inline struct rb_entry
*rb_next(struct rb_entry
*iter
)
113 if (iter
->right
) return rb_head(iter
->right
);
114 while (iter
->parent
&& iter
->parent
->right
== iter
) iter
= iter
->parent
;
118 static inline struct rb_entry
*rb_prev(struct rb_entry
*iter
)
120 if (iter
->left
) return rb_tail(iter
->left
);
121 while (iter
->parent
&& iter
->parent
->left
== iter
) iter
= iter
->parent
;
125 static inline struct rb_entry
*rb_postorder_head(struct rb_entry
*iter
)
127 if (!iter
) return NULL
;
130 while (iter
->left
) iter
= iter
->left
;
131 if (!iter
->right
) return iter
;
136 static inline struct rb_entry
*rb_postorder_next(struct rb_entry
*iter
)
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
);
143 /* iterate through the tree */
144 #define RB_FOR_EACH(cursor, tree) \
145 for ((cursor) = rb_head((tree)->root); (cursor); (cursor) = rb_next(cursor))
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))
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))
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); \
167 static inline void rb_postorder(struct rb_tree
*tree
, rb_traverse_func
*callback
, void *context
)
169 struct rb_entry
*iter
, *next
;
170 RB_FOR_EACH_DESTRUCTOR(iter
, next
, tree
) callback(iter
, context
);
173 static inline void rb_init(struct rb_tree
*tree
, rb_compare_func compare
)
175 tree
->compare
= compare
;
179 static inline void rb_for_each_entry(struct rb_tree
*tree
, rb_traverse_func
*callback
, void *context
)
181 struct rb_entry
*iter
;
182 RB_FOR_EACH(iter
, tree
) callback(iter
, context
);
185 static inline void rb_destroy(struct rb_tree
*tree
, rb_traverse_func
*callback
, void *context
)
187 /* Note that we use postorder here because the callback will likely free the entry. */
188 if (callback
) rb_postorder(tree
, callback
, context
);
192 static inline struct rb_entry
*rb_get(const struct rb_tree
*tree
, const void *key
)
194 struct rb_entry
*entry
= tree
->root
;
197 int c
= tree
->compare(key
, entry
);
198 if (!c
) return entry
;
199 entry
= c
< 0 ? entry
->left
: entry
->right
;
204 static inline int rb_put(struct rb_tree
*tree
, const void *key
, struct rb_entry
*entry
)
206 struct rb_entry
**iter
= &tree
->root
, *parent
= tree
->root
;
213 c
= tree
->compare(key
, parent
);
215 else if (c
< 0) iter
= &parent
->left
;
216 else iter
= &parent
->right
;
219 entry
->flags
= RB_FLAG_RED
;
220 entry
->parent
= parent
;
225 while (rb_is_red(entry
->parent
))
227 if (entry
->parent
== entry
->parent
->parent
->left
)
229 if (rb_is_red(entry
->parent
->parent
->right
))
231 rb_flip_color(entry
->parent
->parent
);
232 entry
= entry
->parent
->parent
;
236 if (entry
== entry
->parent
->right
)
238 entry
= entry
->parent
;
239 rb_rotate_left(tree
, entry
);
241 entry
->parent
->flags
&= ~RB_FLAG_RED
;
242 entry
->parent
->parent
->flags
|= RB_FLAG_RED
;
243 rb_rotate_right(tree
, entry
->parent
->parent
);
248 if (rb_is_red(entry
->parent
->parent
->left
))
250 rb_flip_color(entry
->parent
->parent
);
251 entry
= entry
->parent
->parent
;
255 if (entry
== entry
->parent
->left
)
257 entry
= entry
->parent
;
258 rb_rotate_right(tree
, entry
);
260 entry
->parent
->flags
&= ~RB_FLAG_RED
;
261 entry
->parent
->parent
->flags
|= RB_FLAG_RED
;
262 rb_rotate_left(tree
, entry
->parent
->parent
);
267 tree
->root
->flags
&= ~RB_FLAG_RED
;
272 static inline void rb_remove(struct rb_tree
*tree
, struct rb_entry
*entry
)
274 struct rb_entry
*iter
, *child
, *parent
, *w
;
277 if (entry
->right
&& entry
->left
)
278 for(iter
= entry
->right
; iter
->left
; iter
= iter
->left
);
282 child
= iter
->left
? iter
->left
: iter
->right
;
286 else if (iter
== iter
->parent
->left
)
287 iter
->parent
->left
= child
;
289 iter
->parent
->right
= child
;
291 if (child
) child
->parent
= iter
->parent
;
292 parent
= iter
->parent
;
294 need_fixup
= !rb_is_red(iter
);
301 else if (entry
== iter
->parent
->left
)
302 iter
->parent
->left
= iter
;
304 iter
->parent
->right
= iter
;
306 if (iter
->right
) iter
->right
->parent
= iter
;
307 if (iter
->left
) iter
->left
->parent
= iter
;
308 if (parent
== entry
) parent
= iter
;
313 while (parent
&& !rb_is_red(child
))
315 if (child
== parent
->left
)
320 w
->flags
&= ~RB_FLAG_RED
;
321 parent
->flags
|= RB_FLAG_RED
;
322 rb_rotate_left(tree
, parent
);
325 if (rb_is_red(w
->left
) || rb_is_red(w
->right
))
327 if (!rb_is_red(w
->right
))
329 w
->left
->flags
&= ~RB_FLAG_RED
;
330 w
->flags
|= RB_FLAG_RED
;
331 rb_rotate_right(tree
, w
);
334 w
->flags
= (w
->flags
& ~RB_FLAG_RED
) | (parent
->flags
& RB_FLAG_RED
);
335 parent
->flags
&= ~RB_FLAG_RED
;
337 w
->right
->flags
&= ~RB_FLAG_RED
;
338 rb_rotate_left(tree
, parent
);
348 w
->flags
&= ~RB_FLAG_RED
;
349 parent
->flags
|= RB_FLAG_RED
;
350 rb_rotate_right(tree
, parent
);
353 if (rb_is_red(w
->left
) || rb_is_red(w
->right
))
355 if (!rb_is_red(w
->left
))
357 w
->right
->flags
&= ~RB_FLAG_RED
;
358 w
->flags
|= RB_FLAG_RED
;
359 rb_rotate_left(tree
, w
);
362 w
->flags
= (w
->flags
& ~RB_FLAG_RED
) | (parent
->flags
& RB_FLAG_RED
);
363 parent
->flags
&= ~RB_FLAG_RED
;
365 w
->left
->flags
&= ~RB_FLAG_RED
;
366 rb_rotate_right(tree
, parent
);
371 w
->flags
|= RB_FLAG_RED
;
373 parent
= child
->parent
;
375 if (child
) child
->flags
&= ~RB_FLAG_RED
;
378 if (tree
->root
) tree
->root
->flags
&= ~RB_FLAG_RED
;
381 static inline void rb_remove_key(struct rb_tree
*tree
, const void *key
)
383 struct rb_entry
*entry
= rb_get(tree
, key
);
384 if (entry
) rb_remove(tree
, entry
);
387 static inline void rb_replace(struct rb_tree
*tree
, struct rb_entry
*dst
, struct rb_entry
*src
)
389 if (!(src
->parent
= dst
->parent
))
391 else if (dst
->parent
->left
== dst
)
392 dst
->parent
->left
= src
;
394 dst
->parent
->right
= src
;
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
;
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
418 #endif /* __WINE_WINE_RBTREE_H */