list.h

00001 /*
00002     FreeRTOS V7.6.0 - Copyright (C) 2013 Real Time Engineers Ltd. 
00003     All rights reserved
00004 
00005     VISIT http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION.
00006 
00007     ***************************************************************************
00008      *                                                                       *
00009      *    FreeRTOS provides completely free yet professionally developed,    *
00010      *    robust, strictly quality controlled, supported, and cross          *
00011      *    platform software that has become a de facto standard.             *
00012      *                                                                       *
00013      *    Help yourself get started quickly and support the FreeRTOS         *
00014      *    project by purchasing a FreeRTOS tutorial book, reference          *
00015      *    manual, or both from: http://www.FreeRTOS.org/Documentation        *
00016      *                                                                       *
00017      *    Thank you!                                                         *
00018      *                                                                       *
00019     ***************************************************************************
00020 
00021     This file is part of the FreeRTOS distribution.
00022 
00023     FreeRTOS is free software; you can redistribute it and/or modify it under
00024     the terms of the GNU General Public License (version 2) as published by the
00025     Free Software Foundation >>!AND MODIFIED BY!<< the FreeRTOS exception.
00026 
00027     >>! NOTE: The modification to the GPL is included to allow you to distribute
00028     >>! a combined work that includes FreeRTOS without being obliged to provide
00029     >>! the source code for proprietary components outside of the FreeRTOS
00030     >>! kernel.
00031 
00032     FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY
00033     WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00034     FOR A PARTICULAR PURPOSE.  Full license text is available from the following
00035     link: http://www.freertos.org/a00114.html
00036 
00037     1 tab == 4 spaces!
00038 
00039     ***************************************************************************
00040      *                                                                       *
00041      *    Having a problem?  Start by reading the FAQ "My application does   *
00042      *    not run, what could be wrong?"                                     *
00043      *                                                                       *
00044      *    http://www.FreeRTOS.org/FAQHelp.html                               *
00045      *                                                                       *
00046     ***************************************************************************
00047 
00048     http://www.FreeRTOS.org - Documentation, books, training, latest versions,
00049     license and Real Time Engineers Ltd. contact details.
00050 
00051     http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products,
00052     including FreeRTOS+Trace - an indispensable productivity tool, a DOS
00053     compatible FAT file system, and our tiny thread aware UDP/IP stack.
00054 
00055     http://www.OpenRTOS.com - Real Time Engineers ltd license FreeRTOS to High
00056     Integrity Systems to sell under the OpenRTOS brand.  Low cost OpenRTOS
00057     licenses offer ticketed support, indemnification and middleware.
00058 
00059     http://www.SafeRTOS.com - High Integrity Systems also provide a safety
00060     engineered and independently SIL3 certified version for use in safety and
00061     mission critical applications that require provable dependability.
00062 
00063     1 tab == 4 spaces!
00064 */
00065 
00066 /*
00067  * This is the list implementation used by the scheduler.  While it is tailored
00068  * heavily for the schedulers needs, it is also available for use by
00069  * application code.
00070  *
00071  * xLists can only store pointers to xListItems.  Each xListItem contains a
00072  * numeric value (xItemValue).  Most of the time the lists are sorted in
00073  * descending item value order.
00074  *
00075  * Lists are created already containing one list item.  The value of this
00076  * item is the maximum possible that can be stored, it is therefore always at
00077  * the end of the list and acts as a marker.  The list member pxHead always
00078  * points to this marker - even though it is at the tail of the list.  This
00079  * is because the tail contains a wrap back pointer to the true head of
00080  * the list.
00081  *
00082  * In addition to it's value, each list item contains a pointer to the next
00083  * item in the list (pxNext), a pointer to the list it is in (pxContainer)
00084  * and a pointer to back to the object that contains it.  These later two
00085  * pointers are included for efficiency of list manipulation.  There is
00086  * effectively a two way link between the object containing the list item and
00087  * the list item itself.
00088  *
00089  *
00090  * \page ListIntroduction List Implementation
00091  * \ingroup FreeRTOSIntro
00092  */
00093 
00094 
00095 #ifndef LIST_H
00096 #define LIST_H
00097 
00098 /*
00099  * The list structure members are modified from within interrupts, and therefore
00100  * by rights should be declared volatile.  However, they are only modified in a
00101  * functionally atomic way (within critical sections of with the scheduler
00102  * suspended) and are either passed by reference into a function or indexed via
00103  * a volatile variable.  Therefore, in all use cases tested so far, the volatile
00104  * qualifier can be omitted in order to provide a moderate performance
00105  * improvement without adversely affecting functional behaviour.  The assembly
00106  * instructions generated by the IAR, ARM and GCC compilers when the respective
00107  * compiler's options were set for maximum optimisation has been inspected and
00108  * deemed to be as intended.  That said, as compiler technology advances, and
00109  * especially if aggressive cross module optimisation is used (a use case that
00110  * has not been exercised to any great extend) then it is feasible that the
00111  * volatile qualifier will be needed for correct optimisation.  It is expected
00112  * that a compiler removing essential code because, without the volatile
00113  * qualifier on the list structure members and with aggressive cross module
00114  * optimisation, the compiler deemed the code unnecessary will result in
00115  * complete and obvious failure of the scheduler.  If this is ever experienced
00116  * then the volatile qualifier can be inserted in the relevant places within the
00117  * list structures by simply defining configLIST_VOLATILE to volatile in
00118  * FreeRTOSConfig.h (as per the example at the bottom of this comment block).  
00119  * If configLIST_VOLATILE is not defined then the preprocessor directives below 
00120  * will simply #define configLIST_VOLATILE away completely.
00121  *
00122  * To use volatile list structure members then add the following line to
00123  * FreeRTOSConfig.h (without the quotes):
00124  * "#define configLIST_VOLATILE volatile"
00125  */
00126 #ifndef configLIST_VOLATILE
00127     #define configLIST_VOLATILE
00128 #endif /* configSUPPORT_CROSS_MODULE_OPTIMISATION */
00129 
00130 #ifdef __cplusplus
00131 extern "C" {
00132 #endif
00133 /*
00134  * Definition of the only type of object that a list can contain.
00135  */
00136 struct xLIST_ITEM
00137 {
00138     configLIST_VOLATILE portTickType xItemValue;    /*< The value being listed.  In most cases this is used to sort the list in descending order. */
00139     struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*< Pointer to the next xListItem in the list. */
00140     struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;/*< Pointer to the previous xListItem in the list. */
00141     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. */
00142     void * configLIST_VOLATILE pvContainer;         /*< Pointer to the list in which this list item is placed (if any). */
00143 };
00144 typedef struct xLIST_ITEM xListItem;                /* For some reason lint wants this as two separate definitions. */
00145 
00146 struct xMINI_LIST_ITEM
00147 {
00148     configLIST_VOLATILE portTickType xItemValue;
00149     struct xLIST_ITEM * configLIST_VOLATILE pxNext;
00150     struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
00151 };
00152 typedef struct xMINI_LIST_ITEM xMiniListItem;
00153 
00154 /*
00155  * Definition of the type of queue used by the scheduler.
00156  */
00157 typedef struct xLIST
00158 {
00159     configLIST_VOLATILE unsigned portBASE_TYPE uxNumberOfItems;
00160     xListItem * configLIST_VOLATILE pxIndex;        /*< Used to walk through the list.  Points to the last item returned by a call to pvListGetOwnerOfNextEntry (). */
00161     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. */
00162 } xList;
00163 
00164 /*
00165  * Access macro to set the owner of a list item.  The owner of a list item
00166  * is the object (usually a TCB) that contains the list item.
00167  *
00168  * \page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER
00169  * \ingroup LinkedList
00170  */
00171 #define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )      ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )
00172 
00173 /*
00174  * Access macro to get the owner of a list item.  The owner of a list item
00175  * is the object (usually a TCB) that contains the list item.
00176  *
00177  * \page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER
00178  * \ingroup LinkedList
00179  */
00180 #define listGET_LIST_ITEM_OWNER( pxListItem )       ( pxListItem )->pvOwner
00181 
00182 /*
00183  * Access macro to set the value of the list item.  In most cases the value is
00184  * used to sort the list in descending order.
00185  *
00186  * \page listSET_LIST_ITEM_VALUE listSET_LIST_ITEM_VALUE
00187  * \ingroup LinkedList
00188  */
00189 #define listSET_LIST_ITEM_VALUE( pxListItem, xValue )       ( ( pxListItem )->xItemValue = ( xValue ) )
00190 
00191 /*
00192  * Access macro to retrieve the value of the list item.  The value can
00193  * represent anything - for example a the priority of a task, or the time at
00194  * which a task should be unblocked.
00195  *
00196  * \page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE
00197  * \ingroup LinkedList
00198  */
00199 #define listGET_LIST_ITEM_VALUE( pxListItem )               ( ( pxListItem )->xItemValue )
00200 
00201 /*
00202  * Access macro the retrieve the value of the list item at the head of a given
00203  * list.
00204  *
00205  * \page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE
00206  * \ingroup LinkedList
00207  */
00208 #define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )          ( (&( ( pxList )->xListEnd ))->pxNext->xItemValue )
00209 
00210 /*
00211  * Access macro to determine if a list contains any items.  The macro will
00212  * only have the value true if the list is empty.
00213  *
00214  * \page listLIST_IS_EMPTY listLIST_IS_EMPTY
00215  * \ingroup LinkedList
00216  */
00217 #define listLIST_IS_EMPTY( pxList )             ( ( portBASE_TYPE ) ( ( pxList )->uxNumberOfItems == ( unsigned portBASE_TYPE ) 0 ) )
00218 
00219 /*
00220  * Access macro to return the number of items in the list.
00221  */
00222 #define listCURRENT_LIST_LENGTH( pxList )       ( ( pxList )->uxNumberOfItems )
00223 
00224 /*
00225  * Access function to obtain the owner of the next entry in a list.
00226  *
00227  * The list member pxIndex is used to walk through a list.  Calling
00228  * listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list
00229  * and returns that entries pxOwner parameter.  Using multiple calls to this
00230  * function it is therefore possible to move through every item contained in
00231  * a list.
00232  *
00233  * The pxOwner parameter of a list item is a pointer to the object that owns
00234  * the list item.  In the scheduler this is normally a task control block.
00235  * The pxOwner parameter effectively creates a two way link between the list
00236  * item and its owner.
00237  *
00238  * @param pxList The list from which the next item owner is to be returned.
00239  *
00240  * \page listGET_OWNER_OF_NEXT_ENTRY listGET_OWNER_OF_NEXT_ENTRY
00241  * \ingroup LinkedList
00242  */
00243 #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                        \
00244 {                                                                                           \
00245 xList * const pxConstList = ( pxList );                                                     \
00246     /* Increment the index to the next item and return the item, ensuring */                \
00247     /* we don't return the marker used at the end of the list.  */                          \
00248     ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                            \
00249     if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )  \
00250     {                                                                                       \
00251         ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                        \
00252     }                                                                                       \
00253     ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                          \
00254 }
00255 
00256 
00257 /*
00258  * Access function to obtain the owner of the first entry in a list.  Lists
00259  * are normally sorted in ascending item value order.
00260  *
00261  * This function returns the pxOwner member of the first item in the list.
00262  * The pxOwner parameter of a list item is a pointer to the object that owns
00263  * the list item.  In the scheduler this is normally a task control block.
00264  * The pxOwner parameter effectively creates a two way link between the list
00265  * item and its owner.
00266  *
00267  * @param pxList The list from which the owner of the head item is to be
00268  * returned.
00269  *
00270  * \page listGET_OWNER_OF_HEAD_ENTRY listGET_OWNER_OF_HEAD_ENTRY
00271  * \ingroup LinkedList
00272  */
00273 #define listGET_OWNER_OF_HEAD_ENTRY( pxList )  ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner )
00274 
00275 /*
00276  * Check to see if a list item is within a list.  The list item maintains a
00277  * "container" pointer that points to the list it is in.  All this macro does
00278  * is check to see if the container and the list match.
00279  *
00280  * @param pxList The list we want to know if the list item is within.
00281  * @param pxListItem The list item we want to know if is in the list.
00282  * @return pdTRUE is the list item is in the list, otherwise pdFALSE.
00283  * pointer against
00284  */
00285 #define listIS_CONTAINED_WITHIN( pxList, pxListItem ) ( ( portBASE_TYPE ) ( ( pxListItem )->pvContainer == ( void * ) ( pxList ) ) )
00286 
00287 /*
00288  * Return the list a list item is contained within (referenced from).
00289  *
00290  * @param pxListItem The list item being queried.
00291  * @return A pointer to the xList object that references the pxListItem
00292  */
00293 #define listLIST_ITEM_CONTAINER( pxListItem ) ( ( pxListItem )->pvContainer )
00294 
00295 /*
00296  * This provides a crude means of knowing if a list has been initialised, as
00297  * pxList->xListEnd.xItemValue is set to portMAX_DELAY by the vListInitialise()
00298  * function.
00299  */
00300 #define listLIST_IS_INITIALISED( pxList ) ( ( pxList )->xListEnd.xItemValue == portMAX_DELAY )
00301 
00302 /*
00303  * Must be called before a list is used!  This initialises all the members
00304  * of the list structure and inserts the xListEnd item into the list as a
00305  * marker to the back of the list.
00306  *
00307  * @param pxList Pointer to the list being initialised.
00308  *
00309  * \page vListInitialise vListInitialise
00310  * \ingroup LinkedList
00311  */
00312 void vListInitialise( xList * const pxList );
00313 
00314 /*
00315  * Must be called before a list item is used.  This sets the list container to
00316  * null so the item does not think that it is already contained in a list.
00317  *
00318  * @param pxItem Pointer to the list item being initialised.
00319  *
00320  * \page vListInitialiseItem vListInitialiseItem
00321  * \ingroup LinkedList
00322  */
00323 void vListInitialiseItem( xListItem * const pxItem );
00324 
00325 /*
00326  * Insert a list item into a list.  The item will be inserted into the list in
00327  * a position determined by its item value (descending item value order).
00328  *
00329  * @param pxList The list into which the item is to be inserted.
00330  *
00331  * @param pxNewListItem The item to that is to be placed in the list.
00332  *
00333  * \page vListInsert vListInsert
00334  * \ingroup LinkedList
00335  */
00336 void vListInsert( xList * const pxList, xListItem * const pxNewListItem );
00337 
00338 /*
00339  * Insert a list item into a list.  The item will be inserted in a position
00340  * such that it will be the last item within the list returned by multiple
00341  * calls to listGET_OWNER_OF_NEXT_ENTRY.
00342  *
00343  * The list member pvIndex is used to walk through a list.  Calling
00344  * listGET_OWNER_OF_NEXT_ENTRY increments pvIndex to the next item in the list.
00345  * Placing an item in a list using vListInsertEnd effectively places the item
00346  * in the list position pointed to by pvIndex.  This means that every other
00347  * item within the list will be returned by listGET_OWNER_OF_NEXT_ENTRY before
00348  * the pvIndex parameter again points to the item being inserted.
00349  *
00350  * @param pxList The list into which the item is to be inserted.
00351  *
00352  * @param pxNewListItem The list item to be inserted into the list.
00353  *
00354  * \page vListInsertEnd vListInsertEnd
00355  * \ingroup LinkedList
00356  */
00357 void vListInsertEnd( xList * const pxList, xListItem * const pxNewListItem );
00358 
00359 /*
00360  * Remove an item from a list.  The list item has a pointer to the list that
00361  * it is in, so only the list item need be passed into the function.
00362  *
00363  * @param uxListRemove The item to be removed.  The item will remove itself from
00364  * the list pointed to by it's pxContainer parameter.
00365  *
00366  * @return The number of items that remain in the list after the list item has
00367  * been removed.
00368  *
00369  * \page uxListRemove uxListRemove
00370  * \ingroup LinkedList
00371  */
00372 unsigned portBASE_TYPE uxListRemove( xListItem * const pxItemToRemove );
00373 
00374 #ifdef __cplusplus
00375 }
00376 #endif
00377 
00378 #endif
00379