diff options
| author | dougm <dougm@FreeBSD.org> | 2020-06-20 20:25:39 +0000 |
|---|---|---|
| committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2020-10-26 14:18:46 +0100 |
| commit | d03eaf36dc30bf41fc57f8de100c105f49063429 (patch) | |
| tree | 3d5d935281806df706b33fd1add60f87711ed6fb /newlib | |
| parent | 977a827d2908df223666641a890a5833df3f796c (diff) | |
| download | newlib-d03eaf36dc30bf41fc57f8de100c105f49063429.zip newlib-d03eaf36dc30bf41fc57f8de100c105f49063429.tar.gz newlib-d03eaf36dc30bf41fc57f8de100c105f49063429.tar.bz2 | |
In concluding RB_REMOVE_COLOR, in the case when
the sibling of the root of the too-short tree is black and at least one of the
children of that sibling is red, either one or two rotations finish the
rebalancing. In the case when both of the children are red, the current
implementation uses two rotations where only one is necessary. This change
removes that extra rotation, and in that case also removes a needless
black-to-red-to-black recoloring.
Reviewed by: markj
Differential Revision: https://reviews.freebsd.org/D25335
Diffstat (limited to 'newlib')
| -rw-r--r-- | newlib/libc/include/sys/tree.h | 26 |
1 files changed, 11 insertions, 15 deletions
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h index 372c001..2e1cc1e 100644 --- a/newlib/libc/include/sys/tree.h +++ b/newlib/libc/include/sys/tree.h @@ -493,21 +493,19 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \ RB_ROTATE_LEFT(head, parent, tmp, field);\ tmp = RB_RIGHT(parent, field); \ } \ - if (RB_ISRED(RB_LEFT(tmp, field), field)) { \ + if (RB_ISRED(RB_RIGHT(tmp, field), field)) \ + RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ + else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \ struct type *oleft; \ - oleft = RB_LEFT(tmp, field); \ - RB_COLOR(oleft, field) = RB_BLACK; \ - RB_COLOR(tmp, field) = RB_RED; \ RB_ROTATE_RIGHT(head, tmp, oleft, field); \ - tmp = RB_RIGHT(parent, field); \ - } else if (!RB_ISRED(RB_RIGHT(tmp, field), field)) { \ + RB_COLOR(oleft, field) = RB_BLACK; \ + tmp = oleft; \ + } else { \ RB_COLOR(tmp, field) = RB_RED; \ elm = parent; \ parent = RB_PARENT(elm, field); \ continue; \ } \ - if (RB_ISRED(RB_RIGHT(tmp, field), field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ RB_COLOR(parent, field) = RB_BLACK; \ RB_ROTATE_LEFT(head, parent, tmp, field); \ @@ -520,21 +518,19 @@ name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \ RB_ROTATE_RIGHT(head, parent, tmp, field);\ tmp = RB_LEFT(parent, field); \ } \ - if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \ + if (RB_ISRED(RB_LEFT(tmp, field), field)) \ + RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ + else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \ struct type *oright; \ - oright = RB_RIGHT(tmp, field); \ - RB_COLOR(oright, field) = RB_BLACK; \ - RB_COLOR(tmp, field) = RB_RED; \ RB_ROTATE_LEFT(head, tmp, oright, field); \ - tmp = RB_LEFT(parent, field); \ + RB_COLOR(oright, field) = RB_BLACK; \ + tmp = oright; \ } else if (!RB_ISRED(RB_LEFT(tmp, field), field)) { \ RB_COLOR(tmp, field) = RB_RED; \ elm = parent; \ parent = RB_PARENT(elm, field); \ continue; \ } \ - if (RB_ISRED(RB_LEFT(tmp, field), field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ RB_COLOR(parent, field) = RB_BLACK; \ RB_ROTATE_RIGHT(head, parent, tmp, field); \ |