Mercurial > gnulib
annotate lib/tsearch.c @ 17326:bb52d9cece01
unsetenv etc.: port to Solaris 11 + GNU Emacs
* lib/canonicalize-lgpl.c, lib/getaddrinfo.c, lib/getdelim.c:
* lib/glob.c, lib/random_r.c, lib/setenv.c, lib/tsearch.c:
* lib/unsetenv.c (_GL_ARG_NONNULL): Define before including <config.h>.
GNU Emacs's <config.h> includes <stdlib.h> (which is not a great
idea but is too painful to fix right now), and without this gnulib
change <stdlib.h> was defining _GL_ARG_NONNULL incorrectly when
compiling unsetenv.c on Solaris 11. Fix the problem for
unsetenv.c, and fix other similar occurrences.
| author | Paul Eggert <eggert@cs.ucla.edu> |
|---|---|
| date | Mon, 11 Feb 2013 14:58:56 -0800 |
| parents | e542fd46ad6f |
| children | 344018b6e5d7 |
| rev | line source |
|---|---|
|
17249
e542fd46ad6f
maint: update all copyright year number ranges
Eric Blake <eblake@redhat.com>
parents:
16201
diff
changeset
|
1 /* Copyright (C) 1995-1997, 2000, 2006-2007, 2009-2013 Free Software |
|
12559
c2cbabec01dd
update nearly all FSF copyright year lists to include 2010
Jim Meyering <meyering@redhat.com>
parents:
12422
diff
changeset
|
2 Foundation, Inc. |
| 7585 | 3 Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997. |
| 4 | |
| 5 NOTE: The canonical source of this file is maintained with the GNU C | |
| 6 Library. Bugs can be reported to bug-glibc@gnu.org. | |
| 7 | |
|
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8532
diff
changeset
|
8 This program is free software: you can redistribute it and/or modify it |
| 7585 | 9 under the terms of the GNU General Public License as published by the |
|
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8532
diff
changeset
|
10 Free Software Foundation; either version 3 of the License, or any |
| 7585 | 11 later version. |
| 12 | |
| 13 This program is distributed in the hope that it will be useful, | |
| 14 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 16 GNU General Public License for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
|
9309
bbbbbf4cd1c5
Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents:
8532
diff
changeset
|
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
| 7585 | 20 |
| 21 /* Tree search for red/black trees. | |
| 22 The algorithm for adding nodes is taken from one of the many "Algorithms" | |
| 23 books by Robert Sedgewick, although the implementation differs. | |
| 24 The algorithm for deleting nodes can probably be found in a book named | |
| 25 "Introduction to Algorithms" by Cormen/Leiserson/Rivest. At least that's | |
| 26 the book that my professor took most algorithms from during the "Data | |
| 27 Structures" course... | |
| 28 | |
| 29 Totally public domain. */ | |
| 30 | |
| 31 /* Red/black trees are binary trees in which the edges are colored either red | |
| 32 or black. They have the following properties: | |
| 33 1. The number of black edges on every path from the root to a leaf is | |
| 34 constant. | |
| 35 2. No two red edges are adjacent. | |
| 36 Therefore there is an upper bound on the length of every path, it's | |
| 37 O(log n) where n is the number of nodes in the tree. No path can be longer | |
| 38 than 1+2*P where P is the length of the shortest path in the tree. | |
| 39 Useful for the implementation: | |
| 40 3. If one of the children of a node is NULL, then the other one is red | |
| 41 (if it exists). | |
| 42 | |
| 43 In the implementation, not the edges are colored, but the nodes. The color | |
| 44 interpreted as the color of the edge leading to this node. The color is | |
| 45 meaningless for the root node, but we color the root node black for | |
| 46 convenience. All added nodes are red initially. | |
| 47 | |
| 48 Adding to a red/black tree is rather easy. The right place is searched | |
| 49 with a usual binary tree search. Additionally, whenever a node N is | |
| 50 reached that has two red successors, the successors are colored black and | |
| 51 the node itself colored red. This moves red edges up the tree where they | |
| 52 pose less of a problem once we get to really insert the new node. Changing | |
| 53 N's color to red may violate rule 2, however, so rotations may become | |
| 54 necessary to restore the invariants. Adding a new red leaf may violate | |
| 55 the same rule, so afterwards an additional check is run and the tree | |
| 56 possibly rotated. | |
| 57 | |
| 58 Deleting is hairy. There are mainly two nodes involved: the node to be | |
| 59 deleted (n1), and another node that is to be unchained from the tree (n2). | |
| 60 If n1 has a successor (the node with a smallest key that is larger than | |
| 61 n1), then the successor becomes n2 and its contents are copied into n1, | |
| 62 otherwise n1 becomes n2. | |
| 63 Unchaining a node may violate rule 1: if n2 is black, one subtree is | |
| 64 missing one black edge afterwards. The algorithm must try to move this | |
| 65 error upwards towards the root, so that the subtree that does not have | |
| 66 enough black edges becomes the whole tree. Once that happens, the error | |
| 67 has disappeared. It may not be necessary to go all the way up, since it | |
| 68 is possible that rotations and recoloring can fix the error before that. | |
| 69 | |
| 70 Although the deletion algorithm must walk upwards through the tree, we | |
| 71 do not store parent pointers in the nodes. Instead, delete allocates a | |
| 72 small array of parent pointers and fills it while descending the tree. | |
| 73 Since we know that the length of a path is O(log n), where n is the number | |
| 74 of nodes, this is likely to use less memory. */ | |
| 75 | |
| 76 /* Tree rotations look like this: | |
| 77 A C | |
| 78 / \ / \ | |
| 79 B C A G | |
| 80 / \ / \ --> / \ | |
| 81 D E F G B F | |
| 82 / \ | |
| 83 D E | |
| 84 | |
| 85 In this case, A has been rotated left. This preserves the ordering of the | |
| 86 binary tree. */ | |
| 87 | |
|
12422
f7842310a565
New module 'arg-nonnull'. Declare which arguments expect non-NULL values.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
88 /* Don't use __attribute__ __nonnull__ in this compilation unit. Otherwise gcc |
|
f7842310a565
New module 'arg-nonnull'. Declare which arguments expect non-NULL values.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
89 optimizes away the rootp == NULL tests below. */ |
|
f7842310a565
New module 'arg-nonnull'. Declare which arguments expect non-NULL values.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
90 #define _GL_ARG_NONNULL(params) |
|
f7842310a565
New module 'arg-nonnull'. Declare which arguments expect non-NULL values.
Bruno Haible <bruno@clisp.org>
parents:
12421
diff
changeset
|
91 |
|
17326
bb52d9cece01
unsetenv etc.: port to Solaris 11 + GNU Emacs
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
92 #include <config.h> |
|
bb52d9cece01
unsetenv etc.: port to Solaris 11 + GNU Emacs
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
93 |
| 7585 | 94 /* Specification. */ |
| 8532 | 95 #ifdef IN_LIBINTL |
| 96 # include "tsearch.h" | |
| 97 #else | |
| 98 # include <search.h> | |
| 99 #endif | |
| 7585 | 100 |
| 101 #include <stdlib.h> | |
| 102 | |
| 103 typedef int (*__compar_fn_t) (const void *, const void *); | |
| 104 typedef void (*__action_fn_t) (const void *, VISIT, int); | |
| 105 | |
| 106 #ifndef weak_alias | |
| 107 # define __tsearch tsearch | |
| 108 # define __tfind tfind | |
| 109 # define __tdelete tdelete | |
| 110 # define __twalk twalk | |
| 111 #endif | |
| 112 | |
| 113 #ifndef internal_function | |
| 114 /* Inside GNU libc we mark some function in a special way. In other | |
| 115 environments simply ignore the marking. */ | |
| 116 # define internal_function | |
| 117 #endif | |
| 118 | |
| 119 typedef struct node_t | |
| 120 { | |
| 121 /* Callers expect this to be the first element in the structure - do not | |
| 122 move! */ | |
| 123 const void *key; | |
| 124 struct node_t *left; | |
| 125 struct node_t *right; | |
| 126 unsigned int red:1; | |
| 127 } *node; | |
| 128 typedef const struct node_t *const_node; | |
| 129 | |
| 130 #undef DEBUGGING | |
| 131 | |
| 132 #ifdef DEBUGGING | |
| 133 | |
| 134 /* Routines to check tree invariants. */ | |
| 135 | |
| 136 #include <assert.h> | |
| 137 | |
| 138 #define CHECK_TREE(a) check_tree(a) | |
| 139 | |
| 140 static void | |
| 141 check_tree_recurse (node p, int d_sofar, int d_total) | |
| 142 { | |
| 143 if (p == NULL) | |
| 144 { | |
| 145 assert (d_sofar == d_total); | |
| 146 return; | |
| 147 } | |
| 148 | |
| 149 check_tree_recurse (p->left, d_sofar + (p->left && !p->left->red), d_total); | |
| 150 check_tree_recurse (p->right, d_sofar + (p->right && !p->right->red), d_total); | |
| 151 if (p->left) | |
| 152 assert (!(p->left->red && p->red)); | |
| 153 if (p->right) | |
| 154 assert (!(p->right->red && p->red)); | |
| 155 } | |
| 156 | |
| 157 static void | |
| 158 check_tree (node root) | |
| 159 { | |
| 160 int cnt = 0; | |
| 161 node p; | |
| 162 if (root == NULL) | |
| 163 return; | |
| 164 root->red = 0; | |
| 13051 | 165 for (p = root->left; p; p = p->left) |
| 7585 | 166 cnt += !p->red; |
| 167 check_tree_recurse (root, 0, cnt); | |
| 168 } | |
| 169 | |
| 170 | |
| 171 #else | |
| 172 | |
| 173 #define CHECK_TREE(a) | |
| 174 | |
| 175 #endif | |
| 176 | |
| 177 /* Possibly "split" a node with two red successors, and/or fix up two red | |
| 178 edges in a row. ROOTP is a pointer to the lowest node we visited, PARENTP | |
| 179 and GPARENTP pointers to its parent/grandparent. P_R and GP_R contain the | |
| 180 comparison values that determined which way was taken in the tree to reach | |
| 181 ROOTP. MODE is 1 if we need not do the split, but must check for two red | |
| 182 edges between GPARENTP and ROOTP. */ | |
| 183 static void | |
| 184 maybe_split_for_insert (node *rootp, node *parentp, node *gparentp, | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
185 int p_r, int gp_r, int mode) |
| 7585 | 186 { |
| 187 node root = *rootp; | |
| 188 node *rp, *lp; | |
| 189 rp = &(*rootp)->right; | |
| 190 lp = &(*rootp)->left; | |
| 191 | |
| 192 /* See if we have to split this node (both successors red). */ | |
| 193 if (mode == 1 | |
| 194 || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red)) | |
| 195 { | |
| 196 /* This node becomes red, its successors black. */ | |
| 197 root->red = 1; | |
| 198 if (*rp) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
199 (*rp)->red = 0; |
| 7585 | 200 if (*lp) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
201 (*lp)->red = 0; |
| 7585 | 202 |
| 203 /* If the parent of this node is also red, we have to do | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
204 rotations. */ |
| 7585 | 205 if (parentp != NULL && (*parentp)->red) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
206 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
207 node gp = *gparentp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
208 node p = *parentp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
209 /* There are two main cases: |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
210 1. The edge types (left or right) of the two red edges differ. |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
211 2. Both red edges are of the same type. |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
212 There exist two symmetries of each case, so there is a total of |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
213 4 cases. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
214 if ((p_r > 0) != (gp_r > 0)) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
215 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
216 /* Put the child at the top of the tree, with its parent |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
217 and grandparent as successors. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
218 p->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
219 gp->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
220 root->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
221 if (p_r < 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
222 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
223 /* Child is left of parent. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
224 p->left = *rp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
225 *rp = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
226 gp->right = *lp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
227 *lp = gp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
228 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
229 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
230 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
231 /* Child is right of parent. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
232 p->right = *lp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
233 *lp = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
234 gp->left = *rp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
235 *rp = gp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
236 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
237 *gparentp = root; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
238 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
239 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
240 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
241 *gparentp = *parentp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
242 /* Parent becomes the top of the tree, grandparent and |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
243 child are its successors. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
244 p->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
245 gp->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
246 if (p_r < 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
247 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
248 /* Left edges. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
249 gp->left = p->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
250 p->right = gp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
251 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
252 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
253 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
254 /* Right edges. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
255 gp->right = p->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
256 p->left = gp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
257 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
258 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
259 } |
| 7585 | 260 } |
| 261 } | |
| 262 | |
| 263 /* Find or insert datum into search tree. | |
| 264 KEY is the key to be located, ROOTP is the address of tree root, | |
| 265 COMPAR the ordering function. */ | |
| 266 void * | |
| 267 __tsearch (const void *key, void **vrootp, __compar_fn_t compar) | |
| 268 { | |
| 269 node q; | |
| 270 node *parentp = NULL, *gparentp = NULL; | |
| 271 node *rootp = (node *) vrootp; | |
| 272 node *nextp; | |
| 273 int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler. */ | |
| 274 | |
| 275 if (rootp == NULL) | |
| 276 return NULL; | |
| 277 | |
| 278 /* This saves some additional tests below. */ | |
| 279 if (*rootp != NULL) | |
| 280 (*rootp)->red = 0; | |
| 281 | |
| 282 CHECK_TREE (*rootp); | |
| 283 | |
| 284 nextp = rootp; | |
| 285 while (*nextp != NULL) | |
| 286 { | |
| 287 node root = *rootp; | |
| 288 r = (*compar) (key, root->key); | |
| 289 if (r == 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
290 return root; |
| 7585 | 291 |
| 292 maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0); | |
| 293 /* If that did any rotations, parentp and gparentp are now garbage. | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
294 That doesn't matter, because the values they contain are never |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
295 used again in that case. */ |
| 7585 | 296 |
| 297 nextp = r < 0 ? &root->left : &root->right; | |
| 298 if (*nextp == NULL) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
299 break; |
| 7585 | 300 |
| 301 gparentp = parentp; | |
| 302 parentp = rootp; | |
| 303 rootp = nextp; | |
| 304 | |
| 305 gp_r = p_r; | |
| 306 p_r = r; | |
| 307 } | |
| 308 | |
| 309 q = (struct node_t *) malloc (sizeof (struct node_t)); | |
| 310 if (q != NULL) | |
| 311 { | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
312 *nextp = q; /* link new node to old */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
313 q->key = key; /* initialize new node */ |
| 7585 | 314 q->red = 1; |
| 315 q->left = q->right = NULL; | |
| 316 | |
| 317 if (nextp != rootp) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
318 /* There may be two red edges in a row now, which we must avoid by |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
319 rotating the tree. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
320 maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1); |
| 7585 | 321 } |
| 322 | |
| 323 return q; | |
| 324 } | |
| 325 #ifdef weak_alias | |
| 326 weak_alias (__tsearch, tsearch) | |
| 327 #endif | |
| 328 | |
| 329 | |
| 330 /* Find datum in search tree. | |
| 331 KEY is the key to be located, ROOTP is the address of tree root, | |
| 332 COMPAR the ordering function. */ | |
| 333 void * | |
| 334 __tfind (key, vrootp, compar) | |
| 335 const void *key; | |
| 336 void *const *vrootp; | |
| 337 __compar_fn_t compar; | |
| 338 { | |
| 339 node *rootp = (node *) vrootp; | |
| 340 | |
| 341 if (rootp == NULL) | |
| 342 return NULL; | |
| 343 | |
| 344 CHECK_TREE (*rootp); | |
| 345 | |
| 346 while (*rootp != NULL) | |
| 347 { | |
| 348 node root = *rootp; | |
| 349 int r; | |
| 350 | |
| 351 r = (*compar) (key, root->key); | |
| 352 if (r == 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
353 return root; |
| 7585 | 354 |
| 355 rootp = r < 0 ? &root->left : &root->right; | |
| 356 } | |
| 357 return NULL; | |
| 358 } | |
| 359 #ifdef weak_alias | |
| 360 weak_alias (__tfind, tfind) | |
| 361 #endif | |
| 362 | |
| 363 | |
| 364 /* Delete node with given key. | |
| 365 KEY is the key to be deleted, ROOTP is the address of the root of tree, | |
| 366 COMPAR the comparison function. */ | |
| 367 void * | |
| 368 __tdelete (const void *key, void **vrootp, __compar_fn_t compar) | |
| 369 { | |
| 370 node p, q, r, retval; | |
| 371 int cmp; | |
| 372 node *rootp = (node *) vrootp; | |
| 373 node root, unchained; | |
| 374 /* Stack of nodes so we remember the parents without recursion. It's | |
| 375 _very_ unlikely that there are paths longer than 40 nodes. The tree | |
| 376 would need to have around 250.000 nodes. */ | |
| 377 int stacksize = 100; | |
| 378 int sp = 0; | |
| 379 node *nodestack[100]; | |
| 380 | |
| 381 if (rootp == NULL) | |
| 382 return NULL; | |
| 383 p = *rootp; | |
| 384 if (p == NULL) | |
| 385 return NULL; | |
| 386 | |
| 387 CHECK_TREE (p); | |
| 388 | |
| 389 while ((cmp = (*compar) (key, (*rootp)->key)) != 0) | |
| 390 { | |
| 391 if (sp == stacksize) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
392 abort (); |
| 7585 | 393 |
| 394 nodestack[sp++] = rootp; | |
| 395 p = *rootp; | |
| 396 rootp = ((cmp < 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
397 ? &(*rootp)->left |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
398 : &(*rootp)->right); |
| 7585 | 399 if (*rootp == NULL) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
400 return NULL; |
| 7585 | 401 } |
| 402 | |
| 403 /* This is bogus if the node to be deleted is the root... this routine | |
| 404 really should return an integer with 0 for success, -1 for failure | |
| 405 and errno = ESRCH or something. */ | |
| 406 retval = p; | |
| 407 | |
| 408 /* We don't unchain the node we want to delete. Instead, we overwrite | |
| 409 it with its successor and unchain the successor. If there is no | |
| 410 successor, we really unchain the node to be deleted. */ | |
| 411 | |
| 412 root = *rootp; | |
| 413 | |
| 414 r = root->right; | |
| 415 q = root->left; | |
| 416 | |
| 417 if (q == NULL || r == NULL) | |
| 418 unchained = root; | |
| 419 else | |
| 420 { | |
| 421 node *parent = rootp, *up = &root->right; | |
| 422 for (;;) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
423 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
424 if (sp == stacksize) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
425 abort (); |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
426 nodestack[sp++] = parent; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
427 parent = up; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
428 if ((*up)->left == NULL) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
429 break; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
430 up = &(*up)->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
431 } |
| 7585 | 432 unchained = *up; |
| 433 } | |
| 434 | |
| 435 /* We know that either the left or right successor of UNCHAINED is NULL. | |
| 436 R becomes the other one, it is chained into the parent of UNCHAINED. */ | |
| 437 r = unchained->left; | |
| 438 if (r == NULL) | |
| 439 r = unchained->right; | |
| 440 if (sp == 0) | |
| 441 *rootp = r; | |
| 442 else | |
| 443 { | |
| 444 q = *nodestack[sp-1]; | |
| 445 if (unchained == q->right) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
446 q->right = r; |
| 7585 | 447 else |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
448 q->left = r; |
| 7585 | 449 } |
| 450 | |
| 451 if (unchained != root) | |
| 452 root->key = unchained->key; | |
| 453 if (!unchained->red) | |
| 454 { | |
| 455 /* Now we lost a black edge, which means that the number of black | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
456 edges on every path is no longer constant. We must balance the |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
457 tree. */ |
| 7585 | 458 /* NODESTACK now contains all parents of R. R is likely to be NULL |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
459 in the first iteration. */ |
| 7585 | 460 /* NULL nodes are considered black throughout - this is necessary for |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
461 correctness. */ |
| 7585 | 462 while (sp > 0 && (r == NULL || !r->red)) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
463 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
464 node *pp = nodestack[sp - 1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
465 p = *pp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
466 /* Two symmetric cases. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
467 if (r == p->left) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
468 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
469 /* Q is R's brother, P is R's parent. The subtree with root |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
470 R has one black edge less than the subtree with root Q. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
471 q = p->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
472 if (q->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
473 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
474 /* If Q is red, we know that P is black. We rotate P left |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
475 so that Q becomes the top node in the tree, with P below |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
476 it. P is colored red, Q is colored black. |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
477 This action does not change the black edge count for any |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
478 leaf in the tree, but we will be able to recognize one |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
479 of the following situations, which all require that Q |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
480 is black. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
481 q->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
482 p->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
483 /* Left rotate p. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
484 p->right = q->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
485 q->left = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
486 *pp = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
487 /* Make sure pp is right if the case below tries to use |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
488 it. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
489 nodestack[sp++] = pp = &q->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
490 q = p->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
491 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
492 /* We know that Q can't be NULL here. We also know that Q is |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
493 black. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
494 if ((q->left == NULL || !q->left->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
495 && (q->right == NULL || !q->right->red)) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
496 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
497 /* Q has two black successors. We can simply color Q red. |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
498 The whole subtree with root P is now missing one black |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
499 edge. Note that this action can temporarily make the |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
500 tree invalid (if P is red). But we will exit the loop |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
501 in that case and set P black, which both makes the tree |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
502 valid and also makes the black edge count come out |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
503 right. If P is black, we are at least one step closer |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
504 to the root and we'll try again the next iteration. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
505 q->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
506 r = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
507 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
508 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
509 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
510 /* Q is black, one of Q's successors is red. We can |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
511 repair the tree with one operation and will exit the |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
512 loop afterwards. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
513 if (q->right == NULL || !q->right->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
514 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
515 /* The left one is red. We perform the same action as |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
516 in maybe_split_for_insert where two red edges are |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
517 adjacent but point in different directions: |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
518 Q's left successor (let's call it Q2) becomes the |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
519 top of the subtree we are looking at, its parent (Q) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
520 and grandparent (P) become its successors. The former |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
521 successors of Q2 are placed below P and Q. |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
522 P becomes black, and Q2 gets the color that P had. |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
523 This changes the black edge count only for node R and |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
524 its successors. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
525 node q2 = q->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
526 q2->red = p->red; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
527 p->right = q2->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
528 q->left = q2->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
529 q2->right = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
530 q2->left = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
531 *pp = q2; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
532 p->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
533 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
534 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
535 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
536 /* It's the right one. Rotate P left. P becomes black, |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
537 and Q gets the color that P had. Q's right successor |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
538 also becomes black. This changes the black edge |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
539 count only for node R and its successors. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
540 q->red = p->red; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
541 p->red = 0; |
| 7585 | 542 |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
543 q->right->red = 0; |
| 7585 | 544 |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
545 /* left rotate p */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
546 p->right = q->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
547 q->left = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
548 *pp = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
549 } |
| 7585 | 550 |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
551 /* We're done. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
552 sp = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
553 r = NULL; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
554 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
555 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
556 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
557 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
558 /* Comments: see above. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
559 q = p->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
560 if (q->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
561 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
562 q->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
563 p->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
564 p->left = q->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
565 q->right = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
566 *pp = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
567 nodestack[sp++] = pp = &q->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
568 q = p->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
569 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
570 if ((q->right == NULL || !q->right->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
571 && (q->left == NULL || !q->left->red)) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
572 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
573 q->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
574 r = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
575 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
576 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
577 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
578 if (q->left == NULL || !q->left->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
579 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
580 node q2 = q->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
581 q2->red = p->red; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
582 p->left = q2->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
583 q->right = q2->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
584 q2->left = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
585 q2->right = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
586 *pp = q2; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
587 p->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
588 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
589 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
590 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
591 q->red = p->red; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
592 p->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
593 q->left->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
594 p->left = q->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
595 q->right = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
596 *pp = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
597 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
598 sp = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
599 r = NULL; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
600 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
601 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
602 --sp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
603 } |
| 7585 | 604 if (r != NULL) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
605 r->red = 0; |
| 7585 | 606 } |
| 607 | |
| 608 free (unchained); | |
| 609 return retval; | |
| 610 } | |
| 611 #ifdef weak_alias | |
| 612 weak_alias (__tdelete, tdelete) | |
| 613 #endif | |
| 614 | |
| 615 | |
| 616 /* Walk the nodes of a tree. | |
| 617 ROOT is the root of the tree to be walked, ACTION the function to be | |
| 618 called at each node. LEVEL is the level of ROOT in the whole tree. */ | |
| 619 static void | |
| 620 internal_function | |
| 621 trecurse (const void *vroot, __action_fn_t action, int level) | |
| 622 { | |
| 623 const_node root = (const_node) vroot; | |
| 624 | |
| 625 if (root->left == NULL && root->right == NULL) | |
| 626 (*action) (root, leaf, level); | |
| 627 else | |
| 628 { | |
| 629 (*action) (root, preorder, level); | |
| 630 if (root->left != NULL) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
631 trecurse (root->left, action, level + 1); |
| 7585 | 632 (*action) (root, postorder, level); |
| 633 if (root->right != NULL) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
634 trecurse (root->right, action, level + 1); |
| 7585 | 635 (*action) (root, endorder, level); |
| 636 } | |
| 637 } | |
| 638 | |
| 639 | |
| 640 /* Walk the nodes of a tree. | |
| 641 ROOT is the root of the tree to be walked, ACTION the function to be | |
| 642 called at each node. */ | |
| 643 void | |
| 644 __twalk (const void *vroot, __action_fn_t action) | |
| 645 { | |
| 646 const_node root = (const_node) vroot; | |
| 647 | |
| 648 CHECK_TREE (root); | |
| 649 | |
| 650 if (root != NULL && action != NULL) | |
| 651 trecurse (root, action, 0); | |
| 652 } | |
| 653 #ifdef weak_alias | |
| 654 weak_alias (__twalk, twalk) | |
| 655 #endif | |
| 656 | |
| 657 | |
| 658 #ifdef _LIBC | |
| 659 | |
| 660 /* The standardized functions miss an important functionality: the | |
| 661 tree cannot be removed easily. We provide a function to do this. */ | |
| 662 static void | |
| 663 internal_function | |
| 664 tdestroy_recurse (node root, __free_fn_t freefct) | |
| 665 { | |
| 666 if (root->left != NULL) | |
| 667 tdestroy_recurse (root->left, freefct); | |
| 668 if (root->right != NULL) | |
| 669 tdestroy_recurse (root->right, freefct); | |
| 670 (*freefct) ((void *) root->key); | |
| 671 /* Free the node itself. */ | |
| 672 free (root); | |
| 673 } | |
| 674 | |
| 675 void | |
| 676 __tdestroy (void *vroot, __free_fn_t freefct) | |
| 677 { | |
| 678 node root = (node) vroot; | |
| 679 | |
| 680 CHECK_TREE (root); | |
| 681 | |
| 682 if (root != NULL) | |
| 683 tdestroy_recurse (root, freefct); | |
| 684 } | |
| 685 weak_alias (__tdestroy, tdestroy) | |
| 686 | |
| 687 #endif /* _LIBC */ |