| arb.3 (a5adff0eebb383985cd41fa117ee9381cbed7f8e) | arb.3 (1a13f2e6b444dd8048aebd2ac1f0b8fae9e3088f) |
|---|---|
| 1.\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $ 2.\" 3.\" Copyright 2002 Niels Provos <provos@citi.umich.edu> 4.\" All rights reserved. 5.\" 6.\" Redistribution and use in source and binary forms, with or without 7.\" modification, are permitted provided that the following conditions 8.\" are met: --- 16 unchanged lines hidden (view full) --- 25.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 29.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30.\" 31.\" $FreeBSD$ 32.\" | 1.\" $OpenBSD: tree.3,v 1.7 2002/06/12 01:09:20 provos Exp $ 2.\" 3.\" Copyright 2002 Niels Provos <provos@citi.umich.edu> 4.\" All rights reserved. 5.\" 6.\" Redistribution and use in source and binary forms, with or without 7.\" modification, are permitted provided that the following conditions 8.\" are met: --- 16 unchanged lines hidden (view full) --- 25.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26.\" DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27.\" THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28.\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 29.\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30.\" 31.\" $FreeBSD$ 32.\" |
| 33.Dd September 28, 2019 | 33.Dd October 2, 2019 |
| 34.Dt ARB 3 35.Os 36.Sh NAME 37.Nm ARB_PROTOTYPE , 38.Nm ARB_PROTOTYPE_STATIC , 39.Nm ARB_PROTOTYPE_INSERT , 40.Nm ARB_PROTOTYPE_INSERT_COLOR , 41.Nm ARB_PROTOTYPE_REMOVE , --- 47 unchanged lines hidden (view full) --- 89.Nm ARB_FOREACH_FROM , 90.Nm ARB_FOREACH_SAFE , 91.Nm ARB_FOREACH_REVERSE , 92.Nm ARB_FOREACH_REVERSE_FROM , 93.Nm ARB_FOREACH_REVERSE_SAFE , 94.Nm ARB_INIT , 95.Nm ARB_INSERT , 96.Nm ARB_REMOVE , | 34.Dt ARB 3 35.Os 36.Sh NAME 37.Nm ARB_PROTOTYPE , 38.Nm ARB_PROTOTYPE_STATIC , 39.Nm ARB_PROTOTYPE_INSERT , 40.Nm ARB_PROTOTYPE_INSERT_COLOR , 41.Nm ARB_PROTOTYPE_REMOVE , --- 47 unchanged lines hidden (view full) --- 89.Nm ARB_FOREACH_FROM , 90.Nm ARB_FOREACH_SAFE , 91.Nm ARB_FOREACH_REVERSE , 92.Nm ARB_FOREACH_REVERSE_FROM , 93.Nm ARB_FOREACH_REVERSE_SAFE , 94.Nm ARB_INIT , 95.Nm ARB_INSERT , 96.Nm ARB_REMOVE , |
| 97.Nm ARB_REINSERT | 97.Nm ARB_REINSERT , 98.Nm ARB_RESET_TREE |
| 98.Nd "array-based red-black trees" 99.Sh SYNOPSIS 100.In sys/arb.h 101.Fn ARB_PROTOTYPE NAME TYPE FIELD CMP 102.Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP 103.Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR 104.Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR 105.Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR --- 68 unchanged lines hidden (view full) --- 174.Ft void 175.Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes" 176.Ft "struct TYPE *" 177.Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm" 178.Ft "struct TYPE *" 179.Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm" 180.Ft "struct TYPE *" 181.Fn ARB_REINSERT NAME "ARB_HEAD *head" "struct TYPE *elm" | 99.Nd "array-based red-black trees" 100.Sh SYNOPSIS 101.In sys/arb.h 102.Fn ARB_PROTOTYPE NAME TYPE FIELD CMP 103.Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP 104.Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR 105.Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR 106.Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR --- 68 unchanged lines hidden (view full) --- 175.Ft void 176.Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes" 177.Ft "struct TYPE *" 178.Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm" 179.Ft "struct TYPE *" 180.Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm" 181.Ft "struct TYPE *" 182.Fn ARB_REINSERT NAME "ARB_HEAD *head" "struct TYPE *elm" |
| 183.Ft void 184.Fn ARB_RESET_TREE "ARB_HEAD *head" NAME "int<8|16|32>_t maxnodes" |
|
| 182.Sh DESCRIPTION 183These macros define data structures for and array-based red-black trees. 184They use a single, continuous chunk of memory, and are useful 185e.g., when the tree needs to be transferred between userspace and kernel. 186.Pp 187In the macro definitions, 188.Fa TYPE 189is the name tag of a user defined structure that must contain a field of type --- 280 unchanged lines hidden (view full) --- 470.Pp 471Accordingly, 472.Fn ARB_REMOVE 473returns the pointer to the removed element otherwise they return 474.Dv NULL 475to indicate an error. 476.Pp 477The | 185.Sh DESCRIPTION 186These macros define data structures for and array-based red-black trees. 187They use a single, continuous chunk of memory, and are useful 188e.g., when the tree needs to be transferred between userspace and kernel. 189.Pp 190In the macro definitions, 191.Fa TYPE 192is the name tag of a user defined structure that must contain a field of type --- 280 unchanged lines hidden (view full) --- 473.Pp 474Accordingly, 475.Fn ARB_REMOVE 476returns the pointer to the removed element otherwise they return 477.Dv NULL 478to indicate an error. 479.Pp 480The |
| 478.Fn RB_REINSERT | 481.Fn ARB_REINSERT |
| 479macro updates the position of the element 480.Fa elm 481in the tree. 482This must be called if a member of a 483.Nm tree 484is modified in a way that affects comparison, such as by modifying 485a node's key. 486This is a lower overhead alternative to removing the element 487and reinserting it again. | 482macro updates the position of the element 483.Fa elm 484in the tree. 485This must be called if a member of a 486.Nm tree 487is modified in a way that affects comparison, such as by modifying 488a node's key. 489This is a lower overhead alternative to removing the element 490and reinserting it again. |
| 491.Pp 492The 493.Fn ARB_RESET_TREE 494macro discards the tree topology. 495It does not modify embedded object values or the free list. |
|
| 488.Sh SEE ALSO 489.Xr queue 3 , 490.Xr tree 3 491.Sh HISTORY 492The 493.Nm ARB 494macros first appeared in 495.Fx 13.0 . 496.Sh AUTHORS 497The 498.Nm ARB 499macros were implemented by 500.An Lawrence Stewart Aq Mt lstewart@FreeBSD.org , 501based on 502.Xr tree 3 503macros written by 504.An Niels Provos . | 496.Sh SEE ALSO 497.Xr queue 3 , 498.Xr tree 3 499.Sh HISTORY 500The 501.Nm ARB 502macros first appeared in 503.Fx 13.0 . 504.Sh AUTHORS 505The 506.Nm ARB 507macros were implemented by 508.An Lawrence Stewart Aq Mt lstewart@FreeBSD.org , 509based on 510.Xr tree 3 511macros written by 512.An Niels Provos . |