list.c

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 #include <stdlib.h>
00068 #include "FreeRTOS.h"
00069 #include "list.h"
00070 
00071 /*-----------------------------------------------------------
00072  * PUBLIC LIST API documented in list.h
00073  *----------------------------------------------------------*/
00074 
00075 void vListInitialise( xList * const pxList )
00076 {
00077     /* The list structure contains a list item which is used to mark the
00078     end of the list.  To initialise the list the list end is inserted
00079     as the only list entry. */
00080     pxList->pxIndex = ( xListItem * ) &( pxList->xListEnd );            /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
00081 
00082     /* The list end value is the highest possible value in the list to
00083     ensure it remains at the end of the list. */
00084     pxList->xListEnd.xItemValue = portMAX_DELAY;
00085 
00086     /* The list end next and previous pointers point to itself so we know
00087     when the list is empty. */
00088     pxList->xListEnd.pxNext = ( xListItem * ) &( pxList->xListEnd );    /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
00089     pxList->xListEnd.pxPrevious = ( xListItem * ) &( pxList->xListEnd );/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
00090 
00091     pxList->uxNumberOfItems = ( unsigned portBASE_TYPE ) 0U;
00092 }
00093 /*-----------------------------------------------------------*/
00094 
00095 void vListInitialiseItem( xListItem * const pxItem )
00096 {
00097     /* Make sure the list item is not recorded as being on a list. */
00098     pxItem->pvContainer = NULL;
00099 }
00100 /*-----------------------------------------------------------*/
00101 
00102 void vListInsertEnd( xList * const pxList, xListItem * const pxNewListItem )
00103 {
00104 xListItem * pxIndex;
00105 
00106     /* Insert a new list item into pxList, but rather than sort the list,
00107     makes the new list item the last item to be removed by a call to
00108     pvListGetOwnerOfNextEntry. */
00109     pxIndex = pxList->pxIndex;
00110 
00111     pxNewListItem->pxNext = pxIndex;
00112     pxNewListItem->pxPrevious = pxIndex->pxPrevious;
00113     pxIndex->pxPrevious->pxNext = pxNewListItem;
00114     pxIndex->pxPrevious = pxNewListItem;
00115 
00116     /* Remember which list the item is in. */
00117     pxNewListItem->pvContainer = ( void * ) pxList;
00118 
00119     ( pxList->uxNumberOfItems )++;
00120 }
00121 /*-----------------------------------------------------------*/
00122 
00123 void vListInsert( xList * const pxList, xListItem * const pxNewListItem )
00124 {
00125 xListItem *pxIterator;
00126 portTickType xValueOfInsertion;
00127 
00128     /* Insert the new list item into the list, sorted in ulListItem order. */
00129     xValueOfInsertion = pxNewListItem->xItemValue;
00130 
00131     /* If the list already contains a list item with the same item value then
00132     the new list item should be placed after it.  This ensures that TCB's which
00133     are stored in ready lists (all of which have the same ulListItem value)
00134     get an equal share of the CPU.  However, if the xItemValue is the same as
00135     the back marker the iteration loop below will not end.  This means we need
00136     to guard against this by checking the value first and modifying the
00137     algorithm slightly if necessary. */
00138     if( xValueOfInsertion == portMAX_DELAY )
00139     {
00140         pxIterator = pxList->xListEnd.pxPrevious;
00141     }
00142     else
00143     {
00144         /* *** NOTE ***********************************************************
00145         If you find your application is crashing here then likely causes are:
00146             1) Stack overflow -
00147                see http://www.freertos.org/Stacks-and-stack-overflow-checking.html
00148             2) Incorrect interrupt priority assignment, especially on Cortex-M3
00149                parts where numerically high priority values denote low actual
00150                interrupt priories, which can seem counter intuitive.  See
00151                configMAX_SYSCALL_INTERRUPT_PRIORITY on http://www.freertos.org/a00110.html
00152             3) Calling an API function from within a critical section or when
00153                the scheduler is suspended, or calling an API function that does
00154                not end in "FromISR" from an interrupt.
00155             4) Using a queue or semaphore before it has been initialised or
00156                before the scheduler has been started (are interrupts firing
00157                before vTaskStartScheduler() has been called?).
00158         See http://www.freertos.org/FAQHelp.html for more tips.
00159         **********************************************************************/
00160 
00161         for( pxIterator = ( xListItem * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
00162         {
00163             /* There is nothing to do here, we are just iterating to the
00164             wanted insertion position. */
00165         }
00166     }
00167 
00168     pxNewListItem->pxNext = pxIterator->pxNext;
00169     pxNewListItem->pxNext->pxPrevious = pxNewListItem;
00170     pxNewListItem->pxPrevious = pxIterator;
00171     pxIterator->pxNext = pxNewListItem;
00172 
00173     /* Remember which list the item is in.  This allows fast removal of the
00174     item later. */
00175     pxNewListItem->pvContainer = ( void * ) pxList;
00176 
00177     ( pxList->uxNumberOfItems )++;
00178 }
00179 /*-----------------------------------------------------------*/
00180 
00181 unsigned portBASE_TYPE uxListRemove( xListItem * const pxItemToRemove )
00182 {
00183 xList * pxList;
00184 
00185     pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
00186     pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
00187 
00188     /* The list item knows which list it is in.  Obtain the list from the list
00189     item. */
00190     pxList = ( xList * ) pxItemToRemove->pvContainer;
00191 
00192     /* Make sure the index is left pointing to a valid item. */
00193     if( pxList->pxIndex == pxItemToRemove )
00194     {
00195         pxList->pxIndex = pxItemToRemove->pxPrevious;
00196     }
00197 
00198     pxItemToRemove->pvContainer = NULL;
00199     ( pxList->uxNumberOfItems )--;
00200 
00201     return pxList->uxNumberOfItems;
00202 }
00203 /*-----------------------------------------------------------*/
00204