LiteOS內核源碼分析系列一 盤點那些重要的數據結構 （3）

LiteOS內核源碼分析系列一 盤點那些重要的數據結構 -- SortLinkList

在學習Huawei LiteOS源代碼的時候，常常會遇到一些數據結構的使用。如果沒有掌握這它們的用法，閱讀LiteOS源代碼的時候會很費解、很吃力。本文會給讀者介紹下LiteOS源碼中常用的幾個數據結構，包括: 雙向循環鏈表LOS_DL_LIST，優先級隊列Priority Queue，排序鏈表SortLinkList等。在講解時，會結合相關的繪圖，培養數據結構的平面想象能力，幫助更好的學習和理解這些數據結構用法。

本文中所涉及的LiteOS源碼，均可以在LiteOS開源站點https://gitee.com/LiteOS/LiteOS?獲取。

這是第三部分，也是最后一部分，我們來看看SortLinkList 排序鏈表。

3、SortLinkList 排序鏈表

SortLinkList是LiteOS另外一個比較重要的數據結構，它在LOS_DL_LIST雙向鏈表結構體的基礎上，增加了RollNum滾動數，用于涉及時間到期、超時的業務場景。在阻塞任務是否到期，定時器是否超時場景下，非常依賴SortLinkList排序鏈表這個數據結構。LiteOS排序鏈表支持單一鏈表LOSCFG_BASE_CORE_USE_SINGLE_LIST和多鏈表LOSCFG_BASE_CORE_USE_MULTI_LIST，可以通過LiteOS的menuconfig工具更改Sortlink Option選項來配置使用單鏈表還是多鏈表，我們這里先講述前者。

排序鏈表SortLinkList接口主要內部使用，用戶業務開發時不涉及，不對外提供接口。SortLinkList排序鏈表的代碼都在kernel\base\include\los_sortlink_pri.h頭文件和kernel\base\los_sortlink.c實現文件中。

3.1 SortLinkList 排序鏈表結構體定義

在kernel\base\include\los_sortlink_pri.h文件中定義了兩個結構體，如下述源碼所示。

SortLinkAttribute結構體定義排序鏈表的頭結點LOS_DL_LIST *sortLink，游標UINT16 cursor。SortLinkList結構體定義排序鏈表的業務節點，除了負責雙向鏈接的成員變量LOS_DL_LIST *sortLink，還包括業務信息，UINT32 idxRollNum，即index索引和rollNum滾動數。在單鏈表的排序鏈表中，idxRollNum表示多長時間后會到期。

我們舉個例子，看下面的示意圖。排序鏈表中，有3個鏈表節點，分別在25 ticks、35 ticks、50 ticks后到期超時，已經按到期時間進行了先后排序。三個節點的idxRollNum分別等于25 ticks、10

ticks、15 ticks。每個節點的idxRollNum保存的不是這個節點的超時時間，而是從鏈表head節點到該節點的所

有節點的idxRollNum的加和，才是該節點的超時時間。這樣設計的好處就是，隨著Tick時間推移，只需要更新第一個節點的超時時間就好，可以好好體會一下。

示意圖如下：

源碼如下：

typedef struct { LOS_DL_LIST sortLinkNode; UINT32 idxRollNum; } SortLinkList; typedef struct { LOS_DL_LIST *sortLink; UINT16 cursor; UINT16 reserved; } SortLinkAttribute;

下面我們來學習下排序鏈表支持的那些操作。

3.2 SortLinkList 排序鏈表接口

在繼續之前我們先看下kernel\base\include\los_sortlink_pri.h文件中的一些單鏈表配置LOSCFG_BASE_CORE_USE_SINGLE_LIST下的宏定義，包含滾動數最大值等，對滾動數進行加、減、減少1等操作。

源碼如下：

#define OS_TSK_SORTLINK_LOGLEN 0U #define OS_TSK_SORTLINK_LEN 1U #define OS_TSK_MAX_ROLLNUM 0xFFFFFFFEU #define OS_TSK_LOW_BITS_MASK 0xFFFFFFFFU #define SORTLINK_CURSOR_UPDATE(CURSOR) #define SORTLINK_LISTOBJ_GET(LISTOBJ, SORTLINK) (LISTOBJ = SORTLINK->sortLink) #define ROLLNUM_SUB(NUM1, NUM2) NUM1 = (ROLLNUM(NUM1) - ROLLNUM(NUM2)) #define ROLLNUM_ADD(NUM1, NUM2) NUM1 = (ROLLNUM(NUM1) + ROLLNUM(NUM2)) #define ROLLNUM_DEC(NUM) NUM = ((NUM) - 1) #define ROLLNUM(NUM) (NUM) #define SET_SORTLIST_VALUE(sortList, value) (((SortLinkList *)(sortList))->idxRollNum = (value))

3.2.1 UINT32 OsSortLinkInit() 排序鏈表初始化

在系統啟動軟件初始化，初始化任務、初始化定時器時，會分別初始化任務的排序鏈表和定時器的排序鏈表。

kernel\base\los_task.c : UINT32 OsTaskInit(VOID)函數

`ret = OsSortLinkInit(&g_percpu[index].taskSortLink);`

kernel\base\los_swtmr.c : UINT32 OsSwtmrInit(VOID)函數

`ret = OsSortLinkInit(&g_percpu[cpuid].swtmrSortLink);`

我們看下排序鏈表初始化函數的源代碼，⑴處代碼計算需要申請多少個雙向鏈表的內存大小，對于單鏈表的排序鏈表，OS_TSK_SORTLINK_LOGLEN為0，為一個雙向鏈表申請內存大小即可。然后申請內存，初始化申請的內存區域為0等，⑵處把申請的雙向鏈表節點賦值給sortLinkHeader的鏈表節點，作為排序鏈表的頭節點，然后調用LOS_ListInit()函數初始化為雙向循環鏈表。

源碼如下：

LITE_OS_SEC_TEXT_INIT UINT32 OsSortLinkInit(SortLinkAttribute *sortLinkHeader) { UINT32 size; LOS_DL_LIST *listObject = NULL; ⑴ size = sizeof(LOS_DL_LIST) << OS_TSK_SORTLINK_LOGLEN; listObject = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, size); /* system resident resource */ if (listObject == NULL) { return LOS_NOK; } (VOID)memset_s(listObject, size, 0, size); ⑵ sortLinkHeader->sortLink = listObject; LOS_ListInit(listObject); return LOS_OK; }

3.2.2 VOID OsAdd2SortLink() 排序鏈表插入

在任務等待互斥鎖、信號量等資源阻塞時，定時器啟動時，這些需要等待指定時間的任務、定時器等，都會加入對應的排序鏈表。

我們一起看下代碼，包含2個參數，第一個參數sortLinkHeader用于指定排序鏈表的頭結點，第二個參數sortList是待插入的鏈表節點，此時該節點的滾動數等于對應阻塞任務或定時器的超時時間。

⑴處代碼處理滾動數超大的場景，如果滾動數大于OS_TSK_MAX_ROLLNUM，則設置滾動數等于OS_TSK_MAX_ROLLNUM。⑵處代碼，如果排序鏈表為空， 則把鏈表節點尾部插入。如果排序鏈表不為空，則執行⑶處代碼，獲取排序鏈表上的下一個節點SortLinkList *listSorted。⑷、⑸ 處代碼，如果待插入節點的滾動數大于排序鏈表的下一個節點的滾動數，則把待插入節點的滾動數減去下一個節點的滾動數，并繼續執行⑹處代碼，繼續與下下一個節點進行比較。否則，如果待插入節點的滾動數小于排序鏈表的下一個節點的滾動數，則把下一個節點的滾動數減去待插入節點的滾動數，然后跳出循環，繼續執行⑺處代碼，完成待插入節點的插入。插入過程，可以結合上文的示意圖進行理解。

源碼如下：

LITE_OS_SEC_TEXT VOID OsAdd2SortLink(const SortLinkAttribute *sortLinkHeader, SortLinkList *sortList) { SortLinkList *listSorted = NULL; LOS_DL_LIST *listObject = NULL; ⑴ if (sortList->idxRollNum > OS_TSK_MAX_ROLLNUM) { SET_SORTLIST_VALUE(sortList, OS_TSK_MAX_ROLLNUM); } listObject = sortLinkHeader->sortLink; ⑵ if (listObject->pstNext == listObject) { LOS_ListTailInsert(listObject, &sortList->sortLinkNode); } else { ⑶ listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); do { ⑷ if (ROLLNUM(listSorted->idxRollNum) <= ROLLNUM(sortList->idxRollNum)) { ROLLNUM_SUB(sortList->idxRollNum, listSorted->idxRollNum); } else { ⑸ ROLLNUM_SUB(listSorted->idxRollNum, sortList->idxRollNum); break; } ⑹ listSorted = LOS_DL_LIST_ENTRY(listSorted->sortLinkNode.pstNext, SortLinkList, sortLinkNode); } while (&listSorted->sortLinkNode != listObject); ⑺ LOS_ListTailInsert(&listSorted->sortLinkNode, &sortList->sortLinkNode); } }

3.2.3 VOID OsDeleteSortLink() 排序鏈表刪除

當任務恢復、刪除，定時器停止的時候，會從對應的排序鏈表中刪除。

我們一起閱讀下刪除函數的源代碼，包含2個參數，第一個參數sortLinkHeader用于指定排序鏈表的頭結點，第二個參數sortList是待刪除的鏈表節點。

⑴處是獲取排序鏈表的頭結點listObject，⑵處代碼檢查要刪除的節點是否在排序鏈表里，否則輸出錯誤信息和回溯棧信息。⑶處代碼判斷是否排序鏈表里只有一個業務節點，如果只有一個節點，直接執行⑸處代碼刪除該節點即可。如果排序鏈表里有多個業務節點，則執行⑷處代碼獲取待刪除節點的下一個節點nextSortList，把刪除節點的滾動數加到下一個節點的滾動數里，然后執行⑸處代碼執行刪除操作。

源碼如下：

LITE_OS_SEC_TEXT VOID OsDeleteSortLink(const SortLinkAttribute *sortLinkHeader, SortLinkList *sortList) { LOS_DL_LIST *listObject = NULL; SortLinkList *nextSortList = NULL; ⑴ listObject = sortLinkHeader->sortLink; ⑵ OsCheckSortLink(listObject, &sortList->sortLinkNode); ⑶ if (listObject != sortList->sortLinkNode.pstNext) { ⑷ nextSortList = LOS_DL_LIST_ENTRY(sortList->sortLinkNode.pstNext, SortLinkList, sortLinkNode); ROLLNUM_ADD(nextSortList->idxRollNum, sortList->idxRollNum); } ⑸ LOS_ListDelete(&sortList->sortLinkNode); }

3.2.4 UINT32 OsSortLinkGetNextExpireTime() 獲取下一個超時到期時間

在Tickless特性，會使用此方法獲取下一個超時到期時間。

我們一起閱讀下源代碼，包含1個參數，sortLinkHeader用于指定排序鏈表的頭結點。

⑴處是獲取排序鏈表的頭結點listObject，⑵處代碼判斷排序鏈表是否為空，如果排序鏈表為空，則返回OS_INVALID_VALUE。如果鏈表不為空，⑶處代碼獲取排序鏈表的第一個業務節點，然后獲取其滾動數，即過期時間，進行返回。

源碼如下：

LITE_OS_SEC_TEXT UINT32 OsSortLinkGetNextExpireTime(const SortLinkAttribute *sortLinkHeader) { UINT32 expireTime = OS_INVALID_VALUE; LOS_DL_LIST *listObject = NULL; SortLinkList *listSorted = NULL; ⑴ listObject = sortLinkHeader->sortLink; ⑵ if (!LOS_ListEmpty(listObject)) { ⑶ listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); expireTime = listSorted->idxRollNum; } return expireTime; }

3.2.5 OsSortLinkGetTargetExpireTime() 獲取指定節點的超時時間

定時器獲取剩余超時時間函數LOS_SwtmrTimeGet()會調用函數OsSortLinkGetTargetExpireTime()?獲取指定節點的超時時間。

我們一起看下代碼，包含2個參數，第一個參數sortLinkHeader用于指定排序鏈表的頭結點，第二個參數targetSortList是待獲取超時時間的目標鏈表節點。

⑴處代碼獲取目標節點的滾動數。⑵處代碼獲取排序鏈表的頭結點listObject，⑶處代碼獲取排序鏈表上的下一個節點SortLinkList *listSorted。⑷處循環代碼，當下一個節點不為目標鏈表節點的時候，依次循環，并執行⑸處代碼把循環遍歷的各個節點的滾動數相加，最終的計算結果即為目標節點的超時時間。

源碼如下：

LITE_OS_SEC_TEXT_MINOR UINT32 OsSortLinkGetTargetExpireTime(const SortLinkAttribute *sortLinkHeader, const SortLinkList *targetSortList) { SortLinkList *listSorted = NULL; LOS_DL_LIST *listObject = NULL; ⑴ UINT32 rollNum = targetSortList->idxRollNum; ⑵ listObject = sortLinkHeader->sortLink; ⑶ listSorted = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); ⑷ while (listSorted != targetSortList) { ⑸ rollNum += listSorted->idxRollNum; listSorted = LOS_DL_LIST_ENTRY((listSorted->sortLinkNode).pstNext, SortLinkList, sortLinkNode); } return rollNum; }

3.2.6 VOID OsSortLinkUpdateExpireTime() 更新超時時間

在Tickless特性，會使用此方法更新超時時間。Tickless休眠sleep時，需要把休眠的ticks數目從排序鏈表里減去。調用此方法的函數會保障減去的ticks數小于節點的滾動數。

我們一起閱讀下源代碼，包含2個參數，第一個參數sleepTicks是休眠的ticks數，第二個參數sortLinkHeader用于指定排序鏈表的頭結點。

⑴處獲取排序鏈表的頭結點listObject，⑵處代碼獲取下一個鏈表節點sortList，這個也是排序鏈表的第一個業務節點，然后把該節點的滾動數減去sleepTicks - 1完成超時時間更新。

源碼如下：

LITE_OS_SEC_TEXT VOID OsSortLinkUpdateExpireTime(UINT32 sleepTicks, SortLinkAttribute *sortLinkHeader) { SortLinkList *sortList = NULL; LOS_DL_LIST *listObject = NULL; if (sleepTicks == 0) { return; } ⑴ listObject = sortLinkHeader->sortLink; ⑵ sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); ROLLNUM_SUB(sortList->idxRollNum, sleepTicks - 1); }

3.3 SortLinkList 排序鏈表和Tick時間關系

任務、定時器加入排序鏈表后，隨時時間推移，一個tick一個tick的逝去，排序鏈表中的滾動數是如何更新的呢？

我們看看Tick中斷的處理函數VOID OsTickHandler(VOID)，該函數在kernel\base\los_tick.c文件里。

當時間每走過一個tick，會調用該中斷處理函數，代碼片段中的⑴、⑵處的代碼分別掃描任務和定時器，檢查和更新時間。

LITE_OS_SEC_TEXT VOID OsTickHandler(VOID) { UINT32 intSave; TICK_LOCK(intSave); g_tickCount[ArchCurrCpuid()]++; TICK_UNLOCK(intSave); ...... ⑴ OsTaskScan(); /* task timeout scan */ #if (LOSCFG_BASE_CORE_SWTMR == YES) ⑵ OsSwtmrScan(); #endif }

我們以OsTaskScan()為例，快速了解下排序鏈表和tick時間的關系。函數在kernel\base\los_task.c文件中，函數代碼片段如下：

⑴處代碼獲取任務排序鏈表的第一個節點，然后執行下一行代碼把該節點的滾動數減去1。⑵處代碼循環遍歷排序鏈表，如果滾動數為0，即時間到期了，會調用LOS_ListDelete()函數從從排序鏈表中刪除，然后執行⑶處代碼，獲取對應的taskCB，然后進一步進行業務處理。讀者可以自行查看更多代碼，后續的文章中也會對任務、定時器進行專題進行講解。

LITE_OS_SEC_TEXT VOID OsTaskScan(VOID) { SortLinkList *sortList = NULL; ...... LOS_DL_LIST *listObject = NULL; SortLinkAttribute *taskSortLink = NULL; taskSortLink = &OsPercpuGet()->taskSortLink; SORTLINK_CURSOR_UPDATE(taskSortLink->cursor); SORTLINK_LISTOBJ_GET(listObject, taskSortLink); ...... ⑴ sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); ROLLNUM_DEC(sortList->idxRollNum); ⑵ while (ROLLNUM(sortList->idxRollNum) == 0) { LOS_ListDelete(&sortList->sortLinkNode); ⑶ taskCB = LOS_DL_LIST_ENTRY(sortList, LosTaskCB, sortList); ...... sortList = LOS_DL_LIST_ENTRY(listObject->pstNext, SortLinkList, sortLinkNode); } ...... }

小結

掌握LiteOS內核的雙向循環鏈表LOS_DL_LIST，優先級隊列Priority Queue，排序鏈表SortLinkList等重要的數據結構，給進一步學習、分析LiteOS源代碼打下了基礎，讓后續的學習更加容易。后續也會陸續推出更多的分享文章，敬請期待，也歡迎大家分享學習使用LiteOS的心得，有任何問題、建議，都可以留言給我們：?https://gitee.com/LiteOS/LiteOS/issues?。為了更容易找到LiteOS代碼倉，建議訪問?https://gitee.com/LiteOS/LiteOS?，關注Watch、Star、并Fork到自己賬戶下，如下圖，謝謝。

數據結構 輕量級操作系統 LiteOS

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

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