On Mon, 8 Sep 2014, Jona Joachim wrote:
> On 2014-09-06, Gr?goire Duch?ne <gduch...@awhk.org> wrote:
> > Hi,
> >
> > Although CIRCLEQ_* macros are deprecated, queue(3) does not say so.
>
> perhaps it would be interesting to mention why circle queues got
> deprecated.
Let's go a step further and remove them from the queue(3) manpage, leaving
just a blurb about why and recommending conversion to tail queues.
ok?
Philip
Index: queue.3
===================================================================
RCS file: /cvs/src/share/man/man3/queue.3,v
retrieving revision 1.59
diff -u -p -r1.59 queue.3
--- queue.3 14 Aug 2013 06:32:31 -0000 1.59
+++ queue.3 12 Sep 2014 19:46:19 -0000
@@ -98,27 +98,8 @@
.Nm TAILQ_INSERT_HEAD ,
.Nm TAILQ_INSERT_TAIL ,
.Nm TAILQ_REMOVE ,
-.Nm TAILQ_REPLACE ,
-.Nm CIRCLEQ_ENTRY ,
-.Nm CIRCLEQ_HEAD ,
-.Nm CIRCLEQ_HEAD_INITIALIZER ,
-.Nm CIRCLEQ_FIRST ,
-.Nm CIRCLEQ_LAST ,
-.Nm CIRCLEQ_END ,
-.Nm CIRCLEQ_NEXT ,
-.Nm CIRCLEQ_PREV ,
-.Nm CIRCLEQ_EMPTY ,
-.Nm CIRCLEQ_FOREACH ,
-.Nm CIRCLEQ_FOREACH_SAFE ,
-.Nm CIRCLEQ_FOREACH_REVERSE_SAFE ,
-.Nm CIRCLEQ_INIT ,
-.Nm CIRCLEQ_INSERT_AFTER ,
-.Nm CIRCLEQ_INSERT_BEFORE ,
-.Nm CIRCLEQ_INSERT_HEAD ,
-.Nm CIRCLEQ_INSERT_TAIL ,
-.Nm CIRCLEQ_REMOVE ,
-.Nm CIRCLEQ_REPLACE
-.Nd implementations of singly-linked lists, doubly-linked lists, simple
queues, tail queues, and circular queues
+.Nm TAILQ_REPLACE
+.Nd implementations of singly-linked lists, doubly-linked lists, simple
queues, and tail queues
.Sh SYNOPSIS
.In sys/queue.h
.Pp
@@ -233,44 +214,10 @@
.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
.Ft void
.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "struct TYPE *elm" "struct TYPE *elm2"
"FIELDNAME"
-.Pp
-.Fn CIRCLEQ_ENTRY "TYPE"
-.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
-.Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
-.Ft "struct TYPE *"
-.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
-.Ft "struct TYPE *"
-.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
-.Ft "struct TYPE *"
-.Fn CIRCLEQ_END "CIRCLEQ_HEAD *head"
-.Ft "struct TYPE *"
-.Fn CIRCLEQ_NEXT "struct TYPE *listelm" "FIELDNAME"
-.Ft "struct TYPE *"
-.Fn CIRCLEQ_PREV "struct TYPE *listelm" "FIELDNAME"
-.Ft int
-.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
-.Fn CIRCLEQ_FOREACH "VARNAME" "CIRCLEQ_HEAD *head" "FIELDNAME"
-.Fn CIRCLEQ_FOREACH_SAFE "VARNAME" "CIRCLEQ_HEAD *head" "FIELDNAME"
"TEMP_VARNAME"
-.Fn CIRCLEQ_FOREACH_REVERSE "VARNAME" "CIRCLEQ_HEAD *head" "FIELDNAME"
-.Fn CIRCLEQ_FOREACH_REVERSE_SAFE "VARNAME" "CIRCLEQ_HEAD *head" "FIELDNAME"
"TEMP_VARNAME"
-.Ft void
-.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
-.Ft void
-.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "struct TYPE *listelm" "struct
TYPE *elm" "FIELDNAME"
-.Ft void
-.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "struct TYPE *listelm" "struct
TYPE *elm" "FIELDNAME"
-.Ft void
-.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
-.Ft void
-.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
-.Ft void
-.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
-.Ft void
-.Fn CIRCLEQ_REPLACE "CIRCLEQ_HEAD *head" "struct TYPE *elm" "struct TYPE
*elm2" "FIELDNAME"
.Sh DESCRIPTION
-These macros define and operate on five types of data structures:
-singly-linked lists, simple queues, lists, tail queues, and circular queues.
-All five structures support the following functionality:
+These macros define and operate on four types of data structures:
+singly-linked lists, simple queues, lists, and tail queues.
+All four structures support the following functionality:
.Pp
.Bl -enum -compact -offset indent
.It
@@ -283,7 +230,7 @@ Removal of an entry from the head of the
Forward traversal through the list.
.El
.Pp
-Singly-linked lists are the simplest of the five data structures
+Singly-linked lists are the simplest of the four data structures
and support only the above functionality.
Singly-linked lists are ideal for applications with large datasets
and few or no removals, or for implementing a LIFO queue.
@@ -310,8 +257,8 @@ than singly-linked lists.
Simple queues are ideal for applications with large datasets and
few or no removals, or for implementing a FIFO queue.
.Pp
-All doubly linked types of data structures (lists, tail queues, and circle
-queues) additionally allow:
+All doubly linked types of data structures (lists and tail queues)
+additionally allow:
.Pp
.Bl -enum -compact -offset indent
.It
@@ -354,27 +301,10 @@ Code size is about 15% greater and opera
than singly-linked lists.
.El
.Pp
-Circular queues add the following functionality:
-.Pp
-.Bl -enum -compact -offset indent
-.It
-Entries can be added at the end of a list.
-.It
-They may be traversed backwards, from tail to head.
-.El
-.Pp
-However:
-.Pp
-.Bl -enum -compact -offset indent
-.It
-All list insertions and removals must specify the head of the list.
-.It
-Each head entry requires two pointers rather than one.
-.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
+An additional type of data structure, circular queues, violated the C
+language aliasing rules and were miscompiled as a result.
+All code using them should be converted to another structure;
+tail queues are usually the easiest to convert to.
.Pp
In the macro definitions,
.Fa TYPE
@@ -382,9 +312,8 @@ is the name tag of a user defined struct
.Li SLIST_ENTRY ,
.Li LIST_ENTRY ,
.Li SIMPLEQ_ENTRY ,
-.Li TAILQ_ENTRY ,
or
-.Li CIRCLEQ_ENTRY ,
+.Li TAILQ_ENTRY ,
named
.Fa FIELDNAME .
The argument
@@ -394,9 +323,8 @@ using the macros
.Fn SLIST_HEAD ,
.Fn LIST_HEAD ,
.Fn SIMPLEQ_HEAD ,
-.Fn TAILQ_HEAD ,
or
-.Fn CIRCLEQ_HEAD .
+.Fn TAILQ_HEAD .
See the examples below for further explanation of how these macros are used.
.Sh SINGLY-LINKED LISTS
A singly-linked list is headed by a structure defined by the
@@ -972,164 +900,6 @@ while ((np = TAILQ_FIRST(&head))) {
}
.Ed
-.Sh CIRCULAR QUEUES
-A circular queue is headed by a structure defined by the
-.Fn 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 queue.
-New elements can be added to the queue after an existing element,
-before an existing element, at the head of the queue, or at the end
-of the queue.
-A
-.Fa CIRCLEQ_HEAD
-structure is declared as follows:
-.Bd -literal -offset indent
-CIRCLEQ_HEAD(HEADNAME, TYPE) head;
-.Ed
-.Pp
-where
-.Fa HEADNAME
-is the name of the structure to be defined, and struct
-.Fa 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
-.Fn CIRCLEQ_ENTRY
-macro declares a structure that connects the elements in the circular queue.
-.Pp
-The
-.Fn CIRCLEQ_INIT
-macro initializes the circular queue referenced by
-.Fa head .
-.Pp
-The circular queue can also be initialized statically by using the
-.Fn CIRCLEQ_HEAD_INITIALIZER
-macro.
-.Pp
-The
-.Fn CIRCLEQ_INSERT_HEAD
-macro inserts the new element
-.Fa elm
-at the head of the circular queue.
-.Pp
-The
-.Fn CIRCLEQ_INSERT_TAIL
-macro inserts the new element
-.Fa elm
-at the end of the circular queue.
-.Pp
-The
-.Fn CIRCLEQ_INSERT_AFTER
-macro inserts the new element
-.Fa elm
-after the element
-.Fa listelm .
-.Pp
-The
-.Fn CIRCLEQ_INSERT_BEFORE
-macro inserts the new element
-.Fa elm
-before the element
-.Fa listelm .
-.Pp
-The
-.Fn CIRCLEQ_REMOVE
-macro removes the element
-.Fa elm
-from the circular queue.
-.Pp
-The
-.Fn CIRCLEQ_REPLACE
-macro replaces the list element
-.Fa elm
-with the new element
-.Fa elm2 .
-.Pp
-The
-.Fn CIRCLEQ_FIRST ,
-.Fn CIRCLEQ_LAST ,
-.Fn CIRCLEQ_END ,
-.Fn CIRCLEQ_NEXT
-and
-.Fn CIRCLEQ_PREV
-macros can be used to traverse a circular queue.
-The
-.Fn CIRCLEQ_FOREACH
-is used for circular queue forward traversal:
-.Bd -literal -offset indent
-CIRCLEQ_FOREACH(np, head, FIELDNAME)
-.Ed
-.Pp
-The
-.Fn CIRCLEQ_FOREACH_REVERSE
-macro acts like
-.Fn CIRCLEQ_FOREACH
-but traverses the circular queue backwards.
-.Pp
-The macros
-.Fn CIRCLEQ_FOREACH_SAFE
-and
-.Fn CIRCLEQ_FOREACH_REVERSE_SAFE
-traverse the list referenced by head
-in a forward or reverse direction respectively,
-assigning each element in turn to var.
-However, unlike their unsafe counterparts,
-they permit both the removal of var
-as well as freeing it from within the loop safely
-without interfering with the traversal.
-.Pp
-The
-.Fn CIRCLEQ_EMPTY
-macro should be used to check whether a circular queue is empty.
-.Sh CIRCULAR QUEUE EXAMPLE
-.Bd -literal
-CIRCLEQ_HEAD(circleq, entry) head;
-struct entry {
- ...
- CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
- ...
-} *n1, *n2, *np;
-
-CIRCLEQ_INIT(&head); /* Initialize circular 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);
-
-n2 = malloc(sizeof(struct entry)); /* Insert before. */
-CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
- /* Forward traversal. */
-CIRCLEQ_FOREACH(np, &head, entries)
- np-> ...
- /* Reverse traversal. */
-CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
- np-> ...
- /* Delete. */
-while (!CIRCLEQ_EMPTY(&head)) {
- n1 = CIRCLEQ_FIRST(&head);
- CIRCLEQ_REMOVE(&head, n1, entries);
- free(n1);
-}
-.Ed
.Sh NOTES
It is an error to assume the next and previous fields are preserved
after an element has been removed from a list or queue.
@@ -1143,7 +913,7 @@ The
.Fn SIMPLEQ_END
and
.Fn TAILQ_END
-macros are provided for symmetry with
+macros are provided for symmetry with the historical
.Fn CIRCLEQ_END .
They expand to
.Dv NULL
@@ -1169,3 +939,5 @@ The
.Nm queue
functions first appeared in
.Bx 4.4 .
+The historical circle queue macros were deprecated in
+.Ox 5.5 .
