当前位置： 首页 > article >正文

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

article 2025/1/25 4:43:55

整理 野火 《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 )

http://www.kler.cn/a/517250.html

相关文章：

  • 数据库性能优化(sql优化)_SQL执行计划02_yxy
  • Linux cron 定时任务查看执行情况
  • OpenStack基础架构
  • 电脑办公技巧之如何在 Word 文档中添加文字或图片水印
  • [Computer Vision]实验二：图像特征点提取
  • ChatGPT大模型极简应用开发-CH2-深入了解 GPT-4 和 ChatGPT 的 API
  • Android Studio安装配置
  • pyserial和pymodbus
  • HBase基础shell命令
  • 【深度学习】常见模型-卷积神经网络（Convolutional Neural Networks, CNN）
  • 最新! 在 Linux上搭建Jenkins环境!
  • SQL注入漏洞之基础数据类型注入 字符 数字 搜索 XX 以及靶场实例哟
  • 信创产品测试包括哪些内容？有哪些常用的信创测试工具？
  • 校验收货地址是否超出配送范围实战3（day09）
  • C# volatile 使用详解
  • 如何解压rar格式文件？8种方法（Win/Mac/手机/网页端）
  • DBO朴素贝叶斯分类预测matlab代码
  • 【吉林乡镇界】面图层shp格式arcgis数据乡镇名称和编码wgs84无偏移内容测评
  • Redis 缓存穿透、雪崩和击穿问题及解决方案
  • JAVAweb学习日记（七） 分层解耦
  • 软件需求工程中的风险管理
  • C语言-----扫雷游戏
  • 一款专业通用开源的MES生产执行管理系统
  • Unity常用特性(Attribute)用法
  • 睡眠时间影响因素K-Means可视化分析+XGBoost预测
  • 第15个项目：一个有趣的豆瓣电影TOP爬虫