list.h

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