第6章 数据结构—列表与列表项讲解--总结

整理 野火 《FreeRTOS 内核实现与应用开发实战指南》—基于野火 STM32 全系列（M3/4/7）开发板

文章目录

  • 第6章 数据结构—列表与列表项讲解--总结
    • 6.1 C 语言链表简介
      • 6.1.1 单向链表
      • 6.1.2 双向链表
      • 6.1.3 链表与数组的对比
    • 6.2 FreeRTOS 中链表的实现
      • 6.2.1 实现链表节点
        • 1. 定义链表节点数据结构
        • 2. 链表节点初始化
      • 6.2.2 实现链表根节点
        • 1. 定义链表根节点数据结构
        • 2. 链表根节点初始化
          • `索引节点的补充：`
        • 3. 将节点插入到链表的尾部
        • 4. 将节点按照升序排列插入到链表
        • 5. 将节点从链表删除
        • 6. 节点带参宏小函数

第6章 数据结构—列表与列表项讲解–总结

  列表和列表项是直接从 FreeRTOS 源码的注释中的 list 和 list item 翻译过来的，其实就是对应我们 C 语言当中的链表和节点，在后续的讲解中，我们说的链表就是列表，节点就是列表项。

6.1 C 语言链表简介

  链表作为 C 语言中一种基础的数据结构，在平时写程序的时候用的并不多，但在操作系统里面使用的非常多。链表就好比一个圆形的晾衣架，具体见图 6-1，晾衣架上面有很多钩子，钩子首尾相连。链表也是，链表由节点组成，节点与节点之间首尾相连。
在这里插入图片描述

图 6-1 圆形晾衣架

6.1.1 单向链表

在这里插入图片描述

6.1.2 双向链表

在这里插入图片描述

6.1.3 链表与数组的对比

在这里插入图片描述
总结：
  链表是通过节点把离散的数据链接成一个表，通过对节点的插入和删除操作从而实现对数据的存取。而数组是通过开辟一段连续的内存来存储数据，这是数组和链表最大的区别。数组的每个成员对应链表的节点，成员和节点的数据类型可以是标准的 C 类型或者是用户自定义的结构体。数组有起始地址和结束地址，而链表是一个圈，没有头和尾之分，但是为了方便节点的插入和删除操作会人为的规定一个根节点。

6.2 FreeRTOS 中链表的实现

  FreeRTOS 中与链表相关的操作均在 list.h 和 list.c 这两个文件中实现。

6.2.1 实现链表节点

1. 定义链表节点数据结构
/* 节点结构体定义 */
struct xLIST_ITEM
{
	TickType_t xItemValue;             /* 辅助值，用于帮助节点做顺序排列 */			
	struct xLIST_ITEM *  pxNext;       /* 指向链表下一个节点 */		
	struct xLIST_ITEM *  pxPrevious;   /* 指向链表前一个节点 */	
	void * pvOwner;					   /* 指向拥有该节点的内核对象，通常是TCB */
	void *  pvContainer;		       /* 指向该节点所在的链表 */
};
typedef struct xLIST_ITEM ListItem_t;  /* 节点数据类型重定义 */

在这里插入图片描述

2. 链表节点初始化

  链表节点初始化函数在 list.c 中实现

/* 节点初始化 */
void vListInitialiseItem( ListItem_t * const pxItem )
{
	/* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
	pxItem->pvContainer = NULL;
}

6.2.2 实现链表根节点

1. 定义链表根节点数据结构
/* 链表结构体定义 */
typedef struct xLIST
{
	UBaseType_t uxNumberOfItems;    /* 链表节点计数器 */
	ListItem_t *  pxIndex;			/* 链表节点索引指针 */
	MiniListItem_t xListEnd;		/* 链表最后一个节点 */
} List_t;

在这里插入图片描述

/* mini节点结构体定义，作为双向链表的结尾
   因为双向链表是首尾相连的，头即是尾，尾即是头 */
struct xMINI_LIST_ITEM
{
	TickType_t xItemValue;                      /* 辅助值，用于帮助节点做升序排列 */
	struct xLIST_ITEM *  pxNext;                /* 指向链表下一个节点 */
	struct xLIST_ITEM *  pxPrevious;            /* 指向链表前一个节点 */
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;  /* 最小节点数据类型重定义 */
2. 链表根节点初始化
/* 链表初始化 */
void vListInitialise( List_t * const pxList )
{
	/* 将链表索引指针指向最后一个节点 */ //pxIndex 是链表的索引节点，它始终指向链表的“结束节点”
	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;
}
索引节点的补充：

  在 FreeRTOS 中，链表的索引节点（pxIndex）并不始终指向最后一个节点，而是始终指向一个特殊的“结束节点”（NULL节点）。这个结束节点是链表的一个固定部分，用于简化链表操作的逻辑。
  关于结束节点的作用：

  • 简化插入操作：通过将结束节点作为链表的固定终点，可以避免在插入新节点时对链表尾部进行特殊处理。例如，在上述代码中，新节点的下一个指针直接指向结束节点，而结束节点的上一个节点的下一个指针指向新节点，从而实现了尾部插入。
  • 简化遍历操作：结束节点的存在使得链表的遍历更加统一。遍历链表时，只需要检查当前节点是否为结束节点即可，而无需单独处理链表为空或到达尾部的情况。
  • 统一链表结构：无论链表是否为空，结束节点始终存在，使得链表的结构保持一致。空链表时，结束节点的上一个节点和下一个节点都指向自己。

在这里插入图片描述

3. 将节点插入到链表的尾部
/*
 * 将节点插入到链表的尾部
 * 
 * 参数:
 *   pxList: 指向链表的指针
 *   pxNewListItem: 指向要插入的新节点的指针
 */
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
    //pxIndex 是链表的索引节点，它始终指向链表的“结束节点”
    ListItem_t * const pxIndex = pxList->pxIndex;

    // 将新节点的下一个指针指向索引节点
    pxNewListItem->pxNext = pxIndex;
    // 将新节点的上一个指针指向索引节点的上一个节点
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;
    // 将索引节点的上一个节点的下一个指针指向新节点
    pxIndex->pxPrevious->pxNext = pxNewListItem;
    // 将索引节点的上一个指针指向新节点
    pxIndex->pxPrevious = pxNewListItem;

    /* 记住该节点所在的链表 */
    pxNewListItem->pvContainer = ( void * ) pxList;

    /* 链表节点计数器++ */
    ( pxList->uxNumberOfItems )++;
}
4. 将节点按照升序排列插入到链表

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

/*
 * 将节点按照升序排列插入到链表
 * 
 * 参数:
 *   pxList: 指向链表的指针
 *   pxNewListItem: 指向要插入的新节点的指针
 */
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
    // 声明一个指向 ListItem_t 类型的指针 pxIterator，用于遍历链表
    ListItem_t *pxIterator;
    
    /* 获取节点的排序辅助值 */
    const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

    /* 节点要插入到链表的尾部 */
    if( xValueOfInsertion == portMAX_DELAY )
    {
        // 如果节点的排序辅助值等于 portMAX_DELAY，则将 pxIterator 指向链表的最后一个节点
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
        // 遍历链表，找到第一个 xItemValue 大于 xValueOfInsertion 的节点
        for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd );
             pxIterator->pxNext->xItemValue <= xValueOfInsertion; 
             pxIterator = pxIterator->pxNext )
        {
            /* 没有事情可做，不断迭代只为了找到节点要插入的位置 */            
        }
    }

    // 将新节点插入到 pxIterator 所指向的节点之后
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;

    /* 记住该节点所在的链表 */
    pxNewListItem->pvContainer = ( void * ) pxList;

    /* 链表节点计数器++ */
    ( pxList->uxNumberOfItems )++;
}
5. 将节点从链表删除
/*
 * 将节点从链表中删除
 * 
 * 参数:
 *   pxItemToRemove: 指向要删除的节点的指针
 * 
 * 返回值:
 *   返回链表中剩余节点的个数
 */
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
    /* 获取节点所在的链表 */
    List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;

    // 将待删除节点的下一个节点的前向指针指向待删除节点的前一个节点
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    // 将待删除节点的前一个节点的后向指针指向待删除节点的下一个节点
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    /* 确保索引指向一个有效节点 */
    if( pxList->pxIndex == pxItemToRemove )
    {
        // 如果索引指向待删除节点，则将索引指向待删除节点的前一个节点
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }

    /* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
    pxItemToRemove->pvContainer = NULL;
    
    /* 链表节点计数器-- */
    ( pxList->uxNumberOfItems )--;

    /* 返回链表中剩余节点的个数 */
    return pxList->uxNumberOfItems;
}
6. 节点带参宏小函数
/* 初始化节点的拥有者 */
#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 )	( ( BaseType_t ) ( ( pxList )->uxNumberOfItems == ( UBaseType_t ) 0 ) )

/* 获取链表的节点数 */
#define listCURRENT_LIST_LENGTH( pxList )	( ( pxList )->uxNumberOfItems )

/* 获取链表节点的OWNER，即TCB */
#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )										\
{																							\
	List_t * const pxConstList = ( pxList );											    \
	/* 节点索引指向链表第一个节点调整节点索引指针，指向下一个节点，                               \
    如果当前链表有N个节点，当第N次调用该函数时，pxInedex则指向第N个节点 */                       \
	( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;							\
	/* 当前链表为空 */                                                                       \
	if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )	\
	{																						\
		( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;						\
	}																						\
	/* 获取节点的OWNER，即TCB */                                                             \
	( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;											 \
}

#define listGET_OWNER_OF_HEAD_ENTRY( pxList )  ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner )

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/959351.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

强化学习-Deep Q Network

强化学习-Deep Q Network

文章目录 Deep Q Networkzip(*batch)的内部实现假设&#xff1a;结果&#xff1a; Deep Q Network 这种方式很适合格子游戏。因为格子游戏中的每一个格子就是一个状态&#xff0c;这是离散的&#xff0c;但在现实生活中&#xff0c;很多状态并不是离散而是连续的。所以我们可以…
阅读更多...
C语言-构造数据类型

C语言-构造数据类型

1、构造数据类型 结构体、共用体、枚举。 2、结构体 1、结构体的定义 结构体是一个自定义的复合数据类型&#xff0c;它允许将不同类型的数据组合在一起。 struct 结构体名 {数据类型1 成员变量1;数据类型2 成员变量2;数据类型3 成员变量3;数据类型4 成员变量4; } 2、结构体变…
阅读更多...
FPGA实现任意角度视频旋转（二）视频90度/270度无裁剪旋转

FPGA实现任意角度视频旋转（二）视频90度/270度无裁剪旋转

本文主要介绍如何基于FPGA实现视频的90度/270度无裁剪旋转&#xff0c;旋转效果示意图如下&#xff1a; 为了实时对比旋转效果&#xff0c;采用分屏显示进行处理&#xff0c;左边代表旋转前的视频在屏幕中的位置&#xff0c;右边代表旋转后的视频在屏幕中的位置。 分屏显示的…
阅读更多...
Spark/Kafka

Spark/Kafka

文章目录 项目地址一、Spark1. RDD1.1 五大核心属性1.2 执行原理1.3 四种创建方式二、Kafka2.1 生产者（1）分区器（2）生产者提高吞吐量（3） 生产者数据可靠性数据传递语义幂等性和事务数据有序2.2 Broker（1）Broker工作流程（2）节点服役和退役2.3 副本（1）Follower故障细…
阅读更多...
win32汇编环境,函数的编写与调用、传值或返回值等

win32汇编环境,函数的编写与调用、传值或返回值等

;运行效果 ;win32汇编环境,函数的编写与调用、传值或返回值等 ;函数在被调用的时候&#xff0c;如果此函数实体在前面&#xff0c;可以不用声明。如果实体在后面&#xff0c;则需要先声明。类似于下面的DlgProc函数&#xff0c;因为它的实体在后面&#xff0c;所以需要在调用之…
阅读更多...
[Spring] Gateway详解

[Spring] Gateway详解

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏: &#x1f9ca; Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 &#x1f355; Collection与…
阅读更多...
回顾2024，展望2025

回顾2024，展望2025

项目 LMD performance phase2 今年修修补补&#xff0c;设计和做了很多item&#xff0c;有时候自己都数不清做了什么大大小小的item&#xff0c;但是for LMD performance phase2的go-live确实是最大也是最难的了&#xff0c;无论什么系统&#xff0c;只要用的人多了&#xff…
阅读更多...
旅游风景的代码项目

旅游风景的代码项目

敦煌莫高窟&#xff1a;用代码打开千年艺术的大门 ——一个零基础也能看懂的神奇项目 前言&#xff1a;当古老艺术遇上现代代码 想象一下&#xff0c;你坐在电脑前&#xff0c;指尖轻轻一点&#xff0c;就能穿越到敦煌莫高窟——看飞天的衣袂飘飘、听千年的驼铃声声。这不是科…
阅读更多...
解决lombok注解失效

解决lombok注解失效

问题描述 当出现使用lombok的注解, 但是找不到符号, 或者使用Getter注解却获取不到属性值 就像下面这样 原因: 新版本lombok自动引入了一个插件, 将下面这串代码删除后, 刷新并清除缓存即可解决
阅读更多...
leetcode hot 100 搜索二维矩阵II

leetcode hot 100 搜索二维矩阵II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。每列的元素从上到下升序排列。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,2…
阅读更多...
CentOS7安装使用containerd

CentOS7安装使用containerd

一&#xff0c;安装 1.1、安装containerd 下载 https://github.com/containerd/containerd/releases/download/v1.7.24/cri-containerd-cni-1.7.24-linux-amd64.tar.gz wget https://github.com/containerd/containerd/releases/download/v1.7.24/cri-containerd-cni-1.7.24-…
阅读更多...
easyexcel读取写入excel easyexceldemo

easyexcel读取写入excel easyexceldemo

1.新建springboot项目 2.添加pom依赖 <name>excel</name> <description>excelspringboot例子</description><parent> <groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId&…
阅读更多...
2025数学建模美赛|F题成品论文

2025数学建模美赛|F题成品论文

国家安全政策与网络安全 摘要 随着互联网技术的迅猛发展&#xff0c;网络犯罪问题已成为全球网络安全中的重要研究课题&#xff0c;且网络犯罪的形式和影响日益复杂和严重。本文针对网络犯罪中的问题&#xff0c;基于多元回归分析和差异中的差异&#xff08;DiD&#xff09;思…
阅读更多...
QT QTableWidget控件 全面详解

QT QTableWidget控件 全面详解

本系列文章全面的介绍了QT中的57种控件的使用方法以及示例，包括 Button(PushButton、toolButton、radioButton、checkBox、commandLinkButton、buttonBox)、Layouts(verticalLayout、horizontalLayout、gridLayout、formLayout)、Spacers(verticalSpacer、horizontalSpacer)、…
阅读更多...
SpringBoot--基本使用（配置、整合SpringMVC、Druid、Mybatis、基础特性）

SpringBoot--基本使用（配置、整合SpringMVC、Druid、Mybatis、基础特性）

这里写目录标题 一.介绍1.为什么依赖不需要写版本&#xff1f;2.启动器(Starter)是何方神圣&#xff1f;3.SpringBootApplication注解的功效&#xff1f;4.启动源码5.如何学好SpringBoot 二.SpringBoot3配置文件2.1属性配置文件使用2.2 YAML配置文件使用2.3 YAML配置文件使用2.…
阅读更多...
QT TLS initialization failed

QT TLS initialization failed

qt使用QNetworkAccessManager下载文件&#xff08;给出的链接可以在浏览器里面下载文件&#xff09;&#xff0c;下载失败&#xff0c; 提示“TLS initialization failed”通常是由于Qt在使用HTTPS进行文件下载时&#xff0c;未能正确初始化TLS&#xff08;安全传输层协议&…
阅读更多...
WebODM之python实现

WebODM之python实现

1、安装webodm_slam 主要是了解API文档，查看之前的文章 安装WebODM_slate 2、安装webodm 查看之前的文章 Win10安装WebODM和操作全流程 3、python脚本 项目案例 This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of…
阅读更多...
GitLab配置免密登录和常用命令

GitLab配置免密登录和常用命令

SSH 免密登录 Windows免密登录 删除现有Key 访问目录&#xff1a;C:\Users\Administrator\ .ssh&#xff0c;删除公钥&#xff1a;id_rsa.pub &#xff0c;私钥&#xff1a;id_rsa 2.生成.ssh 秘钥 运行命令生成.ssh 秘钥目录&#xff08; ssh-keygen -t rsa -C xxxxxx126.…
阅读更多...
金融级分布式数据库如何优化？PawSQL发布OceanBase专项调优指南

金融级分布式数据库如何优化？PawSQL发布OceanBase专项调优指南

前言 OceanBase数据库作为国产自主可控的分布式数据库&#xff0c;在金融、电商、政务等领域得到广泛应用&#xff0c;优化OceanBase数据库的查询性能变得愈发重要。PawSQL为OceanBase数据库提供了全方位的SQL性能优化支持&#xff0c;助力用户充分发挥OceanBase数据库的性能潜…
阅读更多...
CentOS7非root用户离线安装Docker及常见问题总结、各种操作系统docker桌面程序下载地址

CentOS7非root用户离线安装Docker及常见问题总结、各种操作系统docker桌面程序下载地址

环境说明 1、安装用户有sudo权限 2、本文讲docker组件安装&#xff0c;不是桌面程序安装 3、本文讲离线安装&#xff0c;不是在线安装 4、目标机器是内网机器&#xff0c;与外部网络不连通 下载 1、下载离线安装包&#xff0c;并上传到$HOME/basic-tool 目录 下载地址&am…
阅读更多...
最新文章

Copyright @ 2022~2023