From owner-freebsd-bugs Tue Jul 18 20:40:13 2000 Delivered-To: freebsd-bugs@freebsd.org Received: from freefall.freebsd.org (freefall.FreeBSD.ORG [204.216.27.21]) by hub.freebsd.org (Postfix) with ESMTP id 42C0037BD77 for ; Tue, 18 Jul 2000 20:40:01 -0700 (PDT) (envelope-from gnats@FreeBSD.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.9.3/8.9.2) id UAA70231; Tue, 18 Jul 2000 20:40:00 -0700 (PDT) (envelope-from gnats@FreeBSD.org) Received: from hand.dotat.at (sfo-gw.covalent.net [207.44.198.62]) by hub.freebsd.org (Postfix) with ESMTP id ACB4437BC52 for ; Tue, 18 Jul 2000 20:33:46 -0700 (PDT) (envelope-from fanf@hand.dotat.at) Received: from fanf by hand.dotat.at with local (Exim 3.15 #3) id 13EkcB-000Ikz-00 for FreeBSD-gnats-submit@freebsd.org; Wed, 19 Jul 2000 03:33:43 +0000 Message-Id: Date: Wed, 19 Jul 2000 03:33:43 +0000 From: Tony Finch Reply-To: Tony Finch To: FreeBSD-gnats-submit@freebsd.org X-Send-Pr-Version: 3.2 Subject: misc/20024: [PATCH] queue(3) concatenation macros Sender: owner-freebsd-bugs@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.org >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 >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