Page MenuHomeFreeBSD
Differential D20477 Diff 63000 head/share/man/man3/arb.3

Changeset View

Standalone View

View Options

head/share/man/man3/arb.3

Show All 24 Lines
.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, .\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY .\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT .\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
.\" .\"
.\" $FreeBSD$ .\" $FreeBSD$
.\" .\"
.Dd September 28, 2019 .Dd October 2, 2019
.Dt ARB 3 .Dt ARB 3
.Os .Os
.Sh NAME .Sh NAME
.Nm ARB_PROTOTYPE , .Nm ARB_PROTOTYPE ,
.Nm ARB_PROTOTYPE_STATIC , .Nm ARB_PROTOTYPE_STATIC ,
.Nm ARB_PROTOTYPE_INSERT , .Nm ARB_PROTOTYPE_INSERT ,
.Nm ARB_PROTOTYPE_INSERT_COLOR , .Nm ARB_PROTOTYPE_INSERT_COLOR ,
.Nm ARB_PROTOTYPE_REMOVE , .Nm ARB_PROTOTYPE_REMOVE ,
▲ Show 20 Lines • Show All 47 Lines • ▼ Show 20 Lines
.Nm ARB_FOREACH_FROM , .Nm ARB_FOREACH_FROM ,
.Nm ARB_FOREACH_SAFE , .Nm ARB_FOREACH_SAFE ,
.Nm ARB_FOREACH_REVERSE , .Nm ARB_FOREACH_REVERSE ,
.Nm ARB_FOREACH_REVERSE_FROM , .Nm ARB_FOREACH_REVERSE_FROM ,
.Nm ARB_FOREACH_REVERSE_SAFE , .Nm ARB_FOREACH_REVERSE_SAFE ,
.Nm ARB_INIT , .Nm ARB_INIT ,
.Nm ARB_INSERT , .Nm ARB_INSERT ,
.Nm ARB_REMOVE , .Nm ARB_REMOVE ,
.Nm ARB_REINSERT .Nm ARB_REINSERT ,
.Nm ARB_RESET_TREE
.Nd "array-based red-black trees" .Nd "array-based red-black trees"
.Sh SYNOPSIS .Sh SYNOPSIS
.In sys/arb.h .In sys/arb.h
.Fn ARB_PROTOTYPE NAME TYPE FIELD CMP .Fn ARB_PROTOTYPE NAME TYPE FIELD CMP
.Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP .Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
.Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR .Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR
.Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR .Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
.Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR .Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR
▲ Show 20 Lines • Show All 68 Lines • ▼ Show 20 Lines
.Ft void .Ft void
.Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes" .Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
.Ft "struct TYPE *" .Ft "struct TYPE *"
.Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm" .Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *" .Ft "struct TYPE *"
.Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm" .Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *" .Ft "struct TYPE *"
.Fn ARB_REINSERT NAME "ARB_HEAD *head" "struct TYPE *elm" .Fn ARB_REINSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
.Ft void
.Fn ARB_RESET_TREE "ARB_HEAD *head" NAME "int<8|16|32>_t maxnodes"
.Sh DESCRIPTION .Sh DESCRIPTION
These macros define data structures for and array-based red-black trees. These macros define data structures for and array-based red-black trees.
They use a single, continuous chunk of memory, and are useful They use a single, continuous chunk of memory, and are useful
e.g., when the tree needs to be transferred between userspace and kernel. e.g., when the tree needs to be transferred between userspace and kernel.
.Pp .Pp
In the macro definitions, In the macro definitions,
.Fa TYPE .Fa TYPE
is the name tag of a user defined structure that must contain a field of type is the name tag of a user defined structure that must contain a field of type
▲ Show 20 Lines • Show All 280 Lines • ▼ Show 20 Lines
.Pp .Pp
Accordingly, Accordingly,
.Fn ARB_REMOVE .Fn ARB_REMOVE
returns the pointer to the removed element otherwise they return returns the pointer to the removed element otherwise they return
.Dv NULL .Dv NULL
to indicate an error. to indicate an error.
.Pp .Pp
The The
.Fn RB_REINSERT .Fn ARB_REINSERT
macro updates the position of the element macro updates the position of the element
.Fa elm .Fa elm
in the tree. in the tree.
This must be called if a member of a This must be called if a member of a
.Nm tree .Nm tree
is modified in a way that affects comparison, such as by modifying is modified in a way that affects comparison, such as by modifying
a node's key. a node's key.
This is a lower overhead alternative to removing the element This is a lower overhead alternative to removing the element
and reinserting it again. and reinserting it again.
.Pp
The
.Fn ARB_RESET_TREE
macro discards the tree topology.
It does not modify embedded object values or the free list.
.Sh SEE ALSO .Sh SEE ALSO
.Xr queue 3 , .Xr queue 3 ,
.Xr tree 3 .Xr tree 3
.Sh HISTORY .Sh HISTORY
The The
.Nm ARB .Nm ARB
macros first appeared in macros first appeared in
.Fx 13.0 . .Fx 13.0 .
Show All 9 Lines