queue.3: Add self to copyright notice
PATCH 1/2 queue.3: Add self to copyright notice
---
Hi Michael,
After these 2 patches, I think I'll only add one more patch to all of the pages improving a bit the SYNOPSIS (taking a good idea from OpenBSD's queue(3)).
I guess you're about to release, so please wait for that one :) I'll have it in a few minutes, anyway :p
Cheers,
Alex
man3/queue.3 | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
man3/queue.3 +2 -1
@@ -1,5 +1,6 @@ .\" Copyright (c) 1993 -.\" The Regents of the University of California. All rights reserved. +.\" 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
Signature · 1 line
2.28.0
PATCH 2/2 queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3
- ffix: Use man markup
- Remove specific notes about code size increase and execution time increase,
as they were (at least) inaccurate. Instead, a generic note has been added.
- Structure the text into subsections.
- Remove sections that were empty after the forks.
- Clearly relate macro names (SLIST, TAILQ, ...) to a human readable name of which data structure they implement.
--- man3/queue.3 | 189 ++++++++++++++++++++------------------------------- 1 file changed, 75 insertions(+), 114 deletions(-)
man3/queue.3 +75 -114
@@ -28,160 +28,121 @@ .\" SUCH DAMAGE. .\" %%%LICENSE_END .\" -.\" @(#)queue.3 8.2 (Berkeley) 1/24/94 -.\" $FreeBSD$ .\" -.Dd February 7, 2015 -.Dt QUEUE 3 -.Os -.Sh NAME -.Nd implementations of singly-linked lists, singly-linked tail queues, -lists, tail queues, and circular queues -.Sh SYNOPSIS -.Sh DESCRIPTION -These macros define and operate on five types of data structures: -singly-linked lists, singly-linked tail queues, lists, tail queues, and -circular queues. -All five structures support the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.TH QUEUE 3 2015-02-7 "GNU" "Linux Programmer's Manual" +.SH NAME +queue \- implementations of linked lists and queues +.SH DESCRIPTION +The +.I <sys/queue.h> +header file provides a set of macros that +define and operate on the following data structures: +.IP * 3 +singly-linked lists (SLIST) +.IP * +doubly-linked lists (LIST) +.IP * +singly-linked tail queues (STAILQ) +.IP * +doubly-linked tail queues (TAILQ) +.IP * +doubly-linked circular queues (CIRCLEQ) +.PP +All structures support the following functionality: +.IP * 3 Insertion of a new entry at the head of the list. -.It +.IP * Insertion of a new entry after any element in the list. -.It +.IP * O(1) removal of an entry from the head of the list. -.It +.IP * Forward traversal through the list. -.\" .It +.\".IP * .\" Swapping the contents of two lists. -.El -.Pp -Singly-linked lists are the simplest of the four data structures +.PP +Code size and execution time +depend on the complexity of the data structure being used, +so programmers should take care of choosing the appropriate one. +.SS Singly-linked lists (SLIST) +Singly-linked lists are the simplest and support only the above functionality. -Singly-linked lists are ideal for applications with large datasets -and few or no removals, +Singly-linked lists are ideal for applications with +large datasets and few or no removals, or for implementing a LIFO queue. Singly-linked lists add the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 O(n) removal of any entry in the list. -.El -.Pp +.SS Singly-linked tail queues (STAILQ) Singly-linked tail queues add the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 Entries can be added at the end of a list. -.It +.IP * O(n) removal of any entry in the list. -.It +.IP * They may be concatenated. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 All list insertions must specify the head of the list. -.It +.IP * 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 -Singly-linked tail queues are ideal for applications with large datasets and -few or no removals, +.PP +Singly-linked tail queues are ideal for applications with +large datasets and few or no removals, or for implementing a FIFO queue. -.Pp +.SS Doubly-linked data structures All doubly linked types of data structures (lists and tail queues) additionally allow: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 Insertion of a new entry before any element in the list. -.It +.IP * O(1) removal of any entry in the list. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 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 +.SS Doubly-linked lists (LIST) Linked lists are the simplest of the doubly linked data structures. They add the following functionality over the above: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 They may be traversed backwards. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 To traverse backwards, an entry to begin the traversal and the list in which it is contained must be specified. -.El -.Pp +.SS Doubly-linked tail queues (TAILQ) Tail queues add the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 Entries can be added at the end of a list. -.It +.IP * They may be traversed backwards, from tail to head. -.It +.IP * They may be concatenated. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 All list insertions and removals must specify the head of the list. -.It +.IP * 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 +.SS Doubly-linked circular queues (CIRCLEQ) Circular queues add the following functionality over the above: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 The first and last entries are connected. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 The termination condition for traversal is more complex. -.It -Code size is about 40% greater and operations run about 45% slower than lists. -.El -.Sh EXAMPLES -.Sh CONFORMING TO +.SH CONFORMING TO Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. Present on the BSDs. -.Nm queue -functions first appeared in -.Bx 4.4 . -.Sh SEE ALSO -.Xr circleq 3 -.Xr insque 3 -.Xr list 3 -.Xr slist 3 -.Xr stailq 3 -.Xr tailq 3 -.\" .Xr tree 3 +.I <sys/queue.h> +macros first appeared in 4.4BSD. +.SH SEE ALSO +.BR circleq (3), +.BR insque (3), +.BR list (3), +.BR slist (3), +.BR stailq (3), +.BR tailq (3) +.\" .BR tree (3)
Signature · 1 line
2.28.0
Michael Kerrisk (man-pages)
AppliedRe: [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3
Hi Alex,
Quoted 11 lines · Alejandro Colomar
- ffix: Use man markup
- Remove specific notes about code size increase and execution time increase,
as they were (at least) inaccurate. Instead, a generic note has been added.
- Structure the text into subsections.
- Remove sections that were empty after the forks.
- Clearly relate macro names (SLIST, TAILQ, ...) to a human readable name of which data structure they implement.
Good clean-up! Thanks!
Applied.
Cheers,
Michael
Quoted 249 lines
Reported-by Michael Kerrisk <[email protected]>Signed-off-by Alejandro Colomar <[email protected]>--- man3/queue.3 | 189 ++++++++++++++++++++------------------------------- 1 file changed, 75 insertions(+), 114 deletions(-)man3/queue.3 +75
-115@@ -28,160 +28,121 @@ .\" SUCH DAMAGE. .\" %%%LICENSE_END .\" -.\" @(#)queue.3 8.2 (Berkeley) 1/24/94 -.\" $FreeBSD$ .\" -.Dd February 7, 2015 -.Dt QUEUE 3 -.Os -.Sh NAME -.Nd implementations of singly-linked lists, singly-linked tail queues, -lists, tail queues, and circular queues -.Sh SYNOPSIS -.Sh DESCRIPTION -These macros define and operate on five types of data structures: -singly-linked lists, singly-linked tail queues, lists, tail queues, and -circular queues. -All five structures support the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.TH QUEUE 3 2015-02-7 "GNU" "Linux Programmer's Manual" +.SH NAME +queue \- implementations of linked lists and queues +.SH DESCRIPTION +The +.I <sys/queue.h> +header file provides a set of macros that +define and operate on the following data structures: +.IP * 3 +singly-linked lists (SLIST) +.IP * +doubly-linked lists (LIST) +.IP * +singly-linked tail queues (STAILQ) +.IP * +doubly-linked tail queues (TAILQ) +.IP * +doubly-linked circular queues (CIRCLEQ) +.PP +All structures support the following functionality: +.IP * 3 Insertion of a new entry at the head of the list. -.It +.IP * Insertion of a new entry after any element in the list. -.It +.IP * O(1) removal of an entry from the head of the list. -.It +.IP * Forward traversal through the list. -.\" .It +.\".IP * .\" Swapping the contents of two lists. -.El -.Pp -Singly-linked lists are the simplest of the four data structures +.PP +Code size and execution time +depend on the complexity of the data structure being used, +so programmers should take care of choosing the appropriate one. +.SS Singly-linked lists (SLIST) +Singly-linked lists are the simplest and support only the above functionality. -Singly-linked lists are ideal for applications with large datasets -and few or no removals, +Singly-linked lists are ideal for applications with +large datasets and few or no removals, or for implementing a LIFO queue. Singly-linked lists add the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 O(n) removal of any entry in the list. -.El -.Pp +.SS Singly-linked tail queues (STAILQ) Singly-linked tail queues add the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 Entries can be added at the end of a list. -.It +.IP * O(n) removal of any entry in the list. -.It +.IP * They may be concatenated. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 All list insertions must specify the head of the list. -.It +.IP * 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 -Singly-linked tail queues are ideal for applications with large datasets and -few or no removals, +.PP +Singly-linked tail queues are ideal for applications with +large datasets and few or no removals, or for implementing a FIFO queue. -.Pp +.SS Doubly-linked data structures All doubly linked types of data structures (lists and tail queues) additionally allow: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 Insertion of a new entry before any element in the list. -.It +.IP * O(1) removal of any entry in the list. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 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 +.SS Doubly-linked lists (LIST) Linked lists are the simplest of the doubly linked data structures. They add the following functionality over the above: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 They may be traversed backwards. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 To traverse backwards, an entry to begin the traversal and the list in which it is contained must be specified. -.El -.Pp +.SS Doubly-linked tail queues (TAILQ) Tail queues add the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 Entries can be added at the end of a list. -.It +.IP * They may be traversed backwards, from tail to head. -.It +.IP * They may be concatenated. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 All list insertions and removals must specify the head of the list. -.It +.IP * 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 +.SS Doubly-linked circular queues (CIRCLEQ) Circular queues add the following functionality over the above: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 The first and last entries are connected. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 The termination condition for traversal is more complex. -.It -Code size is about 40% greater and operations run about 45% slower than lists. -.El -.Sh EXAMPLES -.Sh CONFORMING TO +.SH CONFORMING TO Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. Present on the BSDs. -.Nm queue -functions first appeared in -.Bx 4.4 . -.Sh SEE ALSO -.Xr circleq 3 -.Xr insque 3 -.Xr list 3 -.Xr slist 3 -.Xr stailq 3 -.Xr tailq 3 -.\" .Xr tree 3 +.I <sys/queue.h> +macros first appeared in 4.4BSD. +.SH SEE ALSO +.BR circleq (3), +.BR insque (3), +.BR list (3), +.BR slist (3), +.BR stailq (3), +.BR tailq (3) +.\" .BR tree (3) --2.28.0
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/
Re: [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3
Quoted 15 lines · Michael Kerrisk (man-pages)
Hi Alex,
Quoted 11 lines · Alejandro Colomar
- ffix: Use man markup
- Remove specific notes about code size increase and execution time increase,
as they were (at least) inaccurate. Instead, a generic note has been added.
- Structure the text into subsections.
- Remove sections that were empty after the forks.
- Clearly relate macro names (SLIST, TAILQ, ...) to a human readable name of which data structure they implement.
Quoted 1 line
Good clean-up! Thanks!
:-)
Thanks,
Alex
Quoted 258 lines
Applied.
Cheers,
Michael
Quoted 249 lines
Reported-by Michael Kerrisk <[email protected]>Signed-off-by Alejandro Colomar <[email protected]>--- man3/queue.3 | 189 ++++++++++++++++++++------------------------------- 1 file changed, 75 insertions(+), 114 deletions(-)man3/queue.3 +75
-115@@ -28,160 +28,121 @@ .\" SUCH DAMAGE. .\" %%%LICENSE_END .\" -.\" @(#)queue.3 8.2 (Berkeley) 1/24/94 -.\" $FreeBSD$ .\" -.Dd February 7, 2015 -.Dt QUEUE 3 -.Os -.Sh NAME -.Nd implementations of singly-linked lists, singly-linked tail queues, -lists, tail queues, and circular queues -.Sh SYNOPSIS -.Sh DESCRIPTION -These macros define and operate on five types of data structures: -singly-linked lists, singly-linked tail queues, lists, tail queues, and -circular queues. -All five structures support the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.TH QUEUE 3 2015-02-7 "GNU" "Linux Programmer's Manual" +.SH NAME +queue \- implementations of linked lists and queues +.SH DESCRIPTION +The +.I <sys/queue.h> +header file provides a set of macros that +define and operate on the following data structures: +.IP * 3 +singly-linked lists (SLIST) +.IP * +doubly-linked lists (LIST) +.IP * +singly-linked tail queues (STAILQ) +.IP * +doubly-linked tail queues (TAILQ) +.IP * +doubly-linked circular queues (CIRCLEQ) +.PP +All structures support the following functionality: +.IP * 3 Insertion of a new entry at the head of the list. -.It +.IP * Insertion of a new entry after any element in the list. -.It +.IP * O(1) removal of an entry from the head of the list. -.It +.IP * Forward traversal through the list. -.\" .It +.\".IP * .\" Swapping the contents of two lists. -.El -.Pp -Singly-linked lists are the simplest of the four data structures +.PP +Code size and execution time +depend on the complexity of the data structure being used, +so programmers should take care of choosing the appropriate one. +.SS Singly-linked lists (SLIST) +Singly-linked lists are the simplest and support only the above functionality. -Singly-linked lists are ideal for applications with large datasets -and few or no removals, +Singly-linked lists are ideal for applications with +large datasets and few or no removals, or for implementing a LIFO queue. Singly-linked lists add the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 O(n) removal of any entry in the list. -.El -.Pp +.SS Singly-linked tail queues (STAILQ) Singly-linked tail queues add the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 Entries can be added at the end of a list. -.It +.IP * O(n) removal of any entry in the list. -.It +.IP * They may be concatenated. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 All list insertions must specify the head of the list. -.It +.IP * 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 -Singly-linked tail queues are ideal for applications with large datasets and -few or no removals, +.PP +Singly-linked tail queues are ideal for applications with +large datasets and few or no removals, or for implementing a FIFO queue. -.Pp +.SS Doubly-linked data structures All doubly linked types of data structures (lists and tail queues) additionally allow: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 Insertion of a new entry before any element in the list. -.It +.IP * O(1) removal of any entry in the list. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 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 +.SS Doubly-linked lists (LIST) Linked lists are the simplest of the doubly linked data structures. They add the following functionality over the above: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 They may be traversed backwards. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 To traverse backwards, an entry to begin the traversal and the list in which it is contained must be specified. -.El -.Pp +.SS Doubly-linked tail queues (TAILQ) Tail queues add the following functionality: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 Entries can be added at the end of a list. -.It +.IP * They may be traversed backwards, from tail to head. -.It +.IP * They may be concatenated. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 All list insertions and removals must specify the head of the list. -.It +.IP * 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 +.SS Doubly-linked circular queues (CIRCLEQ) Circular queues add the following functionality over the above: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 The first and last entries are connected. -.El -.Pp +.PP However: -.Pp -.Bl -enum -compact -offset indent -.It +.IP * 3 The termination condition for traversal is more complex. -.It -Code size is about 40% greater and operations run about 45% slower than lists. -.El -.Sh EXAMPLES -.Sh CONFORMING TO +.SH CONFORMING TO Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. Present on the BSDs. -.Nm queue -functions first appeared in -.Bx 4.4 . -.Sh SEE ALSO -.Xr circleq 3 -.Xr insque 3 -.Xr list 3 -.Xr slist 3 -.Xr stailq 3 -.Xr tailq 3 -.\" .Xr tree 3 +.I <sys/queue.h> +macros first appeared in 4.4BSD. +.SH SEE ALSO +.BR circleq (3), +.BR insque (3), +.BR list (3), +.BR slist (3), +.BR stailq (3), +.BR tailq (3) +.\" .BR tree (3) --2.28.0
Hi Alex,
Quoted 2 lines · Alejandro Colomar
Signed-off-by Alejandro Colomar <[email protected]>
Thanks. Applied.
Quoted 7 lines
---
Hi Michael,
After these 2 patches, I think I'll only add one more patch to all of the pages improving a bit the SYNOPSIS (taking a good idea from OpenBSD's queue(3)).
Thanks for the background.
Quoted 1 line
I guess you're about to release, so please wait for that one :)
Yes, within the next week or so.
Thanks,
Michael
Quoted 24 lines
I'll have it in a few minutes, anyway :p
Cheers,
Alex
man3/queue.3 | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)man3/queue.3 +2
-2@@ -1,5 +1,6 @@ .\" Copyright (c) 1993 -.\" The Regents of the University of California. All rights reserved. +.\" 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 --2.28.0
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/