From owner-svn-src-head@freebsd.org Tue Aug 16 17:07:49 2016 Return-Path: Delivered-To: svn-src-head@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 48299BBC76F; Tue, 16 Aug 2016 17:07:49 +0000 (UTC) (envelope-from mckusick@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 25D9E1A0E; Tue, 16 Aug 2016 17:07:49 +0000 (UTC) (envelope-from mckusick@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id u7GH7mgM082436; Tue, 16 Aug 2016 17:07:48 GMT (envelope-from mckusick@FreeBSD.org) Received: (from mckusick@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id u7GH7mMK082434; Tue, 16 Aug 2016 17:07:48 GMT (envelope-from mckusick@FreeBSD.org) Message-Id: <201608161707.u7GH7mMK082434@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: mckusick set sender to mckusick@FreeBSD.org using -f From: Kirk McKusick Date: Tue, 16 Aug 2016 17:07:48 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r304230 - in head: share/man/man3 sys/sys X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 16 Aug 2016 17:07:49 -0000 Author: mckusick Date: Tue Aug 16 17:07:48 2016 New Revision: 304230 URL: https://svnweb.freebsd.org/changeset/base/304230 Log: Add two new macros, SLIST_CONCAT and LIST_CONCAT. Note in both the queue.h header file and in the queue.3 manual page that they are O(n) so should be used only in low-usage paths with short lists (otherwise an STAILQ or TAILQ should be used). Reviewed by: kib Modified: head/share/man/man3/queue.3 head/sys/sys/queue.h Modified: head/share/man/man3/queue.3 ============================================================================== --- head/share/man/man3/queue.3 Tue Aug 16 17:05:15 2016 (r304229) +++ head/share/man/man3/queue.3 Tue Aug 16 17:07:48 2016 (r304230) @@ -28,12 +28,13 @@ .\" @(#)queue.3 8.2 (Berkeley) 1/24/94 .\" $FreeBSD$ .\" -.Dd June 24, 2015 +.Dd August 15, 2016 .Dt QUEUE 3 .Os .Sh NAME .Nm SLIST_CLASS_ENTRY , .Nm SLIST_CLASS_HEAD , +.Nm SLIST_CONCAT , .Nm SLIST_EMPTY , .Nm SLIST_ENTRY , .Nm SLIST_FIRST , @@ -75,6 +76,7 @@ .Nm STAILQ_SWAP , .Nm LIST_CLASS_ENTRY , .Nm LIST_CLASS_HEAD , +.Nm LIST_CONCAT , .Nm LIST_EMPTY , .Nm LIST_ENTRY , .Nm LIST_FIRST , @@ -125,6 +127,7 @@ lists and tail queues .\" .Fn SLIST_CLASS_ENTRY "CLASSTYPE" .Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" +.Fn SLIST_CONCAT "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" "SLIST_ENTRY NAME" .Fn SLIST_EMPTY "SLIST_HEAD *head" .Fn SLIST_ENTRY "TYPE" .Fn SLIST_FIRST "SLIST_HEAD *head" @@ -168,6 +171,7 @@ lists and tail queues .\" .Fn LIST_CLASS_ENTRY "CLASSTYPE" .Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" +.Fn LIST_CONCAT "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" .Fn LIST_EMPTY "LIST_HEAD *head" .Fn LIST_ENTRY "TYPE" .Fn LIST_FIRST "LIST_HEAD *head" @@ -249,6 +253,8 @@ Singly-linked lists add the following fu .Bl -enum -compact -offset indent .It O(n) removal of any entry in the list. +.It +O(n) concatenation of two lists. .El .Pp Singly-linked tail queues add the following functionality: @@ -296,6 +302,8 @@ Linked lists are the simplest of the dou They add the following functionality over the above: .Bl -enum -compact -offset indent .It +O(n) concatenation of two lists. +.It They may be traversed backwards. .El However: @@ -401,6 +409,19 @@ evaluates to an initializer for the list .Fa head . .Pp The macro +.Nm SLIST_CONCAT +concatenates the list headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 +removing all entries from the former. +Use of this macro should be avoided as it traverses the entirety of the +.Fa head1 +list. +A singly-linked tail queue should be used if this macro is needed in +high-usage code paths or to operate on long lists. +.Pp +The macro .Nm SLIST_EMPTY evaluates to true if there are no elements in the list. .Pp @@ -508,6 +529,9 @@ The macro removes the element .Fa elm from the list. +Use of this macro should be avoided as it traverses the entire list. +A doubly-linked list should be used if this macro is needed in +high-usage code paths or to operate on long lists. .Pp The macro .Nm SLIST_SWAP @@ -724,6 +748,9 @@ The macro removes the element .Fa elm from the tail queue. +Use of this macro should be avoided as it traverses the entire list. +A doubly-linked tail queue should be used if this macro is needed in +high-usage code paths or to operate on long tail queues. .Pp The macro .Nm STAILQ_SWAP @@ -823,6 +850,19 @@ evaluates to an initializer for the list .Fa head . .Pp The macro +.Nm LIST_CONCAT +concatenates the list headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 +removing all entries from the former. +Use of this macro should be avoided as it traverses the entirety of the +.Fa head1 +list. +A tail queue should be used if this macro is needed in +high-usage code paths or to operate on long lists. +.Pp +The macro .Nm LIST_EMPTY evaluates to true if there are no elements in the list. .Pp Modified: head/sys/sys/queue.h ============================================================================== --- head/sys/sys/queue.h Tue Aug 16 17:05:15 2016 (r304229) +++ head/sys/sys/queue.h Tue Aug 16 17:07:48 2016 (r304230) @@ -76,6 +76,10 @@ * * For details on the use of these macros, see the queue(3) manual page. * + * Below is a summary of implemented functions where: + * + means the macro is available + * - means the macro is not available + * s means the macro is available but is slow (runs in O(n) time) * * SLIST LIST STAILQ TAILQ * _HEAD + + + + @@ -101,10 +105,10 @@ * _INSERT_BEFORE - + - + * _INSERT_AFTER + + + + * _INSERT_TAIL - - + + - * _CONCAT - - + + + * _CONCAT s s + + * _REMOVE_AFTER + - + - * _REMOVE_HEAD + - + - - * _REMOVE + + + + + * _REMOVE s + s + * _SWAP + + + + * */ @@ -183,6 +187,19 @@ struct { \ /* * Singly-linked List functions. */ +#define SLIST_CONCAT(head1, head2, type, field) do { \ + QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ + if (curelm == NULL) { \ + if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ + SLIST_INIT(head2); \ + } else if (SLIST_FIRST(head2) != NULL) { \ + while (SLIST_NEXT(curelm, field) != NULL) \ + curelm = SLIST_NEXT(curelm, field); \ + SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ + SLIST_INIT(head2); \ + } \ +} while (0) + #define SLIST_EMPTY(head) ((head)->slh_first == NULL) #define SLIST_FIRST(head) ((head)->slh_first) @@ -447,6 +464,23 @@ struct { \ #define QMD_LIST_CHECK_PREV(elm, field) #endif /* (_KERNEL && INVARIANTS) */ +#define LIST_CONCAT(head1, head2, type, field) do { \ + QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \ + if (curelm == NULL) { \ + if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ + LIST_FIRST(head2)->field.le_prev = \ + &LIST_FIRST((head1)); \ + LIST_INIT(head2); \ + } \ + } else if (LIST_FIRST(head2) != NULL) { \ + while (LIST_NEXT(curelm, field) != NULL) \ + curelm = LIST_NEXT(curelm, field); \ + LIST_NEXT(curelm, field) = LIST_FIRST(head2); \ + LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \ + LIST_INIT(head2); \ + } \ +} while (0) + #define LIST_EMPTY(head) ((head)->lh_first == NULL) #define LIST_FIRST(head) ((head)->lh_first)