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