大家好，我是LinuxZn。

本次分享sys/queue.h：

什么是sys/queue.h？

queue.h是Linux、FreeBSD中的一個頭文件。

FreeBSD：FreeBSD 是一種類 UNIX操作系統。

這是一個很實用的頭文件，因為這個頭文件里全是宏定義操作，所以其不僅可以使用在Linux/嵌入式Linux項目中，也可以使用在單片機項目中，我也是因為在我們的單片機項目中看到，才知道有這么一個頭文件的。我覺得挺實用的，與大家分享。

它使用宏實現了如下數據結構：

SLIST：單向無尾鏈表

LIST：雙向無尾鏈表

STAILQ：單向有尾鏈表（可作隊列使用）

TAILQ：雙向有尾鏈表（可作隊列使用）

所有的數據結構都支持如下功能：

在鏈表頭插入節點

在任意節點后插入節點

刪除節點

遍歷節點

我們可以在Linux系統的如下路徑中找到這個頭文件：

/usr/include/sys/queue.h

也可以通過如下網址查看：

https://code.woboq.org/userspace/glibc/misc/sys/queue.h.html

sys/queue.h的使用

下面我們基于SLIST來演示其使用。

SLIST相關宏定義：

/*
?*?Singly-linked?List?definitions.
?*/
#define?SLIST_HEAD(name,?type)?????????
struct?name?{???????????????????
?struct?type?*slh_first;?/*?first?element?*/????????
}

#define?SLIST_HEAD_INITIALIZER(head)???????
?{?NULL?}

#define?SLIST_ENTRY(type)??????????
struct?{??????????????
?struct?type?*sle_next;?/*?next?element?*/?????
}

/*
?*?Singly-linked?List?functions.
?*/
#define?SLIST_INIT(head)?do?{?????????
?(head)->slh_first?=?NULL;?????????
}?while?(/*CONSTCOND*/0)

#define?SLIST_INSERT_AFTER(slistelm,?elm,?field)?do?{???
?(elm)->field.sle_next?=?(slistelm)->field.sle_next;???
?(slistelm)->field.sle_next?=?(elm);???????
}?while?(/*CONSTCOND*/0)

#define?SLIST_INSERT_HEAD(head,?elm,?field)?do?{????
?(elm)->field.sle_next?=?(head)->slh_first;?????
?(head)->slh_first?=?(elm);?????????
}?while?(/*CONSTCOND*/0)

#define?SLIST_REMOVE_HEAD(head,?field)?do?{??????
?(head)->slh_first?=?(head)->slh_first->field.sle_next;??
}?while?(/*CONSTCOND*/0)

#define?SLIST_REMOVE(head,?elm,?type,?field)?do?{????
?if?((head)->slh_first?==?(elm))?{???????
??SLIST_REMOVE_HEAD((head),?field);??????
?}???????????????
?else?{??????????????
??struct?type?*curelm?=?(head)->slh_first;????
??while(curelm->field.sle_next?!=?(elm))?????
???curelm?=?curelm->field.sle_next;?????
??curelm->field.sle_next?=????????
??????curelm->field.sle_next->field.sle_next;????
?}???????????????
}?while?(/*CONSTCOND*/0)

#define?SLIST_FOREACH(var,?head,?field)???????
?for((var)?=?(head)->slh_first;?(var);?(var)?=?(var)->field.sle_next)

/*
?*?Singly-linked?List?access?methods.
?*/
#define?SLIST_EMPTY(head)?((head)->slh_first?==?NULL)
#define?SLIST_FIRST(head)?((head)->slh_first)
#define?SLIST_NEXT(elm,?field)?((elm)->field.sle_next)

?

下面我們通過實例來操作。

首先，創建鏈表頭節點、其它節點結構體，用到SLIST_HEAD與SLIST_ENTRY這兩個宏定義：

?

#define?ELEM_TYPE?int

/*?鏈表節點?*/
typedef?struct?node?
{
????ELEM_TYPE?data;
????SLIST_ENTRY(node)?field;?
}node_st;

/*?鏈表頭?*/
typedef?SLIST_HEAD(head,?node)?head_st;

?

鏈表數據域類型我們定義為int，field表示的是指針域。

① 創建一個頭結點：

?

/*?創建鏈表頭節點并初始化?*/
head_st?*head?=?(head_st?*)malloc(sizeof(head_st));
SLIST_INIT(head);

?

頭節點：不存任何數據的空節點，通常作為鏈表的第一個節點。

② 在鏈表頭部分別插入節點node1、node2：

?

/*?頭插法插入一個節點node1?*/
node_st?*node1?=?(node_st?*)malloc(sizeof(node_st));
node1->data?=?1;
SLIST_INSERT_HEAD(head,?node1,?field);

/*?頭插法插入一個節點node2?*/
node_st?*node2?=?(node_st?*)malloc(sizeof(node_st));
node2->data?=?2;
SLIST_INSERT_HEAD(head,?node2,?field);

?

頭指針：永遠指向鏈表第一個節點的位置。

SLIST_INSERT_HEAD是從鏈表頭部插入節點，新節點總是從頭結點之后插入。

③ 在鏈表節點node2之后插入節點node3：

?

node_st?*node3?=?(node_st?*)malloc(sizeof(node_st));
node3->data?=?3;
SLIST_INSERT_AFTER(node2,?node3,?field);

?

SLIST_INSERT_AFTER是從指定節點slistelm之后插入新節點elm。

④ 遍歷鏈表：

?

node_st?*tmp_elm;
SLIST_FOREACH(tmp_elm,?head,?field)
{
?printf("%d?",?tmp_elm->data);
}

?

輸出為tmp_elm，訪問tmp_elm即可。

⑤ 刪除某個節點node2

?

SLIST_REMOVE(head,?node2,?node,?field);
free(node2);
node2?=?NULL;

?

⑥ 銷毀整個鏈表

?

while?(!SLIST_EMPTY(head))?
{????
????node_st?*p?=?SLIST_FIRST(head);
????SLIST_REMOVE_HEAD(head,?field);
????free(p);
????p?=?NULL;
}
free(head);
head?=?NULL;

?

完整測試代碼：

?

#include?
#include?
#include?

#define?ELEM_TYPE?int

/*?鏈表節點?*/
typedef?struct?node?
{
????ELEM_TYPE?data;
????SLIST_ENTRY(node)?field;?
}node_st;

/*?鏈表頭?*/
typedef?SLIST_HEAD(head,?node)?head_st;

int?main(void)
{
????/*?創建鏈表頭節點并初始化?*/
????head_st?*head?=?(head_st?*)malloc(sizeof(head_st));
????SLIST_INIT(head);

????/*?頭插法插入一個節點node1?*/
????node_st?*node1?=?(node_st?*)malloc(sizeof(node_st));
????node1->data?=?1;
????SLIST_INSERT_HEAD(head,?node1,?field);

????/*?頭插法插入一個節點node2?*/
????node_st?*node2?=?(node_st?*)malloc(sizeof(node_st));
????node2->data?=?2;
????SLIST_INSERT_HEAD(head,?node2,?field);

????/*?遍歷打印當前鏈表節點?*/
????printf("list:
");
????node_st?*tmp_elm;
????SLIST_FOREACH(tmp_elm,?head,?field)
????{
????????printf("%d?",?tmp_elm->data);
????}
????printf("
");

????/*?尾插法插入一個節點node3?*/
????printf("insert?node3:
");
????node_st?*node3?=?(node_st?*)malloc(sizeof(node_st));
????node3->data?=?3;
????SLIST_INSERT_AFTER(node2,?node3,?field);
????SLIST_FOREACH(tmp_elm,?head,?field)
????{
????????printf("%d?",?tmp_elm->data);
????}
????printf("
");

????/*?刪除node2?*/
????printf("delete?node2:
");
????SLIST_REMOVE(head,?node2,?node,?field);
????free(node2);
????node2?=?NULL;
????SLIST_FOREACH(tmp_elm,?head,?field)
????{
????????printf("%d?",?tmp_elm->data);
????}
????printf("
");

????/*?銷毀鏈表?*/
????while?(!SLIST_EMPTY(head))?
????{????
????????node_st?*p?=?SLIST_FIRST(head);
????????SLIST_REMOVE_HEAD(head,?field);
????????free(p);
????????p?=?NULL;
????}
????free(head);
????head?=?NULL;

????return?0;
}

?

編譯、運行：

運行結果與我們上面分析的一致。

本次我們只分享queue.h里最簡單的數據結構。其它幾種數據結構的使用例子及相關宏說明可以通過man命令查看。

man是Linux下的幫助命令。

我們輸入 man queue 即可查到queue.h的相關說明：

可以看到，man命令很強大，可查到queue的幫助說明很詳細，有宏的說明及使用示例等。

以上就是本次的分享，文章如有錯誤，歡迎支持，謝謝！我們下期見~

　　審核編輯：湯梓紅