URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [compat/] [linux/] [current/] [src/] [rbtree.c] - Blame information for rev 825

Go to most recent revision | Details | Compare with Previous | View Log


/*========================================================================
//
//      rbtree.c
//
//      Red Black tree implementation
//
//========================================================================
// ####ECOSGPLCOPYRIGHTBEGIN####
// -------------------------------------------
// This file is part of eCos, the Embedded Configurable Operating System.
// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
//
// eCos is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 or (at your option) any later
// version.
//
// eCos is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License
// along with eCos; if not, write to the Free Software Foundation, Inc.,
// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
//
// As a special exception, if other files instantiate templates or use
// macros or inline functions from this file, or you compile this file
// and link it with other works to produce a work based on this file,
// this file does not by itself cause the resulting work to be covered by
// the GNU General Public License. However the source code for this file
// must still be made available in accordance with section (3) of the GNU
// General Public License v2.
//
// This exception does not invalidate any other reasons why a work based
// on this file might be covered by the GNU General Public License.
// -------------------------------------------
// ####ECOSGPLCOPYRIGHTEND####
//========================================================================
//#####DESCRIPTIONBEGIN####
//
// Author(s):     Niels Provos/OpenBSD
// Contributors:  dwmw2
// Date:          2003-01-21
// Purpose:       This file provides an implementation of red-black trees.
// Description:   Derived from OpenBSD src/sys/sys/tree.h
// Usage:
//
//####DESCRIPTIONEND####
//
//======================================================================
*/
 
/*      $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
/*
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/* Fields renamed to match Linux ones. */
#include <linux/rbtree.h>
 
 
#define RB_HEAD(head)           (head)->rb_node
#define RB_LEFT(elm)            (elm)->rb_left
#define RB_RIGHT(elm)           (elm)->rb_right
#define RB_PARENT(elm)          (elm)->rb_parent
#define RB_COLOR(elm)           (elm)->rb_color
 
 
#define RB_SET(elm, parent) do {                                \
        RB_PARENT(elm) = parent;                                \
        RB_LEFT(elm) = RB_RIGHT(elm) = NULL;    \
        RB_COLOR(elm) = RB_RED;                         \
} while (0)
 
#define RB_SET_BLACKRED(black, red) do {                        \
        RB_COLOR(black) = RB_BLACK;                             \
        RB_COLOR(red) = RB_RED;                                 \
} while (0)
 
#ifndef RB_AUGMENT
#define RB_AUGMENT(x)
#endif
 
#define RB_ROTATE_LEFT(head, elm, tmp) do {                     \
        (tmp) = RB_RIGHT(elm);                                  \
        if ((RB_RIGHT(elm) = RB_LEFT(tmp))) {                   \
                RB_PARENT(RB_LEFT(tmp)) = (elm);                \
        }                                                       \
        RB_AUGMENT(elm);                                        \
        if ((RB_PARENT(tmp) = RB_PARENT(elm))) {                \
                if ((elm) == RB_LEFT(RB_PARENT(elm)))           \
                        RB_LEFT(RB_PARENT(elm)) = (tmp);        \
                else                                            \
                        RB_RIGHT(RB_PARENT(elm)) = (tmp);       \
        } else                                                  \
                (head)->rb_node = (tmp);                        \
        RB_LEFT(tmp) = (elm);                                   \
        RB_PARENT(elm) = (tmp);                                 \
        RB_AUGMENT(tmp);                                        \
        if ((RB_PARENT(tmp)))                                   \
                RB_AUGMENT(RB_PARENT(tmp));                     \
} while (0)
 
#define RB_ROTATE_RIGHT(head, elm, tmp) do {                    \
        (tmp) = RB_LEFT(elm);                                   \
        if ((RB_LEFT(elm) = RB_RIGHT(tmp))) {                   \
                RB_PARENT(RB_RIGHT(tmp)) = (elm);               \
        }                                                       \
        RB_AUGMENT(elm);                                        \
        if ((RB_PARENT(tmp) = RB_PARENT(elm))) {                \
                if ((elm) == RB_LEFT(RB_PARENT(elm)))           \
                        RB_LEFT(RB_PARENT(elm)) = (tmp);        \
                else                                            \
                        RB_RIGHT(RB_PARENT(elm)) = (tmp);       \
        } else                                                  \
                (head)->rb_node = (tmp);                        \
        RB_RIGHT(tmp) = (elm);                                  \
        RB_PARENT(elm) = (tmp);                                 \
        RB_AUGMENT(tmp);                                        \
        if ((RB_PARENT(tmp)))                                   \
                RB_AUGMENT(RB_PARENT(tmp));                     \
} while(0)
 
/* Note args swapped to match Linux */
void rb_insert_color(struct rb_node *elm, struct rb_root *head)
{
        struct rb_node *parent, *gparent, *tmp;
        while ((parent = RB_PARENT(elm)) &&
            RB_COLOR(parent) == RB_RED) {
                gparent = RB_PARENT(parent);
                if (parent == RB_LEFT(gparent)) {
                        tmp = RB_RIGHT(gparent);
                        if (tmp && RB_COLOR(tmp) == RB_RED) {
                                RB_COLOR(tmp) = RB_BLACK;
                                RB_SET_BLACKRED(parent, gparent);
                                elm = gparent;
                                continue;
                        }
                        if (RB_RIGHT(parent) == elm) {
                                RB_ROTATE_LEFT(head, parent, tmp);
                                tmp = parent;
                                parent = elm;
                                elm = tmp;
                        }
                        RB_SET_BLACKRED(parent, gparent);
                        RB_ROTATE_RIGHT(head, gparent, tmp);
                } else {
                        tmp = RB_LEFT(gparent);
                        if (tmp && RB_COLOR(tmp) == RB_RED) {
                                RB_COLOR(tmp) = RB_BLACK;
                                RB_SET_BLACKRED(parent, gparent);
                                elm = gparent;
                                continue;
                        }
                        if (RB_LEFT(parent) == elm) {
                                RB_ROTATE_RIGHT(head, parent, tmp);
                                tmp = parent;
                                parent = elm;
                                elm = tmp;
                        }
                        RB_SET_BLACKRED(parent, gparent);
                        RB_ROTATE_LEFT(head, gparent, tmp);
                }
        }
        RB_COLOR(head->rb_node) = RB_BLACK;
}
 
 
static void rb_remove_color(struct rb_root *head, struct rb_node *parent,
                            struct rb_node *elm)
{
        struct rb_node *tmp;
        while ((elm == NULL || RB_COLOR(elm) == RB_BLACK) &&
            elm != RB_HEAD(head)) {
                if (RB_LEFT(parent) == elm) {
                        tmp = RB_RIGHT(parent);
                        if (RB_COLOR(tmp) == RB_RED) {
                                RB_SET_BLACKRED(tmp, parent);
                                RB_ROTATE_LEFT(head, parent, tmp);
                                tmp = RB_RIGHT(parent);
                        }
                        if ((RB_LEFT(tmp) == NULL ||
                            RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
                            (RB_RIGHT(tmp) == NULL ||
                            RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
                                RB_COLOR(tmp) = RB_RED;
                                elm = parent;
                                parent = RB_PARENT(elm);
                        } else {
                                if (RB_RIGHT(tmp) == NULL ||
                                    RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) {
                                        struct rb_node *oleft;
                                        if ((oleft = RB_LEFT(tmp)))
                                                RB_COLOR(oleft) = RB_BLACK;
                                        RB_COLOR(tmp) = RB_RED;
                                        RB_ROTATE_RIGHT(head, tmp, oleft);
                                        tmp = RB_RIGHT(parent);
                                }
                                RB_COLOR(tmp) = RB_COLOR(parent);
                                RB_COLOR(parent) = RB_BLACK;
                                if (RB_RIGHT(tmp))
                                        RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK;
                                RB_ROTATE_LEFT(head, parent, tmp);
                                elm = RB_HEAD(head);
                                break;
                        }
                } else {
                        tmp = RB_LEFT(parent);
                        if (RB_COLOR(tmp) == RB_RED) {
                                RB_SET_BLACKRED(tmp, parent);
                                RB_ROTATE_RIGHT(head, parent, tmp);
                                tmp = RB_LEFT(parent);
                        }
                        if ((RB_LEFT(tmp) == NULL ||
                            RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
                            (RB_RIGHT(tmp) == NULL ||
                            RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
                                RB_COLOR(tmp) = RB_RED;
                                elm = parent;
                                parent = RB_PARENT(elm);
                        } else {
                                if (RB_LEFT(tmp) == NULL ||
                                    RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) {
                                        struct rb_node *oright;
                                        if ((oright = RB_RIGHT(tmp)))
                                                RB_COLOR(oright) = RB_BLACK;
                                        RB_COLOR(tmp) = RB_RED;
                                        RB_ROTATE_LEFT(head, tmp, oright);
                                        tmp = RB_LEFT(parent);
                                }
                                RB_COLOR(tmp) = RB_COLOR(parent);
                                RB_COLOR(parent) = RB_BLACK;
                                if (RB_LEFT(tmp))
                                        RB_COLOR(RB_LEFT(tmp)) = RB_BLACK;
                                RB_ROTATE_RIGHT(head, parent, tmp);
                                elm = RB_HEAD(head);
                                break;
                        }
                }
        }
        if (elm)
                RB_COLOR(elm) = RB_BLACK;
}
 
/* Note name changed. Guess why :) */
void rb_erase(struct rb_node *elm, struct rb_root *head)
{
        struct rb_node *child, *parent, *old = elm;
        int color;
        if (RB_LEFT(elm) == NULL)
                child = RB_RIGHT(elm);
        else if (RB_RIGHT(elm) == NULL)
                child = RB_LEFT(elm);
        else {
                struct rb_node *left;
                elm = RB_RIGHT(elm);
                while ((left = RB_LEFT(elm)))
                        elm = left;
                child = RB_RIGHT(elm);
                parent = RB_PARENT(elm);
                color = RB_COLOR(elm);
                if (child)
                        RB_PARENT(child) = parent;
                if (parent) {
                        if (RB_LEFT(parent) == elm)
                                RB_LEFT(parent) = child;
                        else
                                RB_RIGHT(parent) = child;
                        RB_AUGMENT(parent);
                } else
                        RB_HEAD(head) = child;
                if (RB_PARENT(elm) == old)
                        parent = elm;
                *(elm) = *(old);
                if (RB_PARENT(old)) {
                        if (RB_LEFT(RB_PARENT(old)) == old)
                                RB_LEFT(RB_PARENT(old)) = elm;
                        else
                                RB_RIGHT(RB_PARENT(old)) = elm;
                        RB_AUGMENT(RB_PARENT(old));
                } else
                        RB_HEAD(head) = elm;
                RB_PARENT(RB_LEFT(old)) = elm;
                if (RB_RIGHT(old))
                        RB_PARENT(RB_RIGHT(old)) = elm;
                if (parent) {
                        left = parent;
                        do {
                                RB_AUGMENT(left);
                        } while ((left = RB_PARENT(left)));
                }
                goto color;
        }
        parent = RB_PARENT(elm);
        color = RB_COLOR(elm);
        if (child)
                RB_PARENT(child) = parent;
        if (parent) {
                if (RB_LEFT(parent) == elm)
                        RB_LEFT(parent) = child;
                else
                        RB_RIGHT(parent) = child;
                RB_AUGMENT(parent);
        } else
                RB_HEAD(head) = child;
color:
        if (color == RB_BLACK)
                rb_remove_color(head, parent, child);
}
 
struct rb_node *rb_next(struct rb_node *elm)
{
        if (RB_RIGHT(elm)) {
                elm = RB_RIGHT(elm);
                while (RB_LEFT(elm))
                        elm = RB_LEFT(elm);
        } else {
                if (RB_PARENT(elm) &&
                    (elm == RB_LEFT(RB_PARENT(elm))))
                        elm = RB_PARENT(elm);
                else {
                        while (RB_PARENT(elm) &&
                            (elm == RB_RIGHT(RB_PARENT(elm))))
                                elm = RB_PARENT(elm);
                        elm = RB_PARENT(elm);
                }
        }
        return (elm);
}
 
struct rb_node *rb_prev(struct rb_node *elm)
{
        if (RB_LEFT(elm)) {
                elm = RB_LEFT(elm);
                while (RB_RIGHT(elm))
                        elm = RB_RIGHT(elm);
        } else {
                if (RB_PARENT(elm) &&
                    (elm == RB_RIGHT(RB_PARENT(elm))))
                        elm = RB_PARENT(elm);
                else {
                        while (RB_PARENT(elm) &&
                            (elm == RB_LEFT(RB_PARENT(elm))))
                                elm = RB_PARENT(elm);
                        elm = RB_PARENT(elm);
                }
        }
        return (elm);
}
 
/* These ones are lifted from Linux -- but that's OK because I
   wrote them. dwmw2. */
struct rb_node *rb_first(struct rb_root *root)
{
        struct rb_node  *n;
 
        n = root->rb_node;
        if (!n)
                return 0;
        while (n->rb_left)
                n = n->rb_left;
        return n;
}
 
void rb_replace_node(struct rb_node *victim, struct rb_node *new,
                     struct rb_root *root)
{
        struct rb_node *parent = victim->rb_parent;
 
        /* Set the surrounding nodes to point to the replacement */
        if (parent) {
                if (victim == parent->rb_left)
                        parent->rb_left = new;
                else
                        parent->rb_right = new;
        } else {
                root->rb_node = new;
        }
        if (victim->rb_left)
                victim->rb_left->rb_parent = new;
        if (victim->rb_right)
                victim->rb_right->rb_parent = new;
 
        /* Copy the pointers/colour from the victim to the replacement */
        *new = *victim;
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [compat/] [linux/] [current/] [src/] [rbtree.c] - Blame information for rev 825

Line No.	Rev	Author	Line
1	786	skrzyp	`/*========================================================================`
2			`//`
3			`// rbtree.c`
4			`//`
5			`// Red Black tree implementation`
6			`//`
7			`//========================================================================`
8			`// ####ECOSGPLCOPYRIGHTBEGIN####`
9			`// -------------------------------------------`
10			`// This file is part of eCos, the Embedded Configurable Operating System.`
11			`// Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.`
12			`//`
13			`// eCos is free software; you can redistribute it and/or modify it under`
14			`// the terms of the GNU General Public License as published by the Free`
15			`// Software Foundation; either version 2 or (at your option) any later`
16			`// version.`
17			`//`
18			`// eCos is distributed in the hope that it will be useful, but WITHOUT`
19			`// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or`
20			`// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License`
21			`// for more details.`
22			`//`
23			`// You should have received a copy of the GNU General Public License`
24			`// along with eCos; if not, write to the Free Software Foundation, Inc.,`
25			`// 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.`
26			`//`
27			`// As a special exception, if other files instantiate templates or use`
28			`// macros or inline functions from this file, or you compile this file`
29			`// and link it with other works to produce a work based on this file,`
30			`// this file does not by itself cause the resulting work to be covered by`
31			`// the GNU General Public License. However the source code for this file`
32			`// must still be made available in accordance with section (3) of the GNU`
33			`// General Public License v2.`
34			`//`
35			`// This exception does not invalidate any other reasons why a work based`
36			`// on this file might be covered by the GNU General Public License.`
37			`// -------------------------------------------`
38			`// ####ECOSGPLCOPYRIGHTEND####`
39			`//========================================================================`
40			`//#####DESCRIPTIONBEGIN####`
41			`//`
42			`// Author(s): Niels Provos/OpenBSD`
43			`// Contributors: dwmw2`
44			`// Date: 2003-01-21`
45			`// Purpose: This file provides an implementation of red-black trees.`
46			`// Description: Derived from OpenBSD src/sys/sys/tree.h`
47			`// Usage:`
48			`//`
49			`//####DESCRIPTIONEND####`
50			`//`
51			`//======================================================================`
52			`*/`
53
54			`/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */`
55			`/*`
56			`* Copyright 2002 Niels Provos <provos@citi.umich.edu>`
57			`* All rights reserved.`
58			`*`
59			`* Redistribution and use in source and binary forms, with or without`
60			`* modification, are permitted provided that the following conditions`
61			`* are met:`
62			`* 1. Redistributions of source code must retain the above copyright`
63			`* notice, this list of conditions and the following disclaimer.`
64			`* 2. Redistributions in binary form must reproduce the above copyright`
65			`* notice, this list of conditions and the following disclaimer in the`
66			`* documentation and/or other materials provided with the distribution.`
67			`*`
68			* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
69			`* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES`
70			`* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.`
71			`* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,`
72			`* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT`
73			`* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,`
74			`* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY`
75			`* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT`
76			`* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF`
77			`* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.`
78			`*/`
79
80			`/* Fields renamed to match Linux ones. */`
81			`#include <linux/rbtree.h>`
82
83
84			`#define RB_HEAD(head) (head)->rb_node`
85			`#define RB_LEFT(elm) (elm)->rb_left`
86			`#define RB_RIGHT(elm) (elm)->rb_right`
87			`#define RB_PARENT(elm) (elm)->rb_parent`
88			`#define RB_COLOR(elm) (elm)->rb_color`
89
90
91			`#define RB_SET(elm, parent) do { \`
92			`RB_PARENT(elm) = parent; \`
93			`RB_LEFT(elm) = RB_RIGHT(elm) = NULL; \`
94			`RB_COLOR(elm) = RB_RED; \`
95			`} while (0)`
96
97			`#define RB_SET_BLACKRED(black, red) do { \`
98			`RB_COLOR(black) = RB_BLACK; \`
99			`RB_COLOR(red) = RB_RED; \`
100			`} while (0)`
101
102			`#ifndef RB_AUGMENT`
103			`#define RB_AUGMENT(x)`
104			`#endif`
105
106			`#define RB_ROTATE_LEFT(head, elm, tmp) do { \`
107			`(tmp) = RB_RIGHT(elm); \`
108			`if ((RB_RIGHT(elm) = RB_LEFT(tmp))) { \`
109			`RB_PARENT(RB_LEFT(tmp)) = (elm); \`
110			`} \`
111			`RB_AUGMENT(elm); \`
112			`if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \`
113			`if ((elm) == RB_LEFT(RB_PARENT(elm))) \`
114			`RB_LEFT(RB_PARENT(elm)) = (tmp); \`
115			`else \`
116			`RB_RIGHT(RB_PARENT(elm)) = (tmp); \`
117			`} else \`
118			`(head)->rb_node = (tmp); \`
119			`RB_LEFT(tmp) = (elm); \`
120			`RB_PARENT(elm) = (tmp); \`
121			`RB_AUGMENT(tmp); \`
122			`if ((RB_PARENT(tmp))) \`
123			`RB_AUGMENT(RB_PARENT(tmp)); \`
124			`} while (0)`
125
126			`#define RB_ROTATE_RIGHT(head, elm, tmp) do { \`
127			`(tmp) = RB_LEFT(elm); \`
128			`if ((RB_LEFT(elm) = RB_RIGHT(tmp))) { \`
129			`RB_PARENT(RB_RIGHT(tmp)) = (elm); \`
130			`} \`
131			`RB_AUGMENT(elm); \`
132			`if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \`
133			`if ((elm) == RB_LEFT(RB_PARENT(elm))) \`
134			`RB_LEFT(RB_PARENT(elm)) = (tmp); \`
135			`else \`
136			`RB_RIGHT(RB_PARENT(elm)) = (tmp); \`
137			`} else \`
138			`(head)->rb_node = (tmp); \`
139			`RB_RIGHT(tmp) = (elm); \`
140			`RB_PARENT(elm) = (tmp); \`
141			`RB_AUGMENT(tmp); \`
142			`if ((RB_PARENT(tmp))) \`
143			`RB_AUGMENT(RB_PARENT(tmp)); \`
144			`} while(0)`
145
146			`/* Note args swapped to match Linux */`
147			`void rb_insert_color(struct rb_node elm, struct rb_root head)`
148			`{`
149			`struct rb_node parent, gparent, *tmp;`
150			`while ((parent = RB_PARENT(elm)) &&`
151			`RB_COLOR(parent) == RB_RED) {`
152			`gparent = RB_PARENT(parent);`
153			`if (parent == RB_LEFT(gparent)) {`
154			`tmp = RB_RIGHT(gparent);`
155			`if (tmp && RB_COLOR(tmp) == RB_RED) {`
156			`RB_COLOR(tmp) = RB_BLACK;`
157			`RB_SET_BLACKRED(parent, gparent);`
158			`elm = gparent;`
159			`continue;`
160			`}`
161			`if (RB_RIGHT(parent) == elm) {`
162			`RB_ROTATE_LEFT(head, parent, tmp);`
163			`tmp = parent;`
164			`parent = elm;`
165			`elm = tmp;`
166			`}`
167			`RB_SET_BLACKRED(parent, gparent);`
168			`RB_ROTATE_RIGHT(head, gparent, tmp);`
169			`} else {`
170			`tmp = RB_LEFT(gparent);`
171			`if (tmp && RB_COLOR(tmp) == RB_RED) {`
172			`RB_COLOR(tmp) = RB_BLACK;`
173			`RB_SET_BLACKRED(parent, gparent);`
174			`elm = gparent;`
175			`continue;`
176			`}`
177			`if (RB_LEFT(parent) == elm) {`
178			`RB_ROTATE_RIGHT(head, parent, tmp);`
179			`tmp = parent;`
180			`parent = elm;`
181			`elm = tmp;`
182			`}`
183			`RB_SET_BLACKRED(parent, gparent);`
184			`RB_ROTATE_LEFT(head, gparent, tmp);`
185			`}`
186			`}`
187			`RB_COLOR(head->rb_node) = RB_BLACK;`
188			`}`
189
190
191			`static void rb_remove_color(struct rb_root head, struct rb_node parent,`
192			`struct rb_node *elm)`
193			`{`
194			`struct rb_node *tmp;`
195			`while ((elm == NULL \|\| RB_COLOR(elm) == RB_BLACK) &&`
196			`elm != RB_HEAD(head)) {`
197			`if (RB_LEFT(parent) == elm) {`
198			`tmp = RB_RIGHT(parent);`
199			`if (RB_COLOR(tmp) == RB_RED) {`
200			`RB_SET_BLACKRED(tmp, parent);`
201			`RB_ROTATE_LEFT(head, parent, tmp);`
202			`tmp = RB_RIGHT(parent);`
203			`}`
204			`if ((RB_LEFT(tmp) == NULL \|\|`
205			`RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&`
206			`(RB_RIGHT(tmp) == NULL \|\|`
207			`RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {`
208			`RB_COLOR(tmp) = RB_RED;`
209			`elm = parent;`
210			`parent = RB_PARENT(elm);`
211			`} else {`
212			`if (RB_RIGHT(tmp) == NULL \|\|`
213			`RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) {`
214			`struct rb_node *oleft;`
215			`if ((oleft = RB_LEFT(tmp)))`
216			`RB_COLOR(oleft) = RB_BLACK;`
217			`RB_COLOR(tmp) = RB_RED;`
218			`RB_ROTATE_RIGHT(head, tmp, oleft);`
219			`tmp = RB_RIGHT(parent);`
220			`}`
221			`RB_COLOR(tmp) = RB_COLOR(parent);`
222			`RB_COLOR(parent) = RB_BLACK;`
223			`if (RB_RIGHT(tmp))`
224			`RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK;`
225			`RB_ROTATE_LEFT(head, parent, tmp);`
226			`elm = RB_HEAD(head);`
227			`break;`
228			`}`
229			`} else {`
230			`tmp = RB_LEFT(parent);`
231			`if (RB_COLOR(tmp) == RB_RED) {`
232			`RB_SET_BLACKRED(tmp, parent);`
233			`RB_ROTATE_RIGHT(head, parent, tmp);`
234			`tmp = RB_LEFT(parent);`
235			`}`
236			`if ((RB_LEFT(tmp) == NULL \|\|`
237			`RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&`
238			`(RB_RIGHT(tmp) == NULL \|\|`
239			`RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {`
240			`RB_COLOR(tmp) = RB_RED;`
241			`elm = parent;`
242			`parent = RB_PARENT(elm);`
243			`} else {`
244			`if (RB_LEFT(tmp) == NULL \|\|`
245			`RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) {`
246			`struct rb_node *oright;`
247			`if ((oright = RB_RIGHT(tmp)))`
248			`RB_COLOR(oright) = RB_BLACK;`
249			`RB_COLOR(tmp) = RB_RED;`
250			`RB_ROTATE_LEFT(head, tmp, oright);`
251			`tmp = RB_LEFT(parent);`
252			`}`
253			`RB_COLOR(tmp) = RB_COLOR(parent);`
254			`RB_COLOR(parent) = RB_BLACK;`
255			`if (RB_LEFT(tmp))`
256			`RB_COLOR(RB_LEFT(tmp)) = RB_BLACK;`
257			`RB_ROTATE_RIGHT(head, parent, tmp);`
258			`elm = RB_HEAD(head);`
259			`break;`
260			`}`
261			`}`
262			`}`
263			`if (elm)`
264			`RB_COLOR(elm) = RB_BLACK;`
265			`}`
266
267			`/* Note name changed. Guess why :) */`
268			`void rb_erase(struct rb_node elm, struct rb_root head)`
269			`{`
270			`struct rb_node child, parent, *old = elm;`
271			`int color;`
272			`if (RB_LEFT(elm) == NULL)`
273			`child = RB_RIGHT(elm);`
274			`else if (RB_RIGHT(elm) == NULL)`
275			`child = RB_LEFT(elm);`
276			`else {`
277			`struct rb_node *left;`
278			`elm = RB_RIGHT(elm);`
279			`while ((left = RB_LEFT(elm)))`
280			`elm = left;`
281			`child = RB_RIGHT(elm);`
282			`parent = RB_PARENT(elm);`
283			`color = RB_COLOR(elm);`
284			`if (child)`
285			`RB_PARENT(child) = parent;`
286			`if (parent) {`
287			`if (RB_LEFT(parent) == elm)`
288			`RB_LEFT(parent) = child;`
289			`else`
290			`RB_RIGHT(parent) = child;`
291			`RB_AUGMENT(parent);`
292			`} else`
293			`RB_HEAD(head) = child;`
294			`if (RB_PARENT(elm) == old)`
295			`parent = elm;`
296			`(elm) = (old);`
297			`if (RB_PARENT(old)) {`
298			`if (RB_LEFT(RB_PARENT(old)) == old)`
299			`RB_LEFT(RB_PARENT(old)) = elm;`
300			`else`
301			`RB_RIGHT(RB_PARENT(old)) = elm;`
302			`RB_AUGMENT(RB_PARENT(old));`
303			`} else`
304			`RB_HEAD(head) = elm;`
305			`RB_PARENT(RB_LEFT(old)) = elm;`
306			`if (RB_RIGHT(old))`
307			`RB_PARENT(RB_RIGHT(old)) = elm;`
308			`if (parent) {`
309			`left = parent;`
310			`do {`
311			`RB_AUGMENT(left);`
312			`} while ((left = RB_PARENT(left)));`
313			`}`
314			`goto color;`
315			`}`
316			`parent = RB_PARENT(elm);`
317			`color = RB_COLOR(elm);`
318			`if (child)`
319			`RB_PARENT(child) = parent;`
320			`if (parent) {`
321			`if (RB_LEFT(parent) == elm)`
322			`RB_LEFT(parent) = child;`
323			`else`
324			`RB_RIGHT(parent) = child;`
325			`RB_AUGMENT(parent);`
326			`} else`
327			`RB_HEAD(head) = child;`
328			`color:`
329			`if (color == RB_BLACK)`
330			`rb_remove_color(head, parent, child);`
331			`}`
332
333			`struct rb_node rb_next(struct rb_node elm)`
334			`{`
335			`if (RB_RIGHT(elm)) {`
336			`elm = RB_RIGHT(elm);`
337			`while (RB_LEFT(elm))`
338			`elm = RB_LEFT(elm);`
339			`} else {`
340			`if (RB_PARENT(elm) &&`
341			`(elm == RB_LEFT(RB_PARENT(elm))))`
342			`elm = RB_PARENT(elm);`
343			`else {`
344			`while (RB_PARENT(elm) &&`
345			`(elm == RB_RIGHT(RB_PARENT(elm))))`
346			`elm = RB_PARENT(elm);`
347			`elm = RB_PARENT(elm);`
348			`}`
349			`}`
350			`return (elm);`
351			`}`
352
353			`struct rb_node rb_prev(struct rb_node elm)`
354			`{`
355			`if (RB_LEFT(elm)) {`
356			`elm = RB_LEFT(elm);`
357			`while (RB_RIGHT(elm))`
358			`elm = RB_RIGHT(elm);`
359			`} else {`
360			`if (RB_PARENT(elm) &&`
361			`(elm == RB_RIGHT(RB_PARENT(elm))))`
362			`elm = RB_PARENT(elm);`
363			`else {`
364			`while (RB_PARENT(elm) &&`
365			`(elm == RB_LEFT(RB_PARENT(elm))))`
366			`elm = RB_PARENT(elm);`
367			`elm = RB_PARENT(elm);`
368			`}`
369			`}`
370			`return (elm);`
371			`}`
372
373			`/* These ones are lifted from Linux -- but that's OK because I`
374			`wrote them. dwmw2. */`
375			`struct rb_node rb_first(struct rb_root root)`
376			`{`
377			`struct rb_node *n;`
378
379			`n = root->rb_node;`
380			`if (!n)`
381			`return 0;`
382			`while (n->rb_left)`
383			`n = n->rb_left;`
384			`return n;`
385			`}`
386
387			`void rb_replace_node(struct rb_node victim, struct rb_node new,`
388			`struct rb_root *root)`
389			`{`
390			`struct rb_node *parent = victim->rb_parent;`
391
392			`/* Set the surrounding nodes to point to the replacement */`
393			`if (parent) {`
394			`if (victim == parent->rb_left)`
395			`parent->rb_left = new;`
396			`else`
397			`parent->rb_right = new;`
398			`} else {`
399			`root->rb_node = new;`
400			`}`
401			`if (victim->rb_left)`
402			`victim->rb_left->rb_parent = new;`
403			`if (victim->rb_right)`
404			`victim->rb_right->rb_parent = new;`
405
406			`/* Copy the pointers/colour from the victim to the replacement */`
407			`new = victim;`
408			`}`