wordpress 没有样式表,网站如何免费做SEO优化,网站空间要多大,网站seo描述FreeRTOS学习——链表#xff08;列表#xff09;list#xff0c;仅用于记录自己阅读与学习源码
FreeRTOS Kernel V10.5.1
参考大佬的好文章#xff1a; freertos内核原理 Day1(链表) FreeRTOS-链表的源码解析
*list_t只能存储指向list_item_t的指针。每个list_item_t都…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 );
}链表索引指针指向尾节点尾节点值设为最大值且前后指针都指向自己节点数量为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 );
}将新节点 pxNewListItem 插入到 pxIndex 之前将节点的pxContainer指针指向链表链表节点数量加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 );
}确认要插入的位置如果节点值是最大值则插入到尾节点之前否则遍历链表插入新节点将新节点的pxContainer指针指向链表链表节点数量加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;
}将节点从链表中移除将节点的pxContainer指针指向NULL链表节点数量减 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
/** 链表成员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
/** 删除节点* 不返回值的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
/** 内联版本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 ); \}
