?

概念

為了性能考慮，嵌入式系統(tǒng)一般使用C語(yǔ)言進(jìn)行開發(fā)，由于C語(yǔ)言標(biāo)準(zhǔn)庫(kù)沒有封裝鏈表，所以嵌入式系統(tǒng)一般自己設(shè)計(jì)和實(shí)現(xiàn)鏈表這種數(shù)據(jù)結(jié)構(gòu)。單鏈表是鏈表中的一種，本文描述OpenAtom OpenHarmony（以下簡(jiǎn)稱“OpenHarmony”）中HDF軟件模塊自己定義的單鏈表，并學(xué)習(xí)其設(shè)計(jì)和實(shí)現(xiàn)方法。其中包含一些技巧，可以提高讀者的軟件開發(fā)能力。 ?

單鏈表定義

在OpenHarmony的HDF軟件模塊中，單鏈表定義在hdf_slist.h中。

?

struct HdfSListNode {    struct HdfSListNode *next; // next element in list, or NULL};

?

如上圖所述，每個(gè)節(jié)點(diǎn)都是HdfSListNode，上圖共有5個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)內(nèi)部有一個(gè)next成員，其值為下一個(gè)節(jié)點(diǎn)在內(nèi)存中的地址。由于可以通過(guò)這個(gè)地址找到下一個(gè)節(jié)點(diǎn)，所以在圖里面用紅色右箭頭來(lái)描述這個(gè)關(guān)系。整體來(lái)看，從1號(hào)節(jié)點(diǎn)可以通過(guò)next成員依次找到后面4個(gè)節(jié)點(diǎn)，從圖形看，就是一個(gè)邏輯上的鏈關(guān)系，我們把這種結(jié)構(gòu)稱為鏈表。

單獨(dú)看5號(hào)節(jié)點(diǎn)，5號(hào)節(jié)點(diǎn)沒有下一個(gè)節(jié)點(diǎn)，所以設(shè)計(jì)上是需要給一個(gè)特定的值來(lái)表示，實(shí)現(xiàn)上一般把5號(hào)節(jié)點(diǎn)的next成員填成0值，表明其為最末尾的節(jié)點(diǎn)。

接下來(lái)我們看下面這個(gè)數(shù)據(jù)結(jié)構(gòu)：

?

struct HdfSList {    struct HdfSListNode *root;};

?

如上圖所示，圓角矩形表示的是HdfSList，其root成員記錄了鏈表中某節(jié)點(diǎn)的地址，為了訪問(wèn)整個(gè)鏈表，需要將root成員的值設(shè)置成第1個(gè)節(jié)點(diǎn)的地址。因?yàn)閱捂湵碇恢С滞粋€(gè)方向查找，不支持往回查找，如上面的錯(cuò)誤范例。如果root記錄的是第二個(gè)節(jié)點(diǎn)地址，則第一個(gè)節(jié)點(diǎn)變得不可訪問(wèn)。 ?

迭代器簡(jiǎn)介

迭代器是伴隨集合概念產(chǎn)生的，意思是依次訪問(wèn)集合中的每一個(gè)元素，迭代器提供訪問(wèn)這些元素的方法。對(duì)于單鏈表而言，鏈表中的每一個(gè)節(jié)點(diǎn)都是一個(gè)元素，所有的節(jié)點(diǎn)組成集合。所以可以通過(guò)迭代器來(lái)訪問(wèn)鏈表中的元素。

迭代器需要提供的基本能力以及操作范式是：

?

初始化迭代器重復(fù)判斷(集合中還有未被訪問(wèn)的元素)     獲取下一個(gè)元素的訪問(wèn)方法     讀寫下一個(gè)元素(也可能是刪除這個(gè)元素)結(jié)束

?

對(duì)于本文描述的單鏈表，其封裝了下面3個(gè)函數(shù)來(lái)支持迭代算法。這3個(gè)函數(shù)分別表示迭代器對(duì)象的初始化；集合中是否還有元素沒有參與迭代；取出集合中下一個(gè)可以參與迭代的元素。

?

/* * @brief initialize iterator * * @param[in] iterator the point of iterator. * @param[in] list the point of operation list. * * @return None */void HdfSListIteratorInit(struct HdfSListIterator *iterator, struct HdfSList *list);
/* * @brief check whether list has next node. * * @param[in] iterator the point of iterator. * * @return the result of check next. */bool HdfSListIteratorHasNext(struct HdfSListIterator *iterator);
/* * @brief get next link in the list and move iterator to next. * * @param[in] iterator the point of iterator. * * @return point to next element of it. */struct?HdfSListNode?*HdfSListIteratorNext(struct?HdfSListIterator?*iterator);

?

迭代器實(shí)現(xiàn)考慮

對(duì)于本文所描述的單鏈表迭代器。直觀上看，除了第一個(gè)節(jié)點(diǎn)，其它節(jié)點(diǎn)都可以通過(guò)next訪問(wèn)到，第一個(gè)節(jié)點(diǎn)通過(guò)root訪問(wèn)到。那實(shí)際上會(huì)不會(huì)就是這么簡(jiǎn)單呢？其實(shí)不然，因?yàn)樾枰紤]到節(jié)點(diǎn)刪除的因素。如下圖，在鏈表迭代過(guò)程中，如果刪除了當(dāng)前節(jié)點(diǎn)，那么怎么找到下一個(gè)節(jié)點(diǎn)呢？

如上圖所示，當(dāng)在遍歷過(guò)程中刪除了curr節(jié)點(diǎn)時(shí)，那么通過(guò)它找到下一個(gè)節(jié)點(diǎn)是不可能了。所以這個(gè)時(shí)候我們必須借助操作curr之前還在鏈表上的上一個(gè)節(jié)點(diǎn)，即上圖的prev節(jié)點(diǎn)，通過(guò)其next成員，找到需要迭代處理的下一個(gè)節(jié)點(diǎn)。所以，迭代過(guò)程中需要記錄prev、curr這2個(gè)節(jié)點(diǎn)的位置信息。迭代過(guò)程實(shí)際就是調(diào)整prev和curr的過(guò)程，對(duì)于不刪除的情況，prev和curr依次向后移動(dòng)，刪除操作時(shí)，只移動(dòng)curr。

另外，對(duì)于第1個(gè)節(jié)點(diǎn)的情況需要特殊處理，所以需要一個(gè)額外的信息來(lái)表示是不是迭代第1個(gè)元素，因?yàn)楸疚拿枋龅牡鲗?duì)象含有3個(gè)信息。如下代碼所示：

?

struct HdfSListIterator {    int stepOnNext;     //是否即將開始遍歷第二個(gè)以及之后的元素    struct HdfSListNode *prev; // points to the item before the current one 當(dāng)前被操作元素的前一個(gè)元素    struct HdfSListNode *curr; // points to the current item (to detect item removal) 當(dāng)前被操作的元素，可能剛操作完，被移除鏈表};

?

結(jié)論

在嵌入式開發(fā)中，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程中，在進(jìn)行OpenHarmony項(xiàng)目開發(fā)中，單鏈表都是很重要的，而本文只是其中一個(gè)軟件模塊的單鏈表實(shí)現(xiàn)。通過(guò)對(duì)單鏈表的實(shí)現(xiàn)的圖示分析，特別是迭代器慣用法的分析，相信讀者對(duì)單鏈表以及迭代器的認(rèn)識(shí)都會(huì)進(jìn)一步提升，更詳盡的代碼分析和閱讀留給讀者自己進(jìn)行，請(qǐng)參考如下代碼文件

https://gitee.com/openharmony/drivers_hdf_core/blob/master/framework/utils/include/hdf_slist.h

https://gitee.com/openharmony/drivers_hdf_core/blob/master/framework/utils/src/hdf_slist.c