链表 → 列表 → list
节点 → 列表项 → list item
4.1 C语言链表
链表分为单向链表和双向链表，链表中的节点之间首尾相连，存放较少的信息，更多的是起到串联的作用。
4.1.1 单向链表
4.1.1.1 链表的定义
下图单向链表拥有 n 个节点，前一节点单向指向后一节点，最后一个节点指向第一个节点，组成一个圈。
节点为一个自定义类型的结构体变量，除了指向下一节点的指针成员外，还可以携带一些私有信息，可定义为下：
| struct node { ????struct node *next; /* 指向链表的下一个节点 */ ????char data1; ??? unsigned char array[]; ????unsigned long *prt; ????struct user_struct data2; ????… … } |
实际上，通常节点结构体中只包含一个用于指向下一个节点的指针成员。需要存放的数据结构体，通过包含节点结构体变量成员，实现数据结构体间的链路。
具体实现如下：
| struct node { ????????struct node *next; /* 指向链表的下一个节点 */ } struct data_struct { ????????/* 在结构体中，内嵌一个节点指针，通过这个节点将数据挂接到链表 */ ????????struct node *next; ????????/* 要存储的数据成员 */ ????… … } |
4.1.1.2 链表的操作
常规操作包括插入和删除，通常会人为地指定一个根节点作为生产者，且此节点还会有一个统计整条链表节点量的计数器。
4.1.2 双向链表
双向链表在单向链表的基础上，增加了一个指向前一节点的指针成员，其余与单向链表一致。
4.1.3 链表与数组区别
- 链表通过节点将处于不连续内存地址的数据连接成一张表，通过对节点的插入和删除操作实现对数据的存取。数组通过开辟一段连续的内存空间来存放数据，通过地址的偏移等操作对指定地址的数组成员数据进行读写；
- 数组的成员类型已经规定好，而链表的节点成员的数据类型可支持定义；
- 数组由起始地址和结束地址，而链表没有头尾之分，只有人为规定的根节点。
4.2 FreeRTOS 中链表的实现
- FreeRTOS 源码中与链表相关的操作在 FreeRTOS_V9.0.0a\Source\include\list.h 和? FreeRTOS_V9.0.0a\Source\list.c 中实现，相应的在 MDK 仿真工程中建立对应的源码文件：FreeRTOS_Project\FreeRTOS\Source\include\list.h；FreeRTOS_Project\FreeRTOS\Source\list.c。
- FreeRTOS 源码中操作系统的配置文件为 FreeRTOSConfig.h，存放在 FreeRTOS_V9.0.0a\Demo 目录下的各个官方移植例程中，不同例程针对不同的内核，相应的在 MDK 仿真工程中建立对应的源码文件：G:\学习-FreeRTOS\FreeRTOS_Project\User\FreeRTOSConfig.h。
- FreeRTOS 定义有自己的数据类型，通过 typedef 对 C 语言已有的数据类型进行重定义，定义代码存放在 FreeRTOS_V9.0.0a\Source\portable\RVDS 目录下，并以针对不同内核进行区分，以 CM3 内核为例：FreeRTOS_V9.0.0a\Source\portable\RVDS\ARM_CM3\portmacro.h。该目录下还有一个 port.c 文件，包含 FreeRTOS 操作系统对 CM3 内核的 NVIC、systick 等接口。
4.2.1 实现链表节点
4.2.1.1 portmacro.h
针对于 FreeRTOS 的类型重定义，添加 portmacro.h 文件至 MDK 工程的 FreeRTOS_Project\FreeRTOS\Source\portable\RVDS\ARM_CM3 目录，并配置工程的头文件目录包含。
源码的内容为：
| #ifndef __PORTMACRO_H #define __PORTMACRO_H #include "stdint.h" /* FreeRTOS 数据类型重定义 */ #define portCHAR???????char #define portFLOAT??????float #define portDOUBLE?????double #define portLONG???????long #define portSHORT??????short #define portSTACK_TYPE uint32_t #define portBASE_TYPE??long typedef portSTACK_TYPE StackType_t; typedef long BaseType_t; typedef unsigned long UBaseType_t; #if( configUSE_16_BIT_TICKS == 1 ) ????????typedef uint16_t TickType_t; ????????#define portMAX_DELAY ( TickType_t ) 0xffff #else ????????typedef uint32_t TickType_t; ????????#define portMAX_DELAY ( TickType_t ) 0xffffffffUL #endif #endif |
宏 configUSE_16_BIT_TICKS 用于定义内核的 systick 定时器为16位或32位。
4.2.1.2 FreeRTOSConfig.h
| #ifndef __FREERTOSCONFIG_H #define __FREERTOSCONFIG_H #define configUSE_16_BIT_TICKS? 0 #endif |
4.2.1.3 list.h
| #ifndef __LIST_H #define __LIST_H #include "portmacro.h" /* 双向链表节点数据类型定义 */ /* 结构体变量类型前缀 x + 变量名 LIST_ITEM */ struct xLIST_ITEM { ??? TickType_t xTtemValue;????????? /* 变量类型前缀 x + 变量名 TtemValue，辅助值，用于节点进行顺序排序 */ ??? struct xLIST_ITEM * pxNext;???? /* [指针前缀 p + ] 变量类型前缀 x + 变量名 Next，指向下一个 xLIST_ITEM 节点*/ ??? struct xLIST_ITEM * pxPrevious; /* [指针前缀 p + ] 变量类型前缀 x + 变量名 Previous，指向前一个 xLIST_ITEM 节点 */ ??? void * pvOwner;???????????????? /* [指针前缀 p + ] 空返回值类型前缀 v + 变量名 Owner，指向拥有该节点的内核对象，通常是TCB */ ??? void * pvContainer;???????????? /* [指针前缀 p + ] 空返回值类型前缀 v + 变量名 Container，指向该节点所在的链表 */ }; /* 节点数据类型重定义 */ typedef struct xLIST_ITEM ListItem_t; void vListInitialiseItem( ListItem_t * const pxItem ); #endif |
4.2.1.3 list.c
| #include "list.h" /* 双向链表节点初始化 */ /* 函数返回值类型前缀 + 函数所在文件名 + 函数功能 */ void vListInitialiseItem( ListItem_t * const pxItem ) { ??? /* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */ ??? pxItem->pvContainer = NULL; } |
4.2.2 实现链表根节点
4.2.2.1 list.h
| /* 链表精简数据类型定义 */ struct xMINI_LIST_TTEM { ??? TickType_t xItemValue; ??? struct xLIST_ITEM * pxNext; ??? struct xLIST_ITEM * pxPrevious; }; typedef struct xMINI_LIST_TTEM MiniListItem_t; /* 双向链表根节点数据类型定义 */ struct xLIST { ??? UBaseType_t uxNumberOfItems; /* 链表节点计数器 */ ??? ListItem_t * pxIndex;??????? /* 链表节点索引 */ ??? MiniListItem_t xListEnd;???? /* 链表最后一个节点 */ }; typedef struct xLIST List_t; void vListInitialiseItem( ListItem_t * const pxItem ); void vListInitialise( List_t * const pxList ); |
4.2.2.2 list.c
| /* 双向链表根节点初始化 */ void vListInitialise( List_t * const pxList ) { ??? /* 将链表节点计数器初始化为0，表示链表为空 */ ??? pxList->uxNumberOfItems = ( UBaseType_t ) 0U; ??? ??? /* 将链表索引指向最后一个节点，也可称为第0个节点，不算入节点计数器 */ ??? pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); ??? ??? /* 将链表最后一个节点的辅助排序值设置为最大，确保该节点为链表的最后一个节点 */??? ??? pxList->xListEnd.xItemValue = portMAX_DELAY; ??? ??? /* 将最后一个节点的指针均指向自身，表示链表为空 */??? ??? pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); ??? pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); } |
