git.sur5r.net Git - freertos/blob - FreeRTOS/Source/include/list.h

   1 /*\r
   2     FreeRTOS V7.5.1 - Copyright (C) 2013 Real Time Engineers Ltd.\r
   3 \r
   4     VISIT http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION.\r
   5 \r
   6     ***************************************************************************\r
   7      *                                                                       *\r
   8      *    FreeRTOS provides completely free yet professionally developed,    *\r
   9      *    robust, strictly quality controlled, supported, and cross          *\r
  10      *    platform software that has become a de facto standard.             *\r
  11      *                                                                       *\r
  12      *    Help yourself get started quickly and support the FreeRTOS         *\r
  13      *    project by purchasing a FreeRTOS tutorial book, reference          *\r
  14      *    manual, or both from: http://www.FreeRTOS.org/Documentation        *\r
  15      *                                                                       *\r
  16      *    Thank you!                                                         *\r
  17      *                                                                       *\r
  18     ***************************************************************************\r
  19 \r
  20     This file is part of the FreeRTOS distribution.\r
  21 \r
  22     FreeRTOS is free software; you can redistribute it and/or modify it under\r
  23     the terms of the GNU General Public License (version 2) as published by the\r
  24     Free Software Foundation >>!AND MODIFIED BY!<< the FreeRTOS exception.\r
  25 \r
  26     >>! NOTE: The modification to the GPL is included to allow you to distribute\r
  27     >>! a combined work that includes FreeRTOS without being obliged to provide\r
  28     >>! the source code for proprietary components outside of the FreeRTOS\r
  29     >>! kernel.\r
  30 \r
  31     FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY\r
  32     WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS\r
  33     FOR A PARTICULAR PURPOSE.  Full license text is available from the following\r
  34     link: http://www.freertos.org/a00114.html\r
  35 \r
  36     1 tab == 4 spaces!\r
  37 \r
  38     ***************************************************************************\r
  39      *                                                                       *\r
  40      *    Having a problem?  Start by reading the FAQ "My application does   *\r
  41      *    not run, what could be wrong?"                                     *\r
  42      *                                                                       *\r
  43      *    http://www.FreeRTOS.org/FAQHelp.html                               *\r
  44      *                                                                       *\r
  45     ***************************************************************************\r
  46 \r
  47     http://www.FreeRTOS.org - Documentation, books, training, latest versions,\r
  48     license and Real Time Engineers Ltd. contact details.\r
  49 \r
  50     http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products,\r
  51     including FreeRTOS+Trace - an indispensable productivity tool, a DOS\r
  52     compatible FAT file system, and our tiny thread aware UDP/IP stack.\r
  53 \r
  54     http://www.OpenRTOS.com - Real Time Engineers ltd license FreeRTOS to High\r
  55     Integrity Systems to sell under the OpenRTOS brand.  Low cost OpenRTOS\r
  56     licenses offer ticketed support, indemnification and middleware.\r
  57 \r
  58     http://www.SafeRTOS.com - High Integrity Systems also provide a safety\r
  59     engineered and independently SIL3 certified version for use in safety and\r
  60     mission critical applications that require provable dependability.\r
  61 \r
  62     1 tab == 4 spaces!\r
  63 */\r
  64 \r
  65 /*\r
  66  * This is the list implementation used by the scheduler.  While it is tailored\r
  67  * heavily for the schedulers needs, it is also available for use by\r
  68  * application code.\r
  69  *\r
  70  * xLists can only store pointers to xListItems.  Each xListItem contains a\r
  71  * numeric value (xItemValue).  Most of the time the lists are sorted in\r
  72  * descending item value order.\r
  73  *\r
  74  * Lists are created already containing one list item.  The value of this\r
  75  * item is the maximum possible that can be stored, it is therefore always at\r
  76  * the end of the list and acts as a marker.  The list member pxHead always\r
  77  * points to this marker - even though it is at the tail of the list.  This\r
  78  * is because the tail contains a wrap back pointer to the true head of\r
  79  * the list.\r
  80  *\r
  81  * In addition to it's value, each list item contains a pointer to the next\r
  82  * item in the list (pxNext), a pointer to the list it is in (pxContainer)\r
  83  * and a pointer to back to the object that contains it.  These later two\r
  84  * pointers are included for efficiency of list manipulation.  There is\r
  85  * effectively a two way link between the object containing the list item and\r
  86  * the list item itself.\r
  87  *\r
  88  *\r
  89  * \page ListIntroduction List Implementation\r
  90  * \ingroup FreeRTOSIntro\r
  91  */\r
  92 \r
  93 \r
  94 #ifndef LIST_H\r
  95 #define LIST_H\r
  96 \r
  97 /*\r
  98  * The list structure members are modified from within interrupts, and therefore\r
  99  * by rights should be declared volatile.  However, they are only modified in a\r
 100  * functionally atomic way (within critical sections of with the scheduler\r
 101  * suspended) and are either passed by reference into a function or indexed via\r
 102  * a volatile variable.  Therefore, in all use cases tested so far, the volatile\r
 103  * qualifier can be omitted in order to provide a moderate performance\r
 104  * improvement without adversely affecting functional behaviour.  The assembly\r
 105  * instructions generated by the IAR, ARM and GCC compilers when the respective\r
 106  * compiler's options were set for maximum optimisation has been inspected and\r
 107  * deemed to be as intended.  That said, as compiler technology advances, and\r
 108  * especially if aggressive cross module optimisation is used (a use case that\r
 109  * has not been exercised to any great extend) then it is feasible that the\r
 110  * volatile qualifier will be needed for correct optimisation.  It is expected\r
 111  * that a compiler removing essential code because, without the volatile\r
 112  * qualifier on the list structure members and with aggressive cross module\r
 113  * optimisation, the compiler deemed the code unnecessary will result in\r
 114  * complete and obvious failure of the scheduler.  If this is ever experienced\r
 115  * then the volatile qualifier can be inserted in the relevant places within the\r
 116  * list structures by simply defining configLIST_VOLATILE to volatile in\r
 117  * FreeRTOSConfig.h (as per the example at the bottom of this comment block).  \r
 118  * If configLIST_VOLATILE is not defined then the preprocessor directives below \r
 119  * will simply #define configLIST_VOLATILE away completely.\r
 120  *\r
 121  * To use volatile list structure members then add the following line to\r
 122  * FreeRTOSConfig.h (without the quotes):\r
 123  * "#define configLIST_VOLATILE volatile"\r
 124  */\r
 125 #ifndef configLIST_VOLATILE\r
 126         #define configLIST_VOLATILE\r
 127 #endif /* configSUPPORT_CROSS_MODULE_OPTIMISATION */\r
 128 \r
 129 #ifdef __cplusplus\r
 130 extern "C" {\r
 131 #endif\r
 132 /*\r
 133  * Definition of the only type of object that a list can contain.\r
 134  */\r
 135 struct xLIST_ITEM\r
 136 {\r
 137         configLIST_VOLATILE portTickType xItemValue;    /*< The value being listed.  In most cases this is used to sort the list in descending order. */\r
 138         struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*< Pointer to the next xListItem in the list. */\r
 139         struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;/*< Pointer to the previous xListItem in the list. */\r
 140         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. */\r
 141         void * configLIST_VOLATILE pvContainer;                 /*< Pointer to the list in which this list item is placed (if any). */\r
 142 };\r
 143 typedef struct xLIST_ITEM xListItem;                            /* For some reason lint wants this as two separate definitions. */\r
 144 \r
 145 struct xMINI_LIST_ITEM\r
 146 {\r
 147         configLIST_VOLATILE portTickType xItemValue;\r
 148         struct xLIST_ITEM * configLIST_VOLATILE pxNext;\r
 149         struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;\r
 150 };\r
 151 typedef struct xMINI_LIST_ITEM xMiniListItem;\r
 152 \r
 153 /*\r
 154  * Definition of the type of queue used by the scheduler.\r
 155  */\r
 156 typedef struct xLIST\r
 157 {\r
 158         configLIST_VOLATILE unsigned portBASE_TYPE uxNumberOfItems;\r
 159         xListItem * configLIST_VOLATILE pxIndex;                /*< Used to walk through the list.  Points to the last item returned by a call to pvListGetOwnerOfNextEntry (). */\r
 160         xMiniListItem 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. */\r
 161 } xList;\r
 162 \r
 163 /*\r
 164  * Access macro to set the owner of a list item.  The owner of a list item\r
 165  * is the object (usually a TCB) that contains the list item.\r
 166  *\r
 167  * \page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER\r
 168  * \ingroup LinkedList\r
 169  */\r
 170 #define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )          ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )\r
 171 \r
 172 /*\r
 173  * Access macro to get the owner of a list item.  The owner of a list item\r
 174  * is the object (usually a TCB) that contains the list item.\r
 175  *\r
 176  * \page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER\r
 177  * \ingroup LinkedList\r
 178  */\r
 179 #define listGET_LIST_ITEM_OWNER( pxListItem )           ( pxListItem )->pvOwner\r
 180 \r
 181 /*\r
 182  * Access macro to set the value of the list item.  In most cases the value is\r
 183  * used to sort the list in descending order.\r
 184  *\r
 185  * \page listSET_LIST_ITEM_VALUE listSET_LIST_ITEM_VALUE\r
 186  * \ingroup LinkedList\r
 187  */\r
 188 #define listSET_LIST_ITEM_VALUE( pxListItem, xValue )           ( ( pxListItem )->xItemValue = ( xValue ) )\r
 189 \r
 190 /*\r
 191  * Access macro to retrieve the value of the list item.  The value can\r
 192  * represent anything - for example a the priority of a task, or the time at\r
 193  * which a task should be unblocked.\r
 194  *\r
 195  * \page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE\r
 196  * \ingroup LinkedList\r
 197  */\r
 198 #define listGET_LIST_ITEM_VALUE( pxListItem )                           ( ( pxListItem )->xItemValue )\r
 199 \r
 200 /*\r
 201  * Access macro the retrieve the value of the list item at the head of a given\r
 202  * list.\r
 203  *\r
 204  * \page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE\r
 205  * \ingroup LinkedList\r
 206  */\r
 207 #define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )                      ( (&( ( pxList )->xListEnd ))->pxNext->xItemValue )\r
 208 \r
 209 /*\r
 210  * Access macro to determine if a list contains any items.  The macro will\r
 211  * only have the value true if the list is empty.\r
 212  *\r
 213  * \page listLIST_IS_EMPTY listLIST_IS_EMPTY\r
 214  * \ingroup LinkedList\r
 215  */\r
 216 #define listLIST_IS_EMPTY( pxList )                             ( ( portBASE_TYPE ) ( ( pxList )->uxNumberOfItems == ( unsigned portBASE_TYPE ) 0 ) )\r
 217 \r
 218 /*\r
 219  * Access macro to return the number of items in the list.\r
 220  */\r
 221 #define listCURRENT_LIST_LENGTH( pxList )               ( ( pxList )->uxNumberOfItems )\r
 222 \r
 223 /*\r
 224  * Access function to obtain the owner of the next entry in a list.\r
 225  *\r
 226  * The list member pxIndex is used to walk through a list.  Calling\r
 227  * listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list\r
 228  * and returns that entries pxOwner parameter.  Using multiple calls to this\r
 229  * function it is therefore possible to move through every item contained in\r
 230  * a list.\r
 231  *\r
 232  * The pxOwner parameter of a list item is a pointer to the object that owns\r
 233  * the list item.  In the scheduler this is normally a task control block.\r
 234  * The pxOwner parameter effectively creates a two way link between the list\r
 235  * item and its owner.\r
 236  *\r
 237  * @param pxList The list from which the next item owner is to be returned.\r
 238  *\r
 239  * \page listGET_OWNER_OF_NEXT_ENTRY listGET_OWNER_OF_NEXT_ENTRY\r
 240  * \ingroup LinkedList\r
 241  */\r
 242 #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                                                            \\r
 243 {                                                                                                                                                                                       \\r
 244 xList * const pxConstList = ( pxList );                                                                                                         \\r
 245         /* Increment the index to the next item and return the item, ensuring */                                \\r
 246         /* we don't return the marker used at the end of the list.  */                                                  \\r
 247         ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                                                    \\r
 248         if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )  \\r
 249         {                                                                                                                                                                               \\r
 250                 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                                            \\r
 251         }                                                                                                                                                                               \\r
 252         ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                                                                  \\r
 253 }\r
 254 \r
 255 \r
 256 /*\r
 257  * Access function to obtain the owner of the first entry in a list.  Lists\r
 258  * are normally sorted in ascending item value order.\r
 259  *\r
 260  * This function returns the pxOwner member of the first item in the list.\r
 261  * The pxOwner parameter of a list item is a pointer to the object that owns\r
 262  * the list item.  In the scheduler this is normally a task control block.\r
 263  * The pxOwner parameter effectively creates a two way link between the list\r
 264  * item and its owner.\r
 265  *\r
 266  * @param pxList The list from which the owner of the head item is to be\r
 267  * returned.\r
 268  *\r
 269  * \page listGET_OWNER_OF_HEAD_ENTRY listGET_OWNER_OF_HEAD_ENTRY\r
 270  * \ingroup LinkedList\r
 271  */\r
 272 #define listGET_OWNER_OF_HEAD_ENTRY( pxList )  ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner )\r
 273 \r
 274 /*\r
 275  * Check to see if a list item is within a list.  The list item maintains a\r
 276  * "container" pointer that points to the list it is in.  All this macro does\r
 277  * is check to see if the container and the list match.\r
 278  *\r
 279  * @param pxList The list we want to know if the list item is within.\r
 280  * @param pxListItem The list item we want to know if is in the list.\r
 281  * @return pdTRUE is the list item is in the list, otherwise pdFALSE.\r
 282  * pointer against\r
 283  */\r
 284 #define listIS_CONTAINED_WITHIN( pxList, pxListItem ) ( ( portBASE_TYPE ) ( ( pxListItem )->pvContainer == ( void * ) ( pxList ) ) )\r
 285 \r
 286 /*\r
 287  * Return the list a list item is contained within (referenced from).\r
 288  *\r
 289  * @param pxListItem The list item being queried.\r
 290  * @return A pointer to the xList object that references the pxListItem\r
 291  */\r
 292 #define listLIST_ITEM_CONTAINER( pxListItem ) ( ( pxListItem )->pvContainer )\r
 293 \r
 294 /*\r
 295  * This provides a crude means of knowing if a list has been initialised, as\r
 296  * pxList->xListEnd.xItemValue is set to portMAX_DELAY by the vListInitialise()\r
 297  * function.\r
 298  */\r
 299 #define listLIST_IS_INITIALISED( pxList ) ( ( pxList )->xListEnd.xItemValue == portMAX_DELAY )\r
 300 \r
 301 /*\r
 302  * Must be called before a list is used!  This initialises all the members\r
 303  * of the list structure and inserts the xListEnd item into the list as a\r
 304  * marker to the back of the list.\r
 305  *\r
 306  * @param pxList Pointer to the list being initialised.\r
 307  *\r
 308  * \page vListInitialise vListInitialise\r
 309  * \ingroup LinkedList\r
 310  */\r
 311 void vListInitialise( xList * const pxList );\r
 312 \r
 313 /*\r
 314  * Must be called before a list item is used.  This sets the list container to\r
 315  * null so the item does not think that it is already contained in a list.\r
 316  *\r
 317  * @param pxItem Pointer to the list item being initialised.\r
 318  *\r
 319  * \page vListInitialiseItem vListInitialiseItem\r
 320  * \ingroup LinkedList\r
 321  */\r
 322 void vListInitialiseItem( xListItem * const pxItem );\r
 323 \r
 324 /*\r
 325  * Insert a list item into a list.  The item will be inserted into the list in\r
 326  * a position determined by its item value (descending item value order).\r
 327  *\r
 328  * @param pxList The list into which the item is to be inserted.\r
 329  *\r
 330  * @param pxNewListItem The item to that is to be placed in the list.\r
 331  *\r
 332  * \page vListInsert vListInsert\r
 333  * \ingroup LinkedList\r
 334  */\r
 335 void vListInsert( xList * const pxList, xListItem * const pxNewListItem );\r
 336 \r
 337 /*\r
 338  * Insert a list item into a list.  The item will be inserted in a position\r
 339  * such that it will be the last item within the list returned by multiple\r
 340  * calls to listGET_OWNER_OF_NEXT_ENTRY.\r
 341  *\r
 342  * The list member pvIndex is used to walk through a list.  Calling\r
 343  * listGET_OWNER_OF_NEXT_ENTRY increments pvIndex to the next item in the list.\r
 344  * Placing an item in a list using vListInsertEnd effectively places the item\r
 345  * in the list position pointed to by pvIndex.  This means that every other\r
 346  * item within the list will be returned by listGET_OWNER_OF_NEXT_ENTRY before\r
 347  * the pvIndex parameter again points to the item being inserted.\r
 348  *\r
 349  * @param pxList The list into which the item is to be inserted.\r
 350  *\r
 351  * @param pxNewListItem The list item to be inserted into the list.\r
 352  *\r
 353  * \page vListInsertEnd vListInsertEnd\r
 354  * \ingroup LinkedList\r
 355  */\r
 356 void vListInsertEnd( xList * const pxList, xListItem * const pxNewListItem );\r
 357 \r
 358 /*\r
 359  * Remove an item from a list.  The list item has a pointer to the list that\r
 360  * it is in, so only the list item need be passed into the function.\r
 361  *\r
 362  * @param uxListRemove The item to be removed.  The item will remove itself from\r
 363  * the list pointed to by it's pxContainer parameter.\r
 364  *\r
 365  * @return The number of items that remain in the list after the list item has\r
 366  * been removed.\r
 367  *\r
 368  * \page uxListRemove uxListRemove\r
 369  * \ingroup LinkedList\r
 370  */\r
 371 unsigned portBASE_TYPE uxListRemove( xListItem * const pxItemToRemove );\r
 372 \r
 373 #ifdef __cplusplus\r
 374 }\r
 375 #endif\r
 376 \r
 377 #endif\r
 378 \r