版權聲明：本文為博主原創文章，未經博主允許不得轉載。 https://blog.csdn.net/tidyjiang/article/details/52750485

Zephyr OS 所有的學習筆記已托管到 Github，CSDN 博客里的內容只是 Github 里內容的拷貝，因此鏈接會有錯誤，請諒解。

最新的學習筆記請移步 GitHub：https://github.com/tidyjiang8/zephyr-inside

本文先簡單地介紹了一些內聯函數的知識，然后再詳細分析 Zephyr OS 內核中的鏈表的源碼。

• 內聯(inline)函數
• 鏈表的定義
• 鏈表的初始化
• 判斷某節點是否是鏈表的頭節點
• 判斷某節點是否是鏈表的尾節點
• 判斷鏈表是否為空
• 獲取鏈表頭節點
• 獲取節點的下一個節點
• 在鏈表尾部插入節點
• 在鏈表頭部插入節點
• 在某節點后插入節點
• 在某節點前插入節點
• 刪除某節點
• 取出第一個節點

內聯(inline)函數

在 Zephyr OS 中，實現了一個雙鏈表，其代碼位于頭文件 inclue/misc/dlist.h 中。

居然將函數實現在頭文件中！！再仔細一看，這些函數不是普通的函數，而是內聯函數！

為什么？這樣有什么好處？在網上搜了一通，總結如下：

• 什么是內聯函數：
  
  • 簡單地講，內聯函數就是用關鍵字 inline 修飾的函數。編譯器在編譯含有內聯函數的文件時，會在調用內聯函數的地方將該函數展開，這一點與處理宏的過程類似。但是，在將內聯函數展開的時候，編譯器會對該內聯函數的類型進行檢查，比如檢查參數、返回值類型等。
• 什么時候使用內聯函數：
  
  • 如果一段代碼需要重用，且重用的頻率很高，且代碼很短，那么推薦使用內聯函數。
• 內聯函數 vs 宏：
  
  • 編譯器會對內聯函數進行類型檢查，而對宏只是進行簡單的替換。
  • 內聯函數在編譯時被展開，宏在預編譯時被展開
• 內聯函數 vs 普通函數：
  
  • 前面已經說了，內聯函數的調用頻率高，代碼短小，在這種情況下，如果不使用內聯函數而使用普通函數，會降低運行效率，因為函數調用有開銷，比如參數、返回值、返回地址等的壓棧、出棧操作。
• 內聯函數的缺點：
  
  • 增加了編譯后的代碼的大小。

在 Zephyr OS 的源碼中，還會看到另外一套鏈表，位于 net/ip/contiki/os/list.[ch]。這套鏈表是移植于Contiki，只在ip協議棧中有使用。

鏈表的定義

struct _dnode {union {struct _dnode *head; struct _dnode *next; };union {struct _dnode *tail; struct _dnode *prev;}; };

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

第一眼就蒙了，為什么節點的定義里面居然有兩個聯合體。直到看到后來，恍惚間想明白了。Zephyr OS 中對該結構體使用 tpyedef 定義了兩種類型：

typedef struct _dnode sys_dlist_t; typedef struct _dnode sys_dnode_t;

• 1
• 2

sys_dlist_t 定義了一個雙鏈表，sys_dnode_t 定義了一個節點。在使用 sys_dlist_t 時，使用的是結構體中的 head, tail 兩個成員；在使用 sys_dnode_t 時，使用的是結構體中的 next, prev 兩個成語。

其實我們可以對上面的代碼展開成兩個結構體：

typedef struct _dnode { // 定義節點struct _dnode *next; // 后繼節點struct _donde *prev; // 前驅節點 } sys_dnode_t;typedef struct _dlist { // 定義鏈表struct _dlist *head; // 鏈表頭struct _dlist *tail; // 鏈表尾 } sys_dlist_t;

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

有人可能會被鏈表和節點兩個概念搞暈了，比如曾經的我。我們只需要記住一點，在使用鏈表的時候，我們都是先定義一個鏈表，然后往鏈表里進行添加節點、刪除節點、查找節點等操作。比如：

sys_dlist_t mylist; // 定義鏈表 sys_dlist_init(&mylist); // 鏈表初始化sys_dnode_t mynode1, mynode2; // 定義節點 ... // 對節點初始化 sys_dlist_append(&mylist, &mynode1); // 插入節點1 sys_dlist_append(&mylist, &mynode2); // 插入節點2

• 1
• 2
• 3
• 4
• 5
• 6
• 7

鏈表的初始化

static inline void sys_dlist_init(sys_dlist_t *list) {list->head = (sys_dnode_t *)list;list->tail = (sys_dnode_t *)list; }

• 1
• 2
• 3
• 4
• 5

理解了前面所說的東西，再看具體的代碼實現，so easy.

進行鏈表的初始化，此時鏈表是空的，沒有任何節點，所以將 head, tail 兩個指針都指向 list 自身。

判斷某節點是否是鏈表的頭節點

static inline int sys_dlist_is_head(sys_dlist_t *list, sys_dnode_t *node) {return list->head == node; }

• 1
• 2
• 3
• 4

判斷某節點是否是鏈表的尾節點

static inline int sys_dlist_is_tail(sys_dlist_t *list, sys_dnode_t *node) {return list->tail == node; }

• 1
• 2
• 3
• 4

判斷鏈表是否為空

static inline int sys_dlist_is_empty(sys_dlist_t *list) {return list->head == list; }

• 1
• 2
• 3
• 4

獲取鏈表頭節點

static inline sys_dnode_t *sys_dlist_peek_head(sys_dlist_t *list) {return sys_dlist_is_empty(list) ? NULL : list->head; }

• 1
• 2
• 3
• 4

先判斷鏈表是否為空，如果為空，則返回 NULL，否則返回頭結點。所以在使用才函數時，需要判斷返回值是否為 NULL，再做處理。

獲取節點的下一個節點

static inline sys_dnode_t *sys_dlist_peek_next(sys_dlist_t *list,sys_dnode_t *node) {return node == list->tail ? NULL : node->next; }

• 1
• 2
• 3
• 4
• 5

先判斷傳入的節點是不是鏈表的尾節點，如果是，則返回 NULL，否則返回下一個節點。所以在使用才函數時，需要判斷返回值是否為 NULL，再做處理。

在鏈表尾部插入節點

static inline void sys_dlist_append(sys_dlist_t *list, sys_dnode_t *node) {node->next = list;node->prev = list->tail;list->tail->next = node;list->tail = node; }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

在鏈表頭部插入節點

static inline void sys_dlist_prepend(sys_dlist_t *list, sys_dnode_t *node) {node->next = list->head;node->prev = list;list->head->prev = node;list->head = node; }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

在某節點后插入節點

static inline void sys_dlist_insert_after(sys_dlist_t *list,sys_dnode_t *insert_point, sys_dnode_t *node) {if (!insert_point) {sys_dlist_prepend(list, node);} else {node->next = insert_point->next;node->prev = insert_point;insert_point->next->prev = node;insert_point->next = node;} }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

在某節點前插入節點

static inline void sys_dlist_insert_before(sys_dlist_t *list,sys_dnode_t *insert_point, sys_dnode_t *node) {if (!insert_point) {sys_dlist_append(list, node);} else {node->prev = insert_point->prev;node->next = insert_point;insert_point->prev->next = node;insert_point->prev = node;} }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

刪除某節點

static inline void sys_dlist_remove(sys_dnode_t *node) {node->prev->next = node->next;node->next->prev = node->prev; }

• 1
• 2
• 3
• 4
• 5

取出第一個節點

static inline sys_dnode_t *sys_dlist_get(sys_dlist_t *list) {sys_dnode_t *node;if (sys_dlist_is_empty(list)) {return NULL;}node = list->head;sys_dlist_remove(node);return node; }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

取出頭節點后將其重鏈表中刪除。

總結

以上是生活随笔為你收集整理的Zephyr OS 内核篇： 内核链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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