os/7.0.2/include/os/list.h

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