LiteOS雙向鏈表使用詳解

官方開放文檔中關于雙向鏈表的介紹比較簡單，并沒有告訴大家到底怎么在自己的數據結構中使用鏈表。其實也比較簡單，時間緊的朋友可以直接看第二部分。

一、雙向鏈表簡介

雙向鏈表是指含有往前和往后兩個方向的鏈表，即每個結點中除存放下一個節點指針外，還增加一個指向其前一個節點的指針。其頭指針head是唯一確定的。從雙向鏈表的任意一個節點開始，都可以很方便的訪問它的前驅和后繼節點。如下圖所示：

LiteOS雙向鏈接跟linux的內核鏈接原理一樣。LiteOS定義了雙向鏈表基本數據結構，并提供了相關的函數和宏定義來操作鏈表，用戶可以添加、刪除節點，遍歷節點等。

LiteOS雙向鏈表數據結構定義如下，包含了兩個指針，分別指向前驅和后繼節點。這是個最基本的數據結構，僅包含有雙向鏈表。

typedef?struct?LOS_DL_LIST { ????struct?LOS_DL_LIST?*pstPrev;????/**

LiteOS雙向鏈表操作函數：

VOID?LOS_ListInit(LOS_DL_LIST?*pstList) #define?LOS_DL_LIST_FIRST(pstObject)?((pstObject)->pstNext) VOID?LOS_ListAdd(LOS_DL_LIST?*pstList,?LOS_DL_LIST?*pstNode) VOID?LOS_ListTailInsert(LOS_DL_LIST?*pstList,?LOS_DL_LIST?*pstNode) VOID?LOS_ListDelete(LOS_DL_LIST?*pstNode) BOOL?LOS_ListEmpty(LOS_DL_LIST?*pstNode)?//return?(BOOL)(pstNode->pstNext?==?pstNode); //取得鏈表所在結構體地址,即根據鏈表節點的地址獲取用戶結構體地址. //item:?鏈表節點地址.用戶結構體中定義的鏈表成員的地址 //type:?用戶結構體名稱 //member:鏈表在用戶結構體中的成員名稱 #define?LOS_DL_LIST_ENTRY(item,?type,?member)?\ ????((type?*)((char?*)item?-?LOS_OFF_SET_OF(type,?member)))?\ //遍歷用戶結構體?for循環 //item:用戶結構體指針。需用戶在外定義好。 //list:?鏈表首地址 //type:?用戶結構體名稱 //member:?鏈表在用戶結構體中的成員名稱 #define?LOS_DL_LIST_FOR_EACH_ENTRY(item,?list,?type,?member)?\ ????for?(item?=?LOS_DL_LIST_ENTRY((list)->pstNext,?type,?member);?\ ????????&item->member?!=?(list);?\ ????????item?=?LOS_DL_LIST_ENTRY(item->member.pstNext,?type,?member))??? //遍歷用戶結構體,可刪除節點??for循環 //item:用戶結構體指針。需用戶在外定義好。 //next:?用戶結構體指針,指向item的下一個節點.?需用戶在外定義該變量。 //list:?鏈表首地址 //type:?用戶結構體名稱 //member:?鏈表在用戶結構體中的成員名稱???????? #define?LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item,?next,?list,?type,?member)????????????\ ????for?(item?=?LOS_DL_LIST_ENTRY((list)->pstNext,?type,?member),?\ ????????next?=?LOS_DL_LIST_ENTRY(item->member.pstNext,?type,?member);?\ ????????&item->member?!=?(list);?\ ????????item?=?next,?next?=?LOS_DL_LIST_ENTRY(item->member.pstNext,?type,?member))???? //遍歷雙向鏈表,不可有刪除節點.僅遍歷鏈表節點(不包括用戶結構體內容) //item:?鏈表指針,?需用戶定義好該變量 //list:?鏈表頭 #define?LOS_DL_LIST_FOR_EACH(item,?list)???\ ????for?((item)?=?(list)->pstNext;?\ ????????(item)?!=?(list);?\ ????????(item)?=?(item)->pstNext)???????? //安全遍歷雙向鏈表,可刪除節點.僅遍歷鏈表節點(不包括用戶結構體內容) //item:?鏈表指針,?需用戶定義好該變量 //next:?鏈表指針,?指向item下一個節點.需用戶定義好該變量 //list:?鏈表頭 #define?LOS_DL_LIST_FOR_EACH_SAFE(item,?next,?list)?\ ????for?(item?=?(list)->pstNext,?next?=?item->pstNext;?item?!=?(list);?\ ????????item?=?next,?next?=?item->pstNext)??? //?定義一個雙向鏈表節點并初始化,可用于初始化一個鏈表頭.變量名為list #define?LOS_DL_LIST_HEAD(list)?\ ????????????LOS_DL_LIST?list?=?{?&(list),?&(list)?}

二、鏈表的使用

LiteOS 內核定義的雙向鏈表跟Linux內核鏈表思想一致，它僅僅包含了兩個指針類型的變量。

用戶使用雙向鏈表時，要將雙向鏈表加入自己的數據結構中。即定義一個結構體，成員包括用戶需要用到的數據類型，最后，在結構體中加入內核雙向鏈表數據類型，使之成為結構體的成員。

如代碼所示，定義用戶結構體，包含雙向鏈表成員：

typedef?struct { ????UINT16??????????member1;??//用戶數據????????? ????UINT16??????????member2;??//用戶數據據???????????????????? ????LOS_DL_LIST?????mList;????//雙向鏈表??? }?User_Data_t;

基本原理是：利用雙向鏈表，將用戶結構體中定義好的鏈表成員變量都鏈接起來；鏈表節點在用戶結構體中的偏移地址是固定的，根據鏈表節點的地址，減去偏移地址，就能得到用戶結構體變量的起始地址了。LiteOS中根據鏈表地址獲取用戶節點地址的宏定義是：

//取得鏈表所在結構體地址,即根據鏈表節點的地址獲取用戶結構體地址. //item:?鏈表節點地址.用戶結構體中定義的鏈表成員的地址 //type:?用戶結構體名稱 //member:鏈表在用戶結構體中的成員名稱 #define?LOS_DL_LIST_ENTRY(item,?type,?member)?\ ????((type?*)((char?*)item?-?LOS_OFF_SET_OF(type,?member)))?\

如下圖所示，利用鏈表將用戶節點中的鏈表成員鏈接起來

示例代碼如下：

User_Data_t??data1,data2,data3;?//定義用戶變量 LOS_DL_LIST??gHeader;???//定義鏈表頭 data1.member1?=?1;data2.member1?=?2;data3.member1?=?3;//初始化用戶數據 LOS_ListInit(&gHeader);??//初始化鏈表 LOS_ListTailInsert(&gHeader,&data1.mList);//將data1添加到鏈表尾部 LOS_ListTailInsert(&gHeader,&data2.mList);//將data2添加到鏈表尾部,即data1之后 LOS_ListTailInsert(&gHeader,&data3.mList);//將data3添加到鏈表尾部,即data2之后 //從鏈表中取數據? LOS_DL_LIST?*node; User_Data_t??*pData; node?=?LOS_DL_LIST_FIRST(&gHeader);?//獲取鏈表第一個節點.node指向data1.mList //根據node取得data1的地址 pData?=?LOS_DL_LIST_ENTRY(node,User_Data_t,mList); printf("data1.member1?is?%d!\r\n",pData->member1); //遍歷鏈表 LOS_DL_LIST_FOR_EACH_ENTRY(pData,&gHeader,User_Data_t,mList) { ????printf("data?member1?is?%d!\r\n",pData->member1); }

軟件開發

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。