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、10ticks、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() 排序連結串列刪除

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

⑴處是獲取排序連結串列的頭結點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到自己賬戶下，如下圖，謝謝。