RTEMS 6.3
Loading...
Searching...
No Matches
bsd-tree.h
Go to the documentation of this file.
1/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */
2/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
3/* $FreeBSD: head/sys/sys/tree.h 347360 2019-05-08 18:47:00Z trasz $ */
4
19
20/*-
21 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
22 *
23 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
24 * All rights reserved.
25 *
26 * Redistribution and use in source and binary forms, with or without
27 * modification, are permitted provided that the following conditions
28 * are met:
29 * 1. Redistributions of source code must retain the above copyright
30 * notice, this list of conditions and the following disclaimer.
31 * 2. Redistributions in binary form must reproduce the above copyright
32 * notice, this list of conditions and the following disclaimer in the
33 * documentation and/or other materials provided with the distribution.
34 *
35 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
36 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
38 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
39 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
40 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
41 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
42 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
43 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
44 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45 */
46
47#ifndef _RTEMS_SCORE_BSD_TREE_H_
48#define _RTEMS_SCORE_BSD_TREE_H_
49
50#include <sys/cdefs.h>
51
52/*
53 * This file defines data structures for different types of trees:
54 * splay trees and red-black trees.
55 *
56 * A splay tree is a self-organizing data structure. Every operation
57 * on the tree causes a splay to happen. The splay moves the requested
58 * node to the root of the tree and partly rebalances it.
59 *
60 * This has the benefit that request locality causes faster lookups as
61 * the requested nodes move to the top of the tree. On the other hand,
62 * every lookup causes memory writes.
63 *
64 * The Balance Theorem bounds the total access time for m operations
65 * and n inserts on an initially empty tree as O((m + n)lg n). The
66 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
67 *
68 * A red-black tree is a binary search tree with the node color as an
69 * extra attribute. It fulfills a set of conditions:
70 * - every search path from the root to a leaf consists of the
71 * same number of black nodes,
72 * - each red node (except for the root) has a black parent,
73 * - each leaf node is black.
74 *
75 * Every operation on a red-black tree is bounded as O(lg n).
76 * The maximum height of a red-black tree is 2lg (n+1).
77 */
78
79#define RTEMS_SPLAY_HEAD(name, type) \
80struct name { \
81 struct type *sph_root; /* root of the tree */ \
82}
83
84#define RTEMS_SPLAY_INITIALIZER(root) \
85 { NULL }
86
87#define RTEMS_SPLAY_INIT(root) do { \
88 (root)->sph_root = NULL; \
89} while (/*CONSTCOND*/ 0)
90
91#define RTEMS_SPLAY_ENTRY(type) \
92struct { \
93 struct type *spe_left; /* left element */ \
94 struct type *spe_right; /* right element */ \
95}
96
97#define RTEMS_SPLAY_LEFT(elm, field) (elm)->field.spe_left
98#define RTEMS_SPLAY_RIGHT(elm, field) (elm)->field.spe_right
99#define RTEMS_SPLAY_ROOT(head) (head)->sph_root
100#define RTEMS_SPLAY_EMPTY(head) (RTEMS_SPLAY_ROOT(head) == NULL)
101
102/* RTEMS_SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold RTEMS_SPLAY_{RIGHT,LEFT} */
103#define RTEMS_SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
104 RTEMS_SPLAY_LEFT((head)->sph_root, field) = RTEMS_SPLAY_RIGHT(tmp, field); \
105 RTEMS_SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
106 (head)->sph_root = tmp; \
107} while (/*CONSTCOND*/ 0)
108
109#define RTEMS_SPLAY_ROTATE_LEFT(head, tmp, field) do { \
110 RTEMS_SPLAY_RIGHT((head)->sph_root, field) = RTEMS_SPLAY_LEFT(tmp, field); \
111 RTEMS_SPLAY_LEFT(tmp, field) = (head)->sph_root; \
112 (head)->sph_root = tmp; \
113} while (/*CONSTCOND*/ 0)
114
115#define RTEMS_SPLAY_LINKLEFT(head, tmp, field) do { \
116 RTEMS_SPLAY_LEFT(tmp, field) = (head)->sph_root; \
117 tmp = (head)->sph_root; \
118 (head)->sph_root = RTEMS_SPLAY_LEFT((head)->sph_root, field); \
119} while (/*CONSTCOND*/ 0)
120
121#define RTEMS_SPLAY_LINKRIGHT(head, tmp, field) do { \
122 RTEMS_SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
123 tmp = (head)->sph_root; \
124 (head)->sph_root = RTEMS_SPLAY_RIGHT((head)->sph_root, field); \
125} while (/*CONSTCOND*/ 0)
126
127#define RTEMS_SPLAY_ASSEMBLE(head, node, left, right, field) do { \
128 RTEMS_SPLAY_RIGHT(left, field) = RTEMS_SPLAY_LEFT((head)->sph_root, field); \
129 RTEMS_SPLAY_LEFT(right, field) = RTEMS_SPLAY_RIGHT((head)->sph_root, field);\
130 RTEMS_SPLAY_LEFT((head)->sph_root, field) = RTEMS_SPLAY_RIGHT(node, field); \
131 RTEMS_SPLAY_RIGHT((head)->sph_root, field) = RTEMS_SPLAY_LEFT(node, field); \
132} while (/*CONSTCOND*/ 0)
133
134/* Generates prototypes and inline functions */
135
136#define RTEMS_SPLAY_PROTOTYPE(name, type, field, cmp) \
137void name##_SPLAY(struct name *, struct type *); \
138void name##_RTEMS_SPLAY_MINMAX(struct name *, int); \
139struct type *name##_RTEMS_SPLAY_INSERT(struct name *, struct type *); \
140struct type *name##_RTEMS_SPLAY_REMOVE(struct name *, struct type *); \
141 \
142/* Finds the node with the same key as elm */ \
143static __unused __inline struct type * \
144name##_RTEMS_SPLAY_FIND(struct name *head, struct type *elm) \
145{ \
146 if (RTEMS_SPLAY_EMPTY(head)) \
147 return(NULL); \
148 name##_SPLAY(head, elm); \
149 if ((cmp)(elm, (head)->sph_root) == 0) \
150 return (head->sph_root); \
151 return (NULL); \
152} \
153 \
154static __unused __inline struct type * \
155name##_RTEMS_SPLAY_NEXT(struct name *head, struct type *elm) \
156{ \
157 name##_SPLAY(head, elm); \
158 if (RTEMS_SPLAY_RIGHT(elm, field) != NULL) { \
159 elm = RTEMS_SPLAY_RIGHT(elm, field); \
160 while (RTEMS_SPLAY_LEFT(elm, field) != NULL) { \
161 elm = RTEMS_SPLAY_LEFT(elm, field); \
162 } \
163 } else \
164 elm = NULL; \
165 return (elm); \
166} \
167 \
168static __unused __inline struct type * \
169name##_RTEMS_SPLAY_MIN_MAX(struct name *head, int val) \
170{ \
171 name##_RTEMS_SPLAY_MINMAX(head, val); \
172 return (RTEMS_SPLAY_ROOT(head)); \
173}
174
175/* Main splay operation.
176 * Moves node close to the key of elm to top
177 */
178#define RTEMS_SPLAY_GENERATE(name, type, field, cmp) \
179struct type * \
180name##_RTEMS_SPLAY_INSERT(struct name *head, struct type *elm) \
181{ \
182 if (RTEMS_SPLAY_EMPTY(head)) { \
183 RTEMS_SPLAY_LEFT(elm, field) = RTEMS_SPLAY_RIGHT(elm, field) = NULL; \
184 } else { \
185 int __comp; \
186 name##_SPLAY(head, elm); \
187 __comp = (cmp)(elm, (head)->sph_root); \
188 if(__comp < 0) { \
189 RTEMS_SPLAY_LEFT(elm, field) = RTEMS_SPLAY_LEFT((head)->sph_root, field);\
190 RTEMS_SPLAY_RIGHT(elm, field) = (head)->sph_root; \
191 RTEMS_SPLAY_LEFT((head)->sph_root, field) = NULL; \
192 } else if (__comp > 0) { \
193 RTEMS_SPLAY_RIGHT(elm, field) = RTEMS_SPLAY_RIGHT((head)->sph_root, field);\
194 RTEMS_SPLAY_LEFT(elm, field) = (head)->sph_root; \
195 RTEMS_SPLAY_RIGHT((head)->sph_root, field) = NULL; \
196 } else \
197 return ((head)->sph_root); \
198 } \
199 (head)->sph_root = (elm); \
200 return (NULL); \
201} \
202 \
203struct type * \
204name##_RTEMS_SPLAY_REMOVE(struct name *head, struct type *elm) \
205{ \
206 struct type *__tmp; \
207 if (RTEMS_SPLAY_EMPTY(head)) \
208 return (NULL); \
209 name##_SPLAY(head, elm); \
210 if ((cmp)(elm, (head)->sph_root) == 0) { \
211 if (RTEMS_SPLAY_LEFT((head)->sph_root, field) == NULL) { \
212 (head)->sph_root = RTEMS_SPLAY_RIGHT((head)->sph_root, field);\
213 } else { \
214 __tmp = RTEMS_SPLAY_RIGHT((head)->sph_root, field); \
215 (head)->sph_root = RTEMS_SPLAY_LEFT((head)->sph_root, field);\
216 name##_SPLAY(head, elm); \
217 RTEMS_SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
218 } \
219 return (elm); \
220 } \
221 return (NULL); \
222} \
223 \
224void \
225name##_SPLAY(struct name *head, struct type *elm) \
226{ \
227 struct type __node, *__left, *__right, *__tmp; \
228 int __comp; \
229\
230 RTEMS_SPLAY_LEFT(&__node, field) = RTEMS_SPLAY_RIGHT(&__node, field) = NULL;\
231 __left = __right = &__node; \
232\
233 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
234 if (__comp < 0) { \
235 __tmp = RTEMS_SPLAY_LEFT((head)->sph_root, field); \
236 if (__tmp == NULL) \
237 break; \
238 if ((cmp)(elm, __tmp) < 0){ \
239 RTEMS_SPLAY_ROTATE_RIGHT(head, __tmp, field); \
240 if (RTEMS_SPLAY_LEFT((head)->sph_root, field) == NULL)\
241 break; \
242 } \
243 RTEMS_SPLAY_LINKLEFT(head, __right, field); \
244 } else if (__comp > 0) { \
245 __tmp = RTEMS_SPLAY_RIGHT((head)->sph_root, field); \
246 if (__tmp == NULL) \
247 break; \
248 if ((cmp)(elm, __tmp) > 0){ \
249 RTEMS_SPLAY_ROTATE_LEFT(head, __tmp, field); \
250 if (RTEMS_SPLAY_RIGHT((head)->sph_root, field) == NULL)\
251 break; \
252 } \
253 RTEMS_SPLAY_LINKRIGHT(head, __left, field); \
254 } \
255 } \
256 RTEMS_SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
257} \
258 \
259/* Splay with either the minimum or the maximum element \
260 * Used to find minimum or maximum element in tree. \
261 */ \
262void name##_RTEMS_SPLAY_MINMAX(struct name *head, int __comp) \
263{ \
264 struct type __node, *__left, *__right, *__tmp; \
265\
266 RTEMS_SPLAY_LEFT(&__node, field) = RTEMS_SPLAY_RIGHT(&__node, field) = NULL;\
267 __left = __right = &__node; \
268\
269 while (1) { \
270 if (__comp < 0) { \
271 __tmp = RTEMS_SPLAY_LEFT((head)->sph_root, field); \
272 if (__tmp == NULL) \
273 break; \
274 if (__comp < 0){ \
275 RTEMS_SPLAY_ROTATE_RIGHT(head, __tmp, field); \
276 if (RTEMS_SPLAY_LEFT((head)->sph_root, field) == NULL)\
277 break; \
278 } \
279 RTEMS_SPLAY_LINKLEFT(head, __right, field); \
280 } else if (__comp > 0) { \
281 __tmp = RTEMS_SPLAY_RIGHT((head)->sph_root, field); \
282 if (__tmp == NULL) \
283 break; \
284 if (__comp > 0) { \
285 RTEMS_SPLAY_ROTATE_LEFT(head, __tmp, field); \
286 if (RTEMS_SPLAY_RIGHT((head)->sph_root, field) == NULL)\
287 break; \
288 } \
289 RTEMS_SPLAY_LINKRIGHT(head, __left, field); \
290 } \
291 } \
292 RTEMS_SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
293}
294
295#define RTEMS_SPLAY_NEGINF -1
296#define RTEMS_SPLAY_INF 1
297
298#define RTEMS_SPLAY_INSERT(name, x, y) name##_RTEMS_SPLAY_INSERT(x, y)
299#define RTEMS_SPLAY_REMOVE(name, x, y) name##_RTEMS_SPLAY_REMOVE(x, y)
300#define RTEMS_SPLAY_FIND(name, x, y) name##_RTEMS_SPLAY_FIND(x, y)
301#define RTEMS_SPLAY_NEXT(name, x, y) name##_RTEMS_SPLAY_NEXT(x, y)
302#define RTEMS_SPLAY_MIN(name, x) (RTEMS_SPLAY_EMPTY(x) ? NULL \
303 : name##_RTEMS_SPLAY_MIN_MAX(x, RTEMS_SPLAY_NEGINF))
304#define RTEMS_SPLAY_MAX(name, x) (RTEMS_SPLAY_EMPTY(x) ? NULL \
305 : name##_RTEMS_SPLAY_MIN_MAX(x, RTEMS_SPLAY_INF))
306
307#define RTEMS_SPLAY_FOREACH(x, name, head) \
308 for ((x) = RTEMS_SPLAY_MIN(name, head); \
309 (x) != NULL; \
310 (x) = RTEMS_SPLAY_NEXT(name, head, x))
311
312/* Macros that define a red-black tree */
313#define RTEMS_RB_HEAD(name, type) \
314struct name { \
315 struct type *rbh_root; /* root of the tree */ \
316}
317
318#define RTEMS_RB_INITIALIZER(root) \
319 { NULL }
320
321#define RTEMS_RB_INIT(root) do { \
322 (root)->rbh_root = NULL; \
323} while (/*CONSTCOND*/ 0)
324
325#define RTEMS_RB_BLACK 0
326#define RTEMS_RB_RED 1
327#define RTEMS_RB_ENTRY(type) \
328struct { \
329 struct type *rbe_left; /* left element */ \
330 struct type *rbe_right; /* right element */ \
331 struct type *rbe_parent; /* parent element */ \
332 int rbe_color; /* node color */ \
333}
334
335#define RTEMS_RB_LEFT(elm, field) (elm)->field.rbe_left
336#define RTEMS_RB_RIGHT(elm, field) (elm)->field.rbe_right
337#define RTEMS_RB_PARENT(elm, field) (elm)->field.rbe_parent
338#define RTEMS_RB_COLOR(elm, field) (elm)->field.rbe_color
339#define RTEMS_RB_ISRED(elm, field) ((elm) != NULL && RTEMS_RB_COLOR(elm, field) == RTEMS_RB_RED)
340#define RTEMS_RB_ROOT(head) (head)->rbh_root
341#define RTEMS_RB_EMPTY(head) (RTEMS_RB_ROOT(head) == NULL)
342
343#define RTEMS_RB_SET_PARENT(dst, src, field) do { \
344 RTEMS_RB_PARENT(dst, field) = src; \
345} while (/*CONSTCOND*/ 0)
346
347#define RTEMS_RB_SET(elm, parent, field) do { \
348 RTEMS_RB_SET_PARENT(elm, parent, field); \
349 RTEMS_RB_LEFT(elm, field) = RTEMS_RB_RIGHT(elm, field) = NULL; \
350 RTEMS_RB_COLOR(elm, field) = RTEMS_RB_RED; \
351} while (/*CONSTCOND*/ 0)
352
353#define RTEMS_RB_SET_BLACKRED(black, red, field) do { \
354 RTEMS_RB_COLOR(black, field) = RTEMS_RB_BLACK; \
355 RTEMS_RB_COLOR(red, field) = RTEMS_RB_RED; \
356} while (/*CONSTCOND*/ 0)
357
358/*
359 * Something to be invoked in a loop at the root of every modified subtree,
360 * from the bottom up to the root, to update augmented node data.
361 */
362#ifndef RTEMS_RB_AUGMENT
363#define RTEMS_RB_AUGMENT(x) break
364#endif
365
366#define RTEMS_RB_SWAP_CHILD(head, out, in, field) do { \
367 if (RTEMS_RB_PARENT(out, field) == NULL) \
368 RTEMS_RB_ROOT(head) = (in); \
369 else if ((out) == RTEMS_RB_LEFT(RTEMS_RB_PARENT(out, field), field)) \
370 RTEMS_RB_LEFT(RTEMS_RB_PARENT(out, field), field) = (in); \
371 else \
372 RTEMS_RB_RIGHT(RTEMS_RB_PARENT(out, field), field) = (in); \
373} while (/*CONSTCOND*/ 0)
374
375#define RTEMS_RB_ROTATE_LEFT(head, elm, tmp, field) do { \
376 (tmp) = RTEMS_RB_RIGHT(elm, field); \
377 if ((RTEMS_RB_RIGHT(elm, field) = RTEMS_RB_LEFT(tmp, field)) != NULL) { \
378 RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(elm, field), elm, field); \
379 } \
380 RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field); \
381 RTEMS_RB_SWAP_CHILD(head, elm, tmp, field); \
382 RTEMS_RB_LEFT(tmp, field) = (elm); \
383 RTEMS_RB_SET_PARENT(elm, tmp, field); \
384 RTEMS_RB_AUGMENT(elm); \
385} while (/*CONSTCOND*/ 0)
386
387#define RTEMS_RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
388 (tmp) = RTEMS_RB_LEFT(elm, field); \
389 if ((RTEMS_RB_LEFT(elm, field) = RTEMS_RB_RIGHT(tmp, field)) != NULL) { \
390 RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(elm, field), elm, field); \
391 } \
392 RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field); \
393 RTEMS_RB_SWAP_CHILD(head, elm, tmp, field); \
394 RTEMS_RB_RIGHT(tmp, field) = (elm); \
395 RTEMS_RB_SET_PARENT(elm, tmp, field); \
396 RTEMS_RB_AUGMENT(elm); \
397} while (/*CONSTCOND*/ 0)
398
399/*
400 * The RTEMS_RB_PARENT_ROTATE_LEFT() and RTEMS_RB_PARENT_ROTATE_RIGHT() rotations are
401 * specialized versions of RTEMS_RB_ROTATE_LEFT() and RTEMS_RB_ROTATE_RIGHT() which may be
402 * used if the parent node exists and the direction of the child element is
403 * known.
404 */
405
406#define RTEMS_RB_PARENT_ROTATE_LEFT(parent, left, tmp, field) do { \
407 (tmp) = RTEMS_RB_RIGHT(left, field); \
408 if ((RTEMS_RB_RIGHT(left, field) = RTEMS_RB_LEFT(tmp, field)) != NULL) { \
409 RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(left, field), left, field); \
410 } \
411 RTEMS_RB_SET_PARENT(tmp, parent, field); \
412 RTEMS_RB_LEFT(parent, field) = (tmp); \
413 RTEMS_RB_LEFT(tmp, field) = (left); \
414 RTEMS_RB_SET_PARENT(left, tmp, field); \
415 RTEMS_RB_AUGMENT(left); \
416} while (/*CONSTCOND*/ 0)
417
418#define RTEMS_RB_PARENT_ROTATE_RIGHT(parent, right, tmp, field) do { \
419 (tmp) = RTEMS_RB_LEFT(right, field); \
420 if ((RTEMS_RB_LEFT(right, field) = RTEMS_RB_RIGHT(tmp, field)) != NULL) { \
421 RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(right, field), right, field); \
422 } \
423 RTEMS_RB_SET_PARENT(tmp, parent, field); \
424 RTEMS_RB_RIGHT(parent, field) = (tmp); \
425 RTEMS_RB_RIGHT(tmp, field) = (right); \
426 RTEMS_RB_SET_PARENT(right, tmp, field); \
427 RTEMS_RB_AUGMENT(right); \
428} while (/*CONSTCOND*/ 0)
429
430/*
431 * The RTEMS_RB_RED_ROTATE_LEFT() and RTEMS_RB_RED_ROTATE_RIGHT() rotations are specialized
432 * versions of RTEMS_RB_ROTATE_LEFT() and RTEMS_RB_ROTATE_RIGHT() which may be used if we
433 * rotate an element with a red child which has a black sibling. Such a red
434 * node must have at least two child nodes so that the following red-black tree
435 * invariant is fulfilled:
436 *
437 * Every path from a given node to any of its descendant NULL nodes goes
438 * through the same number of black nodes.
439 *
440 * elm (could be the root)
441 * / \
442 * BLACK RED (left or right child)
443 * / \
444 * BLACK BLACK
445 */
446
447#define RTEMS_RB_RED_ROTATE_LEFT(head, elm, tmp, field) do { \
448 (tmp) = RTEMS_RB_RIGHT(elm, field); \
449 RTEMS_RB_RIGHT(elm, field) = RTEMS_RB_LEFT(tmp, field); \
450 RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(elm, field), elm, field); \
451 RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field); \
452 RTEMS_RB_SWAP_CHILD(head, elm, tmp, field); \
453 RTEMS_RB_LEFT(tmp, field) = (elm); \
454 RTEMS_RB_SET_PARENT(elm, tmp, field); \
455 RTEMS_RB_AUGMENT(elm); \
456} while (/*CONSTCOND*/ 0)
457
458#define RTEMS_RB_RED_ROTATE_RIGHT(head, elm, tmp, field) do { \
459 (tmp) = RTEMS_RB_LEFT(elm, field); \
460 RTEMS_RB_LEFT(elm, field) = RTEMS_RB_RIGHT(tmp, field); \
461 RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(elm, field), elm, field); \
462 RTEMS_RB_SET_PARENT(tmp, RTEMS_RB_PARENT(elm, field), field); \
463 RTEMS_RB_SWAP_CHILD(head, elm, tmp, field); \
464 RTEMS_RB_RIGHT(tmp, field) = (elm); \
465 RTEMS_RB_SET_PARENT(elm, tmp, field); \
466 RTEMS_RB_AUGMENT(elm); \
467} while (/*CONSTCOND*/ 0)
468
469/* Generates prototypes and inline functions */
470#define RTEMS_RB_PROTOTYPE(name, type, field, cmp) \
471 RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
472#define RTEMS_RB_PROTOTYPE_STATIC(name, type, field, cmp) \
473 RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
474#define RTEMS_RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
475 RTEMS_RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
476 RTEMS_RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
477 RTEMS_RB_PROTOTYPE_INSERT(name, type, attr); \
478 RTEMS_RB_PROTOTYPE_REMOVE(name, type, attr); \
479 RTEMS_RB_PROTOTYPE_FIND(name, type, attr); \
480 RTEMS_RB_PROTOTYPE_NFIND(name, type, attr); \
481 RTEMS_RB_PROTOTYPE_NEXT(name, type, attr); \
482 RTEMS_RB_PROTOTYPE_PREV(name, type, attr); \
483 RTEMS_RB_PROTOTYPE_MINMAX(name, type, attr); \
484 RTEMS_RB_PROTOTYPE_REINSERT(name, type, attr);
485#define RTEMS_RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
486 attr void name##_RTEMS_RB_INSERT_COLOR(struct name *, struct type *)
487#define RTEMS_RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
488 attr void name##_RTEMS_RB_REMOVE_COLOR(struct name *, struct type *)
489#define RTEMS_RB_PROTOTYPE_REMOVE(name, type, attr) \
490 attr struct type *name##_RTEMS_RB_REMOVE(struct name *, struct type *)
491#define RTEMS_RB_PROTOTYPE_INSERT(name, type, attr) \
492 attr struct type *name##_RTEMS_RB_INSERT(struct name *, struct type *)
493#define RTEMS_RB_PROTOTYPE_FIND(name, type, attr) \
494 attr struct type *name##_RTEMS_RB_FIND(struct name *, struct type *)
495#define RTEMS_RB_PROTOTYPE_NFIND(name, type, attr) \
496 attr struct type *name##_RTEMS_RB_NFIND(struct name *, struct type *)
497#define RTEMS_RB_PROTOTYPE_NEXT(name, type, attr) \
498 attr struct type *name##_RTEMS_RB_NEXT(struct type *)
499#define RTEMS_RB_PROTOTYPE_PREV(name, type, attr) \
500 attr struct type *name##_RTEMS_RB_PREV(struct type *)
501#define RTEMS_RB_PROTOTYPE_MINMAX(name, type, attr) \
502 attr struct type *name##_RTEMS_RB_MINMAX(struct name *, int)
503#define RTEMS_RB_PROTOTYPE_REINSERT(name, type, attr) \
504 attr struct type *name##_RTEMS_RB_REINSERT(struct name *, struct type *)
505
506/* Main rb operation.
507 * Moves node close to the key of elm to top
508 */
509#define RTEMS_RB_GENERATE(name, type, field, cmp) \
510 RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp,)
511#define RTEMS_RB_GENERATE_STATIC(name, type, field, cmp) \
512 RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
513#define RTEMS_RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
514 RTEMS_RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
515 RTEMS_RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
516 RTEMS_RB_GENERATE_INSERT(name, type, field, cmp, attr) \
517 RTEMS_RB_GENERATE_REMOVE(name, type, field, attr) \
518 RTEMS_RB_GENERATE_FIND(name, type, field, cmp, attr) \
519 RTEMS_RB_GENERATE_NFIND(name, type, field, cmp, attr) \
520 RTEMS_RB_GENERATE_NEXT(name, type, field, attr) \
521 RTEMS_RB_GENERATE_PREV(name, type, field, attr) \
522 RTEMS_RB_GENERATE_MINMAX(name, type, field, attr) \
523 RTEMS_RB_GENERATE_REINSERT(name, type, field, cmp, attr)
524
525
526#define RTEMS_RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
527attr void \
528name##_RTEMS_RB_INSERT_COLOR(struct name *head, struct type *elm) \
529{ \
530 struct type *parent, *gparent, *tmp; \
531 while (RTEMS_RB_ISRED((parent = RTEMS_RB_PARENT(elm, field)), field)) { \
532 gparent = RTEMS_RB_PARENT(parent, field); \
533 if (parent == RTEMS_RB_LEFT(gparent, field)) { \
534 tmp = RTEMS_RB_RIGHT(gparent, field); \
535 if (RTEMS_RB_ISRED(tmp, field)) { \
536 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_BLACK; \
537 RTEMS_RB_SET_BLACKRED(parent, gparent, field);\
538 elm = gparent; \
539 continue; \
540 } \
541 if (RTEMS_RB_RIGHT(parent, field) == elm) { \
542 RTEMS_RB_PARENT_ROTATE_LEFT(gparent, parent, \
543 tmp, field); \
544 tmp = parent; \
545 parent = elm; \
546 elm = tmp; \
547 } \
548 RTEMS_RB_SET_BLACKRED(parent, gparent, field); \
549 RTEMS_RB_ROTATE_RIGHT(head, gparent, tmp, field); \
550 } else { \
551 tmp = RTEMS_RB_LEFT(gparent, field); \
552 if (RTEMS_RB_ISRED(tmp, field)) { \
553 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_BLACK; \
554 RTEMS_RB_SET_BLACKRED(parent, gparent, field);\
555 elm = gparent; \
556 continue; \
557 } \
558 if (RTEMS_RB_LEFT(parent, field) == elm) { \
559 RTEMS_RB_PARENT_ROTATE_RIGHT(gparent, parent, \
560 tmp, field); \
561 tmp = parent; \
562 parent = elm; \
563 elm = tmp; \
564 } \
565 RTEMS_RB_SET_BLACKRED(parent, gparent, field); \
566 RTEMS_RB_ROTATE_LEFT(head, gparent, tmp, field); \
567 } \
568 } \
569 RTEMS_RB_COLOR(head->rbh_root, field) = RTEMS_RB_BLACK; \
570}
571
572#define RTEMS_RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
573attr void \
574name##_RTEMS_RB_REMOVE_COLOR(struct name *head, struct type *parent) \
575{ \
576 struct type *elm, *tmp; \
577 elm = NULL; \
578 do { \
579 if (RTEMS_RB_LEFT(parent, field) == elm) { \
580 tmp = RTEMS_RB_RIGHT(parent, field); \
581 if (RTEMS_RB_COLOR(tmp, field) == RTEMS_RB_RED) { \
582 RTEMS_RB_SET_BLACKRED(tmp, parent, field); \
583 RTEMS_RB_RED_ROTATE_LEFT(head, parent, tmp, field); \
584 tmp = RTEMS_RB_RIGHT(parent, field); \
585 } \
586 if (RTEMS_RB_ISRED(RTEMS_RB_RIGHT(tmp, field), field)) \
587 RTEMS_RB_COLOR(RTEMS_RB_RIGHT(tmp, field), field) = RTEMS_RB_BLACK; \
588 else if (RTEMS_RB_ISRED(RTEMS_RB_LEFT(tmp, field), field)) { \
589 struct type *oleft; \
590 RTEMS_RB_PARENT_ROTATE_RIGHT(parent, tmp, \
591 oleft, field); \
592 RTEMS_RB_COLOR(oleft, field) = RTEMS_RB_BLACK; \
593 tmp = oleft; \
594 } else { \
595 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_RED; \
596 elm = parent; \
597 parent = RTEMS_RB_PARENT(elm, field); \
598 continue; \
599 } \
600 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_COLOR(parent, field); \
601 RTEMS_RB_COLOR(parent, field) = RTEMS_RB_BLACK; \
602 RTEMS_RB_ROTATE_LEFT(head, parent, tmp, field); \
603 elm = RTEMS_RB_ROOT(head); \
604 break; \
605 } else { \
606 tmp = RTEMS_RB_LEFT(parent, field); \
607 if (RTEMS_RB_COLOR(tmp, field) == RTEMS_RB_RED) { \
608 RTEMS_RB_SET_BLACKRED(tmp, parent, field); \
609 RTEMS_RB_RED_ROTATE_RIGHT(head, parent, tmp, field); \
610 tmp = RTEMS_RB_LEFT(parent, field); \
611 } \
612 if (RTEMS_RB_ISRED(RTEMS_RB_LEFT(tmp, field), field)) \
613 RTEMS_RB_COLOR(RTEMS_RB_LEFT(tmp, field), field) = RTEMS_RB_BLACK; \
614 else if (RTEMS_RB_ISRED(RTEMS_RB_RIGHT(tmp, field), field)) { \
615 struct type *oright; \
616 RTEMS_RB_PARENT_ROTATE_LEFT(parent, tmp, \
617 oright, field); \
618 RTEMS_RB_COLOR(oright, field) = RTEMS_RB_BLACK; \
619 tmp = oright; \
620 } else { \
621 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_RED; \
622 elm = parent; \
623 parent = RTEMS_RB_PARENT(elm, field); \
624 continue; \
625 } \
626 RTEMS_RB_COLOR(tmp, field) = RTEMS_RB_COLOR(parent, field); \
627 RTEMS_RB_COLOR(parent, field) = RTEMS_RB_BLACK; \
628 RTEMS_RB_ROTATE_RIGHT(head, parent, tmp, field); \
629 elm = RTEMS_RB_ROOT(head); \
630 break; \
631 } \
632 } while (RTEMS_RB_COLOR(elm, field) == RTEMS_RB_BLACK && parent != NULL); \
633 RTEMS_RB_COLOR(elm, field) = RTEMS_RB_BLACK; \
634}
635
636#define RTEMS_RB_GENERATE_REMOVE(name, type, field, attr) \
637attr struct type * \
638name##_RTEMS_RB_REMOVE(struct name *head, struct type *elm) \
639{ \
640 struct type *child, *old, *parent, *right; \
641 int color; \
642 \
643 old = elm; \
644 parent = RTEMS_RB_PARENT(elm, field); \
645 right = RTEMS_RB_RIGHT(elm, field); \
646 color = RTEMS_RB_COLOR(elm, field); \
647 if (RTEMS_RB_LEFT(elm, field) == NULL) \
648 elm = child = right; \
649 else if (right == NULL) \
650 elm = child = RTEMS_RB_LEFT(elm, field); \
651 else { \
652 if ((child = RTEMS_RB_LEFT(right, field)) == NULL) { \
653 child = RTEMS_RB_RIGHT(right, field); \
654 RTEMS_RB_RIGHT(old, field) = child; \
655 parent = elm = right; \
656 } else { \
657 do \
658 elm = child; \
659 while ((child = RTEMS_RB_LEFT(elm, field)) != NULL); \
660 child = RTEMS_RB_RIGHT(elm, field); \
661 parent = RTEMS_RB_PARENT(elm, field); \
662 RTEMS_RB_LEFT(parent, field) = child; \
663 RTEMS_RB_SET_PARENT(RTEMS_RB_RIGHT(old, field), elm, field); \
664 } \
665 RTEMS_RB_SET_PARENT(RTEMS_RB_LEFT(old, field), elm, field); \
666 color = RTEMS_RB_COLOR(elm, field); \
667 elm->field = old->field; \
668 } \
669 RTEMS_RB_SWAP_CHILD(head, old, elm, field); \
670 if (child != NULL) { \
671 RTEMS_RB_SET_PARENT(child, parent, field); \
672 RTEMS_RB_COLOR(child, field) = RTEMS_RB_BLACK; \
673 } else if (color != RTEMS_RB_RED && parent != NULL) \
674 name##_RTEMS_RB_REMOVE_COLOR(head, parent); \
675 while (parent != NULL) { \
676 RTEMS_RB_AUGMENT(parent); \
677 parent = RTEMS_RB_PARENT(parent, field); \
678 } \
679 return (old); \
680}
681
682#define RTEMS_RB_GENERATE_INSERT(name, type, field, cmp, attr) \
683/* Inserts a node into the RB tree */ \
684attr struct type * \
685name##_RTEMS_RB_INSERT(struct name *head, struct type *elm) \
686{ \
687 struct type *tmp; \
688 struct type *parent = NULL; \
689 int comp = 0; \
690 tmp = RTEMS_RB_ROOT(head); \
691 while (tmp) { \
692 parent = tmp; \
693 comp = (cmp)(elm, parent); \
694 if (comp < 0) \
695 tmp = RTEMS_RB_LEFT(tmp, field); \
696 else if (comp > 0) \
697 tmp = RTEMS_RB_RIGHT(tmp, field); \
698 else \
699 return (tmp); \
700 } \
701 RTEMS_RB_SET(elm, parent, field); \
702 if (parent != NULL) { \
703 if (comp < 0) \
704 RTEMS_RB_LEFT(parent, field) = elm; \
705 else \
706 RTEMS_RB_RIGHT(parent, field) = elm; \
707 } else \
708 RTEMS_RB_ROOT(head) = elm; \
709 name##_RTEMS_RB_INSERT_COLOR(head, elm); \
710 while (elm != NULL) { \
711 RTEMS_RB_AUGMENT(elm); \
712 elm = RTEMS_RB_PARENT(elm, field); \
713 } \
714 return (NULL); \
715}
716
717#define RTEMS_RB_GENERATE_FIND(name, type, field, cmp, attr) \
718/* Finds the node with the same key as elm */ \
719attr struct type * \
720name##_RTEMS_RB_FIND(struct name *head, struct type *elm) \
721{ \
722 struct type *tmp = RTEMS_RB_ROOT(head); \
723 int comp; \
724 while (tmp) { \
725 comp = cmp(elm, tmp); \
726 if (comp < 0) \
727 tmp = RTEMS_RB_LEFT(tmp, field); \
728 else if (comp > 0) \
729 tmp = RTEMS_RB_RIGHT(tmp, field); \
730 else \
731 return (tmp); \
732 } \
733 return (NULL); \
734}
735
736#define RTEMS_RB_GENERATE_NFIND(name, type, field, cmp, attr) \
737/* Finds the first node greater than or equal to the search key */ \
738attr struct type * \
739name##_RTEMS_RB_NFIND(struct name *head, struct type *elm) \
740{ \
741 struct type *tmp = RTEMS_RB_ROOT(head); \
742 struct type *res = NULL; \
743 int comp; \
744 while (tmp) { \
745 comp = cmp(elm, tmp); \
746 if (comp < 0) { \
747 res = tmp; \
748 tmp = RTEMS_RB_LEFT(tmp, field); \
749 } \
750 else if (comp > 0) \
751 tmp = RTEMS_RB_RIGHT(tmp, field); \
752 else \
753 return (tmp); \
754 } \
755 return (res); \
756}
757
758#define RTEMS_RB_GENERATE_NEXT(name, type, field, attr) \
759/* ARGSUSED */ \
760attr struct type * \
761name##_RTEMS_RB_NEXT(struct type *elm) \
762{ \
763 if (RTEMS_RB_RIGHT(elm, field)) { \
764 elm = RTEMS_RB_RIGHT(elm, field); \
765 while (RTEMS_RB_LEFT(elm, field)) \
766 elm = RTEMS_RB_LEFT(elm, field); \
767 } else { \
768 if (RTEMS_RB_PARENT(elm, field) && \
769 (elm == RTEMS_RB_LEFT(RTEMS_RB_PARENT(elm, field), field))) \
770 elm = RTEMS_RB_PARENT(elm, field); \
771 else { \
772 while (RTEMS_RB_PARENT(elm, field) && \
773 (elm == RTEMS_RB_RIGHT(RTEMS_RB_PARENT(elm, field), field)))\
774 elm = RTEMS_RB_PARENT(elm, field); \
775 elm = RTEMS_RB_PARENT(elm, field); \
776 } \
777 } \
778 return (elm); \
779}
780
781#define RTEMS_RB_GENERATE_PREV(name, type, field, attr) \
782/* ARGSUSED */ \
783attr struct type * \
784name##_RTEMS_RB_PREV(struct type *elm) \
785{ \
786 if (RTEMS_RB_LEFT(elm, field)) { \
787 elm = RTEMS_RB_LEFT(elm, field); \
788 while (RTEMS_RB_RIGHT(elm, field)) \
789 elm = RTEMS_RB_RIGHT(elm, field); \
790 } else { \
791 if (RTEMS_RB_PARENT(elm, field) && \
792 (elm == RTEMS_RB_RIGHT(RTEMS_RB_PARENT(elm, field), field))) \
793 elm = RTEMS_RB_PARENT(elm, field); \
794 else { \
795 while (RTEMS_RB_PARENT(elm, field) && \
796 (elm == RTEMS_RB_LEFT(RTEMS_RB_PARENT(elm, field), field)))\
797 elm = RTEMS_RB_PARENT(elm, field); \
798 elm = RTEMS_RB_PARENT(elm, field); \
799 } \
800 } \
801 return (elm); \
802}
803
804#define RTEMS_RB_GENERATE_MINMAX(name, type, field, attr) \
805attr struct type * \
806name##_RTEMS_RB_MINMAX(struct name *head, int val) \
807{ \
808 struct type *tmp = RTEMS_RB_ROOT(head); \
809 struct type *parent = NULL; \
810 while (tmp) { \
811 parent = tmp; \
812 if (val < 0) \
813 tmp = RTEMS_RB_LEFT(tmp, field); \
814 else \
815 tmp = RTEMS_RB_RIGHT(tmp, field); \
816 } \
817 return (parent); \
818}
819
820#define RTEMS_RB_GENERATE_REINSERT(name, type, field, cmp, attr) \
821attr struct type * \
822name##_RTEMS_RB_REINSERT(struct name *head, struct type *elm) \
823{ \
824 struct type *cmpelm; \
825 if (((cmpelm = RTEMS_RB_PREV(name, head, elm)) != NULL && \
826 cmp(cmpelm, elm) >= 0) || \
827 ((cmpelm = RTEMS_RB_NEXT(name, head, elm)) != NULL && \
828 cmp(elm, cmpelm) >= 0)) { \
829 /* XXXLAS: Remove/insert is heavy handed. */ \
830 RTEMS_RB_REMOVE(name, head, elm); \
831 return (RTEMS_RB_INSERT(name, head, elm)); \
832 } \
833 return (NULL); \
834} \
835
836#define RTEMS_RB_NEGINF -1
837#define RTEMS_RB_INF 1
838
839#define RTEMS_RB_INSERT(name, x, y) name##_RTEMS_RB_INSERT(x, y)
840#define RTEMS_RB_REMOVE(name, x, y) name##_RTEMS_RB_REMOVE(x, y)
841#define RTEMS_RB_FIND(name, x, y) name##_RTEMS_RB_FIND(x, y)
842#define RTEMS_RB_NFIND(name, x, y) name##_RTEMS_RB_NFIND(x, y)
843#define RTEMS_RB_NEXT(name, x, y) name##_RTEMS_RB_NEXT(y)
844#define RTEMS_RB_PREV(name, x, y) name##_RTEMS_RB_PREV(y)
845#define RTEMS_RB_MIN(name, x) name##_RTEMS_RB_MINMAX(x, RTEMS_RB_NEGINF)
846#define RTEMS_RB_MAX(name, x) name##_RTEMS_RB_MINMAX(x, RTEMS_RB_INF)
847#define RTEMS_RB_REINSERT(name, x, y) name##_RTEMS_RB_REINSERT(x, y)
848
849#define RTEMS_RB_FOREACH(x, name, head) \
850 for ((x) = RTEMS_RB_MIN(name, head); \
851 (x) != NULL; \
852 (x) = name##_RTEMS_RB_NEXT(x))
853
854#define RTEMS_RB_FOREACH_FROM(x, name, y) \
855 for ((x) = (y); \
856 ((x) != NULL) && ((y) = name##_RTEMS_RB_NEXT(x), (x) != NULL); \
857 (x) = (y))
858
859#define RTEMS_RB_FOREACH_SAFE(x, name, head, y) \
860 for ((x) = RTEMS_RB_MIN(name, head); \
861 ((x) != NULL) && ((y) = name##_RTEMS_RB_NEXT(x), (x) != NULL); \
862 (x) = (y))
863
864#define RTEMS_RB_FOREACH_REVERSE(x, name, head) \
865 for ((x) = RTEMS_RB_MAX(name, head); \
866 (x) != NULL; \
867 (x) = name##_RTEMS_RB_PREV(x))
868
869#define RTEMS_RB_FOREACH_REVERSE_FROM(x, name, y) \
870 for ((x) = (y); \
871 ((x) != NULL) && ((y) = name##_RTEMS_RB_PREV(x), (x) != NULL); \
872 (x) = (y))
873
874#define RTEMS_RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
875 for ((x) = RTEMS_RB_MAX(name, head); \
876 ((x) != NULL) && ((y) = name##_RTEMS_RB_PREV(x), (x) != NULL); \
877 (x) = (y))
878
879#endif /* _RTEMS_SCORE_BSD_TREE_H_ */
Generated by doxygen 1.18.0