FreeRTOS中列表和列表项插入函数分析

在学习FreeRTOS的过程中，看到列表和列表项插入的时候，对于列表插入函数vListInsert()，理解起来感觉比较费劲。于是对照函数画个示意图，帮助理解。

先看看列表插入函数代码。

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )

{

    ListItem_t *pxIterator;

    const TickType_t xValueOfInsertion=pxNewListItem->xItemValue;

    listTEST_LIST_INTEGRITY( pxList );

    listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

    if( xValueOfInsertion == portMAX_DELAY )

    {

    pxIterator = pxList->xListEnd.pxPrevious;

    }

    else

    {

        for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) 

        {

        }

    }

    pxNewListItem->pxNext = pxIterator->pxNext;

    pxNewListItem->pxNext->pxPrevious = pxNewListItem;

    pxNewListItem->pxPrevious = pxIterator;

    pxIterator->pxNext = pxNewListItem;

    pxNewListItem->pvContainer = ( void * ) pxList;

    ( pxList->uxNumberOfItems )++;

}

参数: pxList:列表项要插入的列表；

pxNewListItem:要插入的列表项

const TickType_t xValueOfInsertion=

pxNewListItem->xItemValue：

获取要插入列表项值(列表项成员变量xItemValue的值)，根据这个值来确定列表项要插入的位置。

listTEST_LIST_INTEGRITY( pxList )和listTEST_LIST_ITEM_INTEGRITY( pxNewListItem )：检查列表和列表项完整性。

if( xValueOfInsertion == portMAX_DELAY )：

获取列表项插入到什么位置，如果插入列表项的值等于portMAX_DELAY，即列表项值为最大值，此时插入的位置为列表最末尾

pxIterator = pxList->xListEnd.pxPrevious：

获取要插入点，列表中xListEnd表示列表末尾，初始化列表时xListEnd的列表值也是portMAX_DELAY，尽管两个值一样，但是要把插入的列表项放在xListEnd前面。

for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion;

pxIterator = pxIterator->pxNext ) ：

如果列表项的值不等于portMAX_DELAY那么就需要在列表中遍历，寻找插入位置，用for循环遍历列表寻找插入点。

通过上面可以知道， pxNewListItem为要插入的列表项，pxIterator为要插入的插入点位置。

假如现在的列表项如下：

此时我们要将 50 插入到列表中去

那么此时pxNewListItem指向的就是50这一项，pxIterator指向的就是40这一项。由上面的for循环也可以看出

pxIterator->pxNext->xItemValue <= xValueOfInsertion;

列表中的值小于等于当要插入的值，插入点就继续指向下一个，此时要插入的值是50，它会依次和列表中的值20、30、40、60比较，当比较到60时，插入点的值是60，大于要插入的值50，此时for循环退出，插入点指向40这一项。

此时列表的状态入下图所示。

下来开始执行列表插入操作。

pxNewListItem->pxNext = pxIterator->pxNext;

将插入点指向的下一个列表项赋值给新插入列表项的下一项。

此时列表项50的下一项指向了列表项60.

pxNewListItem->pxNext->pxPrevious = pxNewListItem;

将新插入列表项的下一项的前一项设置为新插入列表项。

也就是说此时列表项60的上一个列表项指向了50。

pxNewListItem->pxPrevious = pxIterator;

下来将新插入列表项的前一个列表项设置为插入点。

此时列表项50的前一项指向了40。

pxIterator->pxNext = pxNewListItem;

将新插入列表项指向插入点的下一项

此时列表项40的下一项是列表项50,列表项50的下一项是60。列表项60的前一项是列表项50，列表项50的前一项是列表项40。

pxNewListItem->pvContainer = ( void * ) pxList：

插入后，列表项成员变量pvContainer记录此列表项属于哪个列表。

pxList->uxNumberOfItems：列表成员数量加1。

这样列表项50就成功的插入到列表中去了，插入的过程就是将插入点与后面的连接项断开，然后重新连接到新插入项上。在把新插入项和断开的连接项连接起来。这样通过图示就可以很清晰的看到列表插入的过程，下来再去看代码的时候，理解起来就更容易了。