FreeRTOS 列表 List 源码解析

2024-08-29 15:28
文章标签 源码 解析 list 列表 freertos

本文主要是介绍FreeRTOS 列表 List 源码解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 一、链表及链表项的定义
    • 1、链表节点数据结构 xList_ITEM
    • 2、链表精简节点结构 xMINI_LIST_ITEM
    • 3、链表根节点结构 xLIST
  • 二、链表的相关操作
    • 1、初始化
      • 1.1 链表节点初始化
      • 1.2 链表根节点初始化
    • 2、插入
      • 2.1 将节点插入到链表的尾部
      • 2.2 将节点按照升序排列插入到链表
    • 3、删除
    • 4、宏函数

链表是 FreeRTOS 的核心数据结构，有关任务调度、延时、阻塞、事件等操作都是通过对链表进行操作进而实现的。本节将详细分析源码文件 list.c，list.h 的内容，为后续的任务队列等的实现奠定基础。

一、链表及链表项的定义

FreeRTOS 使用的链表结构是环形的双向链表，而关于链表节点的数据结构都在 list.h 中定义。

1、链表节点数据结构 xList_ITEM

首先来看链表节点数据结构定义：

struct xLIST_ITEM
{// 第一个和最后一个成员值// 当 configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES 被使能的时候会被设定为一个固定值，用来检验一个列表项数据是否完整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;                                      // 类似侵入式链表，指向包含该链表项的对象的地址，通常是TCB struct xLIST * configLIST_VOLATILE pxContainer;      // 指向该节点所在的链表listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE             
};
typedef struct xLIST_ITEM ListItem_t;

其结构如下：

这里如果使用 configLIST_VOLATILE，其会被替换为 volatile 关键字。

#define configLIST_VOLATILE volatile

volatile 关键字是让编译器不对该变量进行优化，所谓的优化可以理解为其在生成汇编时，若多次读取该变量时其可能会将变量值放入寄存器中以加快读取速度，而不是真正的读取，这使得当某个变量会快速变化时，优化后“读取”的值并不是变量真实的值。当使用 volatile 关键字时，其会强迫编译器每次使用该变量时都真正的对它进行一次读取。

在链表项的结构体构造中值得注意的是 pvOwner 和 pxContainer 这两个成员变量。

  • pvOwner 指向该节点的拥有者，即该节点内嵌在哪个数据结构中，属于哪个数据结构的一个成员。它提供了一种可以快速访问由此链表项代表的对象的方法。
  • pxContainer 用于指向该节点所在的链表，通常指向链表的根节点。它则提供了一种快速访问其所属链表的方法。

这种处理方式大大提高了链表在任务调度等应用中的处理速度，提高系统效率。

侵入式链表


在 Linux 内核中有很多侵入式的链表的设计，比如在 Linux 中提供的链表项的定义为：

struct list_head
{
        struct list_head *next, *prev;
}

使用链表时只需要将其包含进定义的对象中即可：

struct list_head
{
         // 一些其它成员定义....
         struct list_head *next, *prev;
         // 一些其它成员定义....
}

在此它没有定义类似 ListItem_t 中 pxContainer 这样的成员变量，其获得包含该链表项的对象地址是通过下面一段著名的宏定义实现的：

#define offsetof(s,m) (size_t)&(((s *)0)->m
#define container_of(ptr, type, member) \
({ \
         const typeof( ((type *)0)->member ) *__mptr = (ptr); \
         (type *)( (char *)__mptr - offsetof(type,member) ); \
})

使用实例：

struct node test;
struct list_head *list_item_add = &test.list_item;
struct node *test_add = container_of(list_item_add, struct node, list_item);

container_of() 的实现思路简单概括就是：将成员变量地址减去成员变量在结构体类型中的变量便是实例对象的存储地址。以 struct node 结构体为例，其实例 test 在内存中的存储方式如下图左侧所示。下图右侧给出了如何获得成员在结构体存储中的偏移量，当 &test=0x00 时，其成员的地址便是所需要的偏移量。

因此，offsetof() 宏，其所作的事就是获得偏移量。而 container_of() 宏中的：

(type *)( (char *)__mptr - offsetof(type,member) );

便是用成员地址减去偏移量来获得实例的地址。至于 container_of() 宏中的前一句：

const typeof( ((type *)0)->member ) *__mptr = (ptr);

实时上是起到一个类型检验的作用，拓展关键字 typeof 可以获得变量的类型，如果传入的ptr的类型与成员变量类型不符，那么编译器便会抛出警告，便于检查是否出错。注意 typeof 并不是标准 C 中的关键字，如果所用的编译器不支持，可以将第一句删除，将第二句中的__mptr 替换为 ptr，宏 container_of() 仍然是正确的。

2、链表精简节点结构 xMINI_LIST_ITEM

这个结构是专门用来在下面要讲的 xLIST 表示尾节点，相比于刚才讲到的 xList_ITEM 要精简不少。

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;

3、链表根节点结构 xLIST

typedef struct xLIST
{listFIRST_LIST_INTEGRITY_CHECK_VALUE       // 校验值volatile UBaseType_t uxNumberOfItems;      // 记录该链表里有多少成员（根节点除外）ListItem_t * configLIST_VOLATILE pxIndex;  // 链表节点索引指针MiniListItem_t xListEnd;                   // 链表尾部（实际也是链表的第一个节点），为节省内存使用Mini 链表项listSECOND_LIST_INTEGRITY_CHECK_VALUE      // 校验值
} List_t;

结构图如下：



现在清楚了 List 的基本结构，下面是它的相关操作。

二、链表的相关操作

关于链表的相关操作函数的在 list.c 中实现。

1、初始化

1.1 链表节点初始化

void vListInitialiseItem( ListItem_t * const pxItem )
{/* Make sure the list item is not recorded as being on a list. */pxItem->pxContainer = NULL;/* Write known values into the list item if* configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}

链表项的初始化十分简单只是将 pxContainer 置为NULL，设置一下校验值。

一个初始化好的节点示意图具体如下：
在这里插入图片描述

1.2 链表根节点初始化

void vListInitialise( List_t * const pxList )
{/* 将链表索引指针指向最后一个节点 */pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /* 将链表最后一个节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点 */pxList->xListEnd.xItemValue = portMAX_DELAY;/* 将最后一个节点的pxNext 和pxPrevious 指针均指向节点自身，表示链表为空 */pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );     pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/* 将链表项数目设为0 */pxList->uxNumberOfItems = ( UBaseType_t ) 0U;/* 写入校验值，用于后续检验，为了保证链表结构体是正确的，没有被覆写 */listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}

2、插入

2.1 将节点插入到链表的尾部

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 );/* 将链表项嵌入到pxIndex 指向的链表项前 */pxNewListItem->pxNext = pxIndex;                   // 1pxNewListItem->pxPrevious = pxIndex->pxPrevious;   // 2/* 调试测试用的函数，对代码逻辑理解无影响。 */mtCOVERAGE_TEST_DELAY();pxIndex->pxPrevious->pxNext = pxNewListItem;       // 3pxIndex->pxPrevious = pxNewListItem;               // 4/* 记录链表项属于该链表 */pxNewListItem->pxContainer = pxList;               // 5/* 记录链表中的链表项数目 */( pxList->uxNumberOfItems )++;                     // 6
}

代码整体不难理解，主要是弄明白插入的过程中更改指针的指向：

2.2 将节点按照升序排列插入到链表

将节点按照升序排列插入到链表，如果有两个节点的值相同，则新节点在旧节点的后面插入：

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 );/* 寻找插入位置 */if( xValueOfInsertion == portMAX_DELAY ){// 如果链表项的排序数最大，直接在尾部插入，这里相当于做了一个小小的优化。pxIterator = pxList->xListEnd.pxPrevious;}else{/* 升序寻找插入位置 */for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; 			pxIterator = pxIterator->pxNext ) {/* 空操作 */}}/* 进行插入操作 */pxNewListItem->pxNext = pxIterator->pxNext;         // 1pxNewListItem->pxNext->pxPrevious = pxNewListItem;  // 2pxNewListItem->pxPrevious = pxIterator;				// 3pxIterator->pxNext = pxNewListItem;					// 4/* 记录链表项属于该链表 */pxNewListItem->pxContainer = pxList;				// 5/* 记录链表中的链表项数目 */( pxList->uxNumberOfItems )++;						// 6
}

vListInsert() 的实现比起 vListInsertEnd() 也就多了要先查找插入位置再进行插入操作。

在这里插入图片描述

3、删除

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();}/* 移除的链表项不再被链表拥有 */pxItemToRemove->pxContainer = NULL;/* 减少链表项数目 */( pxList->uxNumberOfItems )--;return pxList->uxNumberOfItems;
}

4、宏函数

在 list.h 中，还定义了各种各样的带参宏，方便对节点做一些简单的操作。

/* 初始化节点的拥有者 */
#define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )    ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )
/* 获取节点拥有者 */
#define listGET_LIST_ITEM_OWNER( pxListItem )             ( ( pxListItem )->pvOwner )/* 初始化节点排序辅助值 */
#define listSET_LIST_ITEM_VALUE( pxListItem, xValue )     ( ( pxListItem )->xItemValue = ( xValue ) )
/* 获取节点排序辅助值 */
#define listGET_LIST_ITEM_VALUE( pxListItem )             ( ( pxListItem )->xItemValue )/* 获取链表根节点的节点计数器的值 */
#define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )        ( ( ( pxList )->xListEnd ).pxNext->xItemValue )/* 获取链表的入口节点 */
#define listGET_HEAD_ENTRY( pxList )                      ( ( ( pxList )->xListEnd ).pxNext )
/* 获取节点的下一个节点 */
#define listGET_NEXT( pxListItem )                        ( ( pxListItem )->pxNext )
/* 获取链表的最后一个节点 */
#define listGET_END_MARKER( pxList )                      ( ( ListItem_t const * ) ( &( ( pxList )->xListEnd ) ) )/* 判断链表是否为空 */
#define listLIST_IS_EMPTY( pxList )                       ( ( ( pxList )->uxNumberOfItems == ( UBaseType_t ) 0 ) ? pdTRUE : pdFALSE )/* 获取链表的节点数 */
#define listCURRENT_LIST_LENGTH( pxList )                 ( ( pxList )->uxNumberOfItems )/* 获取链表第一个节点的OWNER，即TCB */
#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                           \{                                                                                          \List_t * const pxConstList = ( pxList );                                               \/* Increment the index to the next item and return the item, ensuring */               \/* we don't return the marker used at the end of the list.  */                         \( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                           \if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) \{                                                                                      \( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                       \}                                                                                      \( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                         \}/* 获取第一个列表项所属的链表 */
#define listGET_OWNER_OF_HEAD_ENTRY( pxList )            ( ( &( ( pxList )->xListEnd ) )->pxNext->pvOwner )/* 判断给定 pxListItem 是否属于 pxList */
#define listIS_CONTAINED_WITHIN( pxList, pxListItem )    ( ( ( pxListItem )->pxContainer == ( pxList ) ) ? ( pdTRUE ) : ( pdFALSE ) )/* 判断节点是否属于某个链表 */
#define listLIST_ITEM_CONTAINER( pxListItem )            ( ( pxListItem )->pxContainer )/* 判断链表是否已初始化 */
#define listLIST_IS_INITIALISED( pxList )                ( ( pxList )->xListEnd.xItemValue == portMAX_DELAY )

这篇关于FreeRTOS 列表 List 源码解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1118243。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...
如何在Visual Studio中调试.NET源码

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时，发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null，再判断Count。 看了一下Count的源码如下： 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get
阅读更多...
工厂ERP管理系统实现源码（JAVA）

工厂ERP管理系统实现源码（JAVA）

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本，并实时掌握各环节的运营状况。 在采购管理方面，系统能够处理采购订单、供应商管理和采购入库等流程，确保采购过程的透明和高效。仓库管理方面，实现库存的精准管理，包括入库、出库、盘点等操作，确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、
阅读更多...
c++的初始化列表与const成员

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量，在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员，因为执行构造函数时，类对象已经创建完成，只有类对象创建完成才能调用成员函数，构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化，该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面，主要用于给
阅读更多...
OWASP十大安全漏洞解析

OWASP十大安全漏洞解析

OWASP（开放式Web应用程序安全项目）发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南，它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析： 1. 注入漏洞（Injection） 描述：攻击者通过在应用程序的输入数据中插入恶意代码，从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响：可能导致数据泄
阅读更多...
从状态管理到性能优化：全面解析 Android Compose

从状态管理到性能优化：全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动
阅读更多...
Spring 源码解读：自定义实现Bean定义的注册与解析

Spring 源码解读：自定义实现Bean定义的注册与解析

引言 在Spring框架中，Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义，Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制，帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry，以全面掌握Bean注册和解析的核心原理。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2