source: branches/pex/libtransmission/bsdtree.h @ 1540

Last change on this file since 1540 was 1540, checked in by joshe, 15 years ago

Implement Azureus peer protocol, including PEX message.
Implement extended messages, including uTorrent PEX.

  • Property svn:keywords set to Date Rev Author Id
File size: 23.0 KB
Line 
1/*      $Id: bsdtree.h 1540 2007-03-08 04:06:58Z joshe $        */
2/*      $NetBSD: tree.h,v 1.14 2007/01/20 20:15:13 ad Exp $     */
3/*      $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
4/*
5 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef _SYS_TREE_H_
30#define _SYS_TREE_H_
31
32/*
33 * This file defines data structures for different types of trees:
34 * splay trees and red-black trees.
35 *
36 * A splay tree is a self-organizing data structure.  Every operation
37 * on the tree causes a splay to happen.  The splay moves the requested
38 * node to the root of the tree and partly rebalances it.
39 *
40 * This has the benefit that request locality causes faster lookups as
41 * the requested nodes move to the top of the tree.  On the other hand,
42 * every lookup causes memory writes.
43 *
44 * The Balance Theorem bounds the total access time for m operations
45 * and n inserts on an initially empty tree as O((m + n)lg n).  The
46 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
47 *
48 * A red-black tree is a binary search tree with the node color as an
49 * extra attribute.  It fulfills a set of conditions:
50 *      - every search path from the root to a leaf consists of the
51 *        same number of black nodes,
52 *      - each red node (except for the root) has a black parent,
53 *      - each leaf node is black.
54 *
55 * Every operation on a red-black tree is bounded as O(lg n).
56 * The maximum height of a red-black tree is 2lg (n+1).
57 */
58
59#define SPLAY_HEAD(name, type)                                          \
60struct name {                                                           \
61        struct type *sph_root; /* root of the tree */                   \
62}
63
64#define SPLAY_INITIALIZER(root)                                         \
65        { NULL }
66
67#define SPLAY_INIT(root) do {                                           \
68        (root)->sph_root = NULL;                                        \
69} while (/*CONSTCOND*/ 0)
70
71#define SPLAY_ENTRY(type)                                               \
72struct {                                                                \
73        struct type *spe_left; /* left element */                       \
74        struct type *spe_right; /* right element */                     \
75}
76
77#define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
78#define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
79#define SPLAY_ROOT(head)                (head)->sph_root
80#define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
81
82/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
83#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
84        SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
85        SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
86        (head)->sph_root = tmp;                                         \
87} while (/*CONSTCOND*/ 0)
88
89#define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
90        SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
91        SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
92        (head)->sph_root = tmp;                                         \
93} while (/*CONSTCOND*/ 0)
94
95#define SPLAY_LINKLEFT(head, tmp, field) do {                           \
96        SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
97        tmp = (head)->sph_root;                                         \
98        (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
99} while (/*CONSTCOND*/ 0)
100
101#define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
102        SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
103        tmp = (head)->sph_root;                                         \
104        (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
105} while (/*CONSTCOND*/ 0)
106
107#define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
108        SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
109        SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
110        SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
111        SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
112} while (/*CONSTCOND*/ 0)
113
114/* Generates prototypes and inline functions */
115
116#define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
117void name##_SPLAY(struct name *, struct type *);                        \
118void name##_SPLAY_MINMAX(struct name *, int);                           \
119struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
120struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
121                                                                        \
122/* Finds the node with the same key as elm */                           \
123static __inline struct type *                                           \
124name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
125{                                                                       \
126        if (SPLAY_EMPTY(head))                                          \
127                return(NULL);                                           \
128        name##_SPLAY(head, elm);                                        \
129        if ((cmp)(elm, (head)->sph_root) == 0)                          \
130                return (head->sph_root);                                \
131        return (NULL);                                                  \
132}                                                                       \
133                                                                        \
134static __inline struct type *                                           \
135name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
136{                                                                       \
137        name##_SPLAY(head, elm);                                        \
138        if (SPLAY_RIGHT(elm, field) != NULL) {                          \
139                elm = SPLAY_RIGHT(elm, field);                          \
140                while (SPLAY_LEFT(elm, field) != NULL) {                \
141                        elm = SPLAY_LEFT(elm, field);                   \
142                }                                                       \
143        } else                                                          \
144                elm = NULL;                                             \
145        return (elm);                                                   \
146}                                                                       \
147                                                                        \
148static __inline struct type *                                           \
149name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
150{                                                                       \
151        name##_SPLAY_MINMAX(head, val);                                 \
152        return (SPLAY_ROOT(head));                                      \
153}
154
155/* Main splay operation.
156 * Moves node close to the key of elm to top
157 */
158#define SPLAY_GENERATE(name, type, field, cmp)                          \
159struct type *                                                           \
160name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
161{                                                                       \
162    if (SPLAY_EMPTY(head)) {                                            \
163            SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
164    } else {                                                            \
165            int __comp;                                                 \
166            name##_SPLAY(head, elm);                                    \
167            __comp = (cmp)(elm, (head)->sph_root);                      \
168            if(__comp < 0) {                                            \
169                    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
170                    SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
171                    SPLAY_LEFT((head)->sph_root, field) = NULL;         \
172            } else if (__comp > 0) {                                    \
173                    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
174                    SPLAY_LEFT(elm, field) = (head)->sph_root;          \
175                    SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
176            } else                                                      \
177                    return ((head)->sph_root);                          \
178    }                                                                   \
179    (head)->sph_root = (elm);                                           \
180    return (NULL);                                                      \
181}                                                                       \
182                                                                        \
183struct type *                                                           \
184name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
185{                                                                       \
186        struct type *__tmp;                                             \
187        if (SPLAY_EMPTY(head))                                          \
188                return (NULL);                                          \
189        name##_SPLAY(head, elm);                                        \
190        if ((cmp)(elm, (head)->sph_root) == 0) {                        \
191                if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
192                        (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
193                } else {                                                \
194                        __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
195                        (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
196                        name##_SPLAY(head, elm);                        \
197                        SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
198                }                                                       \
199                return (elm);                                           \
200        }                                                               \
201        return (NULL);                                                  \
202}                                                                       \
203                                                                        \
204void                                                                    \
205name##_SPLAY(struct name *head, struct type *elm)                       \
206{                                                                       \
207        struct type __node, *__left, *__right, *__tmp;                  \
208        int __comp;                                                     \
209\
210        SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
211        __left = __right = &__node;                                     \
212\
213        while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
214                if (__comp < 0) {                                       \
215                        __tmp = SPLAY_LEFT((head)->sph_root, field);    \
216                        if (__tmp == NULL)                              \
217                                break;                                  \
218                        if ((cmp)(elm, __tmp) < 0){                     \
219                                SPLAY_ROTATE_RIGHT(head, __tmp, field); \
220                                if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
221                                        break;                          \
222                        }                                               \
223                        SPLAY_LINKLEFT(head, __right, field);           \
224                } else if (__comp > 0) {                                \
225                        __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
226                        if (__tmp == NULL)                              \
227                                break;                                  \
228                        if ((cmp)(elm, __tmp) > 0){                     \
229                                SPLAY_ROTATE_LEFT(head, __tmp, field);  \
230                                if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
231                                        break;                          \
232                        }                                               \
233                        SPLAY_LINKRIGHT(head, __left, field);           \
234                }                                                       \
235        }                                                               \
236        SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
237}                                                                       \
238                                                                        \
239/* Splay with either the minimum or the maximum element                 \
240 * Used to find minimum or maximum element in tree.                     \
241 */                                                                     \
242void name##_SPLAY_MINMAX(struct name *head, int __comp) \
243{                                                                       \
244        struct type __node, *__left, *__right, *__tmp;                  \
245\
246        SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
247        __left = __right = &__node;                                     \
248\
249        while (1) {                                                     \
250                if (__comp < 0) {                                       \
251                        __tmp = SPLAY_LEFT((head)->sph_root, field);    \
252                        if (__tmp == NULL)                              \
253                                break;                                  \
254                        if (__comp < 0){                                \
255                                SPLAY_ROTATE_RIGHT(head, __tmp, field); \
256                                if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
257                                        break;                          \
258                        }                                               \
259                        SPLAY_LINKLEFT(head, __right, field);           \
260                } else if (__comp > 0) {                                \
261                        __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
262                        if (__tmp == NULL)                              \
263                                break;                                  \
264                        if (__comp > 0) {                               \
265                                SPLAY_ROTATE_LEFT(head, __tmp, field);  \
266                                if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
267                                        break;                          \
268                        }                                               \
269                        SPLAY_LINKRIGHT(head, __left, field);           \
270                }                                                       \
271        }                                                               \
272        SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
273}
274
275#define SPLAY_NEGINF    -1
276#define SPLAY_INF       1
277
278#define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
279#define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
280#define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
281#define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
282#define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
283                                        : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
284#define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
285                                        : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
286
287#define SPLAY_FOREACH(x, name, head)                                    \
288        for ((x) = SPLAY_MIN(name, head);                               \
289             (x) != NULL;                                               \
290             (x) = SPLAY_NEXT(name, head, x))
291
292/* Macros that define a red-black tree */
293#define RB_HEAD(name, type)                                             \
294struct name {                                                           \
295        struct type *rbh_root; /* root of the tree */                   \
296}
297
298#define RB_INITIALIZER(root)                                            \
299        { NULL }
300
301#define RB_INIT(root) do {                                              \
302        (root)->rbh_root = NULL;                                        \
303} while (/*CONSTCOND*/ 0)
304
305#define RB_BLACK        0
306#define RB_RED          1
307#define RB_ENTRY(type)                                                  \
308struct {                                                                \
309        struct type *rbe_left;          /* left element */              \
310        struct type *rbe_right;         /* right element */             \
311        struct type *rbe_parent;        /* parent element */            \
312        int rbe_color;                  /* node color */                \
313}
314
315#define RB_LEFT(elm, field)             (elm)->field.rbe_left
316#define RB_RIGHT(elm, field)            (elm)->field.rbe_right
317#define RB_PARENT(elm, field)           (elm)->field.rbe_parent
318#define RB_COLOR(elm, field)            (elm)->field.rbe_color
319#define RB_ROOT(head)                   (head)->rbh_root
320#define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
321
322#define RB_SET(elm, parent, field) do {                                 \
323        RB_PARENT(elm, field) = parent;                                 \
324        RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
325        RB_COLOR(elm, field) = RB_RED;                                  \
326} while (/*CONSTCOND*/ 0)
327
328#define RB_SET_BLACKRED(black, red, field) do {                         \
329        RB_COLOR(black, field) = RB_BLACK;                              \
330        RB_COLOR(red, field) = RB_RED;                                  \
331} while (/*CONSTCOND*/ 0)
332
333#ifndef RB_AUGMENT
334#define RB_AUGMENT(x) (void)(x)
335#endif
336
337#define RB_ROTATE_LEFT(head, elm, tmp, field) do {                      \
338        (tmp) = RB_RIGHT(elm, field);                                   \
339        if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {     \
340                RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
341        }                                                               \
342        RB_AUGMENT(elm);                                                \
343        if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
344                if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
345                        RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
346                else                                                    \
347                        RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
348        } else                                                          \
349                (head)->rbh_root = (tmp);                               \
350        RB_LEFT(tmp, field) = (elm);                                    \
351        RB_PARENT(elm, field) = (tmp);                                  \
352        RB_AUGMENT(tmp);                                                \
353        if ((RB_PARENT(tmp, field)))                                    \
354                RB_AUGMENT(RB_PARENT(tmp, field));                      \
355} while (/*CONSTCOND*/ 0)
356
357#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
358        (tmp) = RB_LEFT(elm, field);                                    \
359        if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {     \
360                RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
361        }                                                               \
362        RB_AUGMENT(elm);                                                \
363        if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
364                if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
365                        RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
366                else                                                    \
367                        RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
368        } else                                                          \
369                (head)->rbh_root = (tmp);                               \
370        RB_RIGHT(tmp, field) = (elm);                                   \
371        RB_PARENT(elm, field) = (tmp);                                  \
372        RB_AUGMENT(tmp);                                                \
373        if ((RB_PARENT(tmp, field)))                                    \
374                RB_AUGMENT(RB_PARENT(tmp, field));                      \
375} while (/*CONSTCOND*/ 0)
376
377/* Generates prototypes and inline functions */
378#define RB_PROTOTYPE(name, type, field, cmp)                            \
379        RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
380#define RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
381        RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
382#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)             \
383attr void name##_RB_INSERT_COLOR(struct name *, struct type *);         \
384attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
385attr struct type *name##_RB_REMOVE(struct name *, struct type *);       \
386attr struct type *name##_RB_INSERT(struct name *, struct type *);       \
387attr struct type *name##_RB_FIND(struct name *, struct type *);         \
388attr struct type *name##_RB_NEXT(struct type *);                        \
389attr 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, __unused static)
399#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)              \
400attr void                                                               \
401name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
402{                                                                       \
403        struct type *parent, *gparent, *tmp;                            \
404        while ((parent = RB_PARENT(elm, field)) != NULL &&              \
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                                                                        \
444attr void                                                               \
445name##_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                                            != NULL)                    \
470                                                RB_COLOR(oleft, field) = RB_BLACK;\
471                                        RB_COLOR(tmp, field) = RB_RED;  \
472                                        RB_ROTATE_RIGHT(head, tmp, oleft, field);\
473                                        tmp = RB_RIGHT(parent, field);  \
474                                }                                       \
475                                RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
476                                RB_COLOR(parent, field) = RB_BLACK;     \
477                                if (RB_RIGHT(tmp, field))               \
478                                        RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
479                                RB_ROTATE_LEFT(head, parent, tmp, field);\
480                                elm = RB_ROOT(head);                    \
481                                break;                                  \
482                        }                                               \
483                } else {                                                \
484                        tmp = RB_LEFT(parent, field);                   \
485                        if (RB_COLOR(tmp, field) == RB_RED) {           \
486                                RB_SET_BLACKRED(tmp, parent, field);    \
487                                RB_ROTATE_RIGHT(head, parent, tmp, field);\
488                                tmp = RB_LEFT(parent, field);           \
489                        }                                               \
490                        if ((RB_LEFT(tmp, field) == NULL ||             \
491                            RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
492                            (RB_RIGHT(tmp, field) == NULL ||            \
493                            RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
494                                RB_COLOR(tmp, field) = RB_RED;          \
495                                elm = parent;                           \
496                                parent = RB_PARENT(elm, field);         \
497                        } else {                                        \
498                                if (RB_LEFT(tmp, field) == NULL ||      \
499                                    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
500                                        struct type *oright;            \
501                                        if ((oright = RB_RIGHT(tmp, field)) \
502                                            != NULL)                    \
503                                                RB_COLOR(oright, field) = RB_BLACK;\
504                                        RB_COLOR(tmp, field) = RB_RED;  \
505                                        RB_ROTATE_LEFT(head, tmp, oright, field);\
506                                        tmp = RB_LEFT(parent, field);   \
507                                }                                       \
508                                RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
509                                RB_COLOR(parent, field) = RB_BLACK;     \
510                                if (RB_LEFT(tmp, field))                \
511                                        RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
512                                RB_ROTATE_RIGHT(head, parent, tmp, field);\
513                                elm = RB_ROOT(head);                    \
514                                break;                                  \
515                        }                                               \
516                }                                                       \
517        }                                                               \
518        if (elm)                                                        \
519                RB_COLOR(elm, field) = RB_BLACK;                        \
520}                                                                       \
521                                                                        \
522attr struct type *                                                      \
523name##_RB_REMOVE(struct name *head, struct type *elm)                   \
524{                                                                       \
525        struct type *child, *parent, *old = elm;                        \
526        int color;                                                      \
527        if (RB_LEFT(elm, field) == NULL)                                \
528                child = RB_RIGHT(elm, field);                           \
529        else if (RB_RIGHT(elm, field) == NULL)                          \
530                child = RB_LEFT(elm, field);                            \
531        else {                                                          \
532                struct type *left;                                      \
533                elm = RB_RIGHT(elm, field);                             \
534                while ((left = RB_LEFT(elm, field)) != NULL)            \
535                        elm = left;                                     \
536                child = RB_RIGHT(elm, field);                           \
537                parent = RB_PARENT(elm, field);                         \
538                color = RB_COLOR(elm, field);                           \
539                if (child)                                              \
540                        RB_PARENT(child, field) = parent;               \
541                if (parent) {                                           \
542                        if (RB_LEFT(parent, field) == elm)              \
543                                RB_LEFT(parent, field) = child;         \
544                        else                                            \
545                                RB_RIGHT(parent, field) = child;        \
546                        RB_AUGMENT(parent);                             \
547                } else                                                  \
548                        RB_ROOT(head) = child;                          \
549                if (RB_PARENT(elm, field) == old)                       \
550                        parent = elm;                                   \
551                (elm)->field = (old)->field;                            \
552                if (RB_PARENT(old, field)) {                            \
553                        if (RB_LEFT(RB_PARENT(old, field), field) == old)\
554                                RB_LEFT(RB_PARENT(old, field), field) = elm;\
555                        else                                            \
556                                RB_RIGHT(RB_PARENT(old, field), field) = elm;\
557                        RB_AUGMENT(RB_PARENT(old, field));              \
558                } else                                                  \
559                        RB_ROOT(head) = elm;                            \
560                RB_PARENT(RB_LEFT(old, field), field) = elm;            \
561                if (RB_RIGHT(old, field))                               \
562                        RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
563                if (parent) {                                           \
564                        left = parent;                                  \
565                        do {                                            \
566                                RB_AUGMENT(left);                       \
567                        } while ((left = RB_PARENT(left, field)) != NULL); \
568                }                                                       \
569                goto color;                                             \
570        }                                                               \
571        parent = RB_PARENT(elm, field);                                 \
572        color = RB_COLOR(elm, field);                                   \
573        if (child)                                                      \
574                RB_PARENT(child, field) = parent;                       \
575        if (parent) {                                                   \
576                if (RB_LEFT(parent, field) == elm)                      \
577                        RB_LEFT(parent, field) = child;                 \
578                else                                                    \
579                        RB_RIGHT(parent, field) = child;                \
580                RB_AUGMENT(parent);                                     \
581        } else                                                          \
582                RB_ROOT(head) = child;                                  \
583color:                                                                  \
584        if (color == RB_BLACK)                                          \
585                name##_RB_REMOVE_COLOR(head, parent, child);            \
586        return (old);                                                   \
587}                                                                       \
588                                                                        \
589/* Inserts a node into the RB tree */                                   \
590attr struct type *                                                      \
591name##_RB_INSERT(struct name *head, struct type *elm)                   \
592{                                                                       \
593        struct type *tmp;                                               \
594        struct type *parent = NULL;                                     \
595        int comp = 0;                                                   \
596        tmp = RB_ROOT(head);                                            \
597        while (tmp) {                                                   \
598                parent = tmp;                                           \
599                comp = (cmp)(elm, parent);                              \
600                if (comp < 0)                                           \
601                        tmp = RB_LEFT(tmp, field);                      \
602                else if (comp > 0)                                      \
603                        tmp = RB_RIGHT(tmp, field);                     \
604                else                                                    \
605                        return (tmp);                                   \
606        }                                                               \
607        RB_SET(elm, parent, field);                                     \
608        if (parent != NULL) {                                           \
609                if (comp < 0)                                           \
610                        RB_LEFT(parent, field) = elm;                   \
611                else                                                    \
612                        RB_RIGHT(parent, field) = elm;                  \
613                RB_AUGMENT(parent);                                     \
614        } else                                                          \
615                RB_ROOT(head) = elm;                                    \
616        name##_RB_INSERT_COLOR(head, elm);                              \
617        return (NULL);                                                  \
618}                                                                       \
619                                                                        \
620/* Finds the node with the same key as elm */                           \
621attr struct type *                                                      \
622name##_RB_FIND(struct name *head, struct type *elm)                     \
623{                                                                       \
624        struct type *tmp = RB_ROOT(head);                               \
625        int comp;                                                       \
626        while (tmp) {                                                   \
627                comp = cmp(elm, tmp);                                   \
628                if (comp < 0)                                           \
629                        tmp = RB_LEFT(tmp, field);                      \
630                else if (comp > 0)                                      \
631                        tmp = RB_RIGHT(tmp, field);                     \
632                else                                                    \
633                        return (tmp);                                   \
634        }                                                               \
635        return (NULL);                                                  \
636}                                                                       \
637                                                                        \
638/* ARGSUSED */                                                          \
639attr struct type *                                                      \
640name##_RB_NEXT(struct type *elm)                                        \
641{                                                                       \
642        if (RB_RIGHT(elm, field)) {                                     \
643                elm = RB_RIGHT(elm, field);                             \
644                while (RB_LEFT(elm, field))                             \
645                        elm = RB_LEFT(elm, field);                      \
646        } else {                                                        \
647                if (RB_PARENT(elm, field) &&                            \
648                    (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
649                        elm = RB_PARENT(elm, field);                    \
650                else {                                                  \
651                        while (RB_PARENT(elm, field) &&                 \
652                            (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
653                                elm = RB_PARENT(elm, field);            \
654                        elm = RB_PARENT(elm, field);                    \
655                }                                                       \
656        }                                                               \
657        return (elm);                                                   \
658}                                                                       \
659                                                                        \
660attr struct type *                                                      \
661name##_RB_MINMAX(struct name *head, int val)                            \
662{                                                                       \
663        struct type *tmp = RB_ROOT(head);                               \
664        struct type *parent = NULL;                                     \
665        while (tmp) {                                                   \
666                parent = tmp;                                           \
667                if (val < 0)                                            \
668                        tmp = RB_LEFT(tmp, field);                      \
669                else                                                    \
670                        tmp = RB_RIGHT(tmp, field);                     \
671        }                                                               \
672        return (parent);                                                \
673}
674
675#define RB_NEGINF       -1
676#define RB_INF  1
677
678#define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
679#define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
680#define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
681#define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
682#define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
683#define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
684
685#define RB_FOREACH(x, name, head)                                       \
686        for ((x) = RB_MIN(name, head);                                  \
687             (x) != NULL;                                               \
688             (x) = name##_RB_NEXT(x))
689
690#endif  /* _SYS_TREE_H_ */
Note: See TracBrowser for help on using the repository browser.