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))
139 /* iterate through the tree using using postorder, making it safe to free the entry */
140 #define WINE_RB_FOR_EACH_DESTRUCTOR(cursor, cursor2, tree) \
141 for ((cursor) = wine_rb_postorder_head((tree)->root); \
142 (cursor) && (((cursor2) = wine_rb_postorder_next(cursor)) || 1); \
143 (cursor) = (cursor2))
145 /* iterate through the tree using a tree entry and postorder, making it safe to free the entry */
146 #define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR(elem, elem2, tree, type, field) \
147 for ((elem) = WINE_RB_ENTRY_VALUE(wine_rb_postorder_head((tree)->root), type, field); \
149 && (((elem2) = WINE_RB_ENTRY_VALUE(wine_rb_postorder_next(&(elem)->field), type, field)) || 1); \
153 static inline void wine_rb_postorder(struct wine_rb_tree
*tree
, wine_rb_traverse_func_t
*callback
, void *context
)
155 struct wine_rb_entry
*iter
, *next
;
156 WINE_RB_FOR_EACH_DESTRUCTOR(iter
, next
, tree
) callback(iter
, context
);
159 static inline void wine_rb_init(struct wine_rb_tree
*tree
, wine_rb_compare_func_t compare
)
161 tree
->compare
= compare
;
165 static inline void wine_rb_for_each_entry(struct wine_rb_tree
*tree
, wine_rb_traverse_func_t
*callback
, void *context
)
167 struct wine_rb_entry
*iter
;
168 WINE_RB_FOR_EACH(iter
, tree
) callback(iter
, context
);
171 static inline void wine_rb_clear(struct wine_rb_tree
*tree
, wine_rb_traverse_func_t
*callback
, void *context
)
173 /* Note that we use postorder here because the callback will likely free the entry. */
174 if (callback
) wine_rb_postorder(tree
, callback
, context
);
178 static inline void wine_rb_destroy(struct wine_rb_tree
*tree
, wine_rb_traverse_func_t
*callback
, void *context
)
180 wine_rb_clear(tree
, callback
, context
);
183 static inline struct wine_rb_entry
*wine_rb_get(const struct wine_rb_tree
*tree
, const void *key
)
185 struct wine_rb_entry
*entry
= tree
->root
;
188 int c
= tree
->compare(key
, entry
);
189 if (!c
) return entry
;
190 entry
= c
< 0 ? entry
->left
: entry
->right
;
195 static inline int wine_rb_put(struct wine_rb_tree
*tree
, const void *key
, struct wine_rb_entry
*entry
)
197 struct wine_rb_entry
**iter
= &tree
->root
, *parent
= tree
->root
;
204 c
= tree
->compare(key
, parent
);
206 else if (c
< 0) iter
= &parent
->left
;
207 else iter
= &parent
->right
;
210 entry
->flags
= WINE_RB_FLAG_RED
;
211 entry
->parent
= parent
;
216 while (wine_rb_is_red(entry
->parent
))
218 if (entry
->parent
== entry
->parent
->parent
->left
)
220 if (wine_rb_is_red(entry
->parent
->parent
->right
))
222 wine_rb_flip_color(entry
->parent
->parent
);
223 entry
= entry
->parent
->parent
;
227 if (entry
== entry
->parent
->right
)
229 entry
= entry
->parent
;
230 wine_rb_rotate_left(tree
, entry
);
232 entry
->parent
->flags
&= ~WINE_RB_FLAG_RED
;
233 entry
->parent
->parent
->flags
|= WINE_RB_FLAG_RED
;
234 wine_rb_rotate_right(tree
, entry
->parent
->parent
);
239 if (wine_rb_is_red(entry
->parent
->parent
->left
))
241 wine_rb_flip_color(entry
->parent
->parent
);
242 entry
= entry
->parent
->parent
;
246 if (entry
== entry
->parent
->left
)
248 entry
= entry
->parent
;
249 wine_rb_rotate_right(tree
, entry
);
251 entry
->parent
->flags
&= ~WINE_RB_FLAG_RED
;
252 entry
->parent
->parent
->flags
|= WINE_RB_FLAG_RED
;
253 wine_rb_rotate_left(tree
, entry
->parent
->parent
);
258 tree
->root
->flags
&= ~WINE_RB_FLAG_RED
;
263 static inline void wine_rb_remove(struct wine_rb_tree
*tree
, struct wine_rb_entry
*entry
)
265 struct wine_rb_entry
*iter
, *child
, *parent
, *w
;
268 if (entry
->right
&& entry
->left
)
269 for(iter
= entry
->right
; iter
->left
; iter
= iter
->left
);
273 child
= iter
->left
? iter
->left
: iter
->right
;
277 else if (iter
== iter
->parent
->left
)
278 iter
->parent
->left
= child
;
280 iter
->parent
->right
= child
;
282 if (child
) child
->parent
= iter
->parent
;
283 parent
= iter
->parent
;
285 need_fixup
= !wine_rb_is_red(iter
);
292 else if (entry
== iter
->parent
->left
)
293 iter
->parent
->left
= iter
;
295 iter
->parent
->right
= iter
;
297 if (iter
->right
) iter
->right
->parent
= iter
;
298 if (iter
->left
) iter
->left
->parent
= iter
;
299 if (parent
== entry
) parent
= iter
;
304 while (parent
&& !wine_rb_is_red(child
))
306 if (child
== parent
->left
)
309 if (wine_rb_is_red(w
))
311 w
->flags
&= ~WINE_RB_FLAG_RED
;
312 parent
->flags
|= WINE_RB_FLAG_RED
;
313 wine_rb_rotate_left(tree
, parent
);
316 if (wine_rb_is_red(w
->left
) || wine_rb_is_red(w
->right
))
318 if (!wine_rb_is_red(w
->right
))
320 w
->left
->flags
&= ~WINE_RB_FLAG_RED
;
321 w
->flags
|= WINE_RB_FLAG_RED
;
322 wine_rb_rotate_right(tree
, w
);
325 w
->flags
= (w
->flags
& ~WINE_RB_FLAG_RED
) | (parent
->flags
& WINE_RB_FLAG_RED
);
326 parent
->flags
&= ~WINE_RB_FLAG_RED
;
328 w
->right
->flags
&= ~WINE_RB_FLAG_RED
;
329 wine_rb_rotate_left(tree
, parent
);
337 if (wine_rb_is_red(w
))
339 w
->flags
&= ~WINE_RB_FLAG_RED
;
340 parent
->flags
|= WINE_RB_FLAG_RED
;
341 wine_rb_rotate_right(tree
, parent
);
344 if (wine_rb_is_red(w
->left
) || wine_rb_is_red(w
->right
))
346 if (!wine_rb_is_red(w
->left
))
348 w
->right
->flags
&= ~WINE_RB_FLAG_RED
;
349 w
->flags
|= WINE_RB_FLAG_RED
;
350 wine_rb_rotate_left(tree
, w
);
353 w
->flags
= (w
->flags
& ~WINE_RB_FLAG_RED
) | (parent
->flags
& WINE_RB_FLAG_RED
);
354 parent
->flags
&= ~WINE_RB_FLAG_RED
;
356 w
->left
->flags
&= ~WINE_RB_FLAG_RED
;
357 wine_rb_rotate_right(tree
, parent
);
362 w
->flags
|= WINE_RB_FLAG_RED
;
364 parent
= child
->parent
;
366 if (child
) child
->flags
&= ~WINE_RB_FLAG_RED
;
369 if (tree
->root
) tree
->root
->flags
&= ~WINE_RB_FLAG_RED
;
372 static inline void wine_rb_remove_key(struct wine_rb_tree
*tree
, const void *key
)
374 struct wine_rb_entry
*entry
= wine_rb_get(tree
, key
);
375 if (entry
) wine_rb_remove(tree
, entry
);
378 #endif /* __WINE_WINE_RBTREE_H */