diff options
Diffstat (limited to 'misc/tsearch.c')
| -rw-r--r-- | misc/tsearch.c | 15 |
1 files changed, 8 insertions, 7 deletions
diff --git a/misc/tsearch.c b/misc/tsearch.c index 7c3a0aaa78..1e94d64595 100644 --- a/misc/tsearch.c +++ b/misc/tsearch.c @@ -1,4 +1,4 @@ -/* Copyright (C) 1995, 1996, 1997, 2000 Free Software Foundation, Inc. +/* Copyright (C) 1995, 1996, 1997, 2000, 2006 Free Software Foundation, Inc. This file is part of the GNU C Library. Contributed by Bernd Schmidt <crux@Pool.Informatik.RWTH-Aachen.DE>, 1997. @@ -285,11 +285,12 @@ __tsearch (const void *key, void **vrootp, __compar_fn_t compar) q->key = key; /* initialize new node */ q->red = 1; q->left = q->right = NULL; + + if (nextp != rootp) + /* There may be two red edges in a row now, which we must avoid by + rotating the tree. */ + maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1); } - if (nextp != rootp) - /* There may be two red edges in a row now, which we must avoid by - rotating the tree. */ - maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1); return q; } @@ -446,7 +447,7 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar) /* Q is R's brother, P is R's parent. The subtree with root R has one black edge less than the subtree with root Q. */ q = p->right; - if (q != NULL && q->red) + if (q->red) { /* If Q is red, we know that P is black. We rotate P left so that Q becomes the top node in the tree, with P below @@ -534,7 +535,7 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar) { /* Comments: see above. */ q = p->left; - if (q != NULL && q->red) + if (q->red) { q->red = 0; p->red = 1; |