From 5396467fb83571882f462b929c99965b2eaf6be4 Mon Sep 17 00:00:00 2001 From: Chris Johns Date: Wed, 9 Jul 2008 02:50:28 +0000 Subject: 2008-07-09 Chris Johns * 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. --- doc/user/chains.t | 681 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 681 insertions(+) create mode 100755 doc/user/chains.t (limited to 'doc/user/chains.t') 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. -- cgit v1.2.3