1: /* $OpenBSD: tree.h,v 1.14 2015/05/25 03:07:49 deraadt 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) do {} while (0)
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: RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
378: #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
379: RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
380: #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
381: attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
382: attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
383: attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
384: attr struct type *name##_RB_INSERT(struct name *, struct type *); \
385: attr struct type *name##_RB_FIND(struct name *, struct type *); \
386: attr struct type *name##_RB_NFIND(struct name *, struct type *); \
387: attr struct type *name##_RB_NEXT(struct type *); \
388: attr struct type *name##_RB_PREV(struct type *); \
389: attr struct type *name##_RB_MINMAX(struct name *, int); \
390: \
391:
392: /* Main rb operation.
393: * Moves node close to the key of elm to top
394: */
395: #define RB_GENERATE(name, type, field, cmp) \
396: RB_GENERATE_INTERNAL(name, type, field, cmp,)
397: #define RB_GENERATE_STATIC(name, type, field, cmp) \
398: RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
399: #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
400: attr void \
401: name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
402: { \
403: struct type *parent, *gparent, *tmp; \
404: while ((parent = RB_PARENT(elm, field)) && \
405: RB_COLOR(parent, field) == RB_RED) { \
406: gparent = RB_PARENT(parent, field); \
407: if (parent == RB_LEFT(gparent, field)) { \
408: tmp = RB_RIGHT(gparent, field); \
409: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
410: RB_COLOR(tmp, field) = RB_BLACK; \
411: RB_SET_BLACKRED(parent, gparent, field);\
412: elm = gparent; \
413: continue; \
414: } \
415: if (RB_RIGHT(parent, field) == elm) { \
416: RB_ROTATE_LEFT(head, parent, tmp, field);\
417: tmp = parent; \
418: parent = elm; \
419: elm = tmp; \
420: } \
421: RB_SET_BLACKRED(parent, gparent, field); \
422: RB_ROTATE_RIGHT(head, gparent, tmp, field); \
423: } else { \
424: tmp = RB_LEFT(gparent, field); \
425: if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
426: RB_COLOR(tmp, field) = RB_BLACK; \
427: RB_SET_BLACKRED(parent, gparent, field);\
428: elm = gparent; \
429: continue; \
430: } \
431: if (RB_LEFT(parent, field) == elm) { \
432: RB_ROTATE_RIGHT(head, parent, tmp, field);\
433: tmp = parent; \
434: parent = elm; \
435: elm = tmp; \
436: } \
437: RB_SET_BLACKRED(parent, gparent, field); \
438: RB_ROTATE_LEFT(head, gparent, tmp, field); \
439: } \
440: } \
441: RB_COLOR(head->rbh_root, field) = RB_BLACK; \
442: } \
443: \
444: attr void \
445: name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
446: { \
447: struct type *tmp; \
448: while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
449: elm != RB_ROOT(head)) { \
450: if (RB_LEFT(parent, field) == elm) { \
451: tmp = RB_RIGHT(parent, field); \
452: if (RB_COLOR(tmp, field) == RB_RED) { \
453: RB_SET_BLACKRED(tmp, parent, field); \
454: RB_ROTATE_LEFT(head, parent, tmp, field);\
455: tmp = RB_RIGHT(parent, field); \
456: } \
457: if ((RB_LEFT(tmp, field) == NULL || \
458: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
459: (RB_RIGHT(tmp, field) == NULL || \
460: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
461: RB_COLOR(tmp, field) = RB_RED; \
462: elm = parent; \
463: parent = RB_PARENT(elm, field); \
464: } else { \
465: if (RB_RIGHT(tmp, field) == NULL || \
466: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
467: struct type *oleft; \
468: if ((oleft = RB_LEFT(tmp, field)))\
469: RB_COLOR(oleft, field) = RB_BLACK;\
470: RB_COLOR(tmp, field) = RB_RED; \
471: RB_ROTATE_RIGHT(head, tmp, oleft, field);\
472: tmp = RB_RIGHT(parent, field); \
473: } \
474: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
475: RB_COLOR(parent, field) = RB_BLACK; \
476: if (RB_RIGHT(tmp, field)) \
477: RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
478: RB_ROTATE_LEFT(head, parent, tmp, field);\
479: elm = RB_ROOT(head); \
480: break; \
481: } \
482: } else { \
483: tmp = RB_LEFT(parent, field); \
484: if (RB_COLOR(tmp, field) == RB_RED) { \
485: RB_SET_BLACKRED(tmp, parent, field); \
486: RB_ROTATE_RIGHT(head, parent, tmp, field);\
487: tmp = RB_LEFT(parent, field); \
488: } \
489: if ((RB_LEFT(tmp, field) == NULL || \
490: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
491: (RB_RIGHT(tmp, field) == NULL || \
492: RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
493: RB_COLOR(tmp, field) = RB_RED; \
494: elm = parent; \
495: parent = RB_PARENT(elm, field); \
496: } else { \
497: if (RB_LEFT(tmp, field) == NULL || \
498: RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
499: struct type *oright; \
500: if ((oright = RB_RIGHT(tmp, field)))\
501: RB_COLOR(oright, field) = RB_BLACK;\
502: RB_COLOR(tmp, field) = RB_RED; \
503: RB_ROTATE_LEFT(head, tmp, oright, field);\
504: tmp = RB_LEFT(parent, field); \
505: } \
506: RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
507: RB_COLOR(parent, field) = RB_BLACK; \
508: if (RB_LEFT(tmp, field)) \
509: RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
510: RB_ROTATE_RIGHT(head, parent, tmp, field);\
511: elm = RB_ROOT(head); \
512: break; \
513: } \
514: } \
515: } \
516: if (elm) \
517: RB_COLOR(elm, field) = RB_BLACK; \
518: } \
519: \
520: attr struct type * \
521: name##_RB_REMOVE(struct name *head, struct type *elm) \
522: { \
523: struct type *child, *parent, *old = elm; \
524: int color; \
525: if (RB_LEFT(elm, field) == NULL) \
526: child = RB_RIGHT(elm, field); \
527: else if (RB_RIGHT(elm, field) == NULL) \
528: child = RB_LEFT(elm, field); \
529: else { \
530: struct type *left; \
531: elm = RB_RIGHT(elm, field); \
532: while ((left = RB_LEFT(elm, field))) \
533: elm = left; \
534: child = RB_RIGHT(elm, field); \
535: parent = RB_PARENT(elm, field); \
536: color = RB_COLOR(elm, field); \
537: if (child) \
538: RB_PARENT(child, field) = parent; \
539: if (parent) { \
540: if (RB_LEFT(parent, field) == elm) \
541: RB_LEFT(parent, field) = child; \
542: else \
543: RB_RIGHT(parent, field) = child; \
544: RB_AUGMENT(parent); \
545: } else \
546: RB_ROOT(head) = child; \
547: if (RB_PARENT(elm, field) == old) \
548: parent = elm; \
549: (elm)->field = (old)->field; \
550: if (RB_PARENT(old, field)) { \
551: if (RB_LEFT(RB_PARENT(old, field), field) == old)\
552: RB_LEFT(RB_PARENT(old, field), field) = elm;\
553: else \
554: RB_RIGHT(RB_PARENT(old, field), field) = elm;\
555: RB_AUGMENT(RB_PARENT(old, field)); \
556: } else \
557: RB_ROOT(head) = elm; \
558: RB_PARENT(RB_LEFT(old, field), field) = elm; \
559: if (RB_RIGHT(old, field)) \
560: RB_PARENT(RB_RIGHT(old, field), field) = elm; \
561: if (parent) { \
562: left = parent; \
563: do { \
564: RB_AUGMENT(left); \
565: } while ((left = RB_PARENT(left, field))); \
566: } \
567: goto color; \
568: } \
569: parent = RB_PARENT(elm, field); \
570: color = RB_COLOR(elm, field); \
571: if (child) \
572: RB_PARENT(child, field) = parent; \
573: if (parent) { \
574: if (RB_LEFT(parent, field) == elm) \
575: RB_LEFT(parent, field) = child; \
576: else \
577: RB_RIGHT(parent, field) = child; \
578: RB_AUGMENT(parent); \
579: } else \
580: RB_ROOT(head) = child; \
581: color: \
582: if (color == RB_BLACK) \
583: name##_RB_REMOVE_COLOR(head, parent, child); \
584: return (old); \
585: } \
586: \
587: /* Inserts a node into the RB tree */ \
588: attr struct type * \
589: name##_RB_INSERT(struct name *head, struct type *elm) \
590: { \
591: struct type *tmp; \
592: struct type *parent = NULL; \
593: int comp = 0; \
594: tmp = RB_ROOT(head); \
595: while (tmp) { \
596: parent = tmp; \
597: comp = (cmp)(elm, parent); \
598: if (comp < 0) \
599: tmp = RB_LEFT(tmp, field); \
600: else if (comp > 0) \
601: tmp = RB_RIGHT(tmp, field); \
602: else \
603: return (tmp); \
604: } \
605: RB_SET(elm, parent, field); \
606: if (parent != NULL) { \
607: if (comp < 0) \
608: RB_LEFT(parent, field) = elm; \
609: else \
610: RB_RIGHT(parent, field) = elm; \
611: RB_AUGMENT(parent); \
612: } else \
613: RB_ROOT(head) = elm; \
614: name##_RB_INSERT_COLOR(head, elm); \
615: return (NULL); \
616: } \
617: \
618: /* Finds the node with the same key as elm */ \
619: attr struct type * \
620: name##_RB_FIND(struct name *head, struct type *elm) \
621: { \
622: struct type *tmp = RB_ROOT(head); \
623: int comp; \
624: while (tmp) { \
625: comp = cmp(elm, tmp); \
626: if (comp < 0) \
627: tmp = RB_LEFT(tmp, field); \
628: else if (comp > 0) \
629: tmp = RB_RIGHT(tmp, field); \
630: else \
631: return (tmp); \
632: } \
633: return (NULL); \
634: } \
635: \
636: /* Finds the first node greater than or equal to the search key */ \
637: attr struct type * \
638: name##_RB_NFIND(struct name *head, struct type *elm) \
639: { \
640: struct type *tmp = RB_ROOT(head); \
641: struct type *res = NULL; \
642: int comp; \
643: while (tmp) { \
644: comp = cmp(elm, tmp); \
645: if (comp < 0) { \
646: res = tmp; \
647: tmp = RB_LEFT(tmp, field); \
648: } \
649: else if (comp > 0) \
650: tmp = RB_RIGHT(tmp, field); \
651: else \
652: return (tmp); \
653: } \
654: return (res); \
655: } \
656: \
657: /* ARGSUSED */ \
658: attr struct type * \
659: name##_RB_NEXT(struct type *elm) \
660: { \
661: if (RB_RIGHT(elm, field)) { \
662: elm = RB_RIGHT(elm, field); \
663: while (RB_LEFT(elm, field)) \
664: elm = RB_LEFT(elm, field); \
665: } else { \
666: if (RB_PARENT(elm, field) && \
667: (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
668: elm = RB_PARENT(elm, field); \
669: else { \
670: while (RB_PARENT(elm, field) && \
671: (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
672: elm = RB_PARENT(elm, field); \
673: elm = RB_PARENT(elm, field); \
674: } \
675: } \
676: return (elm); \
677: } \
678: \
679: /* ARGSUSED */ \
680: attr struct type * \
681: name##_RB_PREV(struct type *elm) \
682: { \
683: if (RB_LEFT(elm, field)) { \
684: elm = RB_LEFT(elm, field); \
685: while (RB_RIGHT(elm, field)) \
686: elm = RB_RIGHT(elm, field); \
687: } else { \
688: if (RB_PARENT(elm, field) && \
689: (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
690: elm = RB_PARENT(elm, field); \
691: else { \
692: while (RB_PARENT(elm, field) && \
693: (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
694: elm = RB_PARENT(elm, field); \
695: elm = RB_PARENT(elm, field); \
696: } \
697: } \
698: return (elm); \
699: } \
700: \
701: attr struct type * \
702: name##_RB_MINMAX(struct name *head, int val) \
703: { \
704: struct type *tmp = RB_ROOT(head); \
705: struct type *parent = NULL; \
706: while (tmp) { \
707: parent = tmp; \
708: if (val < 0) \
709: tmp = RB_LEFT(tmp, field); \
710: else \
711: tmp = RB_RIGHT(tmp, field); \
712: } \
713: return (parent); \
714: }
715:
716: #define RB_NEGINF -1
717: #define RB_INF 1
718:
719: #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
720: #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
721: #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
722: #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
723: #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
724: #define RB_PREV(name, x, y) name##_RB_PREV(y)
725: #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
726: #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
727:
728: #define RB_FOREACH(x, name, head) \
729: for ((x) = RB_MIN(name, head); \
730: (x) != NULL; \
731: (x) = name##_RB_NEXT(x))
732:
733: #define RB_FOREACH_SAFE(x, name, head, y) \
734: for ((x) = RB_MIN(name, head); \
735: ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
736: (x) = (y))
737:
738: #define RB_FOREACH_REVERSE(x, name, head) \
739: for ((x) = RB_MAX(name, head); \
740: (x) != NULL; \
741: (x) = name##_RB_PREV(x))
742:
743: #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
744: for ((x) = RB_MAX(name, head); \
745: ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
746: (x) = (y))
747:
748: #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 / pimd / libite