list.c 9.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215
  1. /*
  2. * FreeRTOS Kernel V10.4.4
  3. * Copyright (C) 2021 Amazon.com, Inc. or its affiliates. All Rights Reserved.
  4. *
  5. * SPDX-License-Identifier: MIT
  6. *
  7. * Permission is hereby granted, free of charge, to any person obtaining a copy of
  8. * this software and associated documentation files (the "Software"), to deal in
  9. * the Software without restriction, including without limitation the rights to
  10. * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
  11. * the Software, and to permit persons to whom the Software is furnished to do so,
  12. * subject to the following conditions:
  13. *
  14. * The above copyright notice and this permission notice shall be included in all
  15. * copies or substantial portions of the Software.
  16. *
  17. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18. * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
  19. * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
  20. * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  21. * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  22. * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  23. *
  24. * https://www.FreeRTOS.org
  25. * https://github.com/FreeRTOS
  26. *
  27. */
  28. #include <stdlib.h>
  29. /* Defining MPU_WRAPPERS_INCLUDED_FROM_API_FILE prevents task.h from redefining
  30. * all the API functions to use the MPU wrappers. That should only be done when
  31. * task.h is included from an application file. */
  32. #define MPU_WRAPPERS_INCLUDED_FROM_API_FILE
  33. #include "FreeRTOS.h"
  34. #include "list.h"
  35. /* Lint e9021, e961 and e750 are suppressed as a MISRA exception justified
  36. * because the MPU ports require MPU_WRAPPERS_INCLUDED_FROM_API_FILE to be
  37. * defined for the header files above, but not in this file, in order to
  38. * generate the correct privileged Vs unprivileged linkage and placement. */
  39. #undef MPU_WRAPPERS_INCLUDED_FROM_API_FILE /*lint !e961 !e750 !e9021. */
  40. /*-----------------------------------------------------------
  41. * PUBLIC LIST API documented in list.h
  42. *----------------------------------------------------------*/
  43. void vListInitialise( List_t * const pxList )
  44. {
  45. /* The list structure contains a list item which is used to mark the
  46. * end of the list. To initialise the list the list end is inserted
  47. * as the only list entry. */
  48. pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
  49. /* The list end value is the highest possible value in the list to
  50. * ensure it remains at the end of the list. */
  51. pxList->xListEnd.xItemValue = portMAX_DELAY;
  52. /* The list end next and previous pointers point to itself so we know
  53. * when the list is empty. */
  54. pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
  55. pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
  56. pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
  57. /* Write known values into the list if
  58. * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
  59. listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
  60. listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
  61. }
  62. /*-----------------------------------------------------------*/
  63. void vListInitialiseItem( ListItem_t * const pxItem )
  64. {
  65. /* Make sure the list item is not recorded as being on a list. */
  66. pxItem->pxContainer = NULL;
  67. /* Write known values into the list item if
  68. * configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
  69. listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
  70. listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
  71. }
  72. /*-----------------------------------------------------------*/
  73. void vListInsertEnd( List_t * const pxList,
  74. ListItem_t * const pxNewListItem )
  75. {
  76. ListItem_t * const pxIndex = pxList->pxIndex;
  77. /* Only effective when configASSERT() is also defined, these tests may catch
  78. * the list data structures being overwritten in memory. They will not catch
  79. * data errors caused by incorrect configuration or use of FreeRTOS. */
  80. listTEST_LIST_INTEGRITY( pxList );
  81. listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
  82. /* Insert a new list item into pxList, but rather than sort the list,
  83. * makes the new list item the last item to be removed by a call to
  84. * listGET_OWNER_OF_NEXT_ENTRY(). */
  85. pxNewListItem->pxNext = pxIndex;
  86. pxNewListItem->pxPrevious = pxIndex->pxPrevious;
  87. /* Only used during decision coverage testing. */
  88. mtCOVERAGE_TEST_DELAY();
  89. pxIndex->pxPrevious->pxNext = pxNewListItem;
  90. pxIndex->pxPrevious = pxNewListItem;
  91. /* Remember which list the item is in. */
  92. pxNewListItem->pxContainer = pxList;
  93. ( pxList->uxNumberOfItems )++;
  94. }
  95. /*-----------------------------------------------------------*/
  96. void vListInsert( List_t * const pxList,
  97. ListItem_t * const pxNewListItem )
  98. {
  99. ListItem_t * pxIterator;
  100. const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
  101. /* Only effective when configASSERT() is also defined, these tests may catch
  102. * the list data structures being overwritten in memory. They will not catch
  103. * data errors caused by incorrect configuration or use of FreeRTOS. */
  104. listTEST_LIST_INTEGRITY( pxList );
  105. listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
  106. /* Insert the new list item into the list, sorted in xItemValue order.
  107. *
  108. * If the list already contains a list item with the same item value then the
  109. * new list item should be placed after it. This ensures that TCBs which are
  110. * stored in ready lists (all of which have the same xItemValue value) get a
  111. * share of the CPU. However, if the xItemValue is the same as the back marker
  112. * the iteration loop below will not end. Therefore the value is checked
  113. * first, and the algorithm slightly modified if necessary. */
  114. if( xValueOfInsertion == portMAX_DELAY )
  115. {
  116. pxIterator = pxList->xListEnd.pxPrevious;
  117. }
  118. else
  119. {
  120. /* *** NOTE ***********************************************************
  121. * If you find your application is crashing here then likely causes are
  122. * listed below. In addition see https://www.FreeRTOS.org/FAQHelp.html for
  123. * more tips, and ensure configASSERT() is defined!
  124. * https://www.FreeRTOS.org/a00110.html#configASSERT
  125. *
  126. * 1) Stack overflow -
  127. * see https://www.FreeRTOS.org/Stacks-and-stack-overflow-checking.html
  128. * 2) Incorrect interrupt priority assignment, especially on Cortex-M
  129. * parts where numerically high priority values denote low actual
  130. * interrupt priorities, which can seem counter intuitive. See
  131. * https://www.FreeRTOS.org/RTOS-Cortex-M3-M4.html and the definition
  132. * of configMAX_SYSCALL_INTERRUPT_PRIORITY on
  133. * https://www.FreeRTOS.org/a00110.html
  134. * 3) Calling an API function from within a critical section or when
  135. * the scheduler is suspended, or calling an API function that does
  136. * not end in "FromISR" from an interrupt.
  137. * 4) Using a queue or semaphore before it has been initialised or
  138. * before the scheduler has been started (are interrupts firing
  139. * before vTaskStartScheduler() has been called?).
  140. * 5) If the FreeRTOS port supports interrupt nesting then ensure that
  141. * the priority of the tick interrupt is at or below
  142. * configMAX_SYSCALL_INTERRUPT_PRIORITY.
  143. **********************************************************************/
  144. for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. *//*lint !e440 The iterator moves to a different value, not xValueOfInsertion. */
  145. {
  146. /* There is nothing to do here, just iterating to the wanted
  147. * insertion position. */
  148. }
  149. }
  150. pxNewListItem->pxNext = pxIterator->pxNext;
  151. pxNewListItem->pxNext->pxPrevious = pxNewListItem;
  152. pxNewListItem->pxPrevious = pxIterator;
  153. pxIterator->pxNext = pxNewListItem;
  154. /* Remember which list the item is in. This allows fast removal of the
  155. * item later. */
  156. pxNewListItem->pxContainer = pxList;
  157. ( pxList->uxNumberOfItems )++;
  158. }
  159. /*-----------------------------------------------------------*/
  160. UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
  161. {
  162. /* The list item knows which list it is in. Obtain the list from the list
  163. * item. */
  164. List_t * const pxList = pxItemToRemove->pxContainer;
  165. pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
  166. pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
  167. /* Only used during decision coverage testing. */
  168. mtCOVERAGE_TEST_DELAY();
  169. /* Make sure the index is left pointing to a valid item. */
  170. if( pxList->pxIndex == pxItemToRemove )
  171. {
  172. pxList->pxIndex = pxItemToRemove->pxPrevious;
  173. }
  174. else
  175. {
  176. mtCOVERAGE_TEST_MARKER();
  177. }
  178. pxItemToRemove->pxContainer = NULL;
  179. ( pxList->uxNumberOfItems )--;
  180. return pxList->uxNumberOfItems;
  181. }
  182. /*-----------------------------------------------------------*/