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