diff options
Diffstat (limited to 'man/man3/list.3')
| -rw-r--r-- | man/man3/list.3 | 308 |
1 files changed, 308 insertions, 0 deletions
diff --git a/man/man3/list.3 b/man/man3/list.3 new file mode 100644 index 000000000..6f33dbf99 --- /dev/null +++ b/man/man3/list.3 @@ -0,0 +1,308 @@ +.\" Copyright (c) 1993 +.\" The Regents of the University of California. All rights reserved. +.\" and Copyright (c) 2020 by Alejandro Colomar <alx@kernel.org> +.\" +.\" SPDX-License-Identifier: BSD-3-Clause +.\" +.\" +.TH LIST 3 (date) "Linux man-pages (unreleased)" +.SH NAME +LIST_EMPTY, +LIST_ENTRY, +LIST_FIRST, +LIST_FOREACH, +.\"LIST_FOREACH_FROM, +.\"LIST_FOREACH_SAFE, +.\"LIST_FOREACH_FROM_SAFE, +LIST_HEAD, +LIST_HEAD_INITIALIZER, +LIST_INIT, +LIST_INSERT_AFTER, +LIST_INSERT_BEFORE, +LIST_INSERT_HEAD, +LIST_NEXT, +.\"LIST_PREV, +LIST_REMOVE +.\"LIST_SWAP +\- implementation of a doubly linked list +.SH LIBRARY +Standard C library +.RI ( libc ", " \-lc ) +.SH SYNOPSIS +.nf +.B #include <sys/queue.h> +.P +.B LIST_ENTRY(TYPE); +.P +.B LIST_HEAD(HEADNAME, TYPE); +.BI "LIST_HEAD LIST_HEAD_INITIALIZER(LIST_HEAD " head ); +.BI "void LIST_INIT(LIST_HEAD *" head ); +.P +.BI "int LIST_EMPTY(LIST_HEAD *" head ); +.P +.BI "void LIST_INSERT_HEAD(LIST_HEAD *" head , +.BI " struct TYPE *" elm ", LIST_ENTRY " NAME ); +.BI "void LIST_INSERT_BEFORE(struct TYPE *" listelm , +.BI " struct TYPE *" elm ", LIST_ENTRY " NAME ); +.BI "void LIST_INSERT_AFTER(struct TYPE *" listelm , +.BI " struct TYPE *" elm ", LIST_ENTRY " NAME ); +.P +.BI "struct TYPE *LIST_FIRST(LIST_HEAD *" head ); +.\" .BI "struct TYPE *LIST_PREV(struct TYPE *" elm ", LIST_HEAD *" head , +.\" .BI " struct TYPE, LIST_ENTRY " NAME ); +.BI "struct TYPE *LIST_NEXT(struct TYPE *" elm ", LIST_ENTRY " NAME ); +.P +.BI "LIST_FOREACH(struct TYPE *" var ", LIST_HEAD *" head ", LIST_ENTRY " NAME ); +.\" .BI "LIST_FOREACH_FROM(struct TYPE *" var ", LIST_HEAD *" head ", LIST_ENTRY " NAME ); +.\" .P +.\" .BI "LIST_FOREACH_SAFE(struct TYPE *" var ", LIST_HEAD *" head , +.\" .BI " LIST_ENTRY " NAME ", struct TYPE *" temp_var ); +.\" .BI "LIST_FOREACH_FROM_SAFE(struct TYPE *" var ", LIST_HEAD *" head , +.\" .BI " LIST_ENTRY " NAME ", struct TYPE *" temp_var ); +.P +.BI "void LIST_REMOVE(struct TYPE *" elm ", LIST_ENTRY " NAME ); +.\" .P +.\" .BI "void LIST_SWAP(LIST_HEAD *" head1 ", LIST_HEAD *" head2 , +.\" .BI " struct TYPE, LIST_ENTRY " NAME ); +.fi +.SH DESCRIPTION +These macros define and operate on doubly linked lists. +.P +In the macro definitions, +.I TYPE +is the name of a user-defined structure, +that must contain a field of type +.IR LIST_ENTRY , +named +.IR NAME . +The argument +.I HEADNAME +is the name of a user-defined structure +that must be declared using the macro +.BR LIST_HEAD (). +.SS Creation +A list is headed by a structure defined by the +.BR 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 +.I LIST_HEAD +structure is declared as follows: +.P +.in +4 +.EX +LIST_HEAD(HEADNAME, TYPE) head; +.EE +.in +.P +where +.I struct HEADNAME +is the structure to be defined, and +.I struct 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: +.P +.in +4 +.EX +struct HEADNAME *headp; +.EE +.in +.P +(The names +.I head +and +.I headp +are user selectable.) +.P +.BR LIST_ENTRY () +declares a structure that connects the elements in the list. +.P +.BR LIST_HEAD_INITIALIZER () +evaluates to an initializer for the list +.IR head . +.P +.BR LIST_INIT () +initializes the list referenced by +.IR head . +.P +.BR LIST_EMPTY () +evaluates to true if there are no elements in the list. +.SS Insertion +.BR LIST_INSERT_HEAD () +inserts the new element +.I elm +at the head of the list. +.P +.BR LIST_INSERT_BEFORE () +inserts the new element +.I elm +before the element +.IR listelm . +.P +.BR LIST_INSERT_AFTER () +inserts the new element +.I elm +after the element +.IR listelm . +.SS Traversal +.BR LIST_FIRST () +returns the first element in the list, or NULL if the list is empty. +.\" .P +.\" .BR LIST_PREV () +.\" returns the previous element in the list, or NULL if this is the first. +.\" List +.\" .I head +.\" must contain element +.\" .IR elm . +.P +.BR LIST_NEXT () +returns the next element in the list, or NULL if this is the last. +.P +.BR LIST_FOREACH () +traverses the list referenced by +.I head +in the forward direction, +assigning each element in turn to +.IR var . +.\" .P +.\" .BR LIST_FOREACH_FROM () +.\" behaves identically to +.\" .BR LIST_FOREACH () +.\" when +.\" .I var +.\" is NULL, else it treats +.\" .I var +.\" as a previously found LIST element and begins the loop at +.\" .I var +.\" instead of the first element in the LIST referenced by +.\" .IR head . +.\" .P +.\" .BR LIST_FOREACH_SAFE () +.\" traverses the list referenced by +.\" .I head +.\" in the forward direction, assigning each element in turn to +.\" .IR var . +.\" However, unlike +.\" .BR LIST_FOREACH () +.\" here it is permitted to both remove +.\" .I var +.\" as well as free it from within the loop safely without interfering with the +.\" traversal. +.\" .P +.\" .BR LIST_FOREACH_FROM_SAFE () +.\" behaves identically to +.\" .BR LIST_FOREACH_SAFE () +.\" when +.\" .I var +.\" is NULL, else it treats +.\" .I var +.\" as a previously found LIST element and begins the loop at +.\" .I var +.\" instead of the first element in the LIST referenced by +.\" .IR head . +.SS Removal +.BR LIST_REMOVE () +removes the element +.I elm +from the list. +.\" .SS Other features +.\" .BR LIST_SWAP () +.\" swaps the contents of +.\" .I head1 +.\" and +.\" .IR head2 . +.SH RETURN VALUE +.BR LIST_EMPTY () +returns nonzero if the list is empty, +and zero if the list contains at least one entry. +.P +.BR LIST_FIRST (), +and +.BR LIST_NEXT () +return a pointer to the first or next +.I TYPE +structure, respectively. +.P +.BR LIST_HEAD_INITIALIZER () +returns an initializer that can be assigned to the list +.IR head . +.SH STANDARDS +BSD. +.SH HISTORY +4.4BSD. +.SH BUGS +.BR LIST_FOREACH () +doesn't allow +.I var +to be removed or freed within the loop, +as it would interfere with the traversal. +.BR LIST_FOREACH_SAFE (), +which is present on the BSDs but is not present in glibc, +fixes this limitation by allowing +.I var +to safely be removed from the list and freed from within the loop +without interfering with the traversal. +.SH EXAMPLES +.\" SRC BEGIN (list.c) +.EX +#include <stddef.h> +#include <stdio.h> +#include <stdlib.h> +#include <sys/queue.h> +\& +struct entry { + int data; + LIST_ENTRY(entry) entries; /* List */ +}; +\& +LIST_HEAD(listhead, entry); +\& +int +main(void) +{ + struct entry *n1, *n2, *n3, *np; + struct listhead head; /* List head */ + int i; +\& + LIST_INIT(&head); /* Initialize the 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); +\& + n3 = malloc(sizeof(struct entry)); /* Insert before */ + LIST_INSERT_BEFORE(n2, n3, entries); +\& + i = 0; /* Forward traversal */ + LIST_FOREACH(np, &head, entries) + np\->data = i++; +\& + LIST_REMOVE(n2, entries); /* Deletion */ + free(n2); + /* Forward traversal */ + LIST_FOREACH(np, &head, entries) + printf("%i\en", np\->data); + /* List deletion */ + n1 = LIST_FIRST(&head); + while (n1 != NULL) { + n2 = LIST_NEXT(n1, entries); + free(n1); + n1 = n2; + } + LIST_INIT(&head); +\& + exit(EXIT_SUCCESS); +} +.EE +.\" SRC END +.SH SEE ALSO +.BR insque (3), +.BR queue (7) |