From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dedi548.your-server.de (dedi548.your-server.de [85.10.215.148]) by sourceware.org (Postfix) with ESMTPS id 2A5D83857C56 for ; Mon, 19 Oct 2020 16:05:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 2A5D83857C56 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=embedded-brains.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=sebastian.huber@embedded-brains.de Received: from sslproxy02.your-server.de ([78.47.166.47]) by dedi548.your-server.de with esmtpsa (TLSv1.3:TLS_AES_256_GCM_SHA384:256) (Exim 4.92.3) (envelope-from ) id 1kUXf1-0004OK-3B for newlib@sourceware.org; Mon, 19 Oct 2020 18:05:23 +0200 Received: from [82.100.198.138] (helo=mail.embedded-brains.de) by sslproxy02.your-server.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (Exim 4.92) (envelope-from ) id 1kUXf1-0002ic-0S for newlib@sourceware.org; Mon, 19 Oct 2020 18:05:23 +0200 Received: from localhost (localhost.localhost [127.0.0.1]) by mail.embedded-brains.de (Postfix) with ESMTP id A99532A168C for ; Mon, 19 Oct 2020 18:04:10 +0200 (CEST) Received: from mail.embedded-brains.de ([127.0.0.1]) by localhost (zimbra.eb.localhost [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id jEVl6bSEsSEg for ; Mon, 19 Oct 2020 18:04:10 +0200 (CEST) Received: from localhost (localhost.localhost [127.0.0.1]) by mail.embedded-brains.de (Postfix) with ESMTP id 5C9852A1683 for ; Mon, 19 Oct 2020 18:04:10 +0200 (CEST) X-Virus-Scanned: amavisd-new at zimbra.eb.localhost Received: from mail.embedded-brains.de ([127.0.0.1]) by localhost (zimbra.eb.localhost [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id QB2YNa3Lnbab for ; Mon, 19 Oct 2020 18:04:10 +0200 (CEST) Received: from linux-diu0.suse (unknown [192.168.96.161]) by mail.embedded-brains.de (Postfix) with ESMTP id 3C3A92A1610 for ; Mon, 19 Oct 2020 18:04:10 +0200 (CEST) From: Sebastian Huber To: newlib@sourceware.org Subject: [PATCH 00/11] Synchronize with FreeBSD Date: Mon, 19 Oct 2020 18:05:13 +0200 Message-Id: <20201019160522.15408-1-sebastian.huber@embedded-brains.de> X-Mailer: git-send-email 2.26.2 MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-Authenticated-Sender: smtp-embedded@poldinet.de X-Virus-Scanned: Clear (ClamAV 0.102.4/25962/Mon Oct 19 15:57:02 2020) X-Spam-Status: No, score=-5.7 required=5.0 tests=BAYES_00, KAM_DMARC_STATUS, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: newlib@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Newlib mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 19 Oct 2020 16:05:25 -0000 This patch set adds some changes after the last synchronization point wit= h FreeBSD to Newlib. In a simple benchmark, the node insert/extract perfor= mance improved. In an intermediate step of this patch set the node color member is remove= d. Later it is restored. I propose to keep the patch series as is to have t= he same change history as FreeBSD. FreeBSD also changed the implementation to so that the node color is stor= ed 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, si= nce they break the ABI/API. I did some rough benchmarking and was not immedi= ately 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(-) --=20 2.26.2