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