FreeRTOS学习——链表list

devtools/2024/11/12 21:52:21/

FreeRTOS学习——链表（列表）list，仅用于记录自己阅读与学习源码

FreeRTOS Kernel V10.5.1

参考大佬的好文章：
freertos内核原理 Day1(链表)
FreeRTOS-链表的源码解析

*list_t只能存储指向list_item_t的指针。每个list_item_t都包含一个数值（xItemValue）。大多数时候，列表是按项目值升序排列的。

*创建的列表已包含一个列表项。此项的值是可以存储的最大值，因此它始终位于列表的末尾，并充当标记。列表成员pxHead始终指向此标记，即使它位于列表的末尾。这是因为尾部包含一个返回指针，指向列表的真正头部。

*除了它的值外，每个列表项还包含一个指向列表中下一个项的指针（pxNext）、一个指向它所在列表的指针（pxContainer）和一个指向包含它的对象的指针。为了提高列表操作的效率，包含了后两个指针。包含列表项的对象和列表项本身之间实际上存在双向链接。

链表结构体

关于链表的结构体，有三个，分别是

1. 节点结构体
2. 尾节点结构体(mini节点）
3. 链表结构体

可以看大佬的博客freertos内核原理 Day1(链表)，非常清晰

节点结构体 ListItem_t

/** 列表可以包含的唯一对象类型的定义*/
struct xLIST_ITEM
{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE           /*< 链表节点完整性检查值1 */configLIST_VOLATILE TickType_t xItemValue;          /*< 链表节点值，用于阻塞升序排序 */struct xLIST_ITEM * configLIST_VOLATILE pxNext;     /*< 指向链表中的下一个节点 */struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*< 指向链表中的上一个节点 */void * pvOwner;                                     /*< 指向拥有该链表节点的对象 (一般是TCB) . */struct xLIST * configLIST_VOLATILE pxContainer;     /*< 指向节点所在的链表. */listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE          /*< 链表节点完整性检查值2. */
};
typedef struct xLIST_ITEM ListItem_t;

若宏configLIST_VOLATILE定义为空，且若完整性检查宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES也为0的话（见下面关于链表宏部分），那么这个链表节点结构体其实就长这个样子，一下子干净多了。

struct xLIST_ITEM
{TickType_t xItemValue;          /*< 链表节点值，用于阻塞升序排序 */struct xLIST_ITEM * pxNext;     /*< 指向链表中的下一个节点 */struct xLIST_ITEM * pxPrevious; /*< 指向链表中的上一个节点 */void * pvOwner;                 /*< 指向拥有该链表节点的对象 (一般是TCB) . */struct xLIST * pxContainer;     /*< 指向节点所在的链表. */
};
typedef struct xLIST_ITEM ListItem_t;

链表节点值TickType_t xItemValue;为什么是TickType_t 类型呢，阻塞时间就是多少个TickType_t ，这个值用于插入延迟列表时，将节点从低到高的排列，阻塞时间段的在最前面，只要前面的没有唤醒，那么后面的也一定在阻塞，因为是升序排列的。

尾节点结构体(mini节点） MiniListItem_t

#if ( configUSE_MINI_LIST_ITEM == 1 )struct xMINI_LIST_ITEM{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< 链表节点完整性检查值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;
#elsetypedef struct xLIST_ITEM      MiniListItem_t;
#endif

如果宏configUSE_MINI_LIST_ITEM 为1 ，则定义xMINI_LIST_ITEM 为MiniListItem_t，否则就把普通节点xLIST_ITEM定义为尾节点。

与普通节点相比，尾节点结构体少了pvOwner和pxContainer

链表结构体（根节点） List_t

/** 调度器使用的队列类型的定义*/
typedef struct xLIST
{listFIRST_LIST_INTEGRITY_CHECK_VALUE      /*< 链表完整性检查值1 */volatile UBaseType_t uxNumberOfItems;ListItem_t * configLIST_VOLATILE pxIndex; /*< 索引指针，通过调用listGET_OWNER_OF_NEXT_ENTRY ()来遍历链表的指针 */MiniListItem_t xListEnd;                  /*< 尾节点拥有最大的xItemValue值. */listSECOND_LIST_INTEGRITY_CHECK_VALUE     /*< 链表完整性检查值2 */
} List_t;

注意，尾节点结构体MiniListItem_t 和链表结构体List_t并不是链表连接起来的，而是MiniListItem_t 是List_t的一部分，可以把List_t想象成一个大东西，而这个大东西 在链表的尾部，也可以说在头尾，因为是双向链表。List_t通过MiniListItem_t 链接起整个链表，只要获取了List_t，就能一节一节的获取整个链表，List_t也可以叫做根节点。

链表操作

初始化链表 vListInitialise

void vListInitialise( List_t * const pxList )
{/* 将索引指针指向尾节点 */pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*尾节点xListEnd使用mini节点结构体，节省RAM *//*给尾节点完整性检查值 赋值，尾节点只有一个完整性检查值 */listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );/* 尾节点值为最大值0xffffffffUL，确保其为最后一个节点*/pxList->xListEnd.xItemValue = portMAX_DELAY;/* 当链表为空时，尾节点的前后指针指向尾节点自己 */pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );     pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); /* 如果尾节点没有使用mini节点结构体，则初始化其pvOwner和pxContainer指针 */#if ( configUSE_MINI_LIST_ITEM == 0 ){pxList->xListEnd.pvOwner = NULL;pxList->xListEnd.pxContainer = NULL;listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );}#endif/*节点数量为0*/pxList->uxNumberOfItems = ( UBaseType_t ) 0U;/* 给链表完整性检查值 赋值 */listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}
  1. 链表索引指针指向尾节点
  2. 尾节点值设为最大值，且前后指针都指向自己
  3. 节点数量为0

初始化链表节点 vListInitialiseItem

void vListInitialiseItem( ListItem_t * const pxItem )
{/* pxContainer指该节点属于哪个链表，初始值为NULL，确保该节点没有在任何链表中. */pxItem->pxContainer = NULL;/* 给节点完整性检查值 赋值. */listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}

链表尾部插入节点 vListInsertEnd

void vListInsertEnd( List_t * const pxList,ListItem_t * const pxNewListItem )
{ListItem_t * const pxIndex = pxList->pxIndex;/* 完整性检查，可以检查链表结构体在内存中是否被重写 */listTEST_LIST_INTEGRITY( pxList );listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );/* 将新节点 pxNewListItem 插入到 pxIndex 之前  */pxNewListItem->pxNext = pxIndex;pxNewListItem->pxPrevious = pxIndex->pxPrevious;/* 覆盖率测试，不影响功能，仅用于覆盖率测试 */mtCOVERAGE_TEST_DELAY();pxIndex->pxPrevious->pxNext = pxNewListItem;pxIndex->pxPrevious = pxNewListItem;/* 将节点的pxContainer指针指向链表 */pxNewListItem->pxContainer = pxList;/*链表节点数量加1*/( pxList->uxNumberOfItems )++;
}
  1. 将新节点 pxNewListItem 插入到 pxIndex 之前
  2. 将节点的pxContainer指针指向链表
  3. 链表节点数量加1

链表插入节点 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 );/* 将新的列表项插入列表，按xItemValue顺序排序* 如果节点值是最大值，则插入到尾节点之前*/if( xValueOfInsertion == portMAX_DELAY ){pxIterator = pxList->xListEnd.pxPrevious;}else{/* *** NOTE ************************************************************  如果程序崩溃，可能原因如下：**   1) 栈溢出*   2) 优先级分配错误*   3) 从关键部分或当调度程序暂停时调用API函数，或从中断调用不以“FromISR”结尾的API函数*   4) 在队列或信号量初始化之前 或 调度程序启动之前使用它（中断是在vTaskStartScheduler（）被调用之前触发的吗？）*   5) 果FreeRTOS端口支持中断嵌套，则确保滴答中断的优先级等于或低于configMAX_SYSCALLINTERRUPT_priority**********************************************************************/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;/* 将新节点的pxContainer指针指向链表 */pxNewListItem->pxContainer = pxList;/*链表节点数量加1*/( pxList->uxNumberOfItems )++;
}
  1. 确认要插入的位置，如果节点值是最大值，则插入到尾节点之前，否则遍历链表
  2. 插入新节点
  3. 将新节点的pxContainer指针指向链表
  4. 链表节点数量加1

从链表移除节点 uxListRemove

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{/* 获取节点所在的链表 */List_t * const pxList = pxItemToRemove->pxContainer;/*将节点从链表中移除*/pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;/* 覆盖率测试，不影响功能，仅用于覆盖率测试 */mtCOVERAGE_TEST_DELAY();/* 确保索引指针指向有效的节点 */if( pxList->pxIndex == pxItemToRemove ){pxList->pxIndex = pxItemToRemove->pxPrevious;}else{/*覆盖率测试，不影响功能，仅用于覆盖率测试*/mtCOVERAGE_TEST_MARKER();}/* 将节点的pxContainer指针指向NULL */pxItemToRemove->pxContainer = NULL;/*链表节点数量减 1*/( pxList->uxNumberOfItems )--;/*返回链表中剩余节点数量*/return pxList->uxNumberOfItems;
}
  1. 将节点从链表中移除
  2. 将节点的pxContainer指针指向NULL
  3. 链表节点数量减 1并返回链表中剩余节点数量

链表宏

configLIST_VOLATILE

*列表结构成员是在中断内修改的，因此应该声明为volatile。然而，它们只能以功能原子的方式进行修改（在调度器挂起的关键部分内），并且要么通过引用传递到函数中，要么通过volatile变量进行索引。因此，在迄今为止测试的所有用例中，可以省略volatile限定符，以便在不影响功能行为的情况下提供适度的性能改进。IAR、ARM和GCC编译器在为最大优化设置相应编译器选项时生成的汇编指令已经过检查，并被认为符合预期。也就是说，随着编译器技术的进步，特别是如果使用了激进的跨模块优化（一个没有得到很大程度应用的用例），那么正确的优化就可能需要volatile限定符。预计编译器会删除基本代码，因为如果列表结构成员上没有volatile限定符，并且进行了积极的跨模块优化，编译器认为代码是不必要的，这将导致调度器完全和明显的失败。如果遇到这种情况，那么只需在FreeRTOSConfig.h中将configLIST_volatile定义为volatile，就可以将volatile限定符插入列表结构中的相关位置（如本注释块底部的示例所示）。如果未定义configLIST_VOLATILE，则下面的预处理器指令将完全#define configLIST_VOLATILE。

*要使用volatile列表结构成员，请在FreeRTOSConfig.h中添加以下行（不带引号）：“#define configLIST_volatile volatile”

#ifndef configLIST_VOLATILE#define configLIST_VOLATILE
#endif /* configSUPPORT_CROSS_MODULE_OPTIMISATION */

简单点说就是在迄今为止测试的所有用例中，可以省略volatile。但是如果使用了激进的跨模块优化，就可能需要volatile限定符，那么就在FreeRTOSConfig.h中添加：“#define configLIST_volatile volatile”。

现在configLIST_VOLATILE是定义为空的，因为volatile可以省略。

configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES

可用于在列表结构中放置已知值的宏，然后检查已知值在应用程序执行过程中是否损坏。这些可能会捕获内存中被覆盖的列表数据结构。它们不会捕获因FreeRTOS配置或使用不正确而导致的数据错误
在这里插入图片描述
在FreeRTOS中，这段宏定义与列表数据完整性检查相关。具体来说，它们的作用是根据configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES宏的值决定是否启用数据完整性检查功能。
（默认为0，即不开启）

当configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES被设置为0时，这段代码通过定义一系列宏为空操作（即不执行任何操作），来关闭列表数据的完整性检查功能。这意味着在使用列表数据结构时，系统不会进行额外的完整性校验，这样可以降低运行时的开销，适用于对性能要求较高的场景。

这些宏的具体定义如下：

*listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE ：列表节点完整检查值1
*listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE：列表节点完整检查值2。
这两个用于表示列表节点完整性检查的值，若不启用则为空。若启用了会在列表节点结构体中添加
TickType_t xListItemIntegrityValue1;
和TickType_t xListItemIntegrityValue2;

*listFIRST_LIST_INTEGRITY_CHECK_VALUE ：列表完整检查值1
*listSECOND_LIST_INTEGRITY_CHECK_VALUE：列表完整检查值2
同上面两个值类似，用于表示整个列表的完整性检查值，同样不启用时为空。

*listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem)：赋值列表节点完整性检查值1
*listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem)：
它会赋值列表节点中的xListItemIntegrityValue为定义的值#define pdINTEGRITY_CHECK_VALUE 0x5a5a5a5aUL

*listSET_LIST_INTEGRITY_CHECK_1_VALUE(pxList) ：赋值列表完整性检查值1
*listSET_LIST_INTEGRITY_CHECK_2_VALUE(pxList)：
同上面两个值类似

*listTEST_LIST_ITEM_INTEGRITY(pxItem)：用于测试列表节点的完整性
*listTEST_LIST_INTEGRITY(pxList)：用于测试整个列表的完整性
上面的宏不是已经幅过值了吗，那么这两个宏就是检查上面的值有没有发生变化

总之，这些宏确保在不需要数据完整性检查时，代码的执行不会受影响，从而提高系统的性能。同时，若需要进行完整性检查（即configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为非零值），这些宏可以被重新定义，以执行必要的检查逻辑。这样的设计使得FreeRTOS能够灵活地在不同的应用场景中进行配置。

listGET_OWNER_OF_NEXT_ENTRY_338">listGET_OWNER_OF_NEXT_ENTRY

/** 链表成员pxIndex用于遍历列表* 调用listGET_OWNER_OF_NEXT_ENTRY会将pxIndex递增到列表中的下一个节点，并返回该节点的拥有者pxOwner（一般是TCB）。* 因此，通过多次调用此函数，可以遍历列表中包含的每个项目。* 列表项的pxOwner参数是指向拥有该列表项的对象的指针。在调度器中，这通常是一个任务控制块。*/
#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                           \{                                                                                          \List_t * const pxConstList = ( pxList );                                               \/* 链表索引pxIndex指向下一个节点*/               \/* 确保不返回尾节点  */                         \( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                           \if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) \{                                                                                      \( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                       \}                                                                                      \( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                         \}

listREMOVE_ITEM_361">listREMOVE_ITEM

/** 删除节点* 不返回值的uxListRemove（）的版本。通过内联对xTaskIncrementTick（）进行了轻微优化*/
#define listREMOVE_ITEM( pxItemToRemove ) \{                                     \/* 获取节点所在的链表 */                                                              \List_t * const pxList = ( pxItemToRemove )->pxContainer;                 \\( pxItemToRemove )->pxNext->pxPrevious = ( pxItemToRemove )->pxPrevious; \( pxItemToRemove )->pxPrevious->pxNext = ( pxItemToRemove )->pxNext;     \/* 确保索引指针指向正确的节点 */              \if( pxList->pxIndex == ( pxItemToRemove ) )                              \{                                                                        \pxList->pxIndex = ( pxItemToRemove )->pxPrevious;                    \}                                                                        \\( pxItemToRemove )->pxContainer = NULL;                                  \( pxList->uxNumberOfItems )--;                                           \}

listINSERT_END_386">listINSERT_END

/** 内联版本vListInsertEnd()对xTaskIncrementTick()进行了轻微优化.** 通过多次调用listGET_OWNER_OF_NEXT_ENTRY.确保插入的节点位于最后一个节点** 列表成员pxIndex用于遍历列表，调用listGET_OWNER_OF_NEXT_ENTRY会将pxIndex递增到列表中的下一个节点。* 使用vListInsertEnd将节点有效地放置在pxIndex指向的列表位置。* 这意味着在pxIndex参数再次指向要插入的项之前，列表中的所有其他项都将由listGET_OWNER_OF_NEXT_ENTRY返回。*/
#define listINSERT_END( pxList, pxNewListItem )           \{                                                     \ListItem_t * const pxIndex = ( pxList )->pxIndex; \\/* 链表完整性检查 */                                 \listTEST_LIST_INTEGRITY( ( pxList ) );                                  \listTEST_LIST_ITEM_INTEGRITY( ( pxNewListItem ) );                      \\/* 通过调用listGET_OWNER_OF_NEXT_ENTRY(). 确保插入的节点位于最后一个节点*/     \( pxNewListItem )->pxNext = pxIndex;                 \( pxNewListItem )->pxPrevious = pxIndex->pxPrevious; \\pxIndex->pxPrevious->pxNext = ( pxNewListItem );     \pxIndex->pxPrevious = ( pxNewListItem );             \\/* 将节点的pxContainer指针指向链表 */                    \( pxNewListItem )->pxContainer = ( pxList );         \\( ( pxList )->uxNumberOfItems )++;                   \}

http://www.ppmy.cn/devtools/113163.html

相关文章

《并发之危：错误实现的并发数据结构如何“摧毁”程序》

《并发之危：错误实现的并发数据结构如何“摧毁”程序》

在当今的软件开发领域&#xff0c;并发编程已经成为了一个不可或缺的部分。随着多核处理器的普及和软件系统规模的不断扩大&#xff0c;开发人员越来越多地需要利用并发来提高程序的性能和响应能力。而在并发编程中&#xff0c;并发数据结构的正确实现至关重要。一旦并发数据结…
阅读更多...
TI DSP下载器XDS100 V2.0无法使用问题

TI DSP下载器XDS100 V2.0无法使用问题

前言 TI DSP下载器XDS100 V2.0用着用着会突然报Error&#xff0c;特别是你想要用Code Composer Studio烧录下载程序的时候 查看设备管理器&#xff0c;发现XDS100 V2.0的设备端口莫名其妙消失了 问了淘宝的厂家&#xff0c;他说TI的开发板信号可能会导致调试器通信信号中断&a…
阅读更多...
gcc编译器详解

gcc编译器详解

目录 GCC编译器详解gcc的编译流程gcc编译细节静态库&#xff08;gcc多个文件链接&#xff09;动态库 GCC编译器详解 因为后面我需要用到Makefile来管理文件&#xff0c;因此不得不先学习一下gcc的使用 &#xff0c;下面是一些具体的使用方法 gcc的编译流程 gcc编译的时候对应…
阅读更多...
SQLite的入门级项目学习记录（一）

SQLite的入门级项目学习记录（一）

从来没有接触过数据库&#xff0c;但是最近有个项目要用到&#xff0c;从0开始记录一下学习的过程&#xff0c;以备忘。 python常见的几个免费数据库 在 Python 中&#xff0c;有几个流行的免费数据库选项&#xff0c;可以根据项目需求选择使用。以下是一些常见的免费…
阅读更多...
模拟面试后端开发复盘

模拟面试后端开发复盘

目录 一&#xff1a;项目的系统开发和设计思路 二&#xff1a;Java的反射是什么&#xff1f;在项目中有用到吗&#xff1f; 三&#xff1a;多态的实现原理 四&#xff1a;项目中的redis是用在了哪里 五&#xff1a;Session和Cookie的区别&#xff0c;Cookie可以被修改吗&a…
阅读更多...
JAVA算法数据结构第一节稀疏矩阵

JAVA算法数据结构第一节稀疏矩阵

一、稀疏矩阵介绍&#xff1a; 稀疏矩阵是一种特殊类型的矩阵&#xff0c;其中大部分元素都是零。在处理这类矩阵时&#xff0c;如果仍然使用标准的矩阵存储方式&#xff08;即传统的二维数组&#xff09;&#xff0c;则会浪费大量的存储空间来保存零值。为了提高存储效率以及…
阅读更多...
DAY20240909 VUE:编程式导航，动态路由，命名路由

DAY20240909 VUE:编程式导航，动态路由，命名路由

VUE:编程式导航&#xff0c;动态路由&#xff0c;命名路由 一、点击‘正在热映’列表能跳到对应详情1编程式导航创建新组件---详情Datail.vue组件模拟正在热映电影 列表页面为Datail.vue组件 配置路由、引入路由使用vue里的编程式导航方案实现点击列表跳转detail页面里 2动态路…
阅读更多...
MATLAB 从 R2024B 开始支持树莓派 5

MATLAB 从 R2024B 开始支持树莓派 5

树莓派&#xff08;Raspberry Pi&#xff09;系列是一系列基于单板计算机的微型电脑&#xff0c;由英国的树莓派基金会于 2012 年开始发布。它的目标是提供一个低成本、易于学习和玩耍的平台&#xff0c;用于教育和初学者学习计算机科学和编程。 目前市面上&#xff0c;最新最…
阅读更多...
最新文章

Copyright @ 2022~2023