list.c - third_party/github/FreeRTOS/FreeRTOS-Kernel - Git at Google

 /*
  * FreeRTOS Kernel <DEVELOPMENT BRANCH>
  * Copyright (C) 2021 Amazon.com, Inc. or its affiliates.  All Rights Reserved.
  *
  * SPDX-License-Identifier: MIT
  *
  * 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.
  *
  * https://www.FreeRTOS.org
  * https://github.com/FreeRTOS
  *
  */


 #include <stdlib.h>

 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
  * all the API functions to use the MPU wrappers.  That should only be done when
  * task.h is included from an application file. */
 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE

 #include "FreeRTOS.h"
 #include "list.h"

 /* Lint e9021, e961 and e750 are suppressed as a MISRA exception justified
  * because the MPU ports require MPU_WRAPPERS_INCLUDED_FROM_API_FILE to be
  * defined for the header files above, but not in this file, in order to
  * generate the correct privileged Vs unprivileged linkage and placement. */
 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE /*lint !e961 !e750 !e9021. */

 /*-----------------------------------------------------------
 * PUBLIC LIST API documented in list.h
 *----------------------------------------------------------*/

 void vListInitialise( List_t * const pxList )
 {
     traceENTER_vListInitialise( pxList );

     /* The list structure contains a list item which is used to mark the
      * end of the list.  To initialise the list the list end is inserted
      * as the only list entry. */
     pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM.  This is checked and valid. */

     listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );

     /* The list end value is the highest possible value in the list to
      * ensure it remains at the end of the list. */
     pxList->xListEnd.xItemValue = portMAX_DELAY;

     /* The list end next and previous pointers point to itself so we know
      * when the list is empty. */
     pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );     /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
     pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM.  This is checked and valid. */

     /* Initialize the remaining fields of xListEnd when it is a proper ListItem_t */
     #if ( configUSE_MINI_LIST_ITEM == 0 )
     {
         pxList->xListEnd.pvOwner = NULL;
         pxList->xListEnd.pxContainer = NULL;
         listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );
     }
     #endif

     pxList->uxNumberOfItems = ( UBaseType_t ) 0U;

     /* Write known values into the list if
      * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
     listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
     listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );

     traceRETURN_vListInitialise();
 }
 /*-----------------------------------------------------------*/

 void vListInitialiseItem( ListItem_t * const pxItem )
 {
     traceENTER_vListInitialiseItem( pxItem );

     /* Make sure the list item is not recorded as being on a list. */
     pxItem->pxContainer = NULL;

     /* Write known values into the list item if
      * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
     listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
     listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );

     traceRETURN_vListInitialiseItem();
 }
 /*-----------------------------------------------------------*/

 void vListInsertEnd( List_t * const pxList,
                      ListItem_t * const pxNewListItem )
 {
     ListItem_t * const pxIndex = pxList->pxIndex;

     traceENTER_vListInsertEnd( pxList, pxNewListItem );

     /* Only effective when configASSERT() is also defined, these tests may catch
      * the list data structures being overwritten in memory.  They will not catch
      * data errors caused by incorrect configuration or use of FreeRTOS. */
     listTEST_LIST_INTEGRITY( pxList );
     listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

     /* Insert a new list item into pxList, but rather than sort the list,
      * makes the new list item the last item to be removed by a call to
      * listGET_OWNER_OF_NEXT_ENTRY(). */
     pxNewListItem->pxNext = pxIndex;
     pxNewListItem->pxPrevious = pxIndex->pxPrevious;

     /* Only used during decision coverage testing. */
     mtCOVERAGE_TEST_DELAY();

     pxIndex->pxPrevious->pxNext = pxNewListItem;
     pxIndex->pxPrevious = pxNewListItem;

     /* Remember which list the item is in. */
     pxNewListItem->pxContainer = pxList;

     ( pxList->uxNumberOfItems )++;

     traceRETURN_vListInsertEnd();
 }
 /*-----------------------------------------------------------*/

 void vListInsert( List_t * const pxList,
                   ListItem_t * const pxNewListItem )
 {
     ListItem_t * pxIterator;
     const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

     traceENTER_vListInsert( pxList, pxNewListItem );

     /* Only effective when configASSERT() is also defined, these tests may catch
      * the list data structures being overwritten in memory.  They will not catch
      * data errors caused by incorrect configuration or use of FreeRTOS. */
     listTEST_LIST_INTEGRITY( pxList );
     listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

     /* Insert the new list item into the list, sorted in xItemValue order.
      *
      * If the list already contains a list item with the same item value then the
      * new list item should be placed after it.  This ensures that TCBs which are
      * stored in ready lists (all of which have the same xItemValue value) get a
      * share of the CPU.  However, if the xItemValue is the same as the back marker
      * the iteration loop below will not end.  Therefore the value is checked
      * first, and the algorithm slightly modified if necessary. */
     if( xValueOfInsertion == portMAX_DELAY )
     {
         pxIterator = pxList->xListEnd.pxPrevious;
     }
     else
     {
         /* *** NOTE ***********************************************************
         *  If you find your application is crashing here then likely causes are
         *  listed below.  In addition see https://www.FreeRTOS.org/FAQHelp.html for
         *  more tips, and ensure configASSERT() is defined!
         *  https://www.FreeRTOS.org/a00110.html#configASSERT
         *
         *   1) Stack overflow -
         *      see https://www.FreeRTOS.org/Stacks-and-stack-overflow-checking.html
         *   2) Incorrect interrupt priority assignment, especially on Cortex-M
         *      parts where numerically high priority values denote low actual
         *      interrupt priorities, which can seem counter intuitive.  See
         *      https://www.FreeRTOS.org/RTOS-Cortex-M3-M4.html and the definition
         *      of configMAX_SYSCALL_INTERRUPT_PRIORITY on
         *      https://www.FreeRTOS.org/a00110.html
         *   3) Calling an API function from within a critical section or when
         *      the scheduler is suspended, or calling an API function that does
         *      not end in "FromISR" from an interrupt.
         *   4) Using a queue or semaphore before it has been initialised or
         *      before the scheduler has been started (are interrupts firing
         *      before vTaskStartScheduler() has been called?).
         *   5) If the FreeRTOS port supports interrupt nesting then ensure that
         *      the priority of the tick interrupt is at or below
         *      configMAX_SYSCALL_INTERRUPT_PRIORITY.
         **********************************************************************/

         for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM.  This is checked and valid. *//*lint !e440 The iterator moves to a different value, not xValueOfInsertion. */
         {
             /* There is nothing to do here, just iterating to the wanted
              * insertion position. */
         }
     }

     pxNewListItem->pxNext = pxIterator->pxNext;
     pxNewListItem->pxNext->pxPrevious = pxNewListItem;
     pxNewListItem->pxPrevious = pxIterator;
     pxIterator->pxNext = pxNewListItem;

     /* Remember which list the item is in.  This allows fast removal of the
      * item later. */
     pxNewListItem->pxContainer = pxList;

     ( pxList->uxNumberOfItems )++;

     traceRETURN_vListInsert();
 }
 /*-----------------------------------------------------------*/

 UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
 {
     /* The list item knows which list it is in.  Obtain the list from the list
      * item. */
     List_t * const pxList = pxItemToRemove->pxContainer;

     traceENTER_uxListRemove( pxItemToRemove );


     pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
     pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

     /* Only used during decision coverage testing. */
     mtCOVERAGE_TEST_DELAY();

     /* Make sure the index is left pointing to a valid item. */
     if( pxList->pxIndex == pxItemToRemove )
     {
         pxList->pxIndex = pxItemToRemove->pxPrevious;
     }
     else
     {
         mtCOVERAGE_TEST_MARKER();
     }

     pxItemToRemove->pxContainer = NULL;
     ( pxList->uxNumberOfItems )--;

     traceRETURN_uxListRemove( pxList->uxNumberOfItems );

     return pxList->uxNumberOfItems;
 }
 /*-----------------------------------------------------------*/
	/*
	* FreeRTOS Kernel <DEVELOPMENT BRANCH>
	* Copyright (C) 2021 Amazon.com, Inc. or its affiliates. All Rights Reserved.
	*
	* SPDX-License-Identifier: MIT
	*
	* 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.
	*
	* https://www.FreeRTOS.org
	* https://github.com/FreeRTOS
	*
	*/


	#include <stdlib.h>

	/* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
	* all the API functions to use the MPU wrappers. That should only be done when
	* task.h is included from an application file. */
	#define MPU_WRAPPERS_INCLUDED_FROM_API_FILE

	#include "FreeRTOS.h"
	#include "list.h"

	/* Lint e9021, e961 and e750 are suppressed as a MISRA exception justified
	* because the MPU ports require MPU_WRAPPERS_INCLUDED_FROM_API_FILE to be
	* defined for the header files above, but not in this file, in order to
	* generate the correct privileged Vs unprivileged linkage and placement. */
	#undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE /lint !e961 !e750 !e9021. /

	/*-----------------------------------------------------------
	* PUBLIC LIST API documented in list.h
	----------------------------------------------------------/

	void vListInitialise( List_t * const pxList )
	{
	traceENTER_vListInitialise( pxList );

	/* The list structure contains a list item which is used to mark the
	* end of the list. To initialise the list the list end is inserted
	* as the only list entry. */
	pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. /

	listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );

	/* The list end value is the highest possible value in the list to
	* ensure it remains at the end of the list. */
	pxList->xListEnd.xItemValue = portMAX_DELAY;

	/* The list end next and previous pointers point to itself so we know
	* when the list is empty. */
	pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); /lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. /
	pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); /lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. /

	/* Initialize the remaining fields of xListEnd when it is a proper ListItem_t */
	#if ( configUSE_MINI_LIST_ITEM == 0 )
	{
	pxList->xListEnd.pvOwner = NULL;
	pxList->xListEnd.pxContainer = NULL;
	listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );
	}
	#endif

	pxList->uxNumberOfItems = ( UBaseType_t ) 0U;

	/* Write known values into the list if
	* configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
	listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
	listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );

	traceRETURN_vListInitialise();
	}
	/-----------------------------------------------------------/

	void vListInitialiseItem( ListItem_t * const pxItem )
	{
	traceENTER_vListInitialiseItem( pxItem );

	/* Make sure the list item is not recorded as being on a list. */
	pxItem->pxContainer = NULL;

	/* Write known values into the list item if
	* configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
	listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
	listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );

	traceRETURN_vListInitialiseItem();
	}
	/-----------------------------------------------------------/

	void vListInsertEnd( List_t * const pxList,
	ListItem_t * const pxNewListItem )
	{
	ListItem_t * const pxIndex = pxList->pxIndex;

	traceENTER_vListInsertEnd( pxList, pxNewListItem );

	/* Only effective when configASSERT() is also defined, these tests may catch
	* the list data structures being overwritten in memory. They will not catch
	* data errors caused by incorrect configuration or use of FreeRTOS. */
	listTEST_LIST_INTEGRITY( pxList );
	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

	/* Insert a new list item into pxList, but rather than sort the list,
	* makes the new list item the last item to be removed by a call to
	* listGET_OWNER_OF_NEXT_ENTRY(). */
	pxNewListItem->pxNext = pxIndex;
	pxNewListItem->pxPrevious = pxIndex->pxPrevious;

	/* Only used during decision coverage testing. */
	mtCOVERAGE_TEST_DELAY();

	pxIndex->pxPrevious->pxNext = pxNewListItem;
	pxIndex->pxPrevious = pxNewListItem;

	/* Remember which list the item is in. */
	pxNewListItem->pxContainer = pxList;

	( pxList->uxNumberOfItems )++;

	traceRETURN_vListInsertEnd();
	}
	/-----------------------------------------------------------/

	void vListInsert( List_t * const pxList,
	ListItem_t * const pxNewListItem )
	{
	ListItem_t * pxIterator;
	const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

	traceENTER_vListInsert( pxList, pxNewListItem );

	/* Only effective when configASSERT() is also defined, these tests may catch
	* the list data structures being overwritten in memory. They will not catch
	* data errors caused by incorrect configuration or use of FreeRTOS. */
	listTEST_LIST_INTEGRITY( pxList );
	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

	/* Insert the new list item into the list, sorted in xItemValue order.
	*
	* If the list already contains a list item with the same item value then the
	* new list item should be placed after it. This ensures that TCBs which are
	* stored in ready lists (all of which have the same xItemValue value) get a
	* share of the CPU. However, if the xItemValue is the same as the back marker
	* the iteration loop below will not end. Therefore the value is checked
	* first, and the algorithm slightly modified if necessary. */
	if( xValueOfInsertion == portMAX_DELAY )
	{
	pxIterator = pxList->xListEnd.pxPrevious;
	}
	else
	{
	/* * NOTE *********************************************************
	* If you find your application is crashing here then likely causes are
	* listed below. In addition see https://www.FreeRTOS.org/FAQHelp.html for
	* more tips, and ensure configASSERT() is defined!
	* https://www.FreeRTOS.org/a00110.html#configASSERT
	*
	* 1) Stack overflow -
	* see https://www.FreeRTOS.org/Stacks-and-stack-overflow-checking.html
	* 2) Incorrect interrupt priority assignment, especially on Cortex-M
	* parts where numerically high priority values denote low actual
	* interrupt priorities, which can seem counter intuitive. See
	* https://www.FreeRTOS.org/RTOS-Cortex-M3-M4.html and the definition
	* of configMAX_SYSCALL_INTERRUPT_PRIORITY on
	* https://www.FreeRTOS.org/a00110.html
	* 3) Calling an API function from within a critical section or when
	* the scheduler is suspended, or calling an API function that does
	* not end in "FromISR" from an interrupt.
	* 4) Using a queue or semaphore before it has been initialised or
	* before the scheduler has been started (are interrupts firing
	* before vTaskStartScheduler() has been called?).
	* 5) If the FreeRTOS port supports interrupt nesting then ensure that
	* the priority of the tick interrupt is at or below
	* configMAX_SYSCALL_INTERRUPT_PRIORITY.
	**********************************************************************/

	for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. //lint !e440 The iterator moves to a different value, not xValueOfInsertion. /
	{
	/* There is nothing to do here, just iterating to the wanted
	* insertion position. */
	}
	}

	pxNewListItem->pxNext = pxIterator->pxNext;
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	pxNewListItem->pxPrevious = pxIterator;
	pxIterator->pxNext = pxNewListItem;

	/* Remember which list the item is in. This allows fast removal of the
	* item later. */
	pxNewListItem->pxContainer = pxList;

	( pxList->uxNumberOfItems )++;

	traceRETURN_vListInsert();
	}
	/-----------------------------------------------------------/

	UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
	{
	/* The list item knows which list it is in. Obtain the list from the list
	* item. */
	List_t * const pxList = pxItemToRemove->pxContainer;

	traceENTER_uxListRemove( pxItemToRemove );



	pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
	pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

	/* Only used during decision coverage testing. */
	mtCOVERAGE_TEST_DELAY();

	/* Make sure the index is left pointing to a valid item. */
	if( pxList->pxIndex == pxItemToRemove )
	{
	pxList->pxIndex = pxItemToRemove->pxPrevious;
	}
	else
	{
	mtCOVERAGE_TEST_MARKER();
	}

	pxItemToRemove->pxContainer = NULL;
	( pxList->uxNumberOfItems )--;

	traceRETURN_uxListRemove( pxList->uxNumberOfItems );

	return pxList->uxNumberOfItems;
	}
	/-----------------------------------------------------------/