從零開始，教你寫FreeRTOS雙向鏈表

嵌入式ARM 2022-07-11 12:00

瑞薩×物聯(lián)網(wǎng)：4 場直播，搞定全棧無線連接開發(fā) 汽車電子架構(gòu)重構(gòu)與智能連接革命

摘要：前幾天給大家講了單向鏈表，今天再結(jié)合FreeRTOS的鏈表源碼，說一下雙向鏈表。

注：鏈表項(xiàng)就是節(jié)點(diǎn)，節(jié)點(diǎn)就是鏈表項(xiàng)，都是指的一個東西，叫啥都無所謂。

一、定義鏈表結(jié)構(gòu)體

//定義鏈表，同時也是鏈表頭
typedef?struct?xLIST
{??
????volatile?unsigned???int?uxNumberOfItems;???
????ListItem_t?*??pxIndex;?
????MiniListItem_t?xListEnd;??????????????????????????
}?List_t;

二、定義mini節(jié)點(diǎn)項(xiàng)

迷你節(jié)點(diǎn)也是節(jié)點(diǎn)，但迷你節(jié)點(diǎn)僅用于標(biāo)記鏈表的末尾和掛載其他插入鏈表中的節(jié)點(diǎn)，用戶是用不到迷你節(jié)點(diǎn)的，鏈表頭節(jié)點(diǎn)和普通節(jié)點(diǎn)可以不一樣。

typedef?struct?xMINI_LIST_ITEM
{
????volatile?unsigned???int?xItemValue;???/*?輔助值，用于幫助節(jié)點(diǎn)做升序排列.?*/
????struct?xLIST_ITEM???*?pxNext;?
????struct?xLIST_ITEM???*?pxPrevious;
}MiniListItem_t;

下面這個頭即使鏈表定義，也是鏈表頭，鏈表頭節(jié)點(diǎn)和普通節(jié)點(diǎn)可以不一樣。

三、定義節(jié)點(diǎn)

節(jié)點(diǎn)在FreeRTOS中叫做鏈表項(xiàng)。

//定義鏈表節(jié)點(diǎn)
typedef?struct?xLIST_ITEM
{???????
????volatile?unsigned???int??xItemValue;??????????
????struct?xLIST_ITEM?*??pxNext;?????
????struct?xLIST_ITEM?*??pxPrevious;?
????void?*?pvOwner;???????????????????????//用于指向該節(jié)點(diǎn)的擁有者??????????????
????struct?xLIST?*??pxContainer;??????????//用于指向該節(jié)點(diǎn)所在的鏈表，通常指向鏈表的根節(jié)點(diǎn)
??????????????
}ListItem_t;

四、初始化鏈表

初始化鏈表就是給鏈表的頭結(jié)點(diǎn)各個參數(shù)賦值。

void?vListInitialise(?List_t?*?const?pxList)
{
????/*初始化時，列表中的列表項(xiàng)數(shù)量為?0（不包含?xListEnd）?*/
????pxList->uxNumberOfItems?=?0;????
????/*?初始化時，列表中只有?xListEnd，因此?pxIndex?指向?xListEnd?*/
????pxList->pxIndex?=?(ListItem_t?*)?&(pxList->xListEnd);?
????/*?xListEnd?的值初始化為最大值，用于列表項(xiàng)升序排序時，排在最后?*/
????pxList->xListEnd.xItemValue?=?portMAX_DELAY;????
????/*?初始化時，列表中只有?xListEnd，因此上一個和下一個列表項(xiàng)都為?xListEnd?本身?*/
????pxList->xListEnd.pxNext?=(ListItem_t?*)?&(pxList->xListEnd);?
????pxList->xListEnd.pxPrevious?=?(ListItem_t?*)?&(pxList->xListEnd);?
}

五、初始化節(jié)點(diǎn)

void?vListInitialiseItem(ListItem_t?*?const?pxItem?)
{
???/*?初始化時，列表項(xiàng)所在列表設(shè)為空?*/
????pxItem->pxContainer?=?NULL;
}

六、將節(jié)點(diǎn)插入到鏈表的尾部

void?vListInsertEnd(?List_t?*?const?pxList,ListItem_t?*?const?pxNewListItem?)
{
????/*?獲取列表?pxIndex?指向的列表項(xiàng)?*/
????ListItem_t?*?const?headEnd?=?pxList->pxIndex;
????/*?更新待插入列表項(xiàng)的指針成員變量?*/
????pxNewListItem->pxNext?=?headEnd;
????pxNewListItem->pxPrevious?=?headEnd->pxPrevious;
????/*?更新列表中原本列表項(xiàng)的指針成員變量?*/
????headEnd->pxPrevious->pxNext?=?pxNewListItem;
????headEnd->pxPrevious?=?pxNewListItem;
????????/*?標(biāo)記待插入列表項(xiàng)的所在列表成員變量?*/
????pxNewListItem->pxContainer?=?pxList;
???/*?列表中列表項(xiàng)的數(shù)量+1?*/
????(pxList->uxNumberOfItems)++;
}

此函數(shù)就是將待插入的列表項(xiàng)插入到列表 pxIndex 指向列表項(xiàng)的前面，要注意的時，pxIndex 不一定指向 xListEnd，而是有可能指向列表中任意一個列表項(xiàng)。

我手畫一張圖來解釋吧！

七、鏈表節(jié)點(diǎn)插入并排序

void?vListInsert(?List_t?*?const?pxList,ListItem_t?*?const?pxNewListItem?)
{
????ListItem_t?*?pxIterator;
????const?int?xValueOfInsertion?=?pxNewListItem->xItemValue;

????/*?如果待插入列表項(xiàng)的值為最大值?*/
????if(?xValueOfInsertion?==?portMAX_DELAY)
????{
????????/*?插入的位置為列表?xListEnd?前面?*/
????????pxIterator?=?pxList->xListEnd.pxPrevious;
????}
????else
????{
?????????/*?遍歷列表中的列表項(xiàng)，找到插入的位置?*/
????????for(?pxIterator?=?(ListItem_t*)&(pxList->xListEnd);?pxIterator->pxNext->xItemValue?<=?xValueOfInsertion;?pxIterator?=?pxIterator->pxNext?)
????????{
????????????
????????}
????}
?/*?根據(jù)升序排列，將節(jié)點(diǎn)插入??在pxIterator后面插入新節(jié)點(diǎn)*/???
????pxNewListItem->pxNext?=?pxIterator->pxNext;
????pxNewListItem->pxNext->pxPrevious?=?pxNewListItem;
????pxNewListItem->pxPrevious?=?pxIterator;
????pxIterator->pxNext?=?pxNewListItem;
?????
????/*?記住該節(jié)點(diǎn)所在的鏈表?*/
????pxNewListItem->pxContainer?=?pxList;
???/*?鏈表節(jié)點(diǎn)計(jì)數(shù)器++?*/
????(?pxList->uxNumberOfItems?)++;
}

在將待插入列表項(xiàng)插入列表之前，會前遍歷列表，找到待插入列表項(xiàng)需要插入的位置。待插入列表項(xiàng)需要插入的位置，是依照列表中列表項(xiàng)的值，按照升序排序確定的。

八、刪除鏈表節(jié)點(diǎn)

int?uxListRemove(?ListItem_t?*?const?pxItemToRemove?)
{
?/*?獲取節(jié)點(diǎn)所在的鏈表?*/
????List_t?*?const?pxList?=?pxItemToRemove->pxContainer;
?
?/*?將指定的節(jié)點(diǎn)從鏈表刪除*/
????pxItemToRemove->pxNext->pxPrevious?=?pxItemToRemove->pxPrevious;
????pxItemToRemove->pxPrevious->pxNext?=?pxItemToRemove->pxNext;
????

????/*?如果?pxIndex?正指向待移除的列表項(xiàng)?*/
????if(?pxList->pxIndex?==?pxItemToRemove?)
????{
????????/*?pxIndex?指向上一個列表項(xiàng)?*/
????????pxList->pxIndex?=?pxItemToRemove->pxPrevious;
????}
????else
????{

????}
???/*?將待移除列表項(xiàng)的所在列表指針清空?*/
????pxItemToRemove->pxContainer?=?NULL;
???/*?鏈表節(jié)點(diǎn)計(jì)數(shù)器--?*/
????(?pxList->uxNumberOfItems?)--;
???/*?返回鏈表中剩余節(jié)點(diǎn)的個數(shù)?*/
????return?pxList->uxNumberOfItems;
}

要刪除節(jié)點(diǎn)，首先就必須要找到節(jié)點(diǎn)。

需要注意的是，函數(shù) uxListRemove()移除后的列表項(xiàng)，依然于列表有著單向聯(lián)系，即移除后列表項(xiàng)中用于指向上一個和下一個列表項(xiàng)的指針，依然指向列表中的列表項(xiàng)。

九、實(shí)例

#include?
#include?
#include?

//定義鏈表節(jié)點(diǎn)
typedef?struct?xLIST_ITEM
{???????
????volatile?unsigned???int??xItemValue;??????????
????struct?xLIST_ITEM?*??pxNext;?????
????struct?xLIST_ITEM?*??pxPrevious;?
????void?*?pvOwner;???????????????????????//用于指向該節(jié)點(diǎn)的擁有者??????????????
????struct?xLIST?*??pxContainer;??????????//用于指向該節(jié)點(diǎn)所在的鏈表，通常指向鏈表的根節(jié)點(diǎn)
??????????????
}ListItem_t;

typedef?struct?xMINI_LIST_ITEM
{
????volatile?unsigned???int?xItemValue;???/*?輔助值，用于幫助節(jié)點(diǎn)做升序排列.?*/
????struct?xLIST_ITEM???*?pxNext;?
????struct?xLIST_ITEM???*?pxPrevious;
}MiniListItem_t;

//定義鏈表，同時也是鏈表頭
typedef?struct?xLIST
{??
????volatile?unsigned???int?uxNumberOfItems;???
????ListItem_t?*??pxIndex;?
????MiniListItem_t?xListEnd;??????????????????????????
}?List_t;

void?vListInitialise(?List_t?*?const?pxList)
{
????pxList->uxNumberOfItems?=?0;????
????pxList->pxIndex?=?(ListItem_t?*)?&(pxList->xListEnd);?
????pxList->xListEnd.xItemValue?=?100;????
????pxList->xListEnd.pxNext?=(ListItem_t?*)?&(pxList->xListEnd);?????/*lint?!e826?!e740?!e9087?The?mini?list?structure?is?used?as?the?list?end?to?save?RAM.??This?is?checked?and?valid.?*/
????pxList->xListEnd.pxPrevious?=?(ListItem_t?*)?&(pxList->xListEnd);?/*lint?!e826?!e740?!e9087?The?mini?list?structure?is?used?as?the?list?end?to?save?RAM.??This?is?checked?and?valid.?*/
}

void?vListInitialiseItem(ListItem_t?*?const?pxItem?)
{
????pxItem->pxContainer?=?NULL;
}
//列表項(xiàng)(節(jié)點(diǎn))末尾插入函數(shù)，將節(jié)點(diǎn)插入到鏈表的尾部??
void?vListInsertEnd(?List_t?*?const?pxList,ListItem_t?*?const?pxNewListItem?)
{
????ListItem_t?*?const?headEnd?=?pxList->pxIndex;

????pxNewListItem->pxNext?=?headEnd;
????pxNewListItem->pxPrevious?=?headEnd->pxPrevious;

????headEnd->pxPrevious->pxNext?=?pxNewListItem;
????headEnd->pxPrevious?=?pxNewListItem;
????
????/*?記住該節(jié)點(diǎn)所在的鏈表.?*/
????pxNewListItem->pxContainer?=?pxList;
?
????(pxList->uxNumberOfItems)++;
}

void?vListInsert(?List_t?*?const?pxList,ListItem_t?*?const?pxNewListItem?)
{
????ListItem_t?*?pxIterator;
????const?int?xValueOfInsertion?=?pxNewListItem->xItemValue;


????if(?xValueOfInsertion?==?100?)
????{
????????pxIterator?=?pxList->xListEnd.pxPrevious;
????}
????else
????{
????????for(?pxIterator?=?(ListItem_t*)&(pxList->xListEnd);?pxIterator->pxNext->xItemValue?<=?xValueOfInsertion;?pxIterator?=?pxIterator->pxNext?)
????????{
????????????
????????}
????}
?/*?根據(jù)升序排列，將節(jié)點(diǎn)插入??在pxIterator后面插入新節(jié)點(diǎn)*/???
????pxNewListItem->pxNext?=?pxIterator->pxNext;
????pxNewListItem->pxNext->pxPrevious?=?pxNewListItem;
????pxNewListItem->pxPrevious?=?pxIterator;
????pxIterator->pxNext?=?pxNewListItem;
?????
????/*?記住該節(jié)點(diǎn)所在的鏈表?*/
????pxNewListItem->pxContainer?=?pxList;
?/*?鏈表節(jié)點(diǎn)計(jì)數(shù)器++?*/
????(?pxList->uxNumberOfItems?)++;
}
int?uxListRemove(?ListItem_t?*?const?pxItemToRemove?)
{
?/*?獲取節(jié)點(diǎn)所在的鏈表?*/
????List_t?*?const?pxList?=?pxItemToRemove->pxContainer;
?
?/*?將指定的節(jié)點(diǎn)從鏈表刪除*/
????pxItemToRemove->pxNext->pxPrevious?=?pxItemToRemove->pxPrevious;
????pxItemToRemove->pxPrevious->pxNext?=?pxItemToRemove->pxNext;
????

????/*調(diào)整鏈表的節(jié)點(diǎn)索引指針?*/
????if(?pxList->pxIndex?==?pxItemToRemove?)
????{
????????pxList->pxIndex?=?pxItemToRemove->pxPrevious;
????}
????else
????{

????}
?/*?初始化該節(jié)點(diǎn)所在的鏈表為空，表示節(jié)點(diǎn)還沒有插入任何鏈表?*/
????pxItemToRemove->pxContainer?=?NULL;
?/*?鏈表節(jié)點(diǎn)計(jì)數(shù)器--?*/
????(?pxList->uxNumberOfItems?)--;
?/*?返回鏈表中剩余節(jié)點(diǎn)的個數(shù)?*/
????return?pxList->uxNumberOfItems;
}

/*?定義鏈表根節(jié)點(diǎn)?*/
struct?xLIST?List_Test;

/*?定義節(jié)點(diǎn)?*/
struct?xLIST_ITEM?List_Item1;
struct?xLIST_ITEM?List_Item2;
struct?xLIST_ITEM?List_Item3;

int?main(void)
{
????/*?定義鏈表根節(jié)點(diǎn)?*/
????struct?xLIST?List_Test;

????/*?定義節(jié)點(diǎn)?*/
????struct?xLIST_ITEM?List_Item1;
????struct?xLIST_ITEM?List_Item2;
????struct?xLIST_ITEM?List_Item3;
????
????/*?鏈表根節(jié)點(diǎn)初始化?*/
????vListInitialise(&List_Test);?

????/*?節(jié)點(diǎn)?1?初始化?*/
????vListInitialiseItem(&List_Item1);
????List_Item1.xItemValue?=?1;

????/*?節(jié)點(diǎn)?2?初始化?*/
????vListInitialiseItem(&List_Item2);
????List_Item2.xItemValue?=?2;

????/*?節(jié)點(diǎn)?3?初始化?*/
????vListInitialiseItem(&List_Item3);
????List_Item3.xItemValue?=?3;

????/*?將節(jié)點(diǎn)插入鏈表，按照升序排列?*/?
????vListInsert(?&List_Test,?&List_Item2);
????vListInsert(?&List_Test,?&List_Item1);
????vListInsert(?&List_Test,?&List_Item3);
?
?while(1);
}

然后隨便找個32的代碼，用keil仿真試一試。

仔細(xì)看一下這張圖：

這個其實(shí)就是FreeRTOS的鏈表源碼，是不是很簡單？

工程下載源碼：

鏈接：https://pan.baidu.com/s/1g34z7l3MSrf12lawF4hKLA?pwd=o8xc?
提取碼：o8xc

其實(shí)這個工程是一個普通的裸機(jī)例程，只是加入了FreeRTOS的鏈表源碼，建議大家自己動手試一下，深入理解鏈表。因?yàn)橐雽W(xué)好任何一個RTOS，必須掌握的基礎(chǔ)知識就是鏈表和隊(duì)列！

END

來源：果果小師弟

版權(quán)歸原作者所有，如有侵權(quán)，請聯(lián)系刪除。

▍推薦閱讀

手把手教你搭建一個輕量級電子實(shí)驗(yàn)室

如何寫一個健壯且高效的串口接收程序？

大規(guī)模裁員后，計(jì)算機(jī)專業(yè)會成下一個土木嗎？

→點(diǎn)關(guān)注，不迷路←

登錄閱讀全文



免責(zé)聲明：該內(nèi)容由專欄作者授權(quán)發(fā)布或作者轉(zhuǎn)載，目的在于傳遞更多信息，并不代表本網(wǎng)贊同其觀點(diǎn)，本站亦不保證或承諾內(nèi)容真實(shí)性等。若內(nèi)容或圖片侵犯您的權(quán)益，請及時聯(lián)系本站刪除。侵權(quán)投訴聯(lián)系：? nick.zong@aspencore.com！

嵌入式ARM 關(guān)注這個時代最火的嵌入式ARM，你想知道的都在這里。

進(jìn)入專欄

評論

嵌入式ARM 關(guān)注這個時代最火的嵌入式ARM，你想知道的都在這里。

文章：3798篇粉絲：197人

 私信

從零開始，教你寫FreeRTOS雙向鏈表

一、定義鏈表結(jié)構(gòu)體

二、定義mini節(jié)點(diǎn)項(xiàng)

三、定義節(jié)點(diǎn)

四、初始化鏈表

五、初始化節(jié)點(diǎn)

六、將節(jié)點(diǎn)插入到鏈表的尾部

七、鏈表節(jié)點(diǎn)插入并排序

八、刪除鏈表節(jié)點(diǎn)

九、實(shí)例

最近文章

熱門文章

推薦

最新資訊

從零開始，教你寫FreeRTOS雙向鏈表

一、定義鏈表結(jié)構(gòu)體

二、定義mini節(jié)點(diǎn)項(xiàng)

三、定義節(jié)點(diǎn)

四、初始化鏈表

五、初始化節(jié)點(diǎn)

六、將節(jié)點(diǎn)插入到鏈表的尾部

七、鏈表節(jié)點(diǎn)插入并排序

八、刪除鏈表節(jié)點(diǎn)

九、實(shí)例

最近文章

熱門文章

推薦

最新資訊

從零開始，教你寫FreeRTOS雙向鏈表

二、定義mini節(jié)點(diǎn)項(xiàng)

三、定義節(jié)點(diǎn)

五、初始化節(jié)點(diǎn)

六、將節(jié)點(diǎn)插入到鏈表的尾部

七、鏈表節(jié)點(diǎn)插入并排序

九、實(shí)例