Date: Thu, 25 Aug 2022 07:27:44 GMT From: Doug Moore <dougm@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: git: b6ce129d24ff - main - rb_tree: optimize rb_insert Message-ID: <202208250727.27P7Ri6M084742@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=b6ce129d24ffe393c43378b1c922d1e56ea2be67 commit b6ce129d24ffe393c43378b1c922d1e56ea2be67 Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2022-08-25 07:26:04 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2022-08-25 07:26:04 +0000 rb_tree: optimize rb_insert In searching for where to insert a new node, RB_INSERT discards the address of the pointer that will have to be modified, so that it must find it again from the values of 'parent' and 'comp'. Stop discarding that address, and so avoid having to recompute it. Reviewed by: alc MFC after: 3 weeks Differential Revision: https://reviews.freebsd.org/D36317 --- sys/sys/tree.h | 21 ++++++++------------- 1 file changed, 8 insertions(+), 13 deletions(-) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 1d4271c2144a..35c6b28be868 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -728,26 +728,21 @@ attr struct type * \ name##_RB_INSERT(struct name *head, struct type *elm) \ { \ struct type *tmp; \ + struct type **tmpp = &RB_ROOT(head); \ struct type *parent = NULL; \ - __typeof(cmp(NULL, NULL)) comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ + \ + while ((tmp = *tmpp) != NULL) { \ parent = tmp; \ - comp = (cmp)(elm, parent); \ + __typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \ if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ + tmpp = &RB_LEFT(parent, field); \ else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ + tmpp = &RB_RIGHT(parent, field); \ else \ - return (tmp); \ + return (parent); \ } \ RB_SET(elm, parent, field); \ - if (parent == NULL) \ - RB_ROOT(head) = elm; \ - else if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ + *tmpp = elm; \ name##_RB_INSERT_COLOR(head, elm); \ RB_UPDATE_AUGMENT(elm, field); \ return (NULL); \
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202208250727.27P7Ri6M084742>