/* FreeRTOS V8.0.0 - Copyright (C) 2014 Real Time Engineers Ltd. All rights reserved VISIT http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION. *************************************************************************** * * * FreeRTOS provides completely free yet professionally developed, * * robust, strictly quality controlled, supported, and cross * * platform software that has become a de facto standard. * * * * Help yourself get started quickly and support the FreeRTOS * * project by purchasing a FreeRTOS tutorial book, reference * * manual, or both from: http://www.FreeRTOS.org/Documentation * * * * Thank you! * * * *************************************************************************** This file is part of the FreeRTOS distribution. FreeRTOS is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License (version 2) as published by the Free Software Foundation >>!AND MODIFIED BY!<< the FreeRTOS exception. >>! NOTE: The modification to the GPL is included to allow you to distribute >>! a combined work that includes FreeRTOS without being obliged to provide >>! the source code for proprietary components outside of the FreeRTOS >>! kernel. FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Full license text is available from the following link: http://www.freertos.org/a00114.html 1 tab == 4 spaces! *************************************************************************** * * * Having a problem? Start by reading the FAQ "My application does * * not run, what could be wrong?" * * * * http://www.FreeRTOS.org/FAQHelp.html * * * *************************************************************************** http://www.FreeRTOS.org - Documentation, books, training, latest versions, license and Real Time Engineers Ltd. contact details. http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products, including FreeRTOS+Trace - an indispensable productivity tool, a DOS compatible FAT file system, and our tiny thread aware UDP/IP stack. http://www.OpenRTOS.com - Real Time Engineers ltd license FreeRTOS to High Integrity Systems to sell under the OpenRTOS brand. Low cost OpenRTOS licenses offer ticketed support, indemnification and middleware. http://www.SafeRTOS.com - High Integrity Systems also provide a safety engineered and independently SIL3 certified version for use in safety and mission critical applications that require provable dependability. 1 tab == 4 spaces! */ /* * This is the list implementation used by the scheduler. While it is tailored * heavily for the schedulers needs, it is also available for use by * application code. * * list_ts can only store pointers to list_item_ts. Each ListItem_t contains a * numeric value (xItemValue). Most of the time the lists are sorted in * descending item value order. * * Lists are created already containing one list item. The value of this * item is the maximum possible that can be stored, it is therefore always at * the end of the list and acts as a marker. The list member pxHead always * points to this marker - even though it is at the tail of the list. This * is because the tail contains a wrap back pointer to the true head of * the list. * * In addition to it's value, each list item contains a pointer to the next * item in the list (pxNext), a pointer to the list it is in (pxContainer) * and a pointer to back to the object that contains it. These later two * pointers are included for efficiency of list manipulation. There is * effectively a two way link between the object containing the list item and * the list item itself. * * * \page ListIntroduction List Implementation * \ingroup FreeRTOSIntro */ #ifndef LIST_H #define LIST_H /* * The list structure members are modified from within interrupts, and therefore * by rights should be declared volatile. However, they are only modified in a * functionally atomic way (within critical sections of with the scheduler * suspended) and are either passed by reference into a function or indexed via * a volatile variable. Therefore, in all use cases tested so far, the volatile * qualifier can be omitted in order to provide a moderate performance * improvement without adversely affecting functional behaviour. The assembly * instructions generated by the IAR, ARM and GCC compilers when the respective * compiler's options were set for maximum optimisation has been inspected and * deemed to be as intended. That said, as compiler technology advances, and * especially if aggressive cross module optimisation is used (a use case that * has not been exercised to any great extend) then it is feasible that the * volatile qualifier will be needed for correct optimisation. It is expected * that a compiler removing essential code because, without the volatile * qualifier on the list structure members and with aggressive cross module * optimisation, the compiler deemed the code unnecessary will result in * complete and obvious failure of the scheduler. If this is ever experienced * then the volatile qualifier can be inserted in the relevant places within the * list structures by simply defining configLIST_VOLATILE to volatile in * FreeRTOSConfig.h (as per the example at the bottom of this comment block). * If configLIST_VOLATILE is not defined then the preprocessor directives below * will simply #define configLIST_VOLATILE away completely. * * To use volatile list structure members then add the following line to * FreeRTOSConfig.h (without the quotes): * "#define configLIST_VOLATILE volatile" */ #ifndef configLIST_VOLATILE #define configLIST_VOLATILE #endif /* configSUPPORT_CROSS_MODULE_OPTIMISATION */ #ifdef __cplusplus extern "C" { #endif /* * Definition of the only type of object that a list can contain. */ struct xLIST_ITEM { configLIST_VOLATILE TickType_t xItemValue; /*< The value being listed. In most cases this is used to sort the list in descending order. */ struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*< Pointer to the next ListItem_t in the list. */ struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*< Pointer to the previous ListItem_t in the list. */ 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. */ void * configLIST_VOLATILE pvContainer; /*< Pointer to the list in which this list item is placed (if any). */ }; typedef struct xLIST_ITEM ListItem_t; /* For some reason lint wants this as two separate definitions. */ struct xMINI_LIST_ITEM { configLIST_VOLATILE TickType_t xItemValue; struct xLIST_ITEM * configLIST_VOLATILE pxNext; struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; }; typedef struct xMINI_LIST_ITEM MiniListItem_t; /* * Definition of the type of queue used by the scheduler. */ typedef struct xLIST { configLIST_VOLATILE UBaseType_t uxNumberOfItems; 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 (). */ 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. */ } List_t; /* * Access macro to set the owner of a list item. The owner of a list item * is the object (usually a TCB) that contains the list item. * * \page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER * \ingroup LinkedList */ #define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner ) ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) ) /* * Access macro to get the owner of a list item. The owner of a list item * is the object (usually a TCB) that contains the list item. * * \page listSET_LIST_ITEM_OWNER listSET_LIST_ITEM_OWNER * \ingroup LinkedList */ #define listGET_LIST_ITEM_OWNER( pxListItem ) ( ( pxListItem )->pvOwner ) /* * Access macro to set the value of the list item. In most cases the value is * used to sort the list in descending order. * * \page listSET_LIST_ITEM_VALUE listSET_LIST_ITEM_VALUE * \ingroup LinkedList */ #define listSET_LIST_ITEM_VALUE( pxListItem, xValue ) ( ( pxListItem )->xItemValue = ( xValue ) ) /* * Access macro to retrieve the value of the list item. The value can * represent anything - for example the priority of a task, or the time at * which a task should be unblocked. * * \page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE * \ingroup LinkedList */ #define listGET_LIST_ITEM_VALUE( pxListItem ) ( ( pxListItem )->xItemValue ) /* * Access macro to retrieve the value of the list item at the head of a given * list. * * \page listGET_LIST_ITEM_VALUE listGET_LIST_ITEM_VALUE * \ingroup LinkedList */ #define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList ) ( ( ( pxList )->xListEnd ).pxNext->xItemValue ) /* * Return the list item at the head of the list. * * \page listGET_HEAD_ENTRY listGET_HEAD_ENTRY * \ingroup LinkedList */ #define listGET_HEAD_ENTRY( pxList ) ( ( ( pxList )->xListEnd ).pxNext ) /* * Return the list item at the head of the list. * * \page listGET_NEXT listGET_NEXT * \ingroup LinkedList */ #define listGET_NEXT( pxListItem ) ( ( pxListItem )->pxNext ) /* * Return the list item that marks the end of the list * * \page listGET_END_MARKER listGET_END_MARKER * \ingroup LinkedList */ #define listGET_END_MARKER( pxList ) ( ( ListItem_t const * ) ( &( ( pxList )->xListEnd ) ) ) /* * Access macro to determine if a list contains any items. The macro will * only have the value true if the list is empty. * * \page listLIST_IS_EMPTY listLIST_IS_EMPTY * \ingroup LinkedList */ #define listLIST_IS_EMPTY( pxList ) ( ( BaseType_t ) ( ( pxList )->uxNumberOfItems == ( UBaseType_t ) 0 ) ) /* * Access macro to return the number of items in the list. */ #define listCURRENT_LIST_LENGTH( pxList ) ( ( pxList )->uxNumberOfItems ) /* * Access function to obtain the owner of the next entry in a list. * * The list member pxIndex is used to walk through a list. Calling * listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list * and returns that entry's pxOwner parameter. Using multiple calls to this * function it is therefore possible to move through every item contained in * a list. * * The pxOwner parameter of a list item is a pointer to the object that owns * the list item. In the scheduler this is normally a task control block. * The pxOwner parameter effectively creates a two way link between the list * item and its owner. * * @param pxTCB pxTCB is set to the address of the owner of the next list item. * @param pxList The list from which the next item owner is to be returned. * * \page listGET_OWNER_OF_NEXT_ENTRY listGET_OWNER_OF_NEXT_ENTRY * \ingroup LinkedList */ #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \ { \ List_t * const pxConstList = ( pxList ); \ /* Increment the index to the next item and return the item, ensuring */ \ /* we don't return the marker used at the end of the list. */ \ ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \ if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) \ { \ ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \ } \ ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; \ } /* * Access function to obtain the owner of the first entry in a list. Lists * are normally sorted in ascending item value order. * * This function returns the pxOwner member of the first item in the list. * The pxOwner parameter of a list item is a pointer to the object that owns * the list item. In the scheduler this is normally a task control block. * The pxOwner parameter effectively creates a two way link between the list * item and its owner. * * @param pxList The list from which the owner of the head item is to be * returned. * * \page listGET_OWNER_OF_HEAD_ENTRY listGET_OWNER_OF_HEAD_ENTRY * \ingroup LinkedList */ #define listGET_OWNER_OF_HEAD_ENTRY( pxList ) ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner ) /* * Check to see if a list item is within a list. The list item maintains a * "container" pointer that points to the list it is in. All this macro does * is check to see if the container and the list match. * * @param pxList The list we want to know if the list item is within. * @param pxListItem The list item we want to know if is in the list. * @return pdTRUE if the list item is in the list, otherwise pdFALSE. */ #define listIS_CONTAINED_WITHIN( pxList, pxListItem ) ( ( BaseType_t ) ( ( pxListItem )->pvContainer == ( void * ) ( pxList ) ) ) /* * Return the list a list item is contained within (referenced from). * * @param pxListItem The list item being queried. * @return A pointer to the List_t object that references the pxListItem */ #define listLIST_ITEM_CONTAINER( pxListItem ) ( ( pxListItem )->pvContainer ) /* * This provides a crude means of knowing if a list has been initialised, as * pxList->xListEnd.xItemValue is set to portMAX_DELAY by the vListInitialise() * function. */ #define listLIST_IS_INITIALISED( pxList ) ( ( pxList )->xListEnd.xItemValue == portMAX_DELAY ) /* * Must be called before a list is used! This initialises all the members * of the list structure and inserts the xListEnd item into the list as a * marker to the back of the list. * * @param pxList Pointer to the list being initialised. * * \page vListInitialise vListInitialise * \ingroup LinkedList */ void vListInitialise( List_t * const pxList ); /* * Must be called before a list item is used. This sets the list container to * null so the item does not think that it is already contained in a list. * * @param pxItem Pointer to the list item being initialised. * * \page vListInitialiseItem vListInitialiseItem * \ingroup LinkedList */ void vListInitialiseItem( ListItem_t * const pxItem ); /* * Insert a list item into a list. The item will be inserted into the list in * a position determined by its item value (descending item value order). * * @param pxList The list into which the item is to be inserted. * * @param pxNewListItem The item that is to be placed in the list. * * \page vListInsert vListInsert * \ingroup LinkedList */ void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem ); /* * Insert a list item into a list. The item will be inserted in a position * such that it will be the last item within the list returned by multiple * calls to listGET_OWNER_OF_NEXT_ENTRY. * * The list member pvIndex is used to walk through a list. Calling * listGET_OWNER_OF_NEXT_ENTRY increments pvIndex to the next item in the list. * Placing an item in a list using vListInsertEnd effectively places the item * in the list position pointed to by pvIndex. This means that every other * item within the list will be returned by listGET_OWNER_OF_NEXT_ENTRY before * the pvIndex parameter again points to the item being inserted. * * @param pxList The list into which the item is to be inserted. * * @param pxNewListItem The list item to be inserted into the list. * * \page vListInsertEnd vListInsertEnd * \ingroup LinkedList */ void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem ); /* * Remove an item from a list. The list item has a pointer to the list that * it is in, so only the list item need be passed into the function. * * @param uxListRemove The item to be removed. The item will remove itself from * the list pointed to by it's pxContainer parameter. * * @return The number of items that remain in the list after the list item has * been removed. * * \page uxListRemove uxListRemove * \ingroup LinkedList */ UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove ); #ifdef __cplusplus } #endif #endif