diff options
| author | trasz <trasz@FreeBSD.org> | 2019-09-28 09:22:52 +0000 |
|---|---|---|
| committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2020-10-26 14:18:46 +0100 |
| commit | fd4cbaba7aaf4a76082b480e1fbeadda0e0faa0c (patch) | |
| tree | 1a2e74f739e75921a750739c8cd359e5557a62f4 | |
| parent | 303c61925d9256be02dcbda8f1e5e0d4adf8b3b9 (diff) | |
| download | newlib-fd4cbaba7aaf4a76082b480e1fbeadda0e0faa0c.zip newlib-fd4cbaba7aaf4a76082b480e1fbeadda0e0faa0c.tar.gz newlib-fd4cbaba7aaf4a76082b480e1fbeadda0e0faa0c.tar.bz2 | |
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
| -rw-r--r-- | newlib/libc/include/sys/tree.h | 26 |
1 files changed, 24 insertions, 2 deletions
diff --git a/newlib/libc/include/sys/tree.h b/newlib/libc/include/sys/tree.h index fd66ceb..0eacf95 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); \ |