Mercurial > ecos-v2_0-branch

annotate packages/compat/linux/current/src/rbtree.c @ 823:19a153ac403c default tip

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