文章目錄

• • • RT-Thread中的鏈表組織結構
    • RT-Thread中的鏈表操作
    • • 鏈表節點的插入
      • 鏈表節點的刪除
      • 鏈表節點元素訪問

RT-Thread中的鏈表組織結構

??RT-Thread中的鏈表是帶表頭節點的雙向循環鏈表結構，它的表頭節點與之前的博客《雙向循環鏈表》中介紹的表頭節點不同，之前博客介紹的表頭節點與后繼節點結構是一致的，這是因為指針類型問題，前面介紹過的鏈表都是前驅節點指向后繼節點的首地址，即指向節點結構體的指針。RT-Thread鏈表節點中的指針并不是指向節點首地址（這種說法并不嚴謹，盡管實際上它確實不是指向節點首地址），而是指向節點中的list結構體元素，這種鏈表結構讓鏈表更加靈活。

/*** Double List structure*/ struct rt_list_node {struct rt_list_node *next; /**< point to next node. */struct rt_list_node *prev; /**< point to prev node. */ }; typedef struct rt_list_node rt_list_t; /**< Type for lists. */

??RT-Thread中的鏈表指針定義為rt_list_t，而不是節點類型，這就可以使鏈表的操作（例如：插入、刪除）不用依賴整個節點，不用管節點結構體中成員的具體情況，甚至可以將不同類型的節點插入鏈表。這就是為什么表頭節點與其他節點不同，在操作鏈表時卻沒有帶來額外的麻煩。
??節點與節點之間可以不一致，那么不管鏈表中節點用于存放何種數據，它的size有多大，表頭節點都可以只存放用于實現算法所需的輔助數據，在節點比較大時可以節省內存空間，還可以一致實現不同鏈表的表頭節點。

??RT-Thread中不同Object鏈表的表頭節點都存放于rt_object_container數組當中，各個鏈表在初始化時都初始化為帶表頭節點的空表，不同Object的節點不同，同一Object的節點也不盡相同。但表頭都采用了統一結構：

/*** The information of the kernel object*/ struct rt_object_information {enum rt_object_class_type type; /**< object class type */rt_list_t object_list; /**< object list */rt_size_t object_size; /**< object size */ };

RT-Thread中的鏈表操作

??之前介紹的雙向循環鏈表的插入、刪除等操作都依賴于節點的結構體類型，要準確找到next、prev等指針在節點中的位置，需要將指向節點的指針定義為該節點類型指針。在諸多不同鏈表，甚至同一鏈表中節點結構不盡相同的情況下，這種方式變得不可行。在節點結構體成員的順序性不做要求的情況下，可以將prev、next兩個指針放在節點起始位置，在遍歷整個鏈表時，進行強轉，從而實現不同鏈表、不同節點之間的遍歷。但是RT-Thread中，每個節點的起始地址都用于存放"parent"以實現類似面向對象語言中的一些特性。且每個"class"的"parent"長度不一，導致之后存放指針的位置不定，強轉這真是個餿主意😐

鏈表節點的插入

??在前文中提到，RT-Thread鏈表節點中都包含rt_list_t結構，且prev、next指針都指向各自前驅節點和后繼節點中的rt_list_t成員，那鏈表插入就不麻煩了，只要將《雙向循環鏈表》的操作方法稍微改動以下，將節點起始地址改為rt_list_t節點起始地址。
?&emsp；RT-Thread中專門實現了插入相關的內聯函數：

/*** @brief insert a node after a list** @param l list to insert it* @param n new node to be inserted*/ rt_inline void rt_list_insert_after(rt_list_t *l, rt_list_t *n) {l->next->prev = n;n->next = l->next;l->next = n;n->prev = l; } /*** @brief insert a node before a list** @param n new node to be inserted* @param l list to insert it*/ rt_inline void rt_list_insert_before(rt_list_t *l, rt_list_t *n) {l->prev->next = n;n->prev = l->prev;l->prev = n;n->next = l; }

鏈表節點的刪除

??節點的刪除也是同樣的道理，在刪除相關節點的時候，不再是將后繼節點（前驅節點）的起始地址賦給前驅節點（后繼節點）的指針，而是將后繼節點（前驅節點）中rt_list_t成員的地址賦給前驅節點（后繼節點）的指針。

/*** @brief remove node from list.* @param n the node to remove from the list.*/ rt_inline void rt_list_remove(rt_list_t *n) {n->next->prev = n->prev;n->prev->next = n->next;n->next = n->prev = n; }

鏈表節點元素訪問

??既然rt_list_t成員是存放在節點中部或是尾部，且不同類型的節點rt_list_t成員位置還不一樣，那在遍歷整個鏈表時，獲得的是后繼節點（前驅節點）的rt_list_t成員的地址，那如何根據rt_list_t成員的地址訪問節點中其他元素。
??盡管不同類型節點中rt_list_t成員位置不定，但是在確定類型節點中，rt_list_t成員的偏移是固定的，在獲取rt_list_t成員地址的情況下，計算出rt_list_t成員在該節點中的偏移，即(rt_list_t成員地址)-(rt_list_t成員偏移）=節點起始地址。關鍵在于如何計算不同類型節點中rt_list_t成員偏移。RT-Thread中給出的相應算法如下：

/*** rt_container_of - return the member address of ptr, if the type of ptr is the* struct type.*/ #define rt_container_of(ptr, type, member) \((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))

??該宏替換之后，ptr是該節點中rt_list_t成員首地址，member是rt_list_t結構體成員，type則是該節點的結構體類型。
??在0地址處強制轉化為type結構體類型，取得的相關member成員地址即為member成員在type類型結構體中的偏移。

type類型結構體成員地址

int element1	0x00000000
int element2	0x00000004
int element3	0x00000008
int element4	040000000c
int element5	0x00000010
…	…
member	member成員地址
…	…

??將計算獲得的節點首地址強制轉化為相應的結構體類型便可訪問相應的數據。

總結

以上是生活随笔為你收集整理的RT-Thread中的链表结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。