begriffs open source - freertos/blob - list.c

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