git.sur5r.net Git - freertos/blob - FreeRTOS/Source/list.c

   1 /*\r
   2     FreeRTOS V8.2.0rc1 - Copyright (C) 2014 Real Time Engineers Ltd.\r
   3     All rights reserved\r
   4 \r
   5     VISIT http://www.FreeRTOS.org TO ENSURE YOU ARE USING THE LATEST VERSION.\r
   6 \r
   7     This file is part of the FreeRTOS distribution.\r
   8 \r
   9     FreeRTOS is free software; you can redistribute it and/or modify it under\r
  10     the terms of the GNU General Public License (version 2) as published by the\r
  11     Free Software Foundation >>!AND MODIFIED BY!<< the FreeRTOS exception.\r
  12 \r
  13     >>!   NOTE: The modification to the GPL is included to allow you to     !<<\r
  14     >>!   distribute a combined work that includes FreeRTOS without being   !<<\r
  15     >>!   obliged to provide the source code for proprietary components     !<<\r
  16     >>!   outside of the FreeRTOS kernel.                                   !<<\r
  17 \r
  18     FreeRTOS is distributed in the hope that it will be useful, but WITHOUT ANY\r
  19     WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS\r
  20     FOR A PARTICULAR PURPOSE.  Full license text is available on the following\r
  21     link: http://www.freertos.org/a00114.html\r
  22 \r
  23     1 tab == 4 spaces!\r
  24 \r
  25     ***************************************************************************\r
  26      *                                                                       *\r
  27      *    Having a problem?  Start by reading the FAQ "My application does   *\r
  28      *    not run, what could be wrong?".  Have you defined configASSERT()?  *\r
  29      *                                                                       *\r
  30      *    http://www.FreeRTOS.org/FAQHelp.html                               *\r
  31      *                                                                       *\r
  32     ***************************************************************************\r
  33 \r
  34     ***************************************************************************\r
  35      *                                                                       *\r
  36      *    FreeRTOS provides completely free yet professionally developed,    *\r
  37      *    robust, strictly quality controlled, supported, and cross          *\r
  38      *    platform software that is more than just the market leader, it     *\r
  39      *    is the industry's de facto standard.                               *\r
  40      *                                                                       *\r
  41      *    Help yourself get started quickly while simultaneously helping     *\r
  42      *    to support the FreeRTOS project by purchasing a FreeRTOS           *\r
  43      *    tutorial book, reference manual, or both:                          *\r
  44      *    http://www.FreeRTOS.org/Documentation                              *\r
  45      *                                                                       *\r
  46     ***************************************************************************\r
  47 \r
  48     ***************************************************************************\r
  49      *                                                                       *\r
  50      *   Investing in training allows your team to be as productive as       *\r
  51      *   possible as early as possible, lowering your overall development    *\r
  52      *   cost, and enabling you to bring a more robust product to market     *\r
  53      *   earlier than would otherwise be possible.  Richard Barry is both    *\r
  54      *   the architect and key author of FreeRTOS, and so also the world's   *\r
  55      *   leading authority on what is the world's most popular real time     *\r
  56      *   kernel for deeply embedded MCU designs.  Obtaining your training    *\r
  57      *   from Richard ensures your team will gain directly from his in-depth *\r
  58      *   product knowledge and years of usage experience.  Contact Real Time *\r
  59      *   Engineers Ltd to enquire about the FreeRTOS Masterclass, presented  *\r
  60      *   by Richard Barry:  http://www.FreeRTOS.org/contact\r
  61      *                                                                       *\r
  62     ***************************************************************************\r
  63 \r
  64     ***************************************************************************\r
  65      *                                                                       *\r
  66      *    You are receiving this top quality software for free.  Please play *\r
  67      *    fair and reciprocate by reporting any suspected issues and         *\r
  68      *    participating in the community forum:                              *\r
  69      *    http://www.FreeRTOS.org/support                                    *\r
  70      *                                                                       *\r
  71      *    Thank you!                                                         *\r
  72      *                                                                       *\r
  73     ***************************************************************************\r
  74 \r
  75     http://www.FreeRTOS.org - Documentation, books, training, latest versions,\r
  76     license and Real Time Engineers Ltd. contact details.\r
  77 \r
  78     http://www.FreeRTOS.org/plus - A selection of FreeRTOS ecosystem products,\r
  79     including FreeRTOS+Trace - an indispensable productivity tool, a DOS\r
  80     compatible FAT file system, and our tiny thread aware UDP/IP stack.\r
  81 \r
  82     http://www.FreeRTOS.org/labs - Where new FreeRTOS products go to incubate.\r
  83     Come and try FreeRTOS+TCP, our new open source TCP/IP stack for FreeRTOS.\r
  84 \r
  85     http://www.OpenRTOS.com - Real Time Engineers ltd license FreeRTOS to High\r
  86     Integrity Systems ltd. to sell under the OpenRTOS brand.  Low cost OpenRTOS\r
  87     licenses offer ticketed support, indemnification and commercial middleware.\r
  88 \r
  89     http://www.SafeRTOS.com - High Integrity Systems also provide a safety\r
  90     engineered and independently SIL3 certified version for use in safety and\r
  91     mission critical applications that require provable dependability.\r
  92 \r
  93     1 tab == 4 spaces!\r
  94 */\r
  95 \r
  96 \r
  97 #include <stdlib.h>\r
  98 #include "FreeRTOS.h"\r
  99 #include "list.h"\r
 100 \r
 101 /*-----------------------------------------------------------\r
 102  * PUBLIC LIST API documented in list.h\r
 103  *----------------------------------------------------------*/\r
 104 \r
 105 void vListInitialise( List_t * const pxList )\r
 106 {\r
 107         /* The list structure contains a list item which is used to mark the\r
 108         end of the list.  To initialise the list the list end is inserted\r
 109         as the only list entry. */\r
 110         pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );                       /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */\r
 111 \r
 112         /* The list end value is the highest possible value in the list to\r
 113         ensure it remains at the end of the list. */\r
 114         pxList->xListEnd.xItemValue = portMAX_DELAY;\r
 115 \r
 116         /* The list end next and previous pointers point to itself so we know\r
 117         when the list is empty. */\r
 118         pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );       /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */\r
 119         pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */\r
 120 \r
 121         pxList->uxNumberOfItems = ( UBaseType_t ) 0U;\r
 122 \r
 123         /* Write known values into the list if\r
 124         configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */\r
 125         listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );\r
 126         listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );\r
 127 }\r
 128 /*-----------------------------------------------------------*/\r
 129 \r
 130 void vListInitialiseItem( ListItem_t * const pxItem )\r
 131 {\r
 132         /* Make sure the list item is not recorded as being on a list. */\r
 133         pxItem->pvContainer = NULL;\r
 134 \r
 135         /* Write known values into the list item if\r
 136         configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */\r
 137         listSET_LIST_ITEM_INTEGRITY_CHECK_1_VALUE( pxItem );\r
 138         listSET_LIST_ITEM_INTEGRITY_CHECK_2_VALUE( pxItem );\r
 139 }\r
 140 /*-----------------------------------------------------------*/\r
 141 \r
 142 void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )\r
 143 {\r
 144 ListItem_t * const pxIndex = pxList->pxIndex;\r
 145 \r
 146         /* Only effective when configASSERT() is also defined, these tests may catch\r
 147         the list data structures being overwritten in memory.  They will not catch\r
 148         data errors caused by incorrect configuration or use of FreeRTOS. */\r
 149         listTEST_LIST_INTEGRITY( pxList );\r
 150         listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );\r
 151 \r
 152         /* Insert a new list item into pxList, but rather than sort the list,\r
 153         makes the new list item the last item to be removed by a call to\r
 154         listGET_OWNER_OF_NEXT_ENTRY(). */\r
 155         pxNewListItem->pxNext = pxIndex;\r
 156         pxNewListItem->pxPrevious = pxIndex->pxPrevious;\r
 157         pxIndex->pxPrevious->pxNext = pxNewListItem;\r
 158         pxIndex->pxPrevious = pxNewListItem;\r
 159 \r
 160         /* Remember which list the item is in. */\r
 161         pxNewListItem->pvContainer = ( void * ) pxList;\r
 162 \r
 163         ( pxList->uxNumberOfItems )++;\r
 164 }\r
 165 /*-----------------------------------------------------------*/\r
 166 \r
 167 void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )\r
 168 {\r
 169 ListItem_t *pxIterator;\r
 170 const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;\r
 171 \r
 172         /* Only effective when configASSERT() is also defined, these tests may catch\r
 173         the list data structures being overwritten in memory.  They will not catch\r
 174         data errors caused by incorrect configuration or use of FreeRTOS. */\r
 175         listTEST_LIST_INTEGRITY( pxList );\r
 176         listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );\r
 177 \r
 178         /* Insert the new list item into the list, sorted in xItemValue order.\r
 179 \r
 180         If the list already contains a list item with the same item value then the\r
 181         new list item should be placed after it.  This ensures that TCB's which are\r
 182         stored in ready lists (all of which have the same xItemValue value) get a\r
 183         share of the CPU.  However, if the xItemValue is the same as the back marker\r
 184         the iteration loop below will not end.  Therefore the value is checked\r
 185         first, and the algorithm slightly modified if necessary. */\r
 186         if( xValueOfInsertion == portMAX_DELAY )\r
 187         {\r
 188                 pxIterator = pxList->xListEnd.pxPrevious;\r
 189         }\r
 190         else\r
 191         {\r
 192                 /* *** NOTE ***********************************************************\r
 193                 If you find your application is crashing here then likely causes are\r
 194                 listed below.  In addition see http://www.freertos.org/FAQHelp.html for\r
 195                 more tips, and ensure configASSERT() is defined!\r
 196                 http://www.freertos.org/a00110.html#configASSERT\r
 197 \r
 198                         1) Stack overflow -\r
 199                            see http://www.freertos.org/Stacks-and-stack-overflow-checking.html\r
 200                         2) Incorrect interrupt priority assignment, especially on Cortex-M\r
 201                            parts where numerically high priority values denote low actual\r
 202                            interrupt priorities, which can seem counter intuitive.  See\r
 203                            http://www.freertos.org/RTOS-Cortex-M3-M4.html and the definition\r
 204                            of configMAX_SYSCALL_INTERRUPT_PRIORITY on\r
 205                            http://www.freertos.org/a00110.html\r
 206                         3) Calling an API function from within a critical section or when\r
 207                            the scheduler is suspended, or calling an API function that does\r
 208                            not end in "FromISR" from an interrupt.\r
 209                         4) Using a queue or semaphore before it has been initialised or\r
 210                            before the scheduler has been started (are interrupts firing\r
 211                            before vTaskStartScheduler() has been called?).\r
 212                 **********************************************************************/\r
 213 \r
 214                 for( pxIterator = ( ListItem_t * ) &( 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. */\r
 215                 {\r
 216                         /* There is nothing to do here, just iterating to the wanted\r
 217                         insertion position. */\r
 218                 }\r
 219         }\r
 220 \r
 221         pxNewListItem->pxNext = pxIterator->pxNext;\r
 222         pxNewListItem->pxNext->pxPrevious = pxNewListItem;\r
 223         pxNewListItem->pxPrevious = pxIterator;\r
 224         pxIterator->pxNext = pxNewListItem;\r
 225 \r
 226         /* Remember which list the item is in.  This allows fast removal of the\r
 227         item later. */\r
 228         pxNewListItem->pvContainer = ( void * ) pxList;\r
 229 \r
 230         ( pxList->uxNumberOfItems )++;\r
 231 }\r
 232 /*-----------------------------------------------------------*/\r
 233 \r
 234 UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )\r
 235 {\r
 236 /* The list item knows which list it is in.  Obtain the list from the list\r
 237 item. */\r
 238 List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;\r
 239 \r
 240         pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;\r
 241         pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;\r
 242 \r
 243         /* Make sure the index is left pointing to a valid item. */\r
 244         if( pxList->pxIndex == pxItemToRemove )\r
 245         {\r
 246                 pxList->pxIndex = pxItemToRemove->pxPrevious;\r
 247         }\r
 248         else\r
 249         {\r
 250                 mtCOVERAGE_TEST_MARKER();\r
 251         }\r
 252 \r
 253         pxItemToRemove->pvContainer = NULL;\r
 254         ( pxList->uxNumberOfItems )--;\r
 255 \r
 256         return pxList->uxNumberOfItems;\r
 257 }\r
 258 /*-----------------------------------------------------------*/\r
 259 \r