Date: Wed, 19 Jul 2000 03:33:43 +0000 From: Tony Finch <dot@dotat.at> To: FreeBSD-gnats-submit@freebsd.org Subject: misc/20024: [PATCH] queue(3) concatenation macros Message-ID: <E13EkcB-000Ikz-00@hand.dotat.at>
next in thread | raw e-mail | index | archive | help
>Number: 20024
>Category: misc
>Synopsis: [PATCH] queue(3) concatenation macros
>Confidential: no
>Severity: non-critical
>Priority: low
>Responsible: freebsd-bugs
>State: open
>Quarter:
>Keywords:
>Date-Required:
>Class: change-request
>Submitter-Id: current-users
>Arrival-Date: Tue Jul 18 20:40:00 PDT 2000
>Closed-Date:
>Last-Modified:
>Originator: Tony Finch <dot@dotat.at>
>Release: FreeBSD 4.0-STABLE-20000705 i386
>Organization:
dotat
>Environment:
>Description:
The patch below adds a couple of macros to queue.h so that TAILQs and
CIRCLEQs may be easily concatenated. It even includes documentation!
>How-To-Repeat:
>Fix:
--- /usr/src/sys/sys/queue.h.orig Tue Jun 6 20:42:32 2000
+++ /usr/src/sys/sys/queue.h Wed Jul 19 03:15:10 2000
@@ -74,7 +74,8 @@
* linked so that an arbitrary element can be removed without a need to
* traverse the list. New elements can be added to the list before or
* after an existing element, at the head of the list, or at the end of
- * the list. A tail queue may be traversed in either direction.
+ * the list. A tail queue may be traversed in either direction. Tail
+ * queues may be concated.
*
* A circle queue is headed by a pair of pointers, one to the head of the
* list and the other to the tail of the list. The elements are doubly
@@ -82,7 +83,7 @@
* traverse the list. New elements can be added to the list before or after
* an existing element, at the head of the list, or at the end of the list.
* A circle queue may be traversed in either direction, but has a more
- * complex end of list detection.
+ * complex end of list detection. Circle queues may be concatenated.
*
* For details on the use of these macros, see the queue(3) manual page.
*
@@ -104,6 +105,7 @@
* _INSERT_TAIL - - + + +
* _REMOVE_HEAD + - + - -
* _REMOVE + + + + +
+ * _CONCAT - - - + +
*
*/
@@ -387,6 +389,15 @@
(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
} while (0)
+#define TAILQ_CONCAT(head1, head2, field) do { \
+ if (!TAILQ_EMPTY(head2)) { \
+ *(head1)->tqh_last = (head2)->tqh_first; \
+ (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
+ (head1)->tqh_last = (head2)->tqh_last; \
+ TAILQ_INIT(head2); \
+ } \
+} while (0)
+
#define TAILQ_REMOVE(head, elm, field) do { \
if (((elm)->field.tqe_next) != NULL) \
(elm)->field.tqe_next->field.tqe_prev = \
@@ -471,6 +482,25 @@
else \
(head)->cqh_last->field.cqe_next = (elm); \
(head)->cqh_last = (elm); \
+} while (0)
+
+#define CIRCLEQ_CONCAT(head1, head2, field) do { \
+ if (!CIRCLEQ_EMPTY(head2)) { \
+ if (!CIRCLEQ_EMPTY(head1)) { \
+ (head1)->cqh_last->field.cqe_next = \
+ (head2)->cqh_first; \
+ (head2)->cqh_first->field.cqe_prev = \
+ (head1)->cqh_last; \
+ } else { \
+ (head1)->cqh_first = (head2)->cqh_first; \
+ (head2)->cqh_first->field.cqe_prev = \
+ (void *)(head1); \
+ } \
+ (head1)->cqh_last = (head2)->cqh_last; \
+ (head2)->cqh_last->field.cqe_next = \
+ (void *)(head1); \
+ CIRCLEQ_INIT(head2); \
+ } \
} while (0)
#define CIRCLEQ_LAST(head) ((head)->cqh_last)
--- /usr/src/share/man/man3/queue.3.orig Tue Jun 6 19:16:35 2000
+++ /usr/src/share/man/man3/queue.3 Wed Jul 19 03:25:39 2000
@@ -86,6 +86,7 @@
.Nm TAILQ_NEXT ,
.Nm TAILQ_PREV ,
.Nm TAILQ_REMOVE ,
+.Nm TAILQ_CONCAT ,
.Nm CIRCLEQ_EMPTY ,
.Nm CIRCLEQ_ENTRY ,
.Nm CIRCLEQ_FIRST ,
@@ -100,7 +101,8 @@
.Nm CIRCLE_LAST ,
.Nm CIRCLE_NEXT ,
.Nm CIRCLE_PREV ,
-.Nm CIRCLEQ_REMOVE
+.Nm CIRCLEQ_REMOVE ,
+.Nm CIRCLEQ_CONCAT
.Nd implementations of singly-linked lists, singly-linked tail queues,
lists, tail queues, and circular queues
.Sh SYNOPSIS
@@ -159,6 +161,7 @@
.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
+.Fn TAILQ_CONCAT "TAILQ_HEAD *queue1" "TAILQ_HEAD *queue2" "TAILQ_ENTRY NAME"
.\"
.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
.Fn CIRCLEQ_ENTRY "TYPE"
@@ -175,6 +178,7 @@
.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
+.Fn CIRCLEQ_CONCAT "CIRCLEQ_HEAD *queue1" "CIRCLEQ_HEAD *queue2" "CIRCLEQ_ENTRY NAME"
.Sh DESCRIPTION
These macros define and operate on five types of data structures:
singly-linked lists, singly-linked tail queues, lists, tail queues,
@@ -245,6 +249,8 @@
Entries can be added at the end of a list.
.It
They may be traversed backwards, from tail to head.
+.It
+They may be concatenated.
.El
However:
.Bl -enum -compact -offset indent
@@ -263,6 +269,8 @@
Entries can be added at the end of a list.
.It
They may be traversed backwards, from tail to head.
+.It
+They may be concatenated.
.El
However:
.Bl -enum -compact -offset indent
@@ -826,6 +834,16 @@
removes the element
.Fa elm
from the tail queue.
+.Pp
+The macro
+.Nm TAILQ_CONCAT
+concatenates
+.Fa queue2
+onto the end of
+.Fa queue1 ,
+leaving
+.Fa queue2
+empty.
.Sh TAIL QUEUE EXAMPLE
.Bd -literal
TAILQ_HEAD(tailhead, entry) head;
@@ -984,6 +1002,16 @@
removes the element
.Fa elm
from the circular queue.
+.Pp
+The macro
+.Nm CIRCLEQ_CONCAT
+concatenates
+.Fa queue2
+onto the end of
+.Fa queue1 ,
+leaving
+.Fa queue2
+empty.
.Sh CIRCULAR QUEUE EXAMPLE
.Bd -literal
CIRCLEQ_HEAD(circleq, entry) head;
>Release-Note:
>Audit-Trail:
>Unformatted:
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-bugs" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?E13EkcB-000Ikz-00>