suricata
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$ */
4 
5 /*-
6  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
7  *
8  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  * notice, this list of conditions and the following disclaimer.
16  * 2. Redistributions in binary form must reproduce the above copyright
17  * notice, this list of conditions and the following disclaimer in the
18  * documentation and/or other materials provided with the distribution.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
21  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
23  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
29  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30  */
31 
32 #ifndef _SYS_TREE_H_
33 #define _SYS_TREE_H_
34 
35 #if defined(__clang_analyzer__)
36 #define _T_ASSERT(a) assert((a))
37 #else
38 #define _T_ASSERT(a)
39 #endif
40 
41 /*
42  * This file defines data structures for different types of trees:
43  * splay trees and red-black trees.
44  *
45  * A splay tree is a self-organizing data structure. Every operation
46  * on the tree causes a splay to happen. The splay moves the requested
47  * node to the root of the tree and partly rebalances it.
48  *
49  * This has the benefit that request locality causes faster lookups as
50  * the requested nodes move to the top of the tree. On the other hand,
51  * every lookup causes memory writes.
52  *
53  * The Balance Theorem bounds the total access time for m operations
54  * and n inserts on an initially empty tree as O((m + n)lg n). The
55  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
56  *
57  * A red-black tree is a binary search tree with the node color as an
58  * extra attribute. It fulfills a set of conditions:
59  * - every search path from the root to a leaf consists of the
60  * same number of black nodes,
61  * - each red node (except for the root) has a black parent,
62  * - each leaf node is black.
63  *
64  * Every operation on a red-black tree is bounded as O(lg n).
65  * The maximum height of a red-black tree is 2lg (n+1).
66  */
67 
68 #define SPLAY_HEAD(name, type) \
69 struct name { \
70  struct type *sph_root; /* root of the tree */ \
71 }
72 
73 #define SPLAY_INITIALIZER(root) \
74  { NULL }
75 
76 #define SPLAY_INIT(root) do { \
77  (root)->sph_root = NULL; \
78 } while (/*CONSTCOND*/ 0)
79 
80 #define SPLAY_ENTRY(type) \
81 struct { \
82  struct type *spe_left; /* left element */ \
83  struct type *spe_right; /* right element */ \
84 }
85 
86 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
87 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
88 #define SPLAY_ROOT(head) (head)->sph_root
89 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
90 
91 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
92 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
93  SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
94  SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
95  (head)->sph_root = tmp; \
96 } while (/*CONSTCOND*/ 0)
97 
98 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
99  SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
100  SPLAY_LEFT(tmp, field) = (head)->sph_root; \
101  (head)->sph_root = tmp; \
102 } while (/*CONSTCOND*/ 0)
103 
104 #define SPLAY_LINKLEFT(head, tmp, field) do { \
105  SPLAY_LEFT(tmp, field) = (head)->sph_root; \
106  tmp = (head)->sph_root; \
107  (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
108 } while (/*CONSTCOND*/ 0)
109 
110 #define SPLAY_LINKRIGHT(head, tmp, field) 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 (/*CONSTCOND*/ 0)
115 
116 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
117  SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
118  SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
119  SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
120  SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
121 } while (/*CONSTCOND*/ 0)
122 
123 /* Generates prototypes and inline functions */
124 
125 #define SPLAY_PROTOTYPE(name, type, field, cmp) \
126 void name##_SPLAY(struct name *, struct type *); \
127 void name##_SPLAY_MINMAX(struct name *, int); \
128 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
129 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
130  \
131 /* Finds the node with the same key as elm */ \
132 static __inline struct type * \
133 name##_SPLAY_FIND(struct name *head, struct type *elm) \
134 { \
135  if (SPLAY_EMPTY(head)) \
136  return(NULL); \
137  name##_SPLAY(head, elm); \
138  if ((cmp)(elm, (head)->sph_root) == 0) \
139  return (head->sph_root); \
140  return (NULL); \
141 } \
142  \
143 static __inline struct type * \
144 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
145 { \
146  name##_SPLAY(head, elm); \
147  if (SPLAY_RIGHT(elm, field) != NULL) { \
148  elm = SPLAY_RIGHT(elm, field); \
149  while (SPLAY_LEFT(elm, field) != NULL) { \
150  elm = SPLAY_LEFT(elm, field); \
151  } \
152  } else \
153  elm = NULL; \
154  return (elm); \
155 } \
156  \
157 static __inline struct type * \
158 name##_SPLAY_MIN_MAX(struct name *head, int val) \
159 { \
160  name##_SPLAY_MINMAX(head, val); \
161  return (SPLAY_ROOT(head)); \
162 }
163 
164 /* Main splay operation.
165  * Moves node close to the key of elm to top
166  */
167 #define SPLAY_GENERATE(name, type, field, cmp) \
168 struct type * \
169 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
170 { \
171  if (SPLAY_EMPTY(head)) { \
172  SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
173  } else { \
174  int __comp; \
175  name##_SPLAY(head, elm); \
176  __comp = (cmp)(elm, (head)->sph_root); \
177  if(__comp < 0) { \
178  SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
179  SPLAY_RIGHT(elm, field) = (head)->sph_root; \
180  SPLAY_LEFT((head)->sph_root, field) = NULL; \
181  } else if (__comp > 0) { \
182  SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
183  SPLAY_LEFT(elm, field) = (head)->sph_root; \
184  SPLAY_RIGHT((head)->sph_root, field) = NULL; \
185  } else \
186  return ((head)->sph_root); \
187  } \
188  (head)->sph_root = (elm); \
189  return (NULL); \
190 } \
191  \
192 struct type * \
193 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
194 { \
195  struct type *__tmp; \
196  if (SPLAY_EMPTY(head)) \
197  return (NULL); \
198  name##_SPLAY(head, elm); \
199  if ((cmp)(elm, (head)->sph_root) == 0) { \
200  if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
201  (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
202  } else { \
203  __tmp = SPLAY_RIGHT((head)->sph_root, field); \
204  (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
205  name##_SPLAY(head, elm); \
206  SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
207  } \
208  return (elm); \
209  } \
210  return (NULL); \
211 } \
212  \
213 void \
214 name##_SPLAY(struct name *head, struct type *elm) \
215 { \
216  struct type __node, *__left, *__right, *__tmp; \
217  int __comp; \
218 \
219  SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
220  __left = __right = &__node; \
221 \
222  while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
223  if (__comp < 0) { \
224  __tmp = SPLAY_LEFT((head)->sph_root, field); \
225  if (__tmp == NULL) \
226  break; \
227  if ((cmp)(elm, __tmp) < 0){ \
228  SPLAY_ROTATE_RIGHT(head, __tmp, field); \
229  if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
230  break; \
231  } \
232  SPLAY_LINKLEFT(head, __right, field); \
233  } else if (__comp > 0) { \
234  __tmp = SPLAY_RIGHT((head)->sph_root, field); \
235  if (__tmp == NULL) \
236  break; \
237  if ((cmp)(elm, __tmp) > 0){ \
238  SPLAY_ROTATE_LEFT(head, __tmp, field); \
239  if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
240  break; \
241  } \
242  SPLAY_LINKRIGHT(head, __left, field); \
243  } \
244  } \
245  SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
246 } \
247  \
248 /* Splay with either the minimum or the maximum element \
249  * Used to find minimum or maximum element in tree. \
250  */ \
251 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
252 { \
253  struct type __node, *__left, *__right, *__tmp; \
254 \
255  SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
256  __left = __right = &__node; \
257 \
258  while (1) { \
259  if (__comp < 0) { \
260  __tmp = SPLAY_LEFT((head)->sph_root, field); \
261  if (__tmp == NULL) \
262  break; \
263  if (__comp < 0){ \
264  SPLAY_ROTATE_RIGHT(head, __tmp, field); \
265  if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
266  break; \
267  } \
268  SPLAY_LINKLEFT(head, __right, field); \
269  } else if (__comp > 0) { \
270  __tmp = SPLAY_RIGHT((head)->sph_root, field); \
271  if (__tmp == NULL) \
272  break; \
273  if (__comp > 0) { \
274  SPLAY_ROTATE_LEFT(head, __tmp, field); \
275  if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
276  break; \
277  } \
278  SPLAY_LINKRIGHT(head, __left, field); \
279  } \
280  } \
281  SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
282 }
283 
284 #define SPLAY_NEGINF -1
285 #define SPLAY_INF 1
286 
287 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
288 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
289 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
290 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
291 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
292  : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
293 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
294  : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
295 
296 #define SPLAY_FOREACH(x, name, head) \
297  for ((x) = SPLAY_MIN(name, head); \
298  (x) != NULL; \
299  (x) = SPLAY_NEXT(name, head, x))
300 
301 /* Macros that define a red-black tree */
302 #define RB_HEAD(name, type) \
303 struct name { \
304  struct type *rbh_root; /* root of the tree */ \
305 }
306 
307 #define RB_INITIALIZER(root) \
308  { NULL }
309 
310 #define RB_INIT(root) do { \
311  (root)->rbh_root = NULL; \
312 } while (/*CONSTCOND*/ 0)
313 
314 #define RB_BLACK 0
315 #define RB_RED 1
316 #define RB_ENTRY(type) \
317 struct { \
318  struct type *rbe_left; /* left element */ \
319  struct type *rbe_right; /* right element */ \
320  struct type *rbe_parent; /* parent element */ \
321  int rbe_color; /* node color */ \
322 }
323 
324 #define RB_LEFT(elm, field) (elm)->field.rbe_left
325 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
326 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
327 #define RB_COLOR(elm, field) (elm)->field.rbe_color
328 #define RB_ROOT(head) (head)->rbh_root
329 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
330 
331 #define RB_SET(elm, parent, field) do { \
332  RB_PARENT(elm, field) = parent; \
333  RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
334  RB_COLOR(elm, field) = RB_RED; \
335 } while (/*CONSTCOND*/ 0)
336 
337 #define RB_SET_BLACKRED(black, red, field) do { \
338  RB_COLOR(black, field) = RB_BLACK; \
339  RB_COLOR(red, field) = RB_RED; \
340 } while (/*CONSTCOND*/ 0)
341 
342 #ifndef RB_AUGMENT
343 #define RB_AUGMENT(x) do {} while (0)
344 #endif
345 
346 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
347  (tmp) = RB_RIGHT(elm, field); \
348  if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
349  RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
350  } \
351  RB_AUGMENT(elm); \
352  if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
353  if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
354  RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
355  else \
356  RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
357  } else \
358  (head)->rbh_root = (tmp); \
359  RB_LEFT(tmp, field) = (elm); \
360  RB_PARENT(elm, field) = (tmp); \
361  RB_AUGMENT(tmp); \
362  if ((RB_PARENT(tmp, field))) \
363  RB_AUGMENT(RB_PARENT(tmp, field)); \
364 } while (/*CONSTCOND*/ 0)
365 
366 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
367  (tmp) = RB_LEFT(elm, field); \
368  if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
369  RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
370  } \
371  RB_AUGMENT(elm); \
372  if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
373  if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
374  RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
375  else \
376  RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
377  } else \
378  (head)->rbh_root = (tmp); \
379  RB_RIGHT(tmp, field) = (elm); \
380  RB_PARENT(elm, field) = (tmp); \
381  RB_AUGMENT(tmp); \
382  if ((RB_PARENT(tmp, field))) \
383  RB_AUGMENT(RB_PARENT(tmp, field)); \
384 } while (/*CONSTCOND*/ 0)
385 
386 /* Generates prototypes and inline functions */
387 #define RB_PROTOTYPE(name, type, field, cmp) \
388  RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
389 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
390  RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
391 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
392  RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
393  RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
394  RB_PROTOTYPE_INSERT(name, type, attr); \
395  RB_PROTOTYPE_REMOVE(name, type, attr); \
396  RB_PROTOTYPE_FIND(name, type, attr); \
397  RB_PROTOTYPE_NFIND(name, type, attr); \
398  RB_PROTOTYPE_NEXT(name, type, attr); \
399  RB_PROTOTYPE_PREV(name, type, attr); \
400  RB_PROTOTYPE_MINMAX(name, type, attr);
401 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
402  attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
403 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
404  attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *)
405 #define RB_PROTOTYPE_REMOVE(name, type, attr) \
406  attr struct type *name##_RB_REMOVE(struct name *, struct type *)
407 #define RB_PROTOTYPE_INSERT(name, type, attr) \
408  attr struct type *name##_RB_INSERT(struct name *, struct type *)
409 #define RB_PROTOTYPE_FIND(name, type, attr) \
410  attr struct type *name##_RB_FIND(struct name *, struct type *)
411 #define RB_PROTOTYPE_NFIND(name, type, attr) \
412  attr struct type *name##_RB_NFIND(struct name *, struct type *)
413 #define RB_PROTOTYPE_NEXT(name, type, attr) \
414  attr struct type *name##_RB_NEXT(struct type *)
415 #define RB_PROTOTYPE_PREV(name, type, attr) \
416  attr struct type *name##_RB_PREV(struct type *)
417 #define RB_PROTOTYPE_MINMAX(name, type, attr) \
418  attr struct type *name##_RB_MINMAX(struct name *, int)
419 
420 /* Main rb operation.
421  * Moves node close to the key of elm to top
422  */
423 #define RB_GENERATE(name, type, field, cmp) \
424  RB_GENERATE_INTERNAL(name, type, field, cmp,)
425 #define RB_GENERATE_STATIC(name, type, field, cmp) \
426  RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
427 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
428  RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
429  RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
430  RB_GENERATE_INSERT(name, type, field, cmp, attr) \
431  RB_GENERATE_REMOVE(name, type, field, attr) \
432  RB_GENERATE_FIND(name, type, field, cmp, attr) \
433  RB_GENERATE_NFIND(name, type, field, cmp, attr) \
434  RB_GENERATE_NEXT(name, type, field, attr) \
435  RB_GENERATE_PREV(name, type, field, attr) \
436  RB_GENERATE_MINMAX(name, type, field, attr)
437 
438 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
439 attr void \
440 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
441 { \
442  struct type *parent, *gparent, *tmp; \
443  while ((parent = RB_PARENT(elm, field)) != NULL && \
444  RB_COLOR(parent, field) == RB_RED) { \
445  gparent = RB_PARENT(parent, field); \
446  _T_ASSERT(gparent); \
447  if (parent == RB_LEFT(gparent, field)) { \
448  tmp = RB_RIGHT(gparent, field); \
449  if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
450  RB_COLOR(tmp, field) = RB_BLACK; \
451  RB_SET_BLACKRED(parent, gparent, field);\
452  elm = gparent; \
453  continue; \
454  } \
455  if (RB_RIGHT(parent, field) == elm) { \
456  RB_ROTATE_LEFT(head, parent, tmp, field);\
457  tmp = parent; \
458  parent = elm; \
459  elm = tmp; \
460  } \
461  RB_SET_BLACKRED(parent, gparent, field); \
462  RB_ROTATE_RIGHT(head, gparent, tmp, field); \
463  } else { \
464  tmp = RB_LEFT(gparent, field); \
465  if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
466  RB_COLOR(tmp, field) = RB_BLACK; \
467  RB_SET_BLACKRED(parent, gparent, field);\
468  elm = gparent; \
469  continue; \
470  } \
471  if (RB_LEFT(parent, field) == elm) { \
472  RB_ROTATE_RIGHT(head, parent, tmp, field);\
473  tmp = parent; \
474  parent = elm; \
475  elm = tmp; \
476  } \
477  RB_SET_BLACKRED(parent, gparent, field); \
478  RB_ROTATE_LEFT(head, gparent, tmp, field); \
479  } \
480  } \
481  RB_COLOR(head->rbh_root, field) = RB_BLACK; \
482 }
483 
484 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
485 attr void \
486 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
487 { \
488  struct type *tmp; \
489  while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
490  elm != RB_ROOT(head)) { \
491  if (RB_LEFT(parent, field) == elm) { \
492  tmp = RB_RIGHT(parent, field); \
493  if (RB_COLOR(tmp, field) == RB_RED) { \
494  RB_SET_BLACKRED(tmp, parent, field); \
495  RB_ROTATE_LEFT(head, parent, tmp, field);\
496  tmp = RB_RIGHT(parent, field); \
497  } \
498  _T_ASSERT(tmp); \
499  if ((RB_LEFT(tmp, field) == NULL || \
500  RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
501  (RB_RIGHT(tmp, field) == NULL || \
502  RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
503  RB_COLOR(tmp, field) = RB_RED; \
504  elm = parent; \
505  parent = RB_PARENT(elm, field); \
506  } else { \
507  if (RB_RIGHT(tmp, field) == NULL || \
508  RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
509  struct type *oleft; \
510  if ((oleft = RB_LEFT(tmp, field)) \
511  != NULL) \
512  RB_COLOR(oleft, field) = RB_BLACK;\
513  RB_COLOR(tmp, field) = RB_RED; \
514  RB_ROTATE_RIGHT(head, tmp, oleft, field);\
515  tmp = RB_RIGHT(parent, field); \
516  } \
517  RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
518  RB_COLOR(parent, field) = RB_BLACK; \
519  if (RB_RIGHT(tmp, field)) \
520  RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
521  RB_ROTATE_LEFT(head, parent, tmp, field);\
522  elm = RB_ROOT(head); \
523  break; \
524  } \
525  } else { \
526  tmp = RB_LEFT(parent, field); \
527  if (RB_COLOR(tmp, field) == RB_RED) { \
528  RB_SET_BLACKRED(tmp, parent, field); \
529  RB_ROTATE_RIGHT(head, parent, tmp, field);\
530  tmp = RB_LEFT(parent, field); \
531  } \
532  _T_ASSERT(tmp); \
533  if ((RB_LEFT(tmp, field) == NULL || \
534  RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
535  (RB_RIGHT(tmp, field) == NULL || \
536  RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
537  RB_COLOR(tmp, field) = RB_RED; \
538  elm = parent; \
539  parent = RB_PARENT(elm, field); \
540  } else { \
541  if (RB_LEFT(tmp, field) == NULL || \
542  RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
543  struct type *oright; \
544  if ((oright = RB_RIGHT(tmp, field)) \
545  != NULL) \
546  RB_COLOR(oright, field) = RB_BLACK;\
547  RB_COLOR(tmp, field) = RB_RED; \
548  RB_ROTATE_LEFT(head, tmp, oright, field);\
549  tmp = RB_LEFT(parent, field); \
550  } \
551  RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
552  RB_COLOR(parent, field) = RB_BLACK; \
553  if (RB_LEFT(tmp, field)) \
554  RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
555  RB_ROTATE_RIGHT(head, parent, tmp, field);\
556  elm = RB_ROOT(head); \
557  break; \
558  } \
559  } \
560  } \
561  if (elm) \
562  RB_COLOR(elm, field) = RB_BLACK; \
563 }
564 
565 #define RB_GENERATE_REMOVE(name, type, field, attr) \
566 attr struct type * \
567 name##_RB_REMOVE(struct name *head, struct type *elm) \
568 { \
569  struct type *child, *parent, *old = elm; \
570  int color; \
571  if (RB_LEFT(elm, field) == NULL) \
572  child = RB_RIGHT(elm, field); \
573  else if (RB_RIGHT(elm, field) == NULL) \
574  child = RB_LEFT(elm, field); \
575  else { \
576  struct type *left; \
577  elm = RB_RIGHT(elm, field); \
578  while ((left = RB_LEFT(elm, field)) != NULL) \
579  elm = left; \
580  child = RB_RIGHT(elm, field); \
581  parent = RB_PARENT(elm, field); \
582  color = RB_COLOR(elm, field); \
583  if (child) \
584  RB_PARENT(child, field) = parent; \
585  if (parent) { \
586  if (RB_LEFT(parent, field) == elm) \
587  RB_LEFT(parent, field) = child; \
588  else \
589  RB_RIGHT(parent, field) = child; \
590  RB_AUGMENT(parent); \
591  } else \
592  RB_ROOT(head) = child; \
593  if (RB_PARENT(elm, field) == old) \
594  parent = elm; \
595  _T_ASSERT((old)); \
596  (elm)->field = (old)->field; \
597  if (RB_PARENT(old, field)) { \
598  if (RB_LEFT(RB_PARENT(old, field), field) == old)\
599  RB_LEFT(RB_PARENT(old, field), field) = elm;\
600  else \
601  RB_RIGHT(RB_PARENT(old, field), field) = elm;\
602  RB_AUGMENT(RB_PARENT(old, field)); \
603  } else \
604  RB_ROOT(head) = elm; \
605  _T_ASSERT(old); \
606  _T_ASSERT(RB_LEFT(old, field)); \
607  RB_PARENT(RB_LEFT(old, field), field) = elm; \
608  if (RB_RIGHT(old, field)) \
609  RB_PARENT(RB_RIGHT(old, field), field) = elm; \
610  if (parent) { \
611  left = parent; \
612  do { \
613  RB_AUGMENT(left); \
614  } while ((left = RB_PARENT(left, field)) != NULL); \
615  } \
616  goto color; \
617  } \
618  parent = RB_PARENT(elm, field); \
619  color = RB_COLOR(elm, field); \
620  if (child) \
621  RB_PARENT(child, field) = parent; \
622  if (parent) { \
623  if (RB_LEFT(parent, field) == elm) \
624  RB_LEFT(parent, field) = child; \
625  else \
626  RB_RIGHT(parent, field) = child; \
627  RB_AUGMENT(parent); \
628  } else \
629  RB_ROOT(head) = child; \
630 color: \
631  if (color == RB_BLACK) \
632  name##_RB_REMOVE_COLOR(head, parent, child); \
633  return (old); \
634 } \
635 
636 #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \
637 /* Inserts a node into the RB tree */ \
638 attr struct type * \
639 name##_RB_INSERT(struct name *head, struct type *elm) \
640 { \
641  struct type *tmp; \
642  struct type *parent = NULL; \
643  int comp = 0; \
644  tmp = RB_ROOT(head); \
645  while (tmp) { \
646  parent = tmp; \
647  comp = (cmp)(elm, parent); \
648  if (comp < 0) \
649  tmp = RB_LEFT(tmp, field); \
650  else if (comp > 0) \
651  tmp = RB_RIGHT(tmp, field); \
652  else \
653  return (tmp); \
654  } \
655  RB_SET(elm, parent, field); \
656  if (parent != NULL) { \
657  if (comp < 0) \
658  RB_LEFT(parent, field) = elm; \
659  else \
660  RB_RIGHT(parent, field) = elm; \
661  RB_AUGMENT(parent); \
662  } else \
663  RB_ROOT(head) = elm; \
664  name##_RB_INSERT_COLOR(head, elm); \
665  return (NULL); \
666 }
667 
668 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \
669 /* Finds the node with the same key as elm */ \
670 attr struct type * \
671 name##_RB_FIND(struct name *head, struct type *elm) \
672 { \
673  struct type *tmp = RB_ROOT(head); \
674  int comp; \
675  while (tmp) { \
676  comp = cmp(elm, tmp); \
677  if (comp < 0) \
678  tmp = RB_LEFT(tmp, field); \
679  else if (comp > 0) \
680  tmp = RB_RIGHT(tmp, field); \
681  else \
682  return (tmp); \
683  } \
684  return (NULL); \
685 }
686 
687 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \
688 /* Finds the first node greater than or equal to the search key */ \
689 attr struct type * \
690 name##_RB_NFIND(struct name *head, struct type *elm) \
691 { \
692  struct type *tmp = RB_ROOT(head); \
693  struct type *res = NULL; \
694  int comp; \
695  while (tmp) { \
696  comp = cmp(elm, tmp); \
697  if (comp < 0) { \
698  res = tmp; \
699  tmp = RB_LEFT(tmp, field); \
700  } \
701  else if (comp > 0) \
702  tmp = RB_RIGHT(tmp, field); \
703  else \
704  return (tmp); \
705  } \
706  return (res); \
707 }
708 
709 #define RB_GENERATE_NEXT(name, type, field, attr) \
710 /* ARGSUSED */ \
711 attr struct type * \
712 name##_RB_NEXT(struct type *elm) \
713 { \
714  if (RB_RIGHT(elm, field)) { \
715  elm = RB_RIGHT(elm, field); \
716  while (RB_LEFT(elm, field)) \
717  elm = RB_LEFT(elm, field); \
718  } else { \
719  if (RB_PARENT(elm, field) && \
720  (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
721  elm = RB_PARENT(elm, field); \
722  else { \
723  while (RB_PARENT(elm, field) && \
724  (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
725  elm = RB_PARENT(elm, field); \
726  elm = RB_PARENT(elm, field); \
727  } \
728  } \
729  return (elm); \
730 }
731 
732 #define RB_GENERATE_PREV(name, type, field, attr) \
733 /* ARGSUSED */ \
734 attr struct type * \
735 name##_RB_PREV(struct type *elm) \
736 { \
737  if (RB_LEFT(elm, field)) { \
738  elm = RB_LEFT(elm, field); \
739  while (RB_RIGHT(elm, field)) \
740  elm = RB_RIGHT(elm, field); \
741  } else { \
742  if (RB_PARENT(elm, field) && \
743  (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
744  elm = RB_PARENT(elm, field); \
745  else { \
746  while (RB_PARENT(elm, field) && \
747  (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
748  elm = RB_PARENT(elm, field); \
749  elm = RB_PARENT(elm, field); \
750  } \
751  } \
752  return (elm); \
753 }
754 
755 #define RB_GENERATE_MINMAX(name, type, field, attr) \
756 attr struct type * \
757 name##_RB_MINMAX(struct name *head, int val) \
758 { \
759  struct type *tmp = RB_ROOT(head); \
760  struct type *parent = NULL; \
761  while (tmp) { \
762  parent = tmp; \
763  if (val < 0) \
764  tmp = RB_LEFT(tmp, field); \
765  else \
766  tmp = RB_RIGHT(tmp, field); \
767  } \
768  return (parent); \
769 }
770 
771 #define RB_NEGINF -1
772 #define RB_INF 1
773 
774 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
775 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
776 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
777 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
778 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
779 #define RB_PREV(name, x, y) name##_RB_PREV(y)
780 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
781 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
782 
783 #define RB_FOREACH(x, name, head) \
784  for ((x) = RB_MIN(name, head); \
785  (x) != NULL; \
786  (x) = name##_RB_NEXT(x))
787 
788 #define RB_FOREACH_FROM(x, name, y) \
789  for ((x) = (y); \
790  ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
791  (x) = (y))
792 
793 #define RB_FOREACH_SAFE(x, name, head, y) \
794  for ((x) = RB_MIN(name, head); \
795  ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
796  (x) = (y))
797 
798 #define RB_FOREACH_REVERSE(x, name, head) \
799  for ((x) = RB_MAX(name, head); \
800  (x) != NULL; \
801  (x) = name##_RB_PREV(x))
802 
803 #define RB_FOREACH_REVERSE_FROM(x, name, y) \
804  for ((x) = (y); \
805  ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
806  (x) = (y))
807 
808 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
809  for ((x) = RB_MAX(name, head); \
810  ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
811  (x) = (y))
812 
813 #endif /* _SYS_TREE_H_ */