slist.3: fork from queue.3
cover slist.3: fork from queue.3
Hi Michael,
Here's slist.3.
I applied to this page all of the fixes you applied to list.3. Also I noticed some unsorted macros,
so I'll check list.3 and sort them if necessary.
Cheers,
Alex
Alejandro Colomar (10):
slist.3: New page that will hold the (slist) contents of queue.3 queue.3, slist.3: NAME: Move code from queue.3 to slist.3 queue.3, slist.3: SYNOPSIS: Move code from queue.3 to list.3 queue.3, slist.3: DESCRIPTION: Move slist specific code from queue.3
to slist.3
queue.3, slist.3: EXAMPLES: Move example program from queue.3 to
slist.3
slist.3: Copy and adapt code from queue.3
slist.3: ffix: Use man markup
slist.3: Add details
SLIST_EMPTY.3, SLIST_ENTRY.3, SLIST_FIRST.3, SLIST_FOREACH.3,
SLIST_HEAD.3, SLIST_HEAD_INITIALIZER.3, SLIST_INIT.3, SLIST_INSERT_AFTER.3, SLIST_INSERT_HEAD.3, SLIST_NEXT.3, SLIST_REMOVE.3, SLIST_REMOVE_HEAD.3: Link to the new slist(3) page instead of queue(3)
queue.3: SEE ALSO: Add slist(3)
man3/SLIST_EMPTY.3 | 2 +- man3/SLIST_ENTRY.3 | 2 +- man3/SLIST_FIRST.3 | 2 +- man3/SLIST_FOREACH.3 | 2 +- man3/SLIST_HEAD.3 | 2 +- man3/SLIST_HEAD_INITIALIZER.3 | 2 +- man3/SLIST_INIT.3 | 2 +- man3/SLIST_INSERT_AFTER.3 | 2 +- man3/SLIST_INSERT_HEAD.3 | 2 +- man3/SLIST_NEXT.3 | 2 +- man3/SLIST_REMOVE.3 | 2 +- man3/SLIST_REMOVE_HEAD.3 | 2 +- man3/queue.3 | 248 +----------------------- man3/slist.3 | 355 ++++++++++++++++++++++++++++++++++ 14 files changed, 368 insertions(+), 259 deletions(-) create mode 100644 man3/slist.3
Signature · 1 line
2.28.0
PATCH 1/10 slist.3: New page that will hold the (slist) contents of queue.3
--- man3/slist.3 | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) create mode 100644 man3/slist.3
man3/slist.3 new file +40 -0
@@ -0,0 +1,40 @@ +.\" Copyright (c) 1993 +.\" The Regents of the University of California. All rights reserved. +.\" and Copyright (c) 2020 by Alejandro Colomar <[email protected]> +.\" +.\" %%%LICENSE_START(BSD_3_CLAUSE_UCB) +.\" 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. +.\" %%%LICENSE_END +.\" +.\" +.TH SLIST 3 2020-10-21 "GNU" "Linux Programmer's Manual" +.SH NAME +.SH SYNOPSIS +.SH DESCRIPTION +.SH RETURN VALUE +.SH CONFORMING TO +.SH BUGS +.SH EXAMPLES +.SH SEE ALSO
Signature · 1 line
2.28.0
PATCH 2/10 queue.3, slist.3: NAME: Move code from queue.3 to slist.3
In reply to Alejandro Colomar--- man3/queue.3 | 17 ----------------- man3/slist.3 | 17 +++++++++++++++++ 2 files changed, 17 insertions(+), 17 deletions(-)
man3/queue.3 +0 -17
@@ -34,23 +34,6 @@ .Dt QUEUE 3 .Os .Sh NAME -.Nm SLIST_EMPTY , -.Nm SLIST_ENTRY , -.Nm SLIST_FIRST , -.Nm SLIST_FOREACH , -.\" .Nm SLIST_FOREACH_FROM , -.\" .Nm SLIST_FOREACH_SAFE , -.\" .Nm SLIST_FOREACH_FROM_SAFE , -.Nm SLIST_HEAD , -.Nm SLIST_HEAD_INITIALIZER , -.Nm SLIST_INIT , -.Nm SLIST_INSERT_AFTER , -.Nm SLIST_INSERT_HEAD , -.Nm SLIST_NEXT , -.\" .Nm SLIST_REMOVE_AFTER , -.Nm SLIST_REMOVE_HEAD , -.Nm SLIST_REMOVE , -.\" .Nm SLIST_SWAP , .Nm STAILQ_CONCAT , .Nm STAILQ_EMPTY , .Nm STAILQ_ENTRY ,
man3/slist.3 +17 -0
@@ -31,6 +31,23 @@ .\" .TH SLIST 3 2020-10-21 "GNU" "Linux Programmer's Manual" .SH NAME +.Nm SLIST_EMPTY , +.Nm SLIST_ENTRY , +.Nm SLIST_FIRST , +.Nm SLIST_FOREACH , +.\" .Nm SLIST_FOREACH_FROM , +.\" .Nm SLIST_FOREACH_SAFE , +.\" .Nm SLIST_FOREACH_FROM_SAFE , +.Nm SLIST_HEAD , +.Nm SLIST_HEAD_INITIALIZER , +.Nm SLIST_INIT , +.Nm SLIST_INSERT_AFTER , +.Nm SLIST_INSERT_HEAD , +.Nm SLIST_NEXT , +.\" .Nm SLIST_REMOVE_AFTER , +.Nm SLIST_REMOVE_HEAD , +.Nm SLIST_REMOVE , +.\" .Nm SLIST_SWAP , .SH SYNOPSIS .SH DESCRIPTION .SH RETURN VALUE
Signature · 1 line
2.28.0
PATCH 3/10 queue.3, slist.3: SYNOPSIS: Move code from queue.3 to list.3
In reply to Alejandro Colomar--- man3/queue.3 | 18 ------------------ man3/slist.3 | 18 ++++++++++++++++++ 2 files changed, 18 insertions(+), 18 deletions(-)
man3/queue.3 +0 -18
@@ -101,24 +101,6 @@ lists, tail queues, and circular queues .Sh SYNOPSIS .In sys/queue.h .\" -.Fn SLIST_EMPTY "SLIST_HEAD *head" -.Fn SLIST_ENTRY "TYPE" -.Fn SLIST_FIRST "SLIST_HEAD *head" -.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.\" .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.\" .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" -.\" .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" -.Fn SLIST_HEAD "HEADNAME" "TYPE" -.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" -.Fn SLIST_INIT "SLIST_HEAD *head" -.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" -.\" .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" -.\" .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME" -.\" .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" .Fn STAILQ_EMPTY "STAILQ_HEAD *head" .Fn STAILQ_ENTRY "TYPE"
man3/slist.3 +18 -0
@@ -49,6 +49,24 @@ .Nm SLIST_REMOVE , .\" .Nm SLIST_SWAP , .SH SYNOPSIS +.Fn SLIST_EMPTY "SLIST_HEAD *head" +.Fn SLIST_ENTRY "TYPE" +.Fn SLIST_FIRST "SLIST_HEAD *head" +.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" +.\" .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" +.\" .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" +.\" .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" +.Fn SLIST_HEAD "HEADNAME" "TYPE" +.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" +.Fn SLIST_INIT "SLIST_HEAD *head" +.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" +.\" .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" +.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" +.\" .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME" +.\" .SH DESCRIPTION .SH RETURN VALUE .SH CONFORMING TO
Signature · 1 line
2.28.0
PATCH 4/10 queue.3, slist.3: DESCRIPTION: Move slist specific code from queue.3 to slist.3
In reply to Alejandro Colomar--- man3/queue.3 | 155 --------------------------------------------------- man3/slist.3 | 155 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 155 insertions(+), 155 deletions(-)
man3/queue.3 +0 -155
@@ -322,161 +322,6 @@ or .Li CIRCLEQ_HEAD . See the examples below for further explanation of how these macros are used. -.Ss Singly-linked lists -A singly-linked list is headed by a structure defined by the -.Nm 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 -.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 -.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 macro -.Nm SLIST_HEAD_INITIALIZER -evaluates to an initializer for the list -.Fa head . -.Pp -The macro -.Nm SLIST_EMPTY -evaluates to true if there are no elements in the list. -.Pp -The macro -.Nm SLIST_ENTRY -declares a structure that connects the elements in -the list. -.Pp -The macro -.Nm SLIST_FIRST -returns the first element in the list or NULL if the list is empty. -.Pp -The macro -.Nm SLIST_FOREACH -traverses the list referenced by -.Fa head -in the forward direction, assigning each element in -turn to -.Fa var . -.\" .Pp -.\" The macro -.\" .Nm SLIST_FOREACH_FROM -.\" behaves identically to -.\" .Nm SLIST_FOREACH -.\" when -.\" .Fa var -.\" is NULL, else it treats -.\" .Fa var -.\" as a previously found SLIST element and begins the loop at -.\" .Fa var -.\" instead of the first element in the SLIST referenced by -.\" .Fa head . -.\" .Pp -.\" The macro -.\" .Nm SLIST_FOREACH_SAFE -.\" traverses the list referenced by -.\" .Fa head -.\" in the forward direction, assigning each element in -.\" turn to -.\" .Fa var . -.\" However, unlike -.\" .Fn SLIST_FOREACH -.\" here it is permitted to both remove -.\" .Fa var -.\" as well as free it from within the loop safely without interfering with the -.\" traversal. -.\" .Pp -.\" The macro -.\" .Nm SLIST_FOREACH_FROM_SAFE -.\" behaves identically to -.\" .Nm SLIST_FOREACH_SAFE -.\" when -.\" .Fa var -.\" is NULL, else it treats -.\" .Fa var -.\" as a previously found SLIST element and begins the loop at -.\" .Fa var -.\" instead of the first element in the SLIST referenced by -.\" .Fa head . -.Pp -The macro -.Nm SLIST_INIT -initializes the list referenced by -.Fa head . -.Pp -The macro -.Nm SLIST_INSERT_HEAD -inserts the new element -.Fa elm -at the head of the list. -.Pp -The macro -.Nm SLIST_INSERT_AFTER -inserts the new element -.Fa elm -after the element -.Fa listelm . -.Pp -The macro -.Nm SLIST_NEXT -returns the next element in the list. -.\" .Pp -.\" The macro -.\" .Nm SLIST_REMOVE_AFTER -.\" removes the element after -.\" .Fa elm -.\" from the list. -.\" Unlike -.\" .Fa SLIST_REMOVE , -.\" this macro does not traverse the entire list. -.Pp -The macro -.Nm SLIST_REMOVE_HEAD -removes the element -.Fa 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 -.Fa SLIST_REMOVE -macro. -.Pp -The macro -.Nm SLIST_REMOVE -removes the element -.Fa elm -from the list. -.\" .Pp -.\" The macro -.\" .Nm SLIST_SWAP -.\" swaps the contents of -.\" .Fa head1 -.\" and -.\" .Fa head2 . -.Pp -See the EXAMPLES section below for an example program using a singly-linked list. .Ss Singly-linked tail queues A singly-linked tail queue is headed by a structure defined by the .Nm STAILQ_HEAD
man3/slist.3 +155 -0
161 lines not on this page · raw message
Signature · 1 line
2.28.0
PATCH 5/10 queue.3, slist.3: EXAMPLES: Move example program from queue.3 to slist.3
In reply to Alejandro Colomar--- man3/queue.3 | 57 ---------------------------------------------------- man3/slist.3 | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 57 insertions(+), 57 deletions(-)
man3/queue.3 +0 -57
@@ -847,63 +847,6 @@ removes the element .Fa elm from the circular queue. .Sh EXAMPLES -.Ss Singly-linked list example -.Bd -literal - -#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 (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); -} -.Ed .Ss Singly-linked tail queue example .Bd -literal #include <stddef.h>
man3/slist.3 +57 -0
61 lines not on this page · raw message
Signature · 1 line
2.28.0
PATCH 6/10 slist.3: Copy and adapt code from queue.3
In reply to Alejandro ColomarA few fixes to note:
- Sorted alphabetically some macros
- ffix: remove alignment spaces in example (as in list.3)
--- man3/slist.3 | 30 +++++++++++++++++++++++------- 1 file changed, 23 insertions(+), 7 deletions(-)
man3/slist.3 +23 -7
@@ -36,38 +36,52 @@ .Nm SLIST_FIRST , .Nm SLIST_FOREACH , .\" .Nm SLIST_FOREACH_FROM , -.\" .Nm SLIST_FOREACH_SAFE , .\" .Nm SLIST_FOREACH_FROM_SAFE , +.\" .Nm SLIST_FOREACH_SAFE , .Nm SLIST_HEAD , .Nm SLIST_HEAD_INITIALIZER , .Nm SLIST_INIT , .Nm SLIST_INSERT_AFTER , .Nm SLIST_INSERT_HEAD , .Nm SLIST_NEXT , +.Nm SLIST_REMOVE , .\" .Nm SLIST_REMOVE_AFTER , .Nm SLIST_REMOVE_HEAD , -.Nm SLIST_REMOVE , .\" .Nm SLIST_SWAP , .SH SYNOPSIS +.In sys/queue.h +.\" .Fn SLIST_EMPTY "SLIST_HEAD *head" .Fn SLIST_ENTRY "TYPE" .Fn SLIST_FIRST "SLIST_HEAD *head" .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" .\" .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.\" .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" .\" .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" +.\" .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" .Fn SLIST_HEAD "HEADNAME" "TYPE" .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" .Fn SLIST_INIT "SLIST_HEAD *head" .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" .\" .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" .\" .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME" .\" .SH DESCRIPTION +In the macro definitions, +.Fa TYPE +is the name of a user-defined structure, +that must contain a field of type +.Li SLIST_ENTRY , +named +.Fa NAME . +The argument +.Fa HEADNAME +is the name of a user defined structure that must be declared +using the macro +.Li SLIST_HEAD . .Ss Singly-linked lists A singly-linked list is headed by a structure defined by the .Nm SLIST_HEAD
@@ -221,10 +235,12 @@ from the list. .\" .Fa head1 .\" and .\" .Fa head2 . -.Pp -See the EXAMPLES section below for an example program using a singly-linked list. .SH RETURN VALUE .SH CONFORMING TO +Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. +Present on the BSDs +(SLIST macros first appeared in +.Bx 4.4 ). .SH BUGS .SH EXAMPLES .Ss Singly-linked list example
@@ -245,7 +261,7 @@ SLIST_HEAD(slisthead, entry); int main(void) { - struct entry *n1, *n2, *n3, *np; + struct entry *n1, *n2, *n3, *np; struct slisthead head; /* Singly-linked List head. */
Signature · 1 line
2.28.0
PATCH 7/10 slist.3: ffix: Use man markup
In reply to Alejandro Colomar--- man3/slist.3 | 260 +++++++++++++++++++++++++++------------------------ 1 file changed, 140 insertions(+), 120 deletions(-)
man3/slist.3 +140 -120
@@ -31,60 +31,77 @@ .\" .TH SLIST 3 2020-10-21 "GNU" "Linux Programmer's Manual" .SH NAME -.Nm SLIST_EMPTY , -.Nm SLIST_ENTRY , -.Nm SLIST_FIRST , -.Nm SLIST_FOREACH , -.\" .Nm SLIST_FOREACH_FROM , -.\" .Nm SLIST_FOREACH_FROM_SAFE , -.\" .Nm SLIST_FOREACH_SAFE , -.Nm SLIST_HEAD , -.Nm SLIST_HEAD_INITIALIZER , -.Nm SLIST_INIT , -.Nm SLIST_INSERT_AFTER , -.Nm SLIST_INSERT_HEAD , -.Nm SLIST_NEXT , -.Nm SLIST_REMOVE , -.\" .Nm SLIST_REMOVE_AFTER , -.Nm SLIST_REMOVE_HEAD , -.\" .Nm SLIST_SWAP , +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 .SH SYNOPSIS -.In sys/queue.h -.\" -.Fn SLIST_EMPTY "SLIST_HEAD *head" -.Fn SLIST_ENTRY "TYPE" -.Fn SLIST_FIRST "SLIST_HEAD *head" -.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.\" .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.\" .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" -.\" .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" -.Fn SLIST_HEAD "HEADNAME" "TYPE" -.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" -.Fn SLIST_INIT "SLIST_HEAD *head" -.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" -.\" .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.\" .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME" -.\" +.nf +.B #include <sys/queue.h> +.PP +.BI "int SLIST_EMPTY(SLIST_HEAD *" head ");" +.PP +.B SLIST_ENTRY(TYPE); +.PP +.BI "SLIST_ENTRY *SLIST_FIRST(SLIST_HEAD *" head ");" +.PP +.BI "SLIST_FOREACH(TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME ");" +.\".PP +.\".BI "SLIST_FOREACH_FROM(TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME ");" +.\".PP +.\".BI "SLIST_FOREACH_FROM_SAFE(TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME ", TYPE *" temp_var ");" +.\".PP +.\".BI "SLIST_FOREACH_SAFE(TYPE *" var ", SLIST_HEAD *" head ", SLIST_ENTRY " NAME ", TYPE *" temp_var ");" +.PP +.B SLIST_HEAD(HEADNAME, TYPE); +.PP +.BI "SLIST_HEAD SLIST_HEAD_INITIALIZER(SLIST_HEAD " head ");" +.PP +.BI "void SLIST_INIT(SLIST_HEAD *" head ");" +.PP +.BI "void SLIST_INSERT_AFTER(TYPE *" listelm ", TYPE *" elm ", SLIST_ENTRY " NAME ");" +.PP +.BI "void SLIST_INSERT_HEAD(SLIST_HEAD *" head ", TYPE *" elm ", SLIST_ENTRY " NAME ");" +.PP +.BI "SLIST_ENTRY *SLIST_NEXT(TYPE *" elm ", SLIST_ENTRY " NAME ");" +.PP +.BI "void SLIST_REMOVE(SLIST_HEAD *" head ", TYPE *" elm ", SLIST_ENTRY " NAME ");" +.\".PP +.\".BI "void SLIST_REMOVE_AFTER(TYPE *" elm ", SLIST_ENTRY " NAME ");" +.PP +.BI "void SLIST_REMOVE_HEAD(SLIST_HEAD *" head ", SLIST_ENTRY " NAME ");" +.\".PP +.\".BI "void SLIST_SWAP(SLIST_HEAD *" head1 ", SLIST_HEAD *" head2 ", SLIST_ENTRY " NAME ");" +.fi .SH DESCRIPTION In the macro definitions, -.Fa TYPE +.I TYPE is the name of a user-defined structure, that must contain a field of type -.Li SLIST_ENTRY , +.IR SLIST_ENTRY , named -.Fa NAME . +.IR NAME . The argument -.Fa HEADNAME +.IR HEADNAME is the name of a user defined structure that must be declared using the macro -.Li SLIST_HEAD . -.Ss Singly-linked lists +.BR SLIST_HEAD (). +.PP A singly-linked list is headed by a structure defined by the -.Nm SLIST_HEAD +.BR SLIST_HEAD () macro. This structure contains a single pointer to the first element on the list.
@@ -93,159 +110,162 @@ 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 -.Fa SLIST_HEAD +.I SLIST_HEAD structure is declared as follows: -.Bd -literal -offset indent +.PP +.in +4 +.EX SLIST_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp +.EE +.in +.PP where -.Fa HEADNAME +.I HEADNAME is the name of the structure to be defined, and -.Fa TYPE +.I 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 +.PP +.in +4 +.EX struct HEADNAME *headp; -.Ed -.Pp +.EE +.in +.PP (The names -.Li head +.I head and -.Li headp +.I headp are user selectable.) -.Pp +.PP The macro -.Nm SLIST_HEAD_INITIALIZER +.BR SLIST_HEAD_INITIALIZER () evaluates to an initializer for the list -.Fa head . -.Pp +.IR head . +.PP The macro -.Nm SLIST_EMPTY +.BR SLIST_EMPTY () evaluates to true if there are no elements in the list. -.Pp +.PP The macro -.Nm SLIST_ENTRY +.BR SLIST_ENTRY () declares a structure that connects the elements in the list. -.Pp +.PP The macro -.Nm SLIST_FIRST +.BR SLIST_FIRST () returns the first element in the list or NULL if the list is empty. -.Pp +.PP The macro -.Nm SLIST_FOREACH +.BR SLIST_FOREACH () traverses the list referenced by -.Fa head +.I head in the forward direction, assigning each element in turn to -.Fa var . -.\" .Pp +.IR var . +.\" .PP .\" The macro -.\" .Nm SLIST_FOREACH_FROM +.\" .BR SLIST_FOREACH_FROM () .\" behaves identically to -.\" .Nm SLIST_FOREACH +.\" .BR SLIST_FOREACH () .\" when -.\" .Fa var +.\" .I var .\" is NULL, else it treats -.\" .Fa var +.\" .I var .\" as a previously found SLIST element and begins the loop at -.\" .Fa var +.\" .I var .\" instead of the first element in the SLIST referenced by -.\" .Fa head . +.\" .IR head . .\" .Pp .\" The macro -.\" .Nm SLIST_FOREACH_SAFE +.\" .BR SLIST_FOREACH_SAFE () .\" traverses the list referenced by -.\" .Fa head +.\" .I head .\" in the forward direction, assigning each element in .\" turn to -.\" .Fa var . +.\" .IR var . .\" However, unlike -.\" .Fn SLIST_FOREACH +.\" .BR SLIST_FOREACH () .\" here it is permitted to both remove -.\" .Fa var +.\" .I var .\" as well as free it from within the loop safely without interfering with the .\" traversal. -.\" .Pp +.\" .PP .\" The macro -.\" .Nm SLIST_FOREACH_FROM_SAFE +.\" .BR SLIST_FOREACH_FROM_SAFE () .\" behaves identically to -.\" .Nm SLIST_FOREACH_SAFE +.\" .BR SLIST_FOREACH_SAFE () .\" when -.\" .Fa var +.\" .I var .\" is NULL, else it treats -.\" .Fa var +.\" .I var .\" as a previously found SLIST element and begins the loop at -.\" .Fa var +.\" .I var .\" instead of the first element in the SLIST referenced by -.\" .Fa head . -.Pp +.\" .IR head . +.PP The macro -.Nm SLIST_INIT +.BR SLIST_INIT () initializes the list referenced by -.Fa head . -.Pp +.IR head . +.PP The macro -.Nm SLIST_INSERT_HEAD +.BR SLIST_INSERT_HEAD () inserts the new element -.Fa elm +.I elm at the head of the list. -.Pp +.PP The macro -.Nm SLIST_INSERT_AFTER +.BR SLIST_INSERT_AFTER () inserts the new element -.Fa elm +.I elm after the element -.Fa listelm . -.Pp +.IR listelm . +.PP The macro -.Nm SLIST_NEXT +.BR SLIST_NEXT () returns the next element in the list. -.\" .Pp +.\" .PP .\" The macro -.\" .Nm SLIST_REMOVE_AFTER +.\" .BR SLIST_REMOVE_AFTER () .\" removes the element after -.\" .Fa elm +.\" .I elm .\" from the list. .\" Unlike -.\" .Fa SLIST_REMOVE , +.\" .IR SLIST_REMOVE , .\" this macro does not traverse the entire list. -.Pp +.PP The macro -.Nm SLIST_REMOVE_HEAD +.BR SLIST_REMOVE_HEAD () removes the element -.Fa elm +.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 -.Fa SLIST_REMOVE +.I SLIST_REMOVE macro. -.Pp +.PP The macro -.Nm SLIST_REMOVE +.BR SLIST_REMOVE () removes the element -.Fa elm +.I elm from the list. -.\" .Pp +.\" .PP .\" The macro -.\" .Nm SLIST_SWAP +.\" .BR SLIST_SWAP () .\" swaps the contents of -.\" .Fa head1 +.\" .I head1 .\" and -.\" .Fa head2 . +.\" .IR head2 . .SH RETURN VALUE .SH CONFORMING TO Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. Present on the BSDs -(SLIST macros first appeared in -.Bx 4.4 ). +(SLIST macros first appeared in 4.4BSD). .SH BUGS .SH EXAMPLES -.Ss Singly-linked list example -.Bd -literal - +.EX #include <stddef.h> #include <stdio.h> #include <stdlib.h>
@@ -299,5 +319,5 @@ main(void) exit(EXIT_SUCCESS); } -.Ed +.EE .SH SEE ALSO
Signature · 1 line
2.28.0
PATCH 8/10 slist.3: Add details
In reply to Alejandro ColomarAdd remaining details to complete the page.
--- man3/slist.3 | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)
man3/slist.3 +32 -0
@@ -48,6 +48,7 @@ SLIST_REMOVE, .\"SLIST_REMOVE_AFTER, SLIST_REMOVE_HEAD .\"SLIST_SWAP +\- implementation of a singly-linked list .SH SYNOPSIS .nf .B #include <sys/queue.h>
@@ -87,6 +88,8 @@ SLIST_REMOVE_HEAD .\".BI "void SLIST_SWAP(SLIST_HEAD *" head1 ", SLIST_HEAD *" head2 ", 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,
@@ -259,11 +262,38 @@ from the list. .\" and .\" .IR head2 . .SH RETURN VALUE +.BR SLIST_EMPTY () +returns non-zero 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 SLIST_ENTRY +structure, respectively. +.PP +.BR SLIST_HEAD_INITIALIZER () +returns an initializer that can be assigned to the list +.IR head . .SH CONFORMING TO Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. Present on the BSDs (SLIST macros first appeared in 4.4BSD). .SH BUGS +The macro +.BR SLIST_FOREACH () +doesn't allow +.I var +to be removed or freed within the loop, +as it would interfere with the traversal. +The macro +.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 .EX #include <stddef.h>
@@ -321,3 +351,5 @@ main(void) } .EE .SH SEE ALSO +.BR insque (3), +.BR queue (3)
Signature · 1 line
2.28.0
PATCH 9/10 SLIST_EMPTY.3, SLIST_ENTRY.3, SLIST_FIRST.3, SLIST_FOREACH.3, SLIST_HEAD.3, SLIST_HEAD_INITIALIZER.3, SLIST_INIT.3, SLIST_INSERT_AFTER.3, SLIST_INSERT_HEAD.3, SLIST_NEXT.3, SLIST_REMOVE.3, SLIST_REMOVE_HEAD.3: Link to the new slist(3) page instead of queue(3)
In reply to Alejandro Colomar--- man3/SLIST_EMPTY.3 | 2 +- man3/SLIST_ENTRY.3 | 2 +- man3/SLIST_FIRST.3 | 2 +- man3/SLIST_FOREACH.3 | 2 +- man3/SLIST_HEAD.3 | 2 +- man3/SLIST_HEAD_INITIALIZER.3 | 2 +- man3/SLIST_INIT.3 | 2 +- man3/SLIST_INSERT_AFTER.3 | 2 +- man3/SLIST_INSERT_HEAD.3 | 2 +- man3/SLIST_NEXT.3 | 2 +- man3/SLIST_REMOVE.3 | 2 +- man3/SLIST_REMOVE_HEAD.3 | 2 +- 12 files changed, 12 insertions(+), 12 deletions(-)
man3/SLIST_EMPTY.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_ENTRY.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_FIRST.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_FOREACH.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_HEAD.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_HEAD_INITIALIZER.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_INIT.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_INSERT_AFTER.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_INSERT_HEAD.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_NEXT.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_REMOVE.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
man3/SLIST_REMOVE_HEAD.3 +1 -1
@@ -1 +1 @@ -.so man3/queue.3 +.so man3/slist.3
Signature · 1 line
2.28.0
PATCH 10/10 queue.3: SEE ALSO: Add slist(3)
In reply to Alejandro Colomar--- man3/queue.3 | 1 + 1 file changed, 1 insertion(+)
man3/queue.3 +1 -0
@@ -1029,4 +1029,5 @@ functions first appeared in .Sh SEE ALSO .Xr insque 3 .Xr list 3 +.Xr slist 3 .\" .Xr tree 3
Signature · 1 line
2.28.0
Hi Alex,
Quoted 7 lines · Alejandro Colomar
Hi Michael,
Here's slist.3.
I applied to this page all of the fixes you applied to list.3. Also I noticed some unsorted macros,
so I'll check list.3 and sort them if necessary.
Thanks! I've applied this series.
Cheers,
Michael
Quoted 35 lines
Alejandro Colomar (10):
slist.3: New page that will hold the (slist) contents of queue.3 queue.3, slist.3: NAME: Move code from queue.3 to slist.3 queue.3, slist.3: SYNOPSIS: Move code from queue.3 to list.3 queue.3, slist.3: DESCRIPTION: Move slist specific code from queue.3
to slist.3
queue.3, slist.3: EXAMPLES: Move example program from queue.3 toslist.3slist.3: Copy and adapt code from queue.3
slist.3: ffix: Use man markup
slist.3: Add details
SLIST_EMPTY.3, SLIST_ENTRY.3, SLIST_FIRST.3, SLIST_FOREACH.3,
SLIST_HEAD.3, SLIST_HEAD_INITIALIZER.3, SLIST_INIT.3, SLIST_INSERT_AFTER.3, SLIST_INSERT_HEAD.3, SLIST_NEXT.3, SLIST_REMOVE.3, SLIST_REMOVE_HEAD.3: Link to the new slist(3) page instead of queue(3)
queue.3: SEE ALSO: Add slist(3)man3/SLIST_EMPTY.3 | 2 +- man3/SLIST_ENTRY.3 | 2 +- man3/SLIST_FIRST.3 | 2 +- man3/SLIST_FOREACH.3 | 2 +- man3/SLIST_HEAD.3 | 2 +- man3/SLIST_HEAD_INITIALIZER.3 | 2 +- man3/SLIST_INIT.3 | 2 +- man3/SLIST_INSERT_AFTER.3 | 2 +- man3/SLIST_INSERT_HEAD.3 | 2 +- man3/SLIST_NEXT.3 | 2 +- man3/SLIST_REMOVE.3 | 2 +- man3/SLIST_REMOVE_HEAD.3 | 2 +- man3/queue.3 | 248 +----------------------- man3/slist.3 | 355 ++++++++++++++++++++++++++++++++++ 14 files changed, 368 insertions(+), 259 deletions(-) create mode 100644 man3/slist.3
Signature · 3 lines
Michael Kerrisk Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/ Linux/UNIX System Programming Training: http://man7.org/training/