]>
Commit | Line | Data |
---|---|---|
04277e02 | 1 | /* Copyright (C) 1995-2019 Free Software Foundation, Inc. |
6d52618b | 2 | This file is part of the GNU C Library. |
993b3242 | 3 | Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997. |
60478656 | 4 | |
6d52618b | 5 | The GNU C Library is free software; you can redistribute it and/or |
41bdb6e2 AJ |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
60478656 | 9 | |
6d52618b UD |
10 | The GNU C Library is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
41bdb6e2 | 13 | Lesser General Public License for more details. |
60478656 | 14 | |
41bdb6e2 | 15 | You should have received a copy of the GNU Lesser General Public |
59ba27a6 | 16 | License along with the GNU C Library; if not, see |
5a82c748 | 17 | <https://www.gnu.org/licenses/>. */ |
60478656 | 18 | |
993b3242 UD |
19 | /* Tree search for red/black trees. |
20 | The algorithm for adding nodes is taken from one of the many "Algorithms" | |
21 | books by Robert Sedgewick, although the implementation differs. | |
22 | The algorithm for deleting nodes can probably be found in a book named | |
23 | "Introduction to Algorithms" by Cormen/Leiserson/Rivest. At least that's | |
24 | the book that my professor took most algorithms from during the "Data | |
25 | Structures" course... | |
1be6ec30 | 26 | |
60478656 | 27 | Totally public domain. */ |
993b3242 UD |
28 | |
29 | /* Red/black trees are binary trees in which the edges are colored either red | |
30 | or black. They have the following properties: | |
31 | 1. The number of black edges on every path from the root to a leaf is | |
32 | constant. | |
33 | 2. No two red edges are adjacent. | |
34 | Therefore there is an upper bound on the length of every path, it's | |
35 | O(log n) where n is the number of nodes in the tree. No path can be longer | |
36 | than 1+2*P where P is the length of the shortest path in the tree. | |
37 | Useful for the implementation: | |
38 | 3. If one of the children of a node is NULL, then the other one is red | |
39 | (if it exists). | |
40 | ||
41 | In the implementation, not the edges are colored, but the nodes. The color | |
42 | interpreted as the color of the edge leading to this node. The color is | |
43 | meaningless for the root node, but we color the root node black for | |
44 | convenience. All added nodes are red initially. | |
45 | ||
46 | Adding to a red/black tree is rather easy. The right place is searched | |
47 | with a usual binary tree search. Additionally, whenever a node N is | |
48 | reached that has two red successors, the successors are colored black and | |
49 | the node itself colored red. This moves red edges up the tree where they | |
50 | pose less of a problem once we get to really insert the new node. Changing | |
51 | N's color to red may violate rule 2, however, so rotations may become | |
52 | necessary to restore the invariants. Adding a new red leaf may violate | |
53 | the same rule, so afterwards an additional check is run and the tree | |
54 | possibly rotated. | |
55 | ||
56 | Deleting is hairy. There are mainly two nodes involved: the node to be | |
57 | deleted (n1), and another node that is to be unchained from the tree (n2). | |
58 | If n1 has a successor (the node with a smallest key that is larger than | |
59 | n1), then the successor becomes n2 and its contents are copied into n1, | |
60 | otherwise n1 becomes n2. | |
61 | Unchaining a node may violate rule 1: if n2 is black, one subtree is | |
62 | missing one black edge afterwards. The algorithm must try to move this | |
63 | error upwards towards the root, so that the subtree that does not have | |
64 | enough black edges becomes the whole tree. Once that happens, the error | |
65 | has disappeared. It may not be necessary to go all the way up, since it | |
66 | is possible that rotations and recoloring can fix the error before that. | |
67 | ||
68 | Although the deletion algorithm must walk upwards through the tree, we | |
69 | do not store parent pointers in the nodes. Instead, delete allocates a | |
70 | small array of parent pointers and fills it while descending the tree. | |
71 | Since we know that the length of a path is O(log n), where n is the number | |
72 | of nodes, this is likely to use less memory. */ | |
73 | ||
74 | /* Tree rotations look like this: | |
75 | A C | |
76 | / \ / \ | |
77 | B C A G | |
78 | / \ / \ --> / \ | |
79 | D E F G B F | |
80 | / \ | |
81 | D E | |
82 | ||
83 | In this case, A has been rotated left. This preserves the ordering of the | |
84 | binary tree. */ | |
60478656 | 85 | |
9d6861b8 MW |
86 | #include <assert.h> |
87 | #include <stdalign.h> | |
88 | #include <stddef.h> | |
60478656 | 89 | #include <stdlib.h> |
f671aeab | 90 | #include <string.h> |
60478656 RM |
91 | #include <search.h> |
92 | ||
9d6861b8 MW |
93 | /* Assume malloc returns naturally aligned (alignof (max_align_t)) |
94 | pointers so we can use the low bits to store some extra info. This | |
95 | works for the left/right node pointers since they are not user | |
96 | visible and always allocated by malloc. The user provides the key | |
97 | pointer and so that can point anywhere and doesn't have to be | |
98 | aligned. */ | |
99 | #define USE_MALLOC_LOW_BIT 1 | |
100 | ||
101 | #ifndef USE_MALLOC_LOW_BIT | |
102 | typedef struct node_t | |
103 | { | |
104 | /* Callers expect this to be the first element in the structure - do not | |
105 | move! */ | |
106 | const void *key; | |
107 | struct node_t *left_node; | |
108 | struct node_t *right_node; | |
109 | unsigned int is_red:1; | |
110 | } *node; | |
111 | ||
112 | #define RED(N) (N)->is_red | |
113 | #define SETRED(N) (N)->is_red = 1 | |
114 | #define SETBLACK(N) (N)->is_red = 0 | |
115 | #define SETNODEPTR(NP,P) (*NP) = (P) | |
116 | #define LEFT(N) (N)->left_node | |
117 | #define LEFTPTR(N) (&(N)->left_node) | |
118 | #define SETLEFT(N,L) (N)->left_node = (L) | |
119 | #define RIGHT(N) (N)->right_node | |
120 | #define RIGHTPTR(N) (&(N)->right_node) | |
121 | #define SETRIGHT(N,R) (N)->right_node = (R) | |
122 | #define DEREFNODEPTR(NP) (*(NP)) | |
123 | ||
124 | #else /* USE_MALLOC_LOW_BIT */ | |
125 | ||
60478656 RM |
126 | typedef struct node_t |
127 | { | |
993b3242 UD |
128 | /* Callers expect this to be the first element in the structure - do not |
129 | move! */ | |
60478656 | 130 | const void *key; |
9d6861b8 MW |
131 | uintptr_t left_node; /* Includes whether the node is red in low-bit. */ |
132 | uintptr_t right_node; | |
993b3242 | 133 | } *node; |
9d6861b8 MW |
134 | |
135 | #define RED(N) (node)((N)->left_node & ((uintptr_t) 0x1)) | |
136 | #define SETRED(N) (N)->left_node |= ((uintptr_t) 0x1) | |
137 | #define SETBLACK(N) (N)->left_node &= ~((uintptr_t) 0x1) | |
138 | #define SETNODEPTR(NP,P) (*NP) = (node)((((uintptr_t)(*NP)) \ | |
139 | & (uintptr_t) 0x1) | (uintptr_t)(P)) | |
140 | #define LEFT(N) (node)((N)->left_node & ~((uintptr_t) 0x1)) | |
141 | #define LEFTPTR(N) (node *)(&(N)->left_node) | |
142 | #define SETLEFT(N,L) (N)->left_node = (((N)->left_node & (uintptr_t) 0x1) \ | |
143 | | (uintptr_t)(L)) | |
144 | #define RIGHT(N) (node)((N)->right_node) | |
145 | #define RIGHTPTR(N) (node *)(&(N)->right_node) | |
146 | #define SETRIGHT(N,R) (N)->right_node = (uintptr_t)(R) | |
147 | #define DEREFNODEPTR(NP) (node)((uintptr_t)(*(NP)) & ~((uintptr_t) 0x1)) | |
148 | ||
149 | #endif /* USE_MALLOC_LOW_BIT */ | |
2a068d20 | 150 | typedef const struct node_t *const_node; |
993b3242 UD |
151 | |
152 | #undef DEBUGGING | |
153 | ||
154 | #ifdef DEBUGGING | |
155 | ||
156 | /* Routines to check tree invariants. */ | |
157 | ||
993b3242 UD |
158 | #define CHECK_TREE(a) check_tree(a) |
159 | ||
160 | static void | |
161 | check_tree_recurse (node p, int d_sofar, int d_total) | |
162 | { | |
163 | if (p == NULL) | |
164 | { | |
165 | assert (d_sofar == d_total); | |
166 | return; | |
167 | } | |
168 | ||
9d6861b8 MW |
169 | check_tree_recurse (LEFT(p), d_sofar + (LEFT(p) && !RED(LEFT(p))), |
170 | d_total); | |
171 | check_tree_recurse (RIGHT(p), d_sofar + (RIGHT(p) && !RED(RIGHT(p))), | |
172 | d_total); | |
173 | if (LEFT(p)) | |
174 | assert (!(RED(LEFT(p)) && RED(p))); | |
175 | if (RIGHT(p)) | |
176 | assert (!(RED(RIGHT(p)) && RED(p))); | |
993b3242 UD |
177 | } |
178 | ||
179 | static void | |
180 | check_tree (node root) | |
181 | { | |
182 | int cnt = 0; | |
183 | node p; | |
184 | if (root == NULL) | |
185 | return; | |
9d6861b8 MW |
186 | SETBLACK(root); |
187 | for(p = LEFT(root); p; p = LEFT(p)) | |
188 | cnt += !RED(p); | |
993b3242 | 189 | check_tree_recurse (root, 0, cnt); |
60478656 | 190 | } |
60478656 | 191 | |
993b3242 | 192 | #else |
60478656 | 193 | |
993b3242 UD |
194 | #define CHECK_TREE(a) |
195 | ||
196 | #endif | |
197 | ||
198 | /* Possibly "split" a node with two red successors, and/or fix up two red | |
199 | edges in a row. ROOTP is a pointer to the lowest node we visited, PARENTP | |
200 | and GPARENTP pointers to its parent/grandparent. P_R and GP_R contain the | |
201 | comparison values that determined which way was taken in the tree to reach | |
202 | ROOTP. MODE is 1 if we need not do the split, but must check for two red | |
203 | edges between GPARENTP and ROOTP. */ | |
204 | static void | |
205 | maybe_split_for_insert (node *rootp, node *parentp, node *gparentp, | |
206 | int p_r, int gp_r, int mode) | |
207 | { | |
9d6861b8 | 208 | node root = DEREFNODEPTR(rootp); |
993b3242 | 209 | node *rp, *lp; |
9d6861b8 MW |
210 | node rpn, lpn; |
211 | rp = RIGHTPTR(root); | |
212 | rpn = RIGHT(root); | |
213 | lp = LEFTPTR(root); | |
214 | lpn = LEFT(root); | |
993b3242 UD |
215 | |
216 | /* See if we have to split this node (both successors red). */ | |
217 | if (mode == 1 | |
9d6861b8 | 218 | || ((rpn) != NULL && (lpn) != NULL && RED(rpn) && RED(lpn))) |
993b3242 UD |
219 | { |
220 | /* This node becomes red, its successors black. */ | |
9d6861b8 MW |
221 | SETRED(root); |
222 | if (rpn) | |
223 | SETBLACK(rpn); | |
224 | if (lpn) | |
225 | SETBLACK(lpn); | |
993b3242 UD |
226 | |
227 | /* If the parent of this node is also red, we have to do | |
228 | rotations. */ | |
9d6861b8 | 229 | if (parentp != NULL && RED(DEREFNODEPTR(parentp))) |
993b3242 | 230 | { |
9d6861b8 MW |
231 | node gp = DEREFNODEPTR(gparentp); |
232 | node p = DEREFNODEPTR(parentp); | |
993b3242 UD |
233 | /* There are two main cases: |
234 | 1. The edge types (left or right) of the two red edges differ. | |
235 | 2. Both red edges are of the same type. | |
236 | There exist two symmetries of each case, so there is a total of | |
237 | 4 cases. */ | |
238 | if ((p_r > 0) != (gp_r > 0)) | |
239 | { | |
240 | /* Put the child at the top of the tree, with its parent | |
241 | and grandparent as successors. */ | |
9d6861b8 MW |
242 | SETRED(p); |
243 | SETRED(gp); | |
244 | SETBLACK(root); | |
993b3242 UD |
245 | if (p_r < 0) |
246 | { | |
247 | /* Child is left of parent. */ | |
9d6861b8 MW |
248 | SETLEFT(p,rpn); |
249 | SETNODEPTR(rp,p); | |
250 | SETRIGHT(gp,lpn); | |
251 | SETNODEPTR(lp,gp); | |
993b3242 UD |
252 | } |
253 | else | |
254 | { | |
255 | /* Child is right of parent. */ | |
9d6861b8 MW |
256 | SETRIGHT(p,lpn); |
257 | SETNODEPTR(lp,p); | |
258 | SETLEFT(gp,rpn); | |
259 | SETNODEPTR(rp,gp); | |
993b3242 | 260 | } |
9d6861b8 | 261 | SETNODEPTR(gparentp,root); |
993b3242 UD |
262 | } |
263 | else | |
264 | { | |
9d6861b8 | 265 | SETNODEPTR(gparentp,p); |
993b3242 UD |
266 | /* Parent becomes the top of the tree, grandparent and |
267 | child are its successors. */ | |
9d6861b8 MW |
268 | SETBLACK(p); |
269 | SETRED(gp); | |
993b3242 UD |
270 | if (p_r < 0) |
271 | { | |
272 | /* Left edges. */ | |
9d6861b8 MW |
273 | SETLEFT(gp,RIGHT(p)); |
274 | SETRIGHT(p,gp); | |
993b3242 UD |
275 | } |
276 | else | |
277 | { | |
278 | /* Right edges. */ | |
9d6861b8 MW |
279 | SETRIGHT(gp,LEFT(p)); |
280 | SETLEFT(p,gp); | |
993b3242 UD |
281 | } |
282 | } | |
283 | } | |
284 | } | |
285 | } | |
286 | ||
287 | /* Find or insert datum into search tree. | |
288 | KEY is the key to be located, ROOTP is the address of tree root, | |
289 | COMPAR the ordering function. */ | |
60478656 | 290 | void * |
993b3242 | 291 | __tsearch (const void *key, void **vrootp, __compar_fn_t compar) |
60478656 | 292 | { |
9d6861b8 | 293 | node q, root; |
993b3242 UD |
294 | node *parentp = NULL, *gparentp = NULL; |
295 | node *rootp = (node *) vrootp; | |
296 | node *nextp; | |
297 | int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler. */ | |
60478656 | 298 | |
9d6861b8 MW |
299 | #ifdef USE_MALLOC_LOW_BIT |
300 | static_assert (alignof (max_align_t) > 1, "malloc must return aligned ptrs"); | |
301 | #endif | |
302 | ||
60478656 RM |
303 | if (rootp == NULL) |
304 | return NULL; | |
305 | ||
993b3242 | 306 | /* This saves some additional tests below. */ |
9d6861b8 MW |
307 | root = DEREFNODEPTR(rootp); |
308 | if (root != NULL) | |
309 | SETBLACK(root); | |
993b3242 | 310 | |
9d6861b8 | 311 | CHECK_TREE (root); |
60478656 | 312 | |
993b3242 | 313 | nextp = rootp; |
9d6861b8 | 314 | while (DEREFNODEPTR(nextp) != NULL) |
993b3242 | 315 | { |
9d6861b8 | 316 | root = DEREFNODEPTR(rootp); |
993b3242 UD |
317 | r = (*compar) (key, root->key); |
318 | if (r == 0) | |
319 | return root; | |
320 | ||
321 | maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0); | |
322 | /* If that did any rotations, parentp and gparentp are now garbage. | |
323 | That doesn't matter, because the values they contain are never | |
324 | used again in that case. */ | |
325 | ||
9d6861b8 MW |
326 | nextp = r < 0 ? LEFTPTR(root) : RIGHTPTR(root); |
327 | if (DEREFNODEPTR(nextp) == NULL) | |
993b3242 UD |
328 | break; |
329 | ||
330 | gparentp = parentp; | |
331 | parentp = rootp; | |
332 | rootp = nextp; | |
333 | ||
334 | gp_r = p_r; | |
335 | p_r = r; | |
60478656 RM |
336 | } |
337 | ||
993b3242 UD |
338 | q = (struct node_t *) malloc (sizeof (struct node_t)); |
339 | if (q != NULL) | |
60478656 | 340 | { |
9d6861b8 MW |
341 | /* Make sure the malloc implementation returns naturally aligned |
342 | memory blocks when expected. Or at least even pointers, so we | |
343 | can use the low bit as red/black flag. Even though we have a | |
344 | static_assert to make sure alignof (max_align_t) > 1 there could | |
345 | be an interposed malloc implementation that might cause havoc by | |
346 | not obeying the malloc contract. */ | |
347 | #ifdef USE_MALLOC_LOW_BIT | |
348 | assert (((uintptr_t) q & (uintptr_t) 0x1) == 0); | |
349 | #endif | |
350 | SETNODEPTR(nextp,q); /* link new node to old */ | |
60478656 | 351 | q->key = key; /* initialize new node */ |
9d6861b8 MW |
352 | SETRED(q); |
353 | SETLEFT(q,NULL); | |
354 | SETRIGHT(q,NULL); | |
cec40916 UD |
355 | |
356 | if (nextp != rootp) | |
357 | /* There may be two red edges in a row now, which we must avoid by | |
358 | rotating the tree. */ | |
359 | maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1); | |
60478656 RM |
360 | } |
361 | ||
362 | return q; | |
363 | } | |
d051b143 | 364 | libc_hidden_def (__tsearch) |
1be6ec30 | 365 | weak_alias (__tsearch, tsearch) |
60478656 RM |
366 | |
367 | ||
993b3242 UD |
368 | /* Find datum in search tree. |
369 | KEY is the key to be located, ROOTP is the address of tree root, | |
370 | COMPAR the ordering function. */ | |
60478656 | 371 | void * |
9dd346ff | 372 | __tfind (const void *key, void *const *vrootp, __compar_fn_t compar) |
60478656 | 373 | { |
9d6861b8 | 374 | node root; |
993b3242 | 375 | node *rootp = (node *) vrootp; |
60478656 RM |
376 | |
377 | if (rootp == NULL) | |
378 | return NULL; | |
379 | ||
9d6861b8 MW |
380 | root = DEREFNODEPTR(rootp); |
381 | CHECK_TREE (root); | |
993b3242 | 382 | |
9d6861b8 | 383 | while (DEREFNODEPTR(rootp) != NULL) |
60478656 | 384 | { |
9d6861b8 | 385 | root = DEREFNODEPTR(rootp); |
60478656 RM |
386 | int r; |
387 | ||
993b3242 UD |
388 | r = (*compar) (key, root->key); |
389 | if (r == 0) | |
390 | return root; | |
60478656 | 391 | |
9d6861b8 | 392 | rootp = r < 0 ? LEFTPTR(root) : RIGHTPTR(root); |
60478656 | 393 | } |
993b3242 | 394 | return NULL; |
60478656 | 395 | } |
d051b143 | 396 | libc_hidden_def (__tfind) |
1be6ec30 | 397 | weak_alias (__tfind, tfind) |
60478656 RM |
398 | |
399 | ||
993b3242 UD |
400 | /* Delete node with given key. |
401 | KEY is the key to be deleted, ROOTP is the address of the root of tree, | |
402 | COMPAR the comparison function. */ | |
60478656 | 403 | void * |
993b3242 | 404 | __tdelete (const void *key, void **vrootp, __compar_fn_t compar) |
60478656 | 405 | { |
993b3242 | 406 | node p, q, r, retval; |
60478656 | 407 | int cmp; |
993b3242 UD |
408 | node *rootp = (node *) vrootp; |
409 | node root, unchained; | |
410 | /* Stack of nodes so we remember the parents without recursion. It's | |
411 | _very_ unlikely that there are paths longer than 40 nodes. The tree | |
412 | would need to have around 250.000 nodes. */ | |
413 | int stacksize = 40; | |
414 | int sp = 0; | |
415 | node **nodestack = alloca (sizeof (node *) * stacksize); | |
60478656 | 416 | |
993b3242 | 417 | if (rootp == NULL) |
60478656 | 418 | return NULL; |
9d6861b8 | 419 | p = DEREFNODEPTR(rootp); |
993b3242 UD |
420 | if (p == NULL) |
421 | return NULL; | |
422 | ||
423 | CHECK_TREE (p); | |
60478656 | 424 | |
9d6861b8 MW |
425 | root = DEREFNODEPTR(rootp); |
426 | while ((cmp = (*compar) (key, root->key)) != 0) | |
60478656 | 427 | { |
993b3242 UD |
428 | if (sp == stacksize) |
429 | { | |
430 | node **newstack; | |
431 | stacksize += 20; | |
432 | newstack = alloca (sizeof (node *) * stacksize); | |
86187531 | 433 | nodestack = memcpy (newstack, nodestack, sp * sizeof (node *)); |
993b3242 UD |
434 | } |
435 | ||
436 | nodestack[sp++] = rootp; | |
9d6861b8 MW |
437 | p = DEREFNODEPTR(rootp); |
438 | if (cmp < 0) | |
439 | { | |
440 | rootp = LEFTPTR(p); | |
441 | root = LEFT(p); | |
442 | } | |
443 | else | |
444 | { | |
445 | rootp = RIGHTPTR(p); | |
446 | root = RIGHT(p); | |
447 | } | |
448 | if (root == NULL) | |
993b3242 | 449 | return NULL; |
60478656 RM |
450 | } |
451 | ||
993b3242 UD |
452 | /* This is bogus if the node to be deleted is the root... this routine |
453 | really should return an integer with 0 for success, -1 for failure | |
454 | and errno = ESRCH or something. */ | |
455 | retval = p; | |
456 | ||
457 | /* We don't unchain the node we want to delete. Instead, we overwrite | |
458 | it with its successor and unchain the successor. If there is no | |
459 | successor, we really unchain the node to be deleted. */ | |
460 | ||
9d6861b8 | 461 | root = DEREFNODEPTR(rootp); |
993b3242 | 462 | |
9d6861b8 MW |
463 | r = RIGHT(root); |
464 | q = LEFT(root); | |
993b3242 UD |
465 | |
466 | if (q == NULL || r == NULL) | |
467 | unchained = root; | |
468 | else | |
60478656 | 469 | { |
9d6861b8 MW |
470 | node *parentp = rootp, *up = RIGHTPTR(root); |
471 | node upn; | |
993b3242 | 472 | for (;;) |
60478656 | 473 | { |
993b3242 UD |
474 | if (sp == stacksize) |
475 | { | |
476 | node **newstack; | |
477 | stacksize += 20; | |
478 | newstack = alloca (sizeof (node *) * stacksize); | |
86187531 | 479 | nodestack = memcpy (newstack, nodestack, sp * sizeof (node *)); |
993b3242 | 480 | } |
9d6861b8 MW |
481 | nodestack[sp++] = parentp; |
482 | parentp = up; | |
483 | upn = DEREFNODEPTR(up); | |
484 | if (LEFT(upn) == NULL) | |
993b3242 | 485 | break; |
9d6861b8 | 486 | up = LEFTPTR(upn); |
60478656 | 487 | } |
9d6861b8 | 488 | unchained = DEREFNODEPTR(up); |
993b3242 UD |
489 | } |
490 | ||
491 | /* We know that either the left or right successor of UNCHAINED is NULL. | |
492 | R becomes the other one, it is chained into the parent of UNCHAINED. */ | |
9d6861b8 | 493 | r = LEFT(unchained); |
993b3242 | 494 | if (r == NULL) |
9d6861b8 | 495 | r = RIGHT(unchained); |
993b3242 | 496 | if (sp == 0) |
9d6861b8 | 497 | SETNODEPTR(rootp,r); |
993b3242 UD |
498 | else |
499 | { | |
9d6861b8 MW |
500 | q = DEREFNODEPTR(nodestack[sp-1]); |
501 | if (unchained == RIGHT(q)) | |
502 | SETRIGHT(q,r); | |
60478656 | 503 | else |
9d6861b8 | 504 | SETLEFT(q,r); |
993b3242 UD |
505 | } |
506 | ||
507 | if (unchained != root) | |
508 | root->key = unchained->key; | |
9d6861b8 | 509 | if (!RED(unchained)) |
993b3242 UD |
510 | { |
511 | /* Now we lost a black edge, which means that the number of black | |
512 | edges on every path is no longer constant. We must balance the | |
513 | tree. */ | |
514 | /* NODESTACK now contains all parents of R. R is likely to be NULL | |
515 | in the first iteration. */ | |
516 | /* NULL nodes are considered black throughout - this is necessary for | |
517 | correctness. */ | |
9d6861b8 | 518 | while (sp > 0 && (r == NULL || !RED(r))) |
993b3242 UD |
519 | { |
520 | node *pp = nodestack[sp - 1]; | |
9d6861b8 | 521 | p = DEREFNODEPTR(pp); |
993b3242 | 522 | /* Two symmetric cases. */ |
9d6861b8 | 523 | if (r == LEFT(p)) |
993b3242 UD |
524 | { |
525 | /* Q is R's brother, P is R's parent. The subtree with root | |
526 | R has one black edge less than the subtree with root Q. */ | |
9d6861b8 MW |
527 | q = RIGHT(p); |
528 | if (RED(q)) | |
993b3242 UD |
529 | { |
530 | /* If Q is red, we know that P is black. We rotate P left | |
531 | so that Q becomes the top node in the tree, with P below | |
532 | it. P is colored red, Q is colored black. | |
533 | This action does not change the black edge count for any | |
534 | leaf in the tree, but we will be able to recognize one | |
535 | of the following situations, which all require that Q | |
536 | is black. */ | |
9d6861b8 MW |
537 | SETBLACK(q); |
538 | SETRED(p); | |
993b3242 | 539 | /* Left rotate p. */ |
9d6861b8 MW |
540 | SETRIGHT(p,LEFT(q)); |
541 | SETLEFT(q,p); | |
542 | SETNODEPTR(pp,q); | |
993b3242 UD |
543 | /* Make sure pp is right if the case below tries to use |
544 | it. */ | |
9d6861b8 MW |
545 | nodestack[sp++] = pp = LEFTPTR(q); |
546 | q = RIGHT(p); | |
993b3242 UD |
547 | } |
548 | /* We know that Q can't be NULL here. We also know that Q is | |
549 | black. */ | |
9d6861b8 MW |
550 | if ((LEFT(q) == NULL || !RED(LEFT(q))) |
551 | && (RIGHT(q) == NULL || !RED(RIGHT(q)))) | |
993b3242 UD |
552 | { |
553 | /* Q has two black successors. We can simply color Q red. | |
554 | The whole subtree with root P is now missing one black | |
555 | edge. Note that this action can temporarily make the | |
556 | tree invalid (if P is red). But we will exit the loop | |
557 | in that case and set P black, which both makes the tree | |
558 | valid and also makes the black edge count come out | |
559 | right. If P is black, we are at least one step closer | |
560 | to the root and we'll try again the next iteration. */ | |
9d6861b8 | 561 | SETRED(q); |
993b3242 UD |
562 | r = p; |
563 | } | |
564 | else | |
565 | { | |
566 | /* Q is black, one of Q's successors is red. We can | |
567 | repair the tree with one operation and will exit the | |
568 | loop afterwards. */ | |
9d6861b8 | 569 | if (RIGHT(q) == NULL || !RED(RIGHT(q))) |
993b3242 UD |
570 | { |
571 | /* The left one is red. We perform the same action as | |
572 | in maybe_split_for_insert where two red edges are | |
573 | adjacent but point in different directions: | |
574 | Q's left successor (let's call it Q2) becomes the | |
575 | top of the subtree we are looking at, its parent (Q) | |
576 | and grandparent (P) become its successors. The former | |
577 | successors of Q2 are placed below P and Q. | |
578 | P becomes black, and Q2 gets the color that P had. | |
579 | This changes the black edge count only for node R and | |
580 | its successors. */ | |
9d6861b8 MW |
581 | node q2 = LEFT(q); |
582 | if (RED(p)) | |
583 | SETRED(q2); | |
584 | else | |
585 | SETBLACK(q2); | |
586 | SETRIGHT(p,LEFT(q2)); | |
587 | SETLEFT(q,RIGHT(q2)); | |
588 | SETRIGHT(q2,q); | |
589 | SETLEFT(q2,p); | |
590 | SETNODEPTR(pp,q2); | |
591 | SETBLACK(p); | |
993b3242 UD |
592 | } |
593 | else | |
594 | { | |
595 | /* It's the right one. Rotate P left. P becomes black, | |
596 | and Q gets the color that P had. Q's right successor | |
597 | also becomes black. This changes the black edge | |
598 | count only for node R and its successors. */ | |
9d6861b8 MW |
599 | if (RED(p)) |
600 | SETRED(q); | |
601 | else | |
602 | SETBLACK(q); | |
603 | SETBLACK(p); | |
993b3242 | 604 | |
9d6861b8 | 605 | SETBLACK(RIGHT(q)); |
993b3242 UD |
606 | |
607 | /* left rotate p */ | |
9d6861b8 MW |
608 | SETRIGHT(p,LEFT(q)); |
609 | SETLEFT(q,p); | |
610 | SETNODEPTR(pp,q); | |
993b3242 UD |
611 | } |
612 | ||
613 | /* We're done. */ | |
614 | sp = 1; | |
615 | r = NULL; | |
616 | } | |
617 | } | |
618 | else | |
619 | { | |
620 | /* Comments: see above. */ | |
9d6861b8 MW |
621 | q = LEFT(p); |
622 | if (RED(q)) | |
993b3242 | 623 | { |
9d6861b8 MW |
624 | SETBLACK(q); |
625 | SETRED(p); | |
626 | SETLEFT(p,RIGHT(q)); | |
627 | SETRIGHT(q,p); | |
628 | SETNODEPTR(pp,q); | |
629 | nodestack[sp++] = pp = RIGHTPTR(q); | |
630 | q = LEFT(p); | |
993b3242 | 631 | } |
9d6861b8 MW |
632 | if ((RIGHT(q) == NULL || !RED(RIGHT(q))) |
633 | && (LEFT(q) == NULL || !RED(LEFT(q)))) | |
993b3242 | 634 | { |
9d6861b8 | 635 | SETRED(q); |
993b3242 UD |
636 | r = p; |
637 | } | |
638 | else | |
639 | { | |
9d6861b8 | 640 | if (LEFT(q) == NULL || !RED(LEFT(q))) |
993b3242 | 641 | { |
9d6861b8 MW |
642 | node q2 = RIGHT(q); |
643 | if (RED(p)) | |
644 | SETRED(q2); | |
645 | else | |
646 | SETBLACK(q2); | |
647 | SETLEFT(p,RIGHT(q2)); | |
648 | SETRIGHT(q,LEFT(q2)); | |
649 | SETLEFT(q2,q); | |
650 | SETRIGHT(q2,p); | |
651 | SETNODEPTR(pp,q2); | |
652 | SETBLACK(p); | |
993b3242 UD |
653 | } |
654 | else | |
655 | { | |
9d6861b8 MW |
656 | if (RED(p)) |
657 | SETRED(q); | |
658 | else | |
659 | SETBLACK(q); | |
660 | SETBLACK(p); | |
661 | SETBLACK(LEFT(q)); | |
662 | SETLEFT(p,RIGHT(q)); | |
663 | SETRIGHT(q,p); | |
664 | SETNODEPTR(pp,q); | |
993b3242 UD |
665 | } |
666 | sp = 1; | |
667 | r = NULL; | |
668 | } | |
669 | } | |
670 | --sp; | |
60478656 | 671 | } |
993b3242 | 672 | if (r != NULL) |
9d6861b8 | 673 | SETBLACK(r); |
60478656 | 674 | } |
993b3242 UD |
675 | |
676 | free (unchained); | |
677 | return retval; | |
60478656 | 678 | } |
d051b143 | 679 | libc_hidden_def (__tdelete) |
4f54cdb1 | 680 | weak_alias (__tdelete, tdelete) |
60478656 RM |
681 | |
682 | ||
993b3242 UD |
683 | /* Walk the nodes of a tree. |
684 | ROOT is the root of the tree to be walked, ACTION the function to be | |
685 | called at each node. LEVEL is the level of ROOT in the whole tree. */ | |
60478656 | 686 | static void |
993b3242 | 687 | trecurse (const void *vroot, __action_fn_t action, int level) |
60478656 | 688 | { |
2a068d20 | 689 | const_node root = (const_node) vroot; |
60478656 | 690 | |
9d6861b8 | 691 | if (LEFT(root) == NULL && RIGHT(root) == NULL) |
60478656 RM |
692 | (*action) (root, leaf, level); |
693 | else | |
694 | { | |
695 | (*action) (root, preorder, level); | |
9d6861b8 MW |
696 | if (LEFT(root) != NULL) |
697 | trecurse (LEFT(root), action, level + 1); | |
60478656 | 698 | (*action) (root, postorder, level); |
9d6861b8 MW |
699 | if (RIGHT(root) != NULL) |
700 | trecurse (RIGHT(root), action, level + 1); | |
60478656 RM |
701 | (*action) (root, endorder, level); |
702 | } | |
703 | } | |
704 | ||
705 | ||
993b3242 UD |
706 | /* Walk the nodes of a tree. |
707 | ROOT is the root of the tree to be walked, ACTION the function to be | |
708 | called at each node. */ | |
60478656 | 709 | void |
993b3242 | 710 | __twalk (const void *vroot, __action_fn_t action) |
60478656 | 711 | { |
2a068d20 | 712 | const_node root = (const_node) vroot; |
993b3242 | 713 | |
9d6861b8 | 714 | CHECK_TREE ((node) root); |
60478656 RM |
715 | |
716 | if (root != NULL && action != NULL) | |
717 | trecurse (root, action, 0); | |
718 | } | |
d051b143 | 719 | libc_hidden_def (__twalk) |
1be6ec30 | 720 | weak_alias (__twalk, twalk) |
d951286f | 721 | |
7b807a35 FW |
722 | /* twalk_r is the same as twalk, but with a closure parameter instead |
723 | of the level. */ | |
724 | static void | |
725 | trecurse_r (const void *vroot, void (*action) (const void *, VISIT, void *), | |
726 | void *closure) | |
727 | { | |
728 | const_node root = (const_node) vroot; | |
d951286f | 729 | |
7b807a35 FW |
730 | if (LEFT(root) == NULL && RIGHT(root) == NULL) |
731 | (*action) (root, leaf, closure); | |
732 | else | |
733 | { | |
734 | (*action) (root, preorder, closure); | |
735 | if (LEFT(root) != NULL) | |
736 | trecurse_r (LEFT(root), action, closure); | |
737 | (*action) (root, postorder, closure); | |
738 | if (RIGHT(root) != NULL) | |
739 | trecurse_r (RIGHT(root), action, closure); | |
740 | (*action) (root, endorder, closure); | |
741 | } | |
742 | } | |
743 | ||
744 | void | |
745 | __twalk_r (const void *vroot, void (*action) (const void *, VISIT, void *), | |
746 | void *closure) | |
747 | { | |
748 | const_node root = (const_node) vroot; | |
749 | ||
750 | CHECK_TREE ((node) root); | |
751 | ||
752 | if (root != NULL && action != NULL) | |
753 | trecurse_r (root, action, closure); | |
754 | } | |
755 | libc_hidden_def (__twalk_r) | |
756 | weak_alias (__twalk_r, twalk_r) | |
d951286f UD |
757 | |
758 | /* The standardized functions miss an important functionality: the | |
759 | tree cannot be removed easily. We provide a function to do this. */ | |
760 | static void | |
761 | tdestroy_recurse (node root, __free_fn_t freefct) | |
762 | { | |
9d6861b8 MW |
763 | if (LEFT(root) != NULL) |
764 | tdestroy_recurse (LEFT(root), freefct); | |
765 | if (RIGHT(root) != NULL) | |
766 | tdestroy_recurse (RIGHT(root), freefct); | |
f671aeab | 767 | (*freefct) ((void *) root->key); |
d951286f UD |
768 | /* Free the node itself. */ |
769 | free (root); | |
770 | } | |
771 | ||
772 | void | |
773 | __tdestroy (void *vroot, __free_fn_t freefct) | |
774 | { | |
775 | node root = (node) vroot; | |
776 | ||
777 | CHECK_TREE (root); | |
778 | ||
779 | if (root != NULL) | |
780 | tdestroy_recurse (root, freefct); | |
781 | } | |
fe84fed0 | 782 | libc_hidden_def (__tdestroy) |
d951286f | 783 | weak_alias (__tdestroy, tdestroy) |