CUBRID Engine  latest
rb_tree.h
Go to the documentation of this file.
1 /*-
2  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25 
26 /*
27  * This source is from sys/tree.h of Free BSD with following modifications
28  * 1. remove SPLAY tree part
29  * 2. etc. (trivial)
30  */
31 
32 #ifndef _RB_TREE_H_
33 #define _RB_TREE_H_
34 
35 /* Macros that define a red-black tree */
36 #define RB_HEAD(name, type) \
37 struct name { \
38  struct type *rbh_root; /* root of the tree */ \
39 }
40 
41 #define RB_INITIALIZER(root) \
42  { NULL }
43 
44 #define RB_INIT(root) do { \
45  (root)->rbh_root = NULL; \
46 } while (/*CONSTCOND*/ 0)
47 
48 #define RB_BLACK 0
49 #define RB_RED 1
50 #define RB_ENTRY(type) \
51 struct { \
52  struct type *rbe_left; /* left element */ \
53  struct type *rbe_right; /* right element */ \
54  struct type *rbe_parent; /* parent element */ \
55  int rbe_color; /* node color */ \
56 }
57 
58 #define RB_LEFT(elm, field) (elm)->field.rbe_left
59 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
60 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
61 #define RB_COLOR(elm, field) (elm)->field.rbe_color
62 #define RB_ROOT(head) (head)->rbh_root
63 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
64 
65 #define RB_SET(elm, parent, field) do { \
66  RB_PARENT(elm, field) = parent; \
67  RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
68  RB_COLOR(elm, field) = RB_RED; \
69 } while (/*CONSTCOND*/ 0)
70 
71 #define RB_SET_BLACKRED(black, red, field) do { \
72  RB_COLOR(black, field) = RB_BLACK; \
73  RB_COLOR(red, field) = RB_RED; \
74 } while (/*CONSTCOND*/ 0)
75 
76 #ifndef RB_AUGMENT
77 #define RB_AUGMENT(x) do {} while (0)
78 #endif
79 
80 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
81  (tmp) = RB_RIGHT(elm, field); \
82  if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
83  RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
84  } \
85  RB_AUGMENT(elm); \
86  if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
87  if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
88  RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
89  else \
90  RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
91  } else \
92  (head)->rbh_root = (tmp); \
93  RB_LEFT(tmp, field) = (elm); \
94  RB_PARENT(elm, field) = (tmp); \
95  RB_AUGMENT(tmp); \
96  if ((RB_PARENT(tmp, field))) \
97  RB_AUGMENT(RB_PARENT(tmp, field)); \
98 } while (/*CONSTCOND*/ 0)
99 
100 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
101  (tmp) = RB_LEFT(elm, field); \
102  if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
103  RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
104  } \
105  RB_AUGMENT(elm); \
106  if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
107  if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
108  RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
109  else \
110  RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
111  } else \
112  (head)->rbh_root = (tmp); \
113  RB_RIGHT(tmp, field) = (elm); \
114  RB_PARENT(elm, field) = (tmp); \
115  RB_AUGMENT(tmp); \
116  if ((RB_PARENT(tmp, field))) \
117  RB_AUGMENT(RB_PARENT(tmp, field)); \
118 } while (/*CONSTCOND*/ 0)
119 
120 /* Generates prototypes and inline functions */
121 #define RB_PROTOTYPE(name, type, field, cmp) \
122  RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
123 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
124  RB_PROTOTYPE_INTERNAL(name, type, field, cmp, static)
125 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
126 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
127 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
128 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
129 attr struct type *name##_RB_INSERT(struct name *, struct type *); \
130 attr struct type *name##_RB_FIND(struct name *, struct type *); \
131 attr struct type *name##_RB_NFIND(struct name *, struct type *); \
132 attr struct type *name##_RB_NEXT(struct type *); \
133 attr struct type *name##_RB_PREV(struct type *); \
134 attr struct type *name##_RB_MINMAX(struct name *, int); \
135  \
136 
137 /* Main rb operation.
138  * Moves node close to the key of elm to top
139  */
140 #define RB_GENERATE(name, type, field, cmp) \
141  RB_GENERATE_INTERNAL(name, type, field, cmp,)
142 #define RB_GENERATE_STATIC(name, type, field, cmp) \
143  RB_GENERATE_INTERNAL(name, type, field, cmp, static)
144 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
145 attr void \
146 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
147 { \
148  struct type *parent, *gparent, *tmp; \
149  while ((parent = RB_PARENT(elm, field)) != NULL && \
150  RB_COLOR(parent, field) == RB_RED) { \
151  gparent = RB_PARENT(parent, field); \
152  if (parent == RB_LEFT(gparent, field)) { \
153  tmp = RB_RIGHT(gparent, field); \
154  if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
155  RB_COLOR(tmp, field) = RB_BLACK; \
156  RB_SET_BLACKRED(parent, gparent, field);\
157  elm = gparent; \
158  continue; \
159  } \
160  if (RB_RIGHT(parent, field) == elm) { \
161  RB_ROTATE_LEFT(head, parent, tmp, field);\
162  tmp = parent; \
163  parent = elm; \
164  elm = tmp; \
165  } \
166  RB_SET_BLACKRED(parent, gparent, field); \
167  RB_ROTATE_RIGHT(head, gparent, tmp, field); \
168  } else { \
169  tmp = RB_LEFT(gparent, field); \
170  if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
171  RB_COLOR(tmp, field) = RB_BLACK; \
172  RB_SET_BLACKRED(parent, gparent, field);\
173  elm = gparent; \
174  continue; \
175  } \
176  if (RB_LEFT(parent, field) == elm) { \
177  RB_ROTATE_RIGHT(head, parent, tmp, field);\
178  tmp = parent; \
179  parent = elm; \
180  elm = tmp; \
181  } \
182  RB_SET_BLACKRED(parent, gparent, field); \
183  RB_ROTATE_LEFT(head, gparent, tmp, field); \
184  } \
185  } \
186  RB_COLOR(head->rbh_root, field) = RB_BLACK; \
187 } \
188  \
189 attr void \
190 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
191 { \
192  struct type *tmp; \
193  while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
194  elm != RB_ROOT(head)) { \
195  if (RB_LEFT(parent, field) == elm) { \
196  tmp = RB_RIGHT(parent, field); \
197  if (RB_COLOR(tmp, field) == RB_RED) { \
198  RB_SET_BLACKRED(tmp, parent, field); \
199  RB_ROTATE_LEFT(head, parent, tmp, field);\
200  tmp = RB_RIGHT(parent, field); \
201  } \
202  if ((RB_LEFT(tmp, field) == NULL || \
203  RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
204  (RB_RIGHT(tmp, field) == NULL || \
205  RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
206  RB_COLOR(tmp, field) = RB_RED; \
207  elm = parent; \
208  parent = RB_PARENT(elm, field); \
209  } else { \
210  if (RB_RIGHT(tmp, field) == NULL || \
211  RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
212  struct type *oleft; \
213  if ((oleft = RB_LEFT(tmp, field)) \
214  != NULL) \
215  RB_COLOR(oleft, field) = RB_BLACK;\
216  RB_COLOR(tmp, field) = RB_RED; \
217  RB_ROTATE_RIGHT(head, tmp, oleft, field);\
218  tmp = RB_RIGHT(parent, field); \
219  } \
220  RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
221  RB_COLOR(parent, field) = RB_BLACK; \
222  if (RB_RIGHT(tmp, field)) \
223  RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
224  RB_ROTATE_LEFT(head, parent, tmp, field);\
225  elm = RB_ROOT(head); \
226  break; \
227  } \
228  } else { \
229  tmp = RB_LEFT(parent, field); \
230  if (RB_COLOR(tmp, field) == RB_RED) { \
231  RB_SET_BLACKRED(tmp, parent, field); \
232  RB_ROTATE_RIGHT(head, parent, tmp, field);\
233  tmp = RB_LEFT(parent, field); \
234  } \
235  if ((RB_LEFT(tmp, field) == NULL || \
236  RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
237  (RB_RIGHT(tmp, field) == NULL || \
238  RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
239  RB_COLOR(tmp, field) = RB_RED; \
240  elm = parent; \
241  parent = RB_PARENT(elm, field); \
242  } else { \
243  if (RB_LEFT(tmp, field) == NULL || \
244  RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
245  struct type *oright; \
246  if ((oright = RB_RIGHT(tmp, field)) \
247  != NULL) \
248  RB_COLOR(oright, field) = RB_BLACK;\
249  RB_COLOR(tmp, field) = RB_RED; \
250  RB_ROTATE_LEFT(head, tmp, oright, field);\
251  tmp = RB_LEFT(parent, field); \
252  } \
253  RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
254  RB_COLOR(parent, field) = RB_BLACK; \
255  if (RB_LEFT(tmp, field)) \
256  RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
257  RB_ROTATE_RIGHT(head, parent, tmp, field);\
258  elm = RB_ROOT(head); \
259  break; \
260  } \
261  } \
262  } \
263  if (elm) \
264  RB_COLOR(elm, field) = RB_BLACK; \
265 } \
266  \
267 attr struct type * \
268 name##_RB_REMOVE(struct name *head, struct type *elm) \
269 { \
270  struct type *child, *parent, *old = elm; \
271  int color; \
272  if (RB_LEFT(elm, field) == NULL) \
273  child = RB_RIGHT(elm, field); \
274  else if (RB_RIGHT(elm, field) == NULL) \
275  child = RB_LEFT(elm, field); \
276  else { \
277  struct type *left; \
278  elm = RB_RIGHT(elm, field); \
279  while ((left = RB_LEFT(elm, field)) != NULL) \
280  elm = left; \
281  child = RB_RIGHT(elm, field); \
282  parent = RB_PARENT(elm, field); \
283  color = RB_COLOR(elm, field); \
284  if (child) \
285  RB_PARENT(child, field) = parent; \
286  if (parent) { \
287  if (RB_LEFT(parent, field) == elm) \
288  RB_LEFT(parent, field) = child; \
289  else \
290  RB_RIGHT(parent, field) = child; \
291  RB_AUGMENT(parent); \
292  } else \
293  RB_ROOT(head) = child; \
294  if (RB_PARENT(elm, field) == old) \
295  parent = elm; \
296  (elm)->field = (old)->field; \
297  if (RB_PARENT(old, field)) { \
298  if (RB_LEFT(RB_PARENT(old, field), field) == old)\
299  RB_LEFT(RB_PARENT(old, field), field) = elm;\
300  else \
301  RB_RIGHT(RB_PARENT(old, field), field) = elm;\
302  RB_AUGMENT(RB_PARENT(old, field)); \
303  } else \
304  RB_ROOT(head) = elm; \
305  RB_PARENT(RB_LEFT(old, field), field) = elm; \
306  if (RB_RIGHT(old, field)) \
307  RB_PARENT(RB_RIGHT(old, field), field) = elm; \
308  if (parent) { \
309  left = parent; \
310  do { \
311  RB_AUGMENT(left); \
312  } while ((left = RB_PARENT(left, field)) != NULL); \
313  } \
314  goto color; \
315  } \
316  parent = RB_PARENT(elm, field); \
317  color = RB_COLOR(elm, field); \
318  if (child) \
319  RB_PARENT(child, field) = parent; \
320  if (parent) { \
321  if (RB_LEFT(parent, field) == elm) \
322  RB_LEFT(parent, field) = child; \
323  else \
324  RB_RIGHT(parent, field) = child; \
325  RB_AUGMENT(parent); \
326  } else \
327  RB_ROOT(head) = child; \
328 color: \
329  if (color == RB_BLACK) \
330  name##_RB_REMOVE_COLOR(head, parent, child); \
331  return (old); \
332 } \
333  \
334 /* Inserts a node into the RB tree */ \
335 attr struct type * \
336 name##_RB_INSERT(struct name *head, struct type *elm) \
337 { \
338  struct type *tmp; \
339  struct type *parent = NULL; \
340  int comp = 0; \
341  tmp = RB_ROOT(head); \
342  while (tmp) { \
343  parent = tmp; \
344  comp = (cmp)(elm, parent); \
345  if (comp < 0) \
346  tmp = RB_LEFT(tmp, field); \
347  else if (comp > 0) \
348  tmp = RB_RIGHT(tmp, field); \
349  else \
350  return (tmp); \
351  } \
352  RB_SET(elm, parent, field); \
353  if (parent != NULL) { \
354  if (comp < 0) \
355  RB_LEFT(parent, field) = elm; \
356  else \
357  RB_RIGHT(parent, field) = elm; \
358  RB_AUGMENT(parent); \
359  } else \
360  RB_ROOT(head) = elm; \
361  name##_RB_INSERT_COLOR(head, elm); \
362  return (NULL); \
363 } \
364  \
365 /* Finds the node with the same key as elm */ \
366 attr struct type * \
367 name##_RB_FIND(struct name *head, struct type *elm) \
368 { \
369  struct type *tmp = RB_ROOT(head); \
370  int comp; \
371  while (tmp) { \
372  comp = cmp(elm, tmp); \
373  if (comp < 0) \
374  tmp = RB_LEFT(tmp, field); \
375  else if (comp > 0) \
376  tmp = RB_RIGHT(tmp, field); \
377  else \
378  return (tmp); \
379  } \
380  return (NULL); \
381 } \
382  \
383 /* Finds the first node greater than or equal to the search key */ \
384 attr struct type * \
385 name##_RB_NFIND(struct name *head, struct type *elm) \
386 { \
387  struct type *tmp = RB_ROOT(head); \
388  struct type *res = NULL; \
389  int comp; \
390  while (tmp) { \
391  comp = cmp(elm, tmp); \
392  if (comp < 0) { \
393  res = tmp; \
394  tmp = RB_LEFT(tmp, field); \
395  } \
396  else if (comp > 0) \
397  tmp = RB_RIGHT(tmp, field); \
398  else \
399  return (tmp); \
400  } \
401  return (res); \
402 } \
403  \
404 /* ARGSUSED */ \
405 attr struct type * \
406 name##_RB_NEXT(struct type *elm) \
407 { \
408  if (RB_RIGHT(elm, field)) { \
409  elm = RB_RIGHT(elm, field); \
410  while (RB_LEFT(elm, field)) \
411  elm = RB_LEFT(elm, field); \
412  } else { \
413  if (RB_PARENT(elm, field) && \
414  (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
415  elm = RB_PARENT(elm, field); \
416  else { \
417  while (RB_PARENT(elm, field) && \
418  (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
419  elm = RB_PARENT(elm, field); \
420  elm = RB_PARENT(elm, field); \
421  } \
422  } \
423  return (elm); \
424 } \
425  \
426 /* ARGSUSED */ \
427 attr struct type * \
428 name##_RB_PREV(struct type *elm) \
429 { \
430  if (RB_LEFT(elm, field)) { \
431  elm = RB_LEFT(elm, field); \
432  while (RB_RIGHT(elm, field)) \
433  elm = RB_RIGHT(elm, field); \
434  } else { \
435  if (RB_PARENT(elm, field) && \
436  (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
437  elm = RB_PARENT(elm, field); \
438  else { \
439  while (RB_PARENT(elm, field) && \
440  (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
441  elm = RB_PARENT(elm, field); \
442  elm = RB_PARENT(elm, field); \
443  } \
444  } \
445  return (elm); \
446 } \
447  \
448 attr struct type * \
449 name##_RB_MINMAX(struct name *head, int val) \
450 { \
451  struct type *tmp = RB_ROOT(head); \
452  struct type *parent = NULL; \
453  while (tmp) { \
454  parent = tmp; \
455  if (val < 0) \
456  tmp = RB_LEFT(tmp, field); \
457  else \
458  tmp = RB_RIGHT(tmp, field); \
459  } \
460  return (parent); \
461 }
462 
463 #define RB_NEGINF -1
464 #define RB_INF 1
465 
466 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
467 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
468 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
469 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
470 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
471 #define RB_PREV(name, x, y) name##_RB_PREV(y)
472 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
473 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
474 
475 #define RB_FOREACH(x, name, head) \
476  for ((x) = RB_MIN(name, head); \
477  (x) != NULL; \
478  (x) = name##_RB_NEXT(x))
479 
480 #define RB_FOREACH_FROM(x, name, y) \
481  for ((x) = (y); \
482  ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
483  (x) = (y))
484 
485 #define RB_FOREACH_SAFE(x, name, head, y) \
486  for ((x) = RB_MIN(name, head); \
487  ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \
488  (x) = (y))
489 
490 #define RB_FOREACH_REVERSE(x, name, head) \
491  for ((x) = RB_MAX(name, head); \
492  (x) != NULL; \
493  (x) = name##_RB_PREV(x))
494 
495 #define RB_FOREACH_REVERSE_FROM(x, name, y) \
496  for ((x) = (y); \
497  ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
498  (x) = (y))
499 
500 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
501  for ((x) = RB_MAX(name, head); \
502  ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
503  (x) = (y))
504 
505 #endif /* _RB_TREE_H_ */