1: /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art 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-back 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)
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: void name##_RB_INSERT_COLOR(struct name *, struct type *); \
378: void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
379: struct type *name##_RB_REMOVE(struct name *, struct type *); \
380: struct type *name##_RB_INSERT(struct name *, struct type *); \
381: struct type *name##_RB_FIND(struct name *, struct type *); \
382: struct type *name##_RB_NEXT(struct type *); \
383: struct type *name##_RB_MINMAX(struct name *, int); \
384: \
385:
386: /* Main rb operation.
387: * Moves node close to the key of elm to top
388: */
389: #define RB_GENERATE(name, type, field, cmp) \
390: void \
391: name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
392: { \
393: struct type *parent, *gparent, *tmp; \
394: while ((parent = RB_PARENT(elm, field)) && \
395: RB_COLOR(parent, field) == RB_RED) { \
396: gparent = RB_PARENT(parent, field); \
397: if (parent == RB_LEFT(gparent, field)) { \
398: tmp = RB_RIGHT(gparent, field); \
399: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
400: RB_COLOR(tmp, field) = RB_BLACK; \
401: RB_SET_BLACKRED(parent, gparent, field);\
402: elm = gparent; \
403: continue; \
404: } \
405: if (RB_RIGHT(parent, field) == elm) { \
406: RB_ROTATE_LEFT(head, parent, tmp, field);\
407: tmp = parent; \
408: parent = elm; \
409: elm = tmp; \
410: } \
411: RB_SET_BLACKRED(parent, gparent, field); \
412: RB_ROTATE_RIGHT(head, gparent, tmp, field); \
413: } else { \
414: tmp = RB_LEFT(gparent, field); \
415: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
416: RB_COLOR(tmp, field) = RB_BLACK; \
417: RB_SET_BLACKRED(parent, gparent, field);\
418: elm = gparent; \
419: continue; \
420: } \
421: if (RB_LEFT(parent, field) == elm) { \
422: RB_ROTATE_RIGHT(head, parent, tmp, field);\
423: tmp = parent; \
424: parent = elm; \
425: elm = tmp; \
426: } \
427: RB_SET_BLACKRED(parent, gparent, field); \
428: RB_ROTATE_LEFT(head, gparent, tmp, field); \
429: } \
430: } \
431: RB_COLOR(head->rbh_root, field) = RB_BLACK; \
432: } \
433: \
434: void \
435: name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
436: { \
437: struct type *tmp; \
438: while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
439: elm != RB_ROOT(head)) { \
440: if (RB_LEFT(parent, field) == elm) { \
441: tmp = RB_RIGHT(parent, field); \
442: if (RB_COLOR(tmp, field) == RB_RED) { \
443: RB_SET_BLACKRED(tmp, parent, field); \
444: RB_ROTATE_LEFT(head, parent, tmp, field);\
445: tmp = RB_RIGHT(parent, field); \
446: } \
447: if ((RB_LEFT(tmp, field) == NULL || \
448: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
449: (RB_RIGHT(tmp, field) == NULL || \
450: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
451: RB_COLOR(tmp, field) = RB_RED; \
452: elm = parent; \
453: parent = RB_PARENT(elm, field); \
454: } else { \
455: if (RB_RIGHT(tmp, field) == NULL || \
456: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
457: struct type *oleft; \
458: if ((oleft = RB_LEFT(tmp, field)))\
459: RB_COLOR(oleft, field) = RB_BLACK;\
460: RB_COLOR(tmp, field) = RB_RED; \
461: RB_ROTATE_RIGHT(head, tmp, oleft, field);\
462: tmp = RB_RIGHT(parent, field); \
463: } \
464: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
465: RB_COLOR(parent, field) = RB_BLACK; \
466: if (RB_RIGHT(tmp, field)) \
467: RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
468: RB_ROTATE_LEFT(head, parent, tmp, field);\
469: elm = RB_ROOT(head); \
470: break; \
471: } \
472: } else { \
473: tmp = RB_LEFT(parent, field); \
474: if (RB_COLOR(tmp, field) == RB_RED) { \
475: RB_SET_BLACKRED(tmp, parent, field); \
476: RB_ROTATE_RIGHT(head, parent, tmp, field);\
477: tmp = RB_LEFT(parent, field); \
478: } \
479: if ((RB_LEFT(tmp, field) == NULL || \
480: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
481: (RB_RIGHT(tmp, field) == NULL || \
482: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
483: RB_COLOR(tmp, field) = RB_RED; \
484: elm = parent; \
485: parent = RB_PARENT(elm, field); \
486: } else { \
487: if (RB_LEFT(tmp, field) == NULL || \
488: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
489: struct type *oright; \
490: if ((oright = RB_RIGHT(tmp, field)))\
491: RB_COLOR(oright, field) = RB_BLACK;\
492: RB_COLOR(tmp, field) = RB_RED; \
493: RB_ROTATE_LEFT(head, tmp, oright, field);\
494: tmp = RB_LEFT(parent, field); \
495: } \
496: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
497: RB_COLOR(parent, field) = RB_BLACK; \
498: if (RB_LEFT(tmp, field)) \
499: RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
500: RB_ROTATE_RIGHT(head, parent, tmp, field);\
501: elm = RB_ROOT(head); \
502: break; \
503: } \
504: } \
505: } \
506: if (elm) \
507: RB_COLOR(elm, field) = RB_BLACK; \
508: } \
509: \
510: struct type * \
511: name##_RB_REMOVE(struct name *head, struct type *elm) \
512: { \
513: struct type *child, *parent, *old = elm; \
514: int color; \
515: if (RB_LEFT(elm, field) == NULL) \
516: child = RB_RIGHT(elm, field); \
517: else if (RB_RIGHT(elm, field) == NULL) \
518: child = RB_LEFT(elm, field); \
519: else { \
520: struct type *left; \
521: elm = RB_RIGHT(elm, field); \
522: while ((left = RB_LEFT(elm, field))) \
523: elm = left; \
524: child = RB_RIGHT(elm, field); \
525: parent = RB_PARENT(elm, field); \
526: color = RB_COLOR(elm, field); \
527: if (child) \
528: RB_PARENT(child, field) = parent; \
529: if (parent) { \
530: if (RB_LEFT(parent, field) == elm) \
531: RB_LEFT(parent, field) = child; \
532: else \
533: RB_RIGHT(parent, field) = child; \
534: RB_AUGMENT(parent); \
535: } else \
536: RB_ROOT(head) = child; \
537: if (RB_PARENT(elm, field) == old) \
538: parent = elm; \
539: (elm)->field = (old)->field; \
540: if (RB_PARENT(old, field)) { \
541: if (RB_LEFT(RB_PARENT(old, field), field) == old)\
542: RB_LEFT(RB_PARENT(old, field), field) = elm;\
543: else \
544: RB_RIGHT(RB_PARENT(old, field), field) = elm;\
545: RB_AUGMENT(RB_PARENT(old, field)); \
546: } else \
547: RB_ROOT(head) = elm; \
548: RB_PARENT(RB_LEFT(old, field), field) = elm; \
549: if (RB_RIGHT(old, field)) \
550: RB_PARENT(RB_RIGHT(old, field), field) = elm; \
551: if (parent) { \
552: left = parent; \
553: do { \
554: RB_AUGMENT(left); \
555: } while ((left = RB_PARENT(left, field))); \
556: } \
557: goto color; \
558: } \
559: parent = RB_PARENT(elm, field); \
560: color = RB_COLOR(elm, field); \
561: if (child) \
562: RB_PARENT(child, field) = parent; \
563: if (parent) { \
564: if (RB_LEFT(parent, field) == elm) \
565: RB_LEFT(parent, field) = child; \
566: else \
567: RB_RIGHT(parent, field) = child; \
568: RB_AUGMENT(parent); \
569: } else \
570: RB_ROOT(head) = child; \
571: color: \
572: if (color == RB_BLACK) \
573: name##_RB_REMOVE_COLOR(head, parent, child); \
574: return (old); \
575: } \
576: \
577: /* Inserts a node into the RB tree */ \
578: struct type * \
579: name##_RB_INSERT(struct name *head, struct type *elm) \
580: { \
581: struct type *tmp; \
582: struct type *parent = NULL; \
583: int comp = 0; \
584: tmp = RB_ROOT(head); \
585: while (tmp) { \
586: parent = tmp; \
587: comp = (cmp)(elm, parent); \
588: if (comp < 0) \
589: tmp = RB_LEFT(tmp, field); \
590: else if (comp > 0) \
591: tmp = RB_RIGHT(tmp, field); \
592: else \
593: return (tmp); \
594: } \
595: RB_SET(elm, parent, field); \
596: if (parent != NULL) { \
597: if (comp < 0) \
598: RB_LEFT(parent, field) = elm; \
599: else \
600: RB_RIGHT(parent, field) = elm; \
601: RB_AUGMENT(parent); \
602: } else \
603: RB_ROOT(head) = elm; \
604: name##_RB_INSERT_COLOR(head, elm); \
605: return (NULL); \
606: } \
607: \
608: /* Finds the node with the same key as elm */ \
609: struct type * \
610: name##_RB_FIND(struct name *head, struct type *elm) \
611: { \
612: struct type *tmp = RB_ROOT(head); \
613: int comp; \
614: while (tmp) { \
615: comp = cmp(elm, tmp); \
616: if (comp < 0) \
617: tmp = RB_LEFT(tmp, field); \
618: else if (comp > 0) \
619: tmp = RB_RIGHT(tmp, field); \
620: else \
621: return (tmp); \
622: } \
623: return (NULL); \
624: } \
625: \
626: struct type * \
627: name##_RB_NEXT(struct type *elm) \
628: { \
629: if (RB_RIGHT(elm, field)) { \
630: elm = RB_RIGHT(elm, field); \
631: while (RB_LEFT(elm, field)) \
632: elm = RB_LEFT(elm, field); \
633: } else { \
634: if (RB_PARENT(elm, field) && \
635: (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
636: elm = RB_PARENT(elm, field); \
637: else { \
638: while (RB_PARENT(elm, field) && \
639: (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
640: elm = RB_PARENT(elm, field); \
641: elm = RB_PARENT(elm, field); \
642: } \
643: } \
644: return (elm); \
645: } \
646: \
647: struct type * \
648: name##_RB_MINMAX(struct name *head, int val) \
649: { \
650: struct type *tmp = RB_ROOT(head); \
651: struct type *parent = NULL; \
652: while (tmp) { \
653: parent = tmp; \
654: if (val < 0) \
655: tmp = RB_LEFT(tmp, field); \
656: else \
657: tmp = RB_RIGHT(tmp, field); \
658: } \
659: return (parent); \
660: }
661:
662: #define RB_NEGINF -1
663: #define RB_INF 1
664:
665: #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
666: #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
667: #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
668: #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
669: #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
670: #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
671:
672: #define RB_FOREACH(x, name, head) \
673: for ((x) = RB_MIN(name, head); \
674: (x) != NULL; \
675: (x) = name##_RB_NEXT(x))
676:
677: #endif /* _SYS_TREE_H_ */
678: /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */
679: /*
680: * Copyright 2002 Niels Provos <provos@citi.umich.edu>
681: * All rights reserved.
682: *
683: * Redistribution and use in source and binary forms, with or without
684: * modification, are permitted provided that the following conditions
685: * are met:
686: * 1. Redistributions of source code must retain the above copyright
687: * notice, this list of conditions and the following disclaimer.
688: * 2. Redistributions in binary form must reproduce the above copyright
689: * notice, this list of conditions and the following disclaimer in the
690: * documentation and/or other materials provided with the distribution.
691: *
692: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
693: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
694: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
695: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
696: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
697: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
698: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
699: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
700: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
701: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
702: */
703:
704: #ifndef _SYS_TREE_H_
705: #define _SYS_TREE_H_
706:
707: /*
708: * This file defines data structures for different types of trees:
709: * splay trees and red-black trees.
710: *
711: * A splay tree is a self-organizing data structure. Every operation
712: * on the tree causes a splay to happen. The splay moves the requested
713: * node to the root of the tree and partly rebalances it.
714: *
715: * This has the benefit that request locality causes faster lookups as
716: * the requested nodes move to the top of the tree. On the other hand,
717: * every lookup causes memory writes.
718: *
719: * The Balance Theorem bounds the total access time for m operations
720: * and n inserts on an initially empty tree as O((m + n)lg n). The
721: * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
722: *
723: * A red-black tree is a binary search tree with the node color as an
724: * extra attribute. It fulfills a set of conditions:
725: * - every search path from the root to a leaf consists of the
726: * same number of black nodes,
727: * - each red node (except for the root) has a black parent,
728: * - each leaf node is black.
729: *
730: * Every operation on a red-black tree is bounded as O(lg n).
731: * The maximum height of a red-black tree is 2lg (n+1).
732: */
733:
734: #define SPLAY_HEAD(name, type) \
735: struct name { \
736: struct type *sph_root; /* root of the tree */ \
737: }
738:
739: #define SPLAY_INITIALIZER(root) \
740: { NULL }
741:
742: #define SPLAY_INIT(root) do { \
743: (root)->sph_root = NULL; \
744: } while (0)
745:
746: #define SPLAY_ENTRY(type) \
747: struct { \
748: struct type *spe_left; /* left element */ \
749: struct type *spe_right; /* right element */ \
750: }
751:
752: #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
753: #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
754: #define SPLAY_ROOT(head) (head)->sph_root
755: #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
756:
757: /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
758: #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
759: SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
760: SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
761: (head)->sph_root = tmp; \
762: } while (0)
763:
764: #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
765: SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
766: SPLAY_LEFT(tmp, field) = (head)->sph_root; \
767: (head)->sph_root = tmp; \
768: } while (0)
769:
770: #define SPLAY_LINKLEFT(head, tmp, field) do { \
771: SPLAY_LEFT(tmp, field) = (head)->sph_root; \
772: tmp = (head)->sph_root; \
773: (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
774: } while (0)
775:
776: #define SPLAY_LINKRIGHT(head, tmp, field) do { \
777: SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
778: tmp = (head)->sph_root; \
779: (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
780: } while (0)
781:
782: #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
783: SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
784: SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
785: SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
786: SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
787: } while (0)
788:
789: /* Generates prototypes and inline functions */
790:
791: #define SPLAY_PROTOTYPE(name, type, field, cmp) \
792: void name##_SPLAY(struct name *, struct type *); \
793: void name##_SPLAY_MINMAX(struct name *, int); \
794: struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
795: struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
796: \
797: /* Finds the node with the same key as elm */ \
798: static __inline struct type * \
799: name##_SPLAY_FIND(struct name *head, struct type *elm) \
800: { \
801: if (SPLAY_EMPTY(head)) \
802: return(NULL); \
803: name##_SPLAY(head, elm); \
804: if ((cmp)(elm, (head)->sph_root) == 0) \
805: return (head->sph_root); \
806: return (NULL); \
807: } \
808: \
809: static __inline struct type * \
810: name##_SPLAY_NEXT(struct name *head, struct type *elm) \
811: { \
812: name##_SPLAY(head, elm); \
813: if (SPLAY_RIGHT(elm, field) != NULL) { \
814: elm = SPLAY_RIGHT(elm, field); \
815: while (SPLAY_LEFT(elm, field) != NULL) { \
816: elm = SPLAY_LEFT(elm, field); \
817: } \
818: } else \
819: elm = NULL; \
820: return (elm); \
821: } \
822: \
823: static __inline struct type * \
824: name##_SPLAY_MIN_MAX(struct name *head, int val) \
825: { \
826: name##_SPLAY_MINMAX(head, val); \
827: return (SPLAY_ROOT(head)); \
828: }
829:
830: /* Main splay operation.
831: * Moves node close to the key of elm to top
832: */
833: #define SPLAY_GENERATE(name, type, field, cmp) \
834: struct type * \
835: name##_SPLAY_INSERT(struct name *head, struct type *elm) \
836: { \
837: if (SPLAY_EMPTY(head)) { \
838: SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
839: } else { \
840: int __comp; \
841: name##_SPLAY(head, elm); \
842: __comp = (cmp)(elm, (head)->sph_root); \
843: if(__comp < 0) { \
844: SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
845: SPLAY_RIGHT(elm, field) = (head)->sph_root; \
846: SPLAY_LEFT((head)->sph_root, field) = NULL; \
847: } else if (__comp > 0) { \
848: SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
849: SPLAY_LEFT(elm, field) = (head)->sph_root; \
850: SPLAY_RIGHT((head)->sph_root, field) = NULL; \
851: } else \
852: return ((head)->sph_root); \
853: } \
854: (head)->sph_root = (elm); \
855: return (NULL); \
856: } \
857: \
858: struct type * \
859: name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
860: { \
861: struct type *__tmp; \
862: if (SPLAY_EMPTY(head)) \
863: return (NULL); \
864: name##_SPLAY(head, elm); \
865: if ((cmp)(elm, (head)->sph_root) == 0) { \
866: if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
867: (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
868: } else { \
869: __tmp = SPLAY_RIGHT((head)->sph_root, field); \
870: (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
871: name##_SPLAY(head, elm); \
872: SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
873: } \
874: return (elm); \
875: } \
876: return (NULL); \
877: } \
878: \
879: void \
880: name##_SPLAY(struct name *head, struct type *elm) \
881: { \
882: struct type __node, *__left, *__right, *__tmp; \
883: int __comp; \
884: \
885: SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
886: __left = __right = &__node; \
887: \
888: while ((__comp = (cmp)(elm, (head)->sph_root))) { \
889: if (__comp < 0) { \
890: __tmp = SPLAY_LEFT((head)->sph_root, field); \
891: if (__tmp == NULL) \
892: break; \
893: if ((cmp)(elm, __tmp) < 0){ \
894: SPLAY_ROTATE_RIGHT(head, __tmp, field); \
895: if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
896: break; \
897: } \
898: SPLAY_LINKLEFT(head, __right, field); \
899: } else if (__comp > 0) { \
900: __tmp = SPLAY_RIGHT((head)->sph_root, field); \
901: if (__tmp == NULL) \
902: break; \
903: if ((cmp)(elm, __tmp) > 0){ \
904: SPLAY_ROTATE_LEFT(head, __tmp, field); \
905: if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
906: break; \
907: } \
908: SPLAY_LINKRIGHT(head, __left, field); \
909: } \
910: } \
911: SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
912: } \
913: \
914: /* Splay with either the minimum or the maximum element \
915: * Used to find minimum or maximum element in tree. \
916: */ \
917: void name##_SPLAY_MINMAX(struct name *head, int __comp) \
918: { \
919: struct type __node, *__left, *__right, *__tmp; \
920: \
921: SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
922: __left = __right = &__node; \
923: \
924: while (1) { \
925: if (__comp < 0) { \
926: __tmp = SPLAY_LEFT((head)->sph_root, field); \
927: if (__tmp == NULL) \
928: break; \
929: if (__comp < 0){ \
930: SPLAY_ROTATE_RIGHT(head, __tmp, field); \
931: if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
932: break; \
933: } \
934: SPLAY_LINKLEFT(head, __right, field); \
935: } else if (__comp > 0) { \
936: __tmp = SPLAY_RIGHT((head)->sph_root, field); \
937: if (__tmp == NULL) \
938: break; \
939: if (__comp > 0) { \
940: SPLAY_ROTATE_LEFT(head, __tmp, field); \
941: if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
942: break; \
943: } \
944: SPLAY_LINKRIGHT(head, __left, field); \
945: } \
946: } \
947: SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
948: }
949:
950: #define SPLAY_NEGINF -1
951: #define SPLAY_INF 1
952:
953: #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
954: #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
955: #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
956: #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
957: #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
958: : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
959: #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
960: : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
961:
962: #define SPLAY_FOREACH(x, name, head) \
963: for ((x) = SPLAY_MIN(name, head); \
964: (x) != NULL; \
965: (x) = SPLAY_NEXT(name, head, x))
966:
967: /* Macros that define a red-back tree */
968: #define RB_HEAD(name, type) \
969: struct name { \
970: struct type *rbh_root; /* root of the tree */ \
971: }
972:
973: #define RB_INITIALIZER(root) \
974: { NULL }
975:
976: #define RB_INIT(root) do { \
977: (root)->rbh_root = NULL; \
978: } while (0)
979:
980: #define RB_BLACK 0
981: #define RB_RED 1
982: #define RB_ENTRY(type) \
983: struct { \
984: struct type *rbe_left; /* left element */ \
985: struct type *rbe_right; /* right element */ \
986: struct type *rbe_parent; /* parent element */ \
987: int rbe_color; /* node color */ \
988: }
989:
990: #define RB_LEFT(elm, field) (elm)->field.rbe_left
991: #define RB_RIGHT(elm, field) (elm)->field.rbe_right
992: #define RB_PARENT(elm, field) (elm)->field.rbe_parent
993: #define RB_COLOR(elm, field) (elm)->field.rbe_color
994: #define RB_ROOT(head) (head)->rbh_root
995: #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
996:
997: #define RB_SET(elm, parent, field) do { \
998: RB_PARENT(elm, field) = parent; \
999: RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
1000: RB_COLOR(elm, field) = RB_RED; \
1001: } while (0)
1002:
1003: #define RB_SET_BLACKRED(black, red, field) do { \
1004: RB_COLOR(black, field) = RB_BLACK; \
1005: RB_COLOR(red, field) = RB_RED; \
1006: } while (0)
1007:
1008: #ifndef RB_AUGMENT
1009: #define RB_AUGMENT(x)
1010: #endif
1011:
1012: #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
1013: (tmp) = RB_RIGHT(elm, field); \
1014: if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
1015: RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
1016: } \
1017: RB_AUGMENT(elm); \
1018: if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
1019: if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
1020: RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
1021: else \
1022: RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1023: } else \
1024: (head)->rbh_root = (tmp); \
1025: RB_LEFT(tmp, field) = (elm); \
1026: RB_PARENT(elm, field) = (tmp); \
1027: RB_AUGMENT(tmp); \
1028: if ((RB_PARENT(tmp, field))) \
1029: RB_AUGMENT(RB_PARENT(tmp, field)); \
1030: } while (0)
1031:
1032: #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
1033: (tmp) = RB_LEFT(elm, field); \
1034: if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
1035: RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
1036: } \
1037: RB_AUGMENT(elm); \
1038: if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
1039: if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
1040: RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
1041: else \
1042: RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1043: } else \
1044: (head)->rbh_root = (tmp); \
1045: RB_RIGHT(tmp, field) = (elm); \
1046: RB_PARENT(elm, field) = (tmp); \
1047: RB_AUGMENT(tmp); \
1048: if ((RB_PARENT(tmp, field))) \
1049: RB_AUGMENT(RB_PARENT(tmp, field)); \
1050: } while (0)
1051:
1052: /* Generates prototypes and inline functions */
1053: #define RB_PROTOTYPE(name, type, field, cmp) \
1054: void name##_RB_INSERT_COLOR(struct name *, struct type *); \
1055: void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
1056: struct type *name##_RB_REMOVE(struct name *, struct type *); \
1057: struct type *name##_RB_INSERT(struct name *, struct type *); \
1058: struct type *name##_RB_FIND(struct name *, struct type *); \
1059: struct type *name##_RB_NEXT(struct type *); \
1060: struct type *name##_RB_MINMAX(struct name *, int); \
1061: \
1062:
1063: /* Main rb operation.
1064: * Moves node close to the key of elm to top
1065: */
1066: #define RB_GENERATE(name, type, field, cmp) \
1067: void \
1068: name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
1069: { \
1070: struct type *parent, *gparent, *tmp; \
1071: while ((parent = RB_PARENT(elm, field)) && \
1072: RB_COLOR(parent, field) == RB_RED) { \
1073: gparent = RB_PARENT(parent, field); \
1074: if (parent == RB_LEFT(gparent, field)) { \
1075: tmp = RB_RIGHT(gparent, field); \
1076: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
1077: RB_COLOR(tmp, field) = RB_BLACK; \
1078: RB_SET_BLACKRED(parent, gparent, field);\
1079: elm = gparent; \
1080: continue; \
1081: } \
1082: if (RB_RIGHT(parent, field) == elm) { \
1083: RB_ROTATE_LEFT(head, parent, tmp, field);\
1084: tmp = parent; \
1085: parent = elm; \
1086: elm = tmp; \
1087: } \
1088: RB_SET_BLACKRED(parent, gparent, field); \
1089: RB_ROTATE_RIGHT(head, gparent, tmp, field); \
1090: } else { \
1091: tmp = RB_LEFT(gparent, field); \
1092: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
1093: RB_COLOR(tmp, field) = RB_BLACK; \
1094: RB_SET_BLACKRED(parent, gparent, field);\
1095: elm = gparent; \
1096: continue; \
1097: } \
1098: if (RB_LEFT(parent, field) == elm) { \
1099: RB_ROTATE_RIGHT(head, parent, tmp, field);\
1100: tmp = parent; \
1101: parent = elm; \
1102: elm = tmp; \
1103: } \
1104: RB_SET_BLACKRED(parent, gparent, field); \
1105: RB_ROTATE_LEFT(head, gparent, tmp, field); \
1106: } \
1107: } \
1108: RB_COLOR(head->rbh_root, field) = RB_BLACK; \
1109: } \
1110: \
1111: void \
1112: name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
1113: { \
1114: struct type *tmp; \
1115: while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
1116: elm != RB_ROOT(head)) { \
1117: if (RB_LEFT(parent, field) == elm) { \
1118: tmp = RB_RIGHT(parent, field); \
1119: if (RB_COLOR(tmp, field) == RB_RED) { \
1120: RB_SET_BLACKRED(tmp, parent, field); \
1121: RB_ROTATE_LEFT(head, parent, tmp, field);\
1122: tmp = RB_RIGHT(parent, field); \
1123: } \
1124: if ((RB_LEFT(tmp, field) == NULL || \
1125: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1126: (RB_RIGHT(tmp, field) == NULL || \
1127: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1128: RB_COLOR(tmp, field) = RB_RED; \
1129: elm = parent; \
1130: parent = RB_PARENT(elm, field); \
1131: } else { \
1132: if (RB_RIGHT(tmp, field) == NULL || \
1133: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
1134: struct type *oleft; \
1135: if ((oleft = RB_LEFT(tmp, field)))\
1136: RB_COLOR(oleft, field) = RB_BLACK;\
1137: RB_COLOR(tmp, field) = RB_RED; \
1138: RB_ROTATE_RIGHT(head, tmp, oleft, field);\
1139: tmp = RB_RIGHT(parent, field); \
1140: } \
1141: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1142: RB_COLOR(parent, field) = RB_BLACK; \
1143: if (RB_RIGHT(tmp, field)) \
1144: RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
1145: RB_ROTATE_LEFT(head, parent, tmp, field);\
1146: elm = RB_ROOT(head); \
1147: break; \
1148: } \
1149: } else { \
1150: tmp = RB_LEFT(parent, field); \
1151: if (RB_COLOR(tmp, field) == RB_RED) { \
1152: RB_SET_BLACKRED(tmp, parent, field); \
1153: RB_ROTATE_RIGHT(head, parent, tmp, field);\
1154: tmp = RB_LEFT(parent, field); \
1155: } \
1156: if ((RB_LEFT(tmp, field) == NULL || \
1157: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1158: (RB_RIGHT(tmp, field) == NULL || \
1159: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1160: RB_COLOR(tmp, field) = RB_RED; \
1161: elm = parent; \
1162: parent = RB_PARENT(elm, field); \
1163: } else { \
1164: if (RB_LEFT(tmp, field) == NULL || \
1165: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
1166: struct type *oright; \
1167: if ((oright = RB_RIGHT(tmp, field)))\
1168: RB_COLOR(oright, field) = RB_BLACK;\
1169: RB_COLOR(tmp, field) = RB_RED; \
1170: RB_ROTATE_LEFT(head, tmp, oright, field);\
1171: tmp = RB_LEFT(parent, field); \
1172: } \
1173: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1174: RB_COLOR(parent, field) = RB_BLACK; \
1175: if (RB_LEFT(tmp, field)) \
1176: RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
1177: RB_ROTATE_RIGHT(head, parent, tmp, field);\
1178: elm = RB_ROOT(head); \
1179: break; \
1180: } \
1181: } \
1182: } \
1183: if (elm) \
1184: RB_COLOR(elm, field) = RB_BLACK; \
1185: } \
1186: \
1187: struct type * \
1188: name##_RB_REMOVE(struct name *head, struct type *elm) \
1189: { \
1190: struct type *child, *parent, *old = elm; \
1191: int color; \
1192: if (RB_LEFT(elm, field) == NULL) \
1193: child = RB_RIGHT(elm, field); \
1194: else if (RB_RIGHT(elm, field) == NULL) \
1195: child = RB_LEFT(elm, field); \
1196: else { \
1197: struct type *left; \
1198: elm = RB_RIGHT(elm, field); \
1199: while ((left = RB_LEFT(elm, field))) \
1200: elm = left; \
1201: child = RB_RIGHT(elm, field); \
1202: parent = RB_PARENT(elm, field); \
1203: color = RB_COLOR(elm, field); \
1204: if (child) \
1205: RB_PARENT(child, field) = parent; \
1206: if (parent) { \
1207: if (RB_LEFT(parent, field) == elm) \
1208: RB_LEFT(parent, field) = child; \
1209: else \
1210: RB_RIGHT(parent, field) = child; \
1211: RB_AUGMENT(parent); \
1212: } else \
1213: RB_ROOT(head) = child; \
1214: if (RB_PARENT(elm, field) == old) \
1215: parent = elm; \
1216: (elm)->field = (old)->field; \
1217: if (RB_PARENT(old, field)) { \
1218: if (RB_LEFT(RB_PARENT(old, field), field) == old)\
1219: RB_LEFT(RB_PARENT(old, field), field) = elm;\
1220: else \
1221: RB_RIGHT(RB_PARENT(old, field), field) = elm;\
1222: RB_AUGMENT(RB_PARENT(old, field)); \
1223: } else \
1224: RB_ROOT(head) = elm; \
1225: RB_PARENT(RB_LEFT(old, field), field) = elm; \
1226: if (RB_RIGHT(old, field)) \
1227: RB_PARENT(RB_RIGHT(old, field), field) = elm; \
1228: if (parent) { \
1229: left = parent; \
1230: do { \
1231: RB_AUGMENT(left); \
1232: } while ((left = RB_PARENT(left, field))); \
1233: } \
1234: goto color; \
1235: } \
1236: parent = RB_PARENT(elm, field); \
1237: color = RB_COLOR(elm, field); \
1238: if (child) \
1239: RB_PARENT(child, field) = parent; \
1240: if (parent) { \
1241: if (RB_LEFT(parent, field) == elm) \
1242: RB_LEFT(parent, field) = child; \
1243: else \
1244: RB_RIGHT(parent, field) = child; \
1245: RB_AUGMENT(parent); \
1246: } else \
1247: RB_ROOT(head) = child; \
1248: color: \
1249: if (color == RB_BLACK) \
1250: name##_RB_REMOVE_COLOR(head, parent, child); \
1251: return (old); \
1252: } \
1253: \
1254: /* Inserts a node into the RB tree */ \
1255: struct type * \
1256: name##_RB_INSERT(struct name *head, struct type *elm) \
1257: { \
1258: struct type *tmp; \
1259: struct type *parent = NULL; \
1260: int comp = 0; \
1261: tmp = RB_ROOT(head); \
1262: while (tmp) { \
1263: parent = tmp; \
1264: comp = (cmp)(elm, parent); \
1265: if (comp < 0) \
1266: tmp = RB_LEFT(tmp, field); \
1267: else if (comp > 0) \
1268: tmp = RB_RIGHT(tmp, field); \
1269: else \
1270: return (tmp); \
1271: } \
1272: RB_SET(elm, parent, field); \
1273: if (parent != NULL) { \
1274: if (comp < 0) \
1275: RB_LEFT(parent, field) = elm; \
1276: else \
1277: RB_RIGHT(parent, field) = elm; \
1278: RB_AUGMENT(parent); \
1279: } else \
1280: RB_ROOT(head) = elm; \
1281: name##_RB_INSERT_COLOR(head, elm); \
1282: return (NULL); \
1283: } \
1284: \
1285: /* Finds the node with the same key as elm */ \
1286: struct type * \
1287: name##_RB_FIND(struct name *head, struct type *elm) \
1288: { \
1289: struct type *tmp = RB_ROOT(head); \
1290: int comp; \
1291: while (tmp) { \
1292: comp = cmp(elm, tmp); \
1293: if (comp < 0) \
1294: tmp = RB_LEFT(tmp, field); \
1295: else if (comp > 0) \
1296: tmp = RB_RIGHT(tmp, field); \
1297: else \
1298: return (tmp); \
1299: } \
1300: return (NULL); \
1301: } \
1302: \
1303: struct type * \
1304: name##_RB_NEXT(struct type *elm) \
1305: { \
1306: if (RB_RIGHT(elm, field)) { \
1307: elm = RB_RIGHT(elm, field); \
1308: while (RB_LEFT(elm, field)) \
1309: elm = RB_LEFT(elm, field); \
1310: } else { \
1311: if (RB_PARENT(elm, field) && \
1312: (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
1313: elm = RB_PARENT(elm, field); \
1314: else { \
1315: while (RB_PARENT(elm, field) && \
1316: (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
1317: elm = RB_PARENT(elm, field); \
1318: elm = RB_PARENT(elm, field); \
1319: } \
1320: } \
1321: return (elm); \
1322: } \
1323: \
1324: struct type * \
1325: name##_RB_MINMAX(struct name *head, int val) \
1326: { \
1327: struct type *tmp = RB_ROOT(head); \
1328: struct type *parent = NULL; \
1329: while (tmp) { \
1330: parent = tmp; \
1331: if (val < 0) \
1332: tmp = RB_LEFT(tmp, field); \
1333: else \
1334: tmp = RB_RIGHT(tmp, field); \
1335: } \
1336: return (parent); \
1337: }
1338:
1339: #define RB_NEGINF -1
1340: #define RB_INF 1
1341:
1342: #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
1343: #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
1344: #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
1345: #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
1346: #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
1347: #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
1348:
1349: #define RB_FOREACH(x, name, head) \
1350: for ((x) = RB_MIN(name, head); \
1351: (x) != NULL; \
1352: (x) = name##_RB_NEXT(x))
1353:
1354: #endif /* _SYS_TREE_H_ */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to tree.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libevent / WIN32-Code