FreeRTOS 实时操作系统第九讲 - 链表 (数据结构)

一、链表简述

  链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点（链表中每一个元素称为节点）组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。

  链表作为 C 语言的一种基础数据结构，在平时写程序中用得并不多，但在操作系统中使用得非常多。如果需要读懂 FreeRTOS 系统的源码，必须弄懂链表，如果只是应用 FreeRTOS 系统，简要了解即可。

  如下图：链表好比一个圆形的晾衣架，晾衣架上有很多钩子，钩子首尾相连；链表也是，链表由节点组成，节点与节点之间也是首尾相连。

  晾衣架的钩子本身不能代表很多东西，但钩子却可以挂载很多东西；同样，链表也类似，链表的节点本身不能储存很多内容，但节点跟晾衣架的钩子一样，可以挂载很多数据。

  另外，链表分为单向链表与双向链表，单向链表很少用，用得较多的是双向链表。

二、单向链表与双向链表

1、单向链表

  单向链表如下图，该链表中共有 n 个节点，前一个节点都有一个指针指向后一个节点，首尾相连，组成一个圈。

2、双链链表

  双向链表如下图，该链表中共有 n 个节点，前一个节点都有两个指针分别指向前后节点，首尾相连，组成一个圈。

3、链表与数组的差异

  链表是通过节点把离散的数据 (比如操作系统中任务) 链接成一个表，通过对节点的插入与删除操作实现对数据的储存。 而数组是通过开辟一段连续的内存来储存数据，这是数组与链表的最大区别。

三、FreeRTOS 中链表实现代码

  说明：FreeRTOS 操作系统中的列表与列表项，分别对应 C 语言中的链表与节点。

1、列表项定义

/*
 * Definition of the only type of object that a list can contain.
 */
struct xLIST_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;			/*< The value being listed.  In most cases this is used to sort the list in descending order. */
	struct xLIST_ITEM * configLIST_VOLATILE pxNext;		/*< Pointer to the next ListItem_t in the list. */
	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;	/*< Pointer to the previous ListItem_t in the list. */
	void * pvOwner;										/*< Pointer to the object (normally a TCB) that contains the list item.  There is therefore a two way link between the object containing the list item and the list item itself. */
	void * configLIST_VOLATILE pvContainer;				/*< Pointer to the list in which this list item is placed (if any). */
	listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE			/*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
};
typedef struct xLIST_ITEM ListItem_t;					/* For some reason lint wants this as two separate definitions. */

列表项结构体参数含义如下：

  1. 用于检测列表数据是否完整
  2. 辅助值 (比如用于任务的优先级)，用于帮助节点进行顺序排列
  3. 指向下一个节点的指针
  4. 指向上一个节点的指针
  5. 指向拥有该节点的内核对象，通常是 TCB(任务控制块 / 任务句柄)
  6. 指向该节点所在的链表
  7. 用于检测列表数据是否完整

2、列表定义

/*
 * Definition of the type of queue used by the scheduler.
 */
typedef struct xLIST
{
	listFIRST_LIST_INTEGRITY_CHECK_VALUE				/*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
	volatile UBaseType_t uxNumberOfItems;
	ListItem_t * configLIST_VOLATILE pxIndex;			/*< Used to walk through the list.  Points to the last item returned by a call to listGET_OWNER_OF_NEXT_ENTRY (). */
	MiniListItem_t xListEnd;							/*< List item that contains the maximum possible item value meaning it is always at the end of the list and is therefore used as a marker. */
	listSECOND_LIST_INTEGRITY_CHECK_VALUE				/*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
} List_t;

列表结构体参数含义如下：

  1. 用于检测列表数据是否完整
  2. 链表节点计数器，用于记录该链表下有多少个节点，根节点除外
  3. 链表节点索引指针，用于遍历节点
  4. 链表最后一个节点。 链表是一个圈，首尾相连的，首就是尾，尾也是首。 从字面理解就是链表的最后一个节点，其实也是链表的第一个节点，称之为生产者。 该生产者的数据类型是一个精简的节点，具体如下图。
  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;

四、链表与节点初始化函数

说明：FreeRTOS 操作系统中的列表与列表项，分别对对 C 语言中的链表与节点。

1、列表项初始化函数

void vListInitialiseItem( ListItem_t * const pxItem )
{
	/* Make sure the list item is not recorded as being on a list. */
	pxItem->pvContainer = 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 );
}

说明： 列表项初始化，只需将 pvContainer 初始化为 NULL 即可，表示该节点还没有插入到任何链表。 初始化后如下图：

2、列表初始化函数

void vListInitialise( List_t * const pxList )
{
	/* The list structure contains a list item which is used to mark the
	end of the list.  To initialise the list the list end is inserted
	as the only list entry. */
	pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );			/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */

	/* The list end value is the highest possible value in the list to
	ensure it remains at the end of the list. */
	pxList->xListEnd.xItemValue = portMAX_DELAY;

	/* The list end next and previous pointers point to itself so we know
	when the list is empty. */
	pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );	/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
	pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */

	pxList->uxNumberOfItems = ( UBaseType_t ) 0U;

	/* Write known values into the list if
	configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
	listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
	listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}

说明： 列表初始化，主要初始化索引指针，链表计数值，与内部精简列表项。初始化后如下图：

五、链表操作函数 (尾部插入、升序插入、移除)

说明：FreeRTOS 操作系统中的列表与列表项，分别对对 C 语言中的链表与节点。

1、将节点插入链表尾部

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t * const pxIndex = pxList->pxIndex;

	/* Only effective when configASSERT() is also defined, these tests may catch
	the list data structures being overwritten in memory.  They will not catch
	data errors caused by incorrect configuration or use of FreeRTOS. */
	listTEST_LIST_INTEGRITY( pxList );
	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

	/* Insert a new list item into pxList, but rather than sort the list,
	makes the new list item the last item to be removed by a call to
	listGET_OWNER_OF_NEXT_ENTRY(). */
	pxNewListItem->pxNext = pxIndex;
	pxNewListItem->pxPrevious = pxIndex->pxPrevious;

	/* Only used during decision coverage testing. */
	mtCOVERAGE_TEST_DELAY();

	pxIndex->pxPrevious->pxNext = pxNewListItem;
	pxIndex->pxPrevious = pxNewListItem;

	/* Remember which list the item is in. */
	pxNewListItem->pvContainer = ( void * ) pxList;

	( pxList->uxNumberOfItems )++;
}

分析如下：

  1. 将新节点的 pxNext 指向根节点内的精简节点；
  2. 将新节点的 pxPrevious 指向之前的最后一个节点；
  3. 将之前最后一个节点的 pxNext 指向新节点；
  4. 将根节点内的精简节点 pxPrevious 指向新节点；
  5. 新节点的 pvContaner 指向链表；
  6. 链表的节点计数值加 1

尾部插入详情如下：

2、将节点按照升序插入链表

说明：如果两个节点的辅助值相同，则新节点在旧节点的后面插入。

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t *pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

	/* Only effective when configASSERT() is also defined, these tests may catch
	the list data structures being overwritten in memory.  They will not catch
	data errors caused by incorrect configuration or use of FreeRTOS. */
	listTEST_LIST_INTEGRITY( pxList );
	listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );

	/* Insert the new list item into the list, sorted in xItemValue order.

	If the list already contains a list item with the same item value then the
	new list item should be placed after it.  This ensures that TCB's which are
	stored in ready lists (all of which have the same xItemValue value) get a
	share of the CPU.  However, if the xItemValue is the same as the back marker
	the iteration loop below will not end.  Therefore the value is checked
	first, and the algorithm slightly modified if necessary. */
	if( xValueOfInsertion == portMAX_DELAY )
	{
		pxIterator = pxList->xListEnd.pxPrevious;
	}
	else
	{
		/* *** NOTE ***********************************************************
		If you find your application is crashing here then likely causes are
		listed below.  In addition see http://www.freertos.org/FAQHelp.html for
		more tips, and ensure configASSERT() is defined!
		http://www.freertos.org/a00110.html#configASSERT

			1) Stack overflow -
			   see http://www.freertos.org/Stacks-and-stack-overflow-checking.html
			2) Incorrect interrupt priority assignment, especially on Cortex-M
			   parts where numerically high priority values denote low actual
			   interrupt priorities, which can seem counter intuitive.  See
			   http://www.freertos.org/RTOS-Cortex-M3-M4.html and the definition
			   of configMAX_SYSCALL_INTERRUPT_PRIORITY on
			   http://www.freertos.org/a00110.html
			3) Calling an API function from within a critical section or when
			   the scheduler is suspended, or calling an API function that does
			   not end in "FromISR" from an interrupt.
			4) Using a queue or semaphore before it has been initialised or
			   before the scheduler has been started (are interrupts firing
			   before vTaskStartScheduler() has been called?).
		**********************************************************************/

		for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
		{
			/* There is nothing to do here, just iterating to the wanted
			insertion position. */
		}
	}

	pxNewListItem->pxNext = pxIterator->pxNext;
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	pxNewListItem->pxPrevious = pxIterator;
	pxIterator->pxNext = pxNewListItem;

	/* Remember which list the item is in.  This allows fast removal of the
	item later. */
	pxNewListItem->pvContainer = ( void * ) pxList;

	( pxList->uxNumberOfItems )++;
}

分析如下：

  1. 查找插入位置；
  2. 调整指向关系
  3. 新节点的 pvContaner 指向链表
  4. 链表的节点计数值加 1

升序插入详情如下：

3、移除节点

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
/* The list item knows which list it is in.  Obtain the list from the list
item. */
List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;

	pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
	pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

	/* Only used during decision coverage testing. */
	mtCOVERAGE_TEST_DELAY();

	/* Make sure the index is left pointing to a valid item. */
	if( pxList->pxIndex == pxItemToRemove )
	{
		pxList->pxIndex = pxItemToRemove->pxPrevious;
	}
	else
	{
		mtCOVERAGE_TEST_MARKER();
	}

	pxItemToRemove->pvContainer = NULL;
	( pxList->uxNumberOfItems )--;

	return pxList->uxNumberOfItems;
}

分析如下：

  1. 通过节点获取链表；
  2. 调整指向关系
  3. 调整链表的索引指针
  4. 将删除节点的 pvContainer 指向 NULL；
  5. 链表的节点计数值减 1
  6. 返回链表的节点计数值

移除详情如下：

六、链表编程测试

说明：软件模拟仿真

1、只创建 1 个任务，在任务中进行链表测试

2、列表与列表项定义
说明：watch 中查看变量值，需要定义为全局变量

3、任务 1 代码

4、设置为模拟仿真，避免仿真错误，删除硬件相关的初始化代码


5、增加断点


6、开始仿真，并在 watch 添加列表与列表项

7、全速仿真至任务 1，再按 F10 单步执行，同时查看 watch 窗口

8、验证 OK。

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

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

相关文章

虾皮、Lazada店铺流量怎么提升？自养号优势及测评系统如何搭建？

虾皮、Lazada店铺流量怎么提升？自养号优势及测评系统如何搭建？

虾皮、Lazada是东南亚地区最大的购物平台之一&#xff0c;吸引了大量的买家和卖家。在竞争激烈的虾皮市场上&#xff0c;如何提升店铺的流量成为许多卖家关注的问题。以下是关于如何提升虾皮、Lazada店铺流量的一些建议。 一、店铺流量怎么提升? 首先&#xff0c;进行优质的…
阅读更多...
C#编程-使用集合

C#编程-使用集合

使用集合 您学习了如何使用数组来有效地存储和操作相似类型额数据。但是，以下限制于数组的使用相关联： 您必须在声明时定义数组的大小。您必须编写代码以对数组执行标准操作，如排序。让我们思考一个示例。假设您想要存储在组织工作的五个雇员的姓名。您可以使用以下语句来声…
阅读更多...
java基于ssm的线上选课系统的设计与实现论文

java基于ssm的线上选课系统的设计与实现论文

摘 要 在如今社会上&#xff0c;关于信息上面的处理&#xff0c;没有任何一个企业或者个人会忽视&#xff0c;如何让信息急速传递&#xff0c;并且归档储存查询&#xff0c;采用之前的纸张记录模式已经不符合当前使用要求了。所以&#xff0c;对学生选课信息管理的提升&#x…
阅读更多...
无人直播源码/技术源头开发/直播贴片技术源头

无人直播源码/技术源头开发/直播贴片技术源头

无人直播源码/技术源头开发/直播贴片&#xff0c;无人直播&#xff0c;无人实景直播。动态切片功能&#xff0c;自动回复功能&#xff0c;压低打断主播音&#xff0c;支持短视频各大主流平台开播。 搭建无人直播源码需要以下步骤&#xff1a; 1. 确定直播平台和工具&#xff1…
阅读更多...
基于孔雀优化算法的航线规划

基于孔雀优化算法的航线规划

MATLAB2020a下正常运行 上传明细-CSDN创作中心
阅读更多...
XSKY SDS 产品率先获得 OceanBase V4 新版本认证

XSKY SDS 产品率先获得 OceanBase V4 新版本认证

近日&#xff0c;北京奥星贝斯科技有限公司&#xff08;简称&#xff1a;OceanBase&#xff09;与北京星辰天合科技股份有限公司&#xff08;简称&#xff1a;XSKY 星辰天合&#xff09;顺利完成产品兼容性认证。 XSKY 的高性能全闪存储以及混闪存储&#xff0c;与 OceanBase V…
阅读更多...
大数据平台Bug Bash大扫除最佳实践

大数据平台Bug Bash大扫除最佳实践

一、背景 随着越来越多的"新人"在日常工作以及大促备战中担当大任&#xff0c;我们发现仅了解自身系统业务已不能满足日常系统开发运维需求。为此&#xff0c;大数据平台部门组织了一次Bug Bash活动&#xff0c;既能提升自己对兄弟产品的理解和使用&#xff0c;又能…
阅读更多...
【IPC通信--信号】

【IPC通信--信号】

信号处理函数 • 信号发送函数 – kill(), sigqueue(), raise(), alarm(), setitimer(), pause() &#xff0c; abort() • 信号安装函数 – signal(), sigaction() • 信号集操作函数 – sigemptyset(), sigfillset(), sigaddset(), sigdelset(), sigismember() 信号发送函数—…
阅读更多...
xgboost对密西西比数据集csv文件进行预测

xgboost对密西西比数据集csv文件进行预测

代码&#xff1a; # 导入需要的库 from sklearn.preprocessing import LabelEncoder import matplotlib.pyplot as plt import pandas as pd import xgboost as xgb from sklearn.model_selection import train_test_split from sklearn.metrics import confusion_matrix, cla…
阅读更多...
自定义事件总线

自定义事件总线

文章目录 什么是自定义事件总线具体实现思路分析定义结构实现 on实现 emit实现 off 源码 什么是自定义事件总线 自定义事件总线属于一种观察着模式&#xff0c;其中包括三个角色发布者&#xff08;Publisher&#xff09;&#xff1a;发出事件&#xff08;Event&#xff09;订阅…
阅读更多...
[SwiftUI]工程最低适配iOS13

[SwiftUI]工程最低适配iOS13

问题&#xff1a; 新建工程&#xff0c;选择最低支持iOS13报错&#xff1a; main() is only available in iOS 14.0 or newer Scene is only available in iOS 14.0 or newer WindowGroup is only available in iOS 14.0 or newer 解决&#xff1a; 注释掉上面代码&#x…
阅读更多...
短剧分销系统搭建：其成为普通人创业的新选择？短剧的红利有多高？

短剧分销系统搭建：其成为普通人创业的新选择？短剧的红利有多高？

去年&#xff0c;短剧进入到了爆发期&#xff0c;成为了年轻人闲暇时间的娱乐方式。短剧每集只有几分钟时间&#xff0c;非常适合当下大众的碎片化时间。根据当下短剧的发展趋势&#xff0c;短剧的市场规模将逐渐赶超电影票房。 目前短剧还进行了多元化发展&#xff0c;逐渐走…
阅读更多...
两数之和 ？ 三数之和？ 四数之和？ 统统搞定

两数之和 ？ 三数之和？ 四数之和？ 统统搞定

&#x1f388;个人主页:&#x1f388; :✨✨✨初阶牛✨✨✨ &#x1f43b;推荐专栏1: &#x1f354;&#x1f35f;&#x1f32f;C语言初阶 &#x1f43b;推荐专栏2: &#x1f354;&#x1f35f;&#x1f32f;C语言进阶 &#x1f511;个人信条: &#x1f335;知行合一 前言 声明…
阅读更多...
高性价比LDR6028Type-C转3.5mm音频和PD快充转接器

高性价比LDR6028Type-C转3.5mm音频和PD快充转接器

随着市面上的大部分手机逐渐取消了3.5mm音频耳机接口&#xff0c;仅保留一个Type-C接口&#xff0c;追求音质和零延迟的用户面临着一大痛点。对于这些用户&#xff0c;Type-C转3.5mm接口线的出现无疑是一大福音。这款线材在刚推出时就受到了手机配件市场的热烈欢迎&#xff0c;…
阅读更多...
Python武器库开发-武器库篇之子域名扫描器开发(四十一)

Python武器库开发-武器库篇之子域名扫描器开发(四十一)

Python武器库开发-武器库篇之子域名扫描器开发(四十一) 在我们做红队攻防或者渗透测试的过程中&#xff0c;信息收集往往都是第一步的&#xff0c;有人说&#xff1a;渗透的本质就是信息收集&#xff0c;前期好的信息收集很大程度上决定了渗透的质量和攻击面&#xff0c;本文将…
阅读更多...
AI数字人国内人工智能产业发展趋势

AI数字人国内人工智能产业发展趋势

随着科技的不断进步&#xff0c;人工智能&#xff08;Artificial Intelligence&#xff0c;简称AI&#xff09;已成为当今社会的热门话题。作为一种复杂而高级的技术&#xff0c;人工智能在国内发展势头迅猛。本文将探讨AI数字人国内人工智能产业的发展趋势。 首先&#xff0c…
阅读更多...
科锐16位汇编学习笔记01汇编基础和debug使用

科锐16位汇编学习笔记01汇编基础和debug使用

为什么学习16位汇编&#xff1f; 16位操作指令最多能够操作两个字节&#xff0c;且更能够体现出与硬件的交互。16位下的指令和32位汇编的指令差不多。16位汇编的指令在32位一样使用.要学好汇编必须要了解一点点硬件知识,16汇编是直接操作硬件,32位汇编指令跟硬件隔离了 硬件运…
阅读更多...
simulink代码生成（六）——中断向量模块的配置

simulink代码生成（六）——中断向量模块的配置

假如系统中存在多个中断&#xff0c;需要合理的配置中断的优先级与中断向量表&#xff1b;在代码生成中&#xff0c;要与中断向量表对应&#xff1b;中断相关的知识参照博客&#xff1a; DSP28335学习——中断向量表的初始化_中断向量表什么时候初始化-CSDN博客 F28335中断系…
阅读更多...
目标检测-One Stage-YOLOv2

目标检测-One Stage-YOLOv2

文章目录 前言一、YOLOv2的网络结构和流程二、YOLOv2的创新点预处理网络结构训练 总结 前言 根据前文目标检测-One Stage-YOLOv1可以看出YOLOv1的主要缺点是&#xff1a; 和Fast-CNN相比&#xff0c;速度快&#xff0c;但精度下降。&#xff08;边框回归不加限制&#xff09;…
阅读更多...
24年初级会计资格考试报名信息采集流程共10大步骤，千万不要搞错

24年初级会计资格考试报名信息采集流程共10大步骤，千万不要搞错

2024年初级会计资格考试报名信息采集流程共10大步骤&#xff0c;不要搞错哦&#xff1b; 第一步&#xff1a;输入证件号、点击登录 第二步&#xff1a;阅读采集须知 第三步&#xff1a;填写个人信息&#xff08;支付宝搜索"亿鸣证件照"或者微信搜索"随时照&q…
阅读更多...
最新文章

Copyright @ 2022~2023