Index: head/share/man/man3/Makefile =================================================================== --- head/share/man/man3/Makefile +++ head/share/man/man3/Makefile @@ -3,7 +3,8 @@ .include -MAN= assert.3 \ +MAN= arb.3 \ + assert.3 \ ATOMIC_VAR_INIT.3 \ bitstring.3 \ CMSG_DATA.3 \ @@ -32,6 +33,42 @@ timeradd.3 \ tree.3 +MLINKS+= arb.3 ARB8_ENTRY.3 \ + arb.3 ARB16_ENTRY.3 \ + arb.3 ARB32_ENTRY.3 \ + arb.3 ARB8_HEAD.3 \ + arb.3 ARB16_HEAD.3 \ + arb.3 ARB32_HEAD.3 \ + arb.3 ARB_ALLOCSIZE.3 \ + arb.3 ARB_INITIALIZER.3 \ + arb.3 ARB_ROOT.3 \ + arb.3 ARB_EMPTY.3 \ + arb.3 ARB_FULL.3 \ + arb.3 ARB_CURNODES.3 \ + arb.3 ARB_MAXNODES.3 \ + arb.3 ARB_NEXT.3 \ + arb.3 ARB_PREV.3 \ + arb.3 ARB_MIN.3 \ + arb.3 ARB_MAX.3 \ + arb.3 ARB_FIND.3 \ + arb.3 ARB_NFIND.3 \ + arb.3 ARB_LEFT.3 \ + arb.3 ARB_LEFTIDX.3 \ + arb.3 ARB_RIGHT.3 \ + arb.3 ARB_RIGHTIDX.3 \ + arb.3 ARB_PARENT.3 \ + arb.3 ARB_PARENTIDX.3 \ + arb.3 ARB_GETFREE.3 \ + arb.3 ARB_FREEIDX.3 \ + arb.3 ARB_FOREACH.3 \ + arb.3 ARB_FOREACH_FROM.3 \ + arb.3 ARB_FOREACH_SAFE.3 \ + arb.3 ARB_FOREACH_REVERSE.3 \ + arb.3 ARB_FOREACH_REVERSE_FROM.3 \ + arb.3 ARB_FOREACH_REVERSE_SAFE.3 \ + arb.3 ARB_INIT.3 \ + arb.3 ARB_INSERT.3 \ + arb.3 ARB_REMOVE.3 MLINKS= ATOMIC_VAR_INIT.3 atomic_compare_exchange_strong.3 \ ATOMIC_VAR_INIT.3 atomic_compare_exchange_strong_explicit.3 \ ATOMIC_VAR_INIT.3 atomic_compare_exchange_weak.3 \ Index: head/share/man/man3/arb.3 =================================================================== --- head/share/man/man3/arb.3 +++ head/share/man/man3/arb.3 @@ -0,0 +1,483 @@ +.\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $ +.\" +.\" Copyright 2002 Niels Provos +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by Niels Provos. +.\" 4. The name of the author may not be used to endorse or promote products +.\" derived from this software without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +.\" IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +.\" INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +.\" (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$ +.\" +.Dd May 8, 2019 +.Dt ARB 3 +.Os +.Sh NAME +.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_ALLOCSIZE , +.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 "array-based red-black trees" +.Sh SYNOPSIS +.In sys/arb.h +.Fn ARB_PROTOTYPE NAME TYPE FIELD CMP +.Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP +.Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR +.Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR +.Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR +.Fn ARB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR +.Fn ARB_PROTOTYPE_FIND NAME TYPE ATTR +.Fn ARB_PROTOTYPE_NFIND NAME TYPE ATTR +.Fn ARB_PROTOTYPE_NEXT NAME TYPE ATTR +.Fn ARB_PROTOTYPE_PREV NAME TYPE ATTR +.Fn ARB_PROTOTYPE_MINMAX 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 +.Fn ARB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR +.Fn ARB_GENERATE_REMOVE NAME TYPE FIELD ATTR +.Fn ARB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR +.Fn ARB_GENERATE_FIND NAME TYPE FIELD CMP ATTR +.Fn ARB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR +.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<8|16|32>_ENTRY +.Fn ARB<8|16|32>_HEAD HEADNAME TYPE +.Ft "size_t" +.Fn ARB_ALLOCSIZE "ARB_HEAD *head" "int<8|16|32>_t maxnodes" "struct TYPE *elm" +.Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes" +.Ft "struct TYPE *" +.Fn ARB_ROOT "ARB_HEAD *head" +.Ft "bool" +.Fn ARB_EMPTY "ARB_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 ARB_NEXT NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_PREV NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_MIN NAME "ARB_HEAD *head" +.Ft "struct TYPE *" +.Fn ARB_MAX NAME "ARB_HEAD *head" +.Ft "struct TYPE *" +.Fn ARB_FIND NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_NFIND NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_LEFT "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "int<8|16|32>_t" +.Fn ARB_LEFTIDX "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn ARB_RIGHT "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "int<8|16|32>_t" +.Fn ARB_RIGHTIDX "struct TYPE *elm" "ARB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn ARB_PARENT "struct TYPE *elm" "ARB_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" "FIELD" +.Ft "int<8|16|32>_t" +.Fn ARB_FREEIDX "ARB_HEAD *head" +.Fn ARB_FOREACH VARNAME NAME "ARB_HEAD *head" +.Fn ARB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME" +.Fn ARB_FOREACH_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME" +.Fn ARB_FOREACH_REVERSE VARNAME NAME "ARB_HEAD *head" +.Fn ARB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME" +.Fn ARB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME" +.Ft void +.Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes" +.Ft "struct TYPE *" +.Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn ARB_REMOVE 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 +e.g., when the tree needs to be transferred between userspace and kernel. +.Pp +In the macro definitions, +.Fa TYPE +is the name tag of a user defined structure that must contain a field of type +.Vt ARB_ENTRY , +named +.Fa ENTRYNAME . +The argument +.Fa HEADNAME +is the name tag of a user defined structure that must be declared +using the +.Fn ARB_HEAD +macro. +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 ARB_PROTOTYPE , +or +.Fn ARB_PROTOTYPE_STATIC . +The function bodies are generated with +.Fn ARB_GENERATE , +or +.Fn ARB_GENERATE_STATIC . +See the examples below for further explanation of how these macros are used. +.Pp +A red-black tree is a binary search tree with the node color as an +extra attribute. +It fulfills a set of conditions: +.Bl -enum -offset indent +.It +Every search path from the root to a leaf consists of the same number of +black nodes. +.It +Each red node (except for the root) has a black parent. +.It +Each leaf node is black. +.El +.Pp +Every operation on a red-black tree is bounded as +.Fn O "lg n" . +The maximum height of a red-black tree is +.Fn 2lg "n + 1" . +.Pp +.Fn ARB_* +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. +Use +.Fn ARB_ALLOCSIZE +to compute the size of memory chunk to allocate. +.Pp +A red-black tree is headed by a structure defined by the +.Fn ARB_HEAD +macro. +A +structure is declared with either of the following: +.Bd -ragged -offset indent +.Fn ARB<8|16|32>_HEAD HEADNAME TYPE +.Va head ; +.Ed +.Pp +where +.Fa HEADNAME +is the name of the structure to be defined, and struct +.Fa TYPE +is the type of the elements to be inserted into the tree. +.Pp +The +.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 ARB_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 ARB_PROTOTYPE +or +.Fn ARB_PROTOTYPE_STATIC +macro, +where +.Fa NAME +is a unique identifier for this particular tree. +The +.Fa TYPE +argument is the type of the structure that is being managed +by the tree. +The +.Fa FIELD +argument is the name of the element defined by +.Fn ARB_ENTRY . +Individual prototypes can be declared with +.Fn ARB_PROTOTYPE_INSERT , +.Fn ARB_PROTOTYPE_INSERT_COLOR , +.Fn ARB_PROTOTYPE_REMOVE , +.Fn ARB_PROTOTYPE_REMOVE_COLOR , +.Fn ARB_PROTOTYPE_FIND , +.Fn ARB_PROTOTYPE_NFIND , +.Fn ARB_PROTOTYPE_NEXT , +.Fn ARB_PROTOTYPE_PREV , +and +.Fn ARB_PROTOTYPE_MINMAX +in case not all functions are required. +The individual prototype macros expect +.Fa NAME , +.Fa TYPE , +and +.Fa ATTR +arguments. +The +.Fa ATTR +argument must be empty for global functions or +.Fa static +for static functions. +.Pp +The function bodies are generated with the +.Fn ARB_GENERATE +or +.Fn ARB_GENERATE_STATIC +macro. +These macros take the same arguments as the +.Fn ARB_PROTOTYPE +and +.Fn ARB_PROTOTYPE_STATIC +macros, but should be used only once. +As an alternative individual function bodies are generated with the +.Fn ARB_GENERATE_INSERT , +.Fn ARB_GENERATE_INSERT_COLOR , +.Fn ARB_GENERATE_REMOVE , +.Fn ARB_GENERATE_REMOVE_COLOR , +.Fn ARB_GENERATE_FIND , +.Fn ARB_GENERATE_NFIND , +.Fn ARB_GENERATE_NEXT , +.Fn ARB_GENERATE_PREV , +and +.Fn ARB_GENERATE_MINMAX +macros. +.Pp +Finally, +the +.Fa CMP +argument is the name of a function used to compare tree nodes +with each other. +The function takes two arguments of type +.Vt "struct TYPE *" . +If the first argument is smaller than the second, the function returns a +value smaller than zero. +If they are equal, the function returns zero. +Otherwise, it should return a value greater than zero. +The compare +function defines the order of the tree elements. +.Pp +The +.Fn ARB_INIT +macro initializes the tree referenced by +.Fa head , +with the array length of +.Fa maxnodes . +.Pp +The red-black tree can also be initialized statically by using the +.Fn ARB_INITIALIZER +macro: +.Bd -ragged -offset indent +.Fn ARB<8|16|32>_HEAD HEADNAME TYPE +.Va head += +.Fn ARB_INITIALIZER &head maxnodes ; +.Ed +.Pp +The +.Fn ARB_INSERT +macro inserts the new element +.Fa elm +into the tree. +.Pp +The +.Fn ARB_REMOVE +macro removes the element +.Fa elm +from the tree pointed by +.Fa head . +.Pp +The +.Fn ARB_FIND +and +.Fn ARB_NFIND +macros can be used to find a particular element in the tree. +.Bd -literal -offset indent +struct TYPE find, *res; +find.key = 30; +res = RB_FIND(NAME, head, &find); +.Ed +.Pp +The +.Fn ARB_ROOT , +.Fn ARB_MIN , +.Fn ARB_MAX , +.Fn ARB_NEXT , +and +.Fn ARB_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 ARB_FOREACH +or +.Fn ARB_FOREACH_REVERSE +macro: +.Bd -ragged -offset indent +.Fn RB_FOREACH np NAME head +.Ed +.Pp +The macros +.Fn ARB_FOREACH_SAFE +and +.Fn ARB_FOREACH_REVERSE_SAFE +traverse the tree referenced by head +in a forward or reverse direction respectively, +assigning each element in turn to np. +However, unlike their unsafe counterparts, +they permit both the removal of np +as well as freeing it from within the loop safely +without interfering with the traversal. +.Pp +Both +.Fn ARB_FOREACH_FROM +and +.Fn ARB_FOREACH_REVERSE_FROM +may be used to continue an interrupted traversal +in a forward or reverse direction respectively. +The head pointer is not required. +The pointer to the node from where to resume the traversal +should be passed as their last argument, +and will be overwritten to provide safe traversal. +.Pp +The +.Fn ARB_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. +The +.Fn ARB_INSERT +returns +.Dv NULL +if the element was inserted in the tree successfully, otherwise they +return a pointer to the element with the colliding key. +.Pp +Accordingly, +.Fn ARB_REMOVE +returns the pointer to the removed element otherwise they return +.Dv NULL +to indicate an error. +.Sh SEE ALSO +.Xr queue 3 , +.Xr tree 3 +.Sh HISTORY +The +.Nm ARB +macros first appeared in +.Fx 13.0 . +.Sh AUTHORS +The +.Nm ARB +macros were implemented by +.An Lawrence Stewart Aq Mt lstewart@FreeBSD.org , +based on +.Xr tree 3 +macros written by +.An Niels Provos . Index: head/share/man/man3/queue.3 =================================================================== --- head/share/man/man3/queue.3 +++ head/share/man/man3/queue.3 @@ -1329,6 +1329,7 @@ mode. .El .Sh SEE ALSO +.Xr arb 3 , .Xr tree 3 .Sh HISTORY The Index: head/share/man/man3/tree.3 =================================================================== --- head/share/man/man3/tree.3 +++ head/share/man/man3/tree.3 @@ -674,6 +674,7 @@ .Dv NULL to indicate an error. .Sh SEE ALSO +.Xr arb 3 , .Xr queue 3 .Sh AUTHORS The author of the tree macros is Index: head/sys/sys/arb.h =================================================================== --- head/sys/sys/arb.h +++ head/sys/sys/arb.h @@ -0,0 +1,779 @@ +/* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ +/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ +/* $FreeBSD$ */ + +/*- + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD + * + * Copyright 2002 Niels Provos + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _SYS_ARB_H_ +#define _SYS_ARB_H_ + +#include + +/* Array-based red-black trees. */ + +#define ARB_NULLIDX -1 +#define ARB_NULLCOL -1 + +#define ARB_BLACK 0 +#define ARB_RED 1 + +#define ARB_NEGINF -1 +#define ARB_INF 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_ALLOCSIZE(head, maxn, x) \ + (sizeof(*head) + (maxn) * sizeof(*x)) + +#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) = ARB_RED; \ +} while (/*CONSTCOND*/ 0) + +#define ARB_SET_BLACKRED(black, red, field) do { \ + ARB_COLOR(black, field) = ARB_BLACK; \ + ARB_COLOR(red, field) = ARB_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) == ARB_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) == ARB_RED) { \ + ARB_COLOR(tmp, field) = ARB_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) == ARB_RED) { \ + ARB_COLOR(tmp, field) = ARB_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) = ARB_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) == ARB_BLACK) && \ + elm != ARB_ROOT(head)) { \ + if (ARB_LEFT(head, parent, field) == elm) { \ + tmp = ARB_RIGHT(head, parent, field); \ + if (ARB_COLOR(tmp, field) == ARB_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) == ARB_BLACK) && \ + (ARB_RIGHT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \ + ARB_COLOR(tmp, field) = ARB_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) == ARB_BLACK) { \ + struct type *oleft; \ + if ((oleft = ARB_LEFT(head, tmp, field)) \ + != NULL) \ + ARB_COLOR(oleft, field) = ARB_BLACK; \ + ARB_COLOR(tmp, field) = ARB_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) = ARB_BLACK; \ + if (ARB_RIGHT(head, tmp, field)) \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) = ARB_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) == ARB_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) == ARB_BLACK) && \ + (ARB_RIGHT(head, tmp, field) == NULL || \ + ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \ + ARB_COLOR(tmp, field) = ARB_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) == ARB_BLACK) { \ + struct type *oright; \ + if ((oright = ARB_RIGHT(head, tmp, field)) \ + != NULL) \ + ARB_COLOR(oright, field) = ARB_BLACK; \ + ARB_COLOR(tmp, field) = ARB_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) = ARB_BLACK; \ + if (ARB_LEFT(head, tmp, field)) \ + ARB_COLOR(ARB_LEFT(head, tmp, field), field) = ARB_BLACK; \ + ARB_ROTATE_RIGHT(head, parent, tmp, field); \ + elm = ARB_ROOT(head); \ + break; \ + } \ + } \ + } \ + if (elm) \ + ARB_COLOR(elm, field) = ARB_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 { \ + ARB_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 == ARB_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, ARB_NEGINF) : ARB_CNODE(x, ARB_MINIDX(x))) +#define ARB_MIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \ + name##_ARB_MINMAX(x, ARB_NEGINF) : ARB_NODE(x, ARB_MINIDX(x))) +#define ARB_CMAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \ + 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_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_ARB_H_ */ Index: head/tests/sys/sys/Makefile =================================================================== --- head/tests/sys/sys/Makefile +++ head/tests/sys/sys/Makefile @@ -2,7 +2,7 @@ TESTSDIR= ${TESTSBASE}/sys/sys -ATF_TESTS_C= bitstring_test qmath_test rb_test splay_test +ATF_TESTS_C= arb_test bitstring_test qmath_test rb_test splay_test WARNS?= 5 Index: head/tests/sys/sys/arb_test.c =================================================================== --- head/tests/sys/sys/arb_test.c +++ head/tests/sys/sys/arb_test.c @@ -0,0 +1,115 @@ +/* $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. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (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$ + */ +#include + +#include +#include +#include + +#include + +struct node { + ARB32_ENTRY() next; + int key; +}; + +ARB32_HEAD(tree, node) *root; + +static int +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); +} + +ARB_PROTOTYPE(tree, node, next, compare); + +ARB_GENERATE(tree, node, next, compare); + +#define ITER 150 +#define MIN 5 +#define MAX 5000 + +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 */ + + root = (struct tree *)calloc(1, ARB_ALLOCSIZE(root, ITER, tmp)); + + ARB_INIT(tmp, next, root, ITER); + + for (i = 0; i < ITER; i++) { + tmp = ARB_GETFREE(root, next); + ATF_REQUIRE_MSG(tmp != NULL, "ARB_GETFREE failed"); + do { + tmp->key = arc4random_uniform(MAX-MIN); + tmp->key += MIN; + } while (ARB_FIND(tree, root, tmp) != NULL); + if (i == 0) + max = min = tmp->key; + else { + if (tmp->key > max) + max = tmp->key; + if (tmp->key < min) + min = tmp->key; + } + ATF_REQUIRE_EQ(NULL, ARB_INSERT(tree, root, tmp)); + } + + ins = ARB_MIN(tree, root); + ATF_REQUIRE_MSG(ins != NULL, "ARB_MIN error"); + ATF_CHECK_EQ(min, ins->key); + tmp = ins; + ins = ARB_MAX(tree, root); + ATF_REQUIRE_MSG(ins != NULL, "ARB_MAX error"); + ATF_CHECK_EQ(max, ins->key); + + ATF_CHECK_EQ(tmp, ARB_REMOVE(tree, root, tmp)); + + for (i = 0; i < ITER - 1; i++) { + 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, arb_test); + + return (atf_no_error()); +}