os/7.4.0/include/os/list.h

   1 /**
   2     FreeRTOS V7.4.0 - Copyright (C) 2013 Real Time Engineers Ltd.
   3
   4     FEATURES AND PORTS ARE ADDED TO FREERTOS ALL THE TIME.  PLEASE VISIT
   5     http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION.
   6
   7     ***************************************************************************
   8      *                                                                       *
   9      *    FreeRTOS tutorial books are available in pdf and paperback.        *
  10      *    Complete, revised, and edited pdf reference manuals are also       *
  11      *    available.                                                         *
  12      *                                                                       *
  13      *    Purchasing FreeRTOS documentation will not only help you, by       *
  14      *    ensuring you get running as quickly as possible and with an        *
  15      *    in-depth knowledge of how to use FreeRTOS, it will also help       *
  16      *    the FreeRTOS project to continue with its mission of providing     *
  17      *    professional grade, cross platform, de facto standard solutions    *
  18      *    for microcontrollers - completely free of charge!                  *
  19      *                                                                       *
  20      *    >>> See http://www.FreeRTOS.org/Documentation for details. <<<     *
  21      *                                                                       *
  22      *    Thank you for using FreeRTOS, and thank you for your support!      *
  23      *                                                                       *
  24     ***************************************************************************
  25
  26
  27     This file is part of the FreeRTOS distribution.
  28
  29     FreeRTOS is free software; you can redistribute it and/or modify it under
  30     the terms of the GNU General Public License (version 2) as published by the
  31     Free Software Foundation AND MODIFIED BY the FreeRTOS exception.
  32
  33     >>>>>>NOTE<<<<<< The modification to the GPL is included to allow you to
  34     distribute a combined work that includes FreeRTOS without being obliged to
  35     provide the source code for proprietary components outside of the FreeRTOS
  36     kernel.
  37
  38     FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY
  39     WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  40     FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  41     details. You should have received a copy of the GNU General Public License
  42     and the FreeRTOS license exception along with FreeRTOS; if not itcan be
  43     viewed here: http://www.freertos.org/a00114.html and also obtained by
  44     writing to Real Time Engineers Ltd., contact details for whom are available
  45     on the FreeRTOS WEB site.
  46
  47     1 tab == 4 spaces!
  48
  49     ***************************************************************************
  50      *                                                                       *
  51      *    Having a problem?  Start by reading the FAQ "My application does   *
  52      *    not run, what could be wrong?"                                     *
  53      *                                                                       *
  54      *    http://www.FreeRTOS.org/FAQHelp.html                               *
  55      *                                                                       *
  56     ***************************************************************************
  57
  58
  59     http://www.FreeRTOS.org - Documentation, books, training, latest versions,
  60     license and Real Time Engineers Ltd. contact details.
  61
  62     http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products,
  63     including FreeRTOS+Trace - an indispensable productivity tool, and our new
  64     fully thread aware and reentrant UDP/IP stack.
  65
  66     http://www.OpenRTOS.com - Real Time Engineers ltd license FreeRTOS to High
  67     Integrity Systems, who sell the code with commercial support,
  68     indemnification and middleware, under the OpenRTOS brand.
  69
  70     http://www.SafeRTOS.com - High Integrity Systems also provide a safety
  71     engineered and independently SIL3 certified version for use in safety and
  72     mission critical applications that require provable dependability.
  73 */
  74
  75 /**
  76  * This is the list implementation used by the scheduler.  While it is tailored
  77  * heavily for the schedulers needs, it is also available for use by
  78  * application code.
  79  *
  80  * xLists can only store pointers to xListItems.  Each xListItem contains a
  81  * numeric value (xItemValue).  Most of the time the lists are sorted in
  82  * descending item value order.
  83  *
  84  * Lists are created already containing one list item.  The value of this
  85  * item is the maximum possible that can be stored, it is therefore always at
  86  * the end of the list and acts as a marker.  The list member pxHead always
  87  * points to this marker - even though it is at the tail of the list.  This
  88  * is because the tail contains a wrap back pointer to the true head of
  89  * the list.
  90  *
  91  * In addition to it's value, each list item contains a pointer to the next
  92  * item in the list (pxNext), a pointer to the list it is in (pxContainer)
  93  * and a pointer to back to the object that contains it.  These later two
  94  * pointers are included for efficiency of list manipulation.  There is
  95  * effectively a two way link between the object containing the list item and
  96  * the list item itself.
  97  *
  98  *
  99  * @ingroup FreeRTOSIntro
 100  */
 101
 102
 103 #ifndef LIST_H
 104 #define LIST_H
 105
 106 #ifdef __cplusplus
 107 extern "C" {
 108 #endif
 109 /**
 110  * Definition of the only type of object that a list can contain.
 111  */
 112 struct xLIST_ITEM
 113 {
 114     portTickType xItemValue;                /**< The value being listed.  In most cases this is used to sort the list in descending order. */
 115     volatile struct xLIST_ITEM * pxNext;    /**< Pointer to the next xListItem in the list. */
 116     volatile struct xLIST_ITEM * pxPrevious;/**< Pointer to the previous xListItem in the list. */
 117     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. */
 118     void * pvContainer;                     /**< Pointer to the list in which this list item is placed (if any). */
 119 };
 120 typedef struct xLIST_ITEM xListItem;        /** For some reason lint wants this as two separate definitions. */
 121
 122 struct xMINI_LIST_ITEM
 123 {
 124     portTickType xItemValue;
 125     volatile struct xLIST_ITEM *pxNext;
 126     volatile struct xLIST_ITEM *pxPrevious;
 127 };
 128 typedef struct xMINI_LIST_ITEM xMiniListItem;
 129
 130 /**
 131  * Definition of the type of queue used by the scheduler.
 132  */
 133 typedef struct xLIST
 134 {
 135     volatile unsigned portBASE_TYPE uxNumberOfItems;
 136     volatile xListItem * pxIndex;           /**< Used to walk through the list.  Points to the last item returned by a call to pvListGetOwnerOfNextEntry (). */
 137     volatile 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. */
 138 } xList;
 139
 140 /**
 141  * Access macro to set the owner of a list item.  The owner of a list item
 142  * is the object (usually a TCB) that contains the list item.
 143  *
 144  * @ingroup LinkedList
 145  */
 146 #define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )      ( pxListItem )->pvOwner = ( void * ) ( pxOwner )
 147
 148 /**
 149  * Access macro to get the owner of a list item.  The owner of a list item
 150  * is the object (usually a TCB) that contains the list item.
 151  *
 152  * @ingroup LinkedList
 153  */
 154 #define listGET_LIST_ITEM_OWNER( pxListItem )       ( pxListItem )->pvOwner
 155
 156 /**
 157  * Access macro to set the value of the list item.  In most cases the value is
 158  * used to sort the list in descending order.
 159  *
 160  * @ingroup LinkedList
 161  */
 162 #define listSET_LIST_ITEM_VALUE( pxListItem, xValue )       ( pxListItem )->xItemValue = ( xValue )
 163
 164 /**
 165  * Access macro to retrieve the value of the list item.  The value can
 166  * represent anything - for example a the priority of a task, or the time at
 167  * which a task should be unblocked.
 168  *
 169  * @ingroup LinkedList
 170  */
 171 #define listGET_LIST_ITEM_VALUE( pxListItem )               ( ( pxListItem )->xItemValue )
 172
 173 /**
 174  * Access macro the retrieve the value of the list item at the head of a given
 175  * list.
 176  *
 177  * @ingroup LinkedList
 178  */
 179 #define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )          ( (&( ( pxList )->xListEnd ))->pxNext->xItemValue )
 180
 181 /**
 182  * Access macro to determine if a list contains any items.  The macro will
 183  * only have the value true if the list is empty.
 184  *
 185  * @ingroup LinkedList
 186  */
 187 #define listLIST_IS_EMPTY( pxList )             ( ( pxList )->uxNumberOfItems == ( unsigned portBASE_TYPE ) 0 )
 188
 189 /**
 190  * Access macro to return the number of items in the list.
 191  */
 192 #define listCURRENT_LIST_LENGTH( pxList )       ( ( pxList )->uxNumberOfItems )
 193
 194 /**
 195  * Access function to obtain the owner of the next entry in a list.
 196  *
 197  * The list member pxIndex is used to walk through a list.  Calling
 198  * listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list
 199  * and returns that entries pxOwner parameter.  Using multiple calls to this
 200  * function it is therefore possible to move through every item contained in
 201  * a list.
 202  *
 203  * The pxOwner parameter of a list item is a pointer to the object that owns
 204  * the list item.  In the scheduler this is normally a task control block.
 205  * The pxOwner parameter effectively creates a two way link between the list
 206  * item and its owner.
 207  *
 208  * @param pxList The list from which the next item owner is to be returned.
 209  *
 210  * @ingroup LinkedList
 211  */
 212 #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                    \
 213 {                                                                                       \
 214 xList * const pxConstList = ( pxList );                                                 \
 215     /** Increment the index to the next item and return the item, ensuring */           \
 216     /** we don't return the marker used at the end of the list.  */                     \
 217     ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                        \
 218     if( ( pxConstList )->pxIndex == ( xListItem * ) &( ( pxConstList )->xListEnd ) )    \
 219     {                                                                                   \
 220         ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                    \
 221     }                                                                                   \
 222     ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                      \
 223 }
 224
 225
 226 /**
 227  * Access function to obtain the owner of the first entry in a list.  Lists
 228  * are normally sorted in ascending item value order.
 229  *
 230  * This function returns the pxOwner member of the first item in the list.
 231  * The pxOwner parameter of a list item is a pointer to the object that owns
 232  * the list item.  In the scheduler this is normally a task control block.
 233  * The pxOwner parameter effectively creates a two way link between the list
 234  * item and its owner.
 235  *
 236  * @param pxList The list from which the owner of the head item is to be
 237  * returned.
 238  *
 239  * @ingroup LinkedList
 240  */
 241 #define listGET_OWNER_OF_HEAD_ENTRY( pxList )  ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner )
 242
 243 /**
 244  * Check to see if a list item is within a list.  The list item maintains a
 245  * "container" pointer that points to the list it is in.  All this macro does
 246  * is check to see if the container and the list match.
 247  *
 248  * @param pxList The list we want to know if the list item is within.
 249  * @param pxListItem The list item we want to know if is in the list.
 250  * @return pdTRUE is the list item is in the list, otherwise pdFALSE.
 251  * pointer against
 252  */
 253 #define listIS_CONTAINED_WITHIN( pxList, pxListItem ) ( ( pxListItem )->pvContainer == ( void * ) ( pxList ) )
 254
 255 /**
 256  * Return the list a list item is contained within (referenced from).
 257  *
 258  * @param pxListItem The list item being queried.
 259  * @return A pointer to the xList object that references the pxListItem
 260  */
 261 #define listLIST_ITEM_CONTAINER( pxListItem ) ( ( pxListItem )->pvContainer )
 262
 263 /**
 264  * This provides a crude means of knowing if a list has been initialised, as
 265  * pxList->xListEnd.xItemValue is set to portMAX_DELAY by the vListInitialise()
 266  * function.
 267  */
 268 #define listLIST_IS_INITIALISED( pxList ) ( ( pxList )->xListEnd.xItemValue == portMAX_DELAY )
 269
 270 /**
 271  * Must be called before a list is used!  This initialises all the members
 272  * of the list structure and inserts the xListEnd item into the list as a
 273  * marker to the back of the list.
 274  *
 275  * @param pxList Pointer to the list being initialised.
 276  *
 277  * @ingroup LinkedList
 278  */
 279 void vListInitialise( xList *pxList );
 280
 281 /**
 282  * Must be called before a list item is used.  This sets the list container to
 283  * null so the item does not think that it is already contained in a list.
 284  *
 285  * @param pxItem Pointer to the list item being initialised.
 286  *
 287  * @ingroup LinkedList
 288  */
 289 void vListInitialiseItem( xListItem *pxItem );
 290
 291 /**
 292  * Insert a list item into a list.  The item will be inserted into the list in
 293  * a position determined by its item value (descending item value order).
 294  *
 295  * @param pxList The list into which the item is to be inserted.
 296  *
 297  * @param pxNewListItem The item to that is to be placed in the list.
 298  *
 299  * @ingroup LinkedList
 300  */
 301 void vListInsert( xList *pxList, xListItem *pxNewListItem );
 302
 303 /**
 304  * Insert a list item into a list.  The item will be inserted in a position
 305  * such that it will be the last item within the list returned by multiple
 306  * calls to listGET_OWNER_OF_NEXT_ENTRY.
 307  *
 308  * The list member pvIndex is used to walk through a list.  Calling
 309  * listGET_OWNER_OF_NEXT_ENTRY increments pvIndex to the next item in the list.
 310  * Placing an item in a list using vListInsertEnd effectively places the item
 311  * in the list position pointed to by pvIndex.  This means that every other
 312  * item within the list will be returned by listGET_OWNER_OF_NEXT_ENTRY before
 313  * the pvIndex parameter again points to the item being inserted.
 314  *
 315  * @param pxList The list into which the item is to be inserted.
 316  *
 317  * @param pxNewListItem The list item to be inserted into the list.
 318  *
 319  * @ingroup LinkedList
 320  */
 321 void vListInsertEnd( xList *pxList, xListItem *pxNewListItem );
 322
 323 /**
 324  * Remove an item from a list.  The list item has a pointer to the list that
 325  * it is in, so only the list item need be passed into the function.
 326  *
 327  * @param uxListRemove The item to be removed.  The item will remove itself from
 328  * the list pointed to by it's pxContainer parameter.
 329  *
 330  * @return The number of items that remain in the list after the list item has
 331  * been removed.
 332  *
 333  * @ingroup LinkedList
 334  */
 335 unsigned portBASE_TYPE uxListRemove( xListItem *pxItemToRemove );
 336
 337 #ifdef __cplusplus
 338 }
 339 #endif
 340
 341 #endif
 342