Index: doc/ChangeLog
===================================================================
--- doc/ChangeLog	(revision ef94f04fec7376016e1d9a65b319e646a921e213)
+++ doc/ChangeLog	(revision 5396467fb83571882f462b929c99965b2eaf6be4)
@@ -1,2 +1,10 @@
+2008-07-09	Chris Johns <chrisj@rtems.org>
+
+	* doc/user/chains.t: New.
+
+	* doc/ada_user/ada_user.texi, doc/user/Makefile.am,
+	doc/user/c_user.texi, doc/user/dirstat.texi: Updated for the
+	chains documentation.
+
 2008-06-20	Joel Sherrill <joel.sherrill@OARcorp.com>
 
Index: doc/ada_user/ada_user.texi
===================================================================
--- doc/ada_user/ada_user.texi	(revision ef94f04fec7376016e1d9a65b319e646a921e213)
+++ doc/ada_user/ada_user.texi	(revision 5396467fb83571882f462b929c99965b2eaf6be4)
@@ -108,4 +108,5 @@
 @include user/cpuuse.texi
 @include user/object.texi
+@include user/chains.texi
 @include user/dirstat.texi
 @include example.texi
@@ -146,4 +147,5 @@
 * CPU Usage Statistics::
 * Object Services::
+* Chains::
 * Directive Status Codes::
 * Example Application::
Index: doc/user/Makefile.am
===================================================================
--- doc/user/Makefile.am	(revision ef94f04fec7376016e1d9a65b319e646a921e213)
+++ doc/user/Makefile.am	(revision 5396467fb83571882f462b929c99965b2eaf6be4)
@@ -19,5 +19,5 @@
     signal.texi part.texi region.texi dpmem.texi io.texi fatal.texi \
     schedule.texi rtmon.texi barrier.texi bsp.texi userext.texi conf.texi \
-    mp.texi stackchk.texi cpuuse.texi object.texi
+    mp.texi stackchk.texi cpuuse.texi object.texi chains.texi
 
 COMMON_FILES += $(top_srcdir)/common/cpright.texi
@@ -178,7 +178,12 @@
 	$(BMENU2) -p "CPU Usage Statistics cpu_usage_reset - Reset CPU Usage Statistics" \
 	    -u "Top" \
+	    -n "Chains" < $< > $@
+
+chains.texi: chains.t
+	$(BMENU2) -p "Object Services OBJECT_GET_CLASS_INFORMATION - Obtain Class Information" \
+	    -u "Top" \
 	    -n "Directive Status Codes" < $< > $@
 
-EXTRA_DIST = bsp.t clock.t concepts.t cpuuse.t datatypes.t conf.t dpmem.t \
+EXTRA_DIST = bsp.t clock.t chains.t concepts.t cpuuse.t datatypes.t conf.t dpmem.t \
     event.t fatal.t init.t intr.t io.t mp.t msg.t overview.t part.t region.t \
     rtmon.t sem.t schedule.t signal.t stackchk.t task.t timer.t userext.t \
Index: doc/user/c_user.texi
===================================================================
--- doc/user/c_user.texi	(revision ef94f04fec7376016e1d9a65b319e646a921e213)
+++ doc/user/c_user.texi	(revision 5396467fb83571882f462b929c99965b2eaf6be4)
@@ -107,4 +107,5 @@
 @include cpuuse.texi
 @include object.texi
+@include chains.texi
 @include dirstat.texi
 @include example.texi
@@ -145,4 +146,5 @@
 * CPU Usage Statistics::
 * Object Services::
+* Chains::
 * Directive Status Codes::
 * Example Application::
Index: doc/user/chains.t
===================================================================
--- doc/user/chains.t	(revision 5396467fb83571882f462b929c99965b2eaf6be4)
+++ doc/user/chains.t	(revision 5396467fb83571882f462b929c99965b2eaf6be4)
@@ -0,0 +1,681 @@
+@c
+@c  COPYRIGHT (c) 1988-2008.
+@c  On-Line Applications Research Corporation (OAR).
+@c  All rights reserved.
+@c
+@c  $Id$
+@c
+
+@chapter Chains
+
+@cindex chains
+
+@section Introduction
+
+The Chains API is an interface to the Super Core (score) chain
+implementation. The Super Core uses chains for all list type
+functions. This includes wait queues and task queues. The Chains API
+provided by RTEMS is:
+
+@itemize @bullet
+@c build_id
+@item @code{@value{DIRPREFIX}chain_node} - Chain node used in user objects
+@item @code{@value{DIRPREFIX}chain_control} - Chain control node
+@item @code{@value{DIRPREFIX}chain_initialize_empty} - initialize the chain as empty
+@item @code{@value{DIRPREFIX}chain_is_null_node} - Is the node NULL ?
+@item @code{@value{DIRPREFIX}chain_head} - Return the chain's head
+@item @code{@value{DIRPREFIX}chain_tail} - Return the chain's tail
+@item @code{@value{DIRPREFIX}chain_are_nodes_equal} - Are the node's equal ?
+@item @code{@value{DIRPREFIX}chain_is_empty} - Is the chain empty ?
+@item @code{@value{DIRPREFIX}chain_is_first} - Is the Node the first in the chain ?
+@item @code{@value{DIRPREFIX}chain_is_last} - Is the Node the last in the chain ? 
+@item @code{@value{DIRPREFIX}chain_has_only_one_node} - Does the node have one node ?
+@item @code{@value{DIRPREFIX}chain_is_head} - Is the node the head ?
+@item @code{@value{DIRPREFIX}chain_is_tail} - Is the node the tail ?
+@item @code{@value{DIRPREFIX}chain_extract} - Extract the node from the chain ?
+@item @code{@value{DIRPREFIX}chain_get} - Return the first node on the chain ?
+@item @code{@value{DIRPREFIX}chain_insert} - Insert the node into the chain ?
+@item @code{@value{DIRPREFIX}chain_append} - Append the node to chain ?
+@item @code{@value{DIRPREFIX}chain_prepend} - Prepend the node to the end of the chain ?
+@end itemize
+
+@section Background
+
+The Chains API maps to the Super Core Chains API. Chains are
+implemented as a double linked list of nodes anchored to a control
+node. The list starts at the control node and is terminated at the
+control node. A node has previous and next pointers. Being a double
+linked list nodes can be inserted and removed without the need to
+travse the chain.
+
+Chains have a small memory footprint and can be used in interrupt
+service routines and are thread safe in a multi-threaded
+environment. The directives list which operations disable interrupts.
+
+Chains are very useful in Board Support packages and applications.
+
+@subsection Nodes
+
+A chain is made up from nodes that orginate from a chain control
+object. A node is of type @code{@value{DIRPREFIX}chain_node}. The node
+is designed to be part of a user data structure and a cast is used to
+move from the node address to the user data structure address. For
+example:
+
+@example
+typedef struct foo
+@{
+  @value{DIRPREFIX}chain_node node;
+  int              bar;
+@} foo;
+@end example
+
+creates a type @code{foo} that can be placed on a chain. To get the
+foo structure from the list you perform the following:
+
+@example
+foo* get_foo(@value{DIRPREFIX}chain_control* control)
+@{
+  return (foo*) @value{DIRPREFIX}chain_get(control);
+@}
+@end example
+
+The node is placed at the start of the user's structure to allow the
+node address on the chain to be easly cast to the user's structure
+address. 
+
+@subsection Controls
+
+A chain is anchored with a control object. Chain control provide the
+user with access to the nodes on the chain. The control is head of the
+node.
+
+
+@example
+       Control
+        next ------------------------->
+        permanent_null <--------------- NODE
+        last ------------------------->
+@end example
+
+The implementation does not require special checks for manipulating
+the first and last nodes on the chain. To accomplish this the
+@code{@value{DIRPREFIX}chain_control} structure is treated as two
+overlapping @code{@value{DIRPREFIX}chain_node} structures.  The
+permanent head of the chain overlays a node structure on the first and
+@code{permanent_null} fields.  The @code{permanent_tail} of the chain
+overlays a node structure on the @code{permanent_null} and @code{last}
+elements of the structure.
+
+@section Operations
+
+@subsection Multi-threading
+
+Chains are designed to be used in a multi-threading environment. The
+directives list which operations mask interrupts. Chains supports
+tasks and interrupt service routines appending and extracting nodes
+with out the need for extra locks. Chains how-ever cannot insure the
+integrity of a chain for all operations. This is the responsibility of
+the user. For example an interrupt service routine extracting nodes
+while a task is iterating over the chain can have unpredictable
+results.
+
+@subsection Creating a Chain
+
+To create a chain you need to declare a chain control then add nodes
+to the control. Consider a user structure and chain control:
+
+@example
+typedef struct foo
+@{
+  @value{DIRPREFIX}chain_node node;
+  uint8_t char*    data;
+@} foo;
+
+@value{DIRPREFIX}chain_control chain;
+@end example
+
+Add nodes with the following code:
+
+@example
+@value{DIRPREFIX}chain_initialize_empty (&chain);
+
+for (i = 0; i < count; i++)
+@{
+  foo* bar = malloc (sizeof (foo));
+  if (!foo)
+    return -1;
+  bar->data = malloc (size);
+  @value{DIRPREFIX}chain_append (&chain, &bar->node);
+@}
+@end example
+
+The chain is initialized and the nodes allocated and appended to the
+chain. This is an example of a pool of buffers.
+
+@subsection Iterating a Chain
+
+@cindex chain iterate
+
+Iterating a chain is a common function. The example shows how to
+iterate the buffer pool chain created in the last section to find
+buffers starting with a specific string. If the buffer is located it is
+extracted from the chain and placed on another chain:
+
+@example
+void foobar (const char*          match,
+             @value{DIRPREFIX}chain_control* chain,
+             @value{DIRPREFIX}chain_control* out)
+@{
+  @value{DIRPREFIX}chain_node* node;
+  foo*              bar;
+
+  @value{DIRPREFIX}chain_initialize_empty (out);
+
+  node = chain->first;
+
+  while (!@value{DIRPREFIX}chain_is_tail (chain, node))
+  @{
+    bar = (foo*) node;
+
+    if (strcmp (match, bar->data) == 0)
+    @{
+      @value{DIRPREFIX}chain_node* next_node = node->next;
+      @value{DIRPREFIX}chain_extract (node);
+      @value{DIRPREFIX}chain_append (out, node);
+      node = next_node; 
+    @}
+  @}
+@}
+@end example
+
+@section Directives
+
+The section details the Chains directives.
+
+@c
+@c Initialize this Chain as Empty
+@c
+@page
+@subsection Initialise Empty
+
+@cindex chain initialise empty
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_initialize_empty
+@example
+void @value{DIRPREFIX}chain_initialize_empty(
+  @value{DIRPREFIX}chain_control *the_chain
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+Returns nothing.
+
+@subheading DESCRIPTION:
+
+This function take in a pointer to a chain control and initializes it
+to empty.
+
+@subheading NOTES:
+
+This call will discard any nodes on the chain.
+
+@c
+@c
+@c
+@page
+@subsection Is Null Node ?
+
+@cindex chain is node null
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_is_null_node
+@example
+boolean @value{DIRPREFIX}chain_is_null_node(
+  const @value{DIRPREFIX}chain_node *the_node
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+Returns TRUE is the node point is NULL and FALSE if the node is not
+NULL.
+
+@subheading DESCRIPTION:
+
+Tests the node to see if it is a NULL returning true if a null.
+
+@c
+@c
+@c
+@page
+@subsection Head
+
+@cindex chain get head
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_head
+@example
+@value{DIRPREFIX}chain_node *@value{DIRPREFIX}chain_head(
+  @value{DIRPREFIX}chain_control *the_chain
+)
+@end example
+@end ifset
+
+@subheading RETURNS
+
+Returns the permanent head node of the chain.
+
+@subheading DESCRIPTION:
+
+This function returns a pointer to the first node on the chain.
+
+@c
+@c
+@c
+@page
+@subsection Tail
+
+@cindex chain get tail
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_tail
+@example
+@value{DIRPREFIX}chain_node *@value{DIRPREFIX}chain_tail(
+  @value{DIRPREFIX}chain_control *the_chain
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+Returns the permanent tail node of the chain.
+
+@subheading DESCRIPTION:
+
+This function returns a pointer to the last node on the chain.
+
+@c
+@c
+@c
+@page
+@subsection Are Two Nodes Equal ?
+
+@cindex chare are nodes equal
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_are_nodes_equal
+@example
+boolean @value{DIRPREFIX}chain_are_nodes_equal(
+  const @value{DIRPREFIX}chain_node *left,
+  const @value{DIRPREFIX}chain_node *right
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+This function returns TRUE if the left node and the right node are
+equal, and FALSE otherwise.
+
+@subheading DESCRIPTION:
+
+This function returns TRUE if the left node and the right node are
+equal, and FALSE otherwise.
+
+@c
+@c
+@c
+@page
+@subsection Is the Chain Empty
+
+@cindex chain is chain empty
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_is_empty
+@example
+boolean @value{DIRPREFIX}chain_is_empty(
+  @value{DIRPREFIX}chain_control *the_chain
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+This function returns TRUE if there a no nodes on the chain and FALSE
+otherwise.
+
+@subheading DESCRIPTION:
+
+This function returns TRUE if there a no nodes on the chain and FALSE
+otherwise.
+
+@c
+@c
+@c
+@page
+@subsection Is this the First Node on the Chain ?
+
+@cindex chain is node the first
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_is_first
+@example
+boolean @value{DIRPREFIX}chain_is_first(
+  const @value{DIRPREFIX}chain_node *the_node
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+This function returns TRUE if the node is the first node on a chain
+and FALSE otherwise.
+
+@subheading DESCRIPTION:
+
+This function returns TRUE if the node is the first node on a chain
+and FALSE otherwise.
+
+@c
+@c
+@c
+@page
+@subsection Is this the Last Node on the Chain ?
+
+@cindex chain is node the last
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_is_last
+@example
+boolean @value{DIRPREFIX}chain_is_last(
+  const @value{DIRPREFIX}chain_node *the_node
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+This function returns TRUE if the node is the last node on a chain and
+FALSE otherwise.
+
+@subheading DESCRIPTION:
+
+This function returns TRUE if the node is the last node on a chain and
+FALSE otherwise.
+
+@c
+@c
+@c
+@page
+@subsection Does this Chain have only One Node ?
+
+@cindex chain only one node
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_has_only_one_node
+@example
+boolean @value{DIRPREFIX}chain_has_only_one_node(
+  const @value{DIRPREFIX}chain_control *the_chain
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+This function returns TRUE if there is only one node on the chain and
+FALSE otherwise.
+
+@subheading DESCRIPTION:
+
+This function returns TRUE if there is only one node on the chain and
+FALSE otherwise.
+
+@c
+@c
+@c
+@page
+@subsection Is this Node the Chain Head ?
+
+@cindex chain is node the head
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_is_head
+@example
+boolean @value{DIRPREFIX}chain_is_head(
+  @value{DIRPREFIX}chain_control    *the_chain,
+  @value{DIRPREFIX}const chain_node *the_node
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+This function returns TRUE if the node is the head of the chain and
+FALSE otherwise.
+
+@subheading DESCRIPTION:
+
+This function returns TRUE if the node is the head of the chain and
+FALSE otherwise.
+
+@c
+@c
+@c
+@page
+@subsection Is this Node the Chain Tail ?
+
+@cindex chain is node the tail
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_is_tail
+@example
+boolean @value{DIRPREFIX}chain_is_tail(
+  @value{DIRPREFIX}chain_control    *the_chain,
+  const @value{DIRPREFIX}chain_node *the_node
+)
+@end example
+@end ifset
+
+@subheading RETURNS
+
+This function returns TRUE if the node is the tail of the chain and
+FALSE otherwise.
+
+@subheading DESCRIPTION:
+
+This function returns TRUE if the node is the tail of the chain and
+FALSE otherwise.
+
+@c
+@c
+@c
+@page
+@subsection Extract a Node
+
+@cindex chain extract a node
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_extract
+@example
+void @value{DIRPREFIX}chain_extract(
+  @value{DIRPREFIX}chain_node *the_node
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+Returns nothing.
+
+@subheading DESCRIPTION:
+
+This routine extracts the node from the chain on which it resides.
+
+@subheading NOTES:
+
+Interrupts are disabled while extracting the node to ensure the
+atomicity of the operation.
+
+@c
+@c
+@c
+@page
+@subsection Get the First Node
+
+@cindex chain get first node
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_get
+@example
+@value{DIRPREFIX}chain_node *@value{DIRPREFIX}chain_get(
+  @value{DIRPREFIX}chain_control *the_chain
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+Returns a pointer a node. If a node was removed, then a pointer to
+that node is returned. If the chain was empty, then NULL is
+returned.
+
+@subheading DESCRIPTION:
+
+This function removes the first node from the chain and returns a
+pointer to that node.  If the chain is empty, then NULL is returned.
+
+@subheading NOTES:
+
+Interrupts are disabled while obtaining the node to ensure the
+atomicity of the operation.
+
+@c
+@c
+@c
+@page
+@subsection Insert a Node
+
+@cindex chain insert a node
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_insert
+@example
+void @value{DIRPREFIX}chain_insert(
+  @value{DIRPREFIX}chain_node *after_node,
+  @value{DIRPREFIX}chain_node *the_node
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+Returns nothing.
+
+@subheading DESCRIPTION:
+
+This routine inserts a node on a chain immediately following the
+specified node.
+
+@subheading NOTES:
+
+Interrupts are disabled during the insert to ensure the atomicity of
+the operation.
+
+@c
+@c
+@c
+@page
+@subsection Append a Node
+
+@cindex chain append a node
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_append
+@example
+void @value{DIRPREFIX}chain_append(
+  @value{DIRPREFIX}chain_control *the_chain,
+  @value{DIRPREFIX}chain_node    *the_node
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+Returns nothing.
+
+@subheading DESCRIPTION:
+
+This routine appends a node to the end of a chain.
+
+@subheading NOTES:
+
+Interrupts are disabled during the append to ensure the atomicity of
+the operation.
+
+@c
+@c
+@c
+@page
+@subsection Prepend a Node
+
+@cindex prepend node
+
+@subheading CALLING SEQUENCE:
+
+@ifset is-C
+@findex @value{DIRPREFIX}chain_prepend
+@example
+void @value{DIRPREFIX}chain_prepend(
+  @value{DIRPREFIX}chain_control *the_chain,
+  @value{DIRPREFIX}chain_node    *the_node
+);
+@end example
+@end ifset
+
+@subheading RETURNS
+
+Returns nothing.
+
+@subheading DESCRIPTION:
+
+This routine prepends a node to the front of the chain.
+
+@subheading NOTES:
+
+Interrupts are disabled during the prepend to ensure the atomicity of
+the operation.
Index: doc/user/dirstat.texi
===================================================================
--- doc/user/dirstat.texi	(revision ef94f04fec7376016e1d9a65b319e646a921e213)
+++ doc/user/dirstat.texi	(revision 5396467fb83571882f462b929c99965b2eaf6be4)
@@ -8,5 +8,5 @@
 
 @ifinfo
-@node Directive Status Codes, Example Application, Object Services OBJECT_GET_CLASS_INFORMATION - Obtain Class Information, Top
+@node Directive Status Codes, Example Application, Chains Prepend a Node, Top
 @end ifinfo
 @chapter Directive Status Codes
