1 /*
2 * Red-black search tree support
3 *
4 * Copyright 2009 Henri Verbeet
5 * Copyright 2009 Andrew Riedi
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
20 */
21
22 #ifndef __WINE_WINE_RBTREE_H
23 #define __WINE_WINE_RBTREE_H
24
25 #define WINE_RB_ENTRY_VALUE(element, type, field) \
26 ((type *)((char *)(element) - FIELD_OFFSET(type, field)))
27
28 struct wine_rb_entry
29 {
30 struct wine_rb_entry *left;
31 struct wine_rb_entry *right;
32 unsigned int flags;
33 };
34
35 struct wine_rb_stack
36 {
37 struct wine_rb_entry ***entries;
38 size_t count;
39 size_t size;
40 };
41
42 struct wine_rb_functions
43 {
44 void *(*alloc)(size_t size);
45 void *(*realloc)(void *ptr, size_t size);
46 void (*free)(void *ptr);
47 int (*compare)(const void *key, const struct wine_rb_entry *entry);
48 };
49
50 struct wine_rb_tree
51 {
52 const struct wine_rb_functions *functions;
53 struct wine_rb_entry *root;
54 struct wine_rb_stack stack;
55 };
56
57 typedef void (wine_rb_traverse_func_t)(struct wine_rb_entry *entry, void *context);
58
59 #define WINE_RB_FLAG_RED 0x1
60 #define WINE_RB_FLAG_STOP 0x2
61 #define WINE_RB_FLAG_TRAVERSED_LEFT 0x4
62 #define WINE_RB_FLAG_TRAVERSED_RIGHT 0x8
63
64 static inline void wine_rb_stack_clear(struct wine_rb_stack *stack)
65 {
66 stack->count = 0;
67 }
68
69 static inline void wine_rb_stack_push(struct wine_rb_stack *stack, struct wine_rb_entry **entry)
70 {
71 stack->entries[stack->count++] = entry;
72 }
73
74 static inline int wine_rb_ensure_stack_size(struct wine_rb_tree *tree, size_t size)
75 {
76 struct wine_rb_stack *stack = &tree->stack;
77
78 if (size > stack->size)
79 {
80 size_t new_size = stack->size << 1;
81 struct wine_rb_entry ***new_entries = tree->functions->realloc(stack->entries,
82 new_size * sizeof(*stack->entries));
83
84 if (!new_entries) return -1;
85
86 stack->entries = new_entries;
87 stack->size = new_size;
88 }
89
90 return 0;
91 }
92
93 static inline int wine_rb_is_red(struct wine_rb_entry *entry)
94 {
95 return entry && (entry->flags & WINE_RB_FLAG_RED);
96 }
97
98 static inline void wine_rb_rotate_left(struct wine_rb_entry **entry)
99 {
100 struct wine_rb_entry *e = *entry;
101 struct wine_rb_entry *right = e->right;
102
103 e->right = right->left;
104 right->left = e;
105 right->flags &= ~WINE_RB_FLAG_RED;
106 right->flags |= e->flags & WINE_RB_FLAG_RED;
107 e->flags |= WINE_RB_FLAG_RED;
108 *entry = right;
109 }
110
111 static inline void wine_rb_rotate_right(struct wine_rb_entry **entry)
112 {
113 struct wine_rb_entry *e = *entry;
114 struct wine_rb_entry *left = e->left;
115
116 e->left = left->right;
117 left->right = e;
118 left->flags &= ~WINE_RB_FLAG_RED;
119 left->flags |= e->flags & WINE_RB_FLAG_RED;
120 e->flags |= WINE_RB_FLAG_RED;
121 *entry = left;
122 }
123
124 static inline void wine_rb_flip_color(struct wine_rb_entry *entry)
125 {
126 entry->flags ^= WINE_RB_FLAG_RED;
127 entry->left->flags ^= WINE_RB_FLAG_RED;
128 entry->right->flags ^= WINE_RB_FLAG_RED;
129 }
130
131 static inline void wine_rb_fixup(struct wine_rb_stack *stack)
132 {
133 while (stack->count)
134 {
135 struct wine_rb_entry **entry = stack->entries[stack->count - 1];
136
137 if ((*entry)->flags & WINE_RB_FLAG_STOP)
138 {
139 (*entry)->flags &= ~WINE_RB_FLAG_STOP;
140 return;
141 }
142
143 if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(entry);
144 if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(entry);
145 if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->right)) wine_rb_flip_color(*entry);
146 --stack->count;
147 }
148 }
149
150 static inline void wine_rb_move_red_left(struct wine_rb_entry **entry)
151 {
152 wine_rb_flip_color(*entry);
153 if (wine_rb_is_red((*entry)->right->left))
154 {
155 wine_rb_rotate_right(&(*entry)->right);
156 wine_rb_rotate_left(entry);
157 wine_rb_flip_color(*entry);
158 }
159 }
160
161 static inline void wine_rb_move_red_right(struct wine_rb_entry **entry)
162 {
163 wine_rb_flip_color(*entry);
164 if (wine_rb_is_red((*entry)->left->left))
165 {
166 wine_rb_rotate_right(entry);
167 wine_rb_flip_color(*entry);
168 }
169 }
170
171 static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
172 {
173 struct wine_rb_entry **entry;
174
175 if (!tree->root) return;
176
177 for (entry = &tree->root;;)
178 {
179 struct wine_rb_entry *e = *entry;
180
181 if (e->left && !(e->flags & WINE_RB_FLAG_TRAVERSED_LEFT))
182 {
183 wine_rb_stack_push(&tree->stack, entry);
184 e->flags |= WINE_RB_FLAG_TRAVERSED_LEFT;
185 entry = &e->left;
186 continue;
187 }
188
189 if (e->right && !(e->flags & WINE_RB_FLAG_TRAVERSED_RIGHT))
190 {
191 wine_rb_stack_push(&tree->stack, entry);
192 e->flags |= WINE_RB_FLAG_TRAVERSED_RIGHT;
193 entry = &e->right;
194 continue;
195 }
196
197 e->flags &= ~(WINE_RB_FLAG_TRAVERSED_LEFT | WINE_RB_FLAG_TRAVERSED_RIGHT);
198 callback(e, context);
199
200 if (!tree->stack.count) break;
201 entry = tree->stack.entries[--tree->stack.count];
202 }
203 }
204
205 static inline int wine_rb_init(struct wine_rb_tree *tree, const struct wine_rb_functions *functions)
206 {
207 tree->functions = functions;
208 tree->root = NULL;
209
210 tree->stack.entries = functions->alloc(16 * sizeof(*tree->stack.entries));
211 if (!tree->stack.entries) return -1;
212 tree->stack.size = 16;
213 tree->stack.count = 0;
214
215 return 0;
216 }
217
218 static inline void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
219 {
220 wine_rb_postorder(tree, callback, context);
221 }
222
223 static inline void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
224 {
225 /* Note that we use postorder here because the callback will likely free the entry. */
226 if (callback) wine_rb_postorder(tree, callback, context);
227
228 tree->root = NULL;
229 tree->functions->free(tree->stack.entries);
230 }
231
232 static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)
233 {
234 struct wine_rb_entry *entry = tree->root;
235 while (entry)
236 {
237 int c = tree->functions->compare(key, entry);
238 if (!c) return entry;
239 entry = c < 0 ? entry->left : entry->right;
240 }
241 return NULL;
242 }
243
244 static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
245 {
246 struct wine_rb_entry **parent = &tree->root;
247 size_t black_height = 1;
248
249 while (*parent)
250 {
251 int c;
252
253 if (!wine_rb_is_red(*parent)) ++black_height;
254
255 wine_rb_stack_push(&tree->stack, parent);
256
257 c = tree->functions->compare(key, *parent);
258 if (!c)
259 {
260 wine_rb_stack_clear(&tree->stack);
261 return -1;
262 }
263 else if (c < 0) parent = &(*parent)->left;
264 else parent = &(*parent)->right;
265 }
266
267 /* After insertion, the path length to any node should be <= (black_height + 1) * 2. */
268 if (wine_rb_ensure_stack_size(tree, black_height << 1) == -1)
269 {
270 wine_rb_stack_clear(&tree->stack);
271 return -1;
272 }
273
274 entry->flags = WINE_RB_FLAG_RED;
275 entry->left = NULL;
276 entry->right = NULL;
277 *parent = entry;
278
279 wine_rb_fixup(&tree->stack);
280 tree->root->flags &= ~WINE_RB_FLAG_RED;
281
282 return 0;
283 }
284
285 static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key)
286 {
287 struct wine_rb_entry **entry = &tree->root;
288
289 while (*entry)
290 {
291 if (tree->functions->compare(key, *entry) < 0)
292 {
293 wine_rb_stack_push(&tree->stack, entry);
294 if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(entry);
295 entry = &(*entry)->left;
296 }
297 else
298 {
299 if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(entry);
300 if (!tree->functions->compare(key, *entry) && !(*entry)->right)
301 {
302 *entry = NULL;
303 break;
304 }
305 if (!wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->right->left))
306 wine_rb_move_red_right(entry);
307 if (!tree->functions->compare(key, *entry))
308 {
309 struct wine_rb_entry **e = &(*entry)->right;
310 struct wine_rb_entry *m = *e;
311 while (m->left) m = m->left;
312
313 wine_rb_stack_push(&tree->stack, entry);
314 (*entry)->flags |= WINE_RB_FLAG_STOP;
315
316 while ((*e)->left)
317 {
318 wine_rb_stack_push(&tree->stack, e);
319 if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(e);
320 e = &(*e)->left;
321 }
322 *e = NULL;
323 wine_rb_fixup(&tree->stack);
324
325 *m = **entry;
326 *entry = m;
327
328 break;
329 }
330 else
331 {
332 wine_rb_stack_push(&tree->stack, entry);
333 entry = &(*entry)->right;
334 }
335 }
336 }
337
338 wine_rb_fixup(&tree->stack);
339 if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
340 }
341
342 #endif /* __WINE_WINE_RBTREE_H */
343
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.