URL https://opencores.org/ocsvn/openrisc_2011-10-31/openrisc_2011-10-31/trunk

Subversion Repositories openrisc_2011-10-31

[/] [openrisc/] [trunk/] [rtos/] [ecos-2.0/] [packages/] [compat/] [linux/] [v2_0/] [src/] [rbtree.c] - Blame information for rev 174

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 Red Hat, 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.,
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 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.
//
// This exception does not invalidate any other reasons why a work based on
// this file might be covered by the GNU General Public License.
//
// Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
// at http://sources.redhat.com/ecos/ecos-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_2011-10-31

[/] [openrisc/] [trunk/] [rtos/] [ecos-2.0/] [packages/] [compat/] [linux/] [v2_0/] [src/] [rbtree.c] - Blame information for rev 174

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