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 33531386101F for ; Mon, 19 Oct 2020 16:05:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 33531386101F 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-0004OS-7v 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-0002k1-4n 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 C97CF2A1684 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 gz8HG8pphUWq 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 6719F2A1686 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 RQx-DtuFka8a 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 4841E2A165B for ; Mon, 19 Oct 2020 18:04:10 +0200 (CEST) From: Sebastian Huber To: newlib@sourceware.org Subject: [PATCH 01/11] Add RB_REINSERT(3), a low overhead alternative to Date: Mon, 19 Oct 2020 18:05:14 +0200 Message-Id: <20201019160522.15408-2-sebastian.huber@embedded-brains.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20201019160522.15408-1-sebastian.huber@embedded-brains.de> References: <20201019160522.15408-1-sebastian.huber@embedded-brains.de> 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=-11.7 required=5.0 tests=BAYES_00, GIT_PATCH_0, 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 From: trasz removing a node and reinserting it back with an updated key. This is one of dependencies for the upcoming stats(3) code. Reviewed by: cem Obtained from: Netflix MFC after: 2 weeks Sponsored by: Klara Inc, Netflix Differential Revision: https://reviews.freebsd.org/D21786 --- newlib/libc/include/sys/tree.h | 26 ++++++++++++++++++++++++-- 1 file changed, 24 insertions(+), 2 deletions(-) diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tre= e.h index fd66ceba1..0eacf951d 100644 --- a/newlib/libc/include/sys/tree.h +++ b/newlib/libc/include/sys/tree.h @@ -393,7 +393,8 @@ struct { \ RB_PROTOTYPE_NFIND(name, type, attr); \ RB_PROTOTYPE_NEXT(name, type, attr); \ RB_PROTOTYPE_PREV(name, type, attr); \ - RB_PROTOTYPE_MINMAX(name, type, attr); + RB_PROTOTYPE_MINMAX(name, type, attr); \ + RB_PROTOTYPE_REINSERT(name, type, attr); #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ attr void name##_RB_INSERT_COLOR(struct name *, struct type *) #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ @@ -412,6 +413,8 @@ struct { \ attr struct type *name##_RB_PREV(struct type *) #define RB_PROTOTYPE_MINMAX(name, type, attr) \ attr struct type *name##_RB_MINMAX(struct name *, int) +#define RB_PROTOTYPE_REINSERT(name, type, attr) \ + attr struct type *name##_RB_REINSERT(struct name *, struct type *) =20 /* Main rb operation. * Moves node close to the key of elm to top @@ -429,7 +432,9 @@ struct { \ RB_GENERATE_NFIND(name, type, field, cmp, attr) \ RB_GENERATE_NEXT(name, type, field, attr) \ RB_GENERATE_PREV(name, type, field, attr) \ - RB_GENERATE_MINMAX(name, type, field, attr) + RB_GENERATE_MINMAX(name, type, field, attr) \ + RB_GENERATE_REINSERT(name, type, field, cmp, attr) + =20 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ attr void \ @@ -758,6 +763,22 @@ name##_RB_MINMAX(struct name *head, int val) \ return (parent); \ } =20 +#define RB_GENERATE_REINSERT(name, type, field, cmp, attr) \ +attr struct type * \ +name##_RB_REINSERT(struct name *head, struct type *elm) \ +{ \ + struct type *cmpelm; \ + if (((cmpelm =3D RB_PREV(name, head, elm)) !=3D NULL && \ + cmp(cmpelm, elm) >=3D 0) || \ + ((cmpelm =3D RB_NEXT(name, head, elm)) !=3D NULL && \ + cmp(elm, cmpelm) >=3D 0)) { \ + /* XXXLAS: Remove/insert is heavy handed. */ \ + RB_REMOVE(name, head, elm); \ + return (RB_INSERT(name, head, elm)); \ + } \ + return (NULL); \ +} \ + #define RB_NEGINF -1 #define RB_INF 1 =20 @@ -769,6 +790,7 @@ name##_RB_MINMAX(struct name *head, int val) \ #define RB_PREV(name, x, y) name##_RB_PREV(y) #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) +#define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y) =20 #define RB_FOREACH(x, name, head) \ for ((x) =3D RB_MIN(name, head); \ --=20 2.26.2