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 WINE_RB_ENTRY_VALUE(element, type, field) \
27 ((type *)((char *)(element) - offsetof(type, field)))
31 struct wine_rb_entry
*parent
;
32 struct wine_rb_entry
*left
;
33 struct wine_rb_entry
*right
;
37 typedef int (*wine_rb_compare_func_t
)(const void *key
, const struct wine_rb_entry
*entry
);
41 wine_rb_compare_func_t compare
;
42 struct wine_rb_entry
*root
;
45 typedef void (wine_rb_traverse_func_t
)(struct wine_rb_entry
*entry
, void *context
);
47 #define WINE_RB_FLAG_RED 0x1
49 static inline int wine_rb_is_red(struct wine_rb_entry
*entry
)
51 return entry
&& (entry
->flags
& WINE_RB_FLAG_RED
);
54 static inline void wine_rb_rotate_left(struct wine_rb_tree
*tree
, struct wine_rb_entry
*e
)
56 struct wine_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 wine_rb_rotate_right(struct wine_rb_tree
*tree
, struct wine_rb_entry
*e
)
74 struct wine_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 wine_rb_flip_color(struct wine_rb_entry
*entry
)
92 entry
->flags
^= WINE_RB_FLAG_RED
;
93 entry
->left
->flags
^= WINE_RB_FLAG_RED
;
94 entry
->right
->flags
^= WINE_RB_FLAG_RED
;
97 static inline struct wine_rb_entry
*wine_rb_head(struct wine_rb_entry
*iter
)
99 if (!iter
) return NULL
;
100 while (iter
->left
) iter
= iter
->left
;
104 static inline struct wine_rb_entry
*wine_rb_next(struct wine_rb_entry
*iter
)
106 if (iter
->right
) return wine_rb_head(iter
->right
);
107 while (iter
->parent
&& iter
->parent
->right
== iter
) iter
= iter
->parent
;
111 static inline struct wine_rb_entry
*wine_rb_postorder_head(struct wine_rb_entry
*iter
)
113 if (!iter
) return NULL
;
116 while (iter
->left
) iter
= iter
->left
;
117 if (!iter
->right
) return iter
;
122 static inline struct wine_rb_entry
*wine_rb_postorder_next(struct wine_rb_entry
*iter
)
124 if (!iter
->parent
) return NULL
;
125 if (iter
== iter
->parent
->right
|| !iter
->parent
->right
) return iter
->parent
;
126 return wine_rb_postorder_head(iter
->parent
->right
);
129 /* iterate through the tree */
130 #define WINE_RB_FOR_EACH(cursor, tree) \
131 for ((cursor) = wine_rb_head((tree)->root); (cursor); (cursor) = wine_rb_next(cursor))
133 /* iterate through the tree using a tree entry */
134 #define WINE_RB_FOR_EACH_ENTRY(elem, tree, type, field) \
135 for ((elem) = WINE_RB_ENTRY_VALUE(wine_rb_head((tree)->root), type, field); \
137 (elem) = WINE_RB_ENTRY_VALUE(wine_rb_next(&elem->field), type, field))
140 static inline void wine_rb_postorder(struct wine_rb_tree
*tree
, wine_rb_traverse_func_t
*callback
, void *context
)
142 struct wine_rb_entry
*iter
, *next
;
144 for (iter
= wine_rb_postorder_head(tree
->root
); iter
; iter
= next
)
146 next
= wine_rb_postorder_next(iter
);
147 callback(iter
, context
);
151 static inline void wine_rb_init(struct wine_rb_tree
*tree
, wine_rb_compare_func_t compare
)
153 tree
->compare
= compare
;
157 static inline void wine_rb_for_each_entry(struct wine_rb_tree
*tree
, wine_rb_traverse_func_t
*callback
, void *context
)
159 struct wine_rb_entry
*iter
;
160 WINE_RB_FOR_EACH(iter
, tree
) callback(iter
, context
);
163 static inline void wine_rb_clear(struct wine_rb_tree
*tree
, wine_rb_traverse_func_t
*callback
, void *context
)
165 /* Note that we use postorder here because the callback will likely free the entry. */
166 if (callback
) wine_rb_postorder(tree
, callback
, context
);
170 static inline void wine_rb_destroy(struct wine_rb_tree
*tree
, wine_rb_traverse_func_t
*callback
, void *context
)
172 wine_rb_clear(tree
, callback
, context
);
175 static inline struct wine_rb_entry
*wine_rb_get(const struct wine_rb_tree
*tree
, const void *key
)
177 struct wine_rb_entry
*entry
= tree
->root
;
180 int c
= tree
->compare(key
, entry
);
181 if (!c
) return entry
;
182 entry
= c
< 0 ? entry
->left
: entry
->right
;
187 static inline int wine_rb_put(struct wine_rb_tree
*tree
, const void *key
, struct wine_rb_entry
*entry
)
189 struct wine_rb_entry
**iter
= &tree
->root
, *parent
= tree
->root
;
196 c
= tree
->compare(key
, parent
);
198 else if (c
< 0) iter
= &parent
->left
;
199 else iter
= &parent
->right
;
202 entry
->flags
= WINE_RB_FLAG_RED
;
203 entry
->parent
= parent
;
208 while (wine_rb_is_red(entry
->parent
))
210 if (entry
->parent
== entry
->parent
->parent
->left
)
212 if (wine_rb_is_red(entry
->parent
->parent
->right
))
214 wine_rb_flip_color(entry
->parent
->parent
);
215 entry
= entry
->parent
->parent
;
219 if (entry
== entry
->parent
->right
)
221 entry
= entry
->parent
;
222 wine_rb_rotate_left(tree
, entry
);
224 entry
->parent
->flags
&= ~WINE_RB_FLAG_RED
;
225 entry
->parent
->parent
->flags
|= WINE_RB_FLAG_RED
;
226 wine_rb_rotate_right(tree
, entry
->parent
->parent
);
231 if (wine_rb_is_red(entry
->parent
->parent
->left
))
233 wine_rb_flip_color(entry
->parent
->parent
);
234 entry
= entry
->parent
->parent
;
238 if (entry
== entry
->parent
->left
)
240 entry
= entry
->parent
;
241 wine_rb_rotate_right(tree
, entry
);
243 entry
->parent
->flags
&= ~WINE_RB_FLAG_RED
;
244 entry
->parent
->parent
->flags
|= WINE_RB_FLAG_RED
;
245 wine_rb_rotate_left(tree
, entry
->parent
->parent
);
250 tree
->root
->flags
&= ~WINE_RB_FLAG_RED
;
255 static inline void wine_rb_remove(struct wine_rb_tree
*tree
, struct wine_rb_entry
*entry
)
257 struct wine_rb_entry
*iter
, *child
, *parent
, *w
;
260 if (entry
->right
&& entry
->left
)
261 for(iter
= entry
->right
; iter
->left
; iter
= iter
->left
);
265 child
= iter
->left
? iter
->left
: iter
->right
;
269 else if (iter
== iter
->parent
->left
)
270 iter
->parent
->left
= child
;
272 iter
->parent
->right
= child
;
274 if (child
) child
->parent
= iter
->parent
;
275 parent
= iter
->parent
;
277 need_fixup
= !wine_rb_is_red(iter
);
284 else if (entry
== iter
->parent
->left
)
285 iter
->parent
->left
= iter
;
287 iter
->parent
->right
= iter
;
289 if (iter
->right
) iter
->right
->parent
= iter
;
290 if (iter
->left
) iter
->left
->parent
= iter
;
291 if (parent
== entry
) parent
= iter
;
296 while (parent
&& !wine_rb_is_red(child
))
298 if (child
== parent
->left
)
301 if (wine_rb_is_red(w
))
303 w
->flags
&= ~WINE_RB_FLAG_RED
;
304 parent
->flags
|= WINE_RB_FLAG_RED
;
305 wine_rb_rotate_left(tree
, parent
);
308 if (wine_rb_is_red(w
->left
) || wine_rb_is_red(w
->right
))
310 if (!wine_rb_is_red(w
->right
))
312 w
->left
->flags
&= ~WINE_RB_FLAG_RED
;
313 w
->flags
|= WINE_RB_FLAG_RED
;
314 wine_rb_rotate_right(tree
, w
);
317 w
->flags
= (w
->flags
& ~WINE_RB_FLAG_RED
) | (parent
->flags
& WINE_RB_FLAG_RED
);
318 parent
->flags
&= ~WINE_RB_FLAG_RED
;
320 w
->right
->flags
&= ~WINE_RB_FLAG_RED
;
321 wine_rb_rotate_left(tree
, parent
);
329 if (wine_rb_is_red(w
))
331 w
->flags
&= ~WINE_RB_FLAG_RED
;
332 parent
->flags
|= WINE_RB_FLAG_RED
;
333 wine_rb_rotate_right(tree
, parent
);
336 if (wine_rb_is_red(w
->left
) || wine_rb_is_red(w
->right
))
338 if (!wine_rb_is_red(w
->left
))
340 w
->right
->flags
&= ~WINE_RB_FLAG_RED
;
341 w
->flags
|= WINE_RB_FLAG_RED
;
342 wine_rb_rotate_left(tree
, w
);
345 w
->flags
= (w
->flags
& ~WINE_RB_FLAG_RED
) | (parent
->flags
& WINE_RB_FLAG_RED
);
346 parent
->flags
&= ~WINE_RB_FLAG_RED
;
348 w
->left
->flags
&= ~WINE_RB_FLAG_RED
;
349 wine_rb_rotate_right(tree
, parent
);
354 w
->flags
|= WINE_RB_FLAG_RED
;
356 parent
= child
->parent
;
358 if (child
) child
->flags
&= ~WINE_RB_FLAG_RED
;
361 if (tree
->root
) tree
->root
->flags
&= ~WINE_RB_FLAG_RED
;
364 static inline void wine_rb_remove_key(struct wine_rb_tree
*tree
, const void *key
)
366 struct wine_rb_entry
*entry
= wine_rb_get(tree
, key
);
367 if (entry
) wine_rb_remove(tree
, entry
);
370 #endif /* __WINE_WINE_RBTREE_H */