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  */\r
  26 \r
  27 \r
  28 #include <stdlib.h>\r
  29 #include "FreeRTOS.h"\r
  30 #include "list.h"\r
  31 \r
  32 /*-----------------------------------------------------------\r
  33 * PUBLIC LIST API documented in list.h\r
  34 *----------------------------------------------------------*/\r
  35 \r
  36 void vListInitialise( List_t * const pxList )\r
  37 {\r
  38     /* The list structure contains a list item which is used to mark the\r
  39      * end of the list.  To initialise the list the list end is inserted\r
  40      * as the only list entry. */\r
  41     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
  42 \r
  43     /* The list end value is the highest possible value in the list to\r
  44      * ensure it remains at the end of the list. */\r
  45     pxList->xListEnd.xItemValue = portMAX_DELAY;\r
  46 \r
  47     /* The list end next and previous pointers point to itself so we know\r
  48      * when the list is empty. */\r
  49     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
  50     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
  51 \r
  52     pxList->uxNumberOfItems     = ( UBaseType_t ) 0U;\r
  53 \r
  54     /* Write known values into the list if\r
  55      * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */\r
  56     listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );\r
  57     listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );\r
  58 }\r
  59 /*-----------------------------------------------------------*/\r
  60 \r
  61 void vListInitialiseItem( ListItem_t * const pxItem )\r
  62 {\r
  63     /* Make sure the list item is not recorded as being on a list. */\r
  64     pxItem->pxContainer = NULL;\r
  65 \r
  66     /* Write known values into the list item if\r
  67      * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */\r
  68     listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );\r
  69     listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );\r
  70 }\r
  71 /*-----------------------------------------------------------*/\r
  72 \r
  73 void vListInsertEnd( List_t * const pxList,\r
  74                      ListItem_t * const pxNewListItem )\r
  75 {\r
  76     ListItem_t * const pxIndex = pxList->pxIndex;\r
  77 \r
  78     /* Only effective when configASSERT() is also defined, these tests may catch\r
  79      * the list data structures being overwritten in memory.  They will not catch\r
  80      * data errors caused by incorrect configuration or use of FreeRTOS. */\r
  81     listTEST_LIST_INTEGRITY( pxList );\r
  82     listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );\r
  83 \r
  84     /* Insert a new list item into pxList, but rather than sort the list,\r
  85      * makes the new list item the last item to be removed by a call to\r
  86      * listGET_OWNER_OF_NEXT_ENTRY(). */\r
  87     pxNewListItem->pxNext       = pxIndex;\r
  88     pxNewListItem->pxPrevious   = pxIndex->pxPrevious;\r
  89 \r
  90     /* Only used during decision coverage testing. */\r
  91     mtCOVERAGE_TEST_DELAY();\r
  92 \r
  93     pxIndex->pxPrevious->pxNext = pxNewListItem;\r
  94     pxIndex->pxPrevious         = pxNewListItem;\r
  95 \r
  96     /* Remember which list the item is in. */\r
  97     pxNewListItem->pxContainer  = pxList;\r
  98 \r
  99     ( pxList->uxNumberOfItems )++;\r
 100 }\r
 101 /*-----------------------------------------------------------*/\r
 102 \r
 103 void vListInsert( List_t * const pxList,\r
 104                   ListItem_t * const pxNewListItem )\r
 105 {\r
 106     ListItem_t *     pxIterator;\r
 107     const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;\r
 108 \r
 109     /* Only effective when configASSERT() is also defined, these tests may catch\r
 110      * the list data structures being overwritten in memory.  They will not catch\r
 111      * data errors caused by incorrect configuration or use of FreeRTOS. */\r
 112     listTEST_LIST_INTEGRITY( pxList );\r
 113     listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );\r
 114 \r
 115     /* Insert the new list item into the list, sorted in xItemValue order.\r
 116      *\r
 117      * If the list already contains a list item with the same item value then the\r
 118      * new list item should be placed after it.  This ensures that TCBs which are\r
 119      * stored in ready lists (all of which have the same xItemValue value) get a\r
 120      * share of the CPU.  However, if the xItemValue is the same as the back marker\r
 121      * the iteration loop below will not end.  Therefore the value is checked\r
 122      * first, and the algorithm slightly modified if necessary. */\r
 123     if( xValueOfInsertion == portMAX_DELAY )\r
 124     {\r
 125         pxIterator = pxList->xListEnd.pxPrevious;\r
 126     }\r
 127     else\r
 128     {\r
 129         /* *** NOTE ***********************************************************\r
 130         *  If you find your application is crashing here then likely causes are\r
 131         *  listed below.  In addition see https://www.freertos.org/FAQHelp.html for\r
 132         *  more tips, and ensure configASSERT() is defined!\r
 133         *  https://www.freertos.org/a00110.html#configASSERT\r
 134         *\r
 135         *   1) Stack overflow -\r
 136         *      see https://www.freertos.org/Stacks-and-stack-overflow-checking.html\r
 137         *   2) Incorrect interrupt priority assignment, especially on Cortex-M\r
 138         *      parts where numerically high priority values denote low actual\r
 139         *      interrupt priorities, which can seem counter intuitive.  See\r
 140         *      https://www.freertos.org/RTOS-Cortex-M3-M4.html and the definition\r
 141         *      of configMAX_SYSCALL_INTERRUPT_PRIORITY on\r
 142         *      https://www.freertos.org/a00110.html\r
 143         *   3) Calling an API function from within a critical section or when\r
 144         *      the scheduler is suspended, or calling an API function that does\r
 145         *      not end in "FromISR" from an interrupt.\r
 146         *   4) Using a queue or semaphore before it has been initialised or\r
 147         *      before the scheduler has been started (are interrupts firing\r
 148         *      before vTaskStartScheduler() has been called?).\r
 149         **********************************************************************/\r
 150 \r
 151         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
 152         {\r
 153             /* There is nothing to do here, just iterating to the wanted\r
 154              * insertion position. */\r
 155         }\r
 156     }\r
 157 \r
 158     pxNewListItem->pxNext             = pxIterator->pxNext;\r
 159     pxNewListItem->pxNext->pxPrevious = pxNewListItem;\r
 160     pxNewListItem->pxPrevious         = pxIterator;\r
 161     pxIterator->pxNext                = pxNewListItem;\r
 162 \r
 163     /* Remember which list the item is in.  This allows fast removal of the\r
 164      * item later. */\r
 165     pxNewListItem->pxContainer        = pxList;\r
 166 \r
 167     ( pxList->uxNumberOfItems )++;\r
 168 }\r
 169 /*-----------------------------------------------------------*/\r
 170 \r
 171 UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )\r
 172 {\r
 173 /* The list item knows which list it is in.  Obtain the list from the list\r
 174  * item. */\r
 175     List_t * const pxList = pxItemToRemove->pxContainer;\r
 176 \r
 177     pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;\r
 178     pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;\r
 179 \r
 180     /* Only used during decision coverage testing. */\r
 181     mtCOVERAGE_TEST_DELAY();\r
 182 \r
 183     /* Make sure the index is left pointing to a valid item. */\r
 184     if( pxList->pxIndex == pxItemToRemove )\r
 185     {\r
 186         pxList->pxIndex = pxItemToRemove->pxPrevious;\r
 187     }\r
 188     else\r
 189     {\r
 190         mtCOVERAGE_TEST_MARKER();\r
 191     }\r
 192 \r
 193     pxItemToRemove->pxContainer        = NULL;\r
 194     ( pxList->uxNumberOfItems )--;\r
 195 \r
 196     return pxList->uxNumberOfItems;\r
 197 }\r
 198 /*-----------------------------------------------------------*/\r