Changeset View
Changeset View
Standalone View
Standalone View
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. | |||||
cem: The grammar is a little awkward. It's fine in man pages to just use very short sentences… | |||||
.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 |
The grammar is a little awkward. It's fine in man pages to just use very short sentences:
"The ... macro discards the tree topology. It does not modify embedded object values or the .Nm free list."
(If nothing else, there is a duplicate period at the end of the current sentence.)