begriffs open source - freertos/blob - list.c

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