suricata
interval-tree.h
Go to the documentation of this file.
1/* $NetBSD: interval-tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */
2/* $OpenBSD: interval-tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
3/* $FreeBSD$ */
4
5/* This is a COPY of the in-tree tree.h modified to accomodate interval
6 * tree operations */
7
8/*-
9 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
10 *
11 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
12 * All rights reserved.
13 *
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions
16 * are met:
17 * 1. Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 * 2. Redistributions in binary form must reproduce the above copyright
20 * notice, this list of conditions and the following disclaimer in the
21 * documentation and/or other materials provided with the distribution.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
24 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
25 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
26 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
28 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
32 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 */
34
35#ifndef _SYS_INTERVALTREE_H_
36#define _SYS_INTERVALTREE_H_
37
38#if defined(__clang_analyzer__)
39#define _T_ASSERT(a) assert((a))
40#else
41#define _T_ASSERT(a)
42#endif
43
44/*
45 * This file defines data structures for interval trees which are
46 * implemented using red-black trees.
47 *
48 * A red-black tree is a binary search tree with the node color as an
49 * extra attribute. It fulfills a set of conditions:
50 * - every search path from the root to a leaf consists of the
51 * same number of black nodes,
52 * - each red node (except for the root) has a black parent,
53 * - each leaf node is black.
54 *
55 * Every operation on a red-black tree is bounded as O(lg n).
56 * The maximum height of a red-black tree is 2lg (n+1).
57 */
58
59/* Macros that define a red-black tree */
60#define IRB_HEAD(name, type) \
61 struct name { \
62 struct type *rbh_root; /* root of the tree */ \
63 }
64
65#define IRB_INITIALIZER(root) \
66 { \
67 NULL \
68 }
69
70#define IRB_INIT(root) \
71 do { \
72 (root)->rbh_root = NULL; \
73 } while (/*CONSTCOND*/ 0)
74
75#define IRB_BLACK 0
76#define IRB_RED 1
77#define IRB_ENTRY(type) \
78 struct { \
79 struct type *rbe_left; /* left element */ \
80 struct type *rbe_right; /* right element */ \
81 struct type *rbe_parent; /* parent element */ \
82 int rbe_color; /* node color */ \
83 }
84
85#define IRB_LEFT(elm, field) (elm)->field.rbe_left
86#define IRB_RIGHT(elm, field) (elm)->field.rbe_right
87#define IRB_PARENT(elm, field) (elm)->field.rbe_parent
88#define IRB_COLOR(elm, field) (elm)->field.rbe_color
89#define IRB_ROOT(head) (head)->rbh_root
90#define IRB_EMPTY(head) (IRB_ROOT(head) == NULL)
91
92#define IRB_SET(elm, parent, field) \
93 do { \
94 IRB_PARENT(elm, field) = parent; \
95 IRB_LEFT(elm, field) = IRB_RIGHT(elm, field) = NULL; \
96 IRB_COLOR(elm, field) = IRB_RED; \
97 } while (/*CONSTCOND*/ 0)
98
99#define IRB_SET_BLACKRED(black, red, field) \
100 do { \
101 IRB_COLOR(black, field) = IRB_BLACK; \
102 IRB_COLOR(red, field) = IRB_RED; \
103 } while (/*CONSTCOND*/ 0)
104
105/*
106 * The implementation of the following macro has been updated.
107 * In order to incorporte it properly, the call sites of this
108 * function have also been updated compared to the standard
109 * Red Black tree implementation in tree.h of BSD */
110#ifndef IRB_AUGMENT
111#define IRB_AUGMENT(x, field) \
112 do { \
113 if (x != NULL) { \
114 x->max = x->port2; \
115 if (IRB_LEFT(x, field) != NULL) { \
116 x->max = MAX(x->max, IRB_LEFT(x, field)->max); \
117 } \
118 if (IRB_RIGHT(x, field) != NULL) { \
119 x->max = MAX(x->max, IRB_RIGHT(x, field)->max); \
120 } \
121 } \
122 } while (0)
123#endif
124
125#define IRB_ROTATE_LEFT(head, elm, tmp, field) \
126 do { \
127 (tmp) = IRB_RIGHT(elm, field); \
128 if ((IRB_RIGHT(elm, field) = IRB_LEFT(tmp, field)) != NULL) { \
129 IRB_PARENT(IRB_LEFT(tmp, field), field) = (elm); \
130 } \
131 if ((IRB_PARENT(tmp, field) = IRB_PARENT(elm, field)) != NULL) { \
132 if ((elm) == IRB_LEFT(IRB_PARENT(elm, field), field)) \
133 IRB_LEFT(IRB_PARENT(elm, field), field) = (tmp); \
134 else \
135 IRB_RIGHT(IRB_PARENT(elm, field), field) = (tmp); \
136 } else \
137 (head)->rbh_root = (tmp); \
138 IRB_LEFT(tmp, field) = (elm); \
139 IRB_PARENT(elm, field) = (tmp); \
140 IRB_AUGMENT(elm, field); \
141 IRB_AUGMENT(tmp, field); \
142 if ((IRB_PARENT(tmp, field))) \
143 IRB_AUGMENT(IRB_PARENT(tmp, field), field); \
144 } while (/*CONSTCOND*/ 0)
145
146#define IRB_ROTATE_RIGHT(head, elm, tmp, field) \
147 do { \
148 (tmp) = IRB_LEFT(elm, field); \
149 if ((IRB_LEFT(elm, field) = IRB_RIGHT(tmp, field)) != NULL) { \
150 IRB_PARENT(IRB_RIGHT(tmp, field), field) = (elm); \
151 } \
152 if ((IRB_PARENT(tmp, field) = IRB_PARENT(elm, field)) != NULL) { \
153 if ((elm) == IRB_LEFT(IRB_PARENT(elm, field), field)) \
154 IRB_LEFT(IRB_PARENT(elm, field), field) = (tmp); \
155 else \
156 IRB_RIGHT(IRB_PARENT(elm, field), field) = (tmp); \
157 } else \
158 (head)->rbh_root = (tmp); \
159 IRB_RIGHT(tmp, field) = (elm); \
160 IRB_PARENT(elm, field) = (tmp); \
161 IRB_AUGMENT(elm, field); \
162 IRB_AUGMENT(tmp, field); \
163 if ((IRB_PARENT(tmp, field))) \
164 IRB_AUGMENT(IRB_PARENT(tmp, field), field); \
165 } while (/*CONSTCOND*/ 0)
166
167/* Generates prototypes and inline functions */
168#define IRB_PROTOTYPE(name, type, field, cmp) IRB_PROTOTYPE_INTERNAL(name, type, field, cmp, )
169#define IRB_PROTOTYPE_STATIC(name, type, field, cmp) \
170 IRB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
171#define IRB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
172 IRB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
173 IRB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
174 IRB_PROTOTYPE_INSERT(name, type, attr); \
175 IRB_PROTOTYPE_REMOVE(name, type, attr); \
176 IRB_PROTOTYPE_FIND(name, type, attr); \
177 IRB_PROTOTYPE_NFIND(name, type, attr); \
178 IRB_PROTOTYPE_NEXT(name, type, attr); \
179 IRB_PROTOTYPE_PREV(name, type, attr); \
180 IRB_PROTOTYPE_MINMAX(name, type, attr);
181#define IRB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
182 attr void name##_IRB_INSERT_COLOR(struct name *, struct type *)
183#define IRB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
184 attr void name##_IRB_REMOVE_COLOR(struct name *, struct type *, struct type *)
185#define IRB_PROTOTYPE_REMOVE(name, type, attr) \
186 attr struct type *name##_IRB_REMOVE(struct name *, struct type *)
187#define IRB_PROTOTYPE_INSERT(name, type, attr) \
188 attr struct type *name##_IRB_INSERT(struct name *, struct type *)
189#define IRB_PROTOTYPE_FIND(name, type, attr) \
190 attr struct type *name##_IRB_FIND(struct name *, struct type *)
191#define IRB_PROTOTYPE_NFIND(name, type, attr) \
192 attr struct type *name##_IRB_NFIND(struct name *, struct type *)
193#define IRB_PROTOTYPE_NEXT(name, type, attr) attr struct type *name##_IRB_NEXT(struct type *)
194#define IRB_PROTOTYPE_PREV(name, type, attr) attr struct type *name##_IRB_PREV(struct type *)
195#define IRB_PROTOTYPE_MINMAX(name, type, attr) \
196 attr struct type *name##_IRB_MINMAX(struct name *, int)
197
198/* Main rb operation.
199 * Moves node close to the key of elm to top
200 */
201#define IRB_GENERATE(name, type, field, cmp) IRB_GENERATE_INTERNAL(name, type, field, cmp, )
202#define IRB_GENERATE_STATIC(name, type, field, cmp) \
203 IRB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
204#define IRB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
205 IRB_GENERATE_INSERT_COLOR(name, type, field, attr) \
206 IRB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
207 IRB_GENERATE_INSERT(name, type, field, cmp, attr) \
208 IRB_GENERATE_REMOVE(name, type, field, attr) \
209 IRB_GENERATE_FIND(name, type, field, cmp, attr) \
210 IRB_GENERATE_NFIND(name, type, field, cmp, attr) \
211 IRB_GENERATE_NEXT(name, type, field, attr) \
212 IRB_GENERATE_PREV(name, type, field, attr) \
213 IRB_GENERATE_MINMAX(name, type, field, attr)
214
215#define IRB_GENERATE_INSERT_COLOR(name, type, field, attr) \
216 attr void name##_IRB_INSERT_COLOR(struct name *head, struct type *elm) \
217 { \
218 struct type *parent, *gparent, *tmp; \
219 while ((parent = IRB_PARENT(elm, field)) != NULL && IRB_COLOR(parent, field) == IRB_RED) { \
220 gparent = IRB_PARENT(parent, field); \
221 _T_ASSERT(gparent); \
222 if (parent == IRB_LEFT(gparent, field)) { \
223 tmp = IRB_RIGHT(gparent, field); \
224 if (tmp && IRB_COLOR(tmp, field) == IRB_RED) { \
225 IRB_COLOR(tmp, field) = IRB_BLACK; \
226 IRB_SET_BLACKRED(parent, gparent, field); \
227 elm = gparent; \
228 continue; \
229 } \
230 if (IRB_RIGHT(parent, field) == elm) { \
231 IRB_ROTATE_LEFT(head, parent, tmp, field); \
232 tmp = parent; \
233 parent = elm; \
234 elm = tmp; \
235 } \
236 IRB_SET_BLACKRED(parent, gparent, field); \
237 IRB_ROTATE_RIGHT(head, gparent, tmp, field); \
238 } else { \
239 tmp = IRB_LEFT(gparent, field); \
240 if (tmp && IRB_COLOR(tmp, field) == IRB_RED) { \
241 IRB_COLOR(tmp, field) = IRB_BLACK; \
242 IRB_SET_BLACKRED(parent, gparent, field); \
243 elm = gparent; \
244 continue; \
245 } \
246 if (IRB_LEFT(parent, field) == elm) { \
247 IRB_ROTATE_RIGHT(head, parent, tmp, field); \
248 tmp = parent; \
249 parent = elm; \
250 elm = tmp; \
251 } \
252 IRB_SET_BLACKRED(parent, gparent, field); \
253 IRB_ROTATE_LEFT(head, gparent, tmp, field); \
254 } \
255 } \
256 IRB_COLOR(head->rbh_root, field) = IRB_BLACK; \
257 }
258
259#define IRB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
260 attr void name##_IRB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
261 { \
262 struct type *tmp; \
263 while ((elm == NULL || IRB_COLOR(elm, field) == IRB_BLACK) && elm != IRB_ROOT(head)) { \
264 if (IRB_LEFT(parent, field) == elm) { \
265 tmp = IRB_RIGHT(parent, field); \
266 if (IRB_COLOR(tmp, field) == IRB_RED) { \
267 IRB_SET_BLACKRED(tmp, parent, field); \
268 IRB_ROTATE_LEFT(head, parent, tmp, field); \
269 tmp = IRB_RIGHT(parent, field); \
270 } \
271 _T_ASSERT(tmp); \
272 if ((IRB_LEFT(tmp, field) == NULL || \
273 IRB_COLOR(IRB_LEFT(tmp, field), field) == IRB_BLACK) && \
274 (IRB_RIGHT(tmp, field) == NULL || \
275 IRB_COLOR(IRB_RIGHT(tmp, field), field) == IRB_BLACK)) { \
276 IRB_COLOR(tmp, field) = IRB_RED; \
277 elm = parent; \
278 parent = IRB_PARENT(elm, field); \
279 } else { \
280 if (IRB_RIGHT(tmp, field) == NULL || \
281 IRB_COLOR(IRB_RIGHT(tmp, field), field) == IRB_BLACK) { \
282 struct type *oleft; \
283 if ((oleft = IRB_LEFT(tmp, field)) != NULL) \
284 IRB_COLOR(oleft, field) = IRB_BLACK; \
285 IRB_COLOR(tmp, field) = IRB_RED; \
286 IRB_ROTATE_RIGHT(head, tmp, oleft, field); \
287 tmp = IRB_RIGHT(parent, field); \
288 } \
289 IRB_COLOR(tmp, field) = IRB_COLOR(parent, field); \
290 IRB_COLOR(parent, field) = IRB_BLACK; \
291 if (IRB_RIGHT(tmp, field)) \
292 IRB_COLOR(IRB_RIGHT(tmp, field), field) = IRB_BLACK; \
293 IRB_ROTATE_LEFT(head, parent, tmp, field); \
294 elm = IRB_ROOT(head); \
295 break; \
296 } \
297 } else { \
298 tmp = IRB_LEFT(parent, field); \
299 if (IRB_COLOR(tmp, field) == IRB_RED) { \
300 IRB_SET_BLACKRED(tmp, parent, field); \
301 IRB_ROTATE_RIGHT(head, parent, tmp, field); \
302 tmp = IRB_LEFT(parent, field); \
303 } \
304 _T_ASSERT(tmp); \
305 if ((IRB_LEFT(tmp, field) == NULL || \
306 IRB_COLOR(IRB_LEFT(tmp, field), field) == IRB_BLACK) && \
307 (IRB_RIGHT(tmp, field) == NULL || \
308 IRB_COLOR(IRB_RIGHT(tmp, field), field) == IRB_BLACK)) { \
309 IRB_COLOR(tmp, field) = IRB_RED; \
310 elm = parent; \
311 parent = IRB_PARENT(elm, field); \
312 } else { \
313 if (IRB_LEFT(tmp, field) == NULL || \
314 IRB_COLOR(IRB_LEFT(tmp, field), field) == IRB_BLACK) { \
315 struct type *oright; \
316 if ((oright = IRB_RIGHT(tmp, field)) != NULL) \
317 IRB_COLOR(oright, field) = IRB_BLACK; \
318 IRB_COLOR(tmp, field) = IRB_RED; \
319 IRB_ROTATE_LEFT(head, tmp, oright, field); \
320 tmp = IRB_LEFT(parent, field); \
321 } \
322 IRB_COLOR(tmp, field) = IRB_COLOR(parent, field); \
323 IRB_COLOR(parent, field) = IRB_BLACK; \
324 if (IRB_LEFT(tmp, field)) \
325 IRB_COLOR(IRB_LEFT(tmp, field), field) = IRB_BLACK; \
326 IRB_ROTATE_RIGHT(head, parent, tmp, field); \
327 elm = IRB_ROOT(head); \
328 break; \
329 } \
330 } \
331 } \
332 if (elm) \
333 IRB_COLOR(elm, field) = IRB_BLACK; \
334 }
335
336#define IRB_GENERATE_REMOVE(name, type, field, attr) \
337 attr struct type *name##_IRB_REMOVE(struct name *head, struct type *elm) \
338 { \
339 struct type *child, *parent, *old = elm; \
340 int color; \
341 if (IRB_LEFT(elm, field) == NULL) \
342 child = IRB_RIGHT(elm, field); \
343 else if (IRB_RIGHT(elm, field) == NULL) \
344 child = IRB_LEFT(elm, field); \
345 else { \
346 struct type *left; \
347 elm = IRB_RIGHT(elm, field); \
348 while ((left = IRB_LEFT(elm, field)) != NULL) \
349 elm = left; \
350 child = IRB_RIGHT(elm, field); \
351 parent = IRB_PARENT(elm, field); \
352 color = IRB_COLOR(elm, field); \
353 if (child) \
354 IRB_PARENT(child, field) = parent; \
355 if (parent) { \
356 if (IRB_LEFT(parent, field) == elm) \
357 IRB_LEFT(parent, field) = child; \
358 else \
359 IRB_RIGHT(parent, field) = child; \
360 IRB_AUGMENT(parent, field); \
361 } else \
362 IRB_ROOT(head) = child; \
363 if (IRB_PARENT(elm, field) == old) \
364 parent = elm; \
365 _T_ASSERT((old)); \
366 (elm)->field = (old)->field; \
367 if (IRB_PARENT(old, field)) { \
368 if (IRB_LEFT(IRB_PARENT(old, field), field) == old) \
369 IRB_LEFT(IRB_PARENT(old, field), field) = elm; \
370 else \
371 IRB_RIGHT(IRB_PARENT(old, field), field) = elm; \
372 IRB_AUGMENT(IRB_PARENT(old, field), field); \
373 } else \
374 IRB_ROOT(head) = elm; \
375 _T_ASSERT(old); \
376 _T_ASSERT(IRB_LEFT(old, field)); \
377 IRB_PARENT(IRB_LEFT(old, field), field) = elm; \
378 if (IRB_RIGHT(old, field)) \
379 IRB_PARENT(IRB_RIGHT(old, field), field) = elm; \
380 if (parent) { \
381 left = parent; \
382 do { \
383 IRB_AUGMENT(left, field); \
384 } while ((left = IRB_PARENT(left, field)) != NULL); \
385 } \
386 goto color; \
387 } \
388 parent = IRB_PARENT(elm, field); \
389 color = IRB_COLOR(elm, field); \
390 if (child) \
391 IRB_PARENT(child, field) = parent; \
392 if (parent) { \
393 if (IRB_LEFT(parent, field) == elm) \
394 IRB_LEFT(parent, field) = child; \
395 else \
396 IRB_RIGHT(parent, field) = child; \
397 IRB_AUGMENT(parent, field); \
398 } else \
399 IRB_ROOT(head) = child; \
400 color: \
401 if (color == IRB_BLACK) \
402 name##_IRB_REMOVE_COLOR(head, parent, child); \
403 return (old); \
404 }
405
406#define IRB_GENERATE_INSERT(name, type, field, cmp, attr) \
407 /* Inserts a node into the IRB tree */ \
408 attr struct type *name##_IRB_INSERT(struct name *head, struct type *elm) \
409 { \
410 struct type *tmp; \
411 struct type *parent = NULL; \
412 int comp = 0; \
413 tmp = IRB_ROOT(head); \
414 while (tmp) { \
415 parent = tmp; \
416 comp = (cmp)(elm, parent); \
417 if (comp < 0) { \
418 tmp = IRB_LEFT(tmp, field); \
419 } else if (comp > 0) { \
420 tmp = IRB_RIGHT(tmp, field); \
421 } else \
422 return (tmp); \
423 } \
424 IRB_SET(elm, parent, field); \
425 if (parent != NULL) { \
426 if (comp < 0) \
427 IRB_LEFT(parent, field) = elm; \
428 else \
429 IRB_RIGHT(parent, field) = elm; \
430 } else \
431 IRB_ROOT(head) = elm; \
432 IRB_AUGMENT(elm, field); \
433 name##_IRB_INSERT_COLOR(head, elm); \
434 return (NULL); \
435 }
436
437#define IRB_GENERATE_FIND(name, type, field, cmp, attr) \
438 /* Finds the node with the same key as elm */ \
439 attr struct type *name##_IRB_FIND(struct name *head, struct type *elm) \
440 { \
441 struct type *tmp = IRB_ROOT(head); \
442 int comp; \
443 while (tmp) { \
444 comp = cmp(elm, tmp); \
445 if (comp < 0) \
446 tmp = IRB_LEFT(tmp, field); \
447 else if (comp > 0) \
448 tmp = IRB_RIGHT(tmp, field); \
449 else \
450 return (tmp); \
451 } \
452 return (NULL); \
453 }
454
455#define IRB_GENERATE_NFIND(name, type, field, cmp, attr) \
456 /* Finds the first node greater than or equal to the search key */ \
457 attr struct type *name##_IRB_NFIND(struct name *head, struct type *elm) \
458 { \
459 struct type *tmp = IRB_ROOT(head); \
460 struct type *res = NULL; \
461 int comp; \
462 while (tmp) { \
463 comp = cmp(elm, tmp); \
464 if (comp < 0) { \
465 res = tmp; \
466 tmp = IRB_LEFT(tmp, field); \
467 } else if (comp > 0) \
468 tmp = IRB_RIGHT(tmp, field); \
469 else \
470 return (tmp); \
471 } \
472 return (res); \
473 }
474
475#define IRB_GENERATE_NEXT(name, type, field, attr) \
476 /* ARGSUSED */ \
477 attr struct type *name##_IRB_NEXT(struct type *elm) \
478 { \
479 if (IRB_RIGHT(elm, field)) { \
480 elm = IRB_RIGHT(elm, field); \
481 while (IRB_LEFT(elm, field)) \
482 elm = IRB_LEFT(elm, field); \
483 } else { \
484 if (IRB_PARENT(elm, field) && (elm == IRB_LEFT(IRB_PARENT(elm, field), field))) \
485 elm = IRB_PARENT(elm, field); \
486 else { \
487 while (IRB_PARENT(elm, field) && \
488 (elm == IRB_RIGHT(IRB_PARENT(elm, field), field))) \
489 elm = IRB_PARENT(elm, field); \
490 elm = IRB_PARENT(elm, field); \
491 } \
492 } \
493 return (elm); \
494 }
495
496#define IRB_GENERATE_PREV(name, type, field, attr) \
497 /* ARGSUSED */ \
498 attr struct type *name##_IRB_PREV(struct type *elm) \
499 { \
500 if (IRB_LEFT(elm, field)) { \
501 elm = IRB_LEFT(elm, field); \
502 while (IRB_RIGHT(elm, field)) \
503 elm = IRB_RIGHT(elm, field); \
504 } else { \
505 if (IRB_PARENT(elm, field) && (elm == IRB_RIGHT(IRB_PARENT(elm, field), field))) \
506 elm = IRB_PARENT(elm, field); \
507 else { \
508 while (IRB_PARENT(elm, field) && (elm == IRB_LEFT(IRB_PARENT(elm, field), field))) \
509 elm = IRB_PARENT(elm, field); \
510 elm = IRB_PARENT(elm, field); \
511 } \
512 } \
513 return (elm); \
514 }
515
516#define IRB_GENERATE_MINMAX(name, type, field, attr) \
517 attr struct type *name##_IRB_MINMAX(struct name *head, int val) \
518 { \
519 struct type *tmp = IRB_ROOT(head); \
520 struct type *parent = NULL; \
521 while (tmp) { \
522 parent = tmp; \
523 if (val < 0) \
524 tmp = IRB_LEFT(tmp, field); \
525 else \
526 tmp = IRB_RIGHT(tmp, field); \
527 } \
528 return (parent); \
529 }
530
531#define IRB_NEGINF -1
532#define IRB_INF 1
533
534#define IRB_INSERT(name, x, y) name##_IRB_INSERT(x, y)
535#define IRB_REMOVE(name, x, y) name##_IRB_REMOVE(x, y)
536#define IRB_FIND(name, x, y) name##_IRB_FIND(x, y)
537#define IRB_NFIND(name, x, y) name##_IRB_NFIND(x, y)
538#define IRB_NEXT(name, x, y) name##_IRB_NEXT(y)
539#define IRB_PREV(name, x, y) name##_IRB_PREV(y)
540#define IRB_MIN(name, x) name##_IRB_MINMAX(x, IRB_NEGINF)
541#define IRB_MAX(name, x) name##_IRB_MINMAX(x, IRB_INF)
542
543#define IRB_FOREACH(x, name, head) \
544 for ((x) = IRB_MIN(name, head); (x) != NULL; (x) = name##_IRB_NEXT(x))
545
546#define IRB_FOREACH_FROM(x, name, y) \
547 for ((x) = (y); ((x) != NULL) && ((y) = name##_IRB_NEXT(x), (x) != NULL); (x) = (y))
548
549#define IRB_FOREACH_SAFE(x, name, head, y) \
550 for ((x) = IRB_MIN(name, head); ((x) != NULL) && ((y) = name##_IRB_NEXT(x), (x) != NULL); \
551 (x) = (y))
552
553#define IRB_FOREACH_REVERSE(x, name, head) \
554 for ((x) = IRB_MAX(name, head); (x) != NULL; (x) = name##_IRB_PREV(x))
555
556#define IRB_FOREACH_REVERSE_FROM(x, name, y) \
557 for ((x) = (y); ((x) != NULL) && ((y) = name##_IRB_PREV(x), (x) != NULL); (x) = (y))
558
559#define IRB_FOREACH_REVERSE_SAFE(x, name, head, y) \
560 for ((x) = IRB_MAX(name, head); ((x) != NULL) && ((y) = name##_IRB_PREV(x), (x) != NULL); \
561 (x) = (y))
562
563#endif /* _SYS_INTERVALTREE_H_ */