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_ */