git: 36447829aee5 - main - rb_tree: drop needless tests from rb_next, rb_prev
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Fri, 10 Jun 2022 21:56:17 UTC
The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=36447829aee545ad9eafbfff3a783ee58cfb28fd commit 36447829aee545ad9eafbfff3a783ee58cfb28fd Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2022-06-10 21:53:16 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2022-06-10 21:53:16 +0000 rb_tree: drop needless tests from rb_next, rb_prev In RB_NEXT, when there is no RB_RIGHT node, the search must proceed through the parent node. There is code written to handle the case when the parent is non-NULL and the current element is the left child of that parent. If you assume that the current element is either the left child of its parent, or the right child of its parent, but not both, then this test is not necessary. Instead of assigning RB_PARENT(elm, field) to elm when elm == RB_LEFT, removing the test has the code assign RB_PARENT(elm, field) to elm when elm != RB_RIGHT. There's no need to examine the RB_LEFT field at all. This change removes that needless RB_LEFT test, and makes a similar change to the RB_PREV implementation. Reviewed by: alc MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D35450 --- sys/sys/tree.h | 22 ++++++---------------- 1 file changed, 6 insertions(+), 16 deletions(-) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index bc01e4de910a..0403288d1d68 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -719,15 +719,10 @@ name##_RB_NEXT(struct type *elm) \ while (RB_LEFT(elm, field)) \ elm = RB_LEFT(elm, field); \ } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ + while (RB_PARENT(elm, field) && \ + (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ elm = RB_PARENT(elm, field); \ - } \ + elm = RB_PARENT(elm, field); \ } \ return (elm); \ } @@ -742,15 +737,10 @@ name##_RB_PREV(struct type *elm) \ while (RB_RIGHT(elm, field)) \ elm = RB_RIGHT(elm, field); \ } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ + while (RB_PARENT(elm, field) && \ + (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ elm = RB_PARENT(elm, field); \ - } \ + elm = RB_PARENT(elm, field); \ } \ return (elm); \ }