FreeRTOS学习笔记-基于stm32（5）列表和列表项

一、列表与列表项简介

        列表是FreeRTOS中的一种数据结构，类似双向循环链表。用来跟踪FreeRTOS中的任务。列表项就是存放在列表中的项目。

二、列表

列表结构体：

typedef struct xLIST
{
	listFIRST_LIST_INTEGRITY_CHECK_VALUE                //校验值
	configLIST_VOLATILE UBaseType_t uxNumberOfItems;    //列表中的列表项数量
	ListItem_t * configLIST_VOLATILE pxIndex;           //用于遍历列表项的指针
	MiniListItem_t xListEnd;                            //末尾列表项
	listSECOND_LIST_INTEGRITY_CHECK_VALUE               //校验值
} List_t;

①、首尾两个校验值是通过宏定义的已知常量，通过检测这两个值来判断列表的数据在运行过程中是否正确。该功能一般用于调试，默认关闭；

②、uxNumberOfItems 用于记录列表中列表项的个数；

③、pxIndex 用来指向列表中的某个列表项，一般用来遍历列表；

④、xListEnd 是末尾列表项

⑤、列表示意图：

三、列表项

struct xLIST_ITEM
{
	listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE             //校验项
	configLIST_VOLATILE TickType_t xItemValue;            //列表项的值
	struct xLIST_ITEM * configLIST_VOLATILE pxNext;       //下一个列表项
	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;   //上一个列表项
	void * pvOwner;                                       //列表项的拥有者
	void * configLIST_VOLATILE pvContainer;               //列表项所在的列表
	listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE            //校验项
typedef struct xLIST_ITEM ListItem_t;

①、首尾校验项默认关闭；

②、xItemValue 为列表项的一个值，用来对列表项进行排序；

③、pxNext、pxPrevious 前后指针；

④、pvOwner 用来指向任务控制块；

⑤、pvContainer 用来指向列表，例如就绪列表、阻塞列表、挂起列表；

⑥、列表项示意图：

四、mini列表项

struct xMINI_LIST_ITEM
{    
	listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE              //校验值
	configLIST_VOLATILE TickType_t xItemValue;             //列表项的值
	struct xLIST_ITEM * configLIST_VOLATILE pxNext;        //上一个列表
	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;    //下一个列表
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;

与列表项类似，固定在列表项的结尾。

mini列表项示意图：

 五、列表与列表项相关API函数

1、列表初始化

void vListInitialise( List_t * const pxList )
{
//列表中只有 xListEnd ，因此 pxIndex 指向 xListEnd 
    pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );

//列表的末尾项因为排在最后，所以要给最大值0xFFFFFFFF
    pxList->xListEnd.xItemValue = portMAX_DELAY;

//列表中只有 xListEnd ，因此上一个与下一个都指向自身
    pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
    pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );

//列表中没有列表项（mini列表项不算），因此赋值为0
    pxList->uxNumberOfItems = ( UBaseType_t ) 0U;

//检测完整性代码，默认关闭
    listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
    listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}

2、列表项初始化 

void vListInitialiseItem( ListItem_t * const pxItem )
{
//初始化列表项所在列表为空
    pxItem->pvContainer = NULL; //初始化 pvContainer 为 NULL

//初始化用于完整性检查的变量，如果开启了这个功能的话。
    listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
    listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}

        列表项其他成员会在插入时进行设置。 

3、插入列表项

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

        用于将插入列表的列表项按照 xItemValue 的大小升序进行排列，有序的插入到列表中。

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 );
    
    //如果新插入的 xItemValue 与末尾列表项 xItemValue 值相等，那么让它插入到末尾列表项的上一个
    if( xValueOfInsertion == portMAX_DELAY )
    {
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {

    //末尾列表项赋值给新定义的列表项 pxIterator，然后遍历列表，判断 xItemValue 的值是否大于 xValueOfInsertion。如果大于则退出循环，找到插入的位置
        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 )++;
}

        插入列表项实例： 

4、末尾插入列表项

        类似于双向链表插入到末尾，无序插入，只与 pxIndex 指向的列表项有关，只插入到 pxIndex 指向的列表项的前面。

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
    //新建一个 pxIndex 指向列表 pxIndex 指向的列表项，默认为末尾列表项
    ListItem_t * const pxIndex = pxList->pxIndex;

    listTEST_LIST_INTEGRITY( pxList );
    listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

    //将待插列表项插入到 pxIndex 的前面
    pxNewListItem->pxNext = pxIndex;
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;

    mtCOVERAGE_TEST_DELAY();

    pxIndex->pxPrevious->pxNext = pxNewListItem;
    pxIndex->pxPrevious = pxNewListItem;

    //更新待插列表项所在列表
    pxNewListItem->pvContainer = ( void * ) pxList;

    //更新列表中所含列表项的数值
    ( pxList->uxNumberOfItems )++;
}

5、移除列表项

        用于将列表项移除其所在列表。返回值为所在列表剩余的列表项。

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
    //获取所在列表
    List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;

    //删除列表中的所在列表项
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    mtCOVERAGE_TEST_DELAY();

    //如果 pxIndex 正好指向待移除的列表项
    if( pxList->pxIndex == pxItemToRemove )
    {
        // 让 pxIndex 指向上一个列表项
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }

    //将待移除的列表项所在列表指针清空
    pxItemToRemove->pvContainer = NULL;

    //更新列表中列表项数量
    ( pxList->uxNumberOfItems )--;

    //返回剩余数量
    return pxList->uxNumberOfItems;
}

六、实例

        该实例执行列表的相关操作并将每次执行完操作后列表项指针所指地址打印出来。

1、定义列表与列表项

List_t      TestList;  //定义测试列表
ListItem_t  ListItem1; //定义测试列表项1
ListItem_t  ListItem2; //定义测试列表项2
ListItem_t  ListItem3; //定义测试列表项3

2、初始化列表与列表项

    vListInitialise( &TestList );
    vListInitialiseItem( &ListItem1 );
    vListInitialiseItem( &ListItem2 );
    vListInitialiseItem( &ListItem3 );
    ListItem1.xItemValue=40;
    ListItem1.xItemValue=60;
    ListItem1.xItemValue=50;

3、插入与删除列表项

    vListInsert(&TestList,&ListItem1);		//插入列表项ListItem1
	printf("/******************添加列表项ListItem1*****************/\r\n");
	printf("项目                              地址				    \r\n");
	printf("TestList->xListEnd->pxNext        %#x					\r\n",(int)(TestList.xListEnd.pxNext));
	printf("ListItem1->pxNext                 %#x					\r\n",(int)(ListItem1.pxNext));
	printf("/*******************前后向连接分割线********************/\r\n");
	printf("TestList->xListEnd->pxPrevious    %#x					\r\n",(int)(TestList.xListEnd.pxPrevious));
	printf("ListItem1->pxPrevious             %#x					\r\n",(int)(ListItem1.pxPrevious));
	printf("/************************结束**************************/\r\n");
    
    vListInsert(&TestList,&ListItem2);	//插入列表项ListItem2
	printf("/******************添加列表项ListItem2*****************/\r\n");
	printf("项目                              地址				    \r\n");
	printf("TestList->xListEnd->pxNext        %#x					\r\n",(int)(TestList.xListEnd.pxNext));
	printf("ListItem1->pxNext                 %#x					\r\n",(int)(ListItem1.pxNext));
	printf("ListItem2->pxNext                 %#x					\r\n",(int)(ListItem2.pxNext));
	printf("/*******************前后向连接分割线********************/\r\n");
	printf("TestList->xListEnd->pxPrevious    %#x					\r\n",(int)(TestList.xListEnd.pxPrevious));
	printf("ListItem1->pxPrevious             %#x					\r\n",(int)(ListItem1.pxPrevious));
	printf("ListItem2->pxPrevious             %#x					\r\n",(int)(ListItem2.pxPrevious));
	printf("/************************结束**************************/\r\n");
    
    vListInsert(&TestList,&ListItem3);	//插入列表项ListItem3
	printf("/******************添加列表项ListItem3*****************/\r\n");
	printf("项目                              地址				    \r\n");
	printf("TestList->xListEnd->pxNext        %#x					\r\n",(int)(TestList.xListEnd.pxNext));
	printf("ListItem1->pxNext                 %#x					\r\n",(int)(ListItem1.pxNext));
	printf("ListItem3->pxNext                 %#x					\r\n",(int)(ListItem3.pxNext));
	printf("ListItem2->pxNext                 %#x					\r\n",(int)(ListItem2.pxNext));
	printf("/*******************前后向连接分割线********************/\r\n");
	printf("TestList->xListEnd->pxPrevious    %#x					\r\n",(int)(TestList.xListEnd.pxPrevious));
	printf("ListItem1->pxPrevious             %#x					\r\n",(int)(ListItem1.pxPrevious));
	printf("ListItem3->pxPrevious             %#x					\r\n",(int)(ListItem3.pxPrevious));
	printf("ListItem2->pxPrevious             %#x					\r\n",(int)(ListItem2.pxPrevious));
	printf("/************************结束**************************/\r\n");
    
    uxListRemove(&ListItem2);						//删除ListItem2
	printf("/******************删除列表项ListItem2*****************/\r\n");
	printf("项目                              地址				    \r\n");
	printf("TestList->xListEnd->pxNext        %#x					\r\n",(int)(TestList.xListEnd.pxNext));
	printf("ListItem1->pxNext                 %#x					\r\n",(int)(ListItem1.pxNext));
	printf("ListItem3->pxNext                 %#x					\r\n",(int)(ListItem3.pxNext));
	printf("/*******************前后向连接分割线********************/\r\n");
	printf("TestList->xListEnd->pxPrevious    %#x					\r\n",(int)(TestList.xListEnd.pxPrevious));
	printf("ListItem1->pxPrevious             %#x					\r\n",(int)(ListItem1.pxPrevious));
	printf("ListItem3->pxPrevious             %#x					\r\n",(int)(ListItem3.pxPrevious));
	printf("/************************结束**************************/\r\n");\
    
    TestList.pxIndex=TestList.pxIndex->pxNext;			//pxIndex向后移一项，这样pxIndex就会指向ListItem1。
	vListInsertEnd(&TestList,&ListItem2);				//列表末尾添加列表项ListItem2
	printf("/***************在末尾添加列表项ListItem2***************/\r\n");
	printf("项目                              地址				    \r\n");
	printf("TestList->pxIndex                 %#x					\r\n",(int)TestList.pxIndex);
	printf("TestList->xListEnd->pxNext        %#x					\r\n",(int)(TestList.xListEnd.pxNext));
	printf("ListItem2->pxNext                 %#x					\r\n",(int)(ListItem2.pxNext));
	printf("ListItem1->pxNext                 %#x					\r\n",(int)(ListItem1.pxNext));
	printf("ListItem3->pxNext                 %#x					\r\n",(int)(ListItem3.pxNext));
	printf("/*******************前后向连接分割线********************/\r\n");
	printf("TestList->xListEnd->pxPrevious    %#x					\r\n",(int)(TestList.xListEnd.pxPrevious));
	printf("ListItem2->pxPrevious             %#x					\r\n",(int)(ListItem2.pxPrevious));
	printf("ListItem1->pxPrevious             %#x					\r\n",(int)(ListItem1.pxPrevious));
	printf("ListItem3->pxPrevious             %#x					\r\n",(int)(ListItem3.pxPrevious));
	printf("/************************结束**************************/\r\n\r\n\r\n");