寫在開始
freertos中的任務涉及到3個很重要的結構體，也就是struct xLIST，struct xMINI_LIST_ITEM與struct xLIST_ITEM。
為什麼會形成類似struct xLIST這種結構呢？
由於它需要計算item的個數，所以它首先要包含uxNumberOfItems，另外它需要指向item的位置，所以有一個ListItem_t * pxIndex。這樣就形成了struct xLIST。這是第一步，稱為結構體A。
而需要定義一個全局變量，struct xMINI_LIST_ITEM，這個節點用來表示整個item的結束(作為全局變量的時候完全可以改寫為struct xLIST_ITEM)。這樣就相當於定義了一個所有內容都是struct xLIST_ITEM的雙鏈表結構，其中只不過多了一個標誌位結束的鏈表。這個鏈表由於與上面的A都是獨立一份的，所以將這個struct xLIST_ITEM集成到A裡面，而pvOwner和pxContainer是多餘的，可以略去，所以就做了一個struct xMINI_LIST_ITEM結構體。
在freertos中，可以看到信號量，互斥量，郵箱也都是集中在一個結構體中，這都是freertos的內存節省的操作。
確定了這些，那麼初始化struct xLIST就好理解了(將struct xMINI_LIST_ITEM拆開)。
代碼分析
初始化代碼如下：
<code>void vListInitialise( List_t * const pxList )
{
\t/* The list structure contains a list item which is used to mark the
\tend of the list. To initialise the list the list end is inserted
\tas the only list entry. */
\tpxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );\t\t\t/*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
\t/* The list end value is the highest possible value in the list to
\tensure it remains at the end of the list. */
\tpxList->xListEnd.xItemValue = portMAX_DELAY;
\t/* The list end next and previous pointers point to itself so we know
\twhen the list is empty. */
\tpxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );\t/*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
\tpxList->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. */
\tpxList->uxNumberOfItems = ( UBaseType_t ) 0U;
\t/* Write known values into the list if
\tconfigUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
\tlistSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
\tlistSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}/<code>
對於單個的item，在程序需要將它插入list之前會重新做初始化，所以在程序運行後，執行的初始化很簡單：
<code>void vListInitialiseItem( ListItem_t * const pxItem )
{
\t/* Make sure the list item is not recorded as being on a list. */
\tpxItem->pxContainer = NULL;
\t/* Write known values into the list item if
\tconfigUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
\tlistSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
\tlistSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}/<code>
建立了鏈表結構，就是為了增刪改查的。那麼插入鏈表分為從尾部插入與從中間插入。現在定義的結構由於相當於定義了頭(list)，所以分為從頭之後插入與在頭的最後一個位置插入兩種情況。
先說從尾部插入。
exist是假想的一個鏈表，這樣理解尾部插入的代碼就會很容易。
<code>void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t * const pxIndex = pxList->pxIndex;
\t/* Only effective when configASSERT() is also defined, these tests may catch
\tthe list data structures being overwritten in memory. They will not catch
\tdata errors caused by incorrect configuration or use of FreeRTOS. */
\tlistTEST_LIST_INTEGRITY( pxList );
\tlistTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
\t/* Insert a new list item into pxList, but rather than sort the list,
\tmakes the new list item the last item to be removed by a call to
\tlistGET_OWNER_OF_NEXT_ENTRY(). */
\tpxNewListItem->pxNext = pxIndex;
\tpxNewListItem->pxPrevious = pxIndex->pxPrevious;
\t/* Only used during decision coverage testing. */
\tmtCOVERAGE_TEST_DELAY();
\tpxIndex->pxPrevious->pxNext = pxNewListItem;
\tpxIndex->pxPrevious = pxNewListItem;
\t/* Remember which list the item is in. */
\tpxNewListItem->pxContainer = pxList;
\t( pxList->uxNumberOfItems )++;
}/<code>
可以看到，在鏈表最後插入的代碼裡，會將pxContainer值賦為這個指定的pxList。最後會將item的個數增加。
再說一下從pxList後插入。
其代碼為：
<code>void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t *pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
\t/* Only effective when configASSERT() is also defined, these tests may catch
\tthe list data structures being overwritten in memory. They will not catch
\tdata errors caused by incorrect configuration or use of FreeRTOS. */
\tlistTEST_LIST_INTEGRITY( pxList );
\tlistTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
\t/* Insert the new list item into the list, sorted in xItemValue order.
\tIf the list already contains a list item with the same item value then the
\tnew list item should be placed after it. This ensures that TCBs which are
\tstored in ready lists (all of which have the same xItemValue value) get a
\tshare of the CPU. However, if the xItemValue is the same as the back marker
\tthe iteration loop below will not end. Therefore the value is checked
\tfirst, and the algorithm slightly modified if necessary. */
\tif( xValueOfInsertion == portMAX_DELAY )
\t{
\t\tpxIterator = pxList->xListEnd.pxPrevious;
\t}
\telse
\t{
\t\t/* *** NOTE ***********************************************************
\t\tIf you find your application is crashing here then likely causes are
\t\tlisted below. In addition see https://www.freertos.org/FAQHelp.html for
\t\tmore tips, and ensure configASSERT() is defined!
\t\thttps://www.freertos.org/a00110.html#configASSERT
\t\t\t1) Stack overflow -
\t\t\t see https://www.freertos.org/Stacks-and-stack-overflow-checking.html
\t\t\t2) Incorrect interrupt priority assignment, especially on Cortex-M
\t\t\t parts where numerically high priority values denote low actual
\t\t\t interrupt priorities, which can seem counter intuitive. See
\t\t\t https://www.freertos.org/RTOS-Cortex-M3-M4.html and the definition
\t\t\t of configMAX_SYSCALL_INTERRUPT_PRIORITY on
\t\t\t https://www.freertos.org/a00110.html
\t\t\t3) Calling an API function from within a critical section or when
\t\t\t the scheduler is suspended, or calling an API function that does
\t\t\t not end in "FromISR" from an interrupt.
\t\t\t4) Using a queue or semaphore before it has been initialised or
\t\t\t before the scheduler has been started (are interrupts firing
\t\t\t before vTaskStartScheduler() has been called?).
\t\t**********************************************************************/
\t\tfor( 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. */
\t\t{
\t\t\t/* There is nothing to do here, just iterating to the wanted
\t\t\tinsertion position. */
\t\t}
\t}
\tpxNewListItem->pxNext = pxIterator->pxNext;
\tpxNewListItem->pxNext->pxPrevious = pxNewListItem;
\tpxNewListItem->pxPrevious = pxIterator;
\tpxIterator->pxNext = pxNewListItem;
\t/* Remember which list the item is in. This allows fast removal of the
\titem later. */
\tpxNewListItem->pxContainer = pxList;
\t( pxList->uxNumberOfItems )++;
}/<code>
從pxList插入涉及到在哪個鏈表位置插入，哪個位置則可以引用結構體中的xItemValue，利用這個值來進行排序插入。
在值為portMAX_DELAY的時候，那就在鏈表的末尾插入，這個前面說過。而從中間插入跟最後插入其實代碼的區別不大。
再說一下鏈表的刪除。
刪除主要就是將鏈表中某一項去掉的過程。需要注意的是如果刪除的是 pxList->pxIndex，那則需要將指針移動到前一個鏈表。代碼如下：
<code>UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
/* The list item knows which list it is in. Obtain the list from the list
item. */
List_t * const pxList = pxItemToRemove->pxContainer;
\tpxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
\tpxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
\t/* Only used during decision coverage testing. */
\tmtCOVERAGE_TEST_DELAY();
\t/* Make sure the index is left pointing to a valid item. */
\tif( pxList->pxIndex == pxItemToRemove )
\t{
\t\tpxList->pxIndex = pxItemToRemove->pxPrevious;
\t}
\telse
\t{
\t\tmtCOVERAGE_TEST_MARKER();
\t}
\tpxItemToRemove->pxContainer = NULL;
\t( pxList->uxNumberOfItems )--;
\treturn pxList->uxNumberOfItems;
}/<code>
分享到:
閱讀更多 wityuan 的文章
