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