From: Sebastian Huber <sebastian.huber@embedded-brains.de>
To: newlib@sourceware.org
Subject: [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD
Date: Mon, 19 Oct 2020 18:05:13 +0200 [thread overview]
Message-ID: <20201019160522.15408-1-sebastian.huber@embedded-brains.de> (raw)
This patch set adds some changes after the last synchronization point with
FreeBSD to Newlib. In a simple benchmark, the node insert/extract performance
improved.
In an intermediate step of this patch set the node color member is removed.
Later it is restored. I propose to keep the patch series as is to have the
same change history as FreeBSD.
FreeBSD also changed the implementation to so that the node color is stored in
the parent pointer in follow up patches. In addition, they changed the
algorithm from red-black to weak AVL. These changes are NOT INCLUDED, since
they break the ABI/API. I did some rough benchmarking and was not immediately
convinced that the new implementation in FreeBSD is better.
dougm (10):
Correct the use of RB_AUGMENT in the RB_TREE
For the case when RB_REMOVE requires a nontrivial
RB_REMOVE invokes RB_REMOVE_COLOR either when
Remove from RB_REMOVE_COLOR some null checks
To reduce the size of an rb_node, drop the color
Restore an RB_COLOR macro, for the benefit of
Fixup r361997 by balancing parens. Duh.
Linuxkpi uses the rb-tree structures
In concluding RB_REMOVE_COLOR, in the case when
Define RB_SET_PARENT to do all assignments
trasz (1):
Add RB_REINSERT(3), a low overhead alternative to
newlib/libc/include/sys/tree.h | 273 ++++++++++++++++-----------------
1 file changed, 130 insertions(+), 143 deletions(-)
--
2.26.2
next reply other threads:[~2020-10-19 16:05 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-10-19 16:05 Sebastian Huber [this message]
2020-10-19 16:05 ` [PATCH 01/11] Add RB_REINSERT(3), a low overhead alternative to Sebastian Huber
2020-10-19 16:05 ` [PATCH 02/11] Correct the use of RB_AUGMENT in the RB_TREE Sebastian Huber
2020-10-19 16:05 ` [PATCH 03/11] For the case when RB_REMOVE requires a nontrivial Sebastian Huber
2020-10-19 16:05 ` [PATCH 04/11] RB_REMOVE invokes RB_REMOVE_COLOR either when Sebastian Huber
2020-10-19 16:05 ` [PATCH 05/11] Remove from RB_REMOVE_COLOR some null checks Sebastian Huber
2020-10-19 16:05 ` [PATCH 06/11] To reduce the size of an rb_node, drop the color Sebastian Huber
2020-10-19 16:05 ` [PATCH 07/11] Restore an RB_COLOR macro, for the benefit of Sebastian Huber
2020-10-19 16:05 ` [PATCH 08/11] Fixup r361997 by balancing parens. Duh Sebastian Huber
2020-10-19 16:05 ` [PATCH 09/11] Linuxkpi uses the rb-tree structures Sebastian Huber
2020-10-26 9:52 ` [PATCH 00/11] Synchronize <sys/tree.h> with FreeBSD Corinna Vinschen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20201019160522.15408-1-sebastian.huber@embedded-brains.de \
--to=sebastian.huber@embedded-brains.de \
--cc=newlib@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).