diff options
Diffstat (limited to 'c_user/chains.rst')
| -rw-r--r-- | c_user/chains.rst | 873 |
1 files changed, 0 insertions, 873 deletions
diff --git a/c_user/chains.rst b/c_user/chains.rst deleted file mode 100644 index caa3ffe..0000000 --- a/c_user/chains.rst +++ /dev/null @@ -1,873 +0,0 @@ -.. 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. |