From 72a62ad88f82fe1ffee50024db4dd0f3fa5806f7 Mon Sep 17 00:00:00 2001 From: Chris Johns Date: Thu, 3 Nov 2016 16:58:08 +1100 Subject: Rename all manuals with an _ to have a -. It helps released naming of files. --- c-user/chains.rst | 873 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 873 insertions(+) create mode 100644 c-user/chains.rst (limited to 'c-user/chains.rst') diff --git a/c-user/chains.rst b/c-user/chains.rst new file mode 100644 index 0000000..caa3ffe --- /dev/null +++ b/c-user/chains.rst @@ -0,0 +1,873 @@ +.. comment SPDX-License-Identifier: CC-BY-SA-4.0 + +.. COMMENT: Copyright 2014 Gedare Bloom. +.. COMMENT: All rights reserved. + +Chains +###### + +.. index:: chains + +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: + +- ``rtems_chain_node`` - Chain node used in user objects + +- ``rtems_chain_control`` - Chain control node + +- rtems_chain_initialize_ - initialize the chain with nodes + +- rtems_chain_initialize_empty_ - initialize the chain as empty + +- rtems_chain_is_null_node_ - Is the node NULL ? + +- rtems_chain_head_ - Return the chain's head + +- rtems_chain_tail_ - Return the chain's tail + +- rtems_chain_are_nodes_equal_ - Are the node's equal ? + +- rtems_chain_is_empty_ - Is the chain empty ? + +- rtems_chain_is_first_ - Is the Node the first in the chain ? + +- rtems_chain_is_last_ - Is the Node the last in the chain ? + +- rtems_chain_has_only_one_node_ - Does the node have one node ? + +- rtems_chain_node_count_unprotected_ - Returns the node count of the chain (unprotected) + +- rtems_chain_is_head_ - Is the node the head ? + +- rtems_chain_is_tail_ - Is the node the tail ? + +- rtems_chain_extract_ - Extract the node from the chain + +- rtems_chain_extract_unprotected_ - Extract the node from the chain (unprotected) + +- rtems_chain_get_ - Return the first node on the chain + +- rtems_chain_get_unprotected_ - Return the first node on the chain (unprotected) + +- rtems_chain_insert_ - Insert the node into the chain + +- rtems_chain_insert_unprotected_ - Insert the node into the chain (unprotected) + +- rtems_chain_append_ - Append the node to chain + +- rtems_chain_append_unprotected_ - Append the node to chain (unprotected) + +- rtems_chain_prepend_ - Prepend the node to the end of the chain + +- rtems_chain_prepend_unprotected_ - Prepend the node to chain (unprotected) + +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. + +Nodes +----- + +A chain is made up from nodes that orginate from a chain control object. A node +is of type ``rtems_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: + +.. code-block:: c + + typedef struct foo + { + rtems_chain_node node; + int bar; + } foo; + +creates a type ``foo`` that can be placed on a chain. To get the foo structure +from the list you perform the following: + +.. code-block:: c + + foo* get_foo(rtems_chain_control* control) + { + return (foo*) rtems_chain_get(control); + } + +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. + +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. + +.. code-block:: c + + [Control] + first ------------------------> + permanent_null <--------------- [NODE] + last -------------------------> + +The implementation does not require special checks for manipulating the first +and last nodes on the chain. To accomplish this the ``rtems_chain_control`` +structure is treated as two overlapping ``rtems_chain_node`` structures. The +permanent head of the chain overlays a node structure on the first and +``permanent_null`` fields. The ``permanent_tail`` of the chain overlays a node +structure on the ``permanent_null`` and ``last`` elements of the structure. + +Operations +========== + +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. + +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: + +.. code-block:: c + + typedef struct foo + { + rtems_chain_node node; + uint8_t char* data; + } foo; + rtems_chain_control chain; + +Add nodes with the following code: + +.. code-block:: c + + rtems_chain_initialize_empty (&chain); + + for (i = 0; i < count; i++) + { + foo* bar = malloc (sizeof (foo)); + if (!bar) + return -1; + bar->data = malloc (size); + rtems_chain_append (&chain, &bar->node); + } + +The chain is initialized and the nodes allocated and appended to the +chain. This is an example of a pool of buffers. + +Iterating a Chain +----------------- +.. index:: 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: + +.. code-block:: c + + void foobar (const char* match, + rtems_chain_control* chain, + rtems_chain_control* out) + { + rtems_chain_node* node; + foo* bar; + + rtems_chain_initialize_empty (out); + + node = chain->first; + while (!rtems_chain_is_tail (chain, node)) + { + bar = (foo*) node; + rtems_chain_node* next_node = node->next; + if (strcmp (match, bar->data) == 0) + { + rtems_chain_extract (node); + rtems_chain_append (out, node); + } + node = next_node; + } + } + +Directives +========== + +The section details the Chains directives. + +.. COMMENT: Initialize this Chain With Nodes + +.. _rtems_chain_initialize: + +Initialize Chain With Nodes +--------------------------- +.. index:: chain initialize + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_initialize + +.. code-block:: c + + void rtems_chain_initialize( + rtems_chain_control *the_chain, + void *starting_address, + size_t number_nodes, + size_t node_size + ) + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This function take in a pointer to a chain control and initializes it to +contain a set of chain nodes. The chain will contain ``number_nodes`` chain +nodes from the memory pointed to by ``start_address``. Each node is assumed to +be ``node_size`` bytes. + +**NOTES:** + +This call will discard any nodes on the chain. + +This call does NOT inititialize any user data on each node. + +.. COMMENT: Initialize this Chain as Empty + +.. _rtems_chain_initialize_empty: + +Initialize Empty +---------------- +.. index:: chain initialize empty + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_initialize_empty + +.. code-block:: c + + void rtems_chain_initialize_empty( + rtems_chain_control *the_chain + ); + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This function take in a pointer to a chain control and initializes it to empty. + +**NOTES:** + +This call will discard any nodes on the chain. + +.. _rtems_chain_is_null_node: + +Is Null Node ? +-------------- +.. index:: chain is node null + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_is_null_node + +.. code-block:: c + + bool rtems_chain_is_null_node( + const rtems_chain_node *the_node + ); + +**RETURNS** + +Returns ``true`` is the node point is NULL and ``false`` if the node is not +NULL. + +**DESCRIPTION:** + +Tests the node to see if it is a NULL returning ``true`` if a null. + +.. _rtems_chain_head: + +Head +---- +.. index:: chain get head + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_head + +.. code-block:: c + + rtems_chain_node *rtems_chain_head( + rtems_chain_control *the_chain + ) + +**RETURNS** + +Returns the permanent head node of the chain. + +**DESCRIPTION:** + +This function returns a pointer to the first node on the chain. + +.. _rtems_chain_tail: + +Tail +---- +.. index:: chain get tail + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_tail + +.. code-block:: c + + rtems_chain_node *rtems_chain_tail( + rtems_chain_control *the_chain + ); + +**RETURNS** + +Returns the permanent tail node of the chain. + +**DESCRIPTION:** + +This function returns a pointer to the last node on the chain. + +.. _rtems_chain_are_nodes_equal: + +Are Two Nodes Equal ? +--------------------- +.. index:: chare are nodes equal + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_are_nodes_equal + +.. code-block:: c + + bool rtems_chain_are_nodes_equal( + const rtems_chain_node *left, + const rtems_chain_node *right + ); + +**RETURNS** + +This function returns ``true`` if the left node and the right node are equal, +and ``false`` otherwise. + +**DESCRIPTION:** + +This function returns ``true`` if the left node and the right node are equal, +and ``false`` otherwise. + +.. _rtems_chain_is_empty: + +Is the Chain Empty +------------------ +.. index:: chain is chain empty + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_is_empty + +.. code-block:: c + + bool rtems_chain_is_empty( + rtems_chain_control *the_chain + ); + +**RETURNS** + +This function returns ``true`` if there a no nodes on the chain and ``false`` +otherwise. + +**DESCRIPTION:** + +This function returns ``true`` if there a no nodes on the chain and ``false`` +otherwise. + +.. _rtems_chain_is_first: + +Is this the First Node on the Chain ? +------------------------------------- +.. index:: chain is node the first + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_is_first + +.. code-block:: c + + bool rtems_chain_is_first( + const rtems_chain_node *the_node + ); + +**RETURNS** + +This function returns ``true`` if the node is the first node on a chain and +``false`` otherwise. + +**DESCRIPTION:** + +This function returns ``true`` if the node is the first node on a chain and +``false`` otherwise. + +.. _rtems_chain_is_last: + +Is this the Last Node on the Chain ? +------------------------------------ +.. index:: chain is node the last + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_is_last + +.. code-block:: c + + bool rtems_chain_is_last( + const rtems_chain_node *the_node + ); + +**RETURNS** + +This function returns ``true`` if the node is the last node on a chain and +``false`` otherwise. + +**DESCRIPTION:** + +This function returns ``true`` if the node is the last node on a chain and +``false`` otherwise. + +.. _rtems_chain_has_only_one_node: + +Does this Chain have only One Node ? +------------------------------------ +.. index:: chain only one node + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_has_only_one_node + +.. code-block:: c + + bool rtems_chain_has_only_one_node( + const rtems_chain_control *the_chain + ); + +**RETURNS** + +This function returns ``true`` if there is only one node on the chain and +``false`` otherwise. + +**DESCRIPTION:** + +This function returns ``true`` if there is only one node on the chain and +``false`` otherwise. + +.. _rtems_chain_node_count_unprotected: + +Returns the node count of the chain (unprotected) +------------------------------------------------- +.. index:: chain only one node + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_node_count_unprotected + +.. code-block:: c + + size_t rtems_chain_node_count_unprotected( + const rtems_chain_control *the_chain + ); + +**RETURNS** + +This function returns the node count of the chain. + +**DESCRIPTION:** + +This function returns the node count of the chain. + +.. _rtems_chain_is_head: + +Is this Node the Chain Head ? +----------------------------- +.. index:: chain is node the head + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_is_head + +.. code-block:: c + + bool rtems_chain_is_head( + rtems_chain_control *the_chain, + rtems_const chain_node *the_node + ); + +**RETURNS** + +This function returns ``true`` if the node is the head of the chain and +``false`` otherwise. + +**DESCRIPTION:** + +This function returns ``true`` if the node is the head of the chain and +``false`` otherwise. + +.. _rtems_chain_is_tail: + +Is this Node the Chain Tail ? +----------------------------- +.. index:: chain is node the tail + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_is_tail + +.. code-block:: c + + bool rtems_chain_is_tail( + rtems_chain_control *the_chain, + const rtems_chain_node *the_node + ) + +**RETURNS** + +This function returns ``true`` if the node is the tail of the chain and +``false`` otherwise. + +**DESCRIPTION:** + +This function returns ``true`` if the node is the tail of the chain and +``false`` otherwise. + +.. _rtems_chain_extract: + +Extract a Node +-------------- +.. index:: chain extract a node + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_extract + +.. code-block:: c + + void rtems_chain_extract( + rtems_chain_node *the_node + ); + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This routine extracts the node from the chain on which it resides. + +**NOTES:** + +Interrupts are disabled while extracting the node to ensure the atomicity of +the operation. + +Use rtems_chain_extract_unprotected_ to avoid disabling of interrupts. + +.. _rtems_chain_extract_unprotected: + +Extract a Node (unprotected) +---------------------------- +.. index:: chain extract a node unprotected + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_extract_unprotected + +.. code-block:: c + + void rtems_chain_extract_unprotected( + rtems_chain_node *the_node + ); + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This routine extracts the node from the chain on which it resides. + +**NOTES:** + +The function does nothing to ensure the atomicity of the operation. + +.. _rtems_chain_get: + +Get the First Node +------------------ +.. index:: chain get first node + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_get + +.. code-block:: c + + rtems_chain_node *rtems_chain_get( + rtems_chain_control *the_chain + ); + +**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. + +**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. + +**NOTES:** + +Interrupts are disabled while obtaining the node to ensure the atomicity of the +operation. + +Use ``rtems_chain_get_unprotected()`` to avoid disabling of interrupts. + +.. _rtems_chain_get_unprotected: + +Get the First Node (unprotected) +-------------------------------- +.. index:: chain get first node + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_get_unprotected + +.. code-block:: c + + rtems_chain_node *rtems_chain_get_unprotected( + rtems_chain_control *the_chain + ); + +**RETURNS:** + +A pointer to the former first node is returned. + +**DESCRIPTION:** + +Removes the first node from the chain and returns a pointer to it. In case the +chain was empty, then the results are unpredictable. + +**NOTES:** + +The function does nothing to ensure the atomicity of the operation. + +.. _rtems_chain_insert: + +Insert a Node +------------- +.. index:: chain insert a node + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_insert + +.. code-block:: c + + void rtems_chain_insert( + rtems_chain_node *after_node, + rtems_chain_node *the_node + ); + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This routine inserts a node on a chain immediately following the specified +node. + +**NOTES:** + +Interrupts are disabled during the insert to ensure the atomicity of the +operation. + +Use rtems_chain_insert_unprotected_ to avoid disabling of interrupts. + +.. _rtems_chain_insert_unprotected: + +Insert a Node (unprotected) +--------------------------- +.. index:: chain insert a node unprotected + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_insert_unprotected + +.. code-block:: c + + void rtems_chain_insert_unprotected( + rtems_chain_node *after_node, + rtems_chain_node *the_node + ); + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This routine inserts a node on a chain immediately following the specified +node. + +**NOTES:** + +The function does nothing to ensure the atomicity of the operation. + +.. _rtems_chain_append: + +Append a Node +------------- +.. index:: chain append a node + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_append + +.. code-block:: c + + void rtems_chain_append( + rtems_chain_control *the_chain, + rtems_chain_node *the_node + ); + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This routine appends a node to the end of a chain. + +**NOTES:** + +Interrupts are disabled during the append to ensure the atomicity of the +operation. + +Use rtems_chain_append_unprotected_ to avoid disabling of interrupts. + +.. _rtems_chain_append_unprotected: + +Append a Node (unprotected) +--------------------------- +.. index:: chain append a node unprotected + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_append_unprotected + +.. code-block:: c + + void rtems_chain_append_unprotected( + rtems_chain_control *the_chain, + rtems_chain_node *the_node + ); + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This routine appends a node to the end of a chain. + +**NOTES:** + +The function does nothing to ensure the atomicity of the operation. + +.. _rtems_chain_prepend: + +Prepend a Node +-------------- +.. index:: prepend node + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_prepend + +.. code-block:: c + + void rtems_chain_prepend( + rtems_chain_control *the_chain, + rtems_chain_node *the_node + ); + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This routine prepends a node to the front of the chain. + +**NOTES:** + +Interrupts are disabled during the prepend to ensure the atomicity of the +operation. + +Use rtems_chain_prepend_unprotected_ to avoid disabling of +interrupts. + +.. _rtems_chain_prepend_unprotected: + +Prepend a Node (unprotected) +---------------------------- +.. index:: prepend node unprotected + +**CALLING SEQUENCE:** + +.. index:: rtems_chain_prepend_unprotected + +.. code-block:: c + + void rtems_chain_prepend_unprotected( + rtems_chain_control *the_chain, + rtems_chain_node *the_node + ); + +**RETURNS** + +Returns nothing. + +**DESCRIPTION:** + +This routine prepends a node to the front of the chain. + +**NOTES:** + +The function does nothing to ensure the atomicity of the operation. -- cgit v1.2.3