文章目錄
- 一、列表與列表項
- 1.1.列表與列表項的簡介
- 1.2.列表與列表項相關結構體
- 1.2.1.列表結構體
- 1.2.2.列表項結構體
- 1.2.3.迷你列表項
- 二、列表相關API函數
- 2.1.列表相關API函數介紹
- 2.1.1.`vListInitalise( )`初始化列表函數
- 2.1.2.`vListInitaliseItem( )`初始化列表項函數
- 2.1.3.`vListInsertEnd( )`列表末尾插入列表項函數
- 2.1.4.`vListInsert( )`列表插入列表項函數
- 2.1.5.`vListRemove( )`列表移除列表項函數
- 三、列表項的插入和刪除實驗
- 3.1.實驗設計
- 3.2.軟件設計
- 3.2.1.列表插入列表項
- 3.2.2.列表移除列表項
- 3.2.3.列表末尾插入列表項
一、列表與列表項
1.1.列表與列表項的簡介
列表是 FreeRTOS 中的一個數據結構,概念上和鏈表有點類似,列表被用來追蹤 FreeRTOS 中的任務,列表項就是存放在列表中的項目;列表相當于鏈表,列表項相當于節點,FreeRTOS 中的列表是一個雙向環形鏈表,列表和列表項的關系和下圖所示:
下面這幾點說明了使用鏈表的好處:
- 列表的特點:列表項間的地址非連續,是人為的連接到一起的,列表項的數目是由后期添加的個數決定的,隨時可以改變。
- 數組的特點:數組成員地址是連續的,數組在最初確定了成員數量后期無法改變。
- 在 OS 中任務的數量是不確定的,并且任務狀態是會發生改變的,所以非常適用列表這種數據結構
1.2.列表與列表項相關結構體
1.2.1.列表結構體
有關列表的均在文件 list.c 和 list.h 中,下面代碼是 list.h 文件有關列表相關的結構體:
typedef struct xLIST
{listFIRST_LIST_INTEGRITY_CHECK_VALUE /* 校驗值 */volatile UBaseType_t uxNumberOfItems; /* 列表中列表項的數量 */ListItem_t *configLIST_VOLATILE pxIndex; /* 用于遍歷列表 */MiniListItem_t xListEnd; /* 最后一個列表項 */listSECOND_LIST_INTEGRITY_CHECK_VALUE /* 校驗值 */
} List_t;
- 在該結構體中,包含了兩個宏,這兩個宏是確定的已知常量,FreeRTOS 通過檢查這兩個常量的值,來判斷列表的數據在程序運行過程中,是否遭到破壞,該功能一般用于調試,默認是不開啟的
- 成員
uxNumberOfItems
,用于記錄列表中列表項的個數(不包含 xListEnd) - 成員
pxIndex
用于指向列表中的某個列表項,一般用于遍歷列表中的所有列表項 - 成員變量
xListEnd
是一個迷你列表項,排在最末尾
下圖是列表結構示意圖:
1.2.2.列表項結構體
有關列表項的均在文件 list.c 和 list.h 中,下面代碼是 list.h 文件有關列表項相關的結構體:
struct xLIST_ITEM
{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /* 用于檢測列表項的數據完整性 */configLIST_VOLATILE TickType_t xItemValue; /* 列表項的值 */struct xLIST_ITEM * configLIST_VOLATILE pxNext; /* 下一個列表項 */struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /* 上一個列表項 */void * pvOwner; /* 列表項的擁有者 */struct xLIST * configLIST_VOLATILE pxContainer; /* 列表項所在列表 */listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /* 用于檢測列表項的數據完整性 */
};
typedef struct xLIST_ITEM ListItem_t; /* 重定義成 ListItem_t */
- 成員變量
xItemValue
為列表項的值,這個值用于按升序對列表中的列表項進行排序,例如:有任務一,數值是10;任務二,數值是20;任務三,數值是30,添加一個任務四,數值是25,任務四應該加入在任務二和任務三之間 - 成員變量
pxNext
和pxPrevious
分別用于指向列表中列表項的下一個列表項和上一個列表項 - 成員變量
pvOwner
用于指向包含列表項的對象(通常是任務控制塊) - 成員變量
pxContainer
用于指向列表項所在列表,例如:運行態、就緒態、堵塞態、掛起態
下圖是列表項結構示意圖:
1.2.3.迷你列表項
迷你列表項也是列表項,但迷你列表項僅用于標記列表的末尾和掛載其他插入列表中的列表項,用戶是用不到迷你列表項的,在 list.h 文件中,有迷你列表項的相關定義,具體的代碼所示:
struct xMINI_LIST_ITEM
{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /* 用于檢測列表項的數據完整性 */configLIST_VOLATILE TickType_t xItemValue; /* 列表項的值 */struct xLIST_ITEM * configLIST_VOLATILE pxNext; /* 下一個列表項 */struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /* 上一個列表項 */
};
typedef struct xMINI_LIST_ITEM MiniListItem_t; /* 重定義成 MiniListItem_t */
- 成員變量
xItemValue
為列表項的值,這個值多用于按升序對列表中的列表項進行排序。 - 成員變量
pxNext
和pxPrevious
分別用于指向列表中列表項的下一個列表項和上一個列
表項。 - 迷你列表項相比于列表項,因為只用于標記列表的末尾和掛載其他插入列表中的列表項,
因此不需要成員變量pxOwner
和pxContainer
,以節省內存開銷。
掛載其他插入列表中的列表項:初始化列表的時候總需要一個列表項提供指向上一個和下一個的指針,用于掛載新來的列表項,迷你列表項結構示意圖如下圖所示:
二、列表相關API函數
2.1.列表相關API函數介紹
函數 | 描述 |
---|---|
vListInitalise( ) | 初始化列表 |
vListInitaliseItem( ) | 初始化列表項 |
vListInsertEnd( ) | 列表末尾插入列表項(無序排列) |
vListInsert( ) | 列表插入列表項(升序排列) |
vListRemove( ) | 列表移除列表項 |
2.1.1.vListInitalise( )
初始化列表函數
下面代碼實現的功能是將列表結構體里面的成員賦值,將遍歷列表的指針指向最后一個列表項;將列表項的值初始化至最大值為0xFFFFFFFF;將指向上一個和下一個的指針指向最后一個列表項;將列表中的列表項數量賦值為 0:
void vListInitialise(List_t * const pxList) //參數內容:待初始化列表
{/* 初始化時,列表中只有 xListEnd,因此 pxIndex 指向 xListEnd */pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );/* xListEnd 的值初始化為最大值,用于列表項升序排序時,排在最后 */pxList->xListEnd.xItemValue = portMAX_DELAY;/* 初始化時,列表中只有 xListEnd,因此上一個和下一個列表項都為 xListEnd 本身 */pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/*初始化時,列表中的列表項數量為 0(不包含 xListEnd) */pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
}
下圖是初始化后列表的結構圖:
2.1.2.vListInitaliseItem( )
初始化列表項函數
該函數只是把列表項所在列表指針指向空,其他成員都沒有改動:
void vListInitialiseItem(ListItem_t * const pxItem) //參數內容:待初始化列表項
{/* 初始化時,列表項所在列表設為空 */pxItem->pxContainer = NULL;}
下圖是初始化后的列表項結構圖:
2.1.3.vListInsertEnd( )
列表末尾插入列表項函數
該函數用于新的列表項插入 pxIndex 指針指向的列表項的前面,是一種無序的插入方法,它的參數有兩個,第一個是需要插入的列表;第二個是新的列表項:
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->pxContainer = pxList;/* 更新列表中列表項的數量 */( pxList->uxNumberOfItems )++;
}
下圖插入列表項后的列表結構圖:
2.1.4.vListInsert( )
列表插入列表項函數
該函數用于新的列表項按升序排列插入列表,它有兩個參數,第一個參數是需要插入的列表;第二個是待插入的新列表項:
void vListInsert(List_t * const pxList, ListItem_t * const pxNewListItem)
{//先定義一個指針用于尋找待插入的新列表項的上一個列表項,再定義一個變量用于獲取新列表項的值用于比較ListItem_t * pxIterator;const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;/* 如果待插入列表項的值為最大值 */if( xValueOfInsertion == portMAX_DELAY ){/* 插入的位置為列表 xListEnd 前面 */pxIterator = pxList->xListEnd.pxPrevious;}else{/* 遍歷列表中的列表項,找到插入的位置 */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;/* 更新待插入列表項所在列表 */pxNewListItem->pxContainer = pxList;/* 更新列表中列表項的數量 */( pxList->uxNumberOfItems )++;
}
下圖是插入列表項后的列表結構圖:
2.1.5.vListRemove( )
列表移除列表項函數
該函數用于將列表項所在列表中移除,它的參數是待移除的列表項,返回值是一個整數,表示所在列表剩余的列表項的數量:
UBaseType_t uxListRemove(ListItem_t * const pxItemToRemove)
{List_t * const pxList = pxItemToRemove->pxContainer;/* 從列表中移除列表項 */pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;/* 如果 pxIndex 正指向待移除的列表項 */if( pxList->pxIndex == pxItemToRemove ){/* pxIndex 指向上一個列表項 */pxList->pxIndex = pxItemToRemove->pxPrevious;}else{mtCOVERAGE_TEST_MARKER();}/* 將待移除列表項的所在列表指針清空 */pxItemToRemove->pxContainer = NULL;/* 更新列表中列表項的數量 */( pxList->uxNumberOfItems )--;/* 返回列表項移除后列表中列表項的數量 */return pxList->uxNumberOfItems;
}
下圖是移除列表項后的列表結構圖:
三、列表項的插入和刪除實驗
3.1.實驗設計
設計三個任務如下所示:
- start_task:用來創建下面兩個任務
- task1:實現 LED0 每 500ms 閃爍一次,用來提示系統正在運行
- task2:調用列表和列表項相關的 API 函數,并且通過串口輸出相應信息
3.2.軟件設計
在 FreeRTOS 入口函數前面,定義測試列表和三個列表項:
List_t TestList;
ListItem_t ListItem1;
ListItem_t ListItem2;
ListItem_t ListItem3;
并在 task2 函數里初始化列表和三個列表項,給這個三列表項進行賦值:
vListInitialise(&TestList);
vListInitialiseItem(&ListItem1);
vListInitialiseItem(&ListItem2);
vListInitialiseItem(&ListItem3);ListItem1.xItemValue = 40;
ListItem2.xItemValue = 60;
ListItem3.xItemValue = 50;
把列表項的地址打印出來,證明列表項之間的準確性。
3.2.1.列表插入列表項
在 task2 函數里面編寫所有插入和刪除函數,通過下面代碼打印,可以知道最后的列表項地址為0cc
,列表項 1、2、3 的地址分別是:
- ListItem1:
0d8
- ListItem2:
0ec
- ListItem3:
100
printf("項目\t\t\地址\r\n");
printf("TestList\t\t0x%p\t\r\n", &TestList);
printf("TestList->pxIndex\t0x%p\t\r\n", TestList.pxIndex);
printf("TestList->xListEnd\t0x%p\t\r\n", (&TestList.xListEnd));
printf("ListItem1\t\t0x%p\t\r\n", &ListItem1);
printf("ListItem2\t\t0x%p\t\r\n", &ListItem2);
printf("ListItem3\t\t0x%p\t\r\n", &ListItem3);
printf("/**************************結束***************************/\r\n");
printf("按下KEY0鍵繼續!\r\n\r\n\r\n");
while (key_scan(0) != KEY0_PRES)
{vTaskDelay(10);
}
在前面的初始化,task3 的值為 50,應該插入在 task1 和 task2 之間,下面將列表項 1、2、3 簡稱為 1、2、3;理論上來說,按升序排列,1 是最小的數值,2 是最大的數值,3 排中間,因此 1 的 Next 應該指向 3 的地址,1 的 Previous 應該指向 End (0cc
);2 的 Next 應該指向 End (0cc
),2 的 Previous 應該指向 3 的地址;而 3 的 Next 應該指向 2 的地址,3 的 Previous 應該指向 1 的地址;最后通過串口輸出的數據證明,情況確實如此:
//在列表分別插入列表項1、2、3
vListInsert((List_t* )&TestList, (ListItem_t*)&ListItem1);
vListInsert((List_t* )&TestList, (ListItem_t*)&ListItem2);
vListInsert((List_t* )&TestList, (ListItem_t*)&ListItem3);
printf("項目\t\t\地址\r\n");
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************結束***************************/\r\n");
printf("按下KEY0鍵繼續!\r\n\r\n\r\n");
while (key_scan(0) != KEY0_PRES)
{vTaskDelay(10);
}
3.2.2.列表移除列表項
本次目標是移除列表項 2,只需要證明 1 的 Next 指向 3,1 的 Previous 指向 End(0cc
);3 的 Next 指向 End(0cc
) ,3 的 Previous 指向 1:
uxListRemove((ListItem_t* )&ListItem2); //需要移除的列表項
printf("項目\t\t\地址\r\n");
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************結束***************************/\r\n");
printf("按下KEY0鍵繼續!\r\n\r\n\r\n");
while (key_scan(0) != KEY0_PRES)
{vTaskDelay(10);
}
3.2.3.列表末尾插入列表項
該函數的設定是將新的列表項,插入到 pxIndex 所指的列表項的前面,由第一個步驟可以發現,指針 pxIndex 指向 End ,因此現在新的列表項將會在 End 前面插入,輸出的結果和升序排列插入一樣:
vListInsertEnd((List_t* )&TestList, //列表(ListItem_t* )&ListItem2); //需要插入的列表項
printf("項目\t\t\地址\r\n");
printf("TestList->pxIndex\t\t0x%p\r\n", TestList.pxIndex);
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************結束***************************/\r\n");
想要將 2 插入在指定列表項之前,只需修改指針 pxIndex 所指的列表項即可,例如:在列表項 1 前面插入:
TestList.pxIndex = &ListItem1; //pxIndex指向列表項1
vListInsertEnd((List_t* )&TestList, //列表(ListItem_t* )&ListItem2); //需要插入的列表項
printf("項目\t\t\地址\r\n");
printf("TestList->pxIndex\t\t0x%p\r\n", TestList.pxIndex);
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************結束***************************/\r\n");
2 的 Next 指向 1 ;2 的 Previous 指向 End: