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
> ==========
> <sys/queue.h> 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
>
