svn commit: r352837 - in head: share/man/man3 sys/sys
Edward Tomasz Napierala
trasz at FreeBSD.org
Sat Sep 28 09:22:53 UTC 2019
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); \
More information about the svn-src-all
mailing list