From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1921) id C3F643894C34; Mon, 26 Oct 2020 13:31:52 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C3F643894C34 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Sebastian Huber To: newlib-cvs@sourceware.org Subject: [newlib-cygwin] Add RB_REINSERT(3), a low overhead alternative to X-Act-Checkin: newlib-cygwin X-Git-Author: trasz X-Git-Refname: refs/heads/master X-Git-Oldrev: 303c61925d9256be02dcbda8f1e5e0d4adf8b3b9 X-Git-Newrev: fd4cbaba7aaf4a76082b480e1fbeadda0e0faa0c Message-Id: <20201026133152.C3F643894C34@sourceware.org> Date: Mon, 26 Oct 2020 13:31:52 +0000 (GMT) X-BeenThere: newlib-cvs@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Newlib GIT logs List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 26 Oct 2020 13:31:52 -0000 https://sourceware.org/git/gitweb.cgi?p=newlib-cygwin.git;h=fd4cbaba7aaf4a76082b480e1fbeadda0e0faa0c commit fd4cbaba7aaf4a76082b480e1fbeadda0e0faa0c Author: trasz Date: Sat Sep 28 09:22:52 2019 +0000 Add RB_REINSERT(3), a low overhead alternative to 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 Diff: --- 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/tree.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 *) /* 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) + #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); \ } +#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 = RB_PREV(name, head, elm)) != NULL && \ + cmp(cmpelm, elm) >= 0) || \ + ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \ + cmp(elm, cmpelm) >= 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 @@ -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) #define RB_FOREACH(x, name, head) \ for ((x) = RB_MIN(name, head); \