Date: Sat, 28 Sep 2019 09:50:02 +0000 (UTC) From: Edward Tomasz Napierala <trasz@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r352839 - in head: share/man/man3 sys/sys Message-ID: <201909280950.x8S9o2XY066708@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
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); \
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201909280950.x8S9o2XY066708>