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

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

Fix for if unused isn't defined.
Pointless churn to silence char*/unint8_t* warnings.
  • Property svn:keywords set to Date Rev Author Id
File size: 23.0 KB
Line 
1/*      $Id: bsdtree.h 1545 2007-03-08 04:53:50Z 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#ifndef __unused
33#define __unused
34#endif
35
36/*
37 * This file defines data structures for different types of trees:
38 * splay trees and red-black trees.
39 *
40 * A splay tree is a self-organizing data structure.  Every operation
41 * on the tree causes a splay to happen.  The splay moves the requested
42 * node to the root of the tree and partly rebalances it.
43 *
44 * This has the benefit that request locality causes faster lookups as
45 * the requested nodes move to the top of the tree.  On the other hand,
46 * every lookup causes memory writes.
47 *
48 * The Balance Theorem bounds the total access time for m operations
49 * and n inserts on an initially empty tree as O((m + n)lg n).  The
50 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
51 *
52 * A red-black tree is a binary search tree with the node color as an
53 * extra attribute.  It fulfills a set of conditions:
54 *      - every search path from the root to a leaf consists of the
55 *        same number of black nodes,
56 *      - each red node (except for the root) has a black parent,
57 *      - each leaf node is black.
58 *
59 * Every operation on a red-black tree is bounded as O(lg n).
60 * The maximum height of a red-black tree is 2lg (n+1).
61 */
62
63#define SPLAY_HEAD(name, type)                                          \
64struct name {                                                           \
65        struct type *sph_root; /* root of the tree */                   \
66}
67
68#define SPLAY_INITIALIZER(root)                                         \
69        { NULL }
70
71#define SPLAY_INIT(root) do {                                           \
72        (root)->sph_root = NULL;                                        \
73} while (/*CONSTCOND*/ 0)
74
75#define SPLAY_ENTRY(type)                                               \
76struct {                                                                \
77        struct type *spe_left; /* left element */                       \
78        struct type *spe_right; /* right element */                     \
79}
80
81#define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
82#define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
83#define SPLAY_ROOT(head)                (head)->sph_root
84#define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
85
86/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
87#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
88        SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
89        SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
90        (head)->sph_root = tmp;                                         \
91} while (/*CONSTCOND*/ 0)
92
93#define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
94        SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
95        SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
96        (head)->sph_root = tmp;                                         \
97} while (/*CONSTCOND*/ 0)
98
99#define SPLAY_LINKLEFT(head, tmp, field) do {                           \
100        SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
101        tmp = (head)->sph_root;                                         \
102        (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
103} while (/*CONSTCOND*/ 0)
104
105#define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
106        SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
107        tmp = (head)->sph_root;                                         \
108        (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
109} while (/*CONSTCOND*/ 0)
110
111#define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
112        SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
113        SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
114        SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
115        SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
116} while (/*CONSTCOND*/ 0)
117
118/* Generates prototypes and inline functions */
119
120#define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
121void name##_SPLAY(struct name *, struct type *);                        \
122void name##_SPLAY_MINMAX(struct name *, int);                           \
123struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
124struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
125                                                                        \
126/* Finds the node with the same key as elm */                           \
127static __inline struct type *                                           \
128name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
129{                                                                       \
130        if (SPLAY_EMPTY(head))                                          \
131                return(NULL);                                           \
132        name##_SPLAY(head, elm);                                        \
133        if ((cmp)(elm, (head)->sph_root) == 0)                          \
134                return (head->sph_root);                                \
135        return (NULL);                                                  \
136}                                                                       \
137                                                                        \
138static __inline struct type *                                           \
139name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
140{                                                                       \
141        name##_SPLAY(head, elm);                                        \
142        if (SPLAY_RIGHT(elm, field) != NULL) {                          \
143                elm = SPLAY_RIGHT(elm, field);                          \
144                while (SPLAY_LEFT(elm, field) != NULL) {                \
145                        elm = SPLAY_LEFT(elm, field);                   \
146                }                                                       \
147        } else                                                          \
148                elm = NULL;                                             \
149        return (elm);                                                   \
150}                                                                       \
151                                                                        \
152static __inline struct type *                                           \
153name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
154{                                                                       \
155        name##_SPLAY_MINMAX(head, val);                                 \
156        return (SPLAY_ROOT(head));                                      \
157}
158
159/* Main splay operation.
160 * Moves node close to the key of elm to top
161 */
162#define SPLAY_GENERATE(name, type, field, cmp)                          \
163struct type *                                                           \
164name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
165{                                                                       \
166    if (SPLAY_EMPTY(head)) {                                            \
167            SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
168    } else {                                                            \
169            int __comp;                                                 \
170            name##_SPLAY(head, elm);                                    \
171            __comp = (cmp)(elm, (head)->sph_root);                      \
172            if(__comp < 0) {                                            \
173                    SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
174                    SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
175                    SPLAY_LEFT((head)->sph_root, field) = NULL;         \
176            } else if (__comp > 0) {                                    \
177                    SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
178                    SPLAY_LEFT(elm, field) = (head)->sph_root;          \
179                    SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
180            } else                                                      \
181                    return ((head)->sph_root);                          \
182    }                                                                   \
183    (head)->sph_root = (elm);                                           \
184    return (NULL);                                                      \
185}                                                                       \
186                                                                        \
187struct type *                                                           \
188name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
189{                                                                       \
190        struct type *__tmp;                                             \
191        if (SPLAY_EMPTY(head))                                          \
192                return (NULL);                                          \
193        name##_SPLAY(head, elm);                                        \
194        if ((cmp)(elm, (head)->sph_root) == 0) {                        \
195                if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
196                        (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
197                } else {                                                \
198                        __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
199                        (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
200                        name##_SPLAY(head, elm);                        \
201                        SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
202                }                                                       \
203                return (elm);                                           \
204        }                                                               \
205        return (NULL);                                                  \
206}                                                                       \
207                                                                        \
208void                                                                    \
209name##_SPLAY(struct name *head, struct type *elm)                       \
210{                                                                       \
211        struct type __node, *__left, *__right, *__tmp;                  \
212        int __comp;                                                     \
213\
214        SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
215        __left = __right = &__node;                                     \
216\
217        while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
218                if (__comp < 0) {                                       \
219                        __tmp = SPLAY_LEFT((head)->sph_root, field);    \
220                        if (__tmp == NULL)                              \
221                                break;                                  \
222                        if ((cmp)(elm, __tmp) < 0){                     \
223                                SPLAY_ROTATE_RIGHT(head, __tmp, field); \
224                                if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
225                                        break;                          \
226                        }                                               \
227                        SPLAY_LINKLEFT(head, __right, field);           \
228                } else if (__comp > 0) {                                \
229                        __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
230                        if (__tmp == NULL)                              \
231                                break;                                  \
232                        if ((cmp)(elm, __tmp) > 0){                     \
233                                SPLAY_ROTATE_LEFT(head, __tmp, field);  \
234                                if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
235                                        break;                          \
236                        }                                               \
237                        SPLAY_LINKRIGHT(head, __left, field);           \
238                }                                                       \
239        }                                                               \
240        SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
241}                                                                       \
242                                                                        \
243/* Splay with either the minimum or the maximum element                 \
244 * Used to find minimum or maximum element in tree.                     \
245 */                                                                     \
246void name##_SPLAY_MINMAX(struct name *head, int __comp) \
247{                                                                       \
248        struct type __node, *__left, *__right, *__tmp;                  \
249\
250        SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
251        __left = __right = &__node;                                     \
252\
253        while (1) {                                                     \
254                if (__comp < 0) {                                       \
255                        __tmp = SPLAY_LEFT((head)->sph_root, field);    \
256                        if (__tmp == NULL)                              \
257                                break;                                  \
258                        if (__comp < 0){                                \
259                                SPLAY_ROTATE_RIGHT(head, __tmp, field); \
260                                if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
261                                        break;                          \
262                        }                                               \
263                        SPLAY_LINKLEFT(head, __right, field);           \
264                } else if (__comp > 0) {                                \
265                        __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
266                        if (__tmp == NULL)                              \
267                                break;                                  \
268                        if (__comp > 0) {                               \
269                                SPLAY_ROTATE_LEFT(head, __tmp, field);  \
270                                if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
271                                        break;                          \
272                        }                                               \
273                        SPLAY_LINKRIGHT(head, __left, field);           \
274                }                                                       \
275        }                                                               \
276        SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
277}
278
279#define SPLAY_NEGINF    -1
280#define SPLAY_INF       1
281
282#define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
283#define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
284#define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
285#define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
286#define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
287                                        : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
288#define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
289                                        : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
290
291#define SPLAY_FOREACH(x, name, head)                                    \
292        for ((x) = SPLAY_MIN(name, head);                               \
293             (x) != NULL;                                               \
294             (x) = SPLAY_NEXT(name, head, x))
295
296/* Macros that define a red-black tree */
297#define RB_HEAD(name, type)                                             \
298struct name {                                                           \
299        struct type *rbh_root; /* root of the tree */                   \
300}
301
302#define RB_INITIALIZER(root)                                            \
303        { NULL }
304
305#define RB_INIT(root) do {                                              \
306        (root)->rbh_root = NULL;                                        \
307} while (/*CONSTCOND*/ 0)
308
309#define RB_BLACK        0
310#define RB_RED          1
311#define RB_ENTRY(type)                                                  \
312struct {                                                                \
313        struct type *rbe_left;          /* left element */              \
314        struct type *rbe_right;         /* right element */             \
315        struct type *rbe_parent;        /* parent element */            \
316        int rbe_color;                  /* node color */                \
317}
318
319#define RB_LEFT(elm, field)             (elm)->field.rbe_left
320#define RB_RIGHT(elm, field)            (elm)->field.rbe_right
321#define RB_PARENT(elm, field)           (elm)->field.rbe_parent
322#define RB_COLOR(elm, field)            (elm)->field.rbe_color
323#define RB_ROOT(head)                   (head)->rbh_root
324#define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
325
326#define RB_SET(elm, parent, field) do {                                 \
327        RB_PARENT(elm, field) = parent;                                 \
328        RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
329        RB_COLOR(elm, field) = RB_RED;                                  \
330} while (/*CONSTCOND*/ 0)
331
332#define RB_SET_BLACKRED(black, red, field) do {                         \
333        RB_COLOR(black, field) = RB_BLACK;                              \
334        RB_COLOR(red, field) = RB_RED;                                  \
335} while (/*CONSTCOND*/ 0)
336
337#ifndef RB_AUGMENT
338#define RB_AUGMENT(x) (void)(x)
339#endif
340
341#define RB_ROTATE_LEFT(head, elm, tmp, field) do {                      \
342        (tmp) = RB_RIGHT(elm, field);                                   \
343        if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {     \
344                RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
345        }                                                               \
346        RB_AUGMENT(elm);                                                \
347        if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
348                if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
349                        RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
350                else                                                    \
351                        RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
352        } else                                                          \
353                (head)->rbh_root = (tmp);                               \
354        RB_LEFT(tmp, field) = (elm);                                    \
355        RB_PARENT(elm, field) = (tmp);                                  \
356        RB_AUGMENT(tmp);                                                \
357        if ((RB_PARENT(tmp, field)))                                    \
358                RB_AUGMENT(RB_PARENT(tmp, field));                      \
359} while (/*CONSTCOND*/ 0)
360
361#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
362        (tmp) = RB_LEFT(elm, field);                                    \
363        if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {     \
364                RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
365        }                                                               \
366        RB_AUGMENT(elm);                                                \
367        if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
368                if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
369                        RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
370                else                                                    \
371                        RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
372        } else                                                          \
373                (head)->rbh_root = (tmp);                               \
374        RB_RIGHT(tmp, field) = (elm);                                   \
375        RB_PARENT(elm, field) = (tmp);                                  \
376        RB_AUGMENT(tmp);                                                \
377        if ((RB_PARENT(tmp, field)))                                    \
378                RB_AUGMENT(RB_PARENT(tmp, field));                      \
379} while (/*CONSTCOND*/ 0)
380
381/* Generates prototypes and inline functions */
382#define RB_PROTOTYPE(name, type, field, cmp)                            \
383        RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
384#define RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
385        RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
386#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)             \
387attr void name##_RB_INSERT_COLOR(struct name *, struct type *);         \
388attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
389attr struct type *name##_RB_REMOVE(struct name *, struct type *);       \
390attr struct type *name##_RB_INSERT(struct name *, struct type *);       \
391attr struct type *name##_RB_FIND(struct name *, struct type *);         \
392attr struct type *name##_RB_NEXT(struct type *);                        \
393attr struct type *name##_RB_MINMAX(struct name *, int);                 \
394                                                                        \
395
396/* Main rb operation.
397 * Moves node close to the key of elm to top
398 */
399#define RB_GENERATE(name, type, field, cmp)                             \
400        RB_GENERATE_INTERNAL(name, type, field, cmp,)
401#define RB_GENERATE_STATIC(name, type, field, cmp)                      \
402        RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
403#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)              \
404attr void                                                               \
405name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
406{                                                                       \
407        struct type *parent, *gparent, *tmp;                            \
408        while ((parent = RB_PARENT(elm, field)) != NULL &&              \
409            RB_COLOR(parent, field) == RB_RED) {                        \
410                gparent = RB_PARENT(parent, field);                     \
411                if (parent == RB_LEFT(gparent, field)) {                \
412                        tmp = RB_RIGHT(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_RIGHT(parent, field) == elm) {           \
420                                RB_ROTATE_LEFT(head, parent, tmp, field);\
421                                tmp = parent;                           \
422                                parent = elm;                           \
423                                elm = tmp;                              \
424                        }                                               \
425                        RB_SET_BLACKRED(parent, gparent, field);        \
426                        RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
427                } else {                                                \
428                        tmp = RB_LEFT(gparent, field);                  \
429                        if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
430                                RB_COLOR(tmp, field) = RB_BLACK;        \
431                                RB_SET_BLACKRED(parent, gparent, field);\
432                                elm = gparent;                          \
433                                continue;                               \
434                        }                                               \
435                        if (RB_LEFT(parent, field) == elm) {            \
436                                RB_ROTATE_RIGHT(head, parent, tmp, field);\
437                                tmp = parent;                           \
438                                parent = elm;                           \
439                                elm = tmp;                              \
440                        }                                               \
441                        RB_SET_BLACKRED(parent, gparent, field);        \
442                        RB_ROTATE_LEFT(head, gparent, tmp, field);      \
443                }                                                       \
444        }                                                               \
445        RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
446}                                                                       \
447                                                                        \
448attr void                                                               \
449name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
450{                                                                       \
451        struct type *tmp;                                               \
452        while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
453            elm != RB_ROOT(head)) {                                     \
454                if (RB_LEFT(parent, field) == elm) {                    \
455                        tmp = RB_RIGHT(parent, field);                  \
456                        if (RB_COLOR(tmp, field) == RB_RED) {           \
457                                RB_SET_BLACKRED(tmp, parent, field);    \
458                                RB_ROTATE_LEFT(head, parent, tmp, field);\
459                                tmp = RB_RIGHT(parent, field);          \
460                        }                                               \
461                        if ((RB_LEFT(tmp, field) == NULL ||             \
462                            RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
463                            (RB_RIGHT(tmp, field) == NULL ||            \
464                            RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
465                                RB_COLOR(tmp, field) = RB_RED;          \
466                                elm = parent;                           \
467                                parent = RB_PARENT(elm, field);         \
468                        } else {                                        \
469                                if (RB_RIGHT(tmp, field) == NULL ||     \
470                                    RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
471                                        struct type *oleft;             \
472                                        if ((oleft = RB_LEFT(tmp, field)) \
473                                            != NULL)                    \
474                                                RB_COLOR(oleft, field) = RB_BLACK;\
475                                        RB_COLOR(tmp, field) = RB_RED;  \
476                                        RB_ROTATE_RIGHT(head, tmp, oleft, field);\
477                                        tmp = RB_RIGHT(parent, field);  \
478                                }                                       \
479                                RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
480                                RB_COLOR(parent, field) = RB_BLACK;     \
481                                if (RB_RIGHT(tmp, field))               \
482                                        RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
483                                RB_ROTATE_LEFT(head, parent, tmp, field);\
484                                elm = RB_ROOT(head);                    \
485                                break;                                  \
486                        }                                               \
487                } else {                                                \
488                        tmp = RB_LEFT(parent, field);                   \
489                        if (RB_COLOR(tmp, field) == RB_RED) {           \
490                                RB_SET_BLACKRED(tmp, parent, field);    \
491                                RB_ROTATE_RIGHT(head, parent, tmp, field);\
492                                tmp = RB_LEFT(parent, field);           \
493                        }                                               \
494                        if ((RB_LEFT(tmp, field) == NULL ||             \
495                            RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
496                            (RB_RIGHT(tmp, field) == NULL ||            \
497                            RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
498                                RB_COLOR(tmp, field) = RB_RED;          \
499                                elm = parent;                           \
500                                parent = RB_PARENT(elm, field);         \
501                        } else {                                        \
502                                if (RB_LEFT(tmp, field) == NULL ||      \
503                                    RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
504                                        struct type *oright;            \
505                                        if ((oright = RB_RIGHT(tmp, field)) \
506                                            != NULL)                    \
507                                                RB_COLOR(oright, field) = RB_BLACK;\
508                                        RB_COLOR(tmp, field) = RB_RED;  \
509                                        RB_ROTATE_LEFT(head, tmp, oright, field);\
510                                        tmp = RB_LEFT(parent, field);   \
511                                }                                       \
512                                RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
513                                RB_COLOR(parent, field) = RB_BLACK;     \
514                                if (RB_LEFT(tmp, field))                \
515                                        RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
516                                RB_ROTATE_RIGHT(head, parent, tmp, field);\
517                                elm = RB_ROOT(head);                    \
518                                break;                                  \
519                        }                                               \
520                }                                                       \
521        }                                                               \
522        if (elm)                                                        \
523                RB_COLOR(elm, field) = RB_BLACK;                        \
524}                                                                       \
525                                                                        \
526attr struct type *                                                      \
527name##_RB_REMOVE(struct name *head, struct type *elm)                   \
528{                                                                       \
529        struct type *child, *parent, *old = elm;                        \
530        int color;                                                      \
531        if (RB_LEFT(elm, field) == NULL)                                \
532                child = RB_RIGHT(elm, field);                           \
533        else if (RB_RIGHT(elm, field) == NULL)                          \
534                child = RB_LEFT(elm, field);                            \
535        else {                                                          \
536                struct type *left;                                      \
537                elm = RB_RIGHT(elm, field);                             \
538                while ((left = RB_LEFT(elm, field)) != NULL)            \
539                        elm = left;                                     \
540                child = RB_RIGHT(elm, field);                           \
541                parent = RB_PARENT(elm, field);                         \
542                color = RB_COLOR(elm, field);                           \
543                if (child)                                              \
544                        RB_PARENT(child, field) = parent;               \
545                if (parent) {                                           \
546                        if (RB_LEFT(parent, field) == elm)              \
547                                RB_LEFT(parent, field) = child;         \
548                        else                                            \
549                                RB_RIGHT(parent, field) = child;        \
550                        RB_AUGMENT(parent);                             \
551                } else                                                  \
552                        RB_ROOT(head) = child;                          \
553                if (RB_PARENT(elm, field) == old)                       \
554                        parent = elm;                                   \
555                (elm)->field = (old)->field;                            \
556                if (RB_PARENT(old, field)) {                            \
557                        if (RB_LEFT(RB_PARENT(old, field), field) == old)\
558                                RB_LEFT(RB_PARENT(old, field), field) = elm;\
559                        else                                            \
560                                RB_RIGHT(RB_PARENT(old, field), field) = elm;\
561                        RB_AUGMENT(RB_PARENT(old, field));              \
562                } else                                                  \
563                        RB_ROOT(head) = elm;                            \
564                RB_PARENT(RB_LEFT(old, field), field) = elm;            \
565                if (RB_RIGHT(old, field))                               \
566                        RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
567                if (parent) {                                           \
568                        left = parent;                                  \
569                        do {                                            \
570                                RB_AUGMENT(left);                       \
571                        } while ((left = RB_PARENT(left, field)) != NULL); \
572                }                                                       \
573                goto color;                                             \
574        }                                                               \
575        parent = RB_PARENT(elm, field);                                 \
576        color = RB_COLOR(elm, field);                                   \
577        if (child)                                                      \
578                RB_PARENT(child, field) = parent;                       \
579        if (parent) {                                                   \
580                if (RB_LEFT(parent, field) == elm)                      \
581                        RB_LEFT(parent, field) = child;                 \
582                else                                                    \
583                        RB_RIGHT(parent, field) = child;                \
584                RB_AUGMENT(parent);                                     \
585        } else                                                          \
586                RB_ROOT(head) = child;                                  \
587color:                                                                  \
588        if (color == RB_BLACK)                                          \
589                name##_RB_REMOVE_COLOR(head, parent, child);            \
590        return (old);                                                   \
591}                                                                       \
592                                                                        \
593/* Inserts a node into the RB tree */                                   \
594attr struct type *                                                      \
595name##_RB_INSERT(struct name *head, struct type *elm)                   \
596{                                                                       \
597        struct type *tmp;                                               \
598        struct type *parent = NULL;                                     \
599        int comp = 0;                                                   \
600        tmp = RB_ROOT(head);                                            \
601        while (tmp) {                                                   \
602                parent = tmp;                                           \
603                comp = (cmp)(elm, parent);                              \
604                if (comp < 0)                                           \
605                        tmp = RB_LEFT(tmp, field);                      \
606                else if (comp > 0)                                      \
607                        tmp = RB_RIGHT(tmp, field);                     \
608                else                                                    \
609                        return (tmp);                                   \
610        }                                                               \
611        RB_SET(elm, parent, field);                                     \
612        if (parent != NULL) {                                           \
613                if (comp < 0)                                           \
614                        RB_LEFT(parent, field) = elm;                   \
615                else                                                    \
616                        RB_RIGHT(parent, field) = elm;                  \
617                RB_AUGMENT(parent);                                     \
618        } else                                                          \
619                RB_ROOT(head) = elm;                                    \
620        name##_RB_INSERT_COLOR(head, elm);                              \
621        return (NULL);                                                  \
622}                                                                       \
623                                                                        \
624/* Finds the node with the same key as elm */                           \
625attr struct type *                                                      \
626name##_RB_FIND(struct name *head, struct type *elm)                     \
627{                                                                       \
628        struct type *tmp = RB_ROOT(head);                               \
629        int comp;                                                       \
630        while (tmp) {                                                   \
631                comp = cmp(elm, tmp);                                   \
632                if (comp < 0)                                           \
633                        tmp = RB_LEFT(tmp, field);                      \
634                else if (comp > 0)                                      \
635                        tmp = RB_RIGHT(tmp, field);                     \
636                else                                                    \
637                        return (tmp);                                   \
638        }                                                               \
639        return (NULL);                                                  \
640}                                                                       \
641                                                                        \
642/* ARGSUSED */                                                          \
643attr struct type *                                                      \
644name##_RB_NEXT(struct type *elm)                                        \
645{                                                                       \
646        if (RB_RIGHT(elm, field)) {                                     \
647                elm = RB_RIGHT(elm, field);                             \
648                while (RB_LEFT(elm, field))                             \
649                        elm = RB_LEFT(elm, field);                      \
650        } else {                                                        \
651                if (RB_PARENT(elm, field) &&                            \
652                    (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
653                        elm = RB_PARENT(elm, field);                    \
654                else {                                                  \
655                        while (RB_PARENT(elm, field) &&                 \
656                            (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
657                                elm = RB_PARENT(elm, field);            \
658                        elm = RB_PARENT(elm, field);                    \
659                }                                                       \
660        }                                                               \
661        return (elm);                                                   \
662}                                                                       \
663                                                                        \
664attr struct type *                                                      \
665name##_RB_MINMAX(struct name *head, int val)                            \
666{                                                                       \
667        struct type *tmp = RB_ROOT(head);                               \
668        struct type *parent = NULL;                                     \
669        while (tmp) {                                                   \
670                parent = tmp;                                           \
671                if (val < 0)                                            \
672                        tmp = RB_LEFT(tmp, field);                      \
673                else                                                    \
674                        tmp = RB_RIGHT(tmp, field);                     \
675        }                                                               \
676        return (parent);                                                \
677}
678
679#define RB_NEGINF       -1
680#define RB_INF  1
681
682#define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
683#define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
684#define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
685#define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
686#define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
687#define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
688
689#define RB_FOREACH(x, name, head)                                       \
690        for ((x) = RB_MIN(name, head);                                  \
691             (x) != NULL;                                               \
692             (x) = name##_RB_NEXT(x))
693
694#endif  /* _SYS_TREE_H_ */
Note: See TracBrowser for help on using the repository browser.