Mercurial > gnulib
annotate lib/tsearch.c @ 40057:b06060465f09
maint: Run 'make update-copyright'
| author | Paul Eggert <eggert@cs.ucla.edu> |
|---|---|
| date | Tue, 01 Jan 2019 00:25:11 +0100 |
| parents | 7fbb07e18508 |
| children |
| rev | line source |
|---|---|
|
40057
b06060465f09
maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents:
19665
diff
changeset
|
1 /* Copyright (C) 1995-1997, 2000, 2006-2007, 2009-2019 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 | |
| 19190 | 19 along with this program. If not, see <https://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 | |
|
19664
ac5267ac9bab
tsearch: Fix compilation error on Android.
Bruno Haible <bruno@clisp.org>
parents:
19484
diff
changeset
|
177 #if GNULIB_defined_tsearch |
|
ac5267ac9bab
tsearch: Fix compilation error on Android.
Bruno Haible <bruno@clisp.org>
parents:
19484
diff
changeset
|
178 |
| 7585 | 179 /* Possibly "split" a node with two red successors, and/or fix up two red |
| 180 edges in a row. ROOTP is a pointer to the lowest node we visited, PARENTP | |
| 181 and GPARENTP pointers to its parent/grandparent. P_R and GP_R contain the | |
| 182 comparison values that determined which way was taken in the tree to reach | |
| 183 ROOTP. MODE is 1 if we need not do the split, but must check for two red | |
| 184 edges between GPARENTP and ROOTP. */ | |
| 185 static void | |
| 186 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
|
187 int p_r, int gp_r, int mode) |
| 7585 | 188 { |
| 189 node root = *rootp; | |
| 190 node *rp, *lp; | |
| 191 rp = &(*rootp)->right; | |
| 192 lp = &(*rootp)->left; | |
| 193 | |
| 194 /* See if we have to split this node (both successors red). */ | |
| 195 if (mode == 1 | |
| 196 || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red)) | |
| 197 { | |
| 198 /* This node becomes red, its successors black. */ | |
| 199 root->red = 1; | |
| 200 if (*rp) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
201 (*rp)->red = 0; |
| 7585 | 202 if (*lp) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
203 (*lp)->red = 0; |
| 7585 | 204 |
| 205 /* 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
|
206 rotations. */ |
| 7585 | 207 if (parentp != NULL && (*parentp)->red) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
208 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
209 node gp = *gparentp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
210 node p = *parentp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
211 /* There are two main cases: |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
212 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
|
213 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
|
214 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
|
215 4 cases. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
216 if ((p_r > 0) != (gp_r > 0)) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
217 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
218 /* 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
|
219 and grandparent as successors. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
220 p->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
221 gp->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
222 root->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
223 if (p_r < 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
224 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
225 /* Child is left of parent. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
226 p->left = *rp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
227 *rp = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
228 gp->right = *lp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
229 *lp = gp; |
|
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 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
232 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
233 /* Child is right of parent. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
234 p->right = *lp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
235 *lp = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
236 gp->left = *rp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
237 *rp = gp; |
|
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 *gparentp = root; |
|
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 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
242 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
243 *gparentp = *parentp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
244 /* 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
|
245 child are its successors. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
246 p->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
247 gp->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
248 if (p_r < 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
249 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
250 /* Left edges. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
251 gp->left = p->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
252 p->right = gp; |
|
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 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
255 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
256 /* Right edges. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
257 gp->right = p->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
258 p->left = gp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
259 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
260 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
261 } |
| 7585 | 262 } |
| 263 } | |
| 264 | |
| 265 /* Find or insert datum into search tree. | |
| 266 KEY is the key to be located, ROOTP is the address of tree root, | |
| 267 COMPAR the ordering function. */ | |
| 268 void * | |
| 269 __tsearch (const void *key, void **vrootp, __compar_fn_t compar) | |
| 270 { | |
| 271 node q; | |
| 272 node *parentp = NULL, *gparentp = NULL; | |
| 273 node *rootp = (node *) vrootp; | |
| 274 node *nextp; | |
| 275 int r = 0, p_r = 0, gp_r = 0; /* No they might not, Mr Compiler. */ | |
| 276 | |
| 277 if (rootp == NULL) | |
| 278 return NULL; | |
| 279 | |
| 280 /* This saves some additional tests below. */ | |
| 281 if (*rootp != NULL) | |
| 282 (*rootp)->red = 0; | |
| 283 | |
| 284 CHECK_TREE (*rootp); | |
| 285 | |
| 286 nextp = rootp; | |
| 287 while (*nextp != NULL) | |
| 288 { | |
| 289 node root = *rootp; | |
| 290 r = (*compar) (key, root->key); | |
| 291 if (r == 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
292 return root; |
| 7585 | 293 |
| 294 maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0); | |
| 295 /* 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
|
296 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
|
297 used again in that case. */ |
| 7585 | 298 |
| 299 nextp = r < 0 ? &root->left : &root->right; | |
| 300 if (*nextp == NULL) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
301 break; |
| 7585 | 302 |
| 303 gparentp = parentp; | |
| 304 parentp = rootp; | |
| 305 rootp = nextp; | |
| 306 | |
| 307 gp_r = p_r; | |
| 308 p_r = r; | |
| 309 } | |
| 310 | |
| 311 q = (struct node_t *) malloc (sizeof (struct node_t)); | |
| 312 if (q != NULL) | |
| 313 { | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
314 *nextp = q; /* link new node to old */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
315 q->key = key; /* initialize new node */ |
| 7585 | 316 q->red = 1; |
| 317 q->left = q->right = NULL; | |
| 318 | |
| 319 if (nextp != rootp) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
320 /* 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
|
321 rotating the tree. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
322 maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1); |
| 7585 | 323 } |
| 324 | |
| 325 return q; | |
| 326 } | |
| 327 #ifdef weak_alias | |
| 328 weak_alias (__tsearch, tsearch) | |
| 329 #endif | |
| 330 | |
| 331 | |
| 332 /* Find datum in search tree. | |
| 333 KEY is the key to be located, ROOTP is the address of tree root, | |
| 334 COMPAR the ordering function. */ | |
| 335 void * | |
|
19665
7fbb07e18508
tsearch: Move from K&R C to ANSI C.
Bruno Haible <bruno@clisp.org>
parents:
19664
diff
changeset
|
336 __tfind (const void *key, void *const *vrootp, __compar_fn_t compar) |
| 7585 | 337 { |
| 338 node *rootp = (node *) vrootp; | |
| 339 | |
| 340 if (rootp == NULL) | |
| 341 return NULL; | |
| 342 | |
| 343 CHECK_TREE (*rootp); | |
| 344 | |
| 345 while (*rootp != NULL) | |
| 346 { | |
| 347 node root = *rootp; | |
| 348 int r; | |
| 349 | |
| 350 r = (*compar) (key, root->key); | |
| 351 if (r == 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
352 return root; |
| 7585 | 353 |
| 354 rootp = r < 0 ? &root->left : &root->right; | |
| 355 } | |
| 356 return NULL; | |
| 357 } | |
| 358 #ifdef weak_alias | |
| 359 weak_alias (__tfind, tfind) | |
| 360 #endif | |
| 361 | |
| 362 | |
| 363 /* Delete node with given key. | |
| 364 KEY is the key to be deleted, ROOTP is the address of the root of tree, | |
| 365 COMPAR the comparison function. */ | |
| 366 void * | |
| 367 __tdelete (const void *key, void **vrootp, __compar_fn_t compar) | |
| 368 { | |
| 369 node p, q, r, retval; | |
| 370 int cmp; | |
| 371 node *rootp = (node *) vrootp; | |
| 372 node root, unchained; | |
| 373 /* Stack of nodes so we remember the parents without recursion. It's | |
| 374 _very_ unlikely that there are paths longer than 40 nodes. The tree | |
| 375 would need to have around 250.000 nodes. */ | |
| 376 int stacksize = 100; | |
| 377 int sp = 0; | |
| 378 node *nodestack[100]; | |
| 379 | |
| 380 if (rootp == NULL) | |
| 381 return NULL; | |
| 382 p = *rootp; | |
| 383 if (p == NULL) | |
| 384 return NULL; | |
| 385 | |
| 386 CHECK_TREE (p); | |
| 387 | |
| 388 while ((cmp = (*compar) (key, (*rootp)->key)) != 0) | |
| 389 { | |
| 390 if (sp == stacksize) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
391 abort (); |
| 7585 | 392 |
| 393 nodestack[sp++] = rootp; | |
| 394 p = *rootp; | |
| 395 rootp = ((cmp < 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
396 ? &(*rootp)->left |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
397 : &(*rootp)->right); |
| 7585 | 398 if (*rootp == NULL) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
399 return NULL; |
| 7585 | 400 } |
| 401 | |
| 402 /* This is bogus if the node to be deleted is the root... this routine | |
| 403 really should return an integer with 0 for success, -1 for failure | |
| 404 and errno = ESRCH or something. */ | |
| 405 retval = p; | |
| 406 | |
| 407 /* We don't unchain the node we want to delete. Instead, we overwrite | |
| 408 it with its successor and unchain the successor. If there is no | |
| 409 successor, we really unchain the node to be deleted. */ | |
| 410 | |
| 411 root = *rootp; | |
| 412 | |
| 413 r = root->right; | |
| 414 q = root->left; | |
| 415 | |
| 416 if (q == NULL || r == NULL) | |
| 417 unchained = root; | |
| 418 else | |
| 419 { | |
| 420 node *parent = rootp, *up = &root->right; | |
| 421 for (;;) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
422 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
423 if (sp == stacksize) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
424 abort (); |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
425 nodestack[sp++] = parent; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
426 parent = up; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
427 if ((*up)->left == NULL) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
428 break; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
429 up = &(*up)->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
430 } |
| 7585 | 431 unchained = *up; |
| 432 } | |
| 433 | |
| 434 /* We know that either the left or right successor of UNCHAINED is NULL. | |
| 435 R becomes the other one, it is chained into the parent of UNCHAINED. */ | |
| 436 r = unchained->left; | |
| 437 if (r == NULL) | |
| 438 r = unchained->right; | |
| 439 if (sp == 0) | |
| 440 *rootp = r; | |
| 441 else | |
| 442 { | |
| 443 q = *nodestack[sp-1]; | |
| 444 if (unchained == q->right) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
445 q->right = r; |
| 7585 | 446 else |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
447 q->left = r; |
| 7585 | 448 } |
| 449 | |
| 450 if (unchained != root) | |
| 451 root->key = unchained->key; | |
| 452 if (!unchained->red) | |
| 453 { | |
| 454 /* 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
|
455 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
|
456 tree. */ |
| 7585 | 457 /* 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
|
458 in the first iteration. */ |
| 7585 | 459 /* 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
|
460 correctness. */ |
| 7585 | 461 while (sp > 0 && (r == NULL || !r->red)) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
462 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
463 node *pp = nodestack[sp - 1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
464 p = *pp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
465 /* Two symmetric cases. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
466 if (r == p->left) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
467 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
468 /* 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
|
469 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
|
470 q = p->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
471 if (q->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
472 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
473 /* 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
|
474 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
|
475 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
|
476 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
|
477 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
|
478 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
|
479 is black. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
480 q->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
481 p->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
482 /* Left rotate p. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
483 p->right = q->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
484 q->left = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
485 *pp = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
486 /* 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
|
487 it. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
488 nodestack[sp++] = pp = &q->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
489 q = p->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
490 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
491 /* 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
|
492 black. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
493 if ((q->left == NULL || !q->left->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
494 && (q->right == NULL || !q->right->red)) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
495 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
496 /* 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
|
497 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
|
498 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
|
499 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
|
500 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
|
501 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
|
502 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
|
503 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
|
504 q->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
505 r = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
506 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
507 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
508 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
509 /* 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
|
510 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
|
511 loop afterwards. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
512 if (q->right == NULL || !q->right->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
513 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
514 /* 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
|
515 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
|
516 adjacent but point in different directions: |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
517 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
|
518 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
|
519 and grandparent (P) become its successors. The former |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
520 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
|
521 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
|
522 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
|
523 its successors. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
524 node q2 = q->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
525 q2->red = p->red; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
526 p->right = q2->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
527 q->left = q2->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
528 q2->right = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
529 q2->left = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
530 *pp = q2; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
531 p->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
532 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
533 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
534 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
535 /* 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
|
536 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
|
537 also becomes black. This changes the black edge |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
538 count only for node R and its successors. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
539 q->red = p->red; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
540 p->red = 0; |
| 7585 | 541 |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
542 q->right->red = 0; |
| 7585 | 543 |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
544 /* left rotate p */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
545 p->right = q->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
546 q->left = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
547 *pp = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
548 } |
| 7585 | 549 |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
550 /* We're done. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
551 sp = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
552 r = NULL; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
553 } |
|
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 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
556 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
557 /* Comments: see above. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
558 q = p->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
559 if (q->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
560 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
561 q->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
562 p->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
563 p->left = q->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
564 q->right = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
565 *pp = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
566 nodestack[sp++] = pp = &q->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
567 q = p->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
568 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
569 if ((q->right == NULL || !q->right->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
570 && (q->left == NULL || !q->left->red)) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
571 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
572 q->red = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
573 r = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
574 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
575 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
576 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
577 if (q->left == NULL || !q->left->red) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
578 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
579 node q2 = q->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
580 q2->red = p->red; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
581 p->left = q2->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
582 q->right = q2->left; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
583 q2->left = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
584 q2->right = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
585 *pp = q2; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
586 p->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
587 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
588 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
589 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
590 q->red = p->red; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
591 p->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
592 q->left->red = 0; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
593 p->left = q->right; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
594 q->right = p; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
595 *pp = q; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
596 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
597 sp = 1; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
598 r = NULL; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
599 } |
|
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 --sp; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
602 } |
| 7585 | 603 if (r != NULL) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
604 r->red = 0; |
| 7585 | 605 } |
| 606 | |
| 607 free (unchained); | |
| 608 return retval; | |
| 609 } | |
| 610 #ifdef weak_alias | |
| 611 weak_alias (__tdelete, tdelete) | |
| 612 #endif | |
| 613 | |
|
19664
ac5267ac9bab
tsearch: Fix compilation error on Android.
Bruno Haible <bruno@clisp.org>
parents:
19484
diff
changeset
|
614 #endif /* GNULIB_defined_tsearch */ |
|
ac5267ac9bab
tsearch: Fix compilation error on Android.
Bruno Haible <bruno@clisp.org>
parents:
19484
diff
changeset
|
615 |
|
ac5267ac9bab
tsearch: Fix compilation error on Android.
Bruno Haible <bruno@clisp.org>
parents:
19484
diff
changeset
|
616 |
|
ac5267ac9bab
tsearch: Fix compilation error on Android.
Bruno Haible <bruno@clisp.org>
parents:
19484
diff
changeset
|
617 #if GNULIB_defined_twalk |
| 7585 | 618 |
| 619 /* Walk the nodes of a tree. | |
| 620 ROOT is the root of the tree to be walked, ACTION the function to be | |
| 621 called at each node. LEVEL is the level of ROOT in the whole tree. */ | |
| 622 static void | |
| 623 internal_function | |
| 624 trecurse (const void *vroot, __action_fn_t action, int level) | |
| 625 { | |
| 626 const_node root = (const_node) vroot; | |
| 627 | |
| 628 if (root->left == NULL && root->right == NULL) | |
| 629 (*action) (root, leaf, level); | |
| 630 else | |
| 631 { | |
| 632 (*action) (root, preorder, level); | |
| 633 if (root->left != NULL) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
634 trecurse (root->left, action, level + 1); |
| 7585 | 635 (*action) (root, postorder, level); |
| 636 if (root->right != NULL) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9309
diff
changeset
|
637 trecurse (root->right, action, level + 1); |
| 7585 | 638 (*action) (root, endorder, level); |
| 639 } | |
| 640 } | |
| 641 | |
| 642 | |
| 643 /* Walk the nodes of a tree. | |
| 644 ROOT is the root of the tree to be walked, ACTION the function to be | |
| 645 called at each node. */ | |
| 646 void | |
| 647 __twalk (const void *vroot, __action_fn_t action) | |
| 648 { | |
| 649 const_node root = (const_node) vroot; | |
| 650 | |
| 651 CHECK_TREE (root); | |
| 652 | |
| 653 if (root != NULL && action != NULL) | |
| 654 trecurse (root, action, 0); | |
| 655 } | |
| 656 #ifdef weak_alias | |
| 657 weak_alias (__twalk, twalk) | |
| 658 #endif | |
| 659 | |
|
19664
ac5267ac9bab
tsearch: Fix compilation error on Android.
Bruno Haible <bruno@clisp.org>
parents:
19484
diff
changeset
|
660 #endif /* GNULIB_defined_twalk */ |
|
ac5267ac9bab
tsearch: Fix compilation error on Android.
Bruno Haible <bruno@clisp.org>
parents:
19484
diff
changeset
|
661 |
| 7585 | 662 |
| 663 #ifdef _LIBC | |
| 664 | |
| 665 /* The standardized functions miss an important functionality: the | |
| 666 tree cannot be removed easily. We provide a function to do this. */ | |
| 667 static void | |
| 668 internal_function | |
| 669 tdestroy_recurse (node root, __free_fn_t freefct) | |
| 670 { | |
| 671 if (root->left != NULL) | |
| 672 tdestroy_recurse (root->left, freefct); | |
| 673 if (root->right != NULL) | |
| 674 tdestroy_recurse (root->right, freefct); | |
| 675 (*freefct) ((void *) root->key); | |
| 676 /* Free the node itself. */ | |
| 677 free (root); | |
| 678 } | |
| 679 | |
| 680 void | |
| 681 __tdestroy (void *vroot, __free_fn_t freefct) | |
| 682 { | |
| 683 node root = (node) vroot; | |
| 684 | |
| 685 CHECK_TREE (root); | |
| 686 | |
| 687 if (root != NULL) | |
| 688 tdestroy_recurse (root, freefct); | |
| 689 } | |
| 690 weak_alias (__tdestroy, tdestroy) | |
| 691 | |
| 692 #endif /* _LIBC */ |