diff options
| -rw-r--r-- | share/man/man3/Makefile | 1 | ||||
| -rw-r--r-- | share/man/man3/arb.3 | 29 | ||||
| -rw-r--r-- | sys/sys/arb.h | 14 |
3 files changed, 33 insertions, 11 deletions
diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile index d8dae7ce5e92..d114496cd734 100644 --- a/share/man/man3/Makefile +++ b/share/man/man3/Makefile @@ -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 \ diff --git a/share/man/man3/arb.3 b/share/man/man3/arb.3 index e230d89657f2..ba81532b151a 100644 --- a/share/man/man3/arb.3 +++ b/share/man/man3/arb.3 @@ -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 generated with the .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 diff --git a/sys/sys/arb.h b/sys/sys/arb.h index 71b81b645d04..e5f0a450cb3a 100644 --- a/sys/sys/arb.h +++ b/sys/sys/arb.h @@ -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 *elm) \ 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); \ |