原创 五、freeRTOS 列表与列表项

FreeRTOS 列表

列表的数据结构：

1. /*
2. * Definition of the type of queue used by the scheduler.
3. */
4. typedef struct xLIST
5. {
6. listFIRST_LIST_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
7. configLIST_VOLATILE UBaseType_t uxNumberOfItems;
8. ListItem_t * configLIST_VOLATILE pxIndex; /*< Used to walk through the list. Points to the last item returned by a call to listGET_OWNER_OF_NEXT_ENTRY (). */
9. MiniListItem_t xListEnd; /*< List item that contains the maximum possible item value meaning it is always at the end of the list and is therefore used as a marker. */
10. listSECOND_LIST_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
11. } List_t;
14. /* Macros used for basic data corruption checks. */
15. #ifndef configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES
16. #define configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES 0
17. #endif
19. // 如果宏定义为1，则这两个链表检查项定义成变量
20. #if (configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES == 0)
21. /* Define the macros to do nothing. */
22. #define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE // 链表节点检查项
23. #define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
24. #define listFIRST_LIST_INTEGRITY_CHECK_VALUE // 链表检查项
25. #define listSECOND_LIST_INTEGRITY_CHECK_VALUE
26. #else
27. /* Define macros that add new members into the list structures. */
28. #define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE TickType_t xListItemIntegrityValue1;
29. #define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE TickType_t xListItemIntegrityValue2;
30. // 链表检查项定义成变量
31. #define listFIRST_LIST_INTEGRITY_CHECK_VALUE TickType_t xListIntegrityValue1;
32. #define listSECOND_LIST_INTEGRITY_CHECK_VALUE TickType_t xListIntegrityValue2;
33. #endif

列表的元素分析：

列表的首尾两个元素，都是用来检查列表完整性的，需要将宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES 设置为 1，开启以后会向这两个地方分别添加一个变量 xListIntegrityValue1 和 xListIntegrityValue2，在初始化列表的时候会这两个变量中写入一个特殊的值，默认不开启这个功能；

uxNumberOfItems 用来记录列表中列表项的数量；

pxIndex 用来记录当前列表项索引号，用于遍历列表；

列表中最后一个列表项，用来表示列表结束，此变量类型为 MiniListItem_t，这是一个迷你列表项；

列表的结构图：

列表项：

列表项就是存放在列表中的项目，FreeRTOS 提供了两种列表项：列表项和迷你列表项；

1. /*
2. * Definition of the only type of object that a list can contain.
3. */
4. struct xLIST_ITEM
5. {
6. listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
7. configLIST_VOLATILE TickType_t xItemValue; /*< The value being listed. In most cases this is used to sort the list in descending order. */
8. struct xLIST_ITEM *configLIST_VOLATILE pxNext; /*< Pointer to the next ListItem_t in the list. */
9. struct xLIST_ITEM *configLIST_VOLATILE pxPrevious; /*< Pointer to the previous ListItem_t in the list. */
10. void *pvOwner; /*< Pointer to the object (normally a TCB) that contains the list item. There is therefore a two way link between the object containing the list item and the list item itself. */
11. void *configLIST_VOLATILE pvContainer; /*< Pointer to the list in which this list item is placed (if any). */
12. listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
13. };
14. typedef struct xLIST_ITEM ListItem_t; /* For some reason lint wants this as two separate definitions. */

首尾两项与列表类似，为完整性检查；

xItemValue 为列表项值；

pxNext 指向下一个列表项，pxPrevious 指向前一个列表项，和 pxNext 配合起来实现类似双向链表的功能；

pvOwner 记录此链表项归谁拥有，通常是任务控制块；

pvContainer 用来记录此列表项归哪个列表；

列表项的结构示意图：

任务控制块的数据结构：

迷你列表项：

1. struct xMINI_LIST_ITEM
2. {
3. listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
4. configLIST_VOLATILE TickType_t xItemValue;
5. struct xLIST_ITEM *configLIST_VOLATILE pxNext;
6. struct xLIST_ITEM *configLIST_VOLATILE pxPrevious;
7. };
8. typedef struct xMINI_LIST_ITEM MiniListItem_t;

参数说明：

列表和列表项相关的操作：

1 列表初始化示意图：

2 列表的升序插入示意图：

插入单个列表项

插入多个列表项

列表的初始化 排序插入等操作，都不需要操作遍历指针 pxList->pxIndex 这个指针。

链表的尾部插入：

由于是环形链表，所以根本就没有头部和尾部之说。那么，如何确定链表开始的地方？这就要靠遍历指针 pxList->pxIndex

pxIndex这个指针指向的列表项，就是链表的开始，那么很明显，pxIndex->Previous指向的列表项就是链表的结尾；

我们所说的链表尾部插入，就是要插入到pxIndex->Previous处。

重点分析：

1. void vListInsertEnd(List_t *const pxList, ListItem_t *const pxNewListItem)
2. {
3. ListItem_t *const pxIndex = pxList->pxIndex;
5. /* Insert a new list item into pxList, but rather than sort the list,
6. makes the new list item the last item to be removed by a call to
7. listGET_OWNER_OF_NEXT_ENTRY(). */
8. // 在pxList中插入一个新的列表项，而不是对列表进行排序
9. // 使新的列表项成为调用listGET_OWNER_OF_NEXT_ENTRY()删除的最后一个项
11. // 这里所谓的末尾要根据列表的成员变量pxIndex来确定，pxIndex所指向的列表项就是要遍历的开始列表项
12. // 即pxIndex所指向的列表项就代表列表头，由于是环形列表，新列表项就应该插入到pxIndex所指向的列表项的前面
13. // 只有这样，才能保证调用listGET_OWNER_OF_NEXT_ENTRY()时被最后删除
14. pxNewListItem->pxNext = pxIndex;
15. pxNewListItem->pxPrevious = pxIndex->pxPrevious;
17. pxIndex->pxPrevious->pxNext = pxNewListItem;
18. pxIndex->pxPrevious = pxNewListItem;
20. /* Remember which list the item is in. */
21. pxNewListItem->pvContainer = (void *)pxList;
23. (pxList->uxNumberOfItems)++;
24. }

插入位置分析：

尾部插入的图示：

插入前：

插入后：

列表的遍历：

列表项的插入和删除实验

代码如下：

1. // 定义一个列表和三个列表项
2. List_t testList;
3. ListItem_t ListItem1;
4. ListItem_t ListItem2;
5. ListItem_t ListItem3;
7. void list_task(void *pvParameters)
8. {
9. vListInitialise(&testList); // 初始化列表
10. vListInitialiseItem(&ListItem1); // 初始化列表项1
11. vListInitialiseItem(&ListItem2); // 初始化列表项2
12. vListInitialiseItem(&ListItem3); // 初始化列表项3
14. ListItem1.xItemValue = 40;
15. ListItem2.xItemValue = 60;
16. ListItem3.xItemValue = 50;
18. // 打印列表和其他列表项的地址
19. printf("\n/*********************列表和列表项地址************************/\n");
20. printf("项目 地址 \n");
21. printf("testList %#X \n", (int)&testList);
22. printf("testList->pxIndex %#X \n", (int)testList.pxIndex);
23. printf("testList->xListEnd %#X \n", (int)&testList.xListEnd);
24. printf("ListItem1 %#X \n", (int)&ListItem1);
25. printf("ListItem2 %#X \n", (int)&ListItem2);
26. printf("ListItem3 %#X \n", (int)&ListItem3);
27. printf("/***************************结束*****************************/\n");
28. printf("按下K1按键继续！\r\n\r\n");
29. while (key_scan(KEY1_GPIO_Port, KEY1_Pin) != KEY_ON);
31. // testList插入ListItem1
32. vListInsert(&testList, &ListItem1); // 插入列表项1
33. printf("\n/*******************添加列表项ListItem1**********************/\n");
34. printf("项目 地址 \n");
35. printf("testList->xListEnd->pxNext %#X \n", (int)testList.xListEnd.pxNext);
36. printf("ListItem1->pxNext %#X \n", (int)ListItem1.pxNext);
37. printf("/**********************前后向连接分割线***********************/\n");
38. printf("testList->xListEnd->pxPrevious %#X \n", (int)testList.xListEnd.pxPrevious);
39. printf("ListItem1->pxPrevious %#X \n", (int)ListItem1.pxPrevious);
40. printf("/***************************结束*****************************/\n");
41. printf("按下K1按键继续！\r\n\r\n");
42. while (key_scan(KEY1_GPIO_Port, KEY1_Pin) != KEY_ON);
44. // testList插入ListItem2
45. vListInsert(&testList, &ListItem2); // 插入列表项2
46. printf("\n/*******************添加列表项ListItem2**********************/\n");
47. printf("项目 地址 \n");
48. printf("testList->xListEnd->pxNext %#X \n", (int)testList.xListEnd.pxNext);
49. printf("ListItem1->pxNext %#X \n", (int)ListItem1.pxNext);
50. printf("ListItem2->pxNext %#X \n", (int)ListItem2.pxNext);
51. printf("/**********************前后向连接分割线***********************/\n");
52. printf("testList->xListEnd->pxPrevious %#X \n", (int)testList.xListEnd.pxPrevious);
53. printf("ListItem1->pxPrevious %#X \n", (int)ListItem1.pxPrevious);
54. printf("ListItem2->pxPrevious %#X \n", (int)ListItem2.pxPrevious);
55. printf("/***************************结束*****************************/\n");
56. printf("按下K1按键继续！\r\n\r\n");
57. while (key_scan(KEY1_GPIO_Port, KEY1_Pin) != KEY_ON);
59. // testList插入ListItem3
60. vListInsert(&testList, &ListItem3); // 插入列表项3
61. printf("\n/*******************添加列表项ListItem3**********************/\n");
62. printf("项目 地址 \n");
63. printf("testList->xListEnd->pxNext %#X \n", (int)testList.xListEnd.pxNext);
64. printf("ListItem1->pxNext %#X \n", (int)ListItem1.pxNext);
65. printf("ListItem3->pxNext %#X \n", (int)ListItem3.pxNext);
66. printf("ListItem2->pxNext %#X \n", (int)ListItem2.pxNext);
67. printf("/**********************前后向连接分割线***********************/\n");
68. printf("testList->xListEnd->pxPrevious %#X \n", (int)testList.xListEnd.pxPrevious);
69. printf("ListItem1->pxPrevious %#X \n", (int)ListItem1.pxPrevious);
70. printf("ListItem3->pxPrevious %#X \n", (int)ListItem3.pxPrevious);
71. printf("ListItem2->pxPrevious %#X \n", (int)ListItem2.pxPrevious);
72. printf("/***************************结束*****************************/\n");
73. printf("按下K1按键继续！\r\n\r\n");
74. while (key_scan(KEY1_GPIO_Port, KEY1_Pin) != KEY_ON);
76. // testList删除ListItem2
77. uxListRemove(&ListItem2);
78. printf("\n/*******************删除列表项ListItem2**********************/\n");
79. printf("项目 地址 \n");
80. printf("testList->xListEnd->pxNext %#X \n", (int)testList.xListEnd.pxNext);
81. printf("ListItem1->pxNext %#X \n", (int)ListItem1.pxNext);
82. printf("ListItem3->pxNext %#X \n", (int)ListItem3.pxNext);
83. printf("/**********************前后向连接分割线***********************/\n");
84. printf("testList->xListEnd->pxPrevious %#X \n", (int)testList.xListEnd.pxPrevious);
85. printf("ListItem1->pxPrevious %#X \n", (int)ListItem1.pxPrevious);
86. printf("ListItem3->pxPrevious %#X \n", (int)ListItem3.pxPrevious);
87. printf("/***************************结束*****************************/\n");
88. printf("按下K1按键继续！\r\n\r\n");
89. while (key_scan(KEY1_GPIO_Port, KEY1_Pin) != KEY_ON);
91. // pxIndex向后移一项，这样pxIndex就会指向ListItem1
92. testList.pxIndex = testList.pxIndex->pxNext;
93. vListInsertEnd(&testList, &ListItem2); // 列表末尾添加列表项ListItem2
94. printf("\n/*****************在末尾添加列表项ListItem2******************/\n");
95. printf("项目 地址 \n");
96. printf("testList.pxIndex %#X \n", (int)testList.pxIndex);
97. printf("testList->xListEnd->pxNext %#X \n", (int)testList.xListEnd.pxNext);
98. printf("ListItem2->pxNext %#X \n", (int)ListItem2.pxNext);
99. printf("ListItem1->pxNext %#X \n", (int)ListItem1.pxNext);
100. printf("ListItem3->pxNext %#X \n", (int)ListItem3.pxNext);
101. printf("/**********************前后向连接分割线***********************/\n");
102. printf("testList->xListEnd->pxPrevious %#X \n", (int)testList.xListEnd.pxPrevious);
103. printf("ListItem2->pxPrevious %#X \n", (int)ListItem2.pxPrevious);
104. printf("ListItem1->pxPrevious %#X \n", (int)ListItem1.pxPrevious);
105. printf("ListItem3->pxPrevious %#X \n", (int)ListItem3.pxPrevious);
106. printf("/***************************结束*****************************/\n");
107. printf("按下K1按键继续！\r\n\r\n");
108. while (key_scan(KEY1_GPIO_Port, KEY1_Pin) != KEY_ON);
109. printf("list_task开始任务调度\n");
111. for (;;)
112. {
113. printf("list_task run!\n");
114. vTaskDelay(500);
115. }
116. }

程序执行结果如下：

/*********************列表和列表项地址************************/

项目                            地址                          

testList                        0X20000080                          

testList->pxIndex               0X20000088                          

testList->xListEnd              0X20000088                          

ListItem1                       0X20000094                          

ListItem2                       0X200000A8                          

ListItem3                       0X200000BC                          

/***************************结束*****************************/

按下K1按键继续！

/*******************添加列表项ListItem1**********************/

项目                            地址                          

testList->xListEnd->pxNext      0X20000094                          

ListItem1->pxNext               0X20000088                          

/**********************前后向连接分割线***********************/

testList->xListEnd->pxPrevious  0X20000094                          

ListItem1->pxPrevious           0X20000088                          

/***************************结束*****************************/

按下K1按键继续！

/*******************添加列表项ListItem2**********************/

项目                            地址                          

testList->xListEnd->pxNext      0X20000094                          

ListItem1->pxNext               0X200000A8                          

ListItem2->pxNext               0X20000088                          

/**********************前后向连接分割线***********************/

testList->xListEnd->pxPrevious  0X200000A8                          

ListItem1->pxPrevious           0X20000088                          

ListItem2->pxPrevious           0X20000094                          

/***************************结束*****************************/

按下K1按键继续！

/*******************添加列表项ListItem3**********************/

项目                            地址                          

testList->xListEnd->pxNext      0X20000094                          

ListItem1->pxNext               0X200000BC                          

ListItem3->pxNext               0X200000A8                          

ListItem2->pxNext               0X20000088                          

/**********************前后向连接分割线***********************/

testList->xListEnd->pxPrevious  0X200000A8                          

ListItem1->pxPrevious           0X20000088                          

ListItem3->pxPrevious           0X20000094                          

ListItem2->pxPrevious           0X200000BC                          

/***************************结束*****************************/

按下K1按键继续！

/*******************删除列表项ListItem2**********************/

项目                            地址                          

testList->xListEnd->pxNext      0X20000094                          

ListItem1->pxNext               0X200000BC                          

ListItem3->pxNext               0X20000088                          

/**********************前后向连接分割线***********************/

testList->xListEnd->pxPrevious  0X200000BC                          

ListItem1->pxPrevious           0X20000088                          

ListItem3->pxPrevious           0X20000094                          

/***************************结束*****************************/

按下K1按键继续！

/*****************在末尾添加列表项ListItem2******************/

项目                            地址                          

testList.pxIndex                0X20000094                          

testList->xListEnd->pxNext      0X200000A8                          

ListItem2->pxNext               0X20000094                          

ListItem1->pxNext               0X200000BC                          

ListItem3->pxNext               0X20000088                          

/**********************前后向连接分割线***********************/

testList->xListEnd->pxPrevious  0X200000BC                          

ListItem2->pxPrevious           0X20000088                          

ListItem1->pxPrevious           0X200000A8                          

ListItem3->pxPrevious           0X20000094                          

/***************************结束*****************************/

按下K1按键继续！

list_task开始任务调度

list_task run!

list_task run!

list_task run!

list_task run!

list_task run!

转载于：https://blog.csdn.net/dingyc_ee/article/details/104071570