2020-10-26 12:35:25 +00:00
/*
* FreeRTOS Kernel V10 .2 .1
* Copyright ( C ) 2019 Amazon . com , Inc . or its affiliates . All Rights Reserved .
*
* Permission is hereby granted , free of charge , to any person obtaining a copy of
* this software and associated documentation files ( the " Software " ) , to deal in
* the Software without restriction , including without limitation the rights to
* use , copy , modify , merge , publish , distribute , sublicense , and / or sell copies of
* the Software , and to permit persons to whom the Software is furnished to do so ,
* subject to the following conditions :
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software .
*
* THE SOFTWARE IS PROVIDED " AS IS " , WITHOUT WARRANTY OF ANY KIND , EXPRESS OR
* IMPLIED , INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY , FITNESS
* FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT . IN NO EVENT SHALL THE AUTHORS OR
* COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM , DAMAGES OR OTHER LIABILITY , WHETHER
* IN AN ACTION OF CONTRACT , TORT OR OTHERWISE , ARISING FROM , OUT OF OR IN
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE .
*
* http : //www.FreeRTOS.org
* http : //aws.amazon.com/freertos
*
* 1 tab = = 4 spaces !
*/
/*
* This is the list implementation used by the scheduler . While it is tailored
* heavily for the schedulers needs , it is also available for use by
* application code .
*
* list_ts can only store pointers to list_item_ts . Each ListItem_t contains a
* numeric value ( xItemValue ) . Most of the time the lists are sorted in
* descending item value order .
*
* Lists are created already containing one list item . The value of this
* item is the maximum possible that can be stored , it is therefore always at
* the end of the list and acts as a marker . The list member pxHead always
* points to this marker - even though it is at the tail of the list . This
* is because the tail contains a wrap back pointer to the true head of
* the list .
*
* In addition to it ' s value , each list item contains a pointer to the next
* item in the list ( pxNext ) , a pointer to the list it is in ( pxContainer )
* and a pointer to back to the object that contains it . These later two
* pointers are included for efficiency of list manipulation . There is
* effectively a two way link between the object containing the list item and
* the list item itself .
*
*
* \ page ListIntroduction List Implementation
* \ ingroup FreeRTOSIntro
*/
# ifndef INC_FREERTOS_H
2020-11-08 19:56:51 +00:00
# error FreeRTOS.h must be included before list.h
2020-10-26 12:35:25 +00:00
# endif
# ifndef LIST_H
# define LIST_H
/*
* The list structure members are modified from within interrupts , and therefore
* by rights should be declared volatile . However , they are only modified in a
* functionally atomic way ( within critical sections of with the scheduler
* suspended ) and are either passed by reference into a function or indexed via
* a volatile variable . Therefore , in all use cases tested so far , the volatile
* qualifier can be omitted in order to provide a moderate performance
* improvement without adversely affecting functional behaviour . The assembly
* instructions generated by the IAR , ARM and GCC compilers when the respective
* compiler ' s options were set for maximum optimisation has been inspected and
* deemed to be as intended . That said , as compiler technology advances , and
* especially if aggressive cross module optimisation is used ( a use case that
* has not been exercised to any great extend ) then it is feasible that the
* volatile qualifier will be needed for correct optimisation . It is expected
* that a compiler removing essential code because , without the volatile
* qualifier on the list structure members and with aggressive cross module
* optimisation , the compiler deemed the code unnecessary will result in
* complete and obvious failure of the scheduler . If this is ever experienced
* then the volatile qualifier can be inserted in the relevant places within the
* list structures by simply defining configLIST_VOLATILE to volatile in
* FreeRTOSConfig . h ( as per the example at the bottom of this comment block ) .
* If configLIST_VOLATILE is not defined then the preprocessor directives below
* will simply # define configLIST_VOLATILE away completely .
*
* To use volatile list structure members then add the following line to
* FreeRTOSConfig . h ( without the quotes ) :
* " #define configLIST_VOLATILE volatile "
*/
# ifndef configLIST_VOLATILE
2020-11-08 19:56:51 +00:00
# define configLIST_VOLATILE
2020-10-26 12:35:25 +00:00
# endif /* configSUPPORT_CROSS_MODULE_OPTIMISATION */
# ifdef __cplusplus
extern " C " {
# endif
/* Macros that can be used to place known values within the list structures,
then check that the known values do not get corrupted during the execution of
the application . These may catch the list data structures being overwritten in
memory . They will not catch data errors caused by incorrect configuration or
use of FreeRTOS . */
# if( configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES == 0 )
2020-11-08 19:56:51 +00:00
/* Define the macros to do nothing. */
# define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
# define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
# define listFIRST_LIST_INTEGRITY_CHECK_VALUE
# define listSECOND_LIST_INTEGRITY_CHECK_VALUE
# define listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem )
# define listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem )
# define listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList )
# define listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList )
# define listTEST_LIST_ITEM_INTEGRITY( pxItem )
# define listTEST_LIST_INTEGRITY( pxList )
2020-10-26 12:35:25 +00:00
# else
2020-11-08 19:56:51 +00:00
/* Define macros that add new members into the list structures. */
# define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE TickType_t xListItemIntegrityValue1;
# define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE TickType_t xListItemIntegrityValue2;
# define listFIRST_LIST_INTEGRITY_CHECK_VALUE TickType_t xListIntegrityValue1;
# define listSECOND_LIST_INTEGRITY_CHECK_VALUE TickType_t xListIntegrityValue2;
2020-10-26 12:35:25 +00:00
2020-11-08 19:56:51 +00:00
/* Define macros that set the new structure members to known values. */
# define listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem ) ( pxItem )->xListItemIntegrityValue1 = pdINTEGRITY_CHECK_VALUE
# define listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem ) ( pxItem )->xListItemIntegrityValue2 = pdINTEGRITY_CHECK_VALUE
# define listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList ) ( pxList )->xListIntegrityValue1 = pdINTEGRITY_CHECK_VALUE
# define listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList ) ( pxList )->xListIntegrityValue2 = pdINTEGRITY_CHECK_VALUE
2020-10-26 12:35:25 +00:00
2020-11-08 19:56:51 +00:00
/* Define macros that will assert if one of the structure members does not
contain its expected value . */
# define listTEST_LIST_ITEM_INTEGRITY( pxItem ) configASSERT( ( ( pxItem )->xListItemIntegrityValue1 == pdINTEGRITY_CHECK_VALUE ) && ( ( pxItem )->xListItemIntegrityValue2 == pdINTEGRITY_CHECK_VALUE ) )
# define listTEST_LIST_INTEGRITY( pxList ) configASSERT( ( ( pxList )->xListIntegrityValue1 == pdINTEGRITY_CHECK_VALUE ) && ( ( pxList )->xListIntegrityValue2 == pdINTEGRITY_CHECK_VALUE ) )
2020-10-26 12:35:25 +00:00
# endif /* configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES */
/*
* Definition of the only type of object that a list can contain .
*/
struct xLIST ;
struct xLIST_ITEM
{
2020-11-08 19:56:51 +00:00
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
configLIST_VOLATILE TickType_t xItemValue ; /*< The value being listed. In most cases this is used to sort the list in descending order. */
struct xLIST_ITEM * configLIST_VOLATILE pxNext ; /*< Pointer to the next ListItem_t in the list. */
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious ; /*< Pointer to the previous ListItem_t in the list. */
void * pvOwner ; /*< Pointer to the object (normally a TCB) that contains the list item. There is therefore a two way link between the object containing the list item and the list item itself. */
struct xLIST * configLIST_VOLATILE pxContainer ; /*< Pointer to the list in which this list item is placed (if any). */
listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
2020-10-26 12:35:25 +00:00
} ;
2020-11-08 19:56:51 +00:00
typedef struct xLIST_ITEM ListItem_t ; /* For some reason lint wants this as two separate definitions. */
2020-10-26 12:35:25 +00:00
struct xMINI_LIST_ITEM
{
2020-11-08 19:56:51 +00:00
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
configLIST_VOLATILE TickType_t xItemValue ;
struct xLIST_ITEM * configLIST_VOLATILE pxNext ;
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious ;
2020-10-26 12:35:25 +00:00
} ;
typedef struct xMINI_LIST_ITEM MiniListItem_t ;
/*
* Definition of the type of queue used by the scheduler .
*/
typedef struct xLIST
{
2020-11-08 19:56:51 +00:00
listFIRST_LIST_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
volatile UBaseType_t uxNumberOfItems ;
ListItem_t * configLIST_VOLATILE pxIndex ; /*< Used to walk through the list. Points to the last item returned by a call to listGET_OWNER_OF_NEXT_ENTRY (). */
MiniListItem_t xListEnd ; /*< List item that contains the maximum possible item value meaning it is always at the end of the list and is therefore used as a marker. */
listSECOND_LIST_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
2020-10-26 12:35:25 +00:00
} List_t ;
/*
* Access macro to set the owner of a list item . The owner of a list item
* is the object ( usually a TCB ) that contains the list item .
*
* \ page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner ) ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )
2020-10-26 12:35:25 +00:00
/*
* Access macro to get the owner of a list item . The owner of a list item
* is the object ( usually a TCB ) that contains the list item .
*
* \ page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listGET_LIST_ITEM_OWNER( pxListItem ) ( ( pxListItem )->pvOwner )
2020-10-26 12:35:25 +00:00
/*
* Access macro to set the value of the list item . In most cases the value is
* used to sort the list in descending order .
*
* \ page listSET_LIST_ITEM_VALUE listSET_LIST_ITEM_VALUE
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listSET_LIST_ITEM_VALUE( pxListItem, xValue ) ( ( pxListItem )->xItemValue = ( xValue ) )
2020-10-26 12:35:25 +00:00
/*
* Access macro to retrieve the value of the list item . The value can
* represent anything - for example the priority of a task , or the time at
* which a task should be unblocked .
*
* \ page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listGET_LIST_ITEM_VALUE( pxListItem ) ( ( pxListItem )->xItemValue )
2020-10-26 12:35:25 +00:00
/*
* Access macro to retrieve the value of the list item at the head of a given
* list .
*
* \ page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList ) ( ( ( pxList )->xListEnd ).pxNext->xItemValue )
2020-10-26 12:35:25 +00:00
/*
* Return the list item at the head of the list .
*
* \ page listGET_HEAD_ENTRY listGET_HEAD_ENTRY
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listGET_HEAD_ENTRY( pxList ) ( ( ( pxList )->xListEnd ).pxNext )
2020-10-26 12:35:25 +00:00
/*
* Return the list item at the head of the list .
*
* \ page listGET_NEXT listGET_NEXT
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listGET_NEXT( pxListItem ) ( ( pxListItem )->pxNext )
2020-10-26 12:35:25 +00:00
/*
* Return the list item that marks the end of the list
*
* \ page listGET_END_MARKER listGET_END_MARKER
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listGET_END_MARKER( pxList ) ( ( ListItem_t const * ) ( &( ( pxList )->xListEnd ) ) )
2020-10-26 12:35:25 +00:00
/*
* Access macro to determine if a list contains any items . The macro will
* only have the value true if the list is empty .
*
* \ page listLIST_IS_EMPTY listLIST_IS_EMPTY
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listLIST_IS_EMPTY( pxList ) ( ( ( pxList )->uxNumberOfItems == ( UBaseType_t ) 0 ) ? pdTRUE : pdFALSE )
2020-10-26 12:35:25 +00:00
/*
* Access macro to return the number of items in the list .
*/
2020-11-08 19:56:51 +00:00
# define listCURRENT_LIST_LENGTH( pxList ) ( ( pxList )->uxNumberOfItems )
2020-10-26 12:35:25 +00:00
/*
* Access function to obtain the owner of the next entry in a list .
*
* The list member pxIndex is used to walk through a list . Calling
* listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list
* and returns that entry ' s pxOwner parameter . Using multiple calls to this
* function it is therefore possible to move through every item contained in
* a list .
*
* The pxOwner parameter of a list item is a pointer to the object that owns
* the list item . In the scheduler this is normally a task control block .
* The pxOwner parameter effectively creates a two way link between the list
* item and its owner .
*
* @ param pxTCB pxTCB is set to the address of the owner of the next list item .
* @ param pxList The list from which the next item owner is to be returned .
*
* \ page listGET_OWNER_OF_NEXT_ENTRY listGET_OWNER_OF_NEXT_ENTRY
* \ ingroup LinkedList
*/
2020-11-08 19:56:51 +00:00
# define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \
{ \
List_t * const pxConstList = ( pxList ) ; \
/* Increment the index to the next item and return the item, ensuring */ \
/* we don't return the marker used at the end of the list. */ \
( pxConstList ) - > pxIndex = ( pxConstList ) - > pxIndex - > pxNext ; \
if ( ( void * ) ( pxConstList ) - > pxIndex = = ( void * ) & ( ( pxConstList ) - > xListEnd ) ) \
{ \
( pxConstList ) - > pxIndex = ( pxConstList ) - > pxIndex - > pxNext ; \
} \
( pxTCB ) = ( pxConstList ) - > pxIndex - > pvOwner ; \
2020-10-26 12:35:25 +00:00
}
/*
* Access function to obtain the owner of the first entry in a list . Lists
* are normally sorted in ascending item value order .
*
* This function returns the pxOwner member of the first item in the list .
* The pxOwner parameter of a list item is a pointer to the object that owns
* the list item . In the scheduler this is normally a task control block .
* The pxOwner parameter effectively creates a two way link between the list
* item and its owner .
*
* @ param pxList The list from which the owner of the head item is to be
* returned .
*
* \ page listGET_OWNER_OF_HEAD_ENTRY listGET_OWNER_OF_HEAD_ENTRY
* \ ingroup LinkedList
*/
# define listGET_OWNER_OF_HEAD_ENTRY( pxList ) ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner )
/*
* Check to see if a list item is within a list . The list item maintains a
* " container " pointer that points to the list it is in . All this macro does
* is check to see if the container and the list match .
*
* @ param pxList The list we want to know if the list item is within .
* @ param pxListItem The list item we want to know if is in the list .
* @ return pdTRUE if the list item is in the list , otherwise pdFALSE .
*/
# define listIS_CONTAINED_WITHIN( pxList, pxListItem ) ( ( ( pxListItem )->pxContainer == ( pxList ) ) ? ( pdTRUE ) : ( pdFALSE ) )
/*
* Return the list a list item is contained within ( referenced from ) .
*
* @ param pxListItem The list item being queried .
* @ return A pointer to the List_t object that references the pxListItem
*/
# define listLIST_ITEM_CONTAINER( pxListItem ) ( ( pxListItem )->pxContainer )
/*
* This provides a crude means of knowing if a list has been initialised , as
* pxList - > xListEnd . xItemValue is set to portMAX_DELAY by the vListInitialise ( )
* function .
*/
# define listLIST_IS_INITIALISED( pxList ) ( ( pxList )->xListEnd.xItemValue == portMAX_DELAY )
/*
* Must be called before a list is used ! This initialises all the members
* of the list structure and inserts the xListEnd item into the list as a
* marker to the back of the list .
*
* @ param pxList Pointer to the list being initialised .
*
* \ page vListInitialise vListInitialise
* \ ingroup LinkedList
*/
void vListInitialise ( List_t * const pxList ) PRIVILEGED_FUNCTION ;
/*
* Must be called before a list item is used . This sets the list container to
* null so the item does not think that it is already contained in a list .
*
* @ param pxItem Pointer to the list item being initialised .
*
* \ page vListInitialiseItem vListInitialiseItem
* \ ingroup LinkedList
*/
void vListInitialiseItem ( ListItem_t * const pxItem ) PRIVILEGED_FUNCTION ;
/*
* Insert a list item into a list . The item will be inserted into the list in
* a position determined by its item value ( descending item value order ) .
*
* @ param pxList The list into which the item is to be inserted .
*
* @ param pxNewListItem The item that is to be placed in the list .
*
* \ page vListInsert vListInsert
* \ ingroup LinkedList
*/
void vListInsert ( List_t * const pxList , ListItem_t * const pxNewListItem ) PRIVILEGED_FUNCTION ;
/*
* Insert a list item into a list . The item will be inserted in a position
* such that it will be the last item within the list returned by multiple
* calls to listGET_OWNER_OF_NEXT_ENTRY .
*
* The list member pxIndex is used to walk through a list . Calling
* listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list .
* Placing an item in a list using vListInsertEnd effectively places the item
* in the list position pointed to by pxIndex . This means that every other
* item within the list will be returned by listGET_OWNER_OF_NEXT_ENTRY before
* the pxIndex parameter again points to the item being inserted .
*
* @ param pxList The list into which the item is to be inserted .
*
* @ param pxNewListItem The list item to be inserted into the list .
*
* \ page vListInsertEnd vListInsertEnd
* \ ingroup LinkedList
*/
void vListInsertEnd ( List_t * const pxList , ListItem_t * const pxNewListItem ) PRIVILEGED_FUNCTION ;
/*
* Remove an item from a list . The list item has a pointer to the list that
* it is in , so only the list item need be passed into the function .
*
* @ param uxListRemove The item to be removed . The item will remove itself from
* the list pointed to by it ' s pxContainer parameter .
*
* @ return The number of items that remain in the list after the list item has
* been removed .
*
* \ page uxListRemove uxListRemove
* \ ingroup LinkedList
*/
UBaseType_t uxListRemove ( ListItem_t * const pxItemToRemove ) PRIVILEGED_FUNCTION ;
# ifdef __cplusplus
}
# endif
# endif