# 内核篇.01 列表与列表项
- 为什么要学列表？
- 链表
- 单向链表
- 双向链表
- FreeRTOS 中链表的实现
- 节点
- 节点初始化
- 尾节点
- 根节点
- 链表根节点初始化
- 将节点插入到链表的尾部
- 将节点按照升序排列插入到链表
- 将节点从链表删除
- 节点带参宏小函数
- 链表节点插入实验
- 实验现象
为什么要学列表？
我们学习FreeRTOS为什么又扯到数据结构了？？FreeRTOS作为一款嵌入式操作系统，我们学习必定要了解他的底层实现，和Windows、ios等系统一样 都是从底层搭建成的，底层是什么？数据结构和大量算法喽，只不过你没了解过其它系统罢了。RTOS相较于那些还是比较简单的，那么我们一块来学习一下 FreeRTOS系统内核吧。
在 FreeRTOS 中存在着大量的基础数据结构列表和列表项的操作，要想读懂 FreeRTOS的源码或者从 0 到 1开始实现 FreeRTOS，就必须弄懂列表和列表项的操作，其实也没那么难。
列表和列表项是直接从 FreeRTOS 源码的注释中的 list 和 list item 翻译过来的，其实就是对应我们 C 语言当中的链表和节点，在后续的讲解中，我们说的链表就是列表，节点就是列表项
链表
数据结构，对于大家计算机的学生都不陌生，第一次学习链表还是在C语言中，但日常使用并不多，再次复习一下，
链表作为 C 语言中一种基础的数据结构，在平时写程序的时候用的并不多，但在操作系统里面使用的非常多。链表就好比一个圆形的晾衣架，晾衣架上面有很多钩子，钩子首尾相连。链表也是，链表由节点组成，节点与节点之间首尾相连。晾衣架的钩子本身不能代表很多东西，但是钩子本身却可以挂很多东西。同样，链表也类似，链表的节点本身不能存储太多东西，或者说链表的节点本来就不是用来存储大量数据的，但是节点跟晾衣架的钩子一样，可以挂很多数据。
链表分为单向链表和双向链表，单向链表很少用，使用最多的还是双向链表
单向链表
- 链表的定义
单向链表示意图具体见图。该链表中共有 n个节点，前一个节点都有一个箭头指向后一个节点，首尾相连，组成一个圈。
对于我们第一次学习数据结构里面的一些名词，链表，堆栈等都很抽象，毕竟都是计算机内存的东西，看不到，那这样给你说节点就是定义一个自定义类型的数据，自定义类型？结构体，类？？c语言中肯定是结构体啦，这样是不是就绕过来了。
节点本身必须包含一个节点指针，用于指向后一个节点，除了这个节点指针是必须有的之外，节点本身还可以携带一些私有信息。
节点都是一个自定义类型的数据结构，在这个数据结构里面可以有单个的数据、数组、
指针数据和自定义的结构体数据类型等等信息，具体见代码清单
//节点结构体定义
struct node
{
struct node *next; /* 指向链表的下一个节点 */
char data1; /* 单个的数据 */
unsigned char array[]; /* 数组 */
unsigned long *prt /* 指针数据 */
struct userstruct data2; /* 自定义结构体类型数据 */
/* ...... */
}
除了 struct node *next 这个节点指针之外，剩下的成员都可以理解为节点携带的数据，但是这种方法很少用。通常的做法是节点里面只包含一个用于指向下一个节点的指针。要通过链表存储的数据内嵌一个节点即可，这些要存储的数据通过这个内嵌的节点即可挂接到链表中，就好像晾衣架的钩子一样，把衣服挂接到晾衣架中。
//节点内嵌在一个数据结构中
/* 节点定义 */
struct node
{
struct node *next; /* 指向链表的下一个节点 */
}
struct userstruct
{
/* 在结构体中，内嵌一个节点指针，通过这个节点将数据挂接到链表 */
struct node *next;
/* 各种各样......，要存储的数据 */
}
示意图：
双向链表
双向链表与单向链表的区别就是节点中有两个节点指针，分别指向前后两个节点，其
它完全一样。有关双向链表的文字描述参考单向链表小节即可，有关双向链表的示意图具
体见图
FreeRTOS 中链表的实现
FreeRTOS 中与链表相关的操作均在 list.h 和 list.c 这两个文件中实现，list.h 第一次使用需要在 include 文件夹下面新建然后添加到工程组文件。
节点
struct xLIST_ITEM
{
TickType_t xItemValue; /* 辅助值，用于帮助节点做顺序排列 */ (1)
struct xLIST_ITEM * pxNext; /* 指向链表下一个节点 */ (2)
struct xLIST_ITEM * pxPrevious; /* 指向链表前一个节点 */ (3)
void * pvOwner; /* 指向拥有该节点的内核对象，通常是 TCB */(4)
void * pvContainer; /* 指向该节点所在的链表 */ (5)
};
typedef struct xLIST_ITEM ListItem_t; /* 节点数据类型重定义 */
xItemValue一个辅助值，用于帮助节点做顺序排列。该辅助值的数据类型为
TickType_t，在 FreeRTOS 中，凡是涉及到数据类型的地方，FreeRTOS 都会将标准的 C 数据类型用 typedef 重新取一个类型名。这些经过重定义的数据类型放在 portmacro.h
portmacro.h头文件是FreeRTOS中对类型重定义的地方。
1 #ifndef PORTMACRO_H
2 #define PORTMACRO_H
3
4 #include "stdint.h"
5 #include "stddef.h"
6
7
8 /* 数据类型重定义 */
9 #define portCHAR char
10 #define portFLOAT float
11 #define portDOUBLE double
12 #define portLONG long
13 #define portSHORT short
14 #define portSTACK_TYPE uint32_t
15 #define portBASE_TYPE long
16
17 typedef portSTACK_TYPE StackType_t;
18 typedef long BaseType_t;
19 typedef unsigned long UBaseType_t;
20
21 #if( configUSE_16_BIT_TICKS == 1 ) (1)
22 typedef uint16_t TickType_t;
23 #define portMAX_DELAY ( TickType_t ) 0xffff
24 #else
25 typedef uint32_t TickType_t;
26 #define portMAX_DELAY ( TickType_t ) 0xffffffffUL
27 #endif
28
29 #endif /* PORTMACRO_H */
链表节点初始化函数在 list.c 中实现，具体实现见代码清单
节点初始化
//链表节点初始化
1 void vListInitialiseItem( ListItem_t * const pxItem )
2 {
3 /* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
4 pxItem->pvContainer = NULL; (1)
5 }
尾节点
链表尾节点的数据结构：
struct xMINI_LIST_ITEM
{
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
configLIST_VOLATILE TickType_t xItemValue;
struct xLIST_ITEM * configLIST_VOLATILE pxNext;
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;
根节点
列表根节点 数据结构 根节点即第一个节点。
typedef struct xLIST
{
UBaseType_t uxNumberOfItems; /* 链表节点计数器 */ (1)
ListItem_t * pxIndex; /* 链表节点索引指针 */ (2)
MiniListItem_t xListEnd; /* 链表最后一个节点 */ (3)
} List_t;
下面三个节点和列表操作函数，具体参数可以参考野火的FreeRTOS讲解。太多了，不过多介绍。
链表根节点初始化
1 void vListInitialise( List_t * const pxList )
2 {
3 /* 将链表索引指针指向最后一个节点 */(1)
4 pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
5
6 /* 将链表最后一个节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点 */(2)
7 pxList->xListEnd.xItemValue = portMAX_DELAY;
8
9 /* 将最后一个节点的 pxNext 和 pxPrevious 指针均指向节点自身，表示链表为空 */(3)
10 pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
11 pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
12
13 /* 初始化链表节点计数器的值为 0，表示链表为空 */(4)
14 pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
15 }
将节点插入到链表的尾部
代码清单 6-11将节点插入到链表的尾部
1 void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
2 {
3 ListItem_t * const pxIndex = pxList->pxIndex;
4
5 pxNewListItem->pxNext = pxIndex; ①
6 pxNewListItem->pxPrevious = pxIndex->pxPrevious; ②
7 pxIndex->pxPrevious->pxNext = pxNewListItem; ③
8 pxIndex->pxPrevious = pxNewListItem; ④
9
10 /* 记住该节点所在的链表 */
11 pxNewListItem->pvContainer = ( void * ) pxList; ⑤
12
13 /* 链表节点计数器++ */
14 ( pxList->uxNumberOfItems )++; ⑥
15 }
将节点按照升序排列插入到链表
1 void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
2 {
3 ListItem_t *pxIterator;
4
5 /* 获取节点的排序辅助值 */
6 const TickType_t xValueOfInsertion = pxNewListItem->xItemValue; (1)
7
8 /* 寻找节点要插入的位置 */ (2)
9 if ( xValueOfInsertion == portMAX_DELAY )
10 {
11 pxIterator = pxList->xListEnd.pxPrevious;
12 }
13 else
14 {
15 for ( pxIterator = ( ListItem_t * ) &( pxList->xListEnd );
16 pxIterator->pxNext->xItemValue <= xValueOfInsertion;
17 pxIterator = pxIterator->pxNext )
18 {
19 /* 没有事情可做，不断迭代只为了找到节点要插入的位置 */
20 }
21 }
22 /* 根据升序排列，将节点插入 */ (3)
23 pxNewListItem->pxNext = pxIterator->pxNext; ①
24 pxNewListItem->pxNext->pxPrevious = pxNewListItem; ②
25 pxNewListItem->pxPrevious = pxIterator; ③
26 pxIterator->pxNext = pxNewListItem; ④
27
28 /* 记住该节点所在的链表 */
29 pxNewListItem->pvContainer = ( void * ) pxList; ⑤
30
31 /* 链表节点计数器++ */
32 ( pxList->uxNumberOfItems )++; ⑥
33 }
将节点从链表删除
1 UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
2 {
3 /* 获取节点所在的链表 */
4 List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
5 /* 将指定的节点从链表删除*/
6 pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious; ①
7 pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext; ②
8
9 /*调整链表的节点索引指针 */
10 if ( pxList->pxIndex == pxItemToRemove )
11 {
12 pxList->pxIndex = pxItemToRemove->pxPrevious;
13 }
14
15 /* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
16 pxItemToRemove->pvContainer = NULL; ③
17
18 /* 链表节点计数器-- */
19 ( pxList->uxNumberOfItems )--; ④
20
21 /* 返回链表中剩余节点的个数 */
22 return pxList->uxNumberOfItems;
23 }
节点带参宏小函数
在 list.h 中，还定义了各种各样的带参宏，方便对节点做一些简单的操作，具体实现见下面代码清单。
节点带参宏小函数
1 /* 初始化节点的拥有者 */
2 #define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )\
3 ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )
4
5 /* 获取节点拥有者 */
6 #define listGET_LIST_ITEM_OWNER( pxListItem )\
7 ( ( pxListItem )->pvOwner )
8
9 /* 初始化节点排序辅助值 */
10 #define listSET_LIST_ITEM_VALUE( pxListItem, xValue )\
11 ( ( pxListItem )->xItemValue = ( xValue ) )
12
13 /* 获取节点排序辅助值 */
14 #define listGET_LIST_ITEM_VALUE( pxListItem )\
15 ( ( pxListItem )->xItemValue )
16
17 /* 获取链表根节点的节点计数器的值 */
18 #define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )\
19 ( ( ( pxList )->xListEnd ).pxNext->xItemValue )
20
21 /* 获取链表的入口节点 */
22 #define listGET_HEAD_ENTRY( pxList )\
23 ( ( ( pxList )->xListEnd ).pxNext )
24
25 /* 获取节点的下一个节点 */
26 #define listGET_NEXT( pxListItem )\
27 ( ( pxListItem )->pxNext )
28
29 /* 获取链表的最后一个节点 */
30 #define listGET_END_MARKER( pxList )\
31 ( ( ListItem_t const * ) ( &( ( pxList )->xListEnd ) ) )
32
33 /* 判断链表是否为空 */
34 #define listLIST_IS_EMPTY( pxList )\
35 ( ( BaseType_t ) ( ( pxList )->uxNumberOfItems == ( UBaseType_t )
0 ) )
36
37 /* 获取链表的节点数 */
38 #define listCURRENT_LIST_LENGTH( pxList )\
39 ( ( pxList )->uxNumberOfItems )
40
41 /* 获取链表第一个节点的 OWNER，即 TCB */
42 #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \
43 { \
44 List_t * const pxConstList = ( pxList ); \
45 /* 节点索引指向链表第一个节点 */ \
46 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \
47 /* 这个操作有啥用？ */ \
48 if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) \
49 { \
50 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \
51 } \
52 /* 获取节点的 OWNER，即 TCB */ \
53 ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; \
54 }
我们把FreeRTOS源码移植到裸机工程中，或者用软件仿真的工程，移植完文件后，在主函数中进行试验，查看实验现象。
链表节点插入实验
我们新建一个根节点（也可以理解为链表）和三个普通节点，然后将这三个普通节点按照节点的排序辅助值做升序排列插入到链表中。
#include "list.h"
//定义根节点 xLIST
struct xLIST List_Test;
//定义三个节点 xList_Item
struct xLIST_ITEM List_Item1;
struct xLIST_ITEM List_Item2;
struct xLIST_ITEM List_Item3;
/* flag 必须定义成全局变量才能添加到逻辑分析仪里面观察波形
* 在逻辑分析仪中要设置以 bit 的模式才能看到波形，不能用默认的模拟量
*/
uint32_t flag1;
uint32_t flag2;
/* 软件延时，不必纠结具体的时间 */
void delay( uint32_t count )
{
for (; count!=0; count--);
}
int main(void)
{
//根节点初始化
vListInitialise(&List_Test);
//节点初始化
vListInitialiseItem(&List_Item1);
vListInitialiseItem(&List_Item2);
vListInitialiseItem(&List_Item3);
//插入链表
vListInsert(&List_Test,&List_Item1);
vListInsert(&List_Test,&List_Item2);
vListInsert(&List_Test,&List_Item3);
for(;;)
{
}
}
实验现象
将程序编译好之后，点击调试按钮，然后全速运行，再然后把 List_Test、List_Item1 、List_Item2 和 List_Item3 这四个全局变量添加到观察窗口，然后查看这几个数据结构中pxNext 和 pxPrevious 的值即可证实图
