diff options
Diffstat (limited to 'man3/slist.3')
| -rw-r--r-- | man3/slist.3 | 319 |
1 files changed, 319 insertions, 0 deletions
diff --git a/man3/slist.3 b/man3/slist.3 new file mode 100644 index 0000000..98ce859 --- /dev/null +++ b/man3/slist.3 @@ -0,0 +1,319 @@ +.\" 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 SLIST 3 2023-05-03 "Linux man-pages 6.05.01" +.SH NAME +SLIST_EMPTY, +SLIST_ENTRY, +SLIST_FIRST, +SLIST_FOREACH, +.\"SLIST_FOREACH_FROM, +.\"SLIST_FOREACH_FROM_SAFE, +.\"SLIST_FOREACH_SAFE, +SLIST_HEAD, +SLIST_HEAD_INITIALIZER, +SLIST_INIT, +SLIST_INSERT_AFTER, +SLIST_INSERT_HEAD, +SLIST_NEXT, +SLIST_REMOVE, +.\"SLIST_REMOVE_AFTER, +SLIST_REMOVE_HEAD +.\"SLIST_SWAP +\- implementation of a singly linked list +.SH LIBRARY +Standard C library +.RI ( libc ", " \-lc ) +.SH SYNOPSIS +.nf +.B #include <sys/queue.h> +.PP +.B SLIST_ENTRY(TYPE); +.PP +.B SLIST_HEAD(HEADNAME, TYPE); +.BI "SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD " head ); +.BI "void SLIST_INIT(SLIST_HEAD *" head ); +.PP +.BI "int SLIST_EMPTY(SLIST_HEAD *" head ); +.PP +.BI "void SLIST_INSERT_HEAD(SLIST_HEAD *" head , +.BI " struct TYPE *" elm ", SLIST_ENTRY " NAME ); +.BI "void SLIST_INSERT_AFTER(struct TYPE *" listelm , +.BI " struct TYPE *" elm ", SLIST_ENTRY " NAME ); +.PP +.BI "struct TYPE *SLIST_FIRST(SLIST_HEAD *" head ); +.BI "struct TYPE *SLIST_NEXT(struct TYPE *" elm ", SLIST_ENTRY " NAME ); +.PP +.BI "SLIST_FOREACH(struct TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME ); +.\" .BI "SLIST_FOREACH_FROM(struct TYPE *" var ", SLIST_HEAD *" head , +.\" .BI " SLIST_ENTRY " NAME ); +.\" .PP +.\" .BI "SLIST_FOREACH_SAFE(struct TYPE *" var ", SLIST_HEAD *" head , +.\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var ); +.\" .BI "SLIST_FOREACH_FROM_SAFE(struct TYPE *" var ", SLIST_HEAD *" head , +.\" .BI " SLIST_ENTRY " NAME ", struct TYPE *" temp_var ); +.PP +.BI "void SLIST_REMOVE(SLIST_HEAD *" head ", struct TYPE *" elm , +.BI " SLIST_ENTRY " NAME ); +.BI "void SLIST_REMOVE_HEAD(SLIST_HEAD *" head , +.BI " SLIST_ENTRY " NAME ); +.\" .BI "void SLIST_REMOVE_AFTER(struct TYPE *" elm , +.\" .BI " SLIST_ENTRY " NAME ); +.\" .PP +.\" .BI "void SLIST_SWAP(SLIST_HEAD *" head1 ", SLIST_HEAD *" head2 , +.\" .BI " SLIST_ENTRY " NAME ); +.fi +.SH DESCRIPTION +These macros define and operate on doubly linked lists. +.PP +In the macro definitions, +.I TYPE +is the name of a user-defined structure, +that must contain a field of type +.IR SLIST_ENTRY , +named +.IR NAME . +The argument +.I HEADNAME +is the name of a user-defined structure +that must be declared using the macro +.BR SLIST_HEAD (). +.SS Creation +A singly linked list is headed by a structure defined by the +.BR 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. +An +.I SLIST_HEAD +structure is declared as follows: +.PP +.in +4 +.EX +SLIST_HEAD(HEADNAME, TYPE) head; +.EE +.in +.PP +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: +.PP +.in +4 +.EX +struct HEADNAME *headp; +.EE +.in +.PP +(The names +.I head +and +.I headp +are user selectable.) +.PP +.BR SLIST_ENTRY () +declares a structure that connects the elements in +the list. +.PP +.BR SLIST_HEAD_INITIALIZER () +evaluates to an initializer for the list +.IR head . +.PP +.BR SLIST_INIT () +initializes the list referenced by +.IR head . +.PP +.BR SLIST_EMPTY () +evaluates to true if there are no elements in the list. +.SS Insertion +.BR SLIST_INSERT_HEAD () +inserts the new element +.I elm +at the head of the list. +.PP +.BR SLIST_INSERT_AFTER () +inserts the new element +.I elm +after the element +.IR listelm . +.SS Traversal +.BR SLIST_FIRST () +returns the first element in the list, or NULL if the list is empty. +.PP +.BR SLIST_NEXT () +returns the next element in the list. +.PP +.BR SLIST_FOREACH () +traverses the list referenced by +.I head +in the forward direction, +assigning each element in turn to +.IR var . +.\" .PP +.\" .BR SLIST_FOREACH_FROM () +.\" behaves identically to +.\" .BR SLIST_FOREACH () +.\" when +.\" .I var +.\" is NULL, else it treats +.\" .I var +.\" as a previously found SLIST element and begins the loop at +.\" .I var +.\" instead of the first element in the SLIST referenced by +.\" .IR head . +.\" .Pp +.\" .BR SLIST_FOREACH_SAFE () +.\" traverses the list referenced by +.\" .I head +.\" in the forward direction, assigning each element in +.\" turn to +.\" .IR var . +.\" However, unlike +.\" .BR SLIST_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. +.\" .PP +.\" .BR SLIST_FOREACH_FROM_SAFE () +.\" behaves identically to +.\" .BR SLIST_FOREACH_SAFE () +.\" when +.\" .I var +.\" is NULL, else it treats +.\" .I var +.\" as a previously found SLIST element and begins the loop at +.\" .I var +.\" instead of the first element in the SLIST referenced by +.\" .IR head . +.SS Removal +.BR SLIST_REMOVE () +removes the element +.I elm +from the list. +.PP +.BR SLIST_REMOVE_HEAD () +removes the element +.I elm +from the head of the list. +For optimum efficiency, +elements being removed from the head of the list +should explicitly use this macro instead of the generic +.BR SLIST_REMOVE (). +.\" .PP +.\" .BR SLIST_REMOVE_AFTER () +.\" removes the element after +.\" .I elm +.\" from the list. +.\" Unlike +.\" .IR SLIST_REMOVE , +.\" this macro does not traverse the entire list. +.\" .SS Other features +.\" .BR SLIST_SWAP () +.\" swaps the contents of +.\" .I head1 +.\" and +.\" .IR head2 . +.SH RETURN VALUE +.BR SLIST_EMPTY () +returns nonzero if the list is empty, +and zero if the list contains at least one entry. +.PP +.BR SLIST_FIRST (), +and +.BR SLIST_NEXT () +return a pointer to the first or next +.I TYPE +structure, respectively. +.PP +.BR SLIST_HEAD_INITIALIZER () +returns an initializer that can be assigned to the list +.IR head . +.SH STANDARDS +BSD. +.SH HISTORY +4.4BSD. +.SH BUGS +.BR SLIST_FOREACH () +doesn't allow +.I var +to be removed or freed within the loop, +as it would interfere with the traversal. +.BR SLIST_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 (slist.c) +.EX +#include <stddef.h> +#include <stdio.h> +#include <stdlib.h> +#include <sys/queue.h> +\& +struct entry { + int data; + SLIST_ENTRY(entry) entries; /* Singly linked list */ +}; +\& +SLIST_HEAD(slisthead, entry); +\& +int +main(void) +{ + struct entry *n1, *n2, *n3, *np; + struct slisthead head; /* Singly linked list + head */ +\& + SLIST_INIT(&head); /* Initialize the queue */ +\& + 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_REMOVE(&head, n2, entry, entries);/* Deletion */ + free(n2); +\& + n3 = SLIST_FIRST(&head); + SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head */ + free(n3); +\& + for (unsigned int i = 0; i < 5; i++) { + n1 = malloc(sizeof(struct entry)); + SLIST_INSERT_HEAD(&head, n1, entries); + n1\->data = i; + } +\& + /* Forward traversal */ + SLIST_FOREACH(np, &head, entries) + printf("%i\en", np\->data); +\& + while (!SLIST_EMPTY(&head)) { /* List deletion */ + n1 = SLIST_FIRST(&head); + SLIST_REMOVE_HEAD(&head, entries); + free(n1); + } + SLIST_INIT(&head); +\& + exit(EXIT_SUCCESS); +} +.EE +.\" SRC END +.SH SEE ALSO +.BR insque (3), +.BR queue (7) |