Line data Source code
1 : /* $OpenBSD: tree.h,v 1.14 2015/05/25 03:07:49 deraadt Exp $ */
2 : /*
3 : * Copyright 2002 Niels Provos <provos@citi.umich.edu>
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions
8 : * are met:
9 : * 1. Redistributions of source code must retain the above copyright
10 : * notice, this list of conditions and the following disclaimer.
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 : * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 : * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 : * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 : * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 : * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 : */
26 :
27 : #ifndef _SYS_TREE_H_
28 : #define _SYS_TREE_H_
29 :
30 : #ifdef __cplusplus
31 : extern "C" {
32 : #endif
33 :
34 : /*
35 : * This file defines data structures for different types of trees:
36 : * splay trees and red-black trees.
37 : *
38 : * A splay tree is a self-organizing data structure. Every operation
39 : * on the tree causes a splay to happen. The splay moves the requested
40 : * node to the root of the tree and partly rebalances it.
41 : *
42 : * This has the benefit that request locality causes faster lookups as
43 : * the requested nodes move to the top of the tree. On the other hand,
44 : * every lookup causes memory writes.
45 : *
46 : * The Balance Theorem bounds the total access time for m operations
47 : * and n inserts on an initially empty tree as O((m + n)lg n). The
48 : * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
49 : *
50 : * A red-black tree is a binary search tree with the node color as an
51 : * extra attribute. It fulfills a set of conditions:
52 : * - every search path from the root to a leaf consists of the
53 : * same number of black nodes,
54 : * - each red node (except for the root) has a black parent,
55 : * - each leaf node is black.
56 : *
57 : * Every operation on a red-black tree is bounded as O(lg n).
58 : * The maximum height of a red-black tree is 2lg (n+1).
59 : */
60 :
61 : #define SPLAY_HEAD(name, type) \
62 : struct name { \
63 : struct type *sph_root; /* root of the tree */ \
64 : }
65 :
66 : #define SPLAY_INITIALIZER(root) \
67 : { \
68 : NULL \
69 : }
70 :
71 : #define SPLAY_INIT(root) \
72 : do { \
73 : (root)->sph_root = NULL; \
74 : } while (0)
75 :
76 : #define SPLAY_ENTRY(type) \
77 : struct { \
78 : struct type *spe_left; /* left element */ \
79 : struct type *spe_right; /* right element */ \
80 : }
81 :
82 : #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
83 : #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
84 : #define SPLAY_ROOT(head) (head)->sph_root
85 : #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
86 :
87 : /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
88 : #define SPLAY_ROTATE_RIGHT(head, tmp, field) \
89 : do { \
90 : SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
91 : SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
92 : (head)->sph_root = tmp; \
93 : } while (0)
94 :
95 : #define SPLAY_ROTATE_LEFT(head, tmp, field) \
96 : do { \
97 : SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
98 : SPLAY_LEFT(tmp, field) = (head)->sph_root; \
99 : (head)->sph_root = tmp; \
100 : } while (0)
101 :
102 : #define SPLAY_LINKLEFT(head, tmp, field) \
103 : do { \
104 : SPLAY_LEFT(tmp, field) = (head)->sph_root; \
105 : tmp = (head)->sph_root; \
106 : (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
107 : } while (0)
108 :
109 : #define SPLAY_LINKRIGHT(head, tmp, field) \
110 : do { \
111 : SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
112 : tmp = (head)->sph_root; \
113 : (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
114 : } while (0)
115 :
116 : #define SPLAY_ASSEMBLE(head, node, left, right, field) \
117 : do { \
118 : SPLAY_RIGHT(left, field) = \
119 : SPLAY_LEFT((head)->sph_root, field); \
120 : SPLAY_LEFT(right, field) = \
121 : SPLAY_RIGHT((head)->sph_root, field); \
122 : SPLAY_LEFT((head)->sph_root, field) = \
123 : SPLAY_RIGHT(node, field); \
124 : SPLAY_RIGHT((head)->sph_root, field) = \
125 : SPLAY_LEFT(node, field); \
126 : } while (0)
127 :
128 : /* Generates prototypes and inline functions */
129 :
130 : #define SPLAY_PROTOTYPE(name, type, field, cmp) \
131 : void name##_SPLAY(struct name *, struct type *); \
132 : void name##_SPLAY_MINMAX(struct name *, int); \
133 : struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
134 : struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
135 : \
136 : /* Finds the node with the same key as elm */ \
137 : static __inline struct type *name##_SPLAY_FIND(struct name *head, \
138 : struct type *elm) \
139 : { \
140 : if (SPLAY_EMPTY(head)) \
141 : return (NULL); \
142 : name##_SPLAY(head, elm); \
143 : if ((cmp)(elm, (head)->sph_root) == 0) \
144 : return (head->sph_root); \
145 : return (NULL); \
146 : } \
147 : \
148 : static __inline struct type *name##_SPLAY_NEXT(struct name *head, \
149 : struct type *elm) \
150 : { \
151 : name##_SPLAY(head, elm); \
152 : if (SPLAY_RIGHT(elm, field) != NULL) { \
153 : elm = SPLAY_RIGHT(elm, field); \
154 : while (SPLAY_LEFT(elm, field) != NULL) { \
155 : elm = SPLAY_LEFT(elm, field); \
156 : } \
157 : } else \
158 : elm = NULL; \
159 : return (elm); \
160 : } \
161 : \
162 : static __inline struct type *name##_SPLAY_MIN_MAX(struct name *head, \
163 : int val) \
164 : { \
165 : name##_SPLAY_MINMAX(head, val); \
166 : return (SPLAY_ROOT(head)); \
167 : }
168 :
169 : /* Main splay operation.
170 : * Moves node close to the key of elm to top
171 : */
172 : #define SPLAY_GENERATE(name, type, field, cmp) \
173 : struct type *name##_SPLAY_INSERT(struct name *head, struct type *elm) \
174 : { \
175 : if (SPLAY_EMPTY(head)) { \
176 : SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = \
177 : NULL; \
178 : } else { \
179 : int __comp; \
180 : name##_SPLAY(head, elm); \
181 : __comp = (cmp)(elm, (head)->sph_root); \
182 : if (__comp < 0) { \
183 : SPLAY_LEFT(elm, field) = \
184 : SPLAY_LEFT((head)->sph_root, field); \
185 : SPLAY_RIGHT(elm, field) = (head)->sph_root; \
186 : SPLAY_LEFT((head)->sph_root, field) = NULL; \
187 : } else if (__comp > 0) { \
188 : SPLAY_RIGHT(elm, field) = \
189 : SPLAY_RIGHT((head)->sph_root, field); \
190 : SPLAY_LEFT(elm, field) = (head)->sph_root; \
191 : SPLAY_RIGHT((head)->sph_root, field) = NULL; \
192 : } else \
193 : return ((head)->sph_root); \
194 : } \
195 : (head)->sph_root = (elm); \
196 : return (NULL); \
197 : } \
198 : \
199 : struct type *name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
200 : { \
201 : struct type *__tmp; \
202 : if (SPLAY_EMPTY(head)) \
203 : return (NULL); \
204 : name##_SPLAY(head, elm); \
205 : if ((cmp)(elm, (head)->sph_root) == 0) { \
206 : if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
207 : (head)->sph_root = \
208 : SPLAY_RIGHT((head)->sph_root, field); \
209 : } else { \
210 : __tmp = SPLAY_RIGHT((head)->sph_root, field); \
211 : (head)->sph_root = \
212 : SPLAY_LEFT((head)->sph_root, field); \
213 : name##_SPLAY(head, elm); \
214 : SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
215 : } \
216 : return (elm); \
217 : } \
218 : return (NULL); \
219 : } \
220 : \
221 : void name##_SPLAY(struct name *head, struct type *elm) \
222 : { \
223 : struct type __node, *__left, *__right, *__tmp; \
224 : int __comp; \
225 : \
226 : SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \
227 : NULL; \
228 : __left = __right = &__node; \
229 : \
230 : while ((__comp = (cmp)(elm, (head)->sph_root))) { \
231 : if (__comp < 0) { \
232 : __tmp = SPLAY_LEFT((head)->sph_root, field); \
233 : if (__tmp == NULL) \
234 : break; \
235 : if ((cmp)(elm, __tmp) < 0) { \
236 : SPLAY_ROTATE_RIGHT(head, __tmp, \
237 : field); \
238 : if (SPLAY_LEFT((head)->sph_root, \
239 : field) \
240 : == NULL) \
241 : break; \
242 : } \
243 : SPLAY_LINKLEFT(head, __right, field); \
244 : } else if (__comp > 0) { \
245 : __tmp = SPLAY_RIGHT((head)->sph_root, field); \
246 : if (__tmp == NULL) \
247 : break; \
248 : if ((cmp)(elm, __tmp) > 0) { \
249 : SPLAY_ROTATE_LEFT(head, __tmp, field); \
250 : if (SPLAY_RIGHT((head)->sph_root, \
251 : field) \
252 : == NULL) \
253 : break; \
254 : } \
255 : SPLAY_LINKRIGHT(head, __left, field); \
256 : } \
257 : } \
258 : SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
259 : } \
260 : \
261 : /* Splay with either the minimum or the maximum element \
262 : * Used to find minimum or maximum element in tree. \
263 : */ \
264 : void name##_SPLAY_MINMAX(struct name *head, int __comp) \
265 : { \
266 : struct type __node, *__left, *__right, *__tmp; \
267 : \
268 : SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = \
269 : NULL; \
270 : __left = __right = &__node; \
271 : \
272 : while (1) { \
273 : if (__comp < 0) { \
274 : __tmp = SPLAY_LEFT((head)->sph_root, field); \
275 : if (__tmp == NULL) \
276 : break; \
277 : if (__comp < 0) { \
278 : SPLAY_ROTATE_RIGHT(head, __tmp, \
279 : field); \
280 : if (SPLAY_LEFT((head)->sph_root, \
281 : field) \
282 : == NULL) \
283 : break; \
284 : } \
285 : SPLAY_LINKLEFT(head, __right, field); \
286 : } else if (__comp > 0) { \
287 : __tmp = SPLAY_RIGHT((head)->sph_root, field); \
288 : if (__tmp == NULL) \
289 : break; \
290 : if (__comp > 0) { \
291 : SPLAY_ROTATE_LEFT(head, __tmp, field); \
292 : if (SPLAY_RIGHT((head)->sph_root, \
293 : field) \
294 : == NULL) \
295 : break; \
296 : } \
297 : SPLAY_LINKRIGHT(head, __left, field); \
298 : } \
299 : } \
300 : SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
301 : }
302 :
303 : #define SPLAY_NEGINF -1
304 : #define SPLAY_INF 1
305 :
306 : #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
307 : #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
308 : #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
309 : #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
310 : #define SPLAY_MIN(name, x) \
311 : (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
312 : #define SPLAY_MAX(name, x) \
313 : (SPLAY_EMPTY(x) ? NULL : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
314 :
315 : #define SPLAY_FOREACH(x, name, head) \
316 : for ((x) = SPLAY_MIN(name, head); (x) != NULL; \
317 : (x) = SPLAY_NEXT(name, head, x))
318 :
319 : /*
320 : * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
321 : *
322 : * Permission to use, copy, modify, and distribute this software for any
323 : * purpose with or without fee is hereby granted, provided that the above
324 : * copyright notice and this permission notice appear in all copies.
325 : *
326 : * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
327 : * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
328 : * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
329 : * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
330 : * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
331 : * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
332 : * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
333 : */
334 :
335 : #define RB_BLACK 0
336 : #define RB_RED 1
337 :
338 : struct rb_type {
339 : int (*t_compare)(const void *, const void *);
340 : void (*t_augment)(void *);
341 : unsigned int t_offset; /* offset of rb_entry in type */
342 : };
343 :
344 : struct rbt_tree {
345 : struct rb_entry *rbt_root;
346 : };
347 :
348 : struct rb_entry {
349 : struct rb_entry *rbt_parent;
350 : struct rb_entry *rbt_left;
351 : struct rb_entry *rbt_right;
352 : unsigned int rbt_color;
353 : };
354 :
355 : #define RB_HEAD(_name, _type) \
356 : struct _name { \
357 : struct rbt_tree rbh_root; \
358 : }
359 :
360 : #define RB_ENTRY(_type) struct rb_entry
361 :
362 21 : static inline void _rb_init(struct rbt_tree *rbt)
363 : {
364 21 : rbt->rbt_root = NULL;
365 : }
366 :
367 97 : static inline int _rb_empty(const struct rbt_tree *rbt)
368 : {
369 97 : return (rbt->rbt_root == NULL);
370 : }
371 :
372 : void *_rb_insert(const struct rb_type *, struct rbt_tree *, void *);
373 : void *_rb_remove(const struct rb_type *, struct rbt_tree *, void *);
374 : void *_rb_find(const struct rb_type *, const struct rbt_tree *, const void *);
375 : void *_rb_nfind(const struct rb_type *, const struct rbt_tree *, const void *);
376 : void *_rb_root(const struct rb_type *, const struct rbt_tree *);
377 : void *_rb_min(const struct rb_type *, const struct rbt_tree *);
378 : void *_rb_max(const struct rb_type *, const struct rbt_tree *);
379 : void *_rb_next(const struct rb_type *, void *);
380 : void *_rb_prev(const struct rb_type *, void *);
381 : void *_rb_left(const struct rb_type *, void *);
382 : void *_rb_right(const struct rb_type *, void *);
383 : void *_rb_parent(const struct rb_type *, void *);
384 : void _rb_set_left(const struct rb_type *, void *, void *);
385 : void _rb_set_right(const struct rb_type *, void *, void *);
386 : void _rb_set_parent(const struct rb_type *, void *, void *);
387 : void _rb_poison(const struct rb_type *, void *, unsigned long);
388 : int _rb_check(const struct rb_type *, void *, unsigned long);
389 :
390 : #define RB_INITIALIZER(_head) { { NULL } }
391 :
392 : #define RB_PROTOTYPE(_name, _type, _field, _cmp) \
393 : extern const struct rb_type *const _name##_RB_TYPE; \
394 : \
395 : __attribute__((__unused__)) static inline void _name##_RB_INIT( \
396 : struct _name *head) \
397 : { \
398 : _rb_init(&head->rbh_root); \
399 : } \
400 : \
401 : __attribute__((__unused__)) static inline struct _type \
402 : *_name##_RB_INSERT(struct _name *head, struct _type *elm) \
403 : { \
404 : return (struct _type *)_rb_insert(_name##_RB_TYPE, \
405 : &head->rbh_root, elm); \
406 : } \
407 : \
408 : __attribute__((__unused__)) static inline struct _type \
409 : *_name##_RB_REMOVE(struct _name *head, struct _type *elm) \
410 : { \
411 : return (struct _type *)_rb_remove(_name##_RB_TYPE, \
412 : &head->rbh_root, elm); \
413 : } \
414 : \
415 : __attribute__((__unused__)) static inline struct _type \
416 : *_name##_RB_FIND(const struct _name *head, \
417 : const struct _type *key) \
418 : { \
419 : return (struct _type *)_rb_find(_name##_RB_TYPE, \
420 : &head->rbh_root, key); \
421 : } \
422 : \
423 : __attribute__((__unused__)) static inline struct _type \
424 : *_name##_RB_NFIND(const struct _name *head, \
425 : const struct _type *key) \
426 : { \
427 : return (struct _type *)_rb_nfind(_name##_RB_TYPE, \
428 : &head->rbh_root, key); \
429 : } \
430 : \
431 : __attribute__((__unused__)) static inline struct _type \
432 : *_name##_RB_ROOT(const struct _name *head) \
433 : { \
434 : return (struct _type *)_rb_root(_name##_RB_TYPE, \
435 : &head->rbh_root); \
436 : } \
437 : \
438 : __attribute__((__unused__)) static inline int _name##_RB_EMPTY( \
439 : const struct _name *head) \
440 : { \
441 : return _rb_empty(&head->rbh_root); \
442 : } \
443 : \
444 : __attribute__((__unused__)) static inline struct _type \
445 : *_name##_RB_MIN(const struct _name *head) \
446 : { \
447 : return (struct _type *)_rb_min(_name##_RB_TYPE, \
448 : &head->rbh_root); \
449 : } \
450 : \
451 : __attribute__((__unused__)) static inline struct _type \
452 : *_name##_RB_MAX(const struct _name *head) \
453 : { \
454 : return (struct _type *)_rb_max(_name##_RB_TYPE, \
455 : &head->rbh_root); \
456 : } \
457 : \
458 : __attribute__((__unused__)) static inline struct _type \
459 : *_name##_RB_NEXT(struct _type *elm) \
460 : { \
461 : return (struct _type *)_rb_next(_name##_RB_TYPE, elm); \
462 : } \
463 : \
464 : __attribute__((__unused__)) static inline struct _type \
465 : *_name##_RB_PREV(struct _type *elm) \
466 : { \
467 : return (struct _type *)_rb_prev(_name##_RB_TYPE, elm); \
468 : } \
469 : \
470 : __attribute__((__unused__)) static inline struct _type \
471 : *_name##_RB_LEFT(struct _type *elm) \
472 : { \
473 : return (struct _type *)_rb_left(_name##_RB_TYPE, elm); \
474 : } \
475 : \
476 : __attribute__((__unused__)) static inline struct _type \
477 : *_name##_RB_RIGHT(struct _type *elm) \
478 : { \
479 : return (struct _type *)_rb_right(_name##_RB_TYPE, elm); \
480 : } \
481 : \
482 : __attribute__((__unused__)) static inline struct _type \
483 : *_name##_RB_PARENT(struct _type *elm) \
484 : { \
485 : return (struct _type *)_rb_parent(_name##_RB_TYPE, elm); \
486 : } \
487 : \
488 : __attribute__((__unused__)) static inline void _name##_RB_SET_LEFT( \
489 : struct _type *elm, struct _type *left) \
490 : { \
491 : _rb_set_left(_name##_RB_TYPE, elm, left); \
492 : } \
493 : \
494 : __attribute__((__unused__)) static inline void _name##_RB_SET_RIGHT( \
495 : struct _type *elm, struct _type *right) \
496 : { \
497 : _rb_set_right(_name##_RB_TYPE, elm, right); \
498 : } \
499 : \
500 : __attribute__((__unused__)) static inline void _name##_RB_SET_PARENT( \
501 : struct _type *elm, struct _type *parent) \
502 : { \
503 : _rb_set_parent(_name##_RB_TYPE, elm, parent); \
504 : } \
505 : \
506 : __attribute__((__unused__)) static inline void _name##_RB_POISON( \
507 : struct _type *elm, unsigned long poison) \
508 : { \
509 : _rb_poison(_name##_RB_TYPE, elm, poison); \
510 : } \
511 : \
512 : __attribute__((__unused__)) static inline int _name##_RB_CHECK( \
513 : struct _type *elm, unsigned long poison) \
514 : { \
515 : return _rb_check(_name##_RB_TYPE, elm, poison); \
516 : }
517 :
518 : #define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \
519 : static int _name##_RB_COMPARE(const void *lptr, const void *rptr) \
520 : { \
521 : const struct _type *l = lptr, *r = rptr; \
522 : return _cmp(l, r); \
523 : } \
524 : static const struct rb_type _name##_RB_INFO = { \
525 : _name##_RB_COMPARE, _aug, offsetof(struct _type, _field), \
526 : }; \
527 : const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO;
528 :
529 : #define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \
530 : static void _name##_RB_AUGMENT(void *ptr) \
531 : { \
532 : struct _type *p = ptr; \
533 : return _aug(p); \
534 : } \
535 : RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT)
536 :
537 : #define RB_GENERATE(_name, _type, _field, _cmp) \
538 : RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)
539 :
540 : #define RB_INIT(_name, _head) _name##_RB_INIT(_head)
541 : #define RB_INSERT(_name, _head, _elm) _name##_RB_INSERT(_head, _elm)
542 : #define RB_REMOVE(_name, _head, _elm) _name##_RB_REMOVE(_head, _elm)
543 : #define RB_FIND(_name, _head, _key) _name##_RB_FIND(_head, _key)
544 : #define RB_NFIND(_name, _head, _key) _name##_RB_NFIND(_head, _key)
545 : #define RB_ROOT(_name, _head) _name##_RB_ROOT(_head)
546 : #define RB_EMPTY(_name, _head) _name##_RB_EMPTY(_head)
547 : #define RB_MIN(_name, _head) _name##_RB_MIN(_head)
548 : #define RB_MAX(_name, _head) _name##_RB_MAX(_head)
549 : #define RB_NEXT(_name, _elm) _name##_RB_NEXT(_elm)
550 : #define RB_PREV(_name, _elm) _name##_RB_PREV(_elm)
551 : #define RB_LEFT(_name, _elm) _name##_RB_LEFT(_elm)
552 : #define RB_RIGHT(_name, _elm) _name##_RB_RIGHT(_elm)
553 : #define RB_PARENT(_name, _elm) _name##_RB_PARENT(_elm)
554 : #define RB_SET_LEFT(_name, _elm, _l) _name##_RB_SET_LEFT(_elm, _l)
555 : #define RB_SET_RIGHT(_name, _elm, _r) _name##_RB_SET_RIGHT(_elm, _r)
556 : #define RB_SET_PARENT(_name, _elm, _p) _name##_RB_SET_PARENT(_elm, _p)
557 : #define RB_POISON(_name, _elm, _p) _name##_RB_POISON(_elm, _p)
558 : #define RB_CHECK(_name, _elm, _p) _name##_RB_CHECK(_elm, _p)
559 :
560 : #define RB_FOREACH(_e, _name, _head) \
561 : for ((_e) = RB_MIN(_name, (_head)); (_e) != NULL; \
562 : (_e) = RB_NEXT(_name, (_e)))
563 :
564 : #define RB_FOREACH_SAFE(_e, _name, _head, _n) \
565 : for ((_e) = RB_MIN(_name, (_head)); \
566 : (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); (_e) = (_n))
567 :
568 : #define RB_FOREACH_REVERSE(_e, _name, _head) \
569 : for ((_e) = RB_MAX(_name, (_head)); (_e) != NULL; \
570 : (_e) = RB_PREV(_name, (_e)))
571 :
572 : #define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \
573 : for ((_e) = RB_MAX(_name, (_head)); \
574 : (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); (_e) = (_n))
575 :
576 : #ifdef __cplusplus
577 : }
578 : #endif
579 :
580 : #endif /* _SYS_TREE_H_ */
|
