diff options
| author | Doug Moore <dougm@FreeBSD.org> | 2020-06-20 20:25:39 +0000 |
|---|---|---|
| committer | Doug Moore <dougm@FreeBSD.org> | 2020-06-20 20:25:39 +0000 |
| commit | bc1bed77a892ca418519fc2626080a55f5137f67 (patch) | |
| tree | c7a18e3e405e9cf3f15153aa0dd58cd69d504fb5 /sys/sys/tree.h | |
| parent | c8b0a88b8d152a0bcf98b57c3206172bd1ac6afa (diff) | |
| download | src-bc1bed77a892ca418519fc2626080a55f5137f67.tar.gz src-bc1bed77a892ca418519fc2626080a55f5137f67.zip | |
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
Notes
Notes:
svn path=/head/; revision=362450
Diffstat (limited to 'sys/sys/tree.h')
| -rw-r--r-- | sys/sys/tree.h | 26 |
1 files changed, 11 insertions, 15 deletions
diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 41eff928e8ed..313545a67301 100644 --- a/sys/sys/tree.h +++ b/sys/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); \ |