Mercurial > ecos-v3_0-branch

annotate packages/compat/linux/current/src/rbtree.c @ 2729:74dbf4c3f2e1 after-copyright-change-20090129

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update all copyright banners to reflect FSF ownership; fix and improve licence text.
author jlarmour
date Thu, 29 Jan 2009 17:47:46 +0000
parents cfe81e17269a
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 //========================================================================
2729
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
8 // ####ECOSGPLCOPYRIGHTBEGIN####
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
9 // -------------------------------------------
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
10 // This file is part of eCos, the Embedded Configurable Operating System.
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
11 // Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
522
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
12 //
2729
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
13 // eCos is free software; you can redistribute it and/or modify it under
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
14 // the terms of the GNU General Public License as published by the Free
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
15 // Software Foundation; either version 2 or (at your option) any later
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
16 // version.
522
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
17 //
2729
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
18 // eCos is distributed in the hope that it will be useful, but WITHOUT
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
19 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
20 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
21 // for more details.
522
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
22 //
2729
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
23 // You should have received a copy of the GNU General Public License
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
24 // along with eCos; if not, write to the Free Software Foundation, Inc.,
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
25 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
522
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
26 //
2729
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
27 // As a special exception, if other files instantiate templates or use
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
28 // macros or inline functions from this file, or you compile this file
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
29 // and link it with other works to produce a work based on this file,
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
30 // this file does not by itself cause the resulting work to be covered by
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
31 // the GNU General Public License. However the source code for this file
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
32 // must still be made available in accordance with section (3) of the GNU
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
33 // General Public License v2.
522
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
34 //
2729
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
35 // This exception does not invalidate any other reasons why a work based
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
36 // on this file might be covered by the GNU General Public License.
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
37 // -------------------------------------------
74dbf4c3f2e1 Update all copyright banners to reflect FSF ownership; fix and improve licence text.
jlarmour
parents: 1320
diff changeset
38 // ####ECOSGPLCOPYRIGHTEND####
522
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
39 //========================================================================
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
40 //#####DESCRIPTIONBEGIN####
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
41 //
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
42 // Author(s): Niels Provos/OpenBSD
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
43 // Contributors: dwmw2
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
44 // Date: 2003-01-21
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
45 // 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
46 // Description: Derived from OpenBSD src/sys/sys/tree.h
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
47 // Usage:
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
48 //
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
49 //####DESCRIPTIONEND####
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
50 //
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 /* $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
55 /*
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
56 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
57 * All rights reserved.
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
58 *
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
59 * 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
60 * modification, are permitted provided that the following conditions
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
61 * are met:
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
62 * 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
63 * notice, this list of conditions and the following disclaimer.
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
64 * 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
65 * 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
66 * documentation and/or other materials provided with the distribution.
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
67 *
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
68 * 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
69 * 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
70 * 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
71 * 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
72 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
73 * 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
74 * 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
75 * 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
76 * (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
77 * 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
78 */
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 /* Fields renamed to match Linux ones. */
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
81 #include <linux/rbtree.h>
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
82
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 #define RB_HEAD(head) (head)->rb_node
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
85 #define RB_LEFT(elm) (elm)->rb_left
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
86 #define RB_RIGHT(elm) (elm)->rb_right
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
87 #define RB_PARENT(elm) (elm)->rb_parent
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
88 #define RB_COLOR(elm) (elm)->rb_color
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
89
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 #define RB_SET(elm, parent) do { \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
92 RB_PARENT(elm) = parent; \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
93 RB_LEFT(elm) = RB_RIGHT(elm) = NULL; \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
94 RB_COLOR(elm) = RB_RED; \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
95 } while (0)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
96
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
97 #define RB_SET_BLACKRED(black, red) do { \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
98 RB_COLOR(black) = RB_BLACK; \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
99 RB_COLOR(red) = RB_RED; \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
100 } while (0)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
101
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
102 #ifndef RB_AUGMENT
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
103 #define RB_AUGMENT(x)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
104 #endif
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
105
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
106 #define RB_ROTATE_LEFT(head, elm, tmp) do { \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
107 (tmp) = RB_RIGHT(elm); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
108 if ((RB_RIGHT(elm) = RB_LEFT(tmp))) { \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
109 RB_PARENT(RB_LEFT(tmp)) = (elm); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
110 } \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
111 RB_AUGMENT(elm); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
112 if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
113 if ((elm) == RB_LEFT(RB_PARENT(elm))) \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
114 RB_LEFT(RB_PARENT(elm)) = (tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
115 else \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
116 RB_RIGHT(RB_PARENT(elm)) = (tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
117 } else \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
118 (head)->rb_node = (tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
119 RB_LEFT(tmp) = (elm); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
120 RB_PARENT(elm) = (tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
121 RB_AUGMENT(tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
122 if ((RB_PARENT(tmp))) \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
123 RB_AUGMENT(RB_PARENT(tmp)); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
124 } while (0)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
125
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
126 #define RB_ROTATE_RIGHT(head, elm, tmp) do { \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
127 (tmp) = RB_LEFT(elm); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
128 if ((RB_LEFT(elm) = RB_RIGHT(tmp))) { \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
129 RB_PARENT(RB_RIGHT(tmp)) = (elm); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
130 } \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
131 RB_AUGMENT(elm); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
132 if ((RB_PARENT(tmp) = RB_PARENT(elm))) { \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
133 if ((elm) == RB_LEFT(RB_PARENT(elm))) \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
134 RB_LEFT(RB_PARENT(elm)) = (tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
135 else \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
136 RB_RIGHT(RB_PARENT(elm)) = (tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
137 } else \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
138 (head)->rb_node = (tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
139 RB_RIGHT(tmp) = (elm); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
140 RB_PARENT(elm) = (tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
141 RB_AUGMENT(tmp); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
142 if ((RB_PARENT(tmp))) \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
143 RB_AUGMENT(RB_PARENT(tmp)); \
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
144 } while(0)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
145
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
146 /* Note args swapped to match Linux */
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
147 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
148 {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
149 struct rb_node *parent, *gparent, *tmp;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
150 while ((parent = RB_PARENT(elm)) &&
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
151 RB_COLOR(parent) == RB_RED) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
152 gparent = RB_PARENT(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
153 if (parent == RB_LEFT(gparent)) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
154 tmp = RB_RIGHT(gparent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
155 if (tmp && RB_COLOR(tmp) == RB_RED) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
156 RB_COLOR(tmp) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
157 RB_SET_BLACKRED(parent, gparent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
158 elm = gparent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
159 continue;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
160 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
161 if (RB_RIGHT(parent) == elm) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
162 RB_ROTATE_LEFT(head, parent, tmp);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
163 tmp = parent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
164 parent = elm;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
165 elm = tmp;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
166 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
167 RB_SET_BLACKRED(parent, gparent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
168 RB_ROTATE_RIGHT(head, gparent, tmp);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
169 } else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
170 tmp = RB_LEFT(gparent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
171 if (tmp && RB_COLOR(tmp) == RB_RED) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
172 RB_COLOR(tmp) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
173 RB_SET_BLACKRED(parent, gparent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
174 elm = gparent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
175 continue;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
176 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
177 if (RB_LEFT(parent) == elm) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
178 RB_ROTATE_RIGHT(head, parent, tmp);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
179 tmp = parent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
180 parent = elm;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
181 elm = tmp;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
182 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
183 RB_SET_BLACKRED(parent, gparent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
184 RB_ROTATE_LEFT(head, gparent, tmp);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
185 }
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 RB_COLOR(head->rb_node) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
188 }
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 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
192 struct rb_node *elm)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
193 {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
194 struct rb_node *tmp;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
195 while ((elm == NULL || RB_COLOR(elm) == RB_BLACK) &&
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
196 elm != RB_HEAD(head)) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
197 if (RB_LEFT(parent) == elm) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
198 tmp = RB_RIGHT(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
199 if (RB_COLOR(tmp) == RB_RED) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
200 RB_SET_BLACKRED(tmp, parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
201 RB_ROTATE_LEFT(head, parent, tmp);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
202 tmp = RB_RIGHT(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
203 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
204 if ((RB_LEFT(tmp) == NULL ||
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
205 RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
206 (RB_RIGHT(tmp) == NULL ||
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
207 RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
208 RB_COLOR(tmp) = RB_RED;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
209 elm = parent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
210 parent = RB_PARENT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
211 } else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
212 if (RB_RIGHT(tmp) == NULL ||
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
213 RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
214 struct rb_node *oleft;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
215 if ((oleft = RB_LEFT(tmp)))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
216 RB_COLOR(oleft) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
217 RB_COLOR(tmp) = RB_RED;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
218 RB_ROTATE_RIGHT(head, tmp, oleft);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
219 tmp = RB_RIGHT(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
220 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
221 RB_COLOR(tmp) = RB_COLOR(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
222 RB_COLOR(parent) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
223 if (RB_RIGHT(tmp))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
224 RB_COLOR(RB_RIGHT(tmp)) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
225 RB_ROTATE_LEFT(head, parent, tmp);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
226 elm = RB_HEAD(head);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
227 break;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
228 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
229 } else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
230 tmp = RB_LEFT(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
231 if (RB_COLOR(tmp) == RB_RED) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
232 RB_SET_BLACKRED(tmp, parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
233 RB_ROTATE_RIGHT(head, parent, tmp);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
234 tmp = RB_LEFT(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
235 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
236 if ((RB_LEFT(tmp) == NULL ||
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
237 RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) &&
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
238 (RB_RIGHT(tmp) == NULL ||
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
239 RB_COLOR(RB_RIGHT(tmp)) == RB_BLACK)) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
240 RB_COLOR(tmp) = RB_RED;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
241 elm = parent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
242 parent = RB_PARENT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
243 } else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
244 if (RB_LEFT(tmp) == NULL ||
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
245 RB_COLOR(RB_LEFT(tmp)) == RB_BLACK) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
246 struct rb_node *oright;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
247 if ((oright = RB_RIGHT(tmp)))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
248 RB_COLOR(oright) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
249 RB_COLOR(tmp) = RB_RED;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
250 RB_ROTATE_LEFT(head, tmp, oright);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
251 tmp = RB_LEFT(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
252 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
253 RB_COLOR(tmp) = RB_COLOR(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
254 RB_COLOR(parent) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
255 if (RB_LEFT(tmp))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
256 RB_COLOR(RB_LEFT(tmp)) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
257 RB_ROTATE_RIGHT(head, parent, tmp);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
258 elm = RB_HEAD(head);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
259 break;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
260 }
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 if (elm)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
264 RB_COLOR(elm) = RB_BLACK;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
265 }
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 /* Note name changed. Guess why :) */
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
268 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
269 {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
270 struct rb_node *child, *parent, *old = elm;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
271 int color;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
272 if (RB_LEFT(elm) == NULL)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
273 child = RB_RIGHT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
274 else if (RB_RIGHT(elm) == NULL)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
275 child = RB_LEFT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
276 else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
277 struct rb_node *left;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
278 elm = RB_RIGHT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
279 while ((left = RB_LEFT(elm)))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
280 elm = left;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
281 child = RB_RIGHT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
282 parent = RB_PARENT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
283 color = RB_COLOR(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
284 if (child)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
285 RB_PARENT(child) = parent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
286 if (parent) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
287 if (RB_LEFT(parent) == elm)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
288 RB_LEFT(parent) = child;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
289 else
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
290 RB_RIGHT(parent) = child;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
291 RB_AUGMENT(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
292 } else
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
293 RB_HEAD(head) = child;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
294 if (RB_PARENT(elm) == old)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
295 parent = elm;
1320
cfe81e17269a Fix some bugs in red-black tree implementation
gthomas
parents: 522
diff changeset
296 *(elm) = *(old);
522
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
297 if (RB_PARENT(old)) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
298 if (RB_LEFT(RB_PARENT(old)) == old)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
299 RB_LEFT(RB_PARENT(old)) = elm;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
300 else
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
301 RB_RIGHT(RB_PARENT(old)) = elm;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
302 RB_AUGMENT(RB_PARENT(old));
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
303 } else
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
304 RB_HEAD(head) = elm;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
305 RB_PARENT(RB_LEFT(old)) = elm;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
306 if (RB_RIGHT(old))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
307 RB_PARENT(RB_RIGHT(old)) = elm;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
308 if (parent) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
309 left = parent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
310 do {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
311 RB_AUGMENT(left);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
312 } while ((left = RB_PARENT(left)));
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
313 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
314 goto color;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
315 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
316 parent = RB_PARENT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
317 color = RB_COLOR(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
318 if (child)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
319 RB_PARENT(child) = parent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
320 if (parent) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
321 if (RB_LEFT(parent) == elm)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
322 RB_LEFT(parent) = child;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
323 else
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
324 RB_RIGHT(parent) = child;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
325 RB_AUGMENT(parent);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
326 } else
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
327 RB_HEAD(head) = child;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
328 color:
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
329 if (color == RB_BLACK)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
330 rb_remove_color(head, parent, child);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
331 }
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 struct rb_node *rb_next(struct rb_node *elm)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
334 {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
335 if (RB_RIGHT(elm)) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
336 elm = RB_RIGHT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
337 while (RB_LEFT(elm))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
338 elm = RB_LEFT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
339 } else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
340 if (RB_PARENT(elm) &&
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
341 (elm == RB_LEFT(RB_PARENT(elm))))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
342 elm = RB_PARENT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
343 else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
344 while (RB_PARENT(elm) &&
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
345 (elm == RB_RIGHT(RB_PARENT(elm))))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
346 elm = 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 }
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 return (elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
351 }
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 struct rb_node *rb_prev(struct rb_node *elm)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
354 {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
355 if (RB_LEFT(elm)) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
356 elm = RB_LEFT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
357 while (RB_RIGHT(elm))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
358 elm = RB_RIGHT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
359 } else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
360 if (RB_PARENT(elm) &&
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
361 (elm == RB_RIGHT(RB_PARENT(elm))))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
362 elm = RB_PARENT(elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
363 else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
364 while (RB_PARENT(elm) &&
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
365 (elm == RB_LEFT(RB_PARENT(elm))))
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
366 elm = 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 }
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 return (elm);
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
371 }
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 /* 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
374 wrote them. dwmw2. */
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
375 struct rb_node *rb_first(struct rb_root *root)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
376 {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
377 struct rb_node *n;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
378
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
379 n = root->rb_node;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
380 if (!n)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
381 return 0;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
382 while (n->rb_left)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
383 n = n->rb_left;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
384 return n;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
385 }
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 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
388 struct rb_root *root)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
389 {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
390 struct rb_node *parent = victim->rb_parent;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
391
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
392 /* Set the surrounding nodes to point to the replacement */
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
393 if (parent) {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
394 if (victim == parent->rb_left)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
395 parent->rb_left = new;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
396 else
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
397 parent->rb_right = new;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
398 } else {
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
399 root->rb_node = new;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
400 }
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
401 if (victim->rb_left)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
402 victim->rb_left->rb_parent = new;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
403 if (victim->rb_right)
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
404 victim->rb_right->rb_parent = new;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
405
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
406 /* 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
407 *new = *victim;
726ecf119e30 Add new Linux kernel compatibility package. Not a compatibility layer
jlarmour
parents:
diff changeset
408 }