diff options
Diffstat (limited to '')
| -rw-r--r-- | doc/ChangeLog | 8 | ||||
| -rw-r--r-- | doc/ada_user/ada_user.texi | 2 | ||||
| -rw-r--r-- | doc/user/Makefile.am | 9 | ||||
| -rw-r--r-- | doc/user/c_user.texi | 2 | ||||
| -rwxr-xr-x | doc/user/chains.t | 681 | ||||
| -rw-r--r-- | doc/user/dirstat.texi | 2 |
6 files changed, 701 insertions, 3 deletions
diff --git a/doc/ChangeLog b/doc/ChangeLog index 22ab2ad059..1d73a92893 100644 --- a/doc/ChangeLog +++ b/doc/ChangeLog @@ -1,3 +1,11 @@ +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> * user/io.t: Fix typos for IO unregister reported by Catalin Morosan diff --git a/doc/ada_user/ada_user.texi b/doc/ada_user/ada_user.texi index 9aa79817ad..b356d3f134 100644 --- a/doc/ada_user/ada_user.texi +++ b/doc/ada_user/ada_user.texi @@ -107,6 +107,7 @@ @include user/stackchk.texi @include user/cpuuse.texi @include user/object.texi +@include user/chains.texi @include user/dirstat.texi @include example.texi @include user/glossary.texi @@ -145,6 +146,7 @@ This is the online version of the RTEMS Ada User's Guide. * Stack Bounds Checker:: * CPU Usage Statistics:: * Object Services:: +* Chains:: * Directive Status Codes:: * Example Application:: * Glossary:: diff --git a/doc/user/Makefile.am b/doc/user/Makefile.am index 32ed2e8a76..4a6f6ccabb 100644 --- a/doc/user/Makefile.am +++ b/doc/user/Makefile.am @@ -18,7 +18,7 @@ GENERATED_FILES = overview.texi concepts.texi datatypes.texi init.texi \ task.texi intr.texi clock.texi timer.texi sem.texi msg.texi event.texi \ 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 @@ -177,9 +177,14 @@ cpuuse.texi: cpuuse.t object.texi: object.t $(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 \ $(TXT_FILES) $(PNG_FILES) $(EPS_IMAGES) $(noinst_DATA) diff --git a/doc/user/c_user.texi b/doc/user/c_user.texi index f828bf07cd..4ed0a3169d 100644 --- a/doc/user/c_user.texi +++ b/doc/user/c_user.texi @@ -106,6 +106,7 @@ @include stackchk.texi @include cpuuse.texi @include object.texi +@include chains.texi @include dirstat.texi @include example.texi @include glossary.texi @@ -144,6 +145,7 @@ This is the online version of the RTEMS C User's Guide. * Stack Bounds Checker:: * CPU Usage Statistics:: * Object Services:: +* Chains:: * Directive Status Codes:: * Example Application:: * Glossary:: diff --git a/doc/user/chains.t b/doc/user/chains.t new file mode 100755 index 0000000000..f6df34121a --- /dev/null +++ b/doc/user/chains.t @@ -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. diff --git a/doc/user/dirstat.texi b/doc/user/dirstat.texi index 440b3ef9ce..727bc8d355 100644 --- a/doc/user/dirstat.texi +++ b/doc/user/dirstat.texi @@ -7,7 +7,7 @@ @c @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 @table @b |