From sacadmin Mon Jan 25 08:37:16 2010 Received: from sac.sfbay.sun.com (localhost [127.0.0.1]) by sac.sfbay.sun.com (8.13.8+Sun/8.13.8) with ESMTP id o0PGbGqH018549; Mon, 25 Jan 2010 08:37:16 -0800 (PST) Received: (from dr146992@localhost) by sac.sfbay.sun.com (8.13.8+Sun/8.13.8/Submit) id o0PGbGvF018545; Mon, 25 Jan 2010 08:37:16 -0800 (PST) Date: Mon, 25 Jan 2010 08:37:16 -0800 (PST) From: Darren Reed Message-Id: <201001251637.o0PGbGvF018545@sac.sfbay.sun.com> To: PSARC-record@sac.sfbay.sun.com Subject: BSD List Interfaces [PSARC/2010/028 FastTrack timeout 02/01/2010] Status: RO Content-Length: 554 Template Version: @(#)sac_nextcase 1.68 02/23/09 SMI This information is Copyright 2010 Sun Microsystems 1. Introduction 1.1. Project/Component Working Name: BSD List Interfaces 1.2. Name of Document Author/Supplier: Author: Darren Reed 1.3 Date of This Document: 25 January, 2010 4. Technical Description See the case directory for more detail 6. Resources and Schedule 6.4. Steering Committee requested information 6.4.1. Consolidation C-team Name: ON 6.5. ARC review type: FastTrack 6.6. ARC Exposure: open From Darren.Reed@Sun.COM Mon Jan 25 08:47:12 2010 Received: from dm-sfbay-01.sfbay.sun.com (dm-sfbay-01.SFBay.Sun.COM [129.145.155.118]) by sac.sfbay.sun.com (8.13.8+Sun/8.13.8) with ESMTP id o0PGlCGq018637 for ; Mon, 25 Jan 2010 08:47:12 -0800 (PST) Received: from gmp-eb-inf-2.sun.com (gmp-eb-inf-2.EU.Sun.COM [192.18.6.24]) by dm-sfbay-01.sfbay.sun.com (8.13.8+Sun/8.13.8/ENSMAIL,v2.4) with ESMTP id o0PGlBYk003127 for ; Mon, 25 Jan 2010 08:47:12 -0800 (PST) Received: from fe-emea-09.sun.com (gmp-eb-lb-1-fe1.eu.sun.com [192.18.6.7] (may be forged)) by gmp-eb-inf-2.sun.com (8.13.7+Sun/8.12.9) with ESMTP id o0PGl6MS014111 for ; Mon, 25 Jan 2010 16:47:06 GMT MIME-version: 1.0 Content-transfer-encoding: 7BIT Content-type: text/plain; CHARSET=US-ASCII; format=flowed Received: from conversion-daemon.fe-emea-09.sun.com by fe-emea-09.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) id <0KWT00H007OK9F00@fe-emea-09.sun.com> for psarc-ext@sac.sfbay.sun.com; Mon, 25 Jan 2010 16:47:03 +0000 (GMT) Received: from [129.157.19.238] ([unknown] [129.157.19.238]) by fe-emea-09.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) with ESMTPSA id <0KWT0095XAM92D40@fe-emea-09.sun.com> for psarc-ext@sac.sfbay.sun.com; Mon, 25 Jan 2010 16:46:57 +0000 (GMT) Date: Mon, 25 Jan 2010 17:46:53 +0100 From: Darren Reed Subject: BSD List Interfaces [PSARC/2010/028 FastTrack timeout 02/01/2010] Sender: Darren.Reed@Sun.COM To: psarc-ext Message-id: <4B5DCAFD.1070504@Sun.COM> User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.1.5) Gecko/20091204 Thunderbird/3.0 Status: RO Content-Length: 6502 Introduction ============ As part of an earlier project, the macros created for 4.4BSD were added to the system as part of the project's implementation. This case seeks to document those interfaces and to make them available for wider use on Solaris. The interfaces included as a part of this case provide an easy to use, type safe, implementation of linked lists and queues. In addition to providing the aforementioned interfaces to internal developers, the delivery of the interfaces in this case has increased the compatibility of Open/Solaris with open source applications from other platforms. A man page can be found within the case directory. The man page and implementation both originate from NetBSD. This case seeks patch binding. Details ======= The current implementation of the BSD macros for supporting both list and queue data structures is found within /usr/include/sys/queue.h. The filename and location have been mirrored on Solaris. This file introduces the following types of data structures: * single linked list * double linked list * tail queue & singly linked tail queue * simple queue * circular queue Single Linked List ------------------ A singly-linked list is headed by a single forward pointer. The elements are singly linked for minimum space and pointer manipulation overhead at the expense of O(n) removal for arbitrary elements. New elements can be added to the list after an existing element or at the head of the list. Elements being removed from the head of the list should use the explicit macro for this purpose for optimum efficiency. A singly-linked list may only be traversed in the forward direction. Singly-linked lists are ideal for applications with large datasets and few or no removals or for implementing a LIFO queue. Double Linked List ------------------ A list is headed by a single forward pointer (or an array of forward pointers for a hash table header). The elements are doubly 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 or at the head of the list. A list may only be traversed in the forward direction. Simple Queue ------------ A simple queue is headed by a pair of pointers, one the head of the list and the other to the tail of the list. The elements are singly linked to save space, so elements can only be removed from the head of the list. New elements can be added to the list after an existing element, at the head of the list, or at the end of the list. A simple queue may only be traversed in the forward direction. Tail queue ---------- A tail 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 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. Circle Queue ------------ 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 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 circle queue may be traversed in either direction, but has a more complex end of list detection. Interfaces ========== Committed LIST_HEAD Committed LIST_ENTRY Committed LIST_INIT Committed LIST_INSERT_AFTER Committed LIST_INSERT_BEFORE Committed LIST_INSERT_HEAD Committed LIST_REMOVE Committed LIST_FOREACH Committed LIST_EMPTY Committed LIST_FIRST Committed LIST_NEXT Committed SLIST_HEAD Committed SLIST_ENTRY Committed SLIST_INIT Committed SLIST_INSERT_AFTER Committed SLIST_INSERT_HEAD Committed SLIST_REMOVE_HEAD Committed SLIST_REMOVE Committed SLIST_FOREACH Committed SLIST_EMPTY Committed SLIST_FIRST Committed SLIST_NEXT Committed STAILQ_HEAD Committed STAILQ_ENTRY Committed STAILQ_INIT Committed STAILQ_INSERT_HEAD Committed STAILQ_INSERT_TAIL Committed STAILQ_INSERT_AFTER Committed STAILQ_REMOVE_HEAD Committed STAILQ_REMOVE Committed STAILQ_FOREACH Committed STAILQ_EMPTY Committed STAILQ_FIRST Committed STAILQ_NEXT Committed SIMPLEQ_HEAD Committed SIMPLEQ_ENTRY Committed SIMPLEQ_INIT Committed SIMPLEQ_INSERT_HEAD Committed SIMPLEQ_INSERT_TAIL Committed SIMPLEQ_INSERT_AFTER Committed SIMPLEQ_REMOVE_HEAD Committed SIMPLEQ_REMOVE Committed SIMPLEQ_FOREACH Committed SIMPLEQ_EMPTY Committed SIMPLEQ_FIRST Committed SIMPLEQ_NEXT Committed TAILQ_HEAD Committed TAILQ_ENTRY Committed TAILQ_INIT Committed TAILQ_INSERT_HEAD Committed TAILQ_INSERT_TAIL Committed TAILQ_INSERT_AFTER Committed TAILQ_INSERT_BEFORE Committed TAILQ_REMOVE Committed TAILQ_FOREACH Committed TAILQ_FOREACH_REVERSE Committed TAILQ_EMPTY Committed TAILQ_FIRST Committed TAILQ_NEXT Committed TAILQ_LAST Committed TAILQ_PREV Committed CIRCLEQ_HEAD Committed CIRCLEQ_HEAD_INITIALIZER Committed CIRCLEQ_ENTRY Committed CIRCLEQ_INIT Committed CIRCLEQ_INSERT_AFTER Committed CIRCLEQ_INSERT_BEFORE Committed CIRCLEQ_INSERT_HEAD Committed CIRCLEQ_INSERT_TAIL Committed CIRCLEQ_REMOVE Committed CIRCLEQ_FOREACH Committed CIRCLEQ_FOREACH_REVERSE Committed CIRCLEQ_EMPTY Committed CIRCLEQ_FIRST Committed CIRCLEQ_LAST Committed CIRCLEQ_NEXT Committed CIRCLEQ_PREV Committed CIRCLEQ_LOOP_NEXT Committed CIRCLEQ_LOOP_PREV Committed From gdamore@sun.com Mon Jan 25 10:57:53 2010 Received: from dm-sfbay-01.sfbay.sun.com (dm-sfbay-01.SFBay.Sun.COM [129.145.155.118]) by sac.sfbay.sun.com (8.13.8+Sun/8.13.8) with ESMTP id o0PIvr5w021112 for ; Mon, 25 Jan 2010 10:57:53 -0800 (PST) Received: from sca-es-mail-2.sun.com (sca-es-mail-2.Sun.COM [192.18.43.133]) by dm-sfbay-01.sfbay.sun.com (8.13.8+Sun/8.13.8/ENSMAIL,v2.4) with ESMTP id o0PIvrxc028236 for ; Mon, 25 Jan 2010 10:57:53 -0800 (PST) Received: from fe-sfbay-09.sun.com ([192.18.43.129]) by sca-es-mail-2.sun.com (8.13.7+Sun/8.12.9) with ESMTP id o0PIvmeL009347 for ; Mon, 25 Jan 2010 10:57:48 -0800 (PST) MIME-version: 1.0 Content-transfer-encoding: 7BIT Content-type: text/plain; CHARSET=US-ASCII; format=flowed Received: from conversion-daemon.fe-sfbay-09.sun.com by fe-sfbay-09.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) id <0KWT00600GFZFN00@fe-sfbay-09.sun.com> for psarc-ext@sac.sfbay.sun.com; Mon, 25 Jan 2010 10:57:47 -0800 (PST) Received: from [192.168.251.11] ([unknown] [76.93.15.33]) by fe-sfbay-09.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) with ESMTPSA id <0KWT00KPCGO3BL90@fe-sfbay-09.sun.com> for psarc-ext@sac.sfbay.sun.com; Mon, 25 Jan 2010 10:57:44 -0800 (PST) Date: Mon, 25 Jan 2010 10:57:38 -0800 From: "Garrett D'Amore" Subject: Re: BSD List Interfaces [PSARC/2010/028 FastTrack timeout 02/01/2010] In-reply-to: <4B5DCAFD.1070504@Sun.COM> Sender: Garrett.Damore@sun.com To: Darren Reed Cc: psarc-ext Message-id: <4B5DE9A2.7040007@sun.com> References: <4B5DCAFD.1070504@Sun.COM> User-Agent: Thunderbird 2.0.0.23 (X11/20091013) Status: RO Content-Length: 6951 Looks reasonable. Will you also be providing a section 9f man page for kernel/driver developers? - Garrett Darren Reed wrote: > Introduction > ============ > As part of an earlier project, the macros created for 4.4BSD were > added to the system as part of the project's implementation. This > case seeks to document those interfaces and to make them available > for wider use on Solaris. The interfaces included as a part of this > case provide an easy to use, type safe, implementation of linked > lists and queues. In addition to providing the aforementioned > interfaces to internal developers, the delivery of the interfaces > in this case has increased the compatibility of Open/Solaris with > open source applications from other platforms. > > A man page can be found within the case directory. > > The man page and implementation both originate from NetBSD. > > This case seeks patch binding. > > Details > ======= > The current implementation of the BSD macros for supporting both list > and queue data structures is found within /usr/include/sys/queue.h. > The filename and location have been mirrored on Solaris. This file > introduces the following types of data structures: > > * single linked list > * double linked list > * tail queue & singly linked tail queue > * simple queue > * circular queue > > Single Linked List > ------------------ > A singly-linked list is headed by a single forward pointer. The > elements are singly linked for minimum space and pointer manipulation > overhead at the expense of O(n) removal for arbitrary elements. New > elements can be added to the list after an existing element or at the > head of the list. Elements being removed from the head of the list > should use the explicit macro for this purpose for optimum > efficiency. A singly-linked list may only be traversed in the forward > direction. Singly-linked lists are ideal for applications with large > datasets and few or no removals or for implementing a LIFO queue. > > Double Linked List > ------------------ > A list is headed by a single forward pointer (or an array of forward > pointers for a hash table header). The elements are doubly 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 or at the head of the list. A list > may only be traversed in the forward direction. > > Simple Queue > ------------ > A simple queue is headed by a pair of pointers, one the head of the > list and the other to the tail of the list. The elements are singly > linked to save space, so elements can only be removed from the > head of the list. New elements can be added to the list after > an existing element, at the head of the list, or at the end of the > list. A simple queue may only be traversed in the forward direction. > > Tail queue > ---------- > A tail 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 > 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. > > Circle Queue > ------------ > 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 > 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 circle queue may be traversed in either direction, but has a more > complex end of list detection. > > Interfaces > ========== > Committed > LIST_HEAD Committed > LIST_ENTRY Committed > LIST_INIT Committed > LIST_INSERT_AFTER Committed > LIST_INSERT_BEFORE Committed > LIST_INSERT_HEAD Committed > LIST_REMOVE Committed > LIST_FOREACH Committed > LIST_EMPTY Committed > LIST_FIRST Committed > LIST_NEXT Committed > SLIST_HEAD Committed > SLIST_ENTRY Committed > SLIST_INIT Committed > SLIST_INSERT_AFTER Committed > SLIST_INSERT_HEAD Committed > SLIST_REMOVE_HEAD Committed > SLIST_REMOVE Committed > SLIST_FOREACH Committed > SLIST_EMPTY Committed > SLIST_FIRST Committed > SLIST_NEXT Committed > STAILQ_HEAD Committed > STAILQ_ENTRY Committed > STAILQ_INIT Committed > STAILQ_INSERT_HEAD Committed > STAILQ_INSERT_TAIL Committed > STAILQ_INSERT_AFTER Committed > STAILQ_REMOVE_HEAD Committed > STAILQ_REMOVE Committed > STAILQ_FOREACH Committed > STAILQ_EMPTY Committed > STAILQ_FIRST Committed > STAILQ_NEXT Committed > SIMPLEQ_HEAD Committed > SIMPLEQ_ENTRY Committed > SIMPLEQ_INIT Committed > SIMPLEQ_INSERT_HEAD Committed > SIMPLEQ_INSERT_TAIL Committed > SIMPLEQ_INSERT_AFTER Committed > SIMPLEQ_REMOVE_HEAD Committed > SIMPLEQ_REMOVE Committed > SIMPLEQ_FOREACH Committed > SIMPLEQ_EMPTY Committed > SIMPLEQ_FIRST Committed > SIMPLEQ_NEXT Committed > TAILQ_HEAD Committed > TAILQ_ENTRY Committed > TAILQ_INIT Committed > TAILQ_INSERT_HEAD Committed > TAILQ_INSERT_TAIL Committed > TAILQ_INSERT_AFTER Committed > TAILQ_INSERT_BEFORE Committed > TAILQ_REMOVE Committed > TAILQ_FOREACH Committed > TAILQ_FOREACH_REVERSE Committed > TAILQ_EMPTY Committed > TAILQ_FIRST Committed > TAILQ_NEXT Committed > TAILQ_LAST Committed > TAILQ_PREV Committed > CIRCLEQ_HEAD Committed > CIRCLEQ_HEAD_INITIALIZER Committed > CIRCLEQ_ENTRY Committed > CIRCLEQ_INIT Committed > CIRCLEQ_INSERT_AFTER Committed > CIRCLEQ_INSERT_BEFORE Committed > CIRCLEQ_INSERT_HEAD Committed > CIRCLEQ_INSERT_TAIL Committed > CIRCLEQ_REMOVE Committed > CIRCLEQ_FOREACH Committed > CIRCLEQ_FOREACH_REVERSE Committed > CIRCLEQ_EMPTY Committed > CIRCLEQ_FIRST Committed > CIRCLEQ_LAST Committed > CIRCLEQ_NEXT Committed > CIRCLEQ_PREV Committed > CIRCLEQ_LOOP_NEXT Committed > CIRCLEQ_LOOP_PREV Committed > From carlsonj@workingcode.com Mon Jan 25 11:50:10 2010 Received: from dm-sfbay-02.sfbay.sun.com (dm-sfbay-02.SFBay.Sun.COM [129.146.11.31]) by sac.sfbay.sun.com (8.13.8+Sun/8.13.8) with ESMTP id o0PJoA0E022011 for ; Mon, 25 Jan 2010 11:50:10 -0800 (PST) Received: from sca-ea-mail-1.sun.com (sca-ea-mail-1.Sun.COM [192.18.43.24]) by dm-sfbay-02.sfbay.sun.com (8.13.8+Sun/8.13.8/ENSMAIL,v2.4) with ESMTP id o0PJoAI7025409 for ; Mon, 25 Jan 2010 11:50:10 -0800 (PST) Received: from relay41i.sun.com ([192.5.209.70]) by sca-ea-mail-1.sun.com (8.13.7+Sun/8.12.9) with ESMTP id o0PJf5q3016665 for ; Mon, 25 Jan 2010 19:50:05 GMT Received: from mmp42es.mmp.us.syntegra.com ([160.41.221.11] [160.41.221.11]) by relay41i.sun.com with ESMTP id BT-MMP-5500488 for psarc-ext@sac.sfbay.sun.com; Mon, 25 Jan 2010 19:49:58 Z Received: from relay42i.sun.com (relay42i.sun.com [192.5.209.72]) by mmp42es.mmp.us.syntegra.com with ESMTP id BT-MMP-11064304; Mon, 25 Jan 2010 19:49:58 Z Received: from carlson.workingcode.com ([75.150.68.97] [75.150.68.97]) by relay4i.sun.com with ESMTP id BT-MMP-45793328; Mon, 25 Jan 2010 19:49:57 Z Received: from [10.50.23.149] (gate.abinitio.com [65.170.40.132]) (authenticated bits=0) by carlson.workingcode.com (8.14.2+Sun/8.14.3) with ESMTP id o0PJnuFo022826 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Mon, 25 Jan 2010 14:49:56 -0500 (EST) Message-ID: <4B5DF5E3.8080005@workingcode.com> Date: Mon, 25 Jan 2010 14:49:55 -0500 From: James Carlson User-Agent: Thunderbird 2.0.0.22 (X11/20090605) To: Darren Reed CC: psarc-ext Subject: Re: BSD List Interfaces [PSARC/2010/028 FastTrack timeout 02/01/2010] References: <4B5DCAFD.1070504@Sun.COM> In-Reply-To: <4B5DCAFD.1070504@Sun.COM> X-Brightmail-Tracker: AAAAAA== X-DCC-sonic.net-Metrics: carlson; whitelist X-Antispam: No, score=3.2/5.0, scanned in 0.158sec at (localhost [127.0.0.1]) by smf-spamd v1.3.1 - http://smfs.sf.net/ MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Status: RO Content-Length: 545 Darren Reed wrote: > * single linked list > * double linked list > * tail queue & singly linked tail queue > * simple queue > * circular queue Looks good. Are these intended as both kernel and user or just kernel only (as might imply)? Perhaps not strictly architectural in nature, but are any mdb walkers and/or dcmds provided to help out when using these, as we have for the native list_t mechanism? If not, you may want to consider investigating those. -- James Carlson 42.703N 71.076W From Darren.Reed@Sun.COM Mon Jan 25 15:33:18 2010 Received: from dm-sfbay-02.sfbay.sun.com (dm-sfbay-02.SFBay.Sun.COM [129.146.11.31]) by sac.sfbay.sun.com (8.13.8+Sun/8.13.8) with ESMTP id o0PNXIru027120 for ; Mon, 25 Jan 2010 15:33:18 -0800 (PST) Received: from gmp-eb-inf-2.sun.com (gmp-eb-inf-2.EU.Sun.COM [192.18.6.24]) by dm-sfbay-02.sfbay.sun.com (8.13.8+Sun/8.13.8/ENSMAIL,v2.4) with ESMTP id o0PNXGwl016755 for ; Mon, 25 Jan 2010 15:33:17 -0800 (PST) Received: from fe-emea-10.sun.com (gmp-eb-lb-1-fe1.eu.sun.com [192.18.6.7] (may be forged)) by gmp-eb-inf-2.sun.com (8.13.7+Sun/8.12.9) with ESMTP id o0PNXBJD004285 for ; Mon, 25 Jan 2010 23:33:11 GMT MIME-version: 1.0 Content-transfer-encoding: 7BIT Content-type: text/plain; CHARSET=US-ASCII; format=flowed Received: from conversion-daemon.fe-emea-10.sun.com by fe-emea-10.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) id <0KWT00100T6X5U00@fe-emea-10.sun.com> for psarc-ext@sac.sfbay.sun.com; Mon, 25 Jan 2010 23:32:46 +0000 (GMT) Received: from [192.168.2.102] ([unknown] [88.100.101.51]) by fe-emea-10.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) with ESMTPSA id <0KWT00EFQTEME550@fe-emea-10.sun.com> for psarc-ext@sac.sfbay.sun.com; Mon, 25 Jan 2010 23:32:46 +0000 (GMT) Date: Tue, 26 Jan 2010 00:32:44 +0100 From: Darren Reed Subject: Re: BSD List Interfaces [PSARC/2010/028 FastTrack timeout 02/01/2010] In-reply-to: <4B5DF5E3.8080005@workingcode.com> Sender: Darren.Reed@Sun.COM To: James Carlson Cc: psarc-ext Message-id: <4B5E2A1C.5030405@Sun.COM> References: <4B5DCAFD.1070504@Sun.COM> <4B5DF5E3.8080005@workingcode.com> User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.1.5) Gecko/20091204 Thunderbird/3.0 Status: RO Content-Length: 713 On 25/01/2010 8:49 PM, James Carlson wrote: > Darren Reed wrote: > >> * single linked list >> * double linked list >> * tail queue& singly linked tail queue >> * simple queue >> * circular queue >> > Looks good. > > Are these intended as both kernel and user or just kernel only (as > might imply)? > The interfaces as presented can be used for both user and kernel. > Perhaps not strictly architectural in nature, but are any mdb walkers > and/or dcmds provided to help out when using these, as we have for the > native list_t mechanism? If not, you may want to consider investigating > those. > Current there are no mdb walkers or dcmds. Seems like a worthy RFE or two. Darren From Darren.Reed@Sun.COM Mon Jan 25 15:35:19 2010 Received: from dm-sfbay-02.sfbay.sun.com (dm-sfbay-02.SFBay.Sun.COM [129.146.11.31]) by sac.sfbay.sun.com (8.13.8+Sun/8.13.8) with ESMTP id o0PNZJw4027134 for ; Mon, 25 Jan 2010 15:35:19 -0800 (PST) Received: from gmp-eb-inf-2.sun.com (gmp-eb-inf-2.EU.Sun.COM [192.18.6.24]) by dm-sfbay-02.sfbay.sun.com (8.13.8+Sun/8.13.8/ENSMAIL,v2.4) with ESMTP id o0PNZILF017648 for ; Mon, 25 Jan 2010 15:35:18 -0800 (PST) Received: from fe-emea-09.sun.com (gmp-eb-lb-1-fe1.eu.sun.com [192.18.6.7] (may be forged)) by gmp-eb-inf-2.sun.com (8.13.7+Sun/8.12.9) with ESMTP id o0PNZCS2004331 for ; Mon, 25 Jan 2010 23:35:12 GMT MIME-version: 1.0 Content-transfer-encoding: 7BIT Content-type: text/plain; CHARSET=US-ASCII; format=flowed Received: from conversion-daemon.fe-emea-09.sun.com by fe-emea-09.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) id <0KWT00M00T93E200@fe-emea-09.sun.com> for psarc-ext@sac.sfbay.sun.com; Mon, 25 Jan 2010 23:34:49 +0000 (GMT) Received: from [192.168.2.102] ([unknown] [88.100.101.51]) by fe-emea-09.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) with ESMTPSA id <0KWT00ECYTI0T450@fe-emea-09.sun.com> for psarc-ext@sac.sfbay.sun.com; Mon, 25 Jan 2010 23:34:49 +0000 (GMT) Date: Tue, 26 Jan 2010 00:34:46 +0100 From: Darren Reed Subject: Re: BSD List Interfaces [PSARC/2010/028 FastTrack timeout 02/01/2010] In-reply-to: <4B5DE9A2.7040007@sun.com> Sender: Darren.Reed@Sun.COM To: "Garrett D'Amore" Cc: psarc-ext Message-id: <4B5E2A96.7070003@Sun.COM> References: <4B5DCAFD.1070504@Sun.COM> <4B5DE9A2.7040007@sun.com> User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.1.5) Gecko/20091204 Thunderbird/3.0 Status: RO Content-Length: 7264 I can't see why not - afterall, the contents of the page will be largely the same. Darren On 25/01/2010 7:57 PM, Garrett D'Amore wrote: > Looks reasonable. Will you also be providing a section 9f man page > for kernel/driver developers? > > - Garrett > > Darren Reed wrote: >> Introduction >> ============ >> As part of an earlier project, the macros created for 4.4BSD were >> added to the system as part of the project's implementation. This >> case seeks to document those interfaces and to make them available >> for wider use on Solaris. The interfaces included as a part of this >> case provide an easy to use, type safe, implementation of linked >> lists and queues. In addition to providing the aforementioned >> interfaces to internal developers, the delivery of the interfaces >> in this case has increased the compatibility of Open/Solaris with >> open source applications from other platforms. >> >> A man page can be found within the case directory. >> >> The man page and implementation both originate from NetBSD. >> >> This case seeks patch binding. >> >> Details >> ======= >> The current implementation of the BSD macros for supporting both list >> and queue data structures is found within /usr/include/sys/queue.h. >> The filename and location have been mirrored on Solaris. This file >> introduces the following types of data structures: >> >> * single linked list >> * double linked list >> * tail queue & singly linked tail queue >> * simple queue >> * circular queue >> >> Single Linked List >> ------------------ >> A singly-linked list is headed by a single forward pointer. The >> elements are singly linked for minimum space and pointer manipulation >> overhead at the expense of O(n) removal for arbitrary elements. New >> elements can be added to the list after an existing element or at the >> head of the list. Elements being removed from the head of the list >> should use the explicit macro for this purpose for optimum >> efficiency. A singly-linked list may only be traversed in the forward >> direction. Singly-linked lists are ideal for applications with large >> datasets and few or no removals or for implementing a LIFO queue. >> >> Double Linked List >> ------------------ >> A list is headed by a single forward pointer (or an array of forward >> pointers for a hash table header). The elements are doubly 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 or at the head of the list. A list >> may only be traversed in the forward direction. >> >> Simple Queue >> ------------ >> A simple queue is headed by a pair of pointers, one the head of the >> list and the other to the tail of the list. The elements are singly >> linked to save space, so elements can only be removed from the >> head of the list. New elements can be added to the list after >> an existing element, at the head of the list, or at the end of the >> list. A simple queue may only be traversed in the forward direction. >> >> Tail queue >> ---------- >> A tail 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 >> 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. >> >> Circle Queue >> ------------ >> 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 >> 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 circle queue may be traversed in either direction, but has a more >> complex end of list detection. >> >> Interfaces >> ========== >> Committed >> LIST_HEAD Committed >> LIST_ENTRY Committed >> LIST_INIT Committed >> LIST_INSERT_AFTER Committed >> LIST_INSERT_BEFORE Committed >> LIST_INSERT_HEAD Committed >> LIST_REMOVE Committed >> LIST_FOREACH Committed >> LIST_EMPTY Committed >> LIST_FIRST Committed >> LIST_NEXT Committed >> SLIST_HEAD Committed >> SLIST_ENTRY Committed >> SLIST_INIT Committed >> SLIST_INSERT_AFTER Committed >> SLIST_INSERT_HEAD Committed >> SLIST_REMOVE_HEAD Committed >> SLIST_REMOVE Committed >> SLIST_FOREACH Committed >> SLIST_EMPTY Committed >> SLIST_FIRST Committed >> SLIST_NEXT Committed >> STAILQ_HEAD Committed >> STAILQ_ENTRY Committed >> STAILQ_INIT Committed >> STAILQ_INSERT_HEAD Committed >> STAILQ_INSERT_TAIL Committed >> STAILQ_INSERT_AFTER Committed >> STAILQ_REMOVE_HEAD Committed >> STAILQ_REMOVE Committed >> STAILQ_FOREACH Committed >> STAILQ_EMPTY Committed >> STAILQ_FIRST Committed >> STAILQ_NEXT Committed >> SIMPLEQ_HEAD Committed >> SIMPLEQ_ENTRY Committed >> SIMPLEQ_INIT Committed >> SIMPLEQ_INSERT_HEAD Committed >> SIMPLEQ_INSERT_TAIL Committed >> SIMPLEQ_INSERT_AFTER Committed >> SIMPLEQ_REMOVE_HEAD Committed >> SIMPLEQ_REMOVE Committed >> SIMPLEQ_FOREACH Committed >> SIMPLEQ_EMPTY Committed >> SIMPLEQ_FIRST Committed >> SIMPLEQ_NEXT Committed >> TAILQ_HEAD Committed >> TAILQ_ENTRY Committed >> TAILQ_INIT Committed >> TAILQ_INSERT_HEAD Committed >> TAILQ_INSERT_TAIL Committed >> TAILQ_INSERT_AFTER Committed >> TAILQ_INSERT_BEFORE Committed >> TAILQ_REMOVE Committed >> TAILQ_FOREACH Committed >> TAILQ_FOREACH_REVERSE Committed >> TAILQ_EMPTY Committed >> TAILQ_FIRST Committed >> TAILQ_NEXT Committed >> TAILQ_LAST Committed >> TAILQ_PREV Committed >> CIRCLEQ_HEAD Committed >> CIRCLEQ_HEAD_INITIALIZER Committed >> CIRCLEQ_ENTRY Committed >> CIRCLEQ_INIT Committed >> CIRCLEQ_INSERT_AFTER Committed >> CIRCLEQ_INSERT_BEFORE Committed >> CIRCLEQ_INSERT_HEAD Committed >> CIRCLEQ_INSERT_TAIL Committed >> CIRCLEQ_REMOVE Committed >> CIRCLEQ_FOREACH Committed >> CIRCLEQ_FOREACH_REVERSE Committed >> CIRCLEQ_EMPTY Committed >> CIRCLEQ_FIRST Committed >> CIRCLEQ_LAST Committed >> CIRCLEQ_NEXT Committed >> CIRCLEQ_PREV Committed >> CIRCLEQ_LOOP_NEXT Committed >> CIRCLEQ_LOOP_PREV Committed >> > From Darren.Reed@Sun.COM Fri Feb 5 08:48:02 2010 Received: from dm-sfbay-02.sfbay.sun.com (dm-sfbay-02.SFBay.Sun.COM [129.146.11.31]) by sac.sfbay.sun.com (8.13.8+Sun/8.13.8) with ESMTP id o15Gm2Dr004452 for ; Fri, 5 Feb 2010 08:48:02 -0800 (PST) Received: from gmp-eb-inf-1.sun.com (gmp-eb-inf-1.EU.Sun.COM [192.18.6.21]) by dm-sfbay-02.sfbay.sun.com (8.13.8+Sun/8.13.8/ENSMAIL,v2.4) with ESMTP id o15Gm1Z8005145 for ; Fri, 5 Feb 2010 08:48:02 -0800 (PST) Received: from fe-emea-09.sun.com (gmp-eb-lb-1-fe1.eu.sun.com [192.18.6.7] (may be forged)) by gmp-eb-inf-1.sun.com (8.13.7+Sun/8.12.9) with ESMTP id o15Gluev001449 for ; Fri, 5 Feb 2010 16:47:56 GMT MIME-version: 1.0 Content-transfer-encoding: 7BIT Content-type: text/plain; CHARSET=US-ASCII; format=flowed Received: from conversion-daemon.fe-emea-09.sun.com by fe-emea-09.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) id <0KXD00100NO0DU00@fe-emea-09.sun.com> for psarc-ext@sac.sfbay.sun.com; Fri, 05 Feb 2010 16:47:34 +0000 (GMT) Received: from [129.157.19.238] ([unknown] [129.157.19.238]) by fe-emea-09.sun.com (Sun Java(tm) System Messaging Server 7u2-7.04 64bit (built Jul 2 2009)) with ESMTPSA id <0KXD00J09NZAWD50@fe-emea-09.sun.com> for psarc-ext@sac.sfbay.sun.com; Fri, 05 Feb 2010 16:47:34 +0000 (GMT) Date: Fri, 05 Feb 2010 17:47:22 +0100 From: Darren Reed Subject: Re: BSD List Interfaces [PSARC/2010/028 FastTrack timeout 02/01/2010] In-reply-to: <4B5DCAFD.1070504@Sun.COM> Sender: Darren.Reed@Sun.COM To: psarc-ext Message-id: <4B6C4B9A.9060209@Sun.COM> References: <4B5DCAFD.1070504@Sun.COM> User-Agent: Thunderbird 2.0.0.23 (Windows/20090812) Status: RO Content-Length: 193 Now that the timeout has expired for this case, I'm marking it approved. The only change to this case will be the addition of a man page delivered to section 9 as well as section 3. Darren