Annotation of src/usr.bin/ssh/tree.h, Revision 1.1.2.2
1.1.2.2 ! miod 1: /* $OpenBSD: tree.h,v 1.1.2.1 2002/05/17 00:03:25 miod Exp $ */
1.1.2.1 miod 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); \
1.1.2.2 ! miod 117: struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
! 118: struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
1.1.2.1 miod 119: \
1.1.2.2 ! miod 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 * \
1.1.2.1 miod 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 \
1.1.2.2 ! miod 175: return ((head)->sph_root); \
1.1.2.1 miod 176: } \
177: (head)->sph_root = (elm); \
1.1.2.2 ! miod 178: return (NULL); \
1.1.2.1 miod 179: } \
180: \
1.1.2.2 ! miod 181: struct type * \
1.1.2.1 miod 182: name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
183: { \
184: struct type *__tmp; \
185: if (SPLAY_EMPTY(head)) \
1.1.2.2 ! miod 186: return (NULL); \
1.1.2.1 miod 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: } \
1.1.2.2 ! miod 197: return (elm); \
1.1.2.1 miod 198: } \
199: return (NULL); \
200: } \
201: \
1.1.2.2 ! miod 202: void \
! 203: name##_SPLAY(struct name *head, struct type *elm) \
1.1.2.1 miod 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: RB_AUGMENT(RB_PARENT(elm, field)); \
347: } else \
348: (head)->rbh_root = (tmp); \
349: RB_LEFT(tmp, field) = (elm); \
350: RB_PARENT(elm, field) = (tmp); \
351: RB_AUGMENT(tmp); \
352: } while (0)
353:
354: #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
355: (tmp) = RB_LEFT(elm, field); \
356: if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
357: RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
358: } \
359: RB_AUGMENT(elm); \
360: if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
361: if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
362: RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
363: else \
364: RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
365: RB_AUGMENT(RB_PARENT(elm, field)); \
366: } else \
367: (head)->rbh_root = (tmp); \
368: RB_RIGHT(tmp, field) = (elm); \
369: RB_PARENT(elm, field) = (tmp); \
370: RB_AUGMENT(tmp); \
371: } while (0)
372:
373: /* Generates prototypes and inline functions */
374: #define RB_PROTOTYPE(name, type, field, cmp) \
375: void name##_RB_INSERT_COLOR(struct name *, struct type *); \
376: void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
1.1.2.2 ! miod 377: struct type *name##_RB_REMOVE(struct name *, struct type *); \
1.1.2.1 miod 378: struct type *name##_RB_INSERT(struct name *, struct type *); \
379: struct type *name##_RB_FIND(struct name *, struct type *); \
380: struct type *name##_RB_NEXT(struct name *, struct type *); \
381: struct type *name##_RB_MINMAX(struct name *, int); \
382: \
383:
384: /* Main rb operation.
385: * Moves node close to the key of elm to top
386: */
387: #define RB_GENERATE(name, type, field, cmp) \
388: void \
389: name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
390: { \
391: struct type *parent, *gparent, *tmp; \
392: while ((parent = RB_PARENT(elm, field)) && \
393: RB_COLOR(parent, field) == RB_RED) { \
394: gparent = RB_PARENT(parent, field); \
395: if (parent == RB_LEFT(gparent, field)) { \
396: tmp = RB_RIGHT(gparent, field); \
397: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
398: RB_COLOR(tmp, field) = RB_BLACK; \
399: RB_SET_BLACKRED(parent, gparent, field);\
400: elm = gparent; \
401: continue; \
402: } \
403: if (RB_RIGHT(parent, field) == elm) { \
404: RB_ROTATE_LEFT(head, parent, tmp, field);\
405: tmp = parent; \
406: parent = elm; \
407: elm = tmp; \
408: } \
409: RB_SET_BLACKRED(parent, gparent, field); \
410: RB_ROTATE_RIGHT(head, gparent, tmp, field); \
411: } else { \
412: tmp = RB_LEFT(gparent, field); \
413: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
414: RB_COLOR(tmp, field) = RB_BLACK; \
415: RB_SET_BLACKRED(parent, gparent, field);\
416: elm = gparent; \
417: continue; \
418: } \
419: if (RB_LEFT(parent, field) == elm) { \
420: RB_ROTATE_RIGHT(head, parent, tmp, field);\
421: tmp = parent; \
422: parent = elm; \
423: elm = tmp; \
424: } \
425: RB_SET_BLACKRED(parent, gparent, field); \
426: RB_ROTATE_LEFT(head, gparent, tmp, field); \
427: } \
428: } \
429: RB_COLOR(head->rbh_root, field) = RB_BLACK; \
430: } \
431: \
432: void \
433: name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
434: { \
435: struct type *tmp; \
436: while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
437: elm != RB_ROOT(head)) { \
438: if (RB_LEFT(parent, field) == elm) { \
439: tmp = RB_RIGHT(parent, field); \
440: if (RB_COLOR(tmp, field) == RB_RED) { \
441: RB_SET_BLACKRED(tmp, parent, field); \
442: RB_ROTATE_LEFT(head, parent, tmp, field);\
443: tmp = RB_RIGHT(parent, field); \
444: } \
445: if ((RB_LEFT(tmp, field) == NULL || \
446: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
447: (RB_RIGHT(tmp, field) == NULL || \
448: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
449: RB_COLOR(tmp, field) = RB_RED; \
450: elm = parent; \
451: parent = RB_PARENT(elm, field); \
452: } else { \
453: if (RB_RIGHT(tmp, field) == NULL || \
454: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
455: struct type *oleft; \
456: if ((oleft = RB_LEFT(tmp, field)))\
457: RB_COLOR(oleft, field) = RB_BLACK;\
458: RB_COLOR(tmp, field) = RB_RED; \
459: RB_ROTATE_RIGHT(head, tmp, oleft, field);\
460: tmp = RB_RIGHT(parent, field); \
461: } \
462: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
463: RB_COLOR(parent, field) = RB_BLACK; \
464: if (RB_RIGHT(tmp, field)) \
465: RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
466: RB_ROTATE_LEFT(head, parent, tmp, field);\
467: elm = RB_ROOT(head); \
468: break; \
469: } \
470: } else { \
471: tmp = RB_LEFT(parent, field); \
472: if (RB_COLOR(tmp, field) == RB_RED) { \
473: RB_SET_BLACKRED(tmp, parent, field); \
474: RB_ROTATE_RIGHT(head, parent, tmp, field);\
475: tmp = RB_LEFT(parent, field); \
476: } \
477: if ((RB_LEFT(tmp, field) == NULL || \
478: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
479: (RB_RIGHT(tmp, field) == NULL || \
480: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
481: RB_COLOR(tmp, field) = RB_RED; \
482: elm = parent; \
483: parent = RB_PARENT(elm, field); \
484: } else { \
485: if (RB_LEFT(tmp, field) == NULL || \
486: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
487: struct type *oright; \
488: if ((oright = RB_RIGHT(tmp, field)))\
489: RB_COLOR(oright, field) = RB_BLACK;\
490: RB_COLOR(tmp, field) = RB_RED; \
491: RB_ROTATE_LEFT(head, tmp, oright, field);\
492: tmp = RB_LEFT(parent, field); \
493: } \
494: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
495: RB_COLOR(parent, field) = RB_BLACK; \
496: if (RB_LEFT(tmp, field)) \
497: RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
498: RB_ROTATE_RIGHT(head, parent, tmp, field);\
499: elm = RB_ROOT(head); \
500: break; \
501: } \
502: } \
503: } \
504: if (elm) \
505: RB_COLOR(elm, field) = RB_BLACK; \
506: } \
507: \
1.1.2.2 ! miod 508: struct type * \
1.1.2.1 miod 509: name##_RB_REMOVE(struct name *head, struct type *elm) \
510: { \
1.1.2.2 ! miod 511: struct type *child, *parent, *old = elm; \
1.1.2.1 miod 512: int color; \
513: if (RB_LEFT(elm, field) == NULL) \
514: child = RB_RIGHT(elm, field); \
515: else if (RB_RIGHT(elm, field) == NULL) \
516: child = RB_LEFT(elm, field); \
517: else { \
1.1.2.2 ! miod 518: struct type *left; \
1.1.2.1 miod 519: elm = RB_RIGHT(elm, field); \
520: while ((left = RB_LEFT(elm, field))) \
521: elm = left; \
522: child = RB_RIGHT(elm, field); \
523: parent = RB_PARENT(elm, field); \
524: color = RB_COLOR(elm, field); \
525: if (child) \
526: RB_PARENT(child, field) = parent; \
527: if (parent) { \
528: if (RB_LEFT(parent, field) == elm) \
529: RB_LEFT(parent, field) = child; \
530: else \
531: RB_RIGHT(parent, field) = child; \
532: RB_AUGMENT(parent); \
533: } else \
534: RB_ROOT(head) = child; \
535: if (RB_PARENT(elm, field) == old) \
536: parent = elm; \
537: (elm)->field = (old)->field; \
538: if (RB_PARENT(old, field)) { \
539: if (RB_LEFT(RB_PARENT(old, field), field) == old)\
540: RB_LEFT(RB_PARENT(old, field), field) = elm;\
541: else \
542: RB_RIGHT(RB_PARENT(old, field), field) = elm;\
543: RB_AUGMENT(RB_PARENT(old, field)); \
544: } else \
545: RB_ROOT(head) = elm; \
546: RB_PARENT(RB_LEFT(old, field), field) = elm; \
547: if (RB_RIGHT(old, field)) \
548: RB_PARENT(RB_RIGHT(old, field), field) = elm; \
549: if (parent) { \
550: left = parent; \
551: do { \
552: RB_AUGMENT(left); \
553: } while ((left = RB_PARENT(left, field))); \
554: } \
555: goto color; \
556: } \
557: parent = RB_PARENT(elm, field); \
558: color = RB_COLOR(elm, field); \
559: if (child) \
560: RB_PARENT(child, field) = parent; \
561: if (parent) { \
562: if (RB_LEFT(parent, field) == elm) \
563: RB_LEFT(parent, field) = child; \
564: else \
565: RB_RIGHT(parent, field) = child; \
566: RB_AUGMENT(parent); \
567: } else \
568: RB_ROOT(head) = child; \
569: color: \
570: if (color == RB_BLACK) \
571: name##_RB_REMOVE_COLOR(head, parent, child); \
1.1.2.2 ! miod 572: return (old); \
1.1.2.1 miod 573: } \
574: \
575: /* Inserts a node into the RB tree */ \
576: struct type * \
577: name##_RB_INSERT(struct name *head, struct type *elm) \
578: { \
579: struct type *tmp; \
580: struct type *parent = NULL; \
581: int comp = 0; \
582: tmp = RB_ROOT(head); \
583: while (tmp) { \
584: parent = tmp; \
585: comp = (cmp)(elm, parent); \
586: if (comp < 0) \
587: tmp = RB_LEFT(tmp, field); \
588: else if (comp > 0) \
589: tmp = RB_RIGHT(tmp, field); \
590: else \
591: return (tmp); \
592: } \
593: RB_SET(elm, parent, field); \
594: if (parent != NULL) { \
595: if (comp < 0) \
596: RB_LEFT(parent, field) = elm; \
597: else \
598: RB_RIGHT(parent, field) = elm; \
599: RB_AUGMENT(parent); \
600: } else \
601: RB_ROOT(head) = elm; \
602: name##_RB_INSERT_COLOR(head, elm); \
603: return (NULL); \
604: } \
605: \
606: /* Finds the node with the same key as elm */ \
607: struct type * \
608: name##_RB_FIND(struct name *head, struct type *elm) \
609: { \
610: struct type *tmp = RB_ROOT(head); \
611: int comp; \
612: while (tmp) { \
613: comp = cmp(elm, tmp); \
614: if (comp < 0) \
615: tmp = RB_LEFT(tmp, field); \
616: else if (comp > 0) \
617: tmp = RB_RIGHT(tmp, field); \
618: else \
619: return (tmp); \
620: } \
621: return (NULL); \
622: } \
623: \
624: struct type * \
625: name##_RB_NEXT(struct name *head, struct type *elm) \
626: { \
627: if (RB_RIGHT(elm, field)) { \
628: elm = RB_RIGHT(elm, field); \
629: while (RB_LEFT(elm, field)) \
630: elm = RB_LEFT(elm, field); \
631: } else { \
632: if (RB_PARENT(elm, field) && \
633: (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
634: elm = RB_PARENT(elm, field); \
635: else { \
636: while (RB_PARENT(elm, field) && \
637: (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
638: elm = RB_PARENT(elm, field); \
639: elm = RB_PARENT(elm, field); \
640: } \
641: } \
642: return (elm); \
643: } \
644: \
645: struct type * \
646: name##_RB_MINMAX(struct name *head, int val) \
647: { \
648: struct type *tmp = RB_ROOT(head); \
649: struct type *parent = NULL; \
650: while (tmp) { \
651: parent = tmp; \
652: if (val < 0) \
653: tmp = RB_LEFT(tmp, field); \
654: else \
655: tmp = RB_RIGHT(tmp, field); \
656: } \
657: return (parent); \
658: }
659:
660: #define RB_NEGINF -1
661: #define RB_INF 1
662:
663: #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
664: #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
665: #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
666: #define RB_NEXT(name, x, y) name##_RB_NEXT(x, y)
667: #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
668: #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
669:
670: #define RB_FOREACH(x, name, head) \
671: for ((x) = RB_MIN(name, head); \
672: (x) != NULL; \
673: (x) = name##_RB_NEXT(head, x))
674:
675: #endif /* _SYS_TREE_H_ */