1. 什么是列表和列表项
/ \9 p0 f8 e- ?& j6 w% s+ L1.1 列表
% q. F0 B) e7 m( N5 m: p7 t列表是FreeRTOS的一个数据结构，被用来跟踪FreeRTOS中的任务。与列表有关的东西都在list.c和list.h文件里。在list.h中定义了一个List_t的结构体：
+ S  x+ I" C% ^# B4 G
0 s+ ^5 l# T* C$ b% \) \9 o

1. typedef struct xLIST
   & [& ^  T8 M5 E- G3 ~
2. {
   0 H: v" K) Q0 w( T9 a5 I
3.   listFIRST_LIST_INTEGRITY_CHECK_VALUE          // 检查列表完整性，将configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设1。默认不开启
   4 q$ a* Q% M7 F! \
4.   configLIST_VOLATILE UBaseType_t uxNumberOfItems; // 用来记录列表中列表项的数量
   
5.   ListItem_t * configLIST_VOLATILE pxIndex;               // 用来记录当前列表项索引号，用于遍历列表
   * `9 B" n3 H4 Q6 R# N7 G& N
6.   MiniListItem_t xListEnd;                                       // 列表中最后一个列表项，用来表示列表结束，此变量类型为MiniListItem_t
   
7.   listSECOND_LIST_INTEGRITY_CHECK_VALUE                       // 检查列表完整性，将configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES设1。默认不开启
   : z5 \2 B7 S- a" U2 z
8. } List_t;

复制代码

! w# A  g0 ]1 ^3 y列表结构示意图为：
( m1 g: U& f8 |: _5 x
! M+ e" n* U. ~( }( ^' w
1.2 列表项
' x5 [5 k/ D/ G4 j; m& b列表项就是存放在列表中的项目，FreeRTOS有两种列表项：列表项和迷你列表项，在list.h中定义：
: ~* ?! j$ y' `) b0 c/ z8 C. s; e

1. struct xLIST_ITEM
   
2. {
   
3.         listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE        
   0 E' t; h0 Q  l* w) Y: Z
4.         configLIST_VOLATILE TickType_t xItemValue;                // xItemValue列表项值        
   
5.         struct xLIST_ITEM * configLIST_VOLATILE pxNext;                // pxNext指向下一个列表项
   
6.         struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;        // pxPrevious指向前一个列表项
   
7.         void * pvOwner;                        // 记录此列表项归谁拥有，通常是任务控制块                                                        
   
8.         void * configLIST_VOLATILE pvContainer;                // 用来记录此列表项归哪个列表。        
   # I5 F/ |; u9 c. @  d! `
9.         listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE               
   
10. };
    
11. typedef struct xLIST_ITEM ListItem_t;      

复制代码

对于pvContainer再多说两句，在任务控制块TCB_t中有两个变量xStateListItem和xEventListItem，这两个变量类型是ListItem_t，即这两个成员变量是列表项。以xStateListItem为例，当创建一个任务后，xStateListItem的pvOwner变量指向这个任务的任务控制块，表示xStateListItem属于此任务。当任务就绪态以后，xStateListItem的变量pvContainer就指向就绪列表，表面此列表项在就绪列表中。
列表项结构示意图如下：

! p5 k. @/ ?4 d0 K7 Y
2 O, e3 m: d3 D2 z* f5 }. p
" b. o* F# g& m6 n; ]& Z) \. J1.3 迷你列表项
迷你列表项在list.h中定义：
* l" M5 `! r4 I# z

1. struct xMINI_LIST_ITEM
   
2. {
   
3.         listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
   
4.         configLIST_VOLATILE  TickType_t           xItemValue;        // xItemValue记录列表项值
   ' p# U) z  E) |$ s+ e5 `  D5 i2 V' q1 ~
5.         struct xLIST_ITEM * configLIST_VOLATILE  pxNext;      // pxNext指向下一个列表项
   3 P$ M! M  V5 r9 E
6.         struct xLIST_ITEM * configLIST_VOLATILE  pxPrevious;  // pxPrevious指向上一个列表项
   " ?3 A; T: ]" }- j2 i) X
7. }
   
8. typedef struct xMINI_LIST_ITEM  MiniListItem_t;           //
   

复制代码

迷你列表项结构示意图如下：
2 W( K2 q2 P. H# E8 W! ]
+ c% ?- h1 [" k- x

2. 列表和列表项初始化
2.1 列表初始化
新创建或定义的列表需要对其做初始化处理，列表的初始化其实就是初始化列表结构体List_t中的各个成员变量，列表的初始化通过使函数vListInitialise()来完成，此函数在list.c中有定义：
7 Y, A# R2 N8 x+ R, j. f5 `
0 D4 t  c* w4 V4 f3 B% r( z! N

1. void vListInitialise( List_t * const pxList )
   : u* r% [' x# t
2. {
   9 F  }* ~9 P% f$ Q" D+ _
3.     // xListEnd用来表示列表的末尾，而pxIndex表示索引号，此时列表只有一个列表项，就是xListEnd,所以pxIndex指向xListEnd。
   
4.         pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );  
   ! C3 m7 M1 U. r% G' r
5.         // xListEnd列表项值初始化为portMAX_DELAY(在portmacro.h中定义)。本教程为0xffffffffUL
   
6.         pxList->xListEnd.xItemValue = portMAX_DELAY;
   ; X' N! `' q) W
7.         // 初始化列表项xListEnd的pxNext变量，因为此列表只有一个列表项，因此pxNext指向自身
   
8.         pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );        
   
9.         // 初始化xListEnd的pxPrevious变量，指向xListEnd自身
   + A( Y$ }. |, E+ Z% K
10.         pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
    
11.         // 由于此时没有其他的列表项，因此uxNumberOfItems为0，注意：这里不算xListEnd
    
12.         pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
    6 C; e$ E2 Q5 S1 u, t+ T# S4 T
13.         // 以下两行用于完整性检查字段，只有configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES为1时有效。STM32写入的是0x5a5a5a5aUL
    
14.         listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
    6 _: h' ~! L% P. z
15.         listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
    
16. }

复制代码

列表初始化如下图：
1 G6 I# a7 `6 q; j! V* ]
9 o/ B; {, n/ W, S8 J" Z- Y, }& i

! {& M5 I# g4 M: g2.2 列表项初始化
" q. X$ Z4 P3 N7 J/ b9 }( P通列表一样，列表项在使用的时候也需要初始化，列表项初始化由函数vListInitialiseItem()函数完成：
' w; k4 `' y2 g0 M# _9 M5 c" j- K

1. void vListInitialiseItem( ListItem_t * const pxItem )
   3 R" n2 V  b; D' o0 G. V8 U
2. {
   
3.         pxItem->pvContainer = NULL;    // 初始化pvContainer为NULL
   - D* t6 ^5 }) o
4.         listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
   " `, t3 m$ e. {4 F% y: v/ {
5.         listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
   & A- K2 H; h# Y2 N7 e
6. }

复制代码

6 T& I. q8 T- Y; C6 u  c/ A列表项的初始化只是将列表项成员变量pvContainer初始化为NULL，并给用于完整性检查的变量赋值。

8 ~& V$ I3 {9 z# S3. 列表项插入
" ^7 g8 t2 O1 x! B' m& ^# g$ A' h3.1 列表项插入函数分析
+ M! O: O* c! O$ l0 a+ R  L, A. y列表项的插入操作用vListInsert()完成：
/ W1 u4 R% ~& e: G& L3 m

1. void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
   
2. {
   - A& d6 Y4 ?$ E% S0 }4 i- |
3.         ListItem_t *pxIterator;
   
4.         const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;  // 获取要插入的列表项值
   
5.         listTEST_LIST_INTEGRITY( pxList );
   
6.         listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
   0 V8 y( Q. U( k$ w! D0 u/ {
7.         // 判断插入列表项的值是否等于portMAX_DELAY，即列表项最大值，是的话就插入列表的最末尾
   
8.         if( xValueOfInsertion == portMAX_DELAY )
   
9.         // 获取要插入点，xListEnd表示列表末尾，初始化时xListEnd=portMAX_DELAY，此时要插入的列表项的列表值也是portMAX_DELAY,放在前面
   6 N! u: D  |; b# b9 Y
10.         {        pxIterator = pxList->xListEnd.pxPrevious;        }
    
11.         else
    
12.         {
    
13.                 // 否则，需要在列表中一个一个的找位置，for循环就是找位置的过程，当找到合适的列表项位置时就跳出。
    4 Z' j7 J! }$ l
14.                 for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd );
    
15.                 pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
    5 y$ D) \  c9 E0 @: c% w+ R4 A
16.                 {        /* 空循环 */        }
    " y& b- Y( c# @* @! ^; Q
17.         }
    
18.         // 经过上面查找，找到列表项插入点。以下四行代码是将列表项插入到列表中，
    
19.     pxNewListItem->pxNext = pxIterator->pxNext;
    ) z# X0 e9 ^! l/ i6 f- |. j
20.         pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    
21.         pxNewListItem->pxPrevious = pxIterator;
    : c. I- c3 Y# J4 G# U4 {6 a; X* I3 f
22.         pxIterator->pxNext = pxNewListItem;
    , A" d' k/ d  V) ~: C
23.         // 列表项已经插入到列表中，那么成员变量pvContainer也记录此列表项属于哪个列表
    
24.         pxNewListItem->pvContainer = ( void * ) pxList;
    
25.         // 列表的成员变量uxNumberOfItems加一，表示添加一个列表项
    
26.         ( pxList->uxNumberOfItems )++;
    
27. }

复制代码

3.2 列表项插入过程示意图

* N' ], T7 E! Z1）插入值为40的列表项
在一个空列表List中插入一个列表值为40的列表项ListItem1，完成后如图：
, ?9 }" _' M& n9 r, w

& n; U  b7 y' H/ s& k  w! \% ~
3 m% ~* P' n" o* a5 |由图可知，列表List和列表项ListItem1中，uxNumberOfItem值为1，表示现在列表中有一个列表项，pvContainer值为List，表示该列表项属于List，此列表是一个环形列表！

* p* ^9 }. ?6 C! Z  B8 K) p2）再插入值为60的列表项
& O& V- _3 d' c8 z# B' O9 p% ?$ [完成后如下图：



9 f' F5 q5 r* S列表项是按照升序的方式插入的，所以ListItem2是插入到ListItem1的后面、xListEnd的前面。
3 i" R  ^# O" X/ j/ R0 P
3）在插入值为50的列表项
& f4 C& Q$ r/ X& i9 [完成后如下图所示：
8 K+ E6 X5 B+ P, k  u; ]
! p6 E  \$ s( L- v$ F8 @2 H7 n& C

按照升序排列的方式，ListItem3放到ListItem1和ListItem2中间。
) Z! ]) M! M  F- w& |
4. 列表项末尾插入
4.1 列表项末尾插入函数分析
列表末尾插入列表项的操作通过函数vListInsertEnd()实现：
0 ~0 e1 z' t* _3 ^# X
$ f; ~, @9 x: }+ z, \

1. void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
   6 A$ d$ x% U; _; s4 J1 w
2. {
   
3.         ListItem_t * const pxIndex = pxList->pxIndex;
   
4.         listTEST_LIST_INTEGRITY( pxList );              // 列表完整性检查
   * i! c5 W$ h, i/ }) A! @% H$ u5 j
5.         listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );  // 列表项完整性检查
   
6.         // 将要插入的列表项插入列表末尾，往列表的末尾添加列表项，由成员变量pxIndex确定，pxIndex指向列表项代表列表头，新列表项插入到pxIndex前面
   5 F5 y% @) b$ P% K
7.         pxNewListItem->pxNext = pxIndex;
   + v) h2 z# S- {+ w2 B9 f
8.         pxNewListItem->pxPrevious = pxIndex->pxPrevious;
   
9.         mtCOVERAGE_TEST_DELAY();
   6 ^  [. j  U* x% L7 C3 c0 H# ^0 O
10.         pxIndex->pxPrevious->pxNext = pxNewListItem;
    
11.         pxIndex->pxPrevious = pxNewListItem;
    
12.         pxNewListItem->pvContainer = ( void * ) pxList;   // 标记新的列表项pxNewListItem，属于列表PxList
    , C. ?; W+ _% N% X1 O& ~' C! ]$ ?* [# v
13.         ( pxList->uxNumberOfItems )++;                    // 记录列表中的列表项数目的变量加一
    
14. }

复制代码

+ ~' O, b* J3 y" x; T- b, F" Z2 ]4.2 列表项末尾插入图示
" g( I! s9 k: t  l! c# j0 w
1）默认列表
在插入列表项前准备一个默认列表：

3 x: H. M6 K( J7 N0 }3 m
% Y. n: A. m7 ~" \; O( O2 m$ Y# t5 p
注意pxIndex指向的列表项为ListItem1。
$ P. x+ v) @$ ~3 I& H
2） 插入值为50的列表项
6 z  |' l/ V* s6 f- x在上面的列表中插入值为50的列表项ListItem3，插入完成后如图：


2 A0 p3 ~/ d$ d- x% H8 K
列表List的pxIndex指向列表项的ListItem1，因此用vListInsertEnd()函数插入ListItem3的话就会在ListItem1的前面插入。
+ [% `9 E$ F' [% N4 W+ x8 r
5. 列表项的删除
列表项的删除通过函数uxListRemove()完成，如下：
8 [2 f" ]2 K+ a' L

1. UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
   $ E" h$ |( ~' x$ v# t
2. {
   # Z/ s( b  \" [
3.         // 读取列表项成员变量pvContainer获知此列表项处于哪个列表中
   7 i) B! P3 `! E" ]9 W5 g; G
4.         List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
   
5.         // 与下面一行代码完成列表项的删除
   
6.         pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
   , ^/ J3 D7 H9 h- b
7.         pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
   ( G8 z# [& a! x0 h4 I5 E
8.         mtCOVERAGE_TEST_DELAY();
   
9.         if( pxList->pxIndex == pxItemToRemove )
   8 o1 j  b$ v4 I2 N4 \
10.         // 如果pxIndex正好指向要删除的列表项，那么删除后要重新给pxIndex找对象，新对象是被删除的列表项的前一个列表项
    ! g5 Z3 J: V7 k( e* y" z- J  B
11.         {        pxList->pxIndex = pxItemToRemove->pxPrevious;        }
    1 @+ v* r  y1 {0 f1 k, i
12.         else        {        mtCOVERAGE_TEST_MARKER();        }
    
13.         pxItemToRemove->pvContainer = NULL;  // 被删除的列表项的成员变量pvContainer清零
    + n, n3 J1 F4 T0 ^, g
14.         ( pxList->uxNumberOfItems )--;
    # S: T  r6 a) O1 ^. Q
15.         return pxList->uxNumberOfItems;      // 返回新列表的当前列表项数目
    
16. }

复制代码

$ k* N! V- C" w3 E4 }( j3 a6. 列表的遍历
/ y" [  I8 w3 c$ ~; O' E介绍列表结构体的时候说过列表List_t中的成员变量pxIndex用来遍历列表的，FreeRTOS提供了一个函数来完成列表的遍历，这个函数是listGET_OWNER_OF_NEXT_ENTRY()。每调用一次这个函数列表的pxIndex变量就会指向下一个列表项，并且返回这个列表项的pxOwner变量值。这个函数本质上是一个宏，在list.h如下定义：
, e; ]5 J" P0 F3 z3 E' D

1. // pxTCB用来保存pxIndex所指向的列表项的pvOwner变量值。pxList表示要遍历的列表
   
2. #define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                                                                
   
3. {                                                                                                                                                                                       
   
4.         List_t * const pxConstList = ( pxList );                                                                                                                                                        
   & `( {  B  h, R1 v* @
5.         ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;        // PxIndex变量指向下一个列表项
   6 c3 ^4 \/ }5 m$ s5 e$ F+ x5 o
6.         // 如果pxIndex指向列表的xListEnd成员变量，表示到列表末尾                                                
   
7.         if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )        
   
8.         {        // 如果到列表末尾的话就跳过xListEnd，pxIndex再一次重新指向处于列表头的列表项，完成一次对列表的遍历                                                                                                                                                                        
   " D, O, y# l6 X) A
9.                 ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                                                
   
10.         }                                                                                                                                                                                
    & u3 C" A/ N5 h7 D' M
11.         ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;        // 将pxIndex所指向的新列表项的pvOwner赋值为pxTCB                                                                                
    , _2 F. J9 D# M. n7 S4 |
12. }

复制代码

————————————————
) }. l9 U$ n+ u+ ~" c版权声明：天亮继续睡
- G8 s* t5 i; W" Q
1 E( m- @% L2 N* A  `9 d5 S9 _# L4 F