|
& u' }( D+ u' K2 b% ?0 p( } o8 F1 |- I FreeRTOS列表&列表项的源码解读1 B2 A- ^; H. M& I 第一次看列表与列表项的时候，感觉很像是链表，虽然我自己的链表也不太会，但是就是感觉很像。 在FreeRTOS中，列表与列表项使用得非常多，是FreeRTOS的一个数据结构，学习过数据结构的同学都知道，数据结构能使我们处理数据更加方便快速，能快速找到数据，在FreeRTOS中，这种列表与列表项更是必不可少的，能让我们的系统跑起来更加流畅迅速。 4 j; W( ?% |- H8 P4 G言归正传，FreeRTOS中使用了大量的列表（List）与列表项（Listitem），在FreeRTOS调度器中，就是用到这些来跟着任务，了解任务的状态，处于挂起、阻塞态、还是就绪态亦或者是运行态。这些信息都会在各自任务的列表中得到。 看任务控制块（tskTaskControlBlock）中的两个列表项： 1 ListItem_t xStateListItem; /*< The list that the state list item of a task is reference from denotes the state of that task (Ready, Blocked, Suspended ). */1 m' u$ Q' d5 l2 ListItem_t xEventListItem; /*< Used to reference a task from an event list. */% m% z0 |" x4 k8 a0 i: t 一个是状态的列表项，一个是事件列表项。他们在创建任务就会被初始化，列表项的初始化是根据实际需要来初始化的，下面会说。 FreeRTOS列表&列表项的结构体 既然知道列表与列表项的重要性，那么我们来解读FreeRTOS中的list.c与list.h的源码吧。从头文件lsit.h开始，看到定义了一些结构体： 1struct xLIST_ITEM1 x' q3 ?5 G: A3 E2{3 V1 g2 _+ i! i9 z1 S6 v* i' a" \$ L- u 3 listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1，则设置为已知值。* / 4 configLIST_VOLATILE TickType_t xItemValue; / * <正在列出的值。在大多数情况下，这用于按降序对列表进行排序。 * /* I- y; _ P2 l1 g7 u' Z 5 struct xLIST_ITEM * configLIST_VOLATILE pxNext; / * <指向列表中下一个ListItem_t的指针。 * / 6 struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; / * <指向列表中前一个ListItem_t的指针。 * / 7 void * pvOwner; / * <指向包含列表项目的对象（通常是TCB）的指针。因此，包含列表项目的对象与列表项目本身之间存在双向链接。 * / 8 void * configLIST_VOLATILE pvContainer; / * <指向此列表项目所在列表的指针（如果有）。 * /% \+ H5 [& V, }' k0 a 9 listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1，则设置为已知值。* /6 R" }0 o: a2 E. M 10};- k( t" q5 {3 y. |7 D 11 typedef struct xLIST_ITEM ListItem_t;) Y3 _( h1 L# o* J( c" T6 ^. S- M 列表项结构体的一些注意的地方： xItemValue 用于列表项的排序，类似1—2—3—4 pxNext 指向下一个列表项的指针 pxPrevious 指向上（前）一个列表项的指针 这两个指针实现了类似双向链表的功能 pvOwner 指向包含列表项目的对象（通常是任务控制块TCB）的指针。因此，包含列表项目的对象与列表项目本身之间存在双向链接。 pvContainer 记录了该列表项属于哪个列表，说白点就是这个儿子是谁生的。。。 ! C* F% t7 f# u6 [同时定义了一个MINI的列表项的结构体，MINI列表项是删减版的列表项，因为很多时候不需要完全版的列表项。就不用浪费那么多内存空间了，这或许就是FreeRTOS是轻量级操作系统的原因吧，能省一点是一点。MINI列表项： 1struct xMINI_LIST_ITEM2{ 3 listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */ 4 configLIST_VOLATILE TickType_t xItemValue;3 n8 l! G! g0 P4 r! P7 v' T 5 struct xLIST_ITEM * configLIST_VOLATILE pxNext; 6 struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;5 x4 b2 S2 |# N/ g9 l# h 7}; b4 e/ g& }/ ]/ d# X 8typedef struct xMINI_LIST_ITEM MiniListItem_t;* m: S( H1 Q+ m3 i( M 再定义了一个列表的结构体，可能看到这里，一些同学已经蒙了，列表与列表项是啥关系啊，按照杰杰的理解，是类似父子关系的，一个列表中，包含多个列表项，就像一个父亲，生了好多孩子，而列表就是父亲，列表项就是孩子。 1typedef struct xLIST 列表的结构体中值得注意的是：2{ 3 listFIRST_LIST_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1，则设置为已知值。* // i5 Z6 @# |" U5 k9 i 4 configLIST_VOLATILE UBaseType_t uxNumberOfItems; 5 ListItem_t * configLIST_VOLATILE pxIndex; / * <用于遍历列表。 指向由listGET_OWNER_OF_NEXT_ENTRY（）调用返回的后一个列表项。*/( K/ w! i# U: l$ V 6 MiniListItem_t xListEnd; / * <List item包含最大可能的项目值，这意味着它始终在列表的末尾，因此用作标记。*/# [* O3 k: @# l6 v* q- s- R n8 T 7 listSECOND_LIST_INTEGRITY_CHECK_VALUE / * <如果configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设置为1，则设置为已知值。* / 8} List_t; uxNumberOfItems 是用来记录列表中列表项的数量的，就是记录父亲有多少个儿子，当然女儿也行~。 pxIndex 是索引编号，用来遍历列表的，调用宏listGET_OWNER_OF_NEXT_ENTRY（）之后索引就会指向返回当前列表项的下一个列表项。 xListEnd 指向的是最后一个列表项，并且这个列表项是MiniListItem属性的，是一个迷你列表项。 & y. @2 I1 A5 w. C 函数： 1void vListInitialise( List_t * const pxList )2{ p* K, O! p( p7 L 3 pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*lint The mini list structure is used as the list end to save RAM. This is checked and valid. */ 4 pxList->xListEnd.xItemValue = portMAX_DELAY;0 @" t" k0 R' S8 v8 L9 } 5 pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); /*lint The mini list structure is used as the list end to save RAM. This is checked and valid. */' b; ]0 a, y* F8 E8 s 6 pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/*lint The mini list structure is used as the list end to save RAM. This is checked and valid. */7 ?6 u& ~ c/ c. }+ j 7 pxList->uxNumberOfItems = ( UBaseType_t ) 0U; 8 listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList ); 9 listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList ); 10} 将列表的索引指向列表中的xListEnd，也就是末尾的列表项（迷你列表项） 列表项的xItemValue数值为portMAX_DELAY，也就是0xffffffffUL，如果在16位处理器中则为0xffff。 列表项的pxNext与pxPrevious这两个指针都指向自己本身xListEnd。 初始化完成的时候列表项的数目为0个。因为还没添加列表项嘛~。
列表项的初始化 函数： 1void vListInitialiseItem( ListItem_t * const pxItem )2{ 3 /* Make sure the list item is not recorded as being on a list. */4 s# n3 l. L2 o, y 4 pxItem->pvContainer = NULL;- J6 z# L; i9 i0 _ ^2 d 5 /* Write known values into the list item if& e) ?4 t/ a- }2 H 6 configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */ 7 listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem ); 8 listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem ); 9} 只需要让列表项的pvContainer指针指向NULL即可，这样子就使得列表项不属于任何一个列表，因为列表项的初始化是要根据实际的情况来进行初始化的。 例如任务创建时用到的一些列表项初始化： 1pxNewTCB->pcTaskName[ configMAX_TASK_NAME_LEN - 1 ] = '\0';, N$ J) Y! v+ y' A/ a- a, V5 d6 Y2pxNewTCB->uxPriority = uxPriority; 3pxNewTCB->uxBasePriority = uxPriority; A- ?. }& P# a7 a! M 4pxNewTCB->uxMutexesHeld = 0; 5 vListInitialiseItem( &( pxNewTCB->xStateListItem ) ); 6 vListInitialiseItem( &( pxNewTCB->xEventListItem ) );. ^8 p% k6 |2 Q K$ `- @' u3 F 又或者是在定时器相关的初始化中： 1 pxNewTimer->pcTimerName = pcTimerName;9 R' ~( K) K6 ~+ s! `6 [2 pxNewTimer->xTimerPeriodInTicks = xTimerPeriodInTicks; 3 pxNewTimer->uxAutoReload = uxAutoReload; 4 pxNewTimer->pvTimerID = pvTimerID; 5 pxNewTimer->pxCallbackFunction = pxCallbackFunction;* w$ |& l# z5 l 6 vListInitialiseItem( &( pxNewTimer->xTimerListItem ) );! i' m3 I- }! w8 t6 b 列表项的末尾插入 函数： 1void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )2{ 3ListItem_t * const pxIndex = pxList->pxIndex; 4 listTEST_LIST_INTEGRITY( pxList ); 5 listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );, g& d( F" N+ T 6 listGET_OWNER_OF_NEXT_ENTRY(). */ 7 pxNewListItem->pxNext = pxIndex; // 1 . q# x8 A5 a/ \4 l* s 8 pxNewListItem->pxPrevious = pxIndex->pxPrevious; // 2" T9 B9 }7 i0 }& \8 d9 x/ O4 E 9 /* Only used during decision coverage testing. */' g" I s, ^% `2 g; L. P1 { 10 mtCOVERAGE_TEST_DELAY(); 11 pxIndex->pxPrevious->pxNext = pxNewListItem; // 3 12 pxIndex->pxPrevious = pxNewListItem; // 4 13 /* Remember which list the item is in. */7 l6 E1 b& ?' p 14 pxNewListItem->pvContainer = ( void * ) pxList;% \4 U% N. A8 Q. {: {8 J1 k 15 ( pxList->uxNumberOfItems )++; 16}( `/ ?' }/ ~: `6 g 传入的参数： pxList：列表项要插入的列表。 pxNewListItem：要插入的列表项是什么。 从末尾插入，那就要先知道哪里是头咯，我们在列表中的成员pxIndex就是用来遍历列表项的啊，那它指向的地方就是列表项的头，那么既然FreeRTOS中的列表很像数据结构中的双向链表，那么，我们可以把它看成一个环，是首尾相连的，那么函数中说的末尾，就是列表项头的前一个，很显然其结构图应该是下图这样子的（初始化结束后pxIndex指向了xListEnd）：
为什么是这样子的呢，一句句代码来解释： 一开始： ListItem_t * const pxIndex = pxList->pxIndex;保存了一开始的索引列表项（xListEnd）的指向。 pxNewListItem->pxNext = pxIndex; // 1新列表项的下一个指向为索引列表项，也就是绿色的箭头。 pxNewListItem->pxPrevious = pxIndex->pxPrevious; // 2刚开始我们初始化完成的时候pxIndex->pxPrevious的指向为自己xListEnd，那么xNewListItem->pxPrevious的指向为xListEnd。如2紫色的箭头。 pxIndex->pxPrevious->pxNext = pxNewListItem; // 3索引列表项（xListEnd）的上一个列表项还是自己，那么自己的下一个列表项指向就是指向了pxNewListItem。 pxIndex->pxPrevious = pxNewListItem; // 4这句就很容易理解啦。如图的4橙色的箭头。 插入完毕的时候标记一下新的列表项插入了哪个列表，并且将uxNumberOfItems进行加一，以表示多了一个列表项。 为什么源码要这样子写呢？因为这只是两个列表项，一个列表含有多个列表项，那么这段代码的通用性就很强了。无论原本列表中有多少个列表项，也无论pxIndex指向哪个列表项！
看看是不是按照源码中那样插入呢？ 0 l( X6 h! r8 r. w' s1 J" V3 R% }列表项的插入 源码： 1void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )2{ 3ListItem_t *pxIterator;* j4 [: R: y1 z6 ? r" l8 y 4const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;% J0 ?* R* j, `! x 5 listTEST_LIST_INTEGRITY( pxList ); 6 listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );+ B5 b" S: l2 _: r! w 7 if( xValueOfInsertion == portMAX_DELAY )7 [" J+ F0 f/ E9 D/ ~( p 8 { 9 pxIterator = pxList->xListEnd.pxPrevious; 10 } 11 else 12 { 13 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. */ 14 { 15 /* There is nothing to do here, just iterating to the wanted 16 insertion position. */ 17 } 18 }0 O8 f8 \" ?; U e 19 pxNewListItem->pxNext = pxIterator->pxNext;$ N5 ?1 H6 j ?* @; Q 20 pxNewListItem->pxNext->pxPrevious = pxNewListItem; 21 pxNewListItem->pxPrevious = pxIterator; 22 pxIterator->pxNext = pxNewListItem;( E- P1 d! r9 B% f, g; l* } 23 /* Remember which list the item is in. This allows fast removal of the- Z; C4 }. v7 l4 j( O* k 24 item later. */ 25 pxNewListItem->pvContainer = ( void * ) pxList;' d ^& X* J/ S7 z+ z8 Y 26 ( pxList->uxNumberOfItems )++; 27} 传入的参数： pxList：列表项要插入的列表。 pxNewListItem：要插入的列表项是什么。 1 D' K2 S# n% L5 d! K& i/ epxList决定了插入哪个列表，pxNewListItem中的xItemValue值决定了列表项插入列表的位置。 ListItem_t *pxIterator; 2const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;定义一个辅助的列表项pxIterator，用来迭代找出插入新列表项的位置，并且保存获取要插入的列表项pxNewListItem的xItemValue。 如果打开了列表项完整性检查，就要用户实现configASSERT()，源码中有说明。 既然是要插入列表项，那么肯定是要知道列表项的位置了，如果新插入列表项的xItemValue是最大的话（portMAX_DELAY），就直接插入列表项的末尾。否则就需要比较列表中各个列表项的xItemValue的大小来进行排列。然后得出新列表项插入的位置。 for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )上面源码就是实现比较的过程。 与上面的从列表项末尾插入的源码一样，FreeRTOS的代码通用性很强，逻辑思维也很强。 如果列表中列表项的数量为0，那么插入的列表项就是在初始化列表项的后面。如下图所示： 过程分析： 新列表项的pxNext指向pxIterator->pxNext，也就是指向了xListEnd（pxIterator）。 pxNewListItem->pxNext = pxIterator->pxNext;而xListEnd（pxIterator）的pxPrevious指向则为pxNewListItem。 pxNewListItem->pxNext->pxPrevious = pxNewListItem;新列表项的（pxPrevious）指针指向xListEnd（pxIterator） pxIterator 的 pxNext 指向了新列表项& u- Z9 S, [0 j9 F* ^ 与从末尾插入列表项其实是一样的，前提是当前列表中列表项的数目为0。 假如列表项中已经有了元素呢，过程又是不一样的了。原来的列表是下图这样子的： 假设插入的列表项的xItemValue是2，而原有的列表项的xItemValue值是3，那么，按照源码，我们插入的列表项是在中间了。而pxIterator则是①号列表项。 插入后的效果：
分析一下插入的过程： 新的列表项的pxNext指向的是pxIterator->pxNext，也就是③号列表项。因为一开始pxIterator->pxNext=指向的就是③号列表项！！ pxNewListItem->pxNext = pxIterator->pxNext;而pxNewListItem->pxNext 即③号列表项的指向上一个列表项指针（pxPrevious）的则指向新插入的列表项，也就是②号列表项了。 pxNewListItem->pxNext->pxPrevious = pxNewListItem;新插入列表项的指向上一个列表项的指针pxNewListItem->pxPrevious指向了辅助列表项pxIterator。很显然要连接起来嘛！ pxNewListItem->pxPrevious = pxIterator;同理，pxIterator列表项的指向下一个列表项的指针则指向新插入的列表项了pxNewListItem。 pxIterator->pxNext = pxNewListItem;而其他没改变指向的地方不需改动。（图中的两条直线做的连接线是不需要改动的） 当插入完成的时候，记录一下新插入的列表项属于哪个列表。并且让该列表下的列表项数目加一。 pxNewListItem->pvContainer = ( void * ) pxList;2 ( pxList->uxNumberOfItems )++;# a1 e& l9 M: ]: S, _删除列表项 源码： 1UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )2{- {$ g/ N! U5 V! V4 J 3/* The list item knows which list it is in. Obtain the list from the list z1 j; k1 J5 i 4item. */% w2 s' C \* }5 i# o 5List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer; 6 pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;% A. t- H+ G7 O+ g* @ T 7 pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;" B- Y0 W* r8 l, k" R( G 8 /* Only used during decision coverage testing. */ 9 mtCOVERAGE_TEST_DELAY(); 10 /* Make sure the index is left pointing to a valid item. */3 x) y, G x8 u9 ~& P 11 if( pxList->pxIndex == pxItemToRemove ) 12 {$ `, k2 D/ `, s0 ?3 K 13 pxList->pxIndex = pxItemToRemove->pxPrevious; 14 }# m, K2 e' X( R9 b5 z8 l 15 else 16 {- h* k1 U* M3 j$ `& y; _( I+ u# u 17 mtCOVERAGE_TEST_MARKER(); 18 }- d' k4 `3 |0 {* K/ K: I! ~1 ~ 19 pxItemToRemove->pvContainer = NULL;: b* ~- K# J* g% y! z; C- a1 r7 r 20 ( pxList->uxNumberOfItems )--;0 J0 b4 K; N' ]5 n* J5 A: J. w 21 return pxList->uxNumberOfItems; 22} 其实删除是很简单的，不用想都知道，要删除列表项，那肯定要知道该列表项是属于哪个列表吧，pvContainer就是记录列表项是属于哪个列表的。 删除就是把列表中的列表项从列表中去掉，其本质其实就是把他们的连接关系删除掉，然后让删除的列表项的前后两个列表连接起来就行了，假如是只有一个列表项，那么删除之后，列表就回到了初始化的状态了。 pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;2 pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;这两句代码就实现了将删除列表项的前后两个列表项连接起来。 按照上面的讲解可以理解这两句简单的代码啦。 % m9 ]( x5 o4 \7 E1 n) a假如删除的列表项是当前索引的列表项，那么在删除之后，列表中的pxIndex就要指向删除列表项的上一个列表项了。 if( pxList->pxIndex == pxItemToRemove )2 {3 pxList->pxIndex = pxItemToRemove->pxPrevious;4 }当然还要把当前删除的列表项的pvContainer指向NULL，让它不属于任何一个列表，因为，删除的本质是删除的仅仅是列表项的连接关系，其内存是没有释放掉的，假如是动态内存分配的话。 并且要把当前列表中列表项的数目返回一下。 0 L3 r% `& }) n% t$ R# B% G至此，列表的源码基本讲解完毕。 . T; C' [! Z2 n: `& n* Q! f9 T& k最后 大家还可以了解一下遍历列表的宏，它在list.h文件中： 1define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \2{ \ 3List_t * const pxConstList = ( pxList ); \ 4 /* Increment the index to the next item and return the item, ensuring */ \ 5 /* we don't return the marker used at the end of the list. */ \ 6 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \' J0 Q; j: m8 M) a! \ 7 if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) \ 8 { \+ p7 A. q8 u! S3 [* K 9 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \ 10 } \ 11 ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; \ 12}9 Y- [+ R; @2 }) o5 p/ {" w 这是一个宏，用于列表的遍历，返回的是列表中列表项的pxOwner成员，每次调用这个宏（函数）的时候，其pxIndex索引会指向当前返回列表项的下一个列表项。
|
| 这排版看起来好难看啊。。。。。。。。。。破总！！！！ |
| @ zero99 |
| 感谢分享！ |
