summaryrefslogtreecommitdiffstats
path: root/man3/slist.3
diff options
context:
space:
mode:
Diffstat (limited to 'man3/slist.3')
-rw-r--r--man3/slist.3319
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)