queue.3: Document CIRCLEQ_* macros
Commit Message
===========
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.
Comments
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
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(-)
@@ -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