begriffs open source - cmsis-freertos/blob - Source/include/list.h

   1 /*
   2  * FreeRTOS Kernel V10.2.0
   3  * Copyright (C) 2019 Amazon.com, Inc. or its affiliates.  All Rights Reserved.
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   6  * this software and associated documentation files (the "Software"), to deal in
   7  * the Software without restriction, including without limitation the rights to
   8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
   9  * the Software, and to permit persons to whom the Software is furnished to do so,
  10  * subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in all
  13  * copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
  17  * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
  18  * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  19  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  20  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21  *
  22  * http://www.FreeRTOS.org
  23  * http://aws.amazon.com/freertos
  24  *
  25  * 1 tab == 4 spaces!
  26  */
  27
  28 /*
  29  * This is the list implementation used by the scheduler.  While it is tailored
  30  * heavily for the schedulers needs, it is also available for use by
  31  * application code.
  32  *
  33  * list_ts can only store pointers to list_item_ts.  Each ListItem_t contains a
  34  * numeric value (xItemValue).  Most of the time the lists are sorted in
  35  * descending item value order.
  36  *
  37  * Lists are created already containing one list item.  The value of this
  38  * item is the maximum possible that can be stored, it is therefore always at
  39  * the end of the list and acts as a marker.  The list member pxHead always
  40  * points to this marker - even though it is at the tail of the list.  This
  41  * is because the tail contains a wrap back pointer to the true head of
  42  * the list.
  43  *
  44  * In addition to it's value, each list item contains a pointer to the next
  45  * item in the list (pxNext), a pointer to the list it is in (pxContainer)
  46  * and a pointer to back to the object that contains it.  These later two
  47  * pointers are included for efficiency of list manipulation.  There is
  48  * effectively a two way link between the object containing the list item and
  49  * the list item itself.
  50  *
  51  *
  52  * \page ListIntroduction List Implementation
  53  * \ingroup FreeRTOSIntro
  54  */
  55
  56 #ifndef INC_FREERTOS_H
  57         #error FreeRTOS.h must be included before list.h
  58 #endif
  59
  60 #ifndef LIST_H
  61 #define LIST_H
  62
  63 /*
  64  * The list structure members are modified from within interrupts, and therefore
  65  * by rights should be declared volatile.  However, they are only modified in a
  66  * functionally atomic way (within critical sections of with the scheduler
  67  * suspended) and are either passed by reference into a function or indexed via
  68  * a volatile variable.  Therefore, in all use cases tested so far, the volatile
  69  * qualifier can be omitted in order to provide a moderate performance
  70  * improvement without adversely affecting functional behaviour.  The assembly
  71  * instructions generated by the IAR, ARM and GCC compilers when the respective
  72  * compiler's options were set for maximum optimisation has been inspected and
  73  * deemed to be as intended.  That said, as compiler technology advances, and
  74  * especially if aggressive cross module optimisation is used (a use case that
  75  * has not been exercised to any great extend) then it is feasible that the
  76  * volatile qualifier will be needed for correct optimisation.  It is expected
  77  * that a compiler removing essential code because, without the volatile
  78  * qualifier on the list structure members and with aggressive cross module
  79  * optimisation, the compiler deemed the code unnecessary will result in
  80  * complete and obvious failure of the scheduler.  If this is ever experienced
  81  * then the volatile qualifier can be inserted in the relevant places within the
  82  * list structures by simply defining configLIST_VOLATILE to volatile in
  83  * FreeRTOSConfig.h (as per the example at the bottom of this comment block).
  84  * If configLIST_VOLATILE is not defined then the preprocessor directives below
  85  * will simply #define configLIST_VOLATILE away completely.
  86  *
  87  * To use volatile list structure members then add the following line to
  88  * FreeRTOSConfig.h (without the quotes):
  89  * "#define configLIST_VOLATILE volatile"
  90  */
  91 #ifndef configLIST_VOLATILE
  92         #define configLIST_VOLATILE
  93 #endif /* configSUPPORT_CROSS_MODULE_OPTIMISATION */
  94
  95 #ifdef __cplusplus
  96 extern "C" {
  97 #endif
  98
  99 /* Macros that can be used to place known values within the list structures,
 100 then check that the known values do not get corrupted during the execution of
 101 the application.   These may catch the list data structures being overwritten in
 102 memory.  They will not catch data errors caused by incorrect configuration or
 103 use of FreeRTOS.*/
 104 #if( configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES == 0 )
 105         /* Define the macros to do nothing. */
 106         #define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
 107         #define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
 108         #define listFIRST_LIST_INTEGRITY_CHECK_VALUE
 109         #define listSECOND_LIST_INTEGRITY_CHECK_VALUE
 110         #define listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem )
 111         #define listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem )
 112         #define listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList )
 113         #define listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList )
 114         #define listTEST_LIST_ITEM_INTEGRITY( pxItem )
 115         #define listTEST_LIST_INTEGRITY( pxList )
 116 #else
 117         /* Define macros that add new members into the list structures. */
 118         #define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE                               TickType_t xListItemIntegrityValue1;
 119         #define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE                              TickType_t xListItemIntegrityValue2;
 120         #define listFIRST_LIST_INTEGRITY_CHECK_VALUE                                    TickType_t xListIntegrityValue1;
 121         #define listSECOND_LIST_INTEGRITY_CHECK_VALUE                                   TickType_t xListIntegrityValue2;
 122
 123         /* Define macros that set the new structure members to known values. */
 124         #define listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem )         ( pxItem )->xListItemIntegrityValue1 = pdINTEGRITY_CHECK_VALUE
 125         #define listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem )        ( pxItem )->xListItemIntegrityValue2 = pdINTEGRITY_CHECK_VALUE
 126         #define listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList )          ( pxList )->xListIntegrityValue1 = pdINTEGRITY_CHECK_VALUE
 127         #define listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList )          ( pxList )->xListIntegrityValue2 = pdINTEGRITY_CHECK_VALUE
 128
 129         /* Define macros that will assert if one of the structure members does not
 130         contain its expected value. */
 131         #define listTEST_LIST_ITEM_INTEGRITY( pxItem )          configASSERT( ( ( pxItem )->xListItemIntegrityValue1 == pdINTEGRITY_CHECK_VALUE ) && ( ( pxItem )->xListItemIntegrityValue2 == pdINTEGRITY_CHECK_VALUE ) )
 132         #define listTEST_LIST_INTEGRITY( pxList )                       configASSERT( ( ( pxList )->xListIntegrityValue1 == pdINTEGRITY_CHECK_VALUE ) && ( ( pxList )->xListIntegrityValue2 == pdINTEGRITY_CHECK_VALUE ) )
 133 #endif /* configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES */
 134
 135
 136 /*
 137  * Definition of the only type of object that a list can contain.
 138  */
 139 struct xLIST;
 140 struct xLIST_ITEM
 141 {
 142         listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE                       /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
 143         configLIST_VOLATILE TickType_t xItemValue;                      /*< The value being listed.  In most cases this is used to sort the list in descending order. */
 144         struct xLIST_ITEM * configLIST_VOLATILE pxNext;         /*< Pointer to the next ListItem_t in the list. */
 145         struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;     /*< Pointer to the previous ListItem_t in the list. */
 146         void * pvOwner;                                                                         /*< Pointer to the object (normally a TCB) that contains the list item.  There is therefore a two way link between the object containing the list item and the list item itself. */
 147         struct xLIST * configLIST_VOLATILE pxContainer;         /*< Pointer to the list in which this list item is placed (if any). */
 148         listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE                      /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
 149 };
 150 typedef struct xLIST_ITEM ListItem_t;                                   /* For some reason lint wants this as two separate definitions. */
 151
 152 struct xMINI_LIST_ITEM
 153 {
 154         listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE                       /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
 155         configLIST_VOLATILE TickType_t xItemValue;
 156         struct xLIST_ITEM * configLIST_VOLATILE pxNext;
 157         struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
 158 };
 159 typedef struct xMINI_LIST_ITEM MiniListItem_t;
 160
 161 /*
 162  * Definition of the type of queue used by the scheduler.
 163  */
 164 typedef struct xLIST
 165 {
 166         listFIRST_LIST_INTEGRITY_CHECK_VALUE                            /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
 167         volatile UBaseType_t uxNumberOfItems;
 168         ListItem_t * configLIST_VOLATILE pxIndex;                       /*< Used to walk through the list.  Points to the last item returned by a call to listGET_OWNER_OF_NEXT_ENTRY (). */
 169         MiniListItem_t xListEnd;                                                        /*< List item that contains the maximum possible item value meaning it is always at the end of the list and is therefore used as a marker. */
 170         listSECOND_LIST_INTEGRITY_CHECK_VALUE                           /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
 171 } List_t;
 172
 173 /*
 174  * Access macro to set the owner of a list item.  The owner of a list item
 175  * is the object (usually a TCB) that contains the list item.
 176  *
 177  * \page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER
 178  * \ingroup LinkedList
 179  */
 180 #define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )          ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )
 181
 182 /*
 183  * Access macro to get the owner of a list item.  The owner of a list item
 184  * is the object (usually a TCB) that contains the list item.
 185  *
 186  * \page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER
 187  * \ingroup LinkedList
 188  */
 189 #define listGET_LIST_ITEM_OWNER( pxListItem )   ( ( pxListItem )->pvOwner )
 190
 191 /*
 192  * Access macro to set the value of the list item.  In most cases the value is
 193  * used to sort the list in descending order.
 194  *
 195  * \page listSET_LIST_ITEM_VALUE listSET_LIST_ITEM_VALUE
 196  * \ingroup LinkedList
 197  */
 198 #define listSET_LIST_ITEM_VALUE( pxListItem, xValue )   ( ( pxListItem )->xItemValue = ( xValue ) )
 199
 200 /*
 201  * Access macro to retrieve the value of the list item.  The value can
 202  * represent anything - for example the priority of a task, or the time at
 203  * which a task should be unblocked.
 204  *
 205  * \page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE
 206  * \ingroup LinkedList
 207  */
 208 #define listGET_LIST_ITEM_VALUE( pxListItem )   ( ( pxListItem )->xItemValue )
 209
 210 /*
 211  * Access macro to retrieve the value of the list item at the head of a given
 212  * list.
 213  *
 214  * \page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE
 215  * \ingroup LinkedList
 216  */
 217 #define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )      ( ( ( pxList )->xListEnd ).pxNext->xItemValue )
 218
 219 /*
 220  * Return the list item at the head of the list.
 221  *
 222  * \page listGET_HEAD_ENTRY listGET_HEAD_ENTRY
 223  * \ingroup LinkedList
 224  */
 225 #define listGET_HEAD_ENTRY( pxList )    ( ( ( pxList )->xListEnd ).pxNext )
 226
 227 /*
 228  * Return the list item at the head of the list.
 229  *
 230  * \page listGET_NEXT listGET_NEXT
 231  * \ingroup LinkedList
 232  */
 233 #define listGET_NEXT( pxListItem )      ( ( pxListItem )->pxNext )
 234
 235 /*
 236  * Return the list item that marks the end of the list
 237  *
 238  * \page listGET_END_MARKER listGET_END_MARKER
 239  * \ingroup LinkedList
 240  */
 241 #define listGET_END_MARKER( pxList )    ( ( ListItem_t const * ) ( &( ( pxList )->xListEnd ) ) )
 242
 243 /*
 244  * Access macro to determine if a list contains any items.  The macro will
 245  * only have the value true if the list is empty.
 246  *
 247  * \page listLIST_IS_EMPTY listLIST_IS_EMPTY
 248  * \ingroup LinkedList
 249  */
 250 #define listLIST_IS_EMPTY( pxList )     ( ( ( pxList )->uxNumberOfItems == ( UBaseType_t ) 0 ) ? pdTRUE : pdFALSE )
 251
 252 /*
 253  * Access macro to return the number of items in the list.
 254  */
 255 #define listCURRENT_LIST_LENGTH( pxList )       ( ( pxList )->uxNumberOfItems )
 256
 257 /*
 258  * Access function to obtain the owner of the next entry in a list.
 259  *
 260  * The list member pxIndex is used to walk through a list.  Calling
 261  * listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list
 262  * and returns that entry's pxOwner parameter.  Using multiple calls to this
 263  * function it is therefore possible to move through every item contained in
 264  * a list.
 265  *
 266  * The pxOwner parameter of a list item is a pointer to the object that owns
 267  * the list item.  In the scheduler this is normally a task control block.
 268  * The pxOwner parameter effectively creates a two way link between the list
 269  * item and its owner.
 270  *
 271  * @param pxTCB pxTCB is set to the address of the owner of the next list item.
 272  * @param pxList The list from which the next item owner is to be returned.
 273  *
 274  * \page listGET_OWNER_OF_NEXT_ENTRY listGET_OWNER_OF_NEXT_ENTRY
 275  * \ingroup LinkedList
 276  */
 277 #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                                                            \
 278 {                                                                                                                                                                                       \
 279 List_t * const pxConstList = ( pxList );                                                                                                        \
 280         /* Increment the index to the next item and return the item, ensuring */                                \
 281         /* we don't return the marker used at the end of the list.  */                                                  \
 282         ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                                                    \
 283         if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )  \
 284         {                                                                                                                                                                               \
 285                 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                                            \
 286         }                                                                                                                                                                               \
 287         ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                                                                  \
 288 }
 289
 290
 291 /*
 292  * Access function to obtain the owner of the first entry in a list.  Lists
 293  * are normally sorted in ascending item value order.
 294  *
 295  * This function returns the pxOwner member of the first item in the list.
 296  * The pxOwner parameter of a list item is a pointer to the object that owns
 297  * the list item.  In the scheduler this is normally a task control block.
 298  * The pxOwner parameter effectively creates a two way link between the list
 299  * item and its owner.
 300  *
 301  * @param pxList The list from which the owner of the head item is to be
 302  * returned.
 303  *
 304  * \page listGET_OWNER_OF_HEAD_ENTRY listGET_OWNER_OF_HEAD_ENTRY
 305  * \ingroup LinkedList
 306  */
 307 #define listGET_OWNER_OF_HEAD_ENTRY( pxList )  ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner )
 308
 309 /*
 310  * Check to see if a list item is within a list.  The list item maintains a
 311  * "container" pointer that points to the list it is in.  All this macro does
 312  * is check to see if the container and the list match.
 313  *
 314  * @param pxList The list we want to know if the list item is within.
 315  * @param pxListItem The list item we want to know if is in the list.
 316  * @return pdTRUE if the list item is in the list, otherwise pdFALSE.
 317  */
 318 #define listIS_CONTAINED_WITHIN( pxList, pxListItem ) ( ( ( pxListItem )->pxContainer == ( pxList ) ) ? ( pdTRUE ) : ( pdFALSE ) )
 319
 320 /*
 321  * Return the list a list item is contained within (referenced from).
 322  *
 323  * @param pxListItem The list item being queried.
 324  * @return A pointer to the List_t object that references the pxListItem
 325  */
 326 #define listLIST_ITEM_CONTAINER( pxListItem ) ( ( pxListItem )->pxContainer )
 327
 328 /*
 329  * This provides a crude means of knowing if a list has been initialised, as
 330  * pxList->xListEnd.xItemValue is set to portMAX_DELAY by the vListInitialise()
 331  * function.
 332  */
 333 #define listLIST_IS_INITIALISED( pxList ) ( ( pxList )->xListEnd.xItemValue == portMAX_DELAY )
 334
 335 /*
 336  * Must be called before a list is used!  This initialises all the members
 337  * of the list structure and inserts the xListEnd item into the list as a
 338  * marker to the back of the list.
 339  *
 340  * @param pxList Pointer to the list being initialised.
 341  *
 342  * \page vListInitialise vListInitialise
 343  * \ingroup LinkedList
 344  */
 345 void vListInitialise( List_t * const pxList ) PRIVILEGED_FUNCTION;
 346
 347 /*
 348  * Must be called before a list item is used.  This sets the list container to
 349  * null so the item does not think that it is already contained in a list.
 350  *
 351  * @param pxItem Pointer to the list item being initialised.
 352  *
 353  * \page vListInitialiseItem vListInitialiseItem
 354  * \ingroup LinkedList
 355  */
 356 void vListInitialiseItem( ListItem_t * const pxItem ) PRIVILEGED_FUNCTION;
 357
 358 /*
 359  * Insert a list item into a list.  The item will be inserted into the list in
 360  * a position determined by its item value (descending item value order).
 361  *
 362  * @param pxList The list into which the item is to be inserted.
 363  *
 364  * @param pxNewListItem The item that is to be placed in the list.
 365  *
 366  * \page vListInsert vListInsert
 367  * \ingroup LinkedList
 368  */
 369 void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem ) PRIVILEGED_FUNCTION;
 370
 371 /*
 372  * Insert a list item into a list.  The item will be inserted in a position
 373  * such that it will be the last item within the list returned by multiple
 374  * calls to listGET_OWNER_OF_NEXT_ENTRY.
 375  *
 376  * The list member pxIndex is used to walk through a list.  Calling
 377  * listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list.
 378  * Placing an item in a list using vListInsertEnd effectively places the item
 379  * in the list position pointed to by pxIndex.  This means that every other
 380  * item within the list will be returned by listGET_OWNER_OF_NEXT_ENTRY before
 381  * the pxIndex parameter again points to the item being inserted.
 382  *
 383  * @param pxList The list into which the item is to be inserted.
 384  *
 385  * @param pxNewListItem The list item to be inserted into the list.
 386  *
 387  * \page vListInsertEnd vListInsertEnd
 388  * \ingroup LinkedList
 389  */
 390 void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem ) PRIVILEGED_FUNCTION;
 391
 392 /*
 393  * Remove an item from a list.  The list item has a pointer to the list that
 394  * it is in, so only the list item need be passed into the function.
 395  *
 396  * @param uxListRemove The item to be removed.  The item will remove itself from
 397  * the list pointed to by it's pxContainer parameter.
 398  *
 399  * @return The number of items that remain in the list after the list item has
 400  * been removed.
 401  *
 402  * \page uxListRemove uxListRemove
 403  * \ingroup LinkedList
 404  */
 405 UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove ) PRIVILEGED_FUNCTION;
 406
 407 #ifdef __cplusplus
 408 }
 409 #endif
 410
 411 #endif
 412