diff options
| -rw-r--r-- | share/man/man3/queue.3 | 1195 | ||||
| -rw-r--r-- | share/man/man3/tree.3 | 582 |
2 files changed, 1777 insertions, 0 deletions
diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3 new file mode 100644 index 0000000..dd3fe53 --- /dev/null +++ b/share/man/man3/queue.3 @@ -0,0 +1,1195 @@ +.\" $NetBSD: queue.3,v 1.4 1995/07/03 00:25:36 mycroft Exp $ +.\" +.\" Copyright (c) 1993 The Regents of the University of California. +.\" 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. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``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 REGENTS OR CONTRIBUTORS 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. +.\" +.\" @(#)queue.3 8.1 (Berkeley) 12/13/93 +.\" +.Dd $Mdocdate: Dec 16 2024 $ +.Dt SLIST_INIT 3 +.Os +.Sh NAME +.Nm SLIST_ENTRY , +.Nm SLIST_HEAD , +.Nm SLIST_HEAD_INITIALIZER , +.Nm SLIST_FIRST , +.Nm SLIST_NEXT , +.Nm SLIST_EMPTY , +.Nm SLIST_FOREACH , +.Nm SLIST_FOREACH_SAFE , +.Nm SLIST_INIT , +.Nm SLIST_INSERT_AFTER , +.Nm SLIST_INSERT_HEAD , +.Nm SLIST_REMOVE_AFTER , +.Nm SLIST_REMOVE_HEAD , +.Nm SLIST_REMOVE , +.Nm LIST_ENTRY , +.Nm LIST_HEAD , +.Nm LIST_HEAD_INITIALIZER , +.Nm LIST_FIRST , +.Nm LIST_NEXT , +.Nm LIST_EMPTY , +.Nm LIST_FOREACH , +.Nm LIST_FOREACH_SAFE , +.Nm LIST_INIT , +.Nm LIST_INSERT_AFTER , +.Nm LIST_INSERT_BEFORE , +.Nm LIST_INSERT_HEAD , +.Nm LIST_REMOVE , +.Nm LIST_REPLACE , +.Nm SIMPLEQ_ENTRY , +.Nm SIMPLEQ_HEAD , +.Nm SIMPLEQ_HEAD_INITIALIZER , +.Nm SIMPLEQ_FIRST , +.Nm SIMPLEQ_NEXT , +.Nm SIMPLEQ_EMPTY , +.Nm SIMPLEQ_FOREACH , +.Nm SIMPLEQ_FOREACH_SAFE , +.Nm SIMPLEQ_INIT , +.Nm SIMPLEQ_INSERT_AFTER , +.Nm SIMPLEQ_INSERT_HEAD , +.Nm SIMPLEQ_INSERT_TAIL , +.Nm SIMPLEQ_REMOVE_AFTER , +.Nm SIMPLEQ_REMOVE_HEAD , +.Nm SIMPLEQ_CONCAT , +.Nm STAILQ_ENTRY , +.Nm STAILQ_HEAD , +.Nm STAILQ_HEAD_INITIALIZER , +.Nm STAILQ_FIRST , +.Nm STAILQ_NEXT , +.Nm STAILQ_LAST , +.Nm STAILQ_EMPTY , +.Nm STAILQ_FOREACH , +.Nm STAILQ_FOREACH_SAFE , +.Nm STAILQ_INIT , +.Nm STAILQ_INSERT_AFTER , +.Nm STAILQ_INSERT_HEAD , +.Nm STAILQ_INSERT_TAIL , +.Nm STAILQ_REMOVE , +.Nm STAILQ_REMOVE_AFTER , +.Nm STAILQ_REMOVE_HEAD , +.Nm STAILQ_CONCAT , +.Nm TAILQ_ENTRY , +.Nm TAILQ_HEAD , +.Nm TAILQ_HEAD_INITIALIZER , +.Nm TAILQ_FIRST , +.Nm TAILQ_NEXT , +.Nm TAILQ_LAST , +.Nm TAILQ_PREV , +.Nm TAILQ_EMPTY , +.Nm TAILQ_FOREACH , +.Nm TAILQ_FOREACH_SAFE , +.Nm TAILQ_FOREACH_REVERSE , +.Nm TAILQ_FOREACH_REVERSE_SAFE , +.Nm TAILQ_INIT , +.Nm TAILQ_INSERT_AFTER , +.Nm TAILQ_INSERT_BEFORE , +.Nm TAILQ_INSERT_HEAD , +.Nm TAILQ_INSERT_TAIL , +.Nm TAILQ_REMOVE , +.Nm TAILQ_REPLACE , +.Nm TAILQ_CONCAT +.Nd intrusive singly-linked and doubly-linked lists, simple queues, singly-linked and doubly-linked tail queues +.Sh SYNOPSIS +.In sys/queue.h +.Pp +.Fn SLIST_ENTRY "TYPE" +.Fn SLIST_HEAD "HEADNAME" "TYPE" +.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" +.Ft "struct TYPE *" +.Fn SLIST_FIRST "SLIST_HEAD *head" +.Ft "struct TYPE *" +.Fn SLIST_NEXT "struct TYPE *listelm" "FIELDNAME" +.Ft int +.Fn SLIST_EMPTY "SLIST_HEAD *head" +.Fn SLIST_FOREACH "VARNAME" "SLIST_HEAD *head" "FIELDNAME" +.Fn SLIST_FOREACH_SAFE "VARNAME" "SLIST_HEAD *head" "FIELDNAME" "TEMP_VARNAME" +.Ft void +.Fn SLIST_INIT "SLIST_HEAD *head" +.Ft void +.Fn SLIST_INSERT_AFTER "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn SLIST_REMOVE_AFTER "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "FIELDNAME" +.Ft void +.Fn SLIST_REMOVE "SLIST_HEAD *head" "struct TYPE *elm" "TYPE" "FIELDNAME" +.Pp +.Fn LIST_ENTRY "TYPE" +.Fn LIST_HEAD "HEADNAME" "TYPE" +.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" +.Ft "struct TYPE *" +.Fn LIST_FIRST "LIST_HEAD *head" +.Ft "struct TYPE *" +.Fn LIST_NEXT "struct TYPE *listelm" "FIELDNAME" +.Ft int +.Fn LIST_EMPTY "LIST_HEAD *head" +.Fn LIST_FOREACH "VARNAME" "LIST_HEAD *head" "FIELDNAME" +.Fn LIST_FOREACH_SAFE "VARNAME" "LIST_HEAD *head" "FIELDNAME" "TEMP_VARNAME" +.Ft void +.Fn LIST_INIT "LIST_HEAD *head" +.Ft void +.Fn LIST_INSERT_AFTER "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn LIST_INSERT_BEFORE "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn LIST_REMOVE "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn LIST_REPLACE "struct TYPE *elm" "struct TYPE *elm2" "FIELDNAME" +.Pp +.Fn SIMPLEQ_ENTRY "TYPE" +.Fn SIMPLEQ_HEAD "HEADNAME" "TYPE" +.Fn SIMPLEQ_HEAD_INITIALIZER "SIMPLEQ_HEAD head" +.Ft "struct TYPE *" +.Fn SIMPLEQ_FIRST "SIMPLEQ_HEAD *head" +.Ft "struct TYPE *" +.Fn SIMPLEQ_NEXT "struct TYPE *listelm" "FIELDNAME" +.Ft int +.Fn SIMPLEQ_EMPTY "SIMPLEQ_HEAD *head" +.Fn SIMPLEQ_FOREACH "VARNAME" "SIMPLEQ_HEAD *head" "FIELDNAME" +.Fn SIMPLEQ_FOREACH_SAFE "VARNAME" "SIMPLEQ_HEAD *head" "FIELDNAME" "TEMP_VARNAME" +.Ft void +.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head" +.Ft void +.Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn SIMPLEQ_REMOVE_AFTER "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "FIELDNAME" +.Fn SIMPLEQ_CONCAT "SIMPLEQ_HEAD *head1" "SIMPLEQ_HEAD *head2" +.Pp +.Fn STAILQ_ENTRY "TYPE" +.Fn STAILQ_HEAD "HEADNAME" "TYPE" +.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" +.Fn STAILQ_FIRST "STAILQ_HEAD *head" +.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_EMPTY "STAILQ_HEAD *head" +.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" +.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn STAILQ_INIT "STAILQ_HEAD *head" +.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" +.Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" +.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" +.Pp +.Fn TAILQ_ENTRY "TYPE" +.Fn TAILQ_HEAD "HEADNAME" "TYPE" +.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" +.Ft "struct TYPE *" +.Fn TAILQ_FIRST "TAILQ_HEAD *head" +.Ft "struct TYPE *" +.Fn TAILQ_NEXT "struct TYPE *listelm" "FIELDNAME" +.Ft "struct TYPE *" +.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" +.Ft "struct TYPE *" +.Fn TAILQ_PREV "struct TYPE *listelm" "HEADNAME" "FIELDNAME" +.Ft int +.Fn TAILQ_EMPTY "TAILQ_HEAD *head" +.Fn TAILQ_FOREACH "VARNAME" "TAILQ_HEAD *head" "FIELDNAME" +.Fn TAILQ_FOREACH_SAFE "VARNAME" "TAILQ_HEAD *head" "FIELDNAME" "TEMP_VARNAME" +.Fn TAILQ_FOREACH_REVERSE "VARNAME" "TAILQ_HEAD *head" "HEADNAME" "FIELDNAME" +.Fn TAILQ_FOREACH_REVERSE_SAFE "VARNAME" "TAILQ_HEAD *head" "HEADNAME" "FIELDNAME" "TEMP_VARNAME" +.Ft void +.Fn TAILQ_INIT "TAILQ_HEAD *head" +.Ft void +.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn TAILQ_INSERT_BEFORE "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME" +.Ft void +.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "struct TYPE *elm" "struct TYPE *elm2" "FIELDNAME" +.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "FIELDNAME" +.Sh DESCRIPTION +These macros define and operate on five types of data structures: +singly-linked lists, simple queues, lists, singly-linked tail queues, +and tail queues. +All five structures support the following functionality: +.Pp +.Bl -enum -compact -offset indent +.It +Insertion of a new entry at the head of the list. +.It +Insertion of a new entry after any element in the list. +.It +Removal of an entry from the head of the list. +.It +Forward traversal through the list. +.El +.Pp +The following table provides a quick overview +of which types support which additional macros: +.Bl -column -offset 6n "LAST, PREV, FOREACH_REVERSE" SLIST LIST SIMPLEQ STAILQ TAILQ +.It LAST, PREV, FOREACH_REVERSE Ta - Ta - Ta - Ta - Ta TAILQ +.It INSERT_BEFORE, REPLACE Ta - Ta LIST Ta - Ta - Ta TAILQ +.It INSERT_TAIL, CONCAT Ta - Ta - Ta SIMPLEQ Ta STAILQ Ta TAILQ +.It REMOVE_AFTER, REMOVE_HEAD Ta SLIST Ta - Ta SIMPLEQ Ta STAILQ Ta - +.It REMOVE Ta SLIST Ta LIST Ta - Ta STAILQ Ta TAILQ +.El +.Pp +Singly-linked lists are the simplest of the five data structures +and support only the above functionality. +Singly-linked lists are ideal for applications with large datasets +and few or no removals, or for implementing a LIFO queue. +.Pp +Simple queues and singly-linked tail queues add the following functionality: +.Pp +.Bl -enum -compact -offset indent +.It +Entries can be added at the end of a list. +.El +.Pp +However: +.Pp +.Bl -enum -compact -offset indent +.It +All list insertions must specify the head of the list. +.It +Each head entry requires two pointers rather than one. +.It +Code size is about 15% greater and operations run about 20% slower +than singly-linked lists. +.El +.Pp +Simple queues and singly-linked tail queues are ideal for applications with +large datasets and few or no removals, or for implementing a FIFO queue. +.Pp +All doubly linked types of data structures (lists and tail queues) +additionally allow: +.Pp +.Bl -enum -compact -offset indent +.It +Insertion of a new entry before any element in the list. +.It +Removal of any entry in the list. +.El +.Pp +However: +.Pp +.Bl -enum -compact -offset indent +.It +Each element requires two pointers rather than one. +.It +Code size and execution time of operations (except for removal) is about +twice that of the singly-linked data-structures. +.El +.Pp +Lists are the simplest of the doubly linked data structures and support +only the above functionality over singly-linked lists. +.Pp +Tail queues add the following functionality: +.Pp +.Bl -enum -compact -offset indent +.It +Entries can be added at the end of a list. +.It +They may be traversed backwards, at a cost. +.El +.Pp +However: +.Pp +.Bl -enum -compact -offset indent +.It +All list insertions and removals must specify the head of the list. +.It +Each head entry requires two pointers rather than one. +.It +Code size is about 15% greater and operations run about 20% slower +than singly-linked lists. +.El +.Pp +An additional type of data structure, circular queues, violated the C +language aliasing rules and were miscompiled as a result. +All code using them should be converted to another structure; +tail queues are usually the easiest to convert to. +.Pp +All these lists and queues are intrusive: they link together user +defined structures containing a field of type +.Li SLIST_ENTRY , +.Li LIST_ENTRY , +.Li SIMPLEQ_ENTRY , +.Li STAILQ_ENTRY , +or +.Li TAILQ_ENTRY . +In the macro definitions, +.Fa TYPE +is the name tag of the user defined structure and +.Fa FIELDNAME +is the name of the +.Li *_ENTRY +field. +If an instance of the user defined structure needs to be a member of +multiple lists at the same time, the structure requires multiple +.Li *_ENTRY +fields, one for each list. +.Pp +The argument +.Fa HEADNAME +is the name tag of a user defined structure that must be declared +using the macros +.Fn SLIST_HEAD , +.Fn LIST_HEAD , +.Fn SIMPLEQ_HEAD , +.Fn STAILQ_HEAD , +or +.Fn TAILQ_HEAD . +See the examples below for further explanation of how these macros are used. +.Sh SINGLY-LINKED LISTS +A singly-linked list is headed by a structure defined by the +.Fn SLIST_HEAD +macro. +This structure contains a single pointer to the first element on the list. +The elements are singly linked for minimum space and pointer manipulation +overhead at the expense of O(n) removal for arbitrary elements. +New elements can be added to the list after an existing element or +at the head of the list. +A +.Fa SLIST_HEAD +structure is declared as follows: +.Bd -literal -offset indent +SLIST_HEAD(HEADNAME, TYPE) 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 linked into the list. +A pointer to the head of the list can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The +.Fa HEADNAME +facility is often not used, leading to the following bizarre code: +.Bd -literal -offset indent +SLIST_HEAD(, TYPE) head, *headp; +.Ed +.Pp +The +.Fn SLIST_ENTRY +macro declares a structure that connects the elements in the list. +.Pp +The +.Fn SLIST_INIT +macro initializes the list referenced by +.Fa head . +.Pp +The list can also be initialized statically by using the +.Fn SLIST_HEAD_INITIALIZER +macro like this: +.Bd -literal -offset indent +SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head); +.Ed +.Pp +The +.Fn SLIST_INSERT_HEAD +macro inserts the new element +.Fa elm +at the head of the list. +.Pp +The +.Fn SLIST_INSERT_AFTER +macro inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The +.Fn SLIST_REMOVE_HEAD +macro removes the first element of the list pointed by +.Fa head . +.Pp +The +.Fn SLIST_REMOVE_AFTER +macro removes the list element immediately following +.Fa elm . +.Pp +The +.Fn SLIST_REMOVE +macro removes the element +.Fa elm +of the list pointed by +.Fa head . +.Pp +The +.Fn SLIST_FIRST +and +.Fn SLIST_NEXT +macros can be used to traverse the list: +.Bd -literal -offset indent +for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, FIELDNAME)) +.Ed +.Pp +Or, for simplicity, one can use the +.Fn SLIST_FOREACH +macro: +.Bd -literal -offset indent +SLIST_FOREACH(np, head, FIELDNAME) +.Ed +.Pp +The macro +.Fn SLIST_FOREACH_SAFE +traverses the list referenced by head in a +forward direction, assigning each element in turn to var. +However, unlike +.Fn SLIST_FOREACH +it is permitted to remove var as well +as free it from within the loop safely without interfering with the traversal. +.Pp +The +.Fn SLIST_EMPTY +macro should be used to check whether a simple list is empty. +.Sh SINGLY-LINKED LIST EXAMPLE +.Bd -literal +SLIST_HEAD(listhead, entry) head; +struct entry { + ... + SLIST_ENTRY(entry) entries; /* Simple list. */ + ... +} *n1, *n2, *np; + +SLIST_INIT(&head); /* Initialize simple list. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +SLIST_INSERT_HEAD(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +SLIST_INSERT_AFTER(n1, n2, entries); + +SLIST_FOREACH(np, &head, entries) /* Forward traversal. */ + np-> ... + +while (!SLIST_EMPTY(&head)) { /* Delete. */ + n1 = SLIST_FIRST(&head); + SLIST_REMOVE_HEAD(&head, entries); + free(n1); +} + +.Ed +.Sh LISTS +A list is headed by a structure defined by the +.Fn LIST_HEAD +macro. +This structure contains a single pointer to the first element on the list. +The elements are doubly linked so that an arbitrary element can be +removed without traversing the list. +New elements can be added to the list after an existing element, +before an existing element, or at the head of the list. +A +.Fa LIST_HEAD +structure is declared as follows: +.Bd -literal -offset indent +LIST_HEAD(HEADNAME, TYPE) 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 linked into the list. +A pointer to the head of the list can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The +.Fa HEADNAME +facility is often not used, leading to the following bizarre code: +.Bd -literal -offset indent +LIST_HEAD(, TYPE) head, *headp; +.Ed +.Pp +The +.Fn LIST_ENTRY +macro declares a structure that connects the elements in the list. +.Pp +The +.Fn LIST_INIT +macro initializes the list referenced by +.Fa head . +.Pp +The list can also be initialized statically by using the +.Fn LIST_HEAD_INITIALIZER +macro like this: +.Bd -literal -offset indent +LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head); +.Ed +.Pp +The +.Fn LIST_INSERT_HEAD +macro inserts the new element +.Fa elm +at the head of the list. +.Pp +The +.Fn LIST_INSERT_AFTER +macro inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The +.Fn LIST_INSERT_BEFORE +macro inserts the new element +.Fa elm +before the element +.Fa listelm . +.Pp +The +.Fn LIST_REMOVE +macro removes the element +.Fa elm +from the list. +.Pp +The +.Fn LIST_REPLACE +macro replaces the list element +.Fa elm +with the new element +.Fa elm2 . +.Pp +The +.Fn LIST_FIRST +and +.Fn LIST_NEXT +macros can be used to traverse the list: +.Bd -literal -offset indent +for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, FIELDNAME)) +.Ed +.Pp +Or, for simplicity, one can use the +.Fn LIST_FOREACH +macro: +.Bd -literal -offset indent +LIST_FOREACH(np, head, FIELDNAME) +.Ed +.Pp +The macro +.Fn LIST_FOREACH_SAFE +traverses the list referenced by head in a +forward direction, assigning each element in turn to var. +However, unlike +.Fn LIST_FOREACH +it is permitted to remove var as well +as free it from within the loop safely without interfering with the traversal. +.Pp +The +.Fn LIST_EMPTY +macro should be used to check whether a list is empty. +.Sh LIST EXAMPLE +.Bd -literal +LIST_HEAD(listhead, entry) head; +struct entry { + ... + LIST_ENTRY(entry) entries; /* List. */ + ... +} *n1, *n2, *np; + +LIST_INIT(&head); /* Initialize list. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +LIST_INSERT_HEAD(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +LIST_INSERT_AFTER(n1, n2, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert before. */ +LIST_INSERT_BEFORE(n1, n2, entries); + /* Forward traversal. */ +LIST_FOREACH(np, &head, entries) + np-> ... + +while (!LIST_EMPTY(&head)) { /* Delete. */ + n1 = LIST_FIRST(&head); + LIST_REMOVE(n1, entries); + free(n1); +} +.Ed +.Sh SIMPLE QUEUES +A simple queue is headed by a structure defined by the +.Fn SIMPLEQ_HEAD +macro. +This structure contains a pair of pointers, one to the first element in the +simple queue and the other to the last element in the simple queue. +The elements are singly linked. +New elements can be added to the queue after an existing element, +at the head of the queue or at the tail of the queue. +A +.Fa SIMPLEQ_HEAD +structure is declared as follows: +.Bd -literal -offset indent +SIMPLEQ_HEAD(HEADNAME, TYPE) 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 linked into the queue. +A pointer to the head of the queue can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The +.Fn SIMPLEQ_ENTRY +macro declares a structure that connects the elements in +the queue. +.Pp +The +.Fn SIMPLEQ_INIT +macro initializes the queue referenced by +.Fa head . +.Pp +The queue can also be initialized statically by using the +.Fn SIMPLEQ_HEAD_INITIALIZER +macro like this: +.Bd -literal -offset indent +SIMPLEQ_HEAD(HEADNAME, TYPE) head = SIMPLEQ_HEAD_INITIALIZER(head); +.Ed +.Pp +The +.Fn SIMPLEQ_INSERT_AFTER +macro inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The +.Fn SIMPLEQ_INSERT_HEAD +macro inserts the new element +.Fa elm +at the head of the queue. +.Pp +The +.Fn SIMPLEQ_INSERT_TAIL +macro inserts the new element +.Fa elm +at the end of the queue. +.Pp +The +.Fn SIMPLEQ_REMOVE_AFTER +macro removes the queue element immediately following +.Fa elm . +.Pp +The +.Fn SIMPLEQ_REMOVE_HEAD +macro removes the first element +from the queue. +.Pp +The +.Fn SIMPLEQ_CONCAT +macro concatenates all the elements of the queue referenced by +.Fa head2 +to the end of the queue referenced by +.Fa head1 , +emptying +.Fa head2 +in the process. +This is more efficient than removing and inserting the individual elements +as it does not actually traverse +.Fa head2 . +.Pp +The +.Fn SIMPLEQ_FIRST +and +.Fn SIMPLEQ_NEXT +macros can be used to traverse the queue. +The +.Fn SIMPLEQ_FOREACH +macro is used for queue traversal: +.Bd -literal -offset indent +SIMPLEQ_FOREACH(np, head, FIELDNAME) +.Ed +.Pp +The macro +.Fn SIMPLEQ_FOREACH_SAFE +traverses the queue referenced by head in a +forward direction, assigning each element in turn to var. +However, unlike +.Fn SIMPLEQ_FOREACH +it is permitted to remove var as well +as free it from within the loop safely without interfering with the traversal. +.Pp +The +.Fn SIMPLEQ_EMPTY +macro should be used to check whether a list is empty. +.Sh SIMPLE QUEUE EXAMPLE +.Bd -literal +SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); +struct entry { + ... + SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ + ... +} *n1, *n2, *np; + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +SIMPLEQ_INSERT_HEAD(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +SIMPLEQ_INSERT_TAIL(&head, n2, entries); + /* Forward traversal. */ +SIMPLEQ_FOREACH(np, &head, entries) + np-> ... + /* Delete. */ +while (!SIMPLEQ_EMPTY(&head)) { + n1 = SIMPLEQ_FIRST(&head); + SIMPLEQ_REMOVE_HEAD(&head, entries); + free(n1); +} +.Ed +.Sh SINGLY-LINKED TAIL QUEUES +A singly-linked tail queue is headed by a structure defined by the +.Fn STAILQ_HEAD +macro. +This structure contains a pair of pointers, one to the first element in +the tail queue and the other to the last element in the tail queue. +The elements are singly linked for minimum space and pointer manipulation +overhead at the expense of O(n) removal for arbitrary elements. +New elements can be added to the tail queue after an existing element, +at the head of the tail queue or at the end of the tail queue. +A +.Fa STAILQ_HEAD +structure is declared as follows: +.Bd -literal -offset indent +STAILQ_HEAD(HEADNAME, TYPE) 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 linked into the tail queue. +A pointer to the head of the tail queue can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The +.Fn STAILQ_ENTRY +macro declares a structure that connects the elements in +the tail queue. +.Pp +The +.Fn STAILQ_INIT +macro initializes the tail queue referenced by +.Fa head . +.Pp +The tail queue can also be initialized statically by using the +.Fn STAILQ_HEAD_INITIALIZER +macro like this: +.Bd -literal -offset indent +STAILQ_HEAD(HEADNAME, TYPE) head = STAILQ_HEAD_INITIALIZER(head); +.Ed +.Pp +The +.Fn STAILQ_INSERT_AFTER +macro inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The +.Fn STAILQ_INSERT_HEAD +macro inserts the new element +.Fa elm +at the head of the tail queue. +.Pp +The +.Fn STAILQ_INSERT_TAIL +macro inserts the new element +.Fa elm +at the end of the tail queue. +.Pp +The +.Fn STAILQ_REMOVE_AFTER +macro removes the queue element immediately following +.Fa elm . +Unlike +.Fa STAILQ_REMOVE , +this macro does not traverse the entire tail queue. +.Pp +The +.Fn STAILQ_REMOVE_HEAD +macro removes the first element +from the tail queue. +For optimum efficiency, +elements being removed from the head of the tail queue should +use this macro explicitly rather than the generic +.Fa STAILQ_REMOVE +macro. +.Pp +The +.Fn STAILQ_REMOVE +macro removes the element +.Fa elm +from the tail queue. +Use of this macro should be avoided as it traverses the entire list. +A doubly-linked tail queue should be used if this macro is needed in +high-usage code paths or to operate on long tail queues. +.Pp +The +.Fn STAILQ_CONCAT +macro concatenates all the elements of the tail queue referenced by +.Fa head2 +to the end of the tail queue referenced by +.Fa head1 , +emptying +.Fa head2 +in the process. +This is more efficient than removing and inserting the individual elements +as it does not actually traverse +.Fa head2 . +.Pp +The +.Fn STAILQ_FOREACH +macro is used for queue traversal: +.Bd -literal -offset indent +STAILQ_FOREACH(np, head, FIELDNAME) +.Ed +.Pp +The macro +.Fn STAILQ_FOREACH_SAFE +traverses the queue referenced by head in a +forward direction, assigning each element in turn to var. +However, unlike +.Fn STAILQ_FOREACH +it is permitted to remove var as well +as free it from within the loop safely without interfering with the traversal. +.Pp +The +.Fn STAILQ_FIRST , +.Fn STAILQ_NEXT , +and +.Fn STAILQ_LAST +macros can be used to manually traverse a tail queue or an arbitrary part of +one. +The +.Fn STAILQ_EMPTY +macro should be used to check whether a tail queue is empty. +.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE +.Bd -literal +STAILQ_HEAD(listhead, entry) head = STAILQ_HEAD_INITIALIZER(head); +struct entry { + ... + STAILQ_ENTRY(entry) entries; /* Singly-linked tail queue. */ + ... +} *n1, *n2, *np; + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +STAILQ_INSERT_HEAD(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +STAILQ_INSERT_TAIL(&head, n2, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +STAILQ_INSERT_AFTER(&head, n1, n2, entries); + + /* Deletion. */ +STAILQ_REMOVE(&head, n2, entry, entries); +free(n2); + /* Deletion from the head. */ +n3 = STAILQ_FIRST(&head); +STAILQ_REMOVE_HEAD(&head, entries); +free(n3); + /* Forward traversal. */ +STAILQ_FOREACH(np, &head, entries) + np-> ... + /* Safe forward traversal. */ +STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { + np-> ... + STAILQ_REMOVE(&head, np, entry, entries); + free(np); +} + /* Delete. */ +while (!STAILQ_EMPTY(&head)) { + n1 = STAILQ_FIRST(&head); + STAILQ_REMOVE_HEAD(&head, entries); + free(n1); +} +.Ed +.Sh TAIL QUEUES +A tail queue is headed by a structure defined by the +.Fn TAILQ_HEAD +macro. +This structure contains a pair of pointers, +one to the first element in the tail queue and the other to +the last element in the tail queue. +The elements are doubly linked so that an arbitrary element can be +removed without traversing the tail queue. +New elements can be added to the queue after an existing element, +before an existing element, at the head of the queue, or at the end +of the queue. +A +.Fa TAILQ_HEAD +structure is declared as follows: +.Bd -literal -offset indent +TAILQ_HEAD(HEADNAME, TYPE) 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 linked into the tail queue. +A pointer to the head of the tail queue can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The +.Fn TAILQ_ENTRY +macro declares a structure that connects the elements in +the tail queue. +.Pp +The +.Fn TAILQ_INIT +macro initializes the tail queue referenced by +.Fa head . +.Pp +The tail queue can also be initialized statically by using the +.Fn TAILQ_HEAD_INITIALIZER +macro. +.Pp +The +.Fn TAILQ_INSERT_HEAD +macro inserts the new element +.Fa elm +at the head of the tail queue. +.Pp +The +.Fn TAILQ_INSERT_TAIL +macro inserts the new element +.Fa elm +at the end of the tail queue. +.Pp +The +.Fn TAILQ_INSERT_AFTER +macro inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The +.Fn TAILQ_INSERT_BEFORE +macro inserts the new element +.Fa elm +before the element +.Fa listelm . +.Pp +The +.Fn TAILQ_REMOVE +macro removes the element +.Fa elm +from the tail queue. +.Pp +The +.Fn TAILQ_REPLACE +macro replaces the list element +.Fa elm +with the new element +.Fa elm2 . +.Pp +The +.Fn TAILQ_CONCAT +macro concatenates all the elements of the tail queue referenced by +.Fa head2 +to the end of the tail queue referenced by +.Fa head1 , +emptying +.Fa head2 +in the process. +This is more efficient than removing and inserting the individual elements +as it does not actually traverse +.Fa head2 . +.Pp +.Fn TAILQ_FOREACH +and +.Fn TAILQ_FOREACH_REVERSE +are used for traversing a tail queue. +.Fn TAILQ_FOREACH +starts at the first element and proceeds towards the last. +.Fn TAILQ_FOREACH_REVERSE +starts at the last element and proceeds towards the first. +.Bd -literal -offset indent +TAILQ_FOREACH(np, &head, FIELDNAME) +TAILQ_FOREACH_REVERSE(np, &head, HEADNAME, FIELDNAME) +.Ed +.Pp +The macros +.Fn TAILQ_FOREACH_SAFE +and +.Fn TAILQ_FOREACH_REVERSE_SAFE +traverse the list referenced by head +in a forward or reverse direction respectively, +assigning each element in turn to var. +However, unlike their unsafe counterparts, +they permit both the removal of var +as well as freeing it from within the loop safely +without interfering with the traversal. +.Pp +The +.Fn TAILQ_FIRST , +.Fn TAILQ_NEXT , +.Fn TAILQ_LAST +and +.Fn TAILQ_PREV +macros can be used to manually traverse a tail queue or an arbitrary part of +one. +.Pp +The +.Fn TAILQ_EMPTY +macro should be used to check whether a tail queue is empty. +.Sh TAIL QUEUE EXAMPLE +.Bd -literal +TAILQ_HEAD(tailhead, entry) head; +struct entry { + ... + TAILQ_ENTRY(entry) entries; /* Tail queue. */ + ... +} *n1, *n2, *np; + +TAILQ_INIT(&head); /* Initialize queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +TAILQ_INSERT_HEAD(&head, n1, entries); + +n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +TAILQ_INSERT_TAIL(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +TAILQ_INSERT_AFTER(&head, n1, n2, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert before. */ +TAILQ_INSERT_BEFORE(n1, n2, entries); + /* Forward traversal. */ +TAILQ_FOREACH(np, &head, entries) + np-> ... + /* Manual forward traversal. */ +for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries)) + np-> ... + /* Delete. */ +while ((np = TAILQ_FIRST(&head))) { + TAILQ_REMOVE(&head, np, entries); + free(np); +} + +.Ed +.Sh SEE ALSO +.Xr tree 3 +.Sh NOTES +It is an error to assume the next and previous fields are preserved +after an element has been removed from a list or queue. +Using any macro (except the various forms of insertion) on an element +removed from a list or queue is incorrect. +An example of erroneous usage is removing the same element twice. +.Pp +The +.Fn SLIST_END , +.Fn LIST_END , +.Fn SIMPLEQ_END , +.Fn STAILQ_END +and +.Fn TAILQ_END +macros are deprecated; they provided symmetry with the historical +.Fn CIRCLEQ_END +and just expand to +.Dv NULL . +.Pp +Trying to free a list in the following way is a common error: +.Bd -literal -offset indent +LIST_FOREACH(var, head, entry) + free(var); +free(head); +.Ed +.Pp +Since +.Va var +is free'd, the FOREACH macros refer to a pointer that may have been +reallocated already. +A similar situation occurs when the current element is deleted +from the list. +In cases like these the data structure's FOREACH_SAFE macros should be used +instead. +.Sh HISTORY +The +.Nm queue +functions first appeared in +.Bx 4.4 . +The historical circle queue macros were deprecated in +.Ox 5.5 . diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 new file mode 100644 index 0000000..7fa1f31 --- /dev/null +++ b/share/man/man3/tree.3 @@ -0,0 +1,582 @@ +.\"/* +.\" * Copyright 2002 Niels Provos <provos@citi.umich.edu> +.\" * 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. +.\" */ +.Dd $Mdocdate: Dec 16 2024 $ +.Dt SPLAY_INIT 3 +.Os +.Sh NAME +.Nm SPLAY_PROTOTYPE , +.Nm SPLAY_GENERATE , +.Nm SPLAY_ENTRY , +.Nm SPLAY_HEAD , +.Nm SPLAY_INITIALIZER , +.Nm SPLAY_ROOT , +.Nm SPLAY_EMPTY , +.Nm SPLAY_NEXT , +.Nm SPLAY_MIN , +.Nm SPLAY_MAX , +.Nm SPLAY_FIND , +.Nm SPLAY_LEFT , +.Nm SPLAY_RIGHT , +.Nm SPLAY_FOREACH , +.Nm SPLAY_INIT , +.Nm SPLAY_INSERT , +.Nm SPLAY_REMOVE , +.Nm RB_PROTOTYPE , +.Nm RB_PROTOTYPE_STATIC , +.Nm RB_GENERATE , +.Nm RB_GENERATE_STATIC , +.Nm RB_ENTRY , +.Nm RB_HEAD , +.Nm RB_INITIALIZER , +.Nm RB_ROOT , +.Nm RB_EMPTY , +.Nm RB_NEXT , +.Nm RB_PREV , +.Nm RB_MIN , +.Nm RB_MAX , +.Nm RB_FIND , +.Nm RB_NFIND , +.Nm RB_LEFT , +.Nm RB_RIGHT , +.Nm RB_PARENT , +.Nm RB_FOREACH , +.Nm RB_FOREACH_SAFE , +.Nm RB_FOREACH_REVERSE , +.Nm RB_FOREACH_REVERSE_SAFE , +.Nm RB_INIT , +.Nm RB_INSERT , +.Nm RB_REMOVE +.Nd implementations of splay and red-black trees +.Sh SYNOPSIS +.In sys/tree.h +.Pp +.Fn SPLAY_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP" +.Fn SPLAY_GENERATE "NAME" "TYPE" "FIELD" "CMP" +.Fn SPLAY_ENTRY "TYPE" +.Fn SPLAY_HEAD "HEADNAME" "TYPE" +.Ft "struct TYPE *" +.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head" +.Fn SPLAY_ROOT "SPLAY_HEAD *head" +.Ft "int" +.Fn SPLAY_EMPTY "SPLAY_HEAD *head" +.Ft "struct TYPE *" +.Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head" +.Ft "struct TYPE *" +.Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head" +.Ft "struct TYPE *" +.Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME" +.Ft "struct TYPE *" +.Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME" +.Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head" +.Ft void +.Fn SPLAY_INIT "SPLAY_HEAD *head" +.Ft "struct TYPE *" +.Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm" +.Pp +.Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP" +.Fn RB_PROTOTYPE_STATIC "NAME" "TYPE" "FIELD" "CMP" +.Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP" +.Fn RB_GENERATE_STATIC "NAME" "TYPE" "FIELD" "CMP" +.Fn RB_ENTRY "TYPE" +.Fn RB_HEAD "HEADNAME" "TYPE" +.Fn RB_INITIALIZER "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_ROOT "RB_HEAD *head" +.Ft "int" +.Fn RB_EMPTY "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_PREV "NAME" "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_MIN "NAME" "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_MAX "NAME" "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_NFIND "NAME" "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME" +.Ft "struct TYPE *" +.Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME" +.Fn RB_FOREACH "VARNAME" "NAME" "RB_HEAD *head" +.Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" +.Fn RB_FOREACH_REVERSE "VARNAME" "NAME" "RB_HEAD *head" +.Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME" +.Ft void +.Fn RB_INIT "RB_HEAD *head" +.Ft "struct TYPE *" +.Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm" +.Ft "struct TYPE *" +.Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm" +.Sh DESCRIPTION +These macros define data structures for different types of trees: +splay trees and red-black trees. +.Pp +In the macro definitions, +.Fa TYPE +is the name tag of a user defined structure that must contain a field named +.Fa FIELD , +of type +.Li SPLAY_ENTRY +or +.Li RB_ENTRY . +The argument +.Fa HEADNAME +is the name tag of a user defined structure that must be declared +using the macros +.Fn SPLAY_HEAD +or +.Fn RB_HEAD . +The argument +.Fa NAME +has to be a unique name prefix for every tree that is defined. +.Pp +The function prototypes are declared with +.Li SPLAY_PROTOTYPE , +.Li RB_PROTOTYPE , +or +.Li RB_PROTOTYPE_STATIC . +The function bodies are generated with +.Li SPLAY_GENERATE , +.Li RB_GENERATE , +or +.Li RB_GENERATE_STATIC . +See the examples below for further explanation of how these macros are used. +.Sh SPLAY TREES +A splay tree is a self-organizing data structure. +Every operation on the tree causes a splay to happen. +The splay moves the requested node to the root of the tree and partly +rebalances it. +.Pp +This has the benefit that request locality causes faster lookups as +the requested nodes move to the top of the tree. +On the other hand, every lookup causes memory writes. +.Pp +The Balance Theorem bounds the total access time for m operations +and n inserts on an initially empty tree as O((m + n)lg n). +The amortized cost for a sequence of m accesses to a splay tree is O(lg n). +.Pp +A splay tree is headed by a structure defined by the +.Fn SPLAY_HEAD +macro. +A +.Fa SPLAY_HEAD +structure is declared as follows: +.Bd -literal -offset indent +SPLAY_HEAD(HEADNAME, TYPE) 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 SPLAY_ENTRY +macro declares a structure that allows elements to be connected in the tree. +.Pp +In order to use the functions that manipulate the tree structure, +their prototypes need to be declared with the +.Fn SPLAY_PROTOTYPE +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 SPLAY_ENTRY . +.Pp +The function bodies are generated with the +.Fn SPLAY_GENERATE +macro. +It takes the same arguments as the +.Fn SPLAY_PROTOTYPE +macro, but should be used only once. +.Pp +Finally, +the +.Fa CMP +argument is the name of a function used to compare trees' nodes +with each other. +The function takes two arguments of type +.Fa "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 SPLAY_INIT +macro initializes the tree referenced by +.Fa head . +.Pp +The splay tree can also be initialized statically by using the +.Fn SPLAY_INITIALIZER +macro like this: +.Bd -literal -offset indent +SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(&head); +.Ed +.Pp +The +.Fn SPLAY_INSERT +macro inserts the new element +.Fa elm +into the tree. +Upon success, +.Va NULL +is returned. +If a matching element already exists in the tree, the insertion is +aborted, and a pointer to the existing element is returned. +.Pp +The +.Fn SPLAY_REMOVE +macro removes the element +.Fa elm +from the tree pointed by +.Fa head . +Upon success, a pointer to the removed element is returned. +.Va NULL +is returned if +.Fa elm +is not present in the tree. +.Pp +The +.Fn SPLAY_FIND +macro can be used to find a particular element in the tree. +.Bd -literal -offset indent +struct TYPE find, *res; +find.key = 30; +res = SPLAY_FIND(NAME, &head, &find); +.Ed +.Pp +The +.Fn SPLAY_ROOT , +.Fn SPLAY_MIN , +.Fn SPLAY_MAX , +and +.Fn SPLAY_NEXT +macros can be used to traverse the tree: +.Bd -literal -offset indent +for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np)) +.Ed +.Pp +Or, for simplicity, one can use the +.Fn SPLAY_FOREACH +macro: +.Bd -literal -offset indent +SPLAY_FOREACH(np, NAME, &head) +.Ed +.Pp +The +.Fn SPLAY_EMPTY +macro should be used to check whether a splay tree is empty. +.Sh RED-BLACK TREES +A red-black tree is a binary search tree with the node color as an +extra attribute. +It fulfills a set of conditions: +.Pp +.Bl -enum -compact -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 O(lg n). +The maximum height of a red-black tree is 2lg (n+1). +.Pp +A red-black tree is headed by a structure defined by the +.Fn RB_HEAD +macro. +A +.Fa RB_HEAD +structure is declared as follows: +.Bd -literal -offset indent +RB_HEAD(HEADNAME, TYPE) 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 RB_ENTRY +macro declares a structure that allows elements to be connected in the tree. +.Pp +In order to use the functions that manipulate the tree structure, +their prototypes need to be declared with the +.Fn RB_PROTOTYPE +or +.Fn RB_PROTOTYPE_STATIC +macros, +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 RB_ENTRY . +.Pp +The function bodies are generated with the +.Fn RB_GENERATE +or +.Fn RB_GENERATE_STATIC +macros. +These macros take the same arguments as the +.Fn RB_PROTOTYPE +and +.Fn RB_PROTOTYPE_STATIC +macros, but should be used only once. +.Pp +Finally, +the +.Fa CMP +argument is the name of a function used to compare trees' nodes +with each other. +The function takes two arguments of type +.Fa "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 RB_INIT +macro initializes the tree referenced by +.Fa head . +.Pp +The red-black tree can also be initialized statically by using the +.Fn RB_INITIALIZER +macro like this: +.Bd -literal -offset indent +RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(&head); +.Ed +.Pp +The +.Fn RB_INSERT +macro inserts the new element +.Fa elm +into the tree. +Upon success, +.Va NULL +is returned. +If a matching element already exists in the tree, the insertion is +aborted, and a pointer to the existing element is returned. +.Pp +The +.Fn RB_REMOVE +macro removes the element +.Fa elm +from the tree pointed by +.Fa head . +.Fn RB_REMOVE +returns +.Fa elm . +.Pp +The +.Fn RB_FIND +and +.Fn RB_NFIND +macros can be used to find a particular element in the tree. +.Fn RB_FIND +finds the node with the same key as +.Fa elm . +.Fn RB_NFIND +finds the first node greater than or equal to the search key. +.Bd -literal -offset indent +struct TYPE find, *res; +find.key = 30; +res = RB_FIND(NAME, &head, &find); +.Ed +.Pp +The +.Fn RB_ROOT , +.Fn RB_MIN , +.Fn RB_MAX , +.Fn RB_NEXT , +and +.Fn RB_PREV +macros can be used to traverse the tree: +.Bd -literal -offset indent +for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np)) +.Ed +.Pp +Or, for simplicity, one can use the +.Fn RB_FOREACH +or +.Fn RB_FOREACH_REVERSE +macros: +.Bd -literal -offset indent +RB_FOREACH(np, NAME, &head) +.Ed +.Pp +The macros +.Fn RB_FOREACH_SAFE +and +.Fn RB_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 +The +.Fn RB_EMPTY +macro should be used to check whether a red-black tree is empty. +.Sh EXAMPLES +The following example demonstrates how to declare a red-black tree +holding integers. +Values are inserted into it and the contents of the tree are printed +in order. +Lastly, the internal structure of the tree is printed. +.Bd -literal -offset 3n +#include <sys/tree.h> +#include <err.h> +#include <stdio.h> +#include <stdlib.h> + +struct node { + RB_ENTRY(node) entry; + int i; +}; + +int intcmp(struct node *, struct node *); +void print_tree(struct node *); + +int +intcmp(struct node *e1, struct node *e2) +{ + return (e1->i < e2->i ? -1 : e1->i > e2->i); +} + +RB_HEAD(inttree, node) head = RB_INITIALIZER(&head); +RB_PROTOTYPE(inttree, node, entry, intcmp) +RB_GENERATE(inttree, node, entry, intcmp) + +int testdata[] = { + 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18, + 7, 11, 14 +}; + +void +print_tree(struct node *n) +{ + struct node *left, *right; + + if (n == NULL) { + printf("nil"); + return; + } + left = RB_LEFT(n, entry); + right = RB_RIGHT(n, entry); + if (left == NULL && right == NULL) + printf("%d", n->i); + else { + printf("%d(", n->i); + print_tree(left); + printf(","); + print_tree(right); + printf(")"); + } +} + +int +main(void) +{ + int i; + struct node *n; + + for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) { + if ((n = malloc(sizeof(struct node))) == NULL) + err(1, NULL); + n->i = testdata[i]; + RB_INSERT(inttree, &head, n); + } + + RB_FOREACH(n, inttree, &head) { + printf("%d\en", n->i); + } + print_tree(RB_ROOT(&head)); + printf("\en"); + return (0); +} +.Ed +.Sh SEE ALSO +.Xr queue 3 +.Sh NOTES +Trying to free a tree in the following way is a common error: +.Bd -literal -offset indent +SPLAY_FOREACH(var, NAME, &head) { + SPLAY_REMOVE(NAME, &head, var); + free(var); +} +free(head); +.Ed +.Pp +Since +.Va var +is free'd, the +.Fn FOREACH +macro refers to a pointer that may have been reallocated already. +Proper code needs a second variable. +.Bd -literal -offset indent +for (var = SPLAY_MIN(NAME, &head); var != NULL; var = nxt) { + nxt = SPLAY_NEXT(NAME, &head, var); + SPLAY_REMOVE(NAME, &head, var); + free(var); +} +.Ed +.Sh AUTHORS +The author of the tree macros is +.An Niels Provos . |