arb.3 (419f843fffd06af29c104330063fb6c22546ea28) arb.3 (a5adff0eebb383985cd41fa117ee9381cbed7f8e)
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 May 8, 2019
33.Dd September 28, 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 ,
42.Nm ARB_PROTOTYPE_REMOVE_COLOR ,
43.Nm ARB_PROTOTYPE_FIND ,
44.Nm ARB_PROTOTYPE_NFIND ,
45.Nm ARB_PROTOTYPE_NEXT ,
46.Nm ARB_PROTOTYPE_PREV ,
47.Nm ARB_PROTOTYPE_MINMAX ,
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 ,
42.Nm ARB_PROTOTYPE_REMOVE_COLOR ,
43.Nm ARB_PROTOTYPE_FIND ,
44.Nm ARB_PROTOTYPE_NFIND ,
45.Nm ARB_PROTOTYPE_NEXT ,
46.Nm ARB_PROTOTYPE_PREV ,
47.Nm ARB_PROTOTYPE_MINMAX ,
48.Nm ARB_PROTOTYPE_REINSERT ,
48.Nm ARB_GENERATE ,
49.Nm ARB_GENERATE_STATIC ,
50.Nm ARB_GENERATE_INSERT ,
51.Nm ARB_GENERATE_INSERT_COLOR ,
52.Nm ARB_GENERATE_REMOVE ,
53.Nm ARB_GENERATE_REMOVE_COLOR ,
54.Nm ARB_GENERATE_FIND ,
55.Nm ARB_GENERATE_NFIND ,
56.Nm ARB_GENERATE_NEXT ,
57.Nm ARB_GENERATE_PREV ,
58.Nm ARB_GENERATE_MINMAX ,
49.Nm ARB_GENERATE ,
50.Nm ARB_GENERATE_STATIC ,
51.Nm ARB_GENERATE_INSERT ,
52.Nm ARB_GENERATE_INSERT_COLOR ,
53.Nm ARB_GENERATE_REMOVE ,
54.Nm ARB_GENERATE_REMOVE_COLOR ,
55.Nm ARB_GENERATE_FIND ,
56.Nm ARB_GENERATE_NFIND ,
57.Nm ARB_GENERATE_NEXT ,
58.Nm ARB_GENERATE_PREV ,
59.Nm ARB_GENERATE_MINMAX ,
60.Nm ARB_GENERATE_REINSERT ,
59.Nm ARB8_ENTRY ,
60.Nm ARB16_ENTRY ,
61.Nm ARB32_ENTRY ,
62.Nm ARB8_HEAD ,
63.Nm ARB16_HEAD ,
64.Nm ARB32_HEAD ,
65.Nm ARB_ALLOCSIZE ,
66.Nm ARB_INITIALIZER ,

--- 19 unchanged lines hidden (view full) ---

86.Nm ARB_FOREACH ,
87.Nm ARB_FOREACH_FROM ,
88.Nm ARB_FOREACH_SAFE ,
89.Nm ARB_FOREACH_REVERSE ,
90.Nm ARB_FOREACH_REVERSE_FROM ,
91.Nm ARB_FOREACH_REVERSE_SAFE ,
92.Nm ARB_INIT ,
93.Nm ARB_INSERT ,
61.Nm ARB8_ENTRY ,
62.Nm ARB16_ENTRY ,
63.Nm ARB32_ENTRY ,
64.Nm ARB8_HEAD ,
65.Nm ARB16_HEAD ,
66.Nm ARB32_HEAD ,
67.Nm ARB_ALLOCSIZE ,
68.Nm ARB_INITIALIZER ,

--- 19 unchanged lines hidden (view full) ---

88.Nm ARB_FOREACH ,
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 ,
94.Nm ARB_REMOVE
96.Nm ARB_REMOVE ,
97.Nm ARB_REINSERT
95.Nd "array-based red-black trees"
96.Sh SYNOPSIS
97.In sys/arb.h
98.Fn ARB_PROTOTYPE NAME TYPE FIELD CMP
99.Fn ARB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
100.Fn ARB_PROTOTYPE_INSERT NAME TYPE ATTR
101.Fn ARB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
102.Fn ARB_PROTOTYPE_REMOVE NAME TYPE ATTR
103.Fn ARB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
104.Fn ARB_PROTOTYPE_FIND NAME TYPE ATTR
105.Fn ARB_PROTOTYPE_NFIND NAME TYPE ATTR
106.Fn ARB_PROTOTYPE_NEXT NAME TYPE ATTR
107.Fn ARB_PROTOTYPE_PREV NAME TYPE ATTR
108.Fn ARB_PROTOTYPE_MINMAX NAME TYPE ATTR
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
106.Fn ARB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
107.Fn ARB_PROTOTYPE_FIND NAME TYPE ATTR
108.Fn ARB_PROTOTYPE_NFIND NAME TYPE ATTR
109.Fn ARB_PROTOTYPE_NEXT NAME TYPE ATTR
110.Fn ARB_PROTOTYPE_PREV NAME TYPE ATTR
111.Fn ARB_PROTOTYPE_MINMAX NAME TYPE ATTR
112.Fn ARB_PROTOTYPE_REINSERT NAME TYPE ATTR
109.Fn ARB_GENERATE NAME TYPE FIELD CMP
110.Fn ARB_GENERATE_STATIC NAME TYPE FIELD CMP
111.Fn ARB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
112.Fn ARB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
113.Fn ARB_GENERATE_REMOVE NAME TYPE FIELD ATTR
114.Fn ARB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
115.Fn ARB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
116.Fn ARB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
117.Fn ARB_GENERATE_NEXT NAME TYPE FIELD ATTR
118.Fn ARB_GENERATE_PREV NAME TYPE FIELD ATTR
119.Fn ARB_GENERATE_MINMAX NAME TYPE FIELD ATTR
113.Fn ARB_GENERATE NAME TYPE FIELD CMP
114.Fn ARB_GENERATE_STATIC NAME TYPE FIELD CMP
115.Fn ARB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
116.Fn ARB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
117.Fn ARB_GENERATE_REMOVE NAME TYPE FIELD ATTR
118.Fn ARB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
119.Fn ARB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
120.Fn ARB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
121.Fn ARB_GENERATE_NEXT NAME TYPE FIELD ATTR
122.Fn ARB_GENERATE_PREV NAME TYPE FIELD ATTR
123.Fn ARB_GENERATE_MINMAX NAME TYPE FIELD ATTR
124.Fn ARB_GENERATE_REINSERT NAME TYPE FIELD CMP ATTR
120.Fn ARB<8|16|32>_ENTRY
121.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
122.Ft "size_t"
123.Fn ARB_ALLOCSIZE "ARB_HEAD *head" "int<8|16|32>_t maxnodes" "struct TYPE *elm"
124.Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
125.Ft "struct TYPE *"
126.Fn ARB_ROOT "ARB_HEAD *head"
127.Ft "bool"

--- 39 unchanged lines hidden (view full) ---

167.Fn ARB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
168.Fn ARB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
169.Ft void
170.Fn ARB_INIT "struct TYPE *elm" "FIELD" "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
171.Ft "struct TYPE *"
172.Fn ARB_INSERT NAME "ARB_HEAD *head" "struct TYPE *elm"
173.Ft "struct TYPE *"
174.Fn ARB_REMOVE NAME "ARB_HEAD *head" "struct TYPE *elm"
125.Fn ARB<8|16|32>_ENTRY
126.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
127.Ft "size_t"
128.Fn ARB_ALLOCSIZE "ARB_HEAD *head" "int<8|16|32>_t maxnodes" "struct TYPE *elm"
129.Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
130.Ft "struct TYPE *"
131.Fn ARB_ROOT "ARB_HEAD *head"
132.Ft "bool"

--- 39 unchanged lines hidden (view full) ---

172.Fn ARB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
173.Fn ARB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "ARB_HEAD *head" "TEMP_VARNAME"
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"
175.Sh DESCRIPTION
176These macros define data structures for and array-based red-black trees.
177They use a single, continuous chunk of memory, and are useful
178e.g., when the tree needs to be transferred between userspace and kernel.
179.Pp
180In the macro definitions,
181.Fa TYPE
182is the name tag of a user defined structure that must contain a field of type

--- 109 unchanged lines hidden (view full) ---

292.Fn ARB_PROTOTYPE_INSERT ,
293.Fn ARB_PROTOTYPE_INSERT_COLOR ,
294.Fn ARB_PROTOTYPE_REMOVE ,
295.Fn ARB_PROTOTYPE_REMOVE_COLOR ,
296.Fn ARB_PROTOTYPE_FIND ,
297.Fn ARB_PROTOTYPE_NFIND ,
298.Fn ARB_PROTOTYPE_NEXT ,
299.Fn ARB_PROTOTYPE_PREV ,
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

--- 109 unchanged lines hidden (view full) ---

299.Fn ARB_PROTOTYPE_INSERT ,
300.Fn ARB_PROTOTYPE_INSERT_COLOR ,
301.Fn ARB_PROTOTYPE_REMOVE ,
302.Fn ARB_PROTOTYPE_REMOVE_COLOR ,
303.Fn ARB_PROTOTYPE_FIND ,
304.Fn ARB_PROTOTYPE_NFIND ,
305.Fn ARB_PROTOTYPE_NEXT ,
306.Fn ARB_PROTOTYPE_PREV ,
307.Fn ARB_PROTOTYPE_MINMAX ,
300and
308and
301.Fn ARB_PROTOTYPE_MINMAX
309.Fn ARB_PROTOTYPE_REINSERT
302in case not all functions are required.
303The individual prototype macros expect
304.Fa NAME ,
305.Fa TYPE ,
306and
307.Fa ATTR
308arguments.
309The

--- 16 unchanged lines hidden (view full) ---

326.Fn ARB_GENERATE_INSERT ,
327.Fn ARB_GENERATE_INSERT_COLOR ,
328.Fn ARB_GENERATE_REMOVE ,
329.Fn ARB_GENERATE_REMOVE_COLOR ,
330.Fn ARB_GENERATE_FIND ,
331.Fn ARB_GENERATE_NFIND ,
332.Fn ARB_GENERATE_NEXT ,
333.Fn ARB_GENERATE_PREV ,
310in case not all functions are required.
311The individual prototype macros expect
312.Fa NAME ,
313.Fa TYPE ,
314and
315.Fa ATTR
316arguments.
317The

--- 16 unchanged lines hidden (view full) ---

334.Fn ARB_GENERATE_INSERT ,
335.Fn ARB_GENERATE_INSERT_COLOR ,
336.Fn ARB_GENERATE_REMOVE ,
337.Fn ARB_GENERATE_REMOVE_COLOR ,
338.Fn ARB_GENERATE_FIND ,
339.Fn ARB_GENERATE_NFIND ,
340.Fn ARB_GENERATE_NEXT ,
341.Fn ARB_GENERATE_PREV ,
342.Fn ARB_GENERATE_MINMAX ,
334and
343and
335.Fn ARB_GENERATE_MINMAX
344.Fn ARB_GENERATE_REINSERT
336macros.
337.Pp
338Finally,
339the
340.Fa CMP
341argument is the name of a function used to compare tree nodes
342with each other.
343The function takes two arguments of type

--- 115 unchanged lines hidden (view full) ---

459if the element was inserted in the tree successfully, otherwise they
460return a pointer to the element with the colliding key.
461.Pp
462Accordingly,
463.Fn ARB_REMOVE
464returns the pointer to the removed element otherwise they return
465.Dv NULL
466to indicate an error.
345macros.
346.Pp
347Finally,
348the
349.Fa CMP
350argument is the name of a function used to compare tree nodes
351with each other.
352The function takes two arguments of type

--- 115 unchanged lines hidden (view full) ---

468if the element was inserted in the tree successfully, otherwise they
469return a pointer to the element with the colliding key.
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
478.Fn RB_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.
467.Sh SEE ALSO
468.Xr queue 3 ,
469.Xr tree 3
470.Sh HISTORY
471The
472.Nm ARB
473macros first appeared in
474.Fx 13.0 .
475.Sh AUTHORS
476The
477.Nm ARB
478macros were implemented by
479.An Lawrence Stewart Aq Mt lstewart@FreeBSD.org ,
480based on
481.Xr tree 3
482macros written by
483.An Niels Provos .
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 .