![[BACK]](/icons/back.gif){kind=icon}
Return to tree.h CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / sys|
Return to tree.h CVS log | Up to [local] / sys / sys |
1.1 nbrk 1: /* $OpenBSD: tree.h,v 1.9 2004/11/24 18:10:42 tdeval Exp $ */
2: /*
3: * Copyright 2002 Niels Provos <provos@citi.umich.edu>
4: * All rights reserved.
5: *
6: * Redistribution and use in source and binary forms, with or without
7: * modification, are permitted provided that the following conditions
8: * are met:
9: * 1. Redistributions of source code must retain the above copyright
10: * notice, this list of conditions and the following disclaimer.
11: * 2. Redistributions in binary form must reproduce the above copyright
12: * notice, this list of conditions and the following disclaimer in the
13: * documentation and/or other materials provided with the distribution.
14: *
15: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25: */
26:
27: #ifndef _SYS_TREE_H_
28: #define _SYS_TREE_H_
29:
30: /*
31: * This file defines data structures for different types of trees:
32: * splay trees and red-black trees.
33: *
34: * A splay tree is a self-organizing data structure. Every operation
35: * on the tree causes a splay to happen. The splay moves the requested
36: * node to the root of the tree and partly rebalances it.
37: *
38: * This has the benefit that request locality causes faster lookups as
39: * the requested nodes move to the top of the tree. On the other hand,
40: * every lookup causes memory writes.
41: *
42: * The Balance Theorem bounds the total access time for m operations
43: * and n inserts on an initially empty tree as O((m + n)lg n). The
44: * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
45: *
46: * A red-black tree is a binary search tree with the node color as an
47: * extra attribute. It fulfills a set of conditions:
48: * - every search path from the root to a leaf consists of the
49: * same number of black nodes,
50: * - each red node (except for the root) has a black parent,
51: * - each leaf node is black.
52: *
53: * Every operation on a red-black tree is bounded as O(lg n).
54: * The maximum height of a red-black tree is 2lg (n+1).
55: */
56:
57: #define SPLAY_HEAD(name, type) \
58: struct name { \
59: struct type *sph_root; /* root of the tree */ \
60: }
61:
62: #define SPLAY_INITIALIZER(root) \
63: { NULL }
64:
65: #define SPLAY_INIT(root) do { \
66: (root)->sph_root = NULL; \
67: } while (0)
68:
69: #define SPLAY_ENTRY(type) \
70: struct { \
71: struct type *spe_left; /* left element */ \
72: struct type *spe_right; /* right element */ \
73: }
74:
75: #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
76: #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
77: #define SPLAY_ROOT(head) (head)->sph_root
78: #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
79:
80: /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
81: #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
82: SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
83: SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
84: (head)->sph_root = tmp; \
85: } while (0)
86:
87: #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
88: SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
89: SPLAY_LEFT(tmp, field) = (head)->sph_root; \
90: (head)->sph_root = tmp; \
91: } while (0)
92:
93: #define SPLAY_LINKLEFT(head, tmp, field) do { \
94: SPLAY_LEFT(tmp, field) = (head)->sph_root; \
95: tmp = (head)->sph_root; \
96: (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
97: } while (0)
98:
99: #define SPLAY_LINKRIGHT(head, tmp, field) do { \
100: SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
101: tmp = (head)->sph_root; \
102: (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
103: } while (0)
104:
105: #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
106: SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
107: SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
108: SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
109: SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
110: } while (0)
111:
112: /* Generates prototypes and inline functions */
113:
114: #define SPLAY_PROTOTYPE(name, type, field, cmp) \
115: void name##_SPLAY(struct name *, struct type *); \
116: void name##_SPLAY_MINMAX(struct name *, int); \
117: struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
118: struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
119: \
120: /* Finds the node with the same key as elm */ \
121: static __inline struct type * \
122: name##_SPLAY_FIND(struct name *head, struct type *elm) \
123: { \
124: if (SPLAY_EMPTY(head)) \
125: return(NULL); \
126: name##_SPLAY(head, elm); \
127: if ((cmp)(elm, (head)->sph_root) == 0) \
128: return (head->sph_root); \
129: return (NULL); \
130: } \
131: \
132: static __inline struct type * \
133: name##_SPLAY_NEXT(struct name *head, struct type *elm) \
134: { \
135: name##_SPLAY(head, elm); \
136: if (SPLAY_RIGHT(elm, field) != NULL) { \
137: elm = SPLAY_RIGHT(elm, field); \
138: while (SPLAY_LEFT(elm, field) != NULL) { \
139: elm = SPLAY_LEFT(elm, field); \
140: } \
141: } else \
142: elm = NULL; \
143: return (elm); \
144: } \
145: \
146: static __inline struct type * \
147: name##_SPLAY_MIN_MAX(struct name *head, int val) \
148: { \
149: name##_SPLAY_MINMAX(head, val); \
150: return (SPLAY_ROOT(head)); \
151: }
152:
153: /* Main splay operation.
154: * Moves node close to the key of elm to top
155: */
156: #define SPLAY_GENERATE(name, type, field, cmp) \
157: struct type * \
158: name##_SPLAY_INSERT(struct name *head, struct type *elm) \
159: { \
160: if (SPLAY_EMPTY(head)) { \
161: SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
162: } else { \
163: int __comp; \
164: name##_SPLAY(head, elm); \
165: __comp = (cmp)(elm, (head)->sph_root); \
166: if(__comp < 0) { \
167: SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
168: SPLAY_RIGHT(elm, field) = (head)->sph_root; \
169: SPLAY_LEFT((head)->sph_root, field) = NULL; \
170: } else if (__comp > 0) { \
171: SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
172: SPLAY_LEFT(elm, field) = (head)->sph_root; \
173: SPLAY_RIGHT((head)->sph_root, field) = NULL; \
174: } else \
175: return ((head)->sph_root); \
176: } \
177: (head)->sph_root = (elm); \
178: return (NULL); \
179: } \
180: \
181: struct type * \
182: name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
183: { \
184: struct type *__tmp; \
185: if (SPLAY_EMPTY(head)) \
186: return (NULL); \
187: name##_SPLAY(head, elm); \
188: if ((cmp)(elm, (head)->sph_root) == 0) { \
189: if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
190: (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
191: } else { \
192: __tmp = SPLAY_RIGHT((head)->sph_root, field); \
193: (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
194: name##_SPLAY(head, elm); \
195: SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
196: } \
197: return (elm); \
198: } \
199: return (NULL); \
200: } \
201: \
202: void \
203: name##_SPLAY(struct name *head, struct type *elm) \
204: { \
205: struct type __node, *__left, *__right, *__tmp; \
206: int __comp; \
207: \
208: SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
209: __left = __right = &__node; \
210: \
211: while ((__comp = (cmp)(elm, (head)->sph_root))) { \
212: if (__comp < 0) { \
213: __tmp = SPLAY_LEFT((head)->sph_root, field); \
214: if (__tmp == NULL) \
215: break; \
216: if ((cmp)(elm, __tmp) < 0){ \
217: SPLAY_ROTATE_RIGHT(head, __tmp, field); \
218: if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
219: break; \
220: } \
221: SPLAY_LINKLEFT(head, __right, field); \
222: } else if (__comp > 0) { \
223: __tmp = SPLAY_RIGHT((head)->sph_root, field); \
224: if (__tmp == NULL) \
225: break; \
226: if ((cmp)(elm, __tmp) > 0){ \
227: SPLAY_ROTATE_LEFT(head, __tmp, field); \
228: if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
229: break; \
230: } \
231: SPLAY_LINKRIGHT(head, __left, field); \
232: } \
233: } \
234: SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
235: } \
236: \
237: /* Splay with either the minimum or the maximum element \
238: * Used to find minimum or maximum element in tree. \
239: */ \
240: void name##_SPLAY_MINMAX(struct name *head, int __comp) \
241: { \
242: struct type __node, *__left, *__right, *__tmp; \
243: \
244: SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
245: __left = __right = &__node; \
246: \
247: while (1) { \
248: if (__comp < 0) { \
249: __tmp = SPLAY_LEFT((head)->sph_root, field); \
250: if (__tmp == NULL) \
251: break; \
252: if (__comp < 0){ \
253: SPLAY_ROTATE_RIGHT(head, __tmp, field); \
254: if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
255: break; \
256: } \
257: SPLAY_LINKLEFT(head, __right, field); \
258: } else if (__comp > 0) { \
259: __tmp = SPLAY_RIGHT((head)->sph_root, field); \
260: if (__tmp == NULL) \
261: break; \
262: if (__comp > 0) { \
263: SPLAY_ROTATE_LEFT(head, __tmp, field); \
264: if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
265: break; \
266: } \
267: SPLAY_LINKRIGHT(head, __left, field); \
268: } \
269: } \
270: SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
271: }
272:
273: #define SPLAY_NEGINF -1
274: #define SPLAY_INF 1
275:
276: #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
277: #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
278: #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
279: #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
280: #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
281: : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
282: #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
283: : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
284:
285: #define SPLAY_FOREACH(x, name, head) \
286: for ((x) = SPLAY_MIN(name, head); \
287: (x) != NULL; \
288: (x) = SPLAY_NEXT(name, head, x))
289:
290: /* Macros that define a red-black tree */
291: #define RB_HEAD(name, type) \
292: struct name { \
293: struct type *rbh_root; /* root of the tree */ \
294: }
295:
296: #define RB_INITIALIZER(root) \
297: { NULL }
298:
299: #define RB_INIT(root) do { \
300: (root)->rbh_root = NULL; \
301: } while (0)
302:
303: #define RB_BLACK 0
304: #define RB_RED 1
305: #define RB_ENTRY(type) \
306: struct { \
307: struct type *rbe_left; /* left element */ \
308: struct type *rbe_right; /* right element */ \
309: struct type *rbe_parent; /* parent element */ \
310: int rbe_color; /* node color */ \
311: }
312:
313: #define RB_LEFT(elm, field) (elm)->field.rbe_left
314: #define RB_RIGHT(elm, field) (elm)->field.rbe_right
315: #define RB_PARENT(elm, field) (elm)->field.rbe_parent
316: #define RB_COLOR(elm, field) (elm)->field.rbe_color
317: #define RB_ROOT(head) (head)->rbh_root
318: #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
319:
320: #define RB_SET(elm, parent, field) do { \
321: RB_PARENT(elm, field) = parent; \
322: RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
323: RB_COLOR(elm, field) = RB_RED; \
324: } while (0)
325:
326: #define RB_SET_BLACKRED(black, red, field) do { \
327: RB_COLOR(black, field) = RB_BLACK; \
328: RB_COLOR(red, field) = RB_RED; \
329: } while (0)
330:
331: #ifndef RB_AUGMENT
332: #define RB_AUGMENT(x)
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_ */