Author: trasz
Date: Sat Sep 28 09:50:01 2019
New Revision: 352839
URL: https://svnweb.freebsd.org/changeset/base/352839
Log:
Rename ARB_REBALANCE(3) to ARB_REINSERT(3) to match tree(3),
and document it.
MFC after: 2 weeks
Sponsored by: Klara Inc, Netflix
Modified:
head/share/man/man3/Makefile
head/share/man/man3/arb.3
head/sys/sys/arb.h
Modified: head/share/man/man3/Makefile
==============================================================================
--- head/share/man/man3/Makefile Sat Sep 28 09:37:05 2019
(r352838)
+++ head/share/man/man3/Makefile Sat Sep 28 09:50:01 2019
(r352839)
@@ -65,6 +65,7 @@ MLINKS= arb.3 ARB8_ENTRY.3 \
arb.3 ARB_PARENT.3 \
arb.3 ARB_PARENTIDX.3 \
arb.3 ARB_PREV.3 \
+ arb.3 ARB_REINSERT.3 \
arb.3 ARB_REMOVE.3 \
arb.3 ARB_RIGHT.3 \
arb.3 ARB_RIGHTIDX.3 \
Modified: head/share/man/man3/arb.3
==============================================================================
--- head/share/man/man3/arb.3 Sat Sep 28 09:37:05 2019 (r352838)
+++ head/share/man/man3/arb.3 Sat Sep 28 09:50:01 2019 (r352839)
@@ -30,7 +30,7 @@
.\"
.\" $FreeBSD$
.\"
-.Dd May 8, 2019
+.Dd September 28, 2019
.Dt ARB 3
.Os
.Sh NAME
@@ -45,6 +45,7 @@
.Nm ARB_PROTOTYPE_NEXT ,
.Nm ARB_PROTOTYPE_PREV ,
.Nm ARB_PROTOTYPE_MINMAX ,
+.Nm ARB_PROTOTYPE_REINSERT ,
.Nm ARB_GENERATE ,
.Nm ARB_GENERATE_STATIC ,
.Nm ARB_GENERATE_INSERT ,
@@ -56,6 +57,7 @@
.Nm ARB_GENERATE_NEXT ,
.Nm ARB_GENERATE_PREV ,
.Nm ARB_GENERATE_MINMAX ,
+.Nm ARB_GENERATE_REINSERT ,
.Nm ARB8_ENTRY ,
.Nm ARB16_ENTRY ,
.Nm ARB32_ENTRY ,
@@ -91,7 +93,8 @@
.Nm ARB_FOREACH_REVERSE_SAFE ,
.Nm ARB_INIT ,
.Nm ARB_INSERT ,
-.Nm ARB_REMOVE
+.Nm ARB_REMOVE ,
+.Nm ARB_REINSERT
.Nd "array-based red-black trees"
.Sh SYNOPSIS
.In sys/arb.h
@@ -106,6 +109,7 @@
.Fn ARB_PROTOTYPE_NEXT NAME TYPE ATTR
.Fn ARB_PROTOTYPE_PREV NAME TYPE ATTR
.Fn ARB_PROTOTYPE_MINMAX NAME TYPE ATTR
+.Fn ARB_PROTOTYPE_REINSERT NAME TYPE ATTR
.Fn ARB_GENERATE NAME TYPE FIELD CMP
.Fn ARB_GENERATE_STATIC NAME TYPE FIELD CMP
.Fn ARB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
@@ -117,6 +121,7 @@
.Fn ARB_GENERATE_NEXT NAME TYPE FIELD ATTR
.Fn ARB_GENERATE_PREV NAME TYPE FIELD ATTR
.Fn ARB_GENERATE_MINMAX NAME TYPE FIELD ATTR
+.Fn ARB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR
.Fn ARB<8|16|32>_ENTRY
.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
.Ft "size_t"
@@ -172,6 +177,8 @@
.Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
.Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm"
+.Ft "struct TYPE *"
+.Fn ARB_REINSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
.Sh DESCRIPTION
These macros define data structures for and array-based red-black trees.
They use a single, continuous chunk of memory, and are useful
@@ -297,8 +304,9 @@ Individual prototypes can be declared with
.Fn ARB_PROTOTYPE_NFIND ,
.Fn ARB_PROTOTYPE_NEXT ,
.Fn ARB_PROTOTYPE_PREV ,
+.Fn ARB_PROTOTYPE_MINMAX ,
and
-.Fn ARB_PROTOTYPE_MINMAX
+.Fn ARB_PROTOTYPE_REINSERT
in case not all functions are required.
The individual prototype macros expect
.Fa NAME ,
@@ -331,8 +339,9 @@ As an alternative individual function bodies are gener
.Fn ARB_GENERATE_NFIND ,
.Fn ARB_GENERATE_NEXT ,
.Fn ARB_GENERATE_PREV ,
+.Fn ARB_GENERATE_MINMAX ,
and
-.Fn ARB_GENERATE_MINMAX
+.Fn ARB_GENERATE_REINSERT
macros.
.Pp
Finally,
@@ -464,6 +473,18 @@ Accordingly,
returns the pointer to the removed element otherwise they return
.Dv NULL
to indicate an error.
+.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 SEE ALSO
.Xr queue 3 ,
.Xr tree 3
Modified: head/sys/sys/arb.h
==============================================================================
--- head/sys/sys/arb.h Sat Sep 28 09:37:05 2019 (r352838)
+++ head/sys/sys/arb.h Sat Sep 28 09:50:01 2019 (r352839)
@@ -253,7 +253,7 @@ struct {
\
ARB_PROTOTYPE_PREV(name, type, attr); \
ARB_PROTOTYPE_CMINMAX(name, type, attr); \
ARB_PROTOTYPE_MINMAX(name, type, attr); \
- ARB_PROTOTYPE_REBALANCE(name, type, attr);
+ ARB_PROTOTYPE_REINSERT(name, type, attr);
#define ARB_PROTOTYPE_INSERT_COLOR(name, type, attr)
\
attr void name##_ARB_INSERT_COLOR(struct name *, struct type *)
#define ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr)
\
@@ -289,8 +289,8 @@ struct {
\
attr const struct type *name##_ARB_CMINMAX(const struct name *, int)
#define ARB_PROTOTYPE_MINMAX(name, type, attr)
\
attr struct type *name##_ARB_MINMAX(const struct name *, int)
-#define ARB_PROTOTYPE_REBALANCE(name, type, attr) \
- attr struct type *name##_ARB_REBALANCE(struct name *, struct type *)
+#define ARB_PROTOTYPE_REINSERT(name, type, attr) \
+ attr struct type *name##_ARB_REINSERT(struct name *, struct type *)
#define ARB_GENERATE(name, type, field, cmp)
\
ARB_GENERATE_INTERNAL(name, type, field, cmp,)
@@ -309,7 +309,7 @@ struct {
\
ARB_GENERATE_PREV(name, type, field, attr) \
ARB_GENERATE_CMINMAX(name, type, field, attr) \
ARB_GENERATE_MINMAX(name, type, field, attr) \
- ARB_GENERATE_REBALANCE(name, type, field, cmp, attr)
+ ARB_GENERATE_REINSERT(name, type, field, cmp, attr)
#define ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \
attr void \
@@ -695,9 +695,9 @@ attr struct type *
\
name##_ARB_MINMAX(const struct name *head, int val) \
{ return (__DECONST(struct type *, name##_ARB_CMINMAX(head, val))); }
-#define ARB_GENERATE_REBALANCE(name, type, field, cmp, attr)
\
+#define ARB_GENERATE_REINSERT(name, type, field, cmp, attr)
\
attr struct type * \
-name##_ARB_REBALANCE(struct name *head, struct type *elm) \
+name##_ARB_REINSERT(struct name *head, struct type *elm) \
{ \
struct type *cmpelm; \
if (((cmpelm = ARB_PREV(name, head, elm)) != NULL && \
@@ -731,7 +731,7 @@ name##_ARB_REBALANCE(struct name *head, struct type *e
name##_ARB_CMINMAX(x, ARB_INF) : ARB_CNODE(x, ARB_MAXIDX(x)))
#define ARB_MAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \
name##_ARB_MINMAX(x, ARB_INF) : ARB_NODE(x, ARB_MAXIDX(x)))
-#define ARB_REBALANCE(name, x, y) name##_ARB_REBALANCE(x, y)
+#define ARB_REINSERT(name, x, y) name##_ARB_REINSERT(x, y)
#define ARB_FOREACH(x, name, head)
\
for ((x) = ARB_MIN(name, head); \
_______________________________________________
svn-src-head@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
