begriffs open source - freertos/blob - list.c

   1 /*\r
   2  * FreeRTOS Kernel <DEVELOPMENT BRANCH>\r
   3  * Copyright (C) 2021 Amazon.com, Inc. or its affiliates.  All Rights Reserved.\r
   4  *\r
   5  * SPDX-License-Identifier: MIT\r
   6  *\r
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy of\r
   8  * this software and associated documentation files (the "Software"), to deal in\r
   9  * the Software without restriction, including without limitation the rights to\r
  10  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of\r
  11  * the Software, and to permit persons to whom the Software is furnished to do so,\r
  12  * subject to the following conditions:\r
  13  *\r
  14  * The above copyright notice and this permission notice shall be included in all\r
  15  * copies or substantial portions of the Software.\r
  16  *\r
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS\r
  19  * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR\r
  20  * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER\r
  21  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
  22  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\r
  23  *\r
  24  * https://www.FreeRTOS.org\r
  25  * https://github.com/FreeRTOS\r
  26  *\r
  27  */\r
  28 \r
  29 \r
  30 #include <stdlib.h>\r
  31 \r
  32 /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining\r
  33  * all the API functions to use the MPU wrappers.  That should only be done when\r
  34  * task.h is included from an application file. */\r
  35 #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE\r
  36 \r
  37 #include "FreeRTOS.h"\r
  38 #include "list.h"\r
  39 \r
  40 /* Lint e9021, e961 and e750 are suppressed as a MISRA exception justified\r
  41  * because the MPU ports require MPU_WRAPPERS_INCLUDED_FROM_API_FILE to be\r
  42  * defined for the header files above, but not in this file, in order to\r
  43  * generate the correct privileged Vs unprivileged linkage and placement. */\r
  44 #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE /*lint !e961 !e750 !e9021. */\r
  45 \r
  46 /*-----------------------------------------------------------\r
  47 * PUBLIC LIST API documented in list.h\r
  48 *----------------------------------------------------------*/\r
  49 \r
  50 void vListInitialise( List_t * const pxList )\r
  51 {\r
  52     /* The list structure contains a list item which is used to mark the\r
  53      * end of the list.  To initialise the list the list end is inserted\r
  54      * as the only list entry. */\r
  55     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. */\r
  56 \r
  57     listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );\r
  58 \r
  59     /* The list end value is the highest possible value in the list to\r
  60      * ensure it remains at the end of the list. */\r
  61     pxList->xListEnd.xItemValue = portMAX_DELAY;\r
  62 \r
  63     /* The list end next and previous pointers point to itself so we know\r
  64      * when the list is empty. */\r
  65     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. */\r
  66     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. */\r
  67 \r
  68     /* Initialize the remaining fields of xListEnd when it is a proper ListItem_t */\r
  69     #if ( configUSE_MINI_LIST_ITEM == 0 )\r
  70     {\r
  71         pxList->xListEnd.pvOwner = NULL;\r
  72         pxList->xListEnd.pxContainer = NULL;\r
  73         listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );\r
  74     }\r
  75     #endif\r
  76 \r
  77     pxList->uxNumberOfItems = ( UBaseType_t ) 0U;\r
  78 \r
  79     /* Write known values into the list if\r
  80      * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */\r
  81     listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );\r
  82     listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );\r
  83 }\r
  84 /*-----------------------------------------------------------*/\r
  85 \r
  86 void vListInitialiseItem( ListItem_t * const pxItem )\r
  87 {\r
  88     /* Make sure the list item is not recorded as being on a list. */\r
  89     pxItem->pxContainer = NULL;\r
  90 \r
  91     /* Write known values into the list item if\r
  92      * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */\r
  93     listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );\r
  94     listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );\r
  95 }\r
  96 /*-----------------------------------------------------------*/\r
  97 \r
  98 void vListInsertEnd( List_t * const pxList,\r
  99                      ListItem_t * const pxNewListItem )\r
 100 {\r
 101     ListItem_t * const pxIndex = pxList->pxIndex;\r
 102 \r
 103     /* Only effective when configASSERT() is also defined, these tests may catch\r
 104      * the list data structures being overwritten in memory.  They will not catch\r
 105      * data errors caused by incorrect configuration or use of FreeRTOS. */\r
 106     listTEST_LIST_INTEGRITY( pxList );\r
 107     listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );\r
 108 \r
 109     /* Insert a new list item into pxList, but rather than sort the list,\r
 110      * makes the new list item the last item to be removed by a call to\r
 111      * listGET_OWNER_OF_NEXT_ENTRY(). */\r
 112     pxNewListItem->pxNext = pxIndex;\r
 113     pxNewListItem->pxPrevious = pxIndex->pxPrevious;\r
 114 \r
 115     /* Only used during decision coverage testing. */\r
 116     mtCOVERAGE_TEST_DELAY();\r
 117 \r
 118     pxIndex->pxPrevious->pxNext = pxNewListItem;\r
 119     pxIndex->pxPrevious = pxNewListItem;\r
 120 \r
 121     /* Remember which list the item is in. */\r
 122     pxNewListItem->pxContainer = pxList;\r
 123 \r
 124     ( pxList->uxNumberOfItems )++;\r
 125 }\r
 126 /*-----------------------------------------------------------*/\r
 127 \r
 128 void vListInsert( List_t * const pxList,\r
 129                   ListItem_t * const pxNewListItem )\r
 130 {\r
 131     ListItem_t * pxIterator;\r
 132     const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;\r
 133 \r
 134     /* Only effective when configASSERT() is also defined, these tests may catch\r
 135      * the list data structures being overwritten in memory.  They will not catch\r
 136      * data errors caused by incorrect configuration or use of FreeRTOS. */\r
 137     listTEST_LIST_INTEGRITY( pxList );\r
 138     listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );\r
 139 \r
 140     /* Insert the new list item into the list, sorted in xItemValue order.\r
 141      *\r
 142      * If the list already contains a list item with the same item value then the\r
 143      * new list item should be placed after it.  This ensures that TCBs which are\r
 144      * stored in ready lists (all of which have the same xItemValue value) get a\r
 145      * share of the CPU.  However, if the xItemValue is the same as the back marker\r
 146      * the iteration loop below will not end.  Therefore the value is checked\r
 147      * first, and the algorithm slightly modified if necessary. */\r
 148     if( xValueOfInsertion == portMAX_DELAY )\r
 149     {\r
 150         pxIterator = pxList->xListEnd.pxPrevious;\r
 151     }\r
 152     else\r
 153     {\r
 154         /* *** NOTE ***********************************************************\r
 155         *  If you find your application is crashing here then likely causes are\r
 156         *  listed below.  In addition see https://www.FreeRTOS.org/FAQHelp.html for\r
 157         *  more tips, and ensure configASSERT() is defined!\r
 158         *  https://www.FreeRTOS.org/a00110.html#configASSERT\r
 159         *\r
 160         *   1) Stack overflow -\r
 161         *      see https://www.FreeRTOS.org/Stacks-and-stack-overflow-checking.html\r
 162         *   2) Incorrect interrupt priority assignment, especially on Cortex-M\r
 163         *      parts where numerically high priority values denote low actual\r
 164         *      interrupt priorities, which can seem counter intuitive.  See\r
 165         *      https://www.FreeRTOS.org/RTOS-Cortex-M3-M4.html and the definition\r
 166         *      of configMAX_SYSCALL_INTERRUPT_PRIORITY on\r
 167         *      https://www.FreeRTOS.org/a00110.html\r
 168         *   3) Calling an API function from within a critical section or when\r
 169         *      the scheduler is suspended, or calling an API function that does\r
 170         *      not end in "FromISR" from an interrupt.\r
 171         *   4) Using a queue or semaphore before it has been initialised or\r
 172         *      before the scheduler has been started (are interrupts firing\r
 173         *      before vTaskStartScheduler() has been called?).\r
 174         *   5) If the FreeRTOS port supports interrupt nesting then ensure that\r
 175         *      the priority of the tick interrupt is at or below\r
 176         *      configMAX_SYSCALL_INTERRUPT_PRIORITY.\r
 177         **********************************************************************/\r
 178 \r
 179         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. */\r
 180         {\r
 181             /* There is nothing to do here, just iterating to the wanted\r
 182              * insertion position. */\r
 183         }\r
 184     }\r
 185 \r
 186     pxNewListItem->pxNext = pxIterator->pxNext;\r
 187     pxNewListItem->pxNext->pxPrevious = pxNewListItem;\r
 188     pxNewListItem->pxPrevious = pxIterator;\r
 189     pxIterator->pxNext = pxNewListItem;\r
 190 \r
 191     /* Remember which list the item is in.  This allows fast removal of the\r
 192      * item later. */\r
 193     pxNewListItem->pxContainer = pxList;\r
 194 \r
 195     ( pxList->uxNumberOfItems )++;\r
 196 }\r
 197 /*-----------------------------------------------------------*/\r
 198 \r
 199 UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )\r
 200 {\r
 201 /* The list item knows which list it is in.  Obtain the list from the list\r
 202  * item. */\r
 203     List_t * const pxList = pxItemToRemove->pxContainer;\r
 204 \r
 205     pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;\r
 206     pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;\r
 207 \r
 208     /* Only used during decision coverage testing. */\r
 209     mtCOVERAGE_TEST_DELAY();\r
 210 \r
 211     /* Make sure the index is left pointing to a valid item. */\r
 212     if( pxList->pxIndex == pxItemToRemove )\r
 213     {\r
 214         pxList->pxIndex = pxItemToRemove->pxPrevious;\r
 215     }\r
 216     else\r
 217     {\r
 218         mtCOVERAGE_TEST_MARKER();\r
 219     }\r
 220 \r
 221     pxItemToRemove->pxContainer = NULL;\r
 222     ( pxList->uxNumberOfItems )--;\r
 223 \r
 224     return pxList->uxNumberOfItems;\r
 225 }\r
 226 /*-----------------------------------------------------------*/\r