* [patch] queue.3: Document CIRCLEQ_* macros
@ 2020-08-21 12:59 Alejandro Colomar
2020-08-24 10:36 ` Michael Kerrisk (man-pages)
0 siblings, 1 reply; 2+ messages in thread
From: Alejandro Colomar @ 2020-08-21 12:59 UTC (permalink / raw)
To: Michael Kerrisk (man-pages); +Cc: linux-man, libc-alpha
[-- Attachment #1: Type: text/plain, Size: 9898 bytes --]
===========
DESCRIPTION
===========
Document ``CIRCLEQ_*`` macros, based on old documentation that was
removed by accident in commit ``c0f21a0``, and improved to match the
rest of the documentation in ``queue.3``.
=======
TESTING
=======
I run ``sudo make`` and then visualized the man page with
``man 3 queue``, and the contents looked good.
_______
P.S.: I noticed that ``git format-patch`` leaves a trailing space at
some places:
The line after ``@@ -1220,6 +1274,192 @@ while (n1 != NULL) {``
The line just before the git version (``-- ``).
However, none of those lines are additions to the code, so they
shouldn't affect the result.
Is that ok?
I run ``git format-patch -1 HEAD --stdout > ../circleq.patch``.
P.S. 2: I attached a copy of the patch just in case that the mailer
adds any trailing spaces or any other weird things. Please, tell me if
there are any inconsistencies in the patch embedded below so that I can
try to prevent them in the future.
________________________________________________________________________
From e8f4a79166042d52de8afdfb8530afc7de4fa977 Mon Sep 17 00:00:00 2001
From: Alejandro Colomar <colomar.6.4.3@gmail.com>
Date: Fri, 21 Aug 2020 14:27:36 +0200
Subject: [PATCH] queue.3: Document CIRCLEQ_* macros
Signed-off-by: Alejandro Colomar <colomar.6.4.3@gmail.com>
---
man3/queue.3 | 256 +++++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 248 insertions(+), 8 deletions(-)
diff --git a/man3/queue.3 b/man3/queue.3
index 260a5b8a5..7fbb92fcc 100644
--- a/man3/queue.3
+++ b/man3/queue.3
@@ -110,10 +110,28 @@
.Nm TAILQ_LAST ,
.Nm TAILQ_NEXT ,
.Nm TAILQ_PREV ,
-.Nm TAILQ_REMOVE
-.\" .Nm TAILQ_SWAP
+.Nm TAILQ_REMOVE ,
+.\" .Nm TAILQ_SWAP ,
+.Nm CIRCLEQ_EMPTY ,
+.Nm CIRCLEQ_ENTRY ,
+.Nm CIRCLEQ_FIRST ,
+.Nm CIRCLEQ_FOREACH ,
+.Nm CIRCLEQ_FOREACH_REVERSE ,
+.Nm CIRCLEQ_HEAD ,
+.Nm CIRCLEQ_HEAD_INITIALIZER ,
+.Nm CIRCLEQ_INIT ,
+.Nm CIRCLEQ_INSERT_AFTER ,
+.Nm CIRCLEQ_INSERT_BEFORE ,
+.Nm CIRCLEQ_INSERT_HEAD ,
+.Nm CIRCLEQ_INSERT_TAIL ,
+.Nm CIRCLEQ_LAST ,
+.Nm CIRCLEQ_LOOP_NEXT ,
+.Nm CIRCLEQ_LOOP_PREV ,
+.Nm CIRCLEQ_NEXT ,
+.Nm CIRCLEQ_PREV ,
+.Nm CIRCLEQ_REMOVE
.Nd implementations of singly-linked lists, singly-linked tail queues,
-lists and tail queues
+lists, tail queues, and circular queues
.Sh SYNOPSIS
.In sys/queue.h
.\"
@@ -198,11 +216,30 @@ lists and tail queues
.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.\" .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE"
"TAILQ_ENTRY NAME"
+.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_ENTRY "TYPE"
+.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head"
"CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
+.Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
+.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE
*elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE
*elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY
NAME"
+.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY
NAME"
+.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_LOOP_NEXT "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_LOOP_PREV "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.\"
.Sh DESCRIPTION
-These macros define and operate on four types of data structures:
-singly-linked lists, singly-linked tail queues, lists, and tail queues.
-All four structures support the following functionality:
+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
@@ -313,6 +350,21 @@ Each head entry requires two pointers rather than one.
Code size is about 15% greater and operations run about 20% slower
than singly-linked lists.
.El
+.Pp----
+Circular queues add the following functionality over the above:
+.Bl -enum -compact -offset indent
+.It
+The first and last entries are connected.
+.El
+.Pp
+However:
+.Pp
+.Bl -enum -compact -offset indent
+.It
+The termination condition for traversal is more complex.
+.It
+Code size is about 40% greater and operations run about 45% slower than
lists.
+.El
.Pp
In the macro definitions,
.Fa TYPE
@@ -321,8 +373,9 @@ that must contain a field of type
.Li SLIST_ENTRY ,
.Li STAILQ_ENTRY ,
.Li LIST_ENTRY ,
-or
.Li TAILQ_ENTRY ,
+or
+.Li CIRCLEQ_ENTRY ,
named
.Fa NAME .
The argument
@@ -332,8 +385,9 @@ using the macros
.Li SLIST_HEAD ,
.Li STAILQ_HEAD ,
.Li LIST_HEAD ,
+.Li TAILQ_HEAD ,
or
-.Li TAILQ_HEAD .
+.Li CIRCLEQ_HEAD .
See the examples below for further explanation of how these
macros are used.
.Ss Singly-linked lists
@@ -1220,6 +1274,192 @@ while (n1 != NULL) {
TAILQ_INIT(&head);
.Ed
+.Ss Circular queues
+A circular queue is headed by a structure defined by the
+.Nm CIRCLEQ_HEAD
+macro.
+This structure contains a pair of pointers,
+one to the first element in the circular queue and the other to
+the last element in the circular queue.
+The elements are doubly linked so that an arbitrary element can be
+removed without traversing the circular queue.
+New elements can be added to the circular queue after an existing element,
+before an existing element, at the head of the circular queue,
+or at the end of the circular queue.
+A
+.Fa CIRCLEQ_HEAD
+structure is declared as follows:
+.Bd -literal -offset indent
+CIRCLEQ_HEAD(HEADNAME, TYPE) head;
+.Ed
+.Pp
+where
+.Li HEADNAME
+is the name of the structure to be defined, and
+.Li TYPE
+is the type of the elements to be linked into the circular queue.
+A pointer to the head of the circular queue 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 CIRCLEQ_HEAD_INITIALIZER
+evaluates to an initializer for the circular queue
+.Fa head .
+.Pp
+The macro
+.Nm CIRCLEQ_EMPTY
+evaluates to true if there are no items on the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_ENTRY
+declares a structure that connects the elements in
+the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_FIRST
+returns the first item on the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_FOREACH
+traverses the circular queue referenced by
+.Fa head
+in the forward direction, assigning each element in turn to
+.Fa var .
+.Fa var
+is set to
+.Fa &head
+if the loop completes normally, or if there were no elements.
+.Pp
+The macro
+.Nm CIRCLEQ_FOREACH_REVERSE
+traverses the circular queue referenced by
+.Fa head
+in the reverse direction, assigning each element in turn to
+.Fa var .
+.Pp
+The macro
+.Nm CIRCLEQ_INIT
+initializes the circular queue referenced by
+.Fa head .
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_HEAD
+inserts the new element
+.Fa elm
+at the head of the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_TAIL
+inserts the new element
+.Fa elm
+at the end of the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_AFTER
+inserts the new element
+.Fa elm
+after the element
+.Fa listelm .
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_BEFORE
+inserts the new element
+.Fa elm
+before the element
+.Fa listelm .
+.Pp
+The macro
+.Nm CIRCLEQ_LAST
+returns the last item on the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_NEXT
+returns the next item on the circular queue, or
+.Fa &head
+if this item is the last one.
+.Pp
+The macro
+.Nm CIRCLEQ_PREV
+returns the previous item on the circular queue, or
+.Fa &head
+if this item is the first one.
+.Pp
+The macro
+.Nm CIRCLEQ_LOOP_NEXT
+returns the next item on the circular queue.
+If
+.Fa elm
+is the last element on the circular queue, the first element is returned.
+.Pp
+The macro
+.Nm CIRCLEQ_LOOP_PREV
+returns the previous item on the circular queue.
+If
+.Fa elm
+is the first element on the circular queue, the last element is returned.
+.Pp
+The macro
+.Nm CIRCLEQ_REMOVE
+removes the element
+.Fa elm
+from the circular queue.
+.Ss Circular queue example
+.Bd -literal
+CIRCLEQ_HEAD(circleq, entry) head =
+ CIRCLEQ_HEAD_INITIALIZER(head);
+struct circleq *headp; /* Circular queue head. */
+struct entry {
+ ...
+ CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
+ ...
+} *n1, *n2, *n3, *np;
+
+CIRCLEQ_INIT(&head); /* Initialize the queue. */
+
+n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
+CIRCLEQ_INSERT_HEAD(&head, n1, entries);
+
+n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
+CIRCLEQ_INSERT_TAIL(&head, n1, entries);
+
+n2 = malloc(sizeof(struct entry)); /* Insert after. */
+CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
+
+n3 = malloc(sizeof(struct entry)); /* Insert before. */
+CIRCLEQ_INSERT_BEFORE(&head, n2, n3, entries);
+
+CIRCLEQ_REMOVE(&head, n2, entries); /* Deletion. */
+free(n2);
+ /* Forward traversal. */
+CIRCLEQ_FOREACH(np, &head, entries)
+ np\-> ...
+ /* Reverse traversal. */
+CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
+ np\-> ...
+ /* CircleQ Deletion. */
+while (!CIRCLEQ_EMPTY(&head)) {
+ n1 = CIRCLEQ_FIRST(&head);
+ CIRCLEQ_REMOVE(&head, n1, entries);
+ free(n1);
+}
+ /* Faster CircleQ Deletion. */
+n1 = CIRCLEQ_FIRST(&head);
+while (n1 != (void *)&head) {
+ n2 = CIRCLEQ_NEXT(n1, entries);
+ free(n1);
+ n1 = n2;
+}
+
+CIRCLEQ_INIT(&head);
+.Ed
.Sh CONFORMING TO
Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008.
Present on the BSDs.
--
2.28.0
[-- Attachment #2: circleq.patch --]
[-- Type: text/x-patch, Size: 8802 bytes --]
From e8f4a79166042d52de8afdfb8530afc7de4fa977 Mon Sep 17 00:00:00 2001
From: Alejandro Colomar <colomar.6.4.3@gmail.com>
Date: Fri, 21 Aug 2020 14:27:36 +0200
Subject: [PATCH] queue.3: Document CIRCLEQ_* macros
Signed-off-by: Alejandro Colomar <colomar.6.4.3@gmail.com>
---
man3/queue.3 | 256 +++++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 248 insertions(+), 8 deletions(-)
diff --git a/man3/queue.3 b/man3/queue.3
index 260a5b8a5..7fbb92fcc 100644
--- a/man3/queue.3
+++ b/man3/queue.3
@@ -110,10 +110,28 @@
.Nm TAILQ_LAST ,
.Nm TAILQ_NEXT ,
.Nm TAILQ_PREV ,
-.Nm TAILQ_REMOVE
-.\" .Nm TAILQ_SWAP
+.Nm TAILQ_REMOVE ,
+.\" .Nm TAILQ_SWAP ,
+.Nm CIRCLEQ_EMPTY ,
+.Nm CIRCLEQ_ENTRY ,
+.Nm CIRCLEQ_FIRST ,
+.Nm CIRCLEQ_FOREACH ,
+.Nm CIRCLEQ_FOREACH_REVERSE ,
+.Nm CIRCLEQ_HEAD ,
+.Nm CIRCLEQ_HEAD_INITIALIZER ,
+.Nm CIRCLEQ_INIT ,
+.Nm CIRCLEQ_INSERT_AFTER ,
+.Nm CIRCLEQ_INSERT_BEFORE ,
+.Nm CIRCLEQ_INSERT_HEAD ,
+.Nm CIRCLEQ_INSERT_TAIL ,
+.Nm CIRCLEQ_LAST ,
+.Nm CIRCLEQ_LOOP_NEXT ,
+.Nm CIRCLEQ_LOOP_PREV ,
+.Nm CIRCLEQ_NEXT ,
+.Nm CIRCLEQ_PREV ,
+.Nm CIRCLEQ_REMOVE
.Nd implementations of singly-linked lists, singly-linked tail queues,
-lists and tail queues
+lists, tail queues, and circular queues
.Sh SYNOPSIS
.In sys/queue.h
.\"
@@ -198,11 +216,30 @@ lists and tail queues
.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.\" .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
+.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_ENTRY "TYPE"
+.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
+.Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
+.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
+.Fn CIRCLEQ_LOOP_NEXT "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_LOOP_PREV "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.\"
.Sh DESCRIPTION
-These macros define and operate on four types of data structures:
-singly-linked lists, singly-linked tail queues, lists, and tail queues.
-All four structures support the following functionality:
+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
@@ -313,6 +350,21 @@ Each head entry requires two pointers rather than one.
Code size is about 15% greater and operations run about 20% slower
than singly-linked lists.
.El
+.Pp----
+Circular queues add the following functionality over the above:
+.Bl -enum -compact -offset indent
+.It
+The first and last entries are connected.
+.El
+.Pp
+However:
+.Pp
+.Bl -enum -compact -offset indent
+.It
+The termination condition for traversal is more complex.
+.It
+Code size is about 40% greater and operations run about 45% slower than lists.
+.El
.Pp
In the macro definitions,
.Fa TYPE
@@ -321,8 +373,9 @@ that must contain a field of type
.Li SLIST_ENTRY ,
.Li STAILQ_ENTRY ,
.Li LIST_ENTRY ,
-or
.Li TAILQ_ENTRY ,
+or
+.Li CIRCLEQ_ENTRY ,
named
.Fa NAME .
The argument
@@ -332,8 +385,9 @@ using the macros
.Li SLIST_HEAD ,
.Li STAILQ_HEAD ,
.Li LIST_HEAD ,
+.Li TAILQ_HEAD ,
or
-.Li TAILQ_HEAD .
+.Li CIRCLEQ_HEAD .
See the examples below for further explanation of how these
macros are used.
.Ss Singly-linked lists
@@ -1220,6 +1274,192 @@ while (n1 != NULL) {
TAILQ_INIT(&head);
.Ed
+.Ss Circular queues
+A circular queue is headed by a structure defined by the
+.Nm CIRCLEQ_HEAD
+macro.
+This structure contains a pair of pointers,
+one to the first element in the circular queue and the other to
+the last element in the circular queue.
+The elements are doubly linked so that an arbitrary element can be
+removed without traversing the circular queue.
+New elements can be added to the circular queue after an existing element,
+before an existing element, at the head of the circular queue,
+or at the end of the circular queue.
+A
+.Fa CIRCLEQ_HEAD
+structure is declared as follows:
+.Bd -literal -offset indent
+CIRCLEQ_HEAD(HEADNAME, TYPE) head;
+.Ed
+.Pp
+where
+.Li HEADNAME
+is the name of the structure to be defined, and
+.Li TYPE
+is the type of the elements to be linked into the circular queue.
+A pointer to the head of the circular queue 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 CIRCLEQ_HEAD_INITIALIZER
+evaluates to an initializer for the circular queue
+.Fa head .
+.Pp
+The macro
+.Nm CIRCLEQ_EMPTY
+evaluates to true if there are no items on the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_ENTRY
+declares a structure that connects the elements in
+the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_FIRST
+returns the first item on the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_FOREACH
+traverses the circular queue referenced by
+.Fa head
+in the forward direction, assigning each element in turn to
+.Fa var .
+.Fa var
+is set to
+.Fa &head
+if the loop completes normally, or if there were no elements.
+.Pp
+The macro
+.Nm CIRCLEQ_FOREACH_REVERSE
+traverses the circular queue referenced by
+.Fa head
+in the reverse direction, assigning each element in turn to
+.Fa var .
+.Pp
+The macro
+.Nm CIRCLEQ_INIT
+initializes the circular queue referenced by
+.Fa head .
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_HEAD
+inserts the new element
+.Fa elm
+at the head of the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_TAIL
+inserts the new element
+.Fa elm
+at the end of the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_AFTER
+inserts the new element
+.Fa elm
+after the element
+.Fa listelm .
+.Pp
+The macro
+.Nm CIRCLEQ_INSERT_BEFORE
+inserts the new element
+.Fa elm
+before the element
+.Fa listelm .
+.Pp
+The macro
+.Nm CIRCLEQ_LAST
+returns the last item on the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_NEXT
+returns the next item on the circular queue, or
+.Fa &head
+if this item is the last one.
+.Pp
+The macro
+.Nm CIRCLEQ_PREV
+returns the previous item on the circular queue, or
+.Fa &head
+if this item is the first one.
+.Pp
+The macro
+.Nm CIRCLEQ_LOOP_NEXT
+returns the next item on the circular queue.
+If
+.Fa elm
+is the last element on the circular queue, the first element is returned.
+.Pp
+The macro
+.Nm CIRCLEQ_LOOP_PREV
+returns the previous item on the circular queue.
+If
+.Fa elm
+is the first element on the circular queue, the last element is returned.
+.Pp
+The macro
+.Nm CIRCLEQ_REMOVE
+removes the element
+.Fa elm
+from the circular queue.
+.Ss Circular queue example
+.Bd -literal
+CIRCLEQ_HEAD(circleq, entry) head =
+ CIRCLEQ_HEAD_INITIALIZER(head);
+struct circleq *headp; /* Circular queue head. */
+struct entry {
+ ...
+ CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
+ ...
+} *n1, *n2, *n3, *np;
+
+CIRCLEQ_INIT(&head); /* Initialize the queue. */
+
+n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
+CIRCLEQ_INSERT_HEAD(&head, n1, entries);
+
+n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
+CIRCLEQ_INSERT_TAIL(&head, n1, entries);
+
+n2 = malloc(sizeof(struct entry)); /* Insert after. */
+CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
+
+n3 = malloc(sizeof(struct entry)); /* Insert before. */
+CIRCLEQ_INSERT_BEFORE(&head, n2, n3, entries);
+
+CIRCLEQ_REMOVE(&head, n2, entries); /* Deletion. */
+free(n2);
+ /* Forward traversal. */
+CIRCLEQ_FOREACH(np, &head, entries)
+ np\-> ...
+ /* Reverse traversal. */
+CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
+ np\-> ...
+ /* CircleQ Deletion. */
+while (!CIRCLEQ_EMPTY(&head)) {
+ n1 = CIRCLEQ_FIRST(&head);
+ CIRCLEQ_REMOVE(&head, n1, entries);
+ free(n1);
+}
+ /* Faster CircleQ Deletion. */
+n1 = CIRCLEQ_FIRST(&head);
+while (n1 != (void *)&head) {
+ n2 = CIRCLEQ_NEXT(n1, entries);
+ free(n1);
+ n1 = n2;
+}
+
+CIRCLEQ_INIT(&head);
+.Ed
.Sh CONFORMING TO
Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008.
Present on the BSDs.
--
2.28.0
^ permalink raw reply related [flat|nested] 2+ messages in thread
* Re: [patch] queue.3: Document CIRCLEQ_* macros
2020-08-21 12:59 [patch] queue.3: Document CIRCLEQ_* macros Alejandro Colomar
@ 2020-08-24 10:36 ` Michael Kerrisk (man-pages)
0 siblings, 0 replies; 2+ messages in thread
From: Michael Kerrisk (man-pages) @ 2020-08-24 10:36 UTC (permalink / raw)
To: Alejandro Colomar; +Cc: linux-man, libc-alpha, mtk.manpages
Hello Alejandro,
On 8/21/20 2:59 PM, Alejandro Colomar wrote:
> ===========
> DESCRIPTION
> ===========
>
> Document ``CIRCLEQ_*`` macros, based on old documentation that was
> removed by accident in commit ``c0f21a0``, and improved to match the
> rest of the documentation in ``queue.3``.
Thanks!
> =======
> TESTING
> =======
>
> I run ``sudo make`` and then visualized the man page with
> ``man 3 queue``, and the contents looked good.
Modulo a few very minor formatting tweaks, yes, looks good.
> _______
>
> P.S.: I noticed that ``git format-patch`` leaves a trailing space at
> some places:
> The line after ``@@ -1220,6 +1274,192 @@ while (n1 != NULL) {``
> The line just before the git version (``-- ``).
> However, none of those lines are additions to the code, so they
> shouldn't affect the result.
> Is that ok?
I don't think it's a problem, but...
> I run ``git format-patch -1 HEAD --stdout > ../circleq.patch``.
>
> P.S. 2: I attached a copy of the patch just in case that the mailer
> adds any trailing spaces or any other weird things. Please, tell me if
> there are any inconsistencies in the patch embedded below so that I can
> try to prevent them in the future.
The inline patch would not apply. I think your mail client might be to
blame. I'm not quite sure of the cause. After checking the problem,
perhaps you could test by sending yourself a patch, and seeing if you
can apply.
However, the attachment worked fine, and I applied. (Nevertheless,
I prefer inline patches if you can fix your mailer.)
Minor comments below.
> ________________________________________________________________________
>
> From e8f4a79166042d52de8afdfb8530afc7de4fa977 Mon Sep 17 00:00:00 2001
> From: Alejandro Colomar <colomar.6.4.3@gmail.com>
> Date: Fri, 21 Aug 2020 14:27:36 +0200
> Subject: [PATCH] queue.3: Document CIRCLEQ_* macros
>
> Signed-off-by: Alejandro Colomar <colomar.6.4.3@gmail.com>
> ---
> man3/queue.3 | 256 +++++++++++++++++++++++++++++++++++++++++++++++++--
> 1 file changed, 248 insertions(+), 8 deletions(-)
>
> diff --git a/man3/queue.3 b/man3/queue.3
> index 260a5b8a5..7fbb92fcc 100644
> --- a/man3/queue.3
> +++ b/man3/queue.3
> @@ -110,10 +110,28 @@
> .Nm TAILQ_LAST ,
> .Nm TAILQ_NEXT ,
> .Nm TAILQ_PREV ,
> -.Nm TAILQ_REMOVE
> -.\" .Nm TAILQ_SWAP
> +.Nm TAILQ_REMOVE ,
> +.\" .Nm TAILQ_SWAP ,
> +.Nm CIRCLEQ_EMPTY ,
> +.Nm CIRCLEQ_ENTRY ,
> +.Nm CIRCLEQ_FIRST ,
> +.Nm CIRCLEQ_FOREACH ,
> +.Nm CIRCLEQ_FOREACH_REVERSE ,
> +.Nm CIRCLEQ_HEAD ,
> +.Nm CIRCLEQ_HEAD_INITIALIZER ,
> +.Nm CIRCLEQ_INIT ,
> +.Nm CIRCLEQ_INSERT_AFTER ,
> +.Nm CIRCLEQ_INSERT_BEFORE ,
> +.Nm CIRCLEQ_INSERT_HEAD ,
> +.Nm CIRCLEQ_INSERT_TAIL ,
> +.Nm CIRCLEQ_LAST ,
> +.Nm CIRCLEQ_LOOP_NEXT ,
> +.Nm CIRCLEQ_LOOP_PREV ,
> +.Nm CIRCLEQ_NEXT ,
> +.Nm CIRCLEQ_PREV ,
> +.Nm CIRCLEQ_REMOVE
> .Nd implementations of singly-linked lists, singly-linked tail queues,
> -lists and tail queues
> +lists, tail queues, and circular queues
> .Sh SYNOPSIS
> .In sys/queue.h
> .\"
> @@ -198,11 +216,30 @@ lists and tail queues
> .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
> .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
> .\" .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE"
> "TAILQ_ENTRY NAME"
> +.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
> +.Fn CIRCLEQ_ENTRY "TYPE"
> +.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
> +.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
> +.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head"
> "CIRCLEQ_ENTRY NAME"
> +.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
> +.Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
> +.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
> +.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE
> *elm" "CIRCLEQ_ENTRY NAME"
> +.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE
> *elm" "CIRCLEQ_ENTRY NAME"
> +.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY
> NAME"
> +.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY
> NAME"
> +.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
> +.Fn CIRCLEQ_LOOP_NEXT "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY
> NAME"
> +.Fn CIRCLEQ_LOOP_PREV "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY
> NAME"
> +.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
> +.Fn CIRCLEQ_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
> +.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
> .\"
> .Sh DESCRIPTION
> -These macros define and operate on four types of data structures:
> -singly-linked lists, singly-linked tail queues, lists, and tail queues.
> -All four structures support the following functionality:
> +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
> @@ -313,6 +350,21 @@ Each head entry requires two pointers rather than one.
> Code size is about 15% greater and operations run about 20% slower
> than singly-linked lists.
> .El
> +.Pp----
Why the "----"? It caused a minor formatting glitch. I removed it.
> +Circular queues add the following functionality over the above:
I added ".Pp" here.
Otherwise, everything is fine. Thanks for the patch!
Cheers,
Michael
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2020-08-24 10:37 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-08-21 12:59 [patch] queue.3: Document CIRCLEQ_* macros Alejandro Colomar
2020-08-24 10:36 ` Michael Kerrisk (man-pages)
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.