Author: trasz Date: Sat Sep 28 09:22:52 2019 New Revision: 352837 URL: https://svnweb.freebsd.org/changeset/base/352837
Log: 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 Modified: head/share/man/man3/Makefile head/share/man/man3/tree.3 head/sys/sys/tree.h Modified: head/share/man/man3/Makefile ============================================================================== --- head/share/man/man3/Makefile Sat Sep 28 09:12:41 2019 (r352836) +++ head/share/man/man3/Makefile Sat Sep 28 09:22:52 2019 (r352837) @@ -324,6 +324,7 @@ MLINKS+= tree.3 RB_EMPTY.3 \ tree.3 RB_PROTOTYPE_REMOVE.3 \ tree.3 RB_PROTOTYPE_REMOVE_COLOR.3 \ tree.3 RB_PROTOTYPE_STATIC.3 \ + tree.3 RB_REINSERT.3 \ tree.3 RB_REMOVE.3 \ tree.3 RB_RIGHT.3 \ tree.3 RB_ROOT.3 \ Modified: head/share/man/man3/tree.3 ============================================================================== --- head/share/man/man3/tree.3 Sat Sep 28 09:12:41 2019 (r352836) +++ head/share/man/man3/tree.3 Sat Sep 28 09:22:52 2019 (r352837) @@ -30,7 +30,7 @@ .\" .\" $FreeBSD$ .\" -.Dd May 8, 2019 +.Dd September 28, 2019 .Dt TREE 3 .Os .Sh NAME @@ -62,6 +62,7 @@ .Nm RB_PROTOTYPE_NEXT , .Nm RB_PROTOTYPE_PREV , .Nm RB_PROTOTYPE_MINMAX , +.Nm RB_PROTOTYPE_REINSERT , .Nm RB_GENERATE , .Nm RB_GENERATE_STATIC , .Nm RB_GENERATE_INSERT , @@ -73,6 +74,7 @@ .Nm RB_GENERATE_NEXT , .Nm RB_GENERATE_PREV , .Nm RB_GENERATE_MINMAX , +.Nm RB_GENERATE_REINSERT , .Nm RB_ENTRY , .Nm RB_HEAD , .Nm RB_INITIALIZER , @@ -95,7 +97,8 @@ .Nm RB_FOREACH_REVERSE_SAFE , .Nm RB_INIT , .Nm RB_INSERT , -.Nm RB_REMOVE +.Nm RB_REMOVE , +.Nm RB_REINSERT .Nd "implementations of splay and red-black trees" .Sh SYNOPSIS .In sys/tree.h @@ -138,6 +141,7 @@ .Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR .Fn RB_PROTOTYPE_PREV NAME TYPE ATTR .Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR +.Fn RB_PROTOTYPE_REINSERT NAME TYPE ATTR .Fn RB_GENERATE NAME TYPE FIELD CMP .Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP .Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR @@ -149,6 +153,7 @@ .Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR .Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR .Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR +.Fn RB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR .Fn RB_ENTRY TYPE .Fn RB_HEAD HEADNAME TYPE .Fn RB_INITIALIZER "RB_HEAD *head" @@ -186,6 +191,8 @@ .Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_REINSERT NAME "RB_HEAD *head" "struct TYPE *elm" .Sh DESCRIPTION These macros define data structures for different types of trees: splay trees and red-black trees. @@ -422,8 +429,9 @@ Individual prototypes can be declared with .Fn RB_PROTOTYPE_NFIND , .Fn RB_PROTOTYPE_NEXT , .Fn RB_PROTOTYPE_PREV , +.Fn RB_PROTOTYPE_MINMAX , and -.Fn RB_PROTOTYPE_MINMAX +.Fn RB_PROTOTYPE_REINSERT in case not all functions are required. The individual prototype macros expect .Fa NAME , @@ -456,8 +464,9 @@ As an alternative individual function bodies are gener .Fn RB_GENERATE_NFIND , .Fn RB_GENERATE_NEXT , .Fn RB_GENERATE_PREV , +.Fn RB_GENERATE_MINMAX , and -.Fn RB_GENERATE_MINMAX +.Fn RB_GENERATE_REINSERT macros. .Pp Finally, @@ -559,6 +568,18 @@ and will be overwritten to provide safe traversal. The .Fn RB_EMPTY macro should be used to check whether a red-black tree is empty. +.Pp +The +.Fn RB_REINSERT +macro updates the position of the element +.Fa elm +in the tree. +This must be called if a member of a +.Nm tree +is modified in a way that affects comparison, such as by modifying +a node's key. +This is a lower overhead alternative to removing the element +and reinserting it again. .Sh EXAMPLES The following example demonstrates how to declare a red-black tree holding integers. Modified: head/sys/sys/tree.h ============================================================================== --- head/sys/sys/tree.h Sat Sep 28 09:12:41 2019 (r352836) +++ head/sys/sys/tree.h Sat Sep 28 09:22:52 2019 (r352837) @@ -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,8 +432,10 @@ 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 \ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ @@ -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); \ _______________________________________________ svn-src-all@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-all To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
