Index: share/man/man3/Makefile =================================================================== --- share/man/man3/Makefile +++ share/man/man3/Makefile @@ -175,7 +175,42 @@ timeradd.3 timespecclear.3 \ timeradd.3 timespecisset.3 \ timeradd.3 timespeccmp.3 -MLINKS+= tree.3 RB_EMPTY.3 \ +MLINKS+= tree.3 ARB8_ENTRY.3 \ + tree.3 ARB16_ENTRY.3 \ + tree.3 ARB32_ENTRY.3 \ + tree.3 ARB8_HEAD.3 \ + tree.3 ARB16_HEAD.3 \ + tree.3 ARB32_HEAD.3 \ + tree.3 ARB_INITIALIZER.3 \ + tree.3 ARB_ROOT.3 \ + tree.3 ARB_EMPTY.3 \ + tree.3 ARB_FULL.3 \ + tree.3 ARB_CURNODES.3 \ + tree.3 ARB_MAXNODES.3 \ + tree.3 ARB_NEXT.3 \ + tree.3 ARB_PREV.3 \ + tree.3 ARB_MIN.3 \ + tree.3 ARB_MAX.3 \ + tree.3 ARB_FIND.3 \ + tree.3 ARB_NFIND.3 \ + tree.3 ARB_LEFT.3 \ + tree.3 ARB_LEFTIDX.3 \ + tree.3 ARB_RIGHT.3 \ + tree.3 ARB_RIGHTIDX.3 \ + tree.3 ARB_PARENT.3 \ + tree.3 ARB_PARENTIDX.3 \ + tree.3 ARB_GETFREE.3 \ + tree.3 ARB_FREEIDX.3 \ + tree.3 ARB_FOREACH.3 \ + tree.3 ARB_FOREACH_FROM.3 \ + tree.3 ARB_FOREACH_SAFE.3 \ + tree.3 ARB_FOREACH_REVERSE.3 \ + tree.3 ARB_FOREACH_REVERSE_FROM.3 \ + tree.3 ARB_FOREACH_REVERSE_SAFE.3 \ + tree.3 ARB_INIT.3 \ + tree.3 ARB_INSERT.3 \ + tree.3 ARB_REMOVE.3 \ + tree.3 RB_EMPTY.3 \ tree.3 RB_ENTRY.3 \ tree.3 RB_FIND.3 \ tree.3 RB_FOREACH.3 \ Index: share/man/man3/tree.3 =================================================================== --- share/man/man3/tree.3 +++ share/man/man3/tree.3 @@ -95,7 +95,64 @@ .Nm RB_FOREACH_REVERSE_SAFE , .Nm RB_INIT , .Nm RB_INSERT , -.Nm RB_REMOVE +.Nm RB_REMOVE , +.Nm ARB_PROTOTYPE , +.Nm ARB_PROTOTYPE_STATIC , +.Nm ARB_PROTOTYPE_INSERT , +.Nm ARB_PROTOTYPE_INSERT_COLOR , +.Nm ARB_PROTOTYPE_REMOVE , +.Nm ARB_PROTOTYPE_REMOVE_COLOR , +.Nm ARB_PROTOTYPE_FIND , +.Nm ARB_PROTOTYPE_NFIND , +.Nm ARB_PROTOTYPE_NEXT , +.Nm ARB_PROTOTYPE_PREV , +.Nm ARB_PROTOTYPE_MINMAX , +.Nm ARB_GENERATE , +.Nm ARB_GENERATE_STATIC , +.Nm ARB_GENERATE_INSERT , +.Nm ARB_GENERATE_INSERT_COLOR , +.Nm ARB_GENERATE_REMOVE , +.Nm ARB_GENERATE_REMOVE_COLOR , +.Nm ARB_GENERATE_FIND , +.Nm ARB_GENERATE_NFIND , +.Nm ARB_GENERATE_NEXT , +.Nm ARB_GENERATE_PREV , +.Nm ARB_GENERATE_MINMAX , +.Nm ARB8_ENTRY , +.Nm ARB16_ENTRY , +.Nm ARB32_ENTRY , +.Nm ARB8_HEAD , +.Nm ARB16_HEAD , +.Nm ARB32_HEAD , +.Nm ARB_INITIALIZER , +.Nm ARB_ROOT , +.Nm ARB_EMPTY , +.Nm ARB_FULL , +.Nm ARB_CURNODES , +.Nm ARB_MAXNODES , +.Nm ARB_NEXT , +.Nm ARB_PREV , +.Nm ARB_MIN , +.Nm ARB_MAX , +.Nm ARB_FIND , +.Nm ARB_NFIND , +.Nm ARB_LEFT , +.Nm ARB_LEFTIDX , +.Nm ARB_RIGHT , +.Nm ARB_RIGHTIDX , +.Nm ARB_PARENT , +.Nm ARB_PARENTIDX , +.Nm ARB_GETFREE , +.Nm ARB_FREEIDX , +.Nm ARB_FOREACH , +.Nm ARB_FOREACH_FROM , +.Nm ARB_FOREACH_SAFE , +.Nm ARB_FOREACH_REVERSE , +.Nm ARB_FOREACH_REVERSE_FROM , +.Nm ARB_FOREACH_REVERSE_SAFE , +.Nm ARB_INIT , +.Nm ARB_INSERT , +.Nm ARB_REMOVE .Nd "implementations of splay and red-black trees" .Sh SYNOPSIS .In sys/tree.h @@ -127,65 +184,86 @@ .Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" .Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm" -.Fn RB_PROTOTYPE NAME TYPE FIELD CMP -.Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP -.Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR -.Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR -.Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR -.Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR -.Fn RB_PROTOTYPE_FIND NAME TYPE ATTR -.Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR -.Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR -.Fn RB_PROTOTYPE_PREV NAME TYPE ATTR -.Fn RB_PROTOTYPE_MINMAX 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 -.Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR -.Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR -.Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR -.Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR -.Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR -.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 (A)RB_PROTOTYPE NAME TYPE FIELD CMP +.Fn (A)RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP +.Fn (A)RB_PROTOTYPE_INSERT NAME TYPE ATTR +.Fn (A)RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR +.Fn (A)RB_PROTOTYPE_REMOVE NAME TYPE ATTR +.Fn (A)RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR +.Fn (A)RB_PROTOTYPE_FIND NAME TYPE ATTR +.Fn (A)RB_PROTOTYPE_NFIND NAME TYPE ATTR +.Fn (A)RB_PROTOTYPE_NEXT NAME TYPE ATTR +.Fn (A)RB_PROTOTYPE_PREV NAME TYPE ATTR +.Fn (A)RB_PROTOTYPE_MINMAX NAME TYPE ATTR +.Fn (A)RB_GENERATE NAME TYPE FIELD CMP +.Fn (A)RB_GENERATE_STATIC NAME TYPE FIELD CMP +.Fn (A)RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR +.Fn (A)RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR +.Fn (A)RB_GENERATE_REMOVE NAME TYPE FIELD ATTR +.Fn (A)RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR +.Fn (A)RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR +.Fn (A)RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR +.Fn (A)RB_GENERATE_NEXT NAME TYPE FIELD ATTR +.Fn (A)RB_GENERATE_PREV NAME TYPE FIELD ATTR +.Fn (A)RB_GENERATE_MINMAX NAME TYPE FIELD ATTR .Fn RB_ENTRY TYPE .Fn RB_HEAD HEADNAME TYPE .Fn RB_INITIALIZER "RB_HEAD *head" +.Fn ARB<8|16|32>_ENTRY +.Fn ARB<8|16|32>_HEAD HEADNAME TYPE +.Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes" .Ft "struct TYPE *" -.Fn RB_ROOT "RB_HEAD *head" +.Fn (A)RB_ROOT "(A)RB_HEAD *head" .Ft "bool" -.Fn RB_EMPTY "RB_HEAD *head" +.Fn (A)RB_EMPTY "(A)RB_HEAD *head" +.Ft "bool" +.Fn ARB_FULL "ARB_HEAD *head" +.Ft "int<8|16|32>_t" +.Fn ARB_CURNODES "ARB_HEAD *head" +.Ft "int<8|16|32>_t" +.Fn ARB_MAXNODES "ARB_HEAD *head" .Ft "struct TYPE *" -.Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm" +.Fn (A)RB_NEXT NAME "(A)RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" -.Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm" +.Fn (A)RB_PREV NAME "(A)RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" -.Fn RB_MIN NAME "RB_HEAD *head" +.Fn (A)RB_MIN NAME "(A)RB_HEAD *head" .Ft "struct TYPE *" -.Fn RB_MAX NAME "RB_HEAD *head" +.Fn (A)RB_MAX NAME "(A)RB_HEAD *head" .Ft "struct TYPE *" -.Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm" +.Fn (A)RB_FIND NAME "(A)RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" -.Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm" +.Fn (A)RB_NFIND NAME "(A)RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" -.Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME" +.Fn (A)RB_LEFT "struct TYPE *elm" "(A)RB_ENTRY NAME" +.Ft "int<8|16|32>_t" +.Fn ARB_LEFTIDX "struct TYPE *elm" "ARB_ENTRY NAME" .Ft "struct TYPE *" -.Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME" +.Fn (A)RB_RIGHT "struct TYPE *elm" "(A)RB_ENTRY NAME" +.Ft "int<8|16|32>_t" +.Fn ARB_RIGHTIDX "struct TYPE *elm" "ARB_ENTRY NAME" .Ft "struct TYPE *" -.Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME" -.Fn RB_FOREACH VARNAME NAME "RB_HEAD *head" -.Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME" -.Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" -.Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head" -.Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME" -.Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" +.Fn (A)RB_PARENT "struct TYPE *elm" "(A)RB_ENTRY NAME" +.Ft "int<8|16|32>_t" +.Fn ARB_PARENTIDX "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn ARB_GETFREE "ARB_HEAD *head" +.Ft "int<8|16|32>_t" +.Fn ARB_FREEIDX "ARB_HEAD *head" +.Fn (A)RB_FOREACH VARNAME NAME "(A)RB_HEAD *head" +.Fn (A)RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME" +.Fn (A)RB_FOREACH_SAFE "VARNAME" "NAME" "(A)RB_HEAD *head" "TEMP_VARNAME" +.Fn (A)RB_FOREACH_REVERSE VARNAME NAME "(A)RB_HEAD *head" +.Fn (A)RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME" +.Fn (A)RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "(A)RB_HEAD *head" "TEMP_VARNAME" .Ft void .Fn RB_INIT "RB_HEAD *head" +.Ft void +.Fn ARB_INIT "ARB_HEAD *head" "int<8|16|32>_t maxnodes" .Ft "struct TYPE *" -.Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm" +.Fn (A)RB_INSERT NAME "(A)RB_HEAD *head" "struct TYPE *elm" .Ft "struct TYPE *" -.Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm" +.Fn (A)RB_REMOVE NAME "(A)RB_HEAD *head" "struct TYPE *elm" .Sh DESCRIPTION These macros define data structures for different types of trees: splay trees and red-black trees. @@ -195,7 +273,7 @@ is the name tag of a user defined structure that must contain a field of type .Vt SPLAY_ENTRY , or -.Vt RB_ENTRY , +.Vt Po A Pc Ns RB_ENTRY , named .Fa ENTRYNAME . The argument @@ -204,21 +282,21 @@ using the macros .Fn SPLAY_HEAD , or -.Fn RB_HEAD . +.Fn (A)RB_HEAD . The argument .Fa NAME has to be a unique name prefix for every tree that is defined. .Pp The function prototypes are declared with .Fn SPLAY_PROTOTYPE , -.Fn RB_PROTOTYPE , +.Fn (A)RB_PROTOTYPE , or -.Fn RB_PROTOTYPE_STATIC . +.Fn (A)RB_PROTOTYPE_STATIC . The function bodies are generated with .Fn SPLAY_GENERATE , -.Fn RB_GENERATE , +.Fn (A)RB_GENERATE , or -.Fn RB_GENERATE_STATIC . +.Fn (A)RB_GENERATE_STATIC . See the examples below for further explanation of how these macros are used. .Sh SPLAY TREES A splay tree is a self-organizing data structure. @@ -376,15 +454,30 @@ The maximum height of a red-black tree is .Fn 2lg "n + 1" . .Pp +.Fn RB_* +variant trees link an arbitrary number of individually allocated entries +together using memory pointers. +.Fn ARB_* +variant trees require entries to be allocated as an array, and uses array +indices to link entries together. +The maximum number of +.Fn ARB_* +tree entries is therefore constrained by the minimum of array size and choice of +signed integer data type used to store array indices. +.Pp A red-black tree is headed by a structure defined by the -.Fn RB_HEAD +.Fn (A)RB_HEAD macro. A -structure is declared as follows: +structure is declared with either of the following: .Bd -ragged -offset indent .Fn RB_HEAD HEADNAME TYPE .Va head ; .Ed +.Bd -ragged -offset indent +.Fn ARB<8|16|32>_HEAD HEADNAME TYPE +.Va head ; +.Ed .Pp where .Fa HEADNAME @@ -393,14 +486,33 @@ is the type of the elements to be inserted into the tree. .Pp The -.Fn RB_ENTRY +.Fn ARB_HEAD +variant includes a suffix denoting the signed integer data type size +.Pq in bits +used to store array indices. +For example, +.Fn ARB_HEAD8 +creates a red-black tree head strucutre with 8-bit signed array indices capable +of indexing up to 128 entries. +.Pp +The +.Fn (A)RB_ENTRY macro declares a structure that allows elements to be connected in the tree. +Similarly to the +.Fn ARB<8|16|32>_HEAD +macro, the +.Fn ARB_ENTRY +variant includes a suffix denoting the signed integer data type size +.Pq in bits +used to store array indices. +Entries should use the same number of bits as the tree head structure they will +be linked into. .Pp In order to use the functions that manipulate the tree structure, their prototypes need to be declared with the -.Fn RB_PROTOTYPE +.Fn (A)RB_PROTOTYPE or -.Fn RB_PROTOTYPE_STATIC +.Fn (A)RB_PROTOTYPE_STATIC macro, where .Fa NAME @@ -412,18 +524,18 @@ The .Fa FIELD argument is the name of the element defined by -.Fn RB_ENTRY . +.Fn (A)RB_ENTRY . Individual prototypes can be declared with -.Fn RB_PROTOTYPE_INSERT , -.Fn RB_PROTOTYPE_INSERT_COLOR , -.Fn RB_PROTOTYPE_REMOVE , -.Fn RB_PROTOTYPE_REMOVE_COLOR , -.Fn RB_PROTOTYPE_FIND , -.Fn RB_PROTOTYPE_NFIND , -.Fn RB_PROTOTYPE_NEXT , -.Fn RB_PROTOTYPE_PREV , +.Fn (A)RB_PROTOTYPE_INSERT , +.Fn (A)RB_PROTOTYPE_INSERT_COLOR , +.Fn (A)RB_PROTOTYPE_REMOVE , +.Fn (A)RB_PROTOTYPE_REMOVE_COLOR , +.Fn (A)RB_PROTOTYPE_FIND , +.Fn (A)RB_PROTOTYPE_NFIND , +.Fn (A)RB_PROTOTYPE_NEXT , +.Fn (A)RB_PROTOTYPE_PREV , and -.Fn RB_PROTOTYPE_MINMAX +.Fn (A)RB_PROTOTYPE_MINMAX in case not all functions are required. The individual prototype macros expect .Fa NAME , @@ -438,26 +550,26 @@ for static functions. .Pp The function bodies are generated with the -.Fn RB_GENERATE +.Fn (A)RB_GENERATE or -.Fn RB_GENERATE_STATIC +.Fn (A)RB_GENERATE_STATIC macro. These macros take the same arguments as the -.Fn RB_PROTOTYPE +.Fn (A)RB_PROTOTYPE and -.Fn RB_PROTOTYPE_STATIC +.Fn (A)RB_PROTOTYPE_STATIC macros, but should be used only once. As an alternative individual function bodies are generated with the -.Fn RB_GENERATE_INSERT , -.Fn RB_GENERATE_INSERT_COLOR , -.Fn RB_GENERATE_REMOVE , -.Fn RB_GENERATE_REMOVE_COLOR , -.Fn RB_GENERATE_FIND , -.Fn RB_GENERATE_NFIND , -.Fn RB_GENERATE_NEXT , -.Fn RB_GENERATE_PREV , +.Fn (A)RB_GENERATE_INSERT , +.Fn (A)RB_GENERATE_INSERT_COLOR , +.Fn (A)RB_GENERATE_REMOVE , +.Fn (A)RB_GENERATE_REMOVE_COLOR , +.Fn (A)RB_GENERATE_FIND , +.Fn (A)RB_GENERATE_NFIND , +.Fn (A)RB_GENERATE_NEXT , +.Fn (A)RB_GENERATE_PREV , and -.Fn RB_GENERATE_MINMAX +.Fn (A)RB_GENERATE_MINMAX macros. .Pp Finally, @@ -475,37 +587,47 @@ function defines the order of the tree elements. .Pp The -.Fn RB_INIT +.Fn (A)RB_INIT macro initializes the tree referenced by -.Fa head . +.Fa head , +with the +.Fn ARB_INIT +variant also taking the array length +.Fa maxnodes . .Pp The red-black tree can also be initialized statically by using the -.Fn RB_INITIALIZER -macro like this: +.Fn (A)RB_INITIALIZER +macro like either: .Bd -ragged -offset indent .Fn RB_HEAD HEADNAME TYPE .Va head = .Fn RB_INITIALIZER &head ; .Ed +.Bd -ragged -offset indent +.Fn ARB<8|16|32>_HEAD HEADNAME TYPE +.Va head += +.Fn ARB_INITIALIZER &head maxnodes ; +.Ed .Pp The -.Fn RB_INSERT +.Fn (A)RB_INSERT macro inserts the new element .Fa elm into the tree. .Pp The -.Fn RB_REMOVE +.Fn (A)RB_REMOVE macro removes the element .Fa elm from the tree pointed by .Fa head . .Pp The -.Fn RB_FIND +.Fn (A)RB_FIND and -.Fn RB_NFIND +.Fn (A)RB_NFIND macros can be used to find a particular element in the tree. .Bd -literal -offset indent struct TYPE find, *res; @@ -514,29 +636,29 @@ .Ed .Pp The -.Fn RB_ROOT , -.Fn RB_MIN , -.Fn RB_MAX , -.Fn RB_NEXT , +.Fn (A)RB_ROOT , +.Fn (A)RB_MIN , +.Fn (A)RB_MAX , +.Fn (A)RB_NEXT , and -.Fn RB_PREV +.Fn (A)RB_PREV macros can be used to traverse the tree: .Pp .Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))" .Pp Or, for simplicity, one can use the -.Fn RB_FOREACH +.Fn (A)RB_FOREACH or -.Fn RB_FOREACH_REVERSE +.Fn (A)RB_FOREACH_REVERSE macro: .Bd -ragged -offset indent .Fn RB_FOREACH np NAME head .Ed .Pp The macros -.Fn RB_FOREACH_SAFE +.Fn (A)RB_FOREACH_SAFE and -.Fn RB_FOREACH_REVERSE_SAFE +.Fn (A)RB_FOREACH_REVERSE_SAFE traverse the tree referenced by head in a forward or reverse direction respectively, assigning each element in turn to np. @@ -546,9 +668,9 @@ without interfering with the traversal. .Pp Both -.Fn RB_FOREACH_FROM +.Fn (A)RB_FOREACH_FROM and -.Fn RB_FOREACH_REVERSE_FROM +.Fn (A)RB_FOREACH_REVERSE_FROM may be used to continue an interrupted traversal in a forward or reverse direction respectively. The head pointer is not required. @@ -557,8 +679,24 @@ and will be overwritten to provide safe traversal. .Pp The -.Fn RB_EMPTY +.Fn (A)RB_EMPTY macro should be used to check whether a red-black tree is empty. +.Pp +Given that ARB trees have an intrinsic upper bound on the number of entries, +some ARB-specific additional macros are defined. +The +.Fn ARB_FULL +macro returns a boolean indicating whether the current number of tree entries +equals the tree's maximum. +The +.Fn ARB_CURNODES +and +.Fn ARB_MAXNODES +macros return the current and maximum number of entries respectively. +The +.Fn ARB_GETFREE +macro returns a pointer to the next free entry in the array of entries, ready to +be linked into the tree. .Sh EXAMPLES The following example demonstrates how to declare a red-black tree holding integers. @@ -658,7 +796,7 @@ .Ed .Pp Both -.Fn RB_INSERT +.Fn (A)RB_INSERT and .Fn SPLAY_INSERT return @@ -667,7 +805,7 @@ return a pointer to the element with the colliding key. .Pp Accordingly, -.Fn RB_REMOVE +.Fn (A)RB_REMOVE and .Fn SPLAY_REMOVE return the pointer to the removed element otherwise they return Index: sys/sys/tree.h =================================================================== --- sys/sys/tree.h +++ sys/sys/tree.h @@ -393,7 +393,8 @@ 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_REBALANCE(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 @@ 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_REBALANCE(name, type, attr) \ + attr struct type *name##_RB_REBALANCE(struct name *, struct type *) /* Main rb operation. * Moves node close to the key of elm to top @@ -429,7 +432,8 @@ 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_REBALANCE(name, type, field, cmp, attr) #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ attr void \ @@ -758,6 +762,22 @@ return (parent); \ } +#define RB_GENERATE_REBALANCE(name, type, field, cmp, attr) \ +attr struct type * \ +name##_RB_REBALANCE(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 +789,7 @@ #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_REBALANCE(name, x, y) name##_RB_REBALANCE(x, y) #define RB_FOREACH(x, name, head) \ for ((x) = RB_MIN(name, head); \ @@ -799,5 +820,738 @@ for ((x) = RB_MAX(name, head); \ ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ (x) = (y)) + +/* Array-based red-black trees. */ + +#define ARB_NULLIDX -1 +#define ARB_NULLCOL -1 + +#define ARB_HEAD(name, type, idxbits) \ +struct name { \ + int##idxbits##_t arb_curnodes; \ + int##idxbits##_t arb_maxnodes; \ + int##idxbits##_t arb_root_idx; \ + int##idxbits##_t arb_free_idx; \ + int##idxbits##_t arb_min_idx; \ + int##idxbits##_t arb_max_idx; \ + struct type arb_nodes[]; \ +} +#define ARB8_HEAD(name, type) ARB_HEAD(name, type, 8) +#define ARB16_HEAD(name, type) ARB_HEAD(name, type, 16) +#define ARB32_HEAD(name, type) ARB_HEAD(name, type, 32) + +#define ARB_INITIALIZER(name, maxn) \ + ((struct name){ 0, maxn, ARB_NULLIDX, ARB_NULLIDX, \ + ARB_NULLIDX, ARB_NULLIDX }) + +#define ARB_INIT(x, field, head, maxn) \ + (head)->arb_curnodes = 0; \ + (head)->arb_maxnodes = (maxn); \ + (head)->arb_root_idx = (head)->arb_free_idx = \ + (head)->arb_min_idx = (head)->arb_max_idx = ARB_NULLIDX; \ + /* The ARB_RETURNFREE() puts all entries on the free list. */ \ + ARB_ARRFOREACH_REVWCOND(x, field, head, \ + ARB_RETURNFREE(head, x, field)) + +#define ARB_ENTRY(idxbits) \ +struct { \ + int##idxbits##_t arbe_parent_idx; \ + int##idxbits##_t arbe_left_idx; \ + int##idxbits##_t arbe_right_idx; \ + int8_t arbe_color; \ +} +#define ARB8_ENTRY() ARB_ENTRY(8) +#define ARB16_ENTRY() ARB_ENTRY(16) +#define ARB32_ENTRY() ARB_ENTRY(32) + +#define ARB_ENTRYINIT(elm, field) do { \ + (elm)->field.arbe_parent_idx = \ + (elm)->field.arbe_left_idx = \ + (elm)->field.arbe_right_idx = ARB_NULLIDX; \ + (elm)->field.arbe_color = ARB_NULLCOL; \ +} while (/*CONSTCOND*/ 0) + +#define ARB_ELMTYPE(head) __typeof(&(head)->arb_nodes[0]) +#define ARB_NODES(head) (head)->arb_nodes +#define ARB_MAXNODES(head) (head)->arb_maxnodes +#define ARB_CURNODES(head) (head)->arb_curnodes +#define ARB_EMPTY(head) ((head)->arb_curnodes == 0) +#define ARB_FULL(head) ((head)->arb_curnodes >= (head)->arb_maxnodes) +#define ARB_CNODE(head, idx) \ + ((((intptr_t)(idx) <= ARB_NULLIDX) || ((idx) >= ARB_MAXNODES(head))) ? \ + NULL : ((const ARB_ELMTYPE(head))(ARB_NODES(head) + (idx)))) +#define ARB_NODE(head, idx) \ + (__DECONST(ARB_ELMTYPE(head), ARB_CNODE(head, idx))) +#define ARB_ROOT(head) ARB_NODE(head, ARB_ROOTIDX(head)) +#define ARB_LEFT(head, elm, field) ARB_NODE(head, ARB_LEFTIDX(elm, field)) +#define ARB_RIGHT(head, elm, field) ARB_NODE(head, ARB_RIGHTIDX(elm, field)) +#define ARB_PARENT(head, elm, field) ARB_NODE(head, ARB_PARENTIDX(elm, field)) +#define ARB_FREEIDX(head) (head)->arb_free_idx +#define ARB_ROOTIDX(head) (head)->arb_root_idx +#define ARB_MINIDX(head) (head)->arb_min_idx +#define ARB_MAXIDX(head) (head)->arb_max_idx +#define ARB_SELFIDX(head, elm) \ + ((elm) ? ((intptr_t)((((const uint8_t *)(elm)) - \ + ((const uint8_t *)ARB_NODES(head))) / sizeof(*(elm)))) : \ + (intptr_t)ARB_NULLIDX) +#define ARB_LEFTIDX(elm, field) (elm)->field.arbe_left_idx +#define ARB_RIGHTIDX(elm, field) (elm)->field.arbe_right_idx +#define ARB_PARENTIDX(elm, field) (elm)->field.arbe_parent_idx +#define ARB_COLOR(elm, field) (elm)->field.arbe_color +#define ARB_PREVFREE(head, elm, field) \ + ARB_NODE(head, ARB_PREVFREEIDX(elm, field)) +#define ARB_PREVFREEIDX(elm, field) ARB_LEFTIDX(elm, field) +#define ARB_NEXTFREE(head, elm, field) \ + ARB_NODE(head, ARB_NEXTFREEIDX(elm, field)) +#define ARB_NEXTFREEIDX(elm, field) ARB_RIGHTIDX(elm, field) +#define ARB_ISFREE(elm, field) (ARB_COLOR(elm, field) == ARB_NULLCOL) + +#define ARB_SET(head, elm, parent, field) do { \ + ARB_PARENTIDX(elm, field) = \ + parent ? ARB_SELFIDX(head, parent) : ARB_NULLIDX; \ + ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(elm, field) = ARB_NULLIDX; \ + ARB_COLOR(elm, field) = RB_RED; \ +} while (/*CONSTCOND*/ 0) + +#define ARB_SET_BLACKRED(black, red, field) do { \ + ARB_COLOR(black, field) = RB_BLACK; \ + ARB_COLOR(red, field) = RB_RED; \ +} while (/*CONSTCOND*/ 0) + +#ifndef ARB_AUGMENT +#define ARB_AUGMENT(x) do {} while (0) +#endif + +#define ARB_ROTATE_LEFT(head, elm, tmp, field) do { \ + __typeof(ARB_RIGHTIDX(elm, field)) _tmpidx; \ + (tmp) = ARB_RIGHT(head, elm, field); \ + _tmpidx = ARB_RIGHTIDX(elm, field); \ + ARB_RIGHTIDX(elm, field) = ARB_LEFTIDX(tmp, field); \ + if (ARB_RIGHTIDX(elm, field) != ARB_NULLIDX) { \ + ARB_PARENTIDX(ARB_LEFT(head, tmp, field), field) = \ + ARB_SELFIDX(head, elm); \ + } \ + ARB_AUGMENT(elm); \ + ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \ + if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \ + if (ARB_SELFIDX(head, elm) == \ + ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \ + ARB_LEFTIDX(ARB_PARENT(head, elm, field), \ + field) = _tmpidx; \ + else \ + ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \ + field) = _tmpidx; \ + } else \ + ARB_ROOTIDX(head) = _tmpidx; \ + ARB_LEFTIDX(tmp, field) = ARB_SELFIDX(head, elm); \ + ARB_PARENTIDX(elm, field) = _tmpidx; \ + ARB_AUGMENT(tmp); \ + if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \ + ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \ +} while (/*CONSTCOND*/ 0) + +#define ARB_ROTATE_RIGHT(head, elm, tmp, field) do { \ + __typeof(ARB_LEFTIDX(elm, field)) _tmpidx; \ + (tmp) = ARB_LEFT(head, elm, field); \ + _tmpidx = ARB_LEFTIDX(elm, field); \ + ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(tmp, field); \ + if (ARB_LEFTIDX(elm, field) != ARB_NULLIDX) { \ + ARB_PARENTIDX(ARB_RIGHT(head, tmp, field), field) = \ + ARB_SELFIDX(head, elm); \ + } \ + ARB_AUGMENT(elm); \ + ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \ + if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \ + if (ARB_SELFIDX(head, elm) == \ + ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \ + ARB_LEFTIDX(ARB_PARENT(head, elm, field), \ + field) = _tmpidx; \ + else \ + ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \ + field) = _tmpidx; \ + } else \ + ARB_ROOTIDX(head) = _tmpidx; \ + ARB_RIGHTIDX(tmp, field) = ARB_SELFIDX(head, elm); \ + ARB_PARENTIDX(elm, field) = _tmpidx; \ + ARB_AUGMENT(tmp); \ + if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \ + ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \ +} while (/*CONSTCOND*/ 0) + +#define ARB_RETURNFREE(head, elm, field) \ +({ \ + ARB_COLOR(elm, field) = ARB_NULLCOL; \ + ARB_NEXTFREEIDX(elm, field) = ARB_FREEIDX(head); \ + ARB_FREEIDX(head) = ARB_SELFIDX(head, elm); \ + elm; \ +}) + +#define ARB_GETFREEAT(head, field, fidx) \ +({ \ + __typeof(ARB_NODE(head, 0)) _elm, _prevelm; \ + int _idx = fidx; \ + if (ARB_FREEIDX(head) == ARB_NULLIDX && !ARB_FULL(head)) { \ + /* Populate the free list. */ \ + ARB_ARRFOREACH_REVERSE(_elm, field, head) { \ + if (ARB_ISFREE(_elm, field)) \ + ARB_RETURNFREE(head, _elm, field); \ + } \ + } \ + _elm = _prevelm = ARB_NODE(head, ARB_FREEIDX(head)); \ + for (; _idx > 0 && _elm != NULL; _idx--, _prevelm = _elm) \ + _elm = ARB_NODE(head, ARB_NEXTFREEIDX(_elm, field)); \ + if (_elm) { \ + if (fidx == 0) \ + ARB_FREEIDX(head) = \ + ARB_NEXTFREEIDX(_elm, field); \ + else \ + ARB_NEXTFREEIDX(_prevelm, field) = \ + ARB_NEXTFREEIDX(_elm, field); \ + } \ + _elm; \ +}) +#define ARB_GETFREE(head, field) ARB_GETFREEAT(head, field, 0) + +/* Generates prototypes and inline functions */ +#define ARB_PROTOTYPE(name, type, field, cmp) \ + ARB_PROTOTYPE_INTERNAL(name, type, field, cmp,) +#define ARB_PROTOTYPE_STATIC(name, type, field, cmp) \ + ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) +#define ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ + ARB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ + ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ + ARB_PROTOTYPE_INSERT(name, type, attr); \ + ARB_PROTOTYPE_REMOVE(name, type, attr); \ + ARB_PROTOTYPE_CFIND(name, type, attr); \ + ARB_PROTOTYPE_FIND(name, type, attr); \ + ARB_PROTOTYPE_NFIND(name, type, attr); \ + ARB_PROTOTYPE_CNEXT(name, type, attr); \ + ARB_PROTOTYPE_NEXT(name, type, attr); \ + ARB_PROTOTYPE_CPREV(name, type, attr); \ + ARB_PROTOTYPE_PREV(name, type, attr); \ + ARB_PROTOTYPE_CMINMAX(name, type, attr); \ + ARB_PROTOTYPE_MINMAX(name, type, attr); \ + ARB_PROTOTYPE_REBALANCE(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) \ + attr void name##_ARB_REMOVE_COLOR(struct name *, struct type *, struct type *) +#define ARB_PROTOTYPE_REMOVE(name, type, attr) \ + attr struct type *name##_ARB_REMOVE(struct name *, struct type *) +#define ARB_PROTOTYPE_INSERT(name, type, attr) \ + attr struct type *name##_ARB_INSERT(struct name *, struct type *) +#define ARB_PROTOTYPE_CFIND(name, type, attr) \ + attr const struct type *name##_ARB_CFIND(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_FIND(name, type, attr) \ + attr struct type *name##_ARB_FIND(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_NFIND(name, type, attr) \ + attr struct type *name##_ARB_NFIND(struct name *, struct type *) +#define ARB_PROTOTYPE_CNFIND(name, type, attr) \ + attr const struct type *name##_ARB_CNFIND(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_CNEXT(name, type, attr) \ + attr const struct type *name##_ARB_CNEXT(const struct name *head,\ + const struct type *) +#define ARB_PROTOTYPE_NEXT(name, type, attr) \ + attr struct type *name##_ARB_NEXT(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_CPREV(name, type, attr) \ + attr const struct type *name##_ARB_CPREV(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_PREV(name, type, attr) \ + attr struct type *name##_ARB_PREV(const struct name *, \ + const struct type *) +#define ARB_PROTOTYPE_CMINMAX(name, type, attr) \ + 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_GENERATE(name, type, field, cmp) \ + ARB_GENERATE_INTERNAL(name, type, field, cmp,) +#define ARB_GENERATE_STATIC(name, type, field, cmp) \ + ARB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) +#define ARB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ + ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \ + ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ + ARB_GENERATE_INSERT(name, type, field, cmp, attr) \ + ARB_GENERATE_REMOVE(name, type, field, attr) \ + ARB_GENERATE_CFIND(name, type, field, cmp, attr) \ + ARB_GENERATE_FIND(name, type, field, cmp, attr) \ + ARB_GENERATE_CNEXT(name, type, field, attr) \ + ARB_GENERATE_NEXT(name, type, field, attr) \ + ARB_GENERATE_CPREV(name, type, field, attr) \ + 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) + +#define ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \ +attr void \ +name##_ARB_INSERT_COLOR(struct name *head, struct type *elm) \ +{ \ + struct type *parent, *gparent, *tmp; \ + while ((parent = ARB_PARENT(head, elm, field)) != NULL && \ + ARB_COLOR(parent, field) == RB_RED) { \ + gparent = ARB_PARENT(head, parent, field); \ + if (parent == ARB_LEFT(head, gparent, field)) { \ + tmp = ARB_RIGHT(head, gparent, field); \ + if (tmp && ARB_COLOR(tmp, field) == RB_RED) { \ + ARB_COLOR(tmp, field) = RB_BLACK; \ + ARB_SET_BLACKRED(parent, gparent, field); \ + elm = gparent; \ + continue; \ + } \ + if (ARB_RIGHT(head, parent, field) == elm) { \ + ARB_ROTATE_LEFT(head, parent, tmp, field); \ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + ARB_SET_BLACKRED(parent, gparent, field); \ + ARB_ROTATE_RIGHT(head, gparent, tmp, field); \ + } else { \ + tmp = ARB_LEFT(head, gparent, field); \ + if (tmp && ARB_COLOR(tmp, field) == RB_RED) { \ + ARB_COLOR(tmp, field) = RB_BLACK; \ + ARB_SET_BLACKRED(parent, gparent, field); \ + elm = gparent; \ + continue; \ + } \ + if (ARB_LEFT(head, parent, field) == elm) { \ + ARB_ROTATE_RIGHT(head, parent, tmp, field); \ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + ARB_SET_BLACKRED(parent, gparent, field); \ + ARB_ROTATE_LEFT(head, gparent, tmp, field); \ + } \ + } \ + ARB_COLOR(ARB_ROOT(head), field) = RB_BLACK; \ +} + +#define ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ +attr void \ +name##_ARB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ +{ \ + struct type *tmp; \ + while ((elm == NULL || ARB_COLOR(elm, field) == RB_BLACK) && \ + elm != ARB_ROOT(head)) { \ + if (ARB_LEFT(head, parent, field) == elm) { \ + tmp = ARB_RIGHT(head, parent, field); \ + if (ARB_COLOR(tmp, field) == RB_RED) { \ + ARB_SET_BLACKRED(tmp, parent, field); \ + ARB_ROTATE_LEFT(head, parent, tmp, field); \ + tmp = ARB_RIGHT(head, parent, field); \ + } \ + if ((ARB_LEFT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_LEFT(head, tmp, field), field) == RB_BLACK) && \ + (ARB_RIGHT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == RB_BLACK)) { \ + ARB_COLOR(tmp, field) = RB_RED; \ + elm = parent; \ + parent = ARB_PARENT(head, elm, field); \ + } else { \ + if (ARB_RIGHT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == RB_BLACK) { \ + struct type *oleft; \ + if ((oleft = ARB_LEFT(head, tmp, field)) \ + != NULL) \ + ARB_COLOR(oleft, field) = RB_BLACK; \ + ARB_COLOR(tmp, field) = RB_RED; \ + ARB_ROTATE_RIGHT(head, tmp, oleft, field); \ + tmp = ARB_RIGHT(head, parent, field); \ + } \ + ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \ + ARB_COLOR(parent, field) = RB_BLACK; \ + if (ARB_RIGHT(head, tmp, field)) \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) = RB_BLACK; \ + ARB_ROTATE_LEFT(head, parent, tmp, field); \ + elm = ARB_ROOT(head); \ + break; \ + } \ + } else { \ + tmp = ARB_LEFT(head, parent, field); \ + if (ARB_COLOR(tmp, field) == RB_RED) { \ + ARB_SET_BLACKRED(tmp, parent, field); \ + ARB_ROTATE_RIGHT(head, parent, tmp, field); \ + tmp = ARB_LEFT(head, parent, field); \ + } \ + if ((ARB_LEFT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_LEFT(head, tmp, field), field) == RB_BLACK) && \ + (ARB_RIGHT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == RB_BLACK)) { \ + ARB_COLOR(tmp, field) = RB_RED; \ + elm = parent; \ + parent = ARB_PARENT(head, elm, field); \ + } else { \ + if (ARB_LEFT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_LEFT(head, tmp, field), field) == RB_BLACK) { \ + struct type *oright; \ + if ((oright = ARB_RIGHT(head, tmp, field)) \ + != NULL) \ + ARB_COLOR(oright, field) = RB_BLACK; \ + ARB_COLOR(tmp, field) = RB_RED; \ + ARB_ROTATE_LEFT(head, tmp, oright, field); \ + tmp = ARB_LEFT(head, parent, field); \ + } \ + ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \ + ARB_COLOR(parent, field) = RB_BLACK; \ + if (ARB_LEFT(head, tmp, field)) \ + ARB_COLOR(ARB_LEFT(head, tmp, field), field) = RB_BLACK; \ + ARB_ROTATE_RIGHT(head, parent, tmp, field); \ + elm = ARB_ROOT(head); \ + break; \ + } \ + } \ + } \ + if (elm) \ + ARB_COLOR(elm, field) = RB_BLACK; \ +} + +#define ARB_GENERATE_REMOVE(name, type, field, attr) \ +attr struct type * \ +name##_ARB_REMOVE(struct name *head, struct type *elm) \ +{ \ + struct type *child, *parent, *old = elm; \ + int color; \ + if (ARB_LEFT(head, elm, field) == NULL) \ + child = ARB_RIGHT(head, elm, field); \ + else if (ARB_RIGHT(head, elm, field) == NULL) \ + child = ARB_LEFT(head, elm, field); \ + else { \ + struct type *left; \ + elm = ARB_RIGHT(head, elm, field); \ + while ((left = ARB_LEFT(head, elm, field)) != NULL) \ + elm = left; \ + child = ARB_RIGHT(head, elm, field); \ + parent = ARB_PARENT(head, elm, field); \ + color = ARB_COLOR(elm, field); \ + if (child) \ + ARB_PARENTIDX(child, field) = \ + ARB_SELFIDX(head, parent); \ + if (parent) { \ + if (ARB_LEFT(head, parent, field) == elm) \ + ARB_LEFTIDX(parent, field) = \ + ARB_SELFIDX(head, child); \ + else \ + ARB_RIGHTIDX(parent, field) = \ + ARB_SELFIDX(head, child); \ + ARB_AUGMENT(parent); \ + } else \ + ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \ + if (ARB_PARENT(head, elm, field) == old) \ + parent = elm; \ + (elm)->field = (old)->field; \ + if (ARB_PARENT(head, old, field)) { \ + if (ARB_LEFT(head, ARB_PARENT(head, old, field), \ + field) == old) \ + ARB_LEFTIDX(ARB_PARENT(head, old, field), \ + field) = ARB_SELFIDX(head, elm); \ + else \ + ARB_RIGHTIDX(ARB_PARENT(head, old, field),\ + field) = ARB_SELFIDX(head, elm); \ + ARB_AUGMENT(ARB_PARENT(head, old, field)); \ + } else \ + ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \ + ARB_PARENTIDX(ARB_LEFT(head, old, field), field) = \ + ARB_SELFIDX(head, elm); \ + if (ARB_RIGHT(head, old, field)) \ + ARB_PARENTIDX(ARB_RIGHT(head, old, field), \ + field) = ARB_SELFIDX(head, elm); \ + if (parent) { \ + left = parent; \ + do { \ + RB_AUGMENT(left); \ + } while ((left = ARB_PARENT(head, left, field)) \ + != NULL); \ + } \ + goto color; \ + } \ + parent = ARB_PARENT(head, elm, field); \ + color = ARB_COLOR(elm, field); \ + if (child) \ + ARB_PARENTIDX(child, field) = ARB_SELFIDX(head, parent);\ + if (parent) { \ + if (ARB_LEFT(head, parent, field) == elm) \ + ARB_LEFTIDX(parent, field) = \ + ARB_SELFIDX(head, child); \ + else \ + ARB_RIGHTIDX(parent, field) = \ + ARB_SELFIDX(head, child); \ + ARB_AUGMENT(parent); \ + } else \ + ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \ +color: \ + if (color == RB_BLACK) \ + name##_ARB_REMOVE_COLOR(head, parent, child); \ + ARB_CURNODES(head) -= 1; \ + if (ARB_MINIDX(head) == ARB_SELFIDX(head, old)) \ + ARB_MINIDX(head) = ARB_PARENTIDX(old, field); \ + if (ARB_MAXIDX(head) == ARB_SELFIDX(head, old)) \ + ARB_MAXIDX(head) = ARB_PARENTIDX(old, field); \ + ARB_RETURNFREE(head, old, field); \ + return (old); \ +} \ + +#define ARB_GENERATE_INSERT(name, type, field, cmp, attr) \ +/* Inserts a node into the RB tree */ \ +attr struct type * \ +name##_ARB_INSERT(struct name *head, struct type *elm) \ +{ \ + struct type *tmp; \ + struct type *parent = NULL; \ + int comp = 0; \ + tmp = ARB_ROOT(head); \ + while (tmp) { \ + parent = tmp; \ + comp = (cmp)(elm, parent); \ + if (comp < 0) \ + tmp = ARB_LEFT(head, tmp, field); \ + else if (comp > 0) \ + tmp = ARB_RIGHT(head, tmp, field); \ + else \ + return (tmp); \ + } \ + ARB_SET(head, elm, parent, field); \ + if (parent != NULL) { \ + if (comp < 0) \ + ARB_LEFTIDX(parent, field) = \ + ARB_SELFIDX(head, elm); \ + else \ + ARB_RIGHTIDX(parent, field) = \ + ARB_SELFIDX(head, elm); \ + ARB_AUGMENT(parent); \ + } else \ + ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \ + name##_ARB_INSERT_COLOR(head, elm); \ + ARB_CURNODES(head) += 1; \ + if (ARB_MINIDX(head) == ARB_NULLIDX || \ + (ARB_PARENTIDX(elm, field) == ARB_MINIDX(head) && \ + ARB_LEFTIDX(parent, field) == ARB_SELFIDX(head, elm))) \ + ARB_MINIDX(head) = ARB_SELFIDX(head, elm); \ + if (ARB_MAXIDX(head) == ARB_NULLIDX || \ + (ARB_PARENTIDX(elm, field) == ARB_MAXIDX(head) && \ + ARB_RIGHTIDX(parent, field) == ARB_SELFIDX(head, elm))) \ + ARB_MAXIDX(head) = ARB_SELFIDX(head, elm); \ + return (NULL); \ +} + +#define ARB_GENERATE_CFIND(name, type, field, cmp, attr) \ +/* Finds the node with the same key as elm */ \ +attr const struct type * \ +name##_ARB_CFIND(const struct name *head, const struct type *elm) \ +{ \ + const struct type *tmp = ARB_ROOT(head); \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) \ + tmp = ARB_LEFT(head, tmp, field); \ + else if (comp > 0) \ + tmp = ARB_RIGHT(head, tmp, field); \ + else \ + return (tmp); \ + } \ + return (NULL); \ +} + +#define ARB_GENERATE_FIND(name, type, field, cmp, attr) \ +attr struct type * \ +name##_ARB_FIND(const struct name *head, const struct type *elm) \ +{ return (__DECONST(struct type *, name##_ARB_CFIND(head, elm))); } + +#define ARB_GENERATE_CNFIND(name, type, field, cmp, attr) \ +/* Finds the first node greater than or equal to the search key */ \ +attr const struct type * \ +name##_ARB_CNFIND(const struct name *head, const struct type *elm) \ +{ \ + const struct type *tmp = ARB_ROOT(head); \ + const struct type *res = NULL; \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) { \ + res = tmp; \ + tmp = ARB_LEFT(head, tmp, field); \ + } \ + else if (comp > 0) \ + tmp = ARB_RIGHT(head, tmp, field); \ + else \ + return (tmp); \ + } \ + return (res); \ +} + +#define ARB_GENERATE_NFIND(name, type, field, cmp, attr) \ +attr struct type * \ +name##_ARB_NFIND(const struct name *head, const struct type *elm) \ +{ return (__DECONST(struct type *, name##_ARB_CNFIND(head, elm))); } + +#define ARB_GENERATE_CNEXT(name, type, field, attr) \ +/* ARGSUSED */ \ +attr const struct type * \ +name##_ARB_CNEXT(const struct name *head, const struct type *elm) \ +{ \ + if (ARB_RIGHT(head, elm, field)) { \ + elm = ARB_RIGHT(head, elm, field); \ + while (ARB_LEFT(head, elm, field)) \ + elm = ARB_LEFT(head, elm, field); \ + } else { \ + if (ARB_PARENT(head, elm, field) && \ + (elm == ARB_LEFT(head, ARB_PARENT(head, elm, field),\ + field))) \ + elm = ARB_PARENT(head, elm, field); \ + else { \ + while (ARB_PARENT(head, elm, field) && \ + (elm == ARB_RIGHT(head, ARB_PARENT(head, \ + elm, field), field))) \ + elm = ARB_PARENT(head, elm, field); \ + elm = ARB_PARENT(head, elm, field); \ + } \ + } \ + return (elm); \ +} + +#define ARB_GENERATE_NEXT(name, type, field, attr) \ +attr struct type * \ +name##_ARB_NEXT(const struct name *head, const struct type *elm) \ +{ return (__DECONST(struct type *, name##_ARB_CNEXT(head, elm))); } + +#define ARB_GENERATE_CPREV(name, type, field, attr) \ +/* ARGSUSED */ \ +attr const struct type * \ +name##_ARB_CPREV(const struct name *head, const struct type *elm) \ +{ \ + if (ARB_LEFT(head, elm, field)) { \ + elm = ARB_LEFT(head, elm, field); \ + while (ARB_RIGHT(head, elm, field)) \ + elm = ARB_RIGHT(head, elm, field); \ + } else { \ + if (ARB_PARENT(head, elm, field) && \ + (elm == ARB_RIGHT(head, ARB_PARENT(head, elm, \ + field), field))) \ + elm = ARB_PARENT(head, elm, field); \ + else { \ + while (ARB_PARENT(head, elm, field) && \ + (elm == ARB_LEFT(head, ARB_PARENT(head, elm,\ + field), field))) \ + elm = ARB_PARENT(head, elm, field); \ + elm = ARB_PARENT(head, elm, field); \ + } \ + } \ + return (elm); \ +} + +#define ARB_GENERATE_PREV(name, type, field, attr) \ +attr struct type * \ +name##_ARB_PREV(const struct name *head, const struct type *elm) \ +{ return (__DECONST(struct type *, name##_ARB_CPREV(head, elm))); } + +#define ARB_GENERATE_CMINMAX(name, type, field, attr) \ +attr const struct type * \ +name##_ARB_CMINMAX(const struct name *head, int val) \ +{ \ + const struct type *tmp = ARB_EMPTY(head) ? NULL : ARB_ROOT(head);\ + const struct type *parent = NULL; \ + while (tmp) { \ + parent = tmp; \ + if (val < 0) \ + tmp = ARB_LEFT(head, tmp, field); \ + else \ + tmp = ARB_RIGHT(head, tmp, field); \ + } \ + return (__DECONST(struct type *, parent)); \ +} + +#define ARB_GENERATE_MINMAX(name, type, field, attr) \ +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) \ +attr struct type * \ +name##_ARB_REBALANCE(struct name *head, struct type *elm) \ +{ \ + struct type *cmpelm; \ + if (((cmpelm = ARB_PREV(name, head, elm)) != NULL && \ + (cmp)(cmpelm, elm) >= 0) || \ + ((cmpelm = ARB_NEXT(name, head, elm)) != NULL && \ + (cmp)(elm, cmpelm) >= 0)) { \ + /* XXXLAS: Remove/insert is heavy handed. */ \ + ARB_REMOVE(name, head, elm); \ + /* Remove puts elm on the free list. */ \ + elm = ARB_GETFREE(head, field); \ + return (ARB_INSERT(name, head, elm)); \ + } \ + return (NULL); \ +} \ + +#define ARB_INSERT(name, x, y) name##_ARB_INSERT(x, y) +#define ARB_REMOVE(name, x, y) name##_ARB_REMOVE(x, y) +#define ARB_CFIND(name, x, y) name##_ARB_CFIND(x, y) +#define ARB_FIND(name, x, y) name##_ARB_FIND(x, y) +#define ARB_CNFIND(name, x, y) name##_ARB_CNFIND(x, y) +#define ARB_NFIND(name, x, y) name##_ARB_NFIND(x, y) +#define ARB_CNEXT(name, x, y) name##_ARB_CNEXT(x, y) +#define ARB_NEXT(name, x, y) name##_ARB_NEXT(x, y) +#define ARB_CPREV(name, x, y) name##_ARB_CPREV(x, y) +#define ARB_PREV(name, x, y) name##_ARB_PREV(x, y) +#define ARB_CMIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \ + name##_ARB_CMINMAX(x, RB_NEGINF) : ARB_CNODE(x, ARB_MINIDX(x))) +#define ARB_MIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \ + name##_ARB_MINMAX(x, RB_NEGINF) : ARB_NODE(x, ARB_MINIDX(x))) +#define ARB_CMAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \ + name##_ARB_CMINMAX(x, RB_INF) : ARB_CNODE(x, ARB_MAXIDX(x))) +#define ARB_MAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \ + name##_ARB_MINMAX(x, RB_INF) : ARB_NODE(x, ARB_MAXIDX(x))) +#define ARB_REBALANCE(name, x, y) name##_ARB_REBALANCE(x, y) + +#define ARB_FOREACH(x, name, head) \ + for ((x) = ARB_MIN(name, head); \ + (x) != NULL; \ + (x) = name##_ARB_NEXT(head, x)) + +#define ARB_FOREACH_FROM(x, name, y) \ + for ((x) = (y); \ + ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \ + (x) = (y)) + +#define ARB_FOREACH_SAFE(x, name, head, y) \ + for ((x) = ARB_MIN(name, head); \ + ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \ + (x) = (y)) + +#define ARB_FOREACH_REVERSE(x, name, head) \ + for ((x) = ARB_MAX(name, head); \ + (x) != NULL; \ + (x) = name##_ARB_PREV(x)) + +#define ARB_FOREACH_REVERSE_FROM(x, name, y) \ + for ((x) = (y); \ + ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \ + (x) = (y)) + +#define ARB_FOREACH_REVERSE_SAFE(x, name, head, y) \ + for ((x) = ARB_MAX(name, head); \ + ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \ + (x) = (y)) + +#define ARB_ARRFOREACH(x, field, head) \ + for ((x) = ARB_NODES(head); \ + ARB_SELFIDX(head, x) < ARB_MAXNODES(head); \ + (x)++) + +#define ARB_ARRFOREACH_REVWCOND(x, field, head, extracond) \ + for ((x) = ARB_NODES(head) + (ARB_MAXNODES(head) - 1); \ + (x) >= ARB_NODES(head) && (extracond); \ + (x)--) + +#define ARB_ARRFOREACH_REVERSE(x, field, head) \ + ARB_ARRFOREACH_REVWCOND(x, field, head, 1) #endif /* _SYS_TREE_H_ */ Index: tests/sys/sys/Makefile =================================================================== --- tests/sys/sys/Makefile +++ tests/sys/sys/Makefile @@ -2,7 +2,7 @@ TESTSDIR= ${TESTSBASE}/sys/sys -ATF_TESTS_C= bitstring_test rb_test splay_test +ATF_TESTS_C= arb_test bitstring_test rb_test splay_test WARNS?= 5 Index: tests/sys/sys/arb_test.c =================================================================== --- tests/sys/sys/arb_test.c +++ tests/sys/sys/arb_test.c @@ -1,5 +1,6 @@ /* $OpenBSD: rb-test.c,v 1.4 2008/04/13 00:22:17 djm Exp $ */ /* + * Copyright 2019 Edward Tomasz Napierala * Copyright 2002 Niels Provos * All rights reserved. * @@ -25,55 +26,58 @@ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * - * $FreeBSD: head/tests/sys/sys/rb_test.c 347426 2019-05-10 08:16:29Z trasz $ + * $FreeBSD: head/tests/sys/sys/arb_test.c 347426 2019-05-10 08:16:29Z trasz $ */ #include #include +#include #include #include struct node { - RB_ENTRY(node) node; + ARB32_ENTRY() next; int key; }; -RB_HEAD(tree, node) root; +ARB32_HEAD(tree, node) *root; static int -compare(struct node *a, struct node *b) +compare(const struct node *a, const struct node *b) { if (a->key < b->key) return (-1); else if (a->key > b->key) return (1); return (0); } -RB_PROTOTYPE(tree, node, node, compare); +ARB_PROTOTYPE(tree, node, next, compare); -RB_GENERATE(tree, node, node, compare); +ARB_GENERATE(tree, node, next, compare); #define ITER 150 #define MIN 5 #define MAX 5000 -ATF_TC_WITHOUT_HEAD(rb_test); -ATF_TC_BODY(rb_test, tc) +ATF_TC_WITHOUT_HEAD(arb_test); +ATF_TC_BODY(arb_test, tc) { struct node *tmp, *ins; int i, max, min; max = min = 42; /* pacify gcc */ - RB_INIT(&root); + root = (struct tree *)calloc(ITER, 128); + ARB_INIT(tmp, next, root, ITER); + for (i = 0; i < ITER; i++) { - tmp = malloc(sizeof(struct node)); - ATF_CHECK_MSG(tmp != NULL, "malloc failed"); + tmp = ARB_GETFREE(root, next); + ATF_REQUIRE_MSG(tmp != NULL, "ARB_GETFREE failed"); do { tmp->key = arc4random_uniform(MAX-MIN); tmp->key += MIN; - } while (RB_FIND(tree, &root, tmp) != NULL); + } while (ARB_FIND(tree, root, tmp) != NULL); if (i == 0) max = min = tmp->key; else { @@ -82,29 +86,30 @@ if (tmp->key < min) min = tmp->key; } - ATF_CHECK_EQ(NULL, RB_INSERT(tree, &root, tmp)); + ATF_REQUIRE_EQ(NULL, ARB_INSERT(tree, root, tmp)); } - ins = RB_MIN(tree, &root); + ins = ARB_MIN(tree, root); + ATF_REQUIRE_MSG(ins != NULL, "ARB_MIN error"); ATF_CHECK_EQ(min, ins->key); tmp = ins; - ins = RB_MAX(tree, &root); + ins = ARB_MAX(tree, root); + ATF_REQUIRE_MSG(ins != NULL, "ARB_MAX error"); ATF_CHECK_EQ(max, ins->key); - ATF_CHECK_EQ(tmp, RB_REMOVE(tree, &root, tmp)); + ATF_CHECK_EQ(tmp, ARB_REMOVE(tree, root, tmp)); for (i = 0; i < ITER - 1; i++) { - tmp = RB_ROOT(&root); - ATF_CHECK_MSG(tmp != NULL, "RB_ROOT error"); - ATF_CHECK_EQ(tmp, RB_REMOVE(tree, &root, tmp)); - free(tmp); + tmp = ARB_ROOT(root); + ATF_REQUIRE_MSG(tmp != NULL, "ARB_ROOT error"); + ATF_CHECK_EQ(tmp, ARB_REMOVE(tree, root, tmp)); } } ATF_TP_ADD_TCS(tp) { - ATF_TP_ADD_TC(tp, rb_test); + ATF_TP_ADD_TC(tp, arb_test); return (atf_no_error()); }