1 | /******************************************************************************␊ |
2 | *␊ |
3 | * Copyright (C) 2008 Jason Evans <jasone@FreeBSD.org>.␊ |
4 | * Copyright (c) 2008-2012 Hewlett-Packard Development Company, L.P.␊ |
5 | * All rights reserved.␊ |
6 | *␊ |
7 | * Redistribution and use in source and binary forms, with or without␊ |
8 | * modification, are permitted provided that the following conditions␊ |
9 | * are met:␊ |
10 | * 1. Redistributions of source code must retain the above copyright␊ |
11 | * notice(s), this list of conditions and the following disclaimer␊ |
12 | * unmodified other than the allowable addition of one or more␊ |
13 | * copyright notices.␊ |
14 | * 2. Redistributions in binary form must reproduce the above copyright␊ |
15 | * notice(s), this list of conditions and the following disclaimer in␊ |
16 | * the documentation and/or other materials provided with the␊ |
17 | * distribution.␊ |
18 | *␊ |
19 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY␊ |
20 | * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE␊ |
21 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR␊ |
22 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE␊ |
23 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR␊ |
24 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF␊ |
25 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR␊ |
26 | * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,␊ |
27 | * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE␊ |
28 | * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,␊ |
29 | * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.␊ |
30 | *␊ |
31 | ******************************************************************************␊ |
32 | *␊ |
33 | * cpp macro implementation of left-leaning red-black trees.␊ |
34 | *␊ |
35 | * Usage:␊ |
36 | *␊ |
37 | * (Optional, see assert(3).)␊ |
38 | * #define NDEBUG␊ |
39 | *␊ |
40 | * (Required.)␊ |
41 | * #include <assert.h>␊ |
42 | * #include <rb.h>␊ |
43 | * ...␊ |
44 | *␊ |
45 | * All operations are done non-recursively. Parent pointers are not used, and␊ |
46 | * color bits are stored in the least significant bit of right-child pointers,␊ |
47 | * thus making node linkage as compact as is possible for red-black trees.␊ |
48 | *␊ |
49 | * Some macros use a comparison function pointer, which is expected to have the␊ |
50 | * following prototype:␊ |
51 | *␊ |
52 | * int (a_cmp *)(a_type *a_node, a_type *a_other);␊ |
53 | * ^^^^^^␊ |
54 | * or a_key␊ |
55 | *␊ |
56 | * Interpretation of comparision function return values:␊ |
57 | *␊ |
58 | * -1 : a_node < a_other␊ |
59 | * 0 : a_node == a_other␊ |
60 | * 1 : a_node > a_other␊ |
61 | *␊ |
62 | * In all cases, the a_node or a_key macro argument is the first argument to the␊ |
63 | * comparison function, which makes it possible to write comparison functions␊ |
64 | * that treat the first argument specially.␊ |
65 | *␊ |
66 | ******************************************************************************/␊ |
67 | ␊ |
68 | #ifndef RB_H_␊ |
69 | #define␉RB_H_␊ |
70 | ␊ |
71 | //__FBSDID("$FreeBSD: head/lib/libc/stdlib/rb.h 178995 2008-05-14 18:33:13Z jasone $");␊ |
72 | ␊ |
73 | /* Node structure. */␊ |
74 | #define␉rb_node(a_type)␉␉␉␉␉␉␉\␊ |
75 | struct {␉␉␉␉␉␉␉␉\␊ |
76 | a_type *rbn_left;␉␉␉␉␉␉␉\␊ |
77 | a_type *rbn_right_red;␉␉␉␉␉␉\␊ |
78 | }␊ |
79 | ␊ |
80 | /* Root structure. */␊ |
81 | #define␉rb_tree(a_type)␉␉␉␉␉␉␉\␊ |
82 | struct {␉␉␉␉␉␉␉␉\␊ |
83 | a_type *rbt_root;␉␉␉␉␉␉␉\␊ |
84 | a_type rbt_nil;␉␉␉␉␉␉␉\␊ |
85 | }␊ |
86 | ␊ |
87 | /* Left accessors. */␊ |
88 | #define␉rbp_left_get(a_type, a_field, a_node)␉␉␉␉\␊ |
89 | ((a_node)->a_field.rbn_left)␊ |
90 | #define␉rbp_left_set(a_type, a_field, a_node, a_left) do {␉␉\␊ |
91 | (a_node)->a_field.rbn_left = a_left;␉␉␉␉\␊ |
92 | } while (0)␊ |
93 | ␊ |
94 | /* Right accessors. */␊ |
95 | #define␉rbp_right_get(a_type, a_field, a_node)␉␉␉␉\␊ |
96 | ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red)␉␉\␊ |
97 | & ((ssize_t)-2)))␊ |
98 | #define␉rbp_right_set(a_type, a_field, a_node, a_right) do {␉␉\␊ |
99 | (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right)␉\␊ |
100 | | (((uintptr_t) (a_node)->a_field.rbn_right_red) & ((size_t)1)));␉\␊ |
101 | } while (0)␊ |
102 | ␊ |
103 | /* Color accessors. */␊ |
104 | #define␉rbp_red_get(a_type, a_field, a_node)␉␉␉␉\␊ |
105 | ((bool) (((uintptr_t) (a_node)->a_field.rbn_right_red)␉␉\␊ |
106 | & ((size_t)1)))␊ |
107 | #define␉rbp_color_set(a_type, a_field, a_node, a_red) do {␉␉\␊ |
108 | (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t)␉␉\␊ |
109 | (a_node)->a_field.rbn_right_red) & ((ssize_t)-2))␉␉␉\␊ |
110 | | ((ssize_t)a_red));␉␉␉␉␉␉\␊ |
111 | } while (0)␊ |
112 | #define␉rbp_red_set(a_type, a_field, a_node) do {␉␉␉\␊ |
113 | (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t)␉␉\␊ |
114 | (a_node)->a_field.rbn_right_red) | ((size_t)1));␉␉␉\␊ |
115 | } while (0)␊ |
116 | #define␉rbp_black_set(a_type, a_field, a_node) do {␉␉␉\␊ |
117 | (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t)␉␉\␊ |
118 | (a_node)->a_field.rbn_right_red) & ((ssize_t)-2));␉␉\␊ |
119 | } while (0)␊ |
120 | ␊ |
121 | /* Node initializer. */␊ |
122 | #define␉rbp_node_new(a_type, a_field, a_tree, a_node) do {␉␉\␊ |
123 | rbp_left_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);␉\␊ |
124 | rbp_right_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil);␉\␊ |
125 | rbp_red_set(a_type, a_field, (a_node));␉␉␉␉\␊ |
126 | } while (0)␊ |
127 | ␊ |
128 | /* Tree initializer. */␊ |
129 | #define␉rb_new(a_type, a_field, a_tree) do {␉␉␉␉\␊ |
130 | (a_tree)->rbt_root = &(a_tree)->rbt_nil;␉␉␉␉\␊ |
131 | rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil);␉␉\␊ |
132 | rbp_black_set(a_type, a_field, &(a_tree)->rbt_nil);␉␉␉\␊ |
133 | } while (0)␊ |
134 | ␊ |
135 | /* Tree operations. */␊ |
136 | #define␉rbp_black_height(a_type, a_field, a_tree, r_height) do {␉\␊ |
137 | a_type *rbp_bh_t;␉␉␉␉␉␉␉\␊ |
138 | for (rbp_bh_t = (a_tree)->rbt_root, (r_height) = 0;␉␉␉\␊ |
139 | rbp_bh_t != &(a_tree)->rbt_nil;␉␉␉␉␉\␊ |
140 | rbp_bh_t = rbp_left_get(a_type, a_field, rbp_bh_t)) {␉␉\␊ |
141 | if (rbp_red_get(a_type, a_field, rbp_bh_t) == false) {␉␉\␊ |
142 | (r_height)++;␉␉␉␉␉␉\␊ |
143 | }␉␉␉␉␉␉␉␉\␊ |
144 | }␉␉␉␉␉␉␉␉␉\␊ |
145 | } while (0)␊ |
146 | ␊ |
147 | #define␉rbp_first(a_type, a_field, a_tree, a_root, r_node) do {␉␉\␊ |
148 | for ((r_node) = (a_root);␉␉␉␉␉␉\␊ |
149 | rbp_left_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;␉\␊ |
150 | (r_node) = rbp_left_get(a_type, a_field, (r_node))) {␉␉\␊ |
151 | }␉␉␉␉␉␉␉␉␉\␊ |
152 | } while (0)␊ |
153 | ␊ |
154 | #define␉rbp_last(a_type, a_field, a_tree, a_root, r_node) do {␉␉\␊ |
155 | for ((r_node) = (a_root);␉␉␉␉␉␉\␊ |
156 | rbp_right_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;␉\␊ |
157 | (r_node) = rbp_right_get(a_type, a_field, (r_node))) {␉␉\␊ |
158 | }␉␉␉␉␉␉␉␉␉\␊ |
159 | } while (0)␊ |
160 | ␊ |
161 | #define␉rbp_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {␉\␊ |
162 | if (rbp_right_get(a_type, a_field, (a_node))␉␉␉\␊ |
163 | != &(a_tree)->rbt_nil) {␉␉␉␉␉␉\␊ |
164 | rbp_first(a_type, a_field, a_tree, rbp_right_get(a_type,␉\␊ |
165 | a_field, (a_node)), (r_node));␉␉␉␉\␊ |
166 | } else {␉␉␉␉␉␉␉␉\␊ |
167 | a_type *rbp_n_t = (a_tree)->rbt_root;␉␉␉␉\␊ |
168 | assert(rbp_n_t != &(a_tree)->rbt_nil);␉␉␉␉\␊ |
169 | (r_node) = &(a_tree)->rbt_nil;␉␉␉␉␉\␊ |
170 | while (true) {␉␉␉␉␉␉␉\␊ |
171 | int rbp_n_cmp = (a_cmp)((a_node), rbp_n_t);␉␉␉\␊ |
172 | if (rbp_n_cmp < 0) {␉␉␉␉␉\␊ |
173 | (r_node) = rbp_n_t;␉␉␉␉␉\␊ |
174 | rbp_n_t = rbp_left_get(a_type, a_field, rbp_n_t);␉\␊ |
175 | } else if (rbp_n_cmp > 0) {␉␉␉␉␉\␊ |
176 | rbp_n_t = rbp_right_get(a_type, a_field, rbp_n_t);␉\␊ |
177 | } else {␉␉␉␉␉␉␉\␊ |
178 | break;␉␉␉␉␉␉␉\␊ |
179 | }␉␉␉␉␉␉␉␉\␊ |
180 | assert(rbp_n_t != &(a_tree)->rbt_nil);␉␉␉\␊ |
181 | }␉␉␉␉␉␉␉␉\␊ |
182 | }␉␉␉␉␉␉␉␉␉\␊ |
183 | } while (0)␊ |
184 | ␊ |
185 | #define␉rbp_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {␉\␊ |
186 | if (rbp_left_get(a_type, a_field, (a_node)) != &(a_tree)->rbt_nil) {\␊ |
187 | rbp_last(a_type, a_field, a_tree, rbp_left_get(a_type,␉␉\␊ |
188 | a_field, (a_node)), (r_node));␉␉␉␉\␊ |
189 | } else {␉␉␉␉␉␉␉␉\␊ |
190 | a_type *rbp_p_t = (a_tree)->rbt_root;␉␉␉␉\␊ |
191 | assert(rbp_p_t != &(a_tree)->rbt_nil);␉␉␉␉\␊ |
192 | (r_node) = &(a_tree)->rbt_nil;␉␉␉␉␉\␊ |
193 | while (true) {␉␉␉␉␉␉␉\␊ |
194 | int rbp_p_cmp = (a_cmp)((a_node), rbp_p_t);␉␉␉\␊ |
195 | if (rbp_p_cmp < 0) {␉␉␉␉␉\␊ |
196 | rbp_p_t = rbp_left_get(a_type, a_field, rbp_p_t);␉\␊ |
197 | } else if (rbp_p_cmp > 0) {␉␉␉␉␉\␊ |
198 | (r_node) = rbp_p_t;␉␉␉␉␉\␊ |
199 | rbp_p_t = rbp_right_get(a_type, a_field, rbp_p_t);␉\␊ |
200 | } else {␉␉␉␉␉␉␉\␊ |
201 | break;␉␉␉␉␉␉␉\␊ |
202 | }␉␉␉␉␉␉␉␉\␊ |
203 | assert(rbp_p_t != &(a_tree)->rbt_nil);␉␉␉\␊ |
204 | }␉␉␉␉␉␉␉␉\␊ |
205 | }␉␉␉␉␉␉␉␉␉\␊ |
206 | } while (0)␊ |
207 | ␊ |
208 | #define␉rb_first(a_type, a_field, a_tree, r_node) do {␉␉␉\␊ |
209 | rbp_first(a_type, a_field, a_tree, (a_tree)->rbt_root, (r_node));␉\␊ |
210 | if ((r_node) == &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
211 | (r_node) = NULL;␉␉␉␉␉␉\␊ |
212 | }␉␉␉␉␉␉␉␉␉\␊ |
213 | } while (0)␊ |
214 | ␊ |
215 | #define␉rb_last(a_type, a_field, a_tree, r_node) do {␉␉␉\␊ |
216 | rbp_last(a_type, a_field, a_tree, (a_tree)->rbt_root, r_node);␉\␊ |
217 | if ((r_node) == &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
218 | (r_node) = NULL;␉␉␉␉␉␉\␊ |
219 | }␉␉␉␉␉␉␉␉␉\␊ |
220 | } while (0)␊ |
221 | ␊ |
222 | #define␉rb_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {␉\␊ |
223 | rbp_next(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));␉\␊ |
224 | if ((r_node) == &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
225 | (r_node) = NULL;␉␉␉␉␉␉\␊ |
226 | }␉␉␉␉␉␉␉␉␉\␊ |
227 | } while (0)␊ |
228 | ␊ |
229 | #define␉rb_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do {␉\␊ |
230 | rbp_prev(a_type, a_field, a_cmp, a_tree, (a_node), (r_node));␉\␊ |
231 | if ((r_node) == &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
232 | (r_node) = NULL;␉␉␉␉␉␉\␊ |
233 | }␉␉␉␉␉␉␉␉␉\␊ |
234 | } while (0)␊ |
235 | ␊ |
236 | #define␉rb_search(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {␉\␊ |
237 | int rbp_se_cmp;␉␉␉␉␉␉␉\␊ |
238 | (r_node) = (a_tree)->rbt_root;␉␉␉␉␉\␊ |
239 | while ((r_node) != &(a_tree)->rbt_nil␉␉␉␉\␊ |
240 | && (rbp_se_cmp = (a_cmp)((a_key), (r_node))) != 0) {␉␉\␊ |
241 | if (rbp_se_cmp < 0) {␉␉␉␉␉␉\␊ |
242 | (r_node) = rbp_left_get(a_type, a_field, (r_node));␉␉\␊ |
243 | } else {␉␉␉␉␉␉␉\␊ |
244 | (r_node) = rbp_right_get(a_type, a_field, (r_node));␉\␊ |
245 | }␉␉␉␉␉␉␉␉\␊ |
246 | }␉␉␉␉␉␉␉␉␉\␊ |
247 | if ((r_node) == &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
248 | (r_node) = NULL;␉␉␉␉␉␉\␊ |
249 | }␉␉␉␉␉␉␉␉␉\␊ |
250 | } while (0)␊ |
251 | ␊ |
252 | /*␊ |
253 | * Find a match if it exists. Otherwise, find the next greater node, if one␊ |
254 | * exists.␊ |
255 | */␊ |
256 | #define␉rb_nsearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {␉\␊ |
257 | a_type *rbp_ns_t = (a_tree)->rbt_root;␉␉␉␉\␊ |
258 | (r_node) = NULL;␉␉␉␉␉␉␉\␊ |
259 | while (rbp_ns_t != &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
260 | int rbp_ns_cmp = (a_cmp)((a_key), rbp_ns_t);␉␉␉\␊ |
261 | if (rbp_ns_cmp < 0) {␉␉␉␉␉␉\␊ |
262 | (r_node) = rbp_ns_t;␉␉␉␉␉\␊ |
263 | rbp_ns_t = rbp_left_get(a_type, a_field, rbp_ns_t);␉␉\␊ |
264 | } else if (rbp_ns_cmp > 0) {␉␉␉␉␉\␊ |
265 | rbp_ns_t = rbp_right_get(a_type, a_field, rbp_ns_t);␉\␊ |
266 | } else {␉␉␉␉␉␉␉\␊ |
267 | (r_node) = rbp_ns_t;␉␉␉␉␉\␊ |
268 | break;␉␉␉␉␉␉␉\␊ |
269 | }␉␉␉␉␉␉␉␉\␊ |
270 | }␉␉␉␉␉␉␉␉␉\␊ |
271 | } while (0)␊ |
272 | ␊ |
273 | /*␊ |
274 | * Find a match if it exists. Otherwise, find the previous lesser node, if one␊ |
275 | * exists.␊ |
276 | */␊ |
277 | #define␉rb_psearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do {␉\␊ |
278 | a_type *rbp_ps_t = (a_tree)->rbt_root;␉␉␉␉\␊ |
279 | (r_node) = NULL;␉␉␉␉␉␉␉\␊ |
280 | while (rbp_ps_t != &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
281 | int rbp_ps_cmp = (a_cmp)((a_key), rbp_ps_t);␉␉␉\␊ |
282 | if (rbp_ps_cmp < 0) {␉␉␉␉␉␉\␊ |
283 | rbp_ps_t = rbp_left_get(a_type, a_field, rbp_ps_t);␉␉\␊ |
284 | } else if (rbp_ps_cmp > 0) {␉␉␉␉␉\␊ |
285 | (r_node) = rbp_ps_t;␉␉␉␉␉\␊ |
286 | rbp_ps_t = rbp_right_get(a_type, a_field, rbp_ps_t);␉\␊ |
287 | } else {␉␉␉␉␉␉␉\␊ |
288 | (r_node) = rbp_ps_t;␉␉␉␉␉\␊ |
289 | break;␉␉␉␉␉␉␉\␊ |
290 | }␉␉␉␉␉␉␉␉\␊ |
291 | }␉␉␉␉␉␉␉␉␉\␊ |
292 | } while (0)␊ |
293 | ␊ |
294 | #define␉rbp_rotate_left(a_type, a_field, a_node, r_node) do {␉␉\␊ |
295 | (r_node) = rbp_right_get(a_type, a_field, (a_node));␉␉\␊ |
296 | rbp_right_set(a_type, a_field, (a_node),␉␉␉␉\␊ |
297 | rbp_left_get(a_type, a_field, (r_node)));␉␉␉␉\␊ |
298 | rbp_left_set(a_type, a_field, (r_node), (a_node));␉␉␉\␊ |
299 | } while (0)␊ |
300 | ␊ |
301 | #define␉rbp_rotate_right(a_type, a_field, a_node, r_node) do {␉␉\␊ |
302 | (r_node) = rbp_left_get(a_type, a_field, (a_node));␉␉␉\␊ |
303 | rbp_left_set(a_type, a_field, (a_node),␉␉␉␉\␊ |
304 | rbp_right_get(a_type, a_field, (r_node)));␉␉␉\␊ |
305 | rbp_right_set(a_type, a_field, (r_node), (a_node));␉␉␉\␊ |
306 | } while (0)␊ |
307 | ␊ |
308 | #define␉rbp_lean_left(a_type, a_field, a_node, r_node) do {␉␉\␊ |
309 | bool rbp_ll_red;␉␉␉␉␉␉␉\␊ |
310 | rbp_rotate_left(a_type, a_field, (a_node), (r_node));␉␉\␊ |
311 | rbp_ll_red = rbp_red_get(a_type, a_field, (a_node));␉␉\␊ |
312 | rbp_color_set(a_type, a_field, (r_node), rbp_ll_red);␉␉\␊ |
313 | rbp_red_set(a_type, a_field, (a_node));␉␉␉␉\␊ |
314 | } while (0)␊ |
315 | ␊ |
316 | #define␉rbp_lean_right(a_type, a_field, a_node, r_node) do {␉␉\␊ |
317 | bool rbp_lr_red;␉␉␉␉␉␉␉\␊ |
318 | rbp_rotate_right(a_type, a_field, (a_node), (r_node));␉␉\␊ |
319 | rbp_lr_red = rbp_red_get(a_type, a_field, (a_node));␉␉\␊ |
320 | rbp_color_set(a_type, a_field, (r_node), rbp_lr_red);␉␉\␊ |
321 | rbp_red_set(a_type, a_field, (a_node));␉␉␉␉\␊ |
322 | } while (0)␊ |
323 | ␊ |
324 | #define␉rbp_move_red_left(a_type, a_field, a_node, r_node) do {␉␉\␊ |
325 | a_type *rbp_mrl_t, *rbp_mrl_u;␉␉␉␉␉\␊ |
326 | rbp_mrl_t = rbp_left_get(a_type, a_field, (a_node));␉␉\␊ |
327 | rbp_red_set(a_type, a_field, rbp_mrl_t);␉␉␉␉\␊ |
328 | rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));␉␉\␊ |
329 | rbp_mrl_u = rbp_left_get(a_type, a_field, rbp_mrl_t);␉␉\␊ |
330 | if (rbp_red_get(a_type, a_field, rbp_mrl_u)) {␉␉␉\␊ |
331 | rbp_rotate_right(a_type, a_field, rbp_mrl_t, rbp_mrl_u);␉\␊ |
332 | rbp_right_set(a_type, a_field, (a_node), rbp_mrl_u);␉␉\␊ |
333 | rbp_rotate_left(a_type, a_field, (a_node), (r_node));␉␉\␊ |
334 | rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node));␉␉\␊ |
335 | if (rbp_red_get(a_type, a_field, rbp_mrl_t)) {␉␉␉\␊ |
336 | rbp_black_set(a_type, a_field, rbp_mrl_t);␉␉␉\␊ |
337 | rbp_red_set(a_type, a_field, (a_node));␉␉␉\␊ |
338 | rbp_rotate_left(a_type, a_field, (a_node), rbp_mrl_t);␉\␊ |
339 | rbp_left_set(a_type, a_field, (r_node), rbp_mrl_t);␉␉\␊ |
340 | } else {␉␉␉␉␉␉␉\␊ |
341 | rbp_black_set(a_type, a_field, (a_node));␉␉␉\␊ |
342 | }␉␉␉␉␉␉␉␉\␊ |
343 | } else {␉␉␉␉␉␉␉␉\␊ |
344 | rbp_red_set(a_type, a_field, (a_node));␉␉␉␉\␊ |
345 | rbp_rotate_left(a_type, a_field, (a_node), (r_node));␉␉\␊ |
346 | }␉␉␉␉␉␉␉␉␉\␊ |
347 | } while (0)␊ |
348 | ␊ |
349 | #define␉rbp_move_red_right(a_type, a_field, a_node, r_node) do {␉\␊ |
350 | a_type *rbp_mrr_t;␉␉␉␉␉␉␉\␊ |
351 | rbp_mrr_t = rbp_left_get(a_type, a_field, (a_node));␉␉\␊ |
352 | if (rbp_red_get(a_type, a_field, rbp_mrr_t)) {␉␉␉\␊ |
353 | a_type *rbp_mrr_u, *rbp_mrr_v;␉␉␉␉␉\␊ |
354 | rbp_mrr_u = rbp_right_get(a_type, a_field, rbp_mrr_t);␉␉\␊ |
355 | rbp_mrr_v = rbp_left_get(a_type, a_field, rbp_mrr_u);␉␉\␊ |
356 | if (rbp_red_get(a_type, a_field, rbp_mrr_v)) {␉␉␉\␊ |
357 | rbp_color_set(a_type, a_field, rbp_mrr_u,␉␉␉\␊ |
358 | rbp_red_get(a_type, a_field, (a_node)));␉␉␉\␊ |
359 | rbp_black_set(a_type, a_field, rbp_mrr_v);␉␉␉\␊ |
360 | rbp_rotate_left(a_type, a_field, rbp_mrr_t, rbp_mrr_u);␉\␊ |
361 | rbp_left_set(a_type, a_field, (a_node), rbp_mrr_u);␉␉\␊ |
362 | rbp_rotate_right(a_type, a_field, (a_node), (r_node));␉\␊ |
363 | rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);␉\␊ |
364 | rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);␉\␊ |
365 | } else {␉␉␉␉␉␉␉\␊ |
366 | rbp_color_set(a_type, a_field, rbp_mrr_t,␉␉␉\␊ |
367 | rbp_red_get(a_type, a_field, (a_node)));␉␉␉\␊ |
368 | rbp_red_set(a_type, a_field, rbp_mrr_u);␉␉␉\␊ |
369 | rbp_rotate_right(a_type, a_field, (a_node), (r_node));␉\␊ |
370 | rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);␉\␊ |
371 | rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);␉\␊ |
372 | }␉␉␉␉␉␉␉␉\␊ |
373 | rbp_red_set(a_type, a_field, (a_node));␉␉␉␉\␊ |
374 | } else {␉␉␉␉␉␉␉␉\␊ |
375 | rbp_red_set(a_type, a_field, rbp_mrr_t);␉␉␉\␊ |
376 | rbp_mrr_t = rbp_left_get(a_type, a_field, rbp_mrr_t);␉␉\␊ |
377 | if (rbp_red_get(a_type, a_field, rbp_mrr_t)) {␉␉␉\␊ |
378 | rbp_black_set(a_type, a_field, rbp_mrr_t);␉␉␉\␊ |
379 | rbp_rotate_right(a_type, a_field, (a_node), (r_node));␉\␊ |
380 | rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t);␉\␊ |
381 | rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t);␉\␊ |
382 | } else {␉␉␉␉␉␉␉\␊ |
383 | rbp_rotate_left(a_type, a_field, (a_node), (r_node));␉\␊ |
384 | }␉␉␉␉␉␉␉␉\␊ |
385 | }␉␉␉␉␉␉␉␉␉\␊ |
386 | } while (0)␊ |
387 | ␊ |
388 | #define␉rb_insert(a_type, a_field, a_cmp, a_tree, a_node) do {␉␉\␊ |
389 | a_type rbp_i_s;␉␉␉␉␉␉␉\␊ |
390 | a_type *rbp_i_g, *rbp_i_p, *rbp_i_c, *rbp_i_t, *rbp_i_u;␉␉\␊ |
391 | int rbp_i_cmp = 0;␉␉␉␉␉␉␉\␊ |
392 | rbp_i_g = &(a_tree)->rbt_nil;␉␉␉␉␉\␊ |
393 | rbp_left_set(a_type, a_field, &rbp_i_s, (a_tree)->rbt_root);␉\␊ |
394 | rbp_right_set(a_type, a_field, &rbp_i_s, &(a_tree)->rbt_nil);␉\␊ |
395 | rbp_black_set(a_type, a_field, &rbp_i_s);␉␉␉␉\␊ |
396 | rbp_i_p = &rbp_i_s;␉␉␉␉␉␉␉\␊ |
397 | rbp_i_c = (a_tree)->rbt_root;␉␉␉␉␉\␊ |
398 | /* Iteratively search down the tree for the insertion point, */\␊ |
399 | /* splitting 4-nodes as they are encountered. At the end of each */\␊ |
400 | /* iteration, rbp_i_g->rbp_i_p->rbp_i_c is a 3-level path down */\␊ |
401 | /* the tree, assuming a sufficiently deep tree. */\␊ |
402 | while (rbp_i_c != &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
403 | rbp_i_t = rbp_left_get(a_type, a_field, rbp_i_c);␉␉\␊ |
404 | rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t);␉␉\␊ |
405 | if (rbp_red_get(a_type, a_field, rbp_i_t)␉␉␉\␊ |
406 | && rbp_red_get(a_type, a_field, rbp_i_u)) {␉␉␉\␊ |
407 | /* rbp_i_c is the top of a logical 4-node, so split it. */\␊ |
408 | /* This iteration does not move down the tree, due to the */\␊ |
409 | /* disruptiveness of node splitting. */\␊ |
410 | /* */\␊ |
411 | /* Rotate right. */\␊ |
412 | rbp_rotate_right(a_type, a_field, rbp_i_c, rbp_i_t);␉\␊ |
413 | /* Pass red links up one level. */\␊ |
414 | rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t);␉␉\␊ |
415 | rbp_black_set(a_type, a_field, rbp_i_u);␉␉␉\␊ |
416 | if (rbp_left_get(a_type, a_field, rbp_i_p) == rbp_i_c) {␉\␊ |
417 | rbp_left_set(a_type, a_field, rbp_i_p, rbp_i_t);␉\␊ |
418 | rbp_i_c = rbp_i_t;␉␉␉␉␉\␊ |
419 | } else {␉␉␉␉␉␉␉\␊ |
420 | /* rbp_i_c was the right child of rbp_i_p, so rotate */\␊ |
421 | /* left in order to maintain the left-leaning */\␊ |
422 | /* invariant. */\␊ |
423 | assert(rbp_right_get(a_type, a_field, rbp_i_p)␉␉\␊ |
424 | == rbp_i_c);␉␉␉␉␉␉\␊ |
425 | rbp_right_set(a_type, a_field, rbp_i_p, rbp_i_t);␉\␊ |
426 | rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_u);␉\␊ |
427 | if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\␊ |
428 | rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_u);␉\␊ |
429 | } else {␉␉␉␉␉␉\␊ |
430 | assert(rbp_right_get(a_type, a_field, rbp_i_g)␉\␊ |
431 | == rbp_i_p);␉␉␉␉␉\␊ |
432 | rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_u);␉\␊ |
433 | }␉␉␉␉␉␉␉\␊ |
434 | rbp_i_p = rbp_i_u;␉␉␉␉␉\␊ |
435 | rbp_i_cmp = (a_cmp)((a_node), rbp_i_p);␉␉␉\␊ |
436 | if (rbp_i_cmp < 0) {␉␉␉␉␉\␊ |
437 | rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_p);␉\␊ |
438 | } else {␉␉␉␉␉␉\␊ |
439 | assert(rbp_i_cmp > 0);␉␉␉␉\␊ |
440 | rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_p);␉\␊ |
441 | }␉␉␉␉␉␉␉\␊ |
442 | continue;␉␉␉␉␉␉\␊ |
443 | }␉␉␉␉␉␉␉␉\␊ |
444 | }␉␉␉␉␉␉␉␉\␊ |
445 | rbp_i_g = rbp_i_p;␉␉␉␉␉␉\␊ |
446 | rbp_i_p = rbp_i_c;␉␉␉␉␉␉\␊ |
447 | rbp_i_cmp = (a_cmp)((a_node), rbp_i_c);␉␉␉␉\␊ |
448 | if (rbp_i_cmp < 0) {␉␉␉␉␉␉\␊ |
449 | rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_c);␉␉\␊ |
450 | } else {␉␉␉␉␉␉␉\␊ |
451 | assert(rbp_i_cmp > 0);␉␉␉␉␉\␊ |
452 | rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_c);␉␉\␊ |
453 | }␉␉␉␉␉␉␉␉\␊ |
454 | }␉␉␉␉␉␉␉␉␉\␊ |
455 | /* rbp_i_p now refers to the node under which to insert. */\␊ |
456 | rbp_node_new(a_type, a_field, a_tree, (a_node));␉␉␉\␊ |
457 | if (rbp_i_cmp > 0) {␉␉␉␉␉␉\␊ |
458 | rbp_right_set(a_type, a_field, rbp_i_p, (a_node));␉␉\␊ |
459 | rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_t);␉␉\␊ |
460 | if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {␉\␊ |
461 | rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_t);␉␉\␊ |
462 | } else if (rbp_right_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\␊ |
463 | rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_t);␉␉\␊ |
464 | }␉␉␉␉␉␉␉␉\␊ |
465 | } else {␉␉␉␉␉␉␉␉\␊ |
466 | rbp_left_set(a_type, a_field, rbp_i_p, (a_node));␉␉\␊ |
467 | }␉␉␉␉␉␉␉␉␉\␊ |
468 | /* Update the root and make sure that it is black. */\␊ |
469 | (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_i_s);␉\␊ |
470 | rbp_black_set(a_type, a_field, (a_tree)->rbt_root);␉␉␉\␊ |
471 | } while (0)␊ |
472 | ␊ |
473 | #define␉rb_remove(a_type, a_field, a_cmp, a_tree, a_node) do {␉␉\␊ |
474 | a_type rbp_r_s;␉␉␉␉␉␉␉\␊ |
475 | a_type *rbp_r_p, *rbp_r_c, *rbp_r_xp, *rbp_r_t, *rbp_r_u;␉␉\␊ |
476 | int rbp_r_cmp;␉␉␉␉␉␉␉\␊ |
477 | rbp_left_set(a_type, a_field, &rbp_r_s, (a_tree)->rbt_root);␉\␊ |
478 | rbp_right_set(a_type, a_field, &rbp_r_s, &(a_tree)->rbt_nil);␉\␊ |
479 | rbp_black_set(a_type, a_field, &rbp_r_s);␉␉␉␉\␊ |
480 | rbp_r_p = &rbp_r_s;␉␉␉␉␉␉␉\␊ |
481 | rbp_r_c = (a_tree)->rbt_root;␉␉␉␉␉\␊ |
482 | rbp_r_xp = &(a_tree)->rbt_nil;␉␉␉␉␉\␊ |
483 | /* Iterate down the tree, but always transform 2-nodes to 3- or */\␊ |
484 | /* 4-nodes in order to maintain the invariant that the current */\␊ |
485 | /* node is not a 2-node. This allows simple deletion once a leaf */\␊ |
486 | /* is reached. Handle the root specially though, since there may */\␊ |
487 | /* be no way to convert it from a 2-node to a 3-node. */\␊ |
488 | rbp_r_cmp = (a_cmp)((a_node), rbp_r_c);␉␉␉␉\␊ |
489 | if (rbp_r_cmp < 0) {␉␉␉␉␉␉\␊ |
490 | rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);␉␉\␊ |
491 | rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);␉␉\␊ |
492 | if (rbp_red_get(a_type, a_field, rbp_r_t) == false␉␉\␊ |
493 | && rbp_red_get(a_type, a_field, rbp_r_u) == false) {␉␉\␊ |
494 | /* Apply standard transform to prepare for left move. */\␊ |
495 | rbp_move_red_left(a_type, a_field, rbp_r_c, rbp_r_t);␉\␊ |
496 | rbp_black_set(a_type, a_field, rbp_r_t);␉␉␉\␊ |
497 | rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);␉␉\␊ |
498 | rbp_r_c = rbp_r_t;␉␉␉␉␉␉\␊ |
499 | } else {␉␉␉␉␉␉␉\␊ |
500 | /* Move left. */\␊ |
501 | rbp_r_p = rbp_r_c;␉␉␉␉␉␉\␊ |
502 | rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c);␉␉\␊ |
503 | }␉␉␉␉␉␉␉␉\␊ |
504 | } else {␉␉␉␉␉␉␉␉\␊ |
505 | if (rbp_r_cmp == 0) {␉␉␉␉␉␉\␊ |
506 | assert((a_node) == rbp_r_c);␉␉␉␉\␊ |
507 | if (rbp_right_get(a_type, a_field, rbp_r_c)␉␉␉\␊ |
508 | == &(a_tree)->rbt_nil) {␉␉␉␉␉\␊ |
509 | /* Delete root node (which is also a leaf node). */\␊ |
510 | if (rbp_left_get(a_type, a_field, rbp_r_c)␉␉\␊ |
511 | != &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
512 | rbp_lean_right(a_type, a_field, rbp_r_c, rbp_r_t);␉\␊ |
513 | rbp_right_set(a_type, a_field, rbp_r_t,␉␉\␊ |
514 | &(a_tree)->rbt_nil);␉␉␉␉\␊ |
515 | } else {␉␉␉␉␉␉\␊ |
516 | rbp_r_t = &(a_tree)->rbt_nil;␉␉␉\␊ |
517 | }␉␉␉␉␉␉␉\␊ |
518 | rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);␉\␊ |
519 | } else {␉␉␉␉␉␉␉\␊ |
520 | /* This is the node we want to delete, but we will */\␊ |
521 | /* instead swap it with its successor and delete the */\␊ |
522 | /* successor. Record enough information to do the */\␊ |
523 | /* swap later. rbp_r_xp is the a_node's parent. */\␊ |
524 | rbp_r_xp = rbp_r_p;␉␉␉␉␉\␊ |
525 | rbp_r_cmp = 1; /* Note that deletion is incomplete. */\␊ |
526 | }␉␉␉␉␉␉␉␉\␊ |
527 | }␉␉␉␉␉␉␉␉\␊ |
528 | if (rbp_r_cmp == 1) {␉␉␉␉␉␉\␊ |
529 | if (rbp_red_get(a_type, a_field, rbp_left_get(a_type,␉\␊ |
530 | a_field, rbp_right_get(a_type, a_field, rbp_r_c)))␉\␊ |
531 | == false) {␉␉␉␉␉␉\␊ |
532 | rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);␉\␊ |
533 | if (rbp_red_get(a_type, a_field, rbp_r_t)) {␉␉\␊ |
534 | /* Standard transform. */\␊ |
535 | rbp_move_red_right(a_type, a_field, rbp_r_c,␉\␊ |
536 | rbp_r_t);␉␉␉␉␉␉\␊ |
537 | } else {␉␉␉␉␉␉\␊ |
538 | /* Root-specific transform. */\␊ |
539 | rbp_red_set(a_type, a_field, rbp_r_c);␉␉\␊ |
540 | rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);␉\␊ |
541 | if (rbp_red_get(a_type, a_field, rbp_r_u)) {␉\␊ |
542 | rbp_black_set(a_type, a_field, rbp_r_u);␉\␊ |
543 | rbp_rotate_right(a_type, a_field, rbp_r_c,␉\␊ |
544 | rbp_r_t);␉␉␉␉␉\␊ |
545 | rbp_rotate_left(a_type, a_field, rbp_r_c,␉\␊ |
546 | rbp_r_u);␉␉␉␉␉\␊ |
547 | rbp_right_set(a_type, a_field, rbp_r_t,␉␉\␊ |
548 | rbp_r_u);␉␉␉␉␉\␊ |
549 | } else {␉␉␉␉␉␉\␊ |
550 | rbp_red_set(a_type, a_field, rbp_r_t);␉␉\␊ |
551 | rbp_rotate_left(a_type, a_field, rbp_r_c,␉\␊ |
552 | rbp_r_t);␉␉␉␉␉\␊ |
553 | }␉␉␉␉␉␉␉\␊ |
554 | }␉␉␉␉␉␉␉\␊ |
555 | rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);␉\␊ |
556 | rbp_r_c = rbp_r_t;␉␉␉␉␉\␊ |
557 | } else {␉␉␉␉␉␉␉\␊ |
558 | /* Move right. */\␊ |
559 | rbp_r_p = rbp_r_c;␉␉␉␉␉\␊ |
560 | rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c);␉\␊ |
561 | }␉␉␉␉␉␉␉␉\␊ |
562 | }␉␉␉␉␉␉␉␉\␊ |
563 | }␉␉␉␉␉␉␉␉␉\␊ |
564 | if (rbp_r_cmp != 0) {␉␉␉␉␉␉\␊ |
565 | while (true) {␉␉␉␉␉␉␉\␊ |
566 | assert(rbp_r_p != &(a_tree)->rbt_nil);␉␉␉\␊ |
567 | rbp_r_cmp = (a_cmp)((a_node), rbp_r_c);␉␉␉\␊ |
568 | if (rbp_r_cmp < 0) {␉␉␉␉␉\␊ |
569 | rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c);␉\␊ |
570 | if (rbp_r_t == &(a_tree)->rbt_nil) {␉␉␉\␊ |
571 | /* rbp_r_c now refers to the successor node to */\␊ |
572 | /* relocate, and rbp_r_xp/a_node refer to the */\␊ |
573 | /* context for the relocation. */\␊ |
574 | if (rbp_left_get(a_type, a_field, rbp_r_xp)␉␉\␊ |
575 | == (a_node)) {␉␉␉␉␉\␊ |
576 | rbp_left_set(a_type, a_field, rbp_r_xp,␉␉\␊ |
577 | rbp_r_c);␉␉␉␉␉\␊ |
578 | } else {␉␉␉␉␉␉\␊ |
579 | assert(rbp_right_get(a_type, a_field,␉␉\␊ |
580 | rbp_r_xp) == (a_node));␉␉␉\␊ |
581 | rbp_right_set(a_type, a_field, rbp_r_xp,␉\␊ |
582 | rbp_r_c);␉␉␉␉␉\␊ |
583 | }␉␉␉␉␉␉␉\␊ |
584 | rbp_left_set(a_type, a_field, rbp_r_c,␉␉\␊ |
585 | rbp_left_get(a_type, a_field, (a_node)));␉␉\␊ |
586 | rbp_right_set(a_type, a_field, rbp_r_c,␉␉\␊ |
587 | rbp_right_get(a_type, a_field, (a_node)));␉\␊ |
588 | rbp_color_set(a_type, a_field, rbp_r_c,␉␉\␊ |
589 | rbp_red_get(a_type, a_field, (a_node)));␉␉\␊ |
590 | if (rbp_left_get(a_type, a_field, rbp_r_p)␉␉\␊ |
591 | == rbp_r_c) {␉␉␉␉␉\␊ |
592 | rbp_left_set(a_type, a_field, rbp_r_p,␉␉\␊ |
593 | &(a_tree)->rbt_nil);␉␉␉␉\␊ |
594 | } else {␉␉␉␉␉␉\␊ |
595 | assert(rbp_right_get(a_type, a_field, rbp_r_p)␉\␊ |
596 | == rbp_r_c);␉␉␉␉␉\␊ |
597 | rbp_right_set(a_type, a_field, rbp_r_p,␉␉\␊ |
598 | &(a_tree)->rbt_nil);␉␉␉␉\␊ |
599 | }␉␉␉␉␉␉␉\␊ |
600 | break;␉␉␉␉␉␉\␊ |
601 | }␉␉␉␉␉␉␉\␊ |
602 | rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);␉\␊ |
603 | if (rbp_red_get(a_type, a_field, rbp_r_t) == false␉\␊ |
604 | && rbp_red_get(a_type, a_field, rbp_r_u) == false) {␉\␊ |
605 | rbp_move_red_left(a_type, a_field, rbp_r_c,␉␉\␊ |
606 | rbp_r_t);␉␉␉␉␉␉\␊ |
607 | if (rbp_left_get(a_type, a_field, rbp_r_p)␉␉\␊ |
608 | == rbp_r_c) {␉␉␉␉␉\␊ |
609 | rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\␊ |
610 | } else {␉␉␉␉␉␉\␊ |
611 | rbp_right_set(a_type, a_field, rbp_r_p,␉␉\␊ |
612 | rbp_r_t);␉␉␉␉␉\␊ |
613 | }␉␉␉␉␉␉␉\␊ |
614 | rbp_r_c = rbp_r_t;␉␉␉␉␉\␊ |
615 | } else {␉␉␉␉␉␉\␊ |
616 | rbp_r_p = rbp_r_c;␉␉␉␉␉\␊ |
617 | rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c);␉\␊ |
618 | }␉␉␉␉␉␉␉\␊ |
619 | } else {␉␉␉␉␉␉␉\␊ |
620 | /* Check whether to delete this node (it has to be */\␊ |
621 | /* the correct node and a leaf node). */\␊ |
622 | if (rbp_r_cmp == 0) {␉␉␉␉␉\␊ |
623 | assert((a_node) == rbp_r_c);␉␉␉\␊ |
624 | if (rbp_right_get(a_type, a_field, rbp_r_c)␉␉\␊ |
625 | == &(a_tree)->rbt_nil) {␉␉␉␉\␊ |
626 | /* Delete leaf node. */\␊ |
627 | if (rbp_left_get(a_type, a_field, rbp_r_c)␉\␊ |
628 | != &(a_tree)->rbt_nil) {␉␉␉\␊ |
629 | rbp_lean_right(a_type, a_field, rbp_r_c,␉\␊ |
630 | rbp_r_t);␉␉␉␉␉\␊ |
631 | rbp_right_set(a_type, a_field, rbp_r_t,␉\␊ |
632 | &(a_tree)->rbt_nil);␉␉␉\␊ |
633 | } else {␉␉␉␉␉\␊ |
634 | rbp_r_t = &(a_tree)->rbt_nil;␉␉\␊ |
635 | }␉␉␉␉␉␉\␊ |
636 | if (rbp_left_get(a_type, a_field, rbp_r_p)␉\␊ |
637 | == rbp_r_c) {␉␉␉␉␉\␊ |
638 | rbp_left_set(a_type, a_field, rbp_r_p,␉\␊ |
639 | rbp_r_t);␉␉␉␉␉\␊ |
640 | } else {␉␉␉␉␉\␊ |
641 | rbp_right_set(a_type, a_field, rbp_r_p,␉\␊ |
642 | rbp_r_t);␉␉␉␉␉\␊ |
643 | }␉␉␉␉␉␉\␊ |
644 | break;␉␉␉␉␉␉\␊ |
645 | } else {␉␉␉␉␉␉\␊ |
646 | /* This is the node we want to delete, but we */\␊ |
647 | /* will instead swap it with its successor */\␊ |
648 | /* and delete the successor. Record enough */\␊ |
649 | /* information to do the swap later. */\␊ |
650 | /* rbp_r_xp is a_node's parent. */\␊ |
651 | rbp_r_xp = rbp_r_p;␉␉␉␉\␊ |
652 | }␉␉␉␉␉␉␉\␊ |
653 | }␉␉␉␉␉␉␉\␊ |
654 | rbp_r_t = rbp_right_get(a_type, a_field, rbp_r_c);␉\␊ |
655 | rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t);␉\␊ |
656 | if (rbp_red_get(a_type, a_field, rbp_r_u) == false) {␉\␊ |
657 | rbp_move_red_right(a_type, a_field, rbp_r_c,␉\␊ |
658 | rbp_r_t);␉␉␉␉␉␉\␊ |
659 | if (rbp_left_get(a_type, a_field, rbp_r_p)␉␉\␊ |
660 | == rbp_r_c) {␉␉␉␉␉\␊ |
661 | rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\␊ |
662 | } else {␉␉␉␉␉␉\␊ |
663 | rbp_right_set(a_type, a_field, rbp_r_p,␉␉\␊ |
664 | rbp_r_t);␉␉␉␉␉\␊ |
665 | }␉␉␉␉␉␉␉\␊ |
666 | rbp_r_c = rbp_r_t;␉␉␉␉␉\␊ |
667 | } else {␉␉␉␉␉␉\␊ |
668 | rbp_r_p = rbp_r_c;␉␉␉␉␉\␊ |
669 | rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c);␉\␊ |
670 | }␉␉␉␉␉␉␉\␊ |
671 | }␉␉␉␉␉␉␉␉\␊ |
672 | }␉␉␉␉␉␉␉␉\␊ |
673 | }␉␉␉␉␉␉␉␉␉\␊ |
674 | /* Update root. */\␊ |
675 | (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_r_s);␉\␊ |
676 | } while (0)␊ |
677 | ␊ |
678 | /*␊ |
679 | * The rb_wrap() macro provides a convenient way to wrap functions around the␊ |
680 | * cpp macros. The main benefits of wrapping are that 1) repeated macro␊ |
681 | * expansion can cause code bloat, especially for rb_{insert,remove)(), and␊ |
682 | * 2) type, linkage, comparison functions, etc. need not be specified at every␊ |
683 | * call point.␊ |
684 | */␊ |
685 | ␊ |
686 | #define␉rb_wrap(a_attr, a_prefix, a_tree_type, a_type, a_field, a_cmp)␉\␊ |
687 | a_attr void␉␉␉␉␉␉␉␉\␊ |
688 | a_prefix##new(a_tree_type *tree) {␉␉␉␉␉\␊ |
689 | rb_new(a_type, a_field, tree);␉␉␉␉␉\␊ |
690 | }␉␉␉␉␉␉␉␉␉\␊ |
691 | a_attr a_type *␉␉␉␉␉␉␉␉\␊ |
692 | a_prefix##first(a_tree_type *tree) {␉␉␉␉␉\␊ |
693 | a_type *ret;␉␉␉␉␉␉␉\␊ |
694 | rb_first(a_type, a_field, tree, ret);␉␉␉␉\␊ |
695 | return (ret);␉␉␉␉␉␉␉\␊ |
696 | }␉␉␉␉␉␉␉␉␉\␊ |
697 | a_attr a_type *␉␉␉␉␉␉␉␉\␊ |
698 | a_prefix##last(a_tree_type *tree) {␉␉␉␉␉\␊ |
699 | a_type *ret;␉␉␉␉␉␉␉\␊ |
700 | rb_last(a_type, a_field, tree, ret);␉␉␉␉\␊ |
701 | return (ret);␉␉␉␉␉␉␉\␊ |
702 | }␉␉␉␉␉␉␉␉␉\␊ |
703 | a_attr a_type *␉␉␉␉␉␉␉␉\␊ |
704 | a_prefix##next(a_tree_type *tree, a_type *node) {␉␉␉\␊ |
705 | a_type *ret;␉␉␉␉␉␉␉\␊ |
706 | rb_next(a_type, a_field, a_cmp, tree, node, ret);␉␉␉\␊ |
707 | return (ret);␉␉␉␉␉␉␉\␊ |
708 | }␉␉␉␉␉␉␉␉␉\␊ |
709 | a_attr a_type *␉␉␉␉␉␉␉␉\␊ |
710 | a_prefix##prev(a_tree_type *tree, a_type *node) {␉␉␉\␊ |
711 | a_type *ret;␉␉␉␉␉␉␉\␊ |
712 | rb_prev(a_type, a_field, a_cmp, tree, node, ret);␉␉␉\␊ |
713 | return (ret);␉␉␉␉␉␉␉\␊ |
714 | }␉␉␉␉␉␉␉␉␉\␊ |
715 | a_attr a_type *␉␉␉␉␉␉␉␉\␊ |
716 | a_prefix##search(a_tree_type *tree, a_type *key) {␉␉␉\␊ |
717 | a_type *ret;␉␉␉␉␉␉␉\␊ |
718 | rb_search(a_type, a_field, a_cmp, tree, key, ret);␉␉␉\␊ |
719 | return (ret);␉␉␉␉␉␉␉\␊ |
720 | }␉␉␉␉␉␉␉␉␉\␊ |
721 | a_attr a_type *␉␉␉␉␉␉␉␉\␊ |
722 | a_prefix##nsearch(a_tree_type *tree, a_type *key) {␉␉␉\␊ |
723 | a_type *ret;␉␉␉␉␉␉␉\␊ |
724 | rb_nsearch(a_type, a_field, a_cmp, tree, key, ret);␉␉␉\␊ |
725 | return (ret);␉␉␉␉␉␉␉\␊ |
726 | }␉␉␉␉␉␉␉␉␉\␊ |
727 | a_attr a_type *␉␉␉␉␉␉␉␉\␊ |
728 | a_prefix##psearch(a_tree_type *tree, a_type *key) {␉␉␉\␊ |
729 | a_type *ret;␉␉␉␉␉␉␉\␊ |
730 | rb_psearch(a_type, a_field, a_cmp, tree, key, ret);␉␉␉\␊ |
731 | return (ret);␉␉␉␉␉␉␉\␊ |
732 | }␉␉␉␉␉␉␉␉␉\␊ |
733 | a_attr void␉␉␉␉␉␉␉␉\␊ |
734 | a_prefix##insert(a_tree_type *tree, a_type *node) {␉␉␉\␊ |
735 | rb_insert(a_type, a_field, a_cmp, tree, node);␉␉␉\␊ |
736 | }␉␉␉␉␉␉␉␉␉\␊ |
737 | a_attr void␉␉␉␉␉␉␉␉\␊ |
738 | a_prefix##remove(a_tree_type *tree, a_type *node) {␉␉␉\␊ |
739 | rb_remove(a_type, a_field, a_cmp, tree, node);␉␉␉\␊ |
740 | }␊ |
741 | ␊ |
742 | /*␊ |
743 | * The iterators simulate recursion via an array of pointers that store the␊ |
744 | * current path. This is critical to performance, since a series of calls to␊ |
745 | * rb_{next,prev}() would require time proportional to (n lg n), whereas this␊ |
746 | * implementation only requires time proportional to (n).␊ |
747 | *␊ |
748 | * Since the iterators cache a path down the tree, any tree modification may␊ |
749 | * cause the cached path to become invalid. In order to continue iteration,␊ |
750 | * use something like the following sequence:␊ |
751 | *␊ |
752 | * {␊ |
753 | * a_type *node, *tnode;␊ |
754 | *␊ |
755 | * rb_foreach_begin(a_type, a_field, a_tree, node) {␊ |
756 | * ...␊ |
757 | * rb_next(a_type, a_field, a_cmp, a_tree, node, tnode);␊ |
758 | * rb_remove(a_type, a_field, a_cmp, a_tree, node);␊ |
759 | * rb_foreach_next(a_type, a_field, a_cmp, a_tree, tnode);␊ |
760 | * ...␊ |
761 | * } rb_foreach_end(a_type, a_field, a_tree, node)␊ |
762 | * }␊ |
763 | *␊ |
764 | * Note that this idiom is not advised if every iteration modifies the tree,␊ |
765 | * since in that case there is no algorithmic complexity improvement over a␊ |
766 | * series of rb_{next,prev}() calls, thus making the setup overhead wasted␊ |
767 | * effort.␊ |
768 | */␊ |
769 | ␊ |
770 | #define␉rb_foreach_begin(a_type, a_field, a_tree, a_var) {␉␉\␊ |
771 | /* Compute the maximum possible tree depth (3X the black height). */\␊ |
772 | unsigned rbp_f_height;␉␉␉␉␉␉\␊ |
773 | rbp_black_height(a_type, a_field, a_tree, rbp_f_height);␉␉\␊ |
774 | rbp_f_height *= 3;␉␉␉␉␉␉␉\␊ |
775 | {␉␉␉␉␉␉␉␉␉\␊ |
776 | /* Initialize the path to contain the left spine. */\␊ |
777 | a_type *rbp_f_path[rbp_f_height];␉␉␉␉\␊ |
778 | a_type *rbp_f_node;␉␉␉␉␉␉\␊ |
779 | bool rbp_f_synced = false;␉␉␉␉␉\␊ |
780 | unsigned rbp_f_depth = 0;␉␉␉␉␉\␊ |
781 | if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {␉␉␉\␊ |
782 | rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;␉␉\␊ |
783 | rbp_f_depth++;␉␉␉␉␉␉\␊ |
784 | while ((rbp_f_node = rbp_left_get(a_type, a_field,␉␉\␊ |
785 | rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {␉\␊ |
786 | rbp_f_path[rbp_f_depth] = rbp_f_node;␉␉␉\␊ |
787 | rbp_f_depth++;␉␉␉␉␉␉\␊ |
788 | }␉␉␉␉␉␉␉␉\␊ |
789 | }␉␉␉␉␉␉␉␉\␊ |
790 | /* While the path is non-empty, iterate. */\␊ |
791 | while (rbp_f_depth > 0) {␉␉␉␉␉\␊ |
792 | (a_var) = rbp_f_path[rbp_f_depth-1];␊ |
793 | ␊ |
794 | /* Only use if modifying the tree during iteration. */␊ |
795 | #define␉rb_foreach_next(a_type, a_field, a_cmp, a_tree, a_node)␉␉\␊ |
796 | /* Re-initialize the path to contain the path to a_node. */\␊ |
797 | rbp_f_depth = 0;␉␉␉␉␉␉\␊ |
798 | if (a_node != NULL) {␉␉␉␉␉\␊ |
799 | if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {␉␉\␊ |
800 | rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;␉\␊ |
801 | rbp_f_depth++;␉␉␉␉␉\␊ |
802 | rbp_f_node = rbp_f_path[0];␉␉␉␉\␊ |
803 | while (true) {␉␉␉␉␉\␊ |
804 | int rbp_f_cmp = (a_cmp)((a_node),␉␉\␊ |
805 | rbp_f_path[rbp_f_depth-1]);␉␉␉\␊ |
806 | if (rbp_f_cmp < 0) {␉␉␉␉\␊ |
807 | rbp_f_node = rbp_left_get(a_type, a_field,␉\␊ |
808 | rbp_f_path[rbp_f_depth-1]);␉␉\␊ |
809 | } else if (rbp_f_cmp > 0) {␉␉␉\␊ |
810 | rbp_f_node = rbp_right_get(a_type, a_field,␉\␊ |
811 | rbp_f_path[rbp_f_depth-1]);␉␉\␊ |
812 | } else {␉␉␉␉␉\␊ |
813 | break;␉␉␉␉␉\␊ |
814 | }␉␉␉␉␉␉\␊ |
815 | assert(rbp_f_node != &(a_tree)->rbt_nil);␉\␊ |
816 | rbp_f_path[rbp_f_depth] = rbp_f_node;␉␉\␊ |
817 | rbp_f_depth++;␉␉␉␉␉\␊ |
818 | }␉␉␉␉␉␉␉\␊ |
819 | }␉␉␉␉␉␉␉\␊ |
820 | }␉␉␉␉␉␉␉␉\␊ |
821 | rbp_f_synced = true;␊ |
822 | ␊ |
823 | #define␉rb_foreach_end(a_type, a_field, a_tree, a_var)␉␉␉\␊ |
824 | if (rbp_f_synced) {␉␉␉␉␉␉\␊ |
825 | rbp_f_synced = false;␉␉␉␉␉\␊ |
826 | continue;␉␉␉␉␉␉\␊ |
827 | }␉␉␉␉␉␉␉␉\␊ |
828 | /* Find the successor. */\␊ |
829 | if ((rbp_f_node = rbp_right_get(a_type, a_field,␉␉\␊ |
830 | rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {␉\␊ |
831 | /* The successor is the left-most node in the right */\␊ |
832 | /* subtree. */\␊ |
833 | rbp_f_path[rbp_f_depth] = rbp_f_node;␉␉␉\␊ |
834 | rbp_f_depth++;␉␉␉␉␉␉\␊ |
835 | while ((rbp_f_node = rbp_left_get(a_type, a_field,␉\␊ |
836 | rbp_f_path[rbp_f_depth-1])) != &(a_tree)->rbt_nil) {␉\␊ |
837 | rbp_f_path[rbp_f_depth] = rbp_f_node;␉␉\␊ |
838 | rbp_f_depth++;␉␉␉␉␉\␊ |
839 | }␉␉␉␉␉␉␉\␊ |
840 | } else {␉␉␉␉␉␉␉\␊ |
841 | /* The successor is above the current node. Unwind */\␊ |
842 | /* until a left-leaning edge is removed from the */\␊ |
843 | /* path, or the path is empty. */\␊ |
844 | for (rbp_f_depth--; rbp_f_depth > 0; rbp_f_depth--) {␉\␊ |
845 | if (rbp_left_get(a_type, a_field,␉␉␉\␊ |
846 | rbp_f_path[rbp_f_depth-1])␉␉␉\␊ |
847 | == rbp_f_path[rbp_f_depth]) {␉␉␉\␊ |
848 | break;␉␉␉␉␉␉\␊ |
849 | }␉␉␉␉␉␉␉\␊ |
850 | }␉␉␉␉␉␉␉\␊ |
851 | }␉␉␉␉␉␉␉␉\␊ |
852 | }␉␉␉␉␉␉␉␉\␊ |
853 | }␉␉␉␉␉␉␉␉␉\␊ |
854 | }␊ |
855 | ␊ |
856 | #define␉rb_foreach_reverse_begin(a_type, a_field, a_tree, a_var) {␉\␊ |
857 | /* Compute the maximum possible tree depth (3X the black height). */\␊ |
858 | unsigned rbp_fr_height;␉␉␉␉␉␉\␊ |
859 | rbp_black_height(a_type, a_field, a_tree, rbp_fr_height);␉␉\␊ |
860 | rbp_fr_height *= 3;␉␉␉␉␉␉␉\␊ |
861 | {␉␉␉␉␉␉␉␉␉\␊ |
862 | /* Initialize the path to contain the right spine. */\␊ |
863 | a_type *rbp_fr_path[rbp_fr_height];␉␉␉␉\␊ |
864 | a_type *rbp_fr_node;␉␉␉␉␉␉\␊ |
865 | bool rbp_fr_synced = false;␉␉␉␉␉\␊ |
866 | unsigned rbp_fr_depth = 0;␉␉␉␉␉\␊ |
867 | if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {␉␉␉\␊ |
868 | rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root;␉␉\␊ |
869 | rbp_fr_depth++;␉␉␉␉␉␉\␊ |
870 | while ((rbp_fr_node = rbp_right_get(a_type, a_field,␉\␊ |
871 | rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {␉\␊ |
872 | rbp_fr_path[rbp_fr_depth] = rbp_fr_node;␉␉\␊ |
873 | rbp_fr_depth++;␉␉␉␉␉␉\␊ |
874 | }␉␉␉␉␉␉␉␉\␊ |
875 | }␉␉␉␉␉␉␉␉\␊ |
876 | /* While the path is non-empty, iterate. */\␊ |
877 | while (rbp_fr_depth > 0) {␉␉␉␉␉\␊ |
878 | (a_var) = rbp_fr_path[rbp_fr_depth-1];␊ |
879 | ␊ |
880 | /* Only use if modifying the tree during iteration. */␊ |
881 | #define␉rb_foreach_reverse_prev(a_type, a_field, a_cmp, a_tree, a_node)␉\␊ |
882 | /* Re-initialize the path to contain the path to a_node. */\␊ |
883 | rbp_fr_depth = 0;␉␉␉␉␉␉\␊ |
884 | if (a_node != NULL) {␉␉␉␉␉\␊ |
885 | if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {␉␉\␊ |
886 | rbp_fr_path[rbp_fr_depth] = (a_tree)->rbt_root;␉\␊ |
887 | rbp_fr_depth++;␉␉␉␉␉\␊ |
888 | rbp_fr_node = rbp_fr_path[0];␉␉␉\␊ |
889 | while (true) {␉␉␉␉␉\␊ |
890 | int rbp_fr_cmp = (a_cmp)((a_node),␉␉\␊ |
891 | rbp_fr_path[rbp_fr_depth-1]);␉␉␉\␊ |
892 | if (rbp_fr_cmp < 0) {␉␉␉␉\␊ |
893 | rbp_fr_node = rbp_left_get(a_type, a_field,␉\␊ |
894 | rbp_fr_path[rbp_fr_depth-1]);␉␉\␊ |
895 | } else if (rbp_fr_cmp > 0) {␉␉␉\␊ |
896 | rbp_fr_node = rbp_right_get(a_type, a_field,\␊ |
897 | rbp_fr_path[rbp_fr_depth-1]);␉␉\␊ |
898 | } else {␉␉␉␉␉\␊ |
899 | break;␉␉␉␉␉\␊ |
900 | }␉␉␉␉␉␉\␊ |
901 | assert(rbp_fr_node != &(a_tree)->rbt_nil);␉\␊ |
902 | rbp_fr_path[rbp_fr_depth] = rbp_fr_node;␉\␊ |
903 | rbp_fr_depth++;␉␉␉␉␉\␊ |
904 | }␉␉␉␉␉␉␉\␊ |
905 | }␉␉␉␉␉␉␉\␊ |
906 | }␉␉␉␉␉␉␉␉\␊ |
907 | rbp_fr_synced = true;␊ |
908 | ␊ |
909 | #define␉rb_foreach_reverse_end(a_type, a_field, a_tree, a_var)␉␉\␊ |
910 | if (rbp_fr_synced) {␉␉␉␉␉\␊ |
911 | rbp_fr_synced = false;␉␉␉␉␉\␊ |
912 | continue;␉␉␉␉␉␉\␊ |
913 | }␉␉␉␉␉␉␉␉\␊ |
914 | if (rbp_fr_depth == 0) {␉␉␉␉␉\␊ |
915 | /* rb_foreach_reverse_sync() was called with a NULL */\␊ |
916 | /* a_node. */\␊ |
917 | break;␉␉␉␉␉␉␉\␊ |
918 | }␉␉␉␉␉␉␉␉\␊ |
919 | /* Find the predecessor. */\␊ |
920 | if ((rbp_fr_node = rbp_left_get(a_type, a_field,␉␉\␊ |
921 | rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {␉\␊ |
922 | /* The predecessor is the right-most node in the left */\␊ |
923 | /* subtree. */\␊ |
924 | rbp_fr_path[rbp_fr_depth] = rbp_fr_node;␉␉\␊ |
925 | rbp_fr_depth++;␉␉␉␉␉␉\␊ |
926 | while ((rbp_fr_node = rbp_right_get(a_type, a_field,␉\␊ |
927 | rbp_fr_path[rbp_fr_depth-1])) != &(a_tree)->rbt_nil) {\␊ |
928 | rbp_fr_path[rbp_fr_depth] = rbp_fr_node;␉␉\␊ |
929 | rbp_fr_depth++;␉␉␉␉␉\␊ |
930 | }␉␉␉␉␉␉␉\␊ |
931 | } else {␉␉␉␉␉␉␉\␊ |
932 | /* The predecessor is above the current node. Unwind */\␊ |
933 | /* until a right-leaning edge is removed from the */\␊ |
934 | /* path, or the path is empty. */\␊ |
935 | for (rbp_fr_depth--; rbp_fr_depth > 0; rbp_fr_depth--) {\␊ |
936 | if (rbp_right_get(a_type, a_field,␉␉␉\␊ |
937 | rbp_fr_path[rbp_fr_depth-1])␉␉␉\␊ |
938 | == rbp_fr_path[rbp_fr_depth]) {␉␉␉\␊ |
939 | break;␉␉␉␉␉␉\␊ |
940 | }␉␉␉␉␉␉␉\␊ |
941 | }␉␉␉␉␉␉␉\␊ |
942 | }␉␉␉␉␉␉␉␉\␊ |
943 | }␉␉␉␉␉␉␉␉\␊ |
944 | }␉␉␉␉␉␉␉␉␉\␊ |
945 | }␊ |
946 | ␊ |
947 | #endif /* RB_H_ */ |