大家好，我是LinuxZn。

本次分享sys/queue.h：

什么是sys/queue.h？

queue.h是Linux、FreeBSD中的一個(gè)頭文件。

FreeBSD：FreeBSD 是一種類 UNIX操作系統(tǒng)。

這是一個(gè)很實(shí)用的頭文件，因?yàn)檫@個(gè)頭文件里全是宏定義操作，所以其不僅可以使用在Linux/嵌入式Linux項(xiàng)目中，也可以使用在單片機(jī)項(xiàng)目中，我也是因?yàn)樵谖覀兊膯纹瑱C(jī)項(xiàng)目中看到，才知道有這么一個(gè)頭文件的。我覺得挺實(shí)用的，與大家分享。

它使用宏實(shí)現(xiàn)了如下數(shù)據(jù)結(jié)構(gòu)：

SLIST：單向無尾鏈表

LIST：雙向無尾鏈表

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

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

所有的數(shù)據(jù)結(jié)構(gòu)都支持如下功能：

在鏈表頭插入節(jié)點(diǎn)

在任意節(jié)點(diǎn)后插入節(jié)點(diǎn)

刪除節(jié)點(diǎn)

遍歷節(jié)點(diǎn)

我們可以在Linux系統(tǒng)的如下路徑中找到這個(gè)頭文件：

/usr/include/sys/queue.h

也可以通過如下網(wǎng)址查看：

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

sys/queue.h的使用

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

SLIST相關(guān)宏定義：

/*
?*?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)

?

下面我們通過實(shí)例來操作。

首先，創(chuàng)建鏈表頭節(jié)點(diǎn)、其它節(jié)點(diǎn)結(jié)構(gòu)體，用到SLIST_HEAD與SLIST_ENTRY這兩個(gè)宏定義：

?

#define?ELEM_TYPE?int

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

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

?

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

① 創(chuàng)建一個(gè)頭結(jié)點(diǎn)：

?

/*?創(chuàng)建鏈表頭節(jié)點(diǎn)并初始化?*/
head_st?*head?=?(head_st?*)malloc(sizeof(head_st));
SLIST_INIT(head);

?

頭節(jié)點(diǎn)：不存任何數(shù)據(jù)的空節(jié)點(diǎn)，通常作為鏈表的第一個(gè)節(jié)點(diǎn)。

② 在鏈表頭部分別插入節(jié)點(diǎn)node1、node2：

?

/*?頭插法插入一個(gè)節(jié)點(diǎn)node1?*/
node_st?*node1?=?(node_st?*)malloc(sizeof(node_st));
node1->data?=?1;
SLIST_INSERT_HEAD(head,?node1,?field);

/*?頭插法插入一個(gè)節(jié)點(diǎn)node2?*/
node_st?*node2?=?(node_st?*)malloc(sizeof(node_st));
node2->data?=?2;
SLIST_INSERT_HEAD(head,?node2,?field);

?

頭指針：永遠(yuǎn)指向鏈表第一個(gè)節(jié)點(diǎn)的位置。

SLIST_INSERT_HEAD是從鏈表頭部插入節(jié)點(diǎn)，新節(jié)點(diǎn)總是從頭結(jié)點(diǎn)之后插入。

③ 在鏈表節(jié)點(diǎn)node2之后插入節(jié)點(diǎn)node3：

?

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

?

SLIST_INSERT_AFTER是從指定節(jié)點(diǎn)slistelm之后插入新節(jié)點(diǎn)elm。

④ 遍歷鏈表：

?

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

?

輸出為tmp_elm，訪問tmp_elm即可。

⑤ 刪除某個(gè)節(jié)點(diǎn)node2

?

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

?

⑥ 銷毀整個(gè)鏈表

?

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

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

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

int?main(void)
{
????/*?創(chuàng)建鏈表頭節(jié)點(diǎn)并初始化?*/
????head_st?*head?=?(head_st?*)malloc(sizeof(head_st));
????SLIST_INIT(head);

????/*?頭插法插入一個(gè)節(jié)點(diǎn)node1?*/
????node_st?*node1?=?(node_st?*)malloc(sizeof(node_st));
????node1->data?=?1;
????SLIST_INSERT_HEAD(head,?node1,?field);

????/*?頭插法插入一個(gè)節(jié)點(diǎn)node2?*/
????node_st?*node2?=?(node_st?*)malloc(sizeof(node_st));
????node2->data?=?2;
????SLIST_INSERT_HEAD(head,?node2,?field);

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

????/*?尾插法插入一個(gè)節(jié)點(diǎn)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;
}

?

編譯、運(yùn)行：

運(yùn)行結(jié)果與我們上面分析的一致。

本次我們只分享queue.h里最簡單的數(shù)據(jù)結(jié)構(gòu)。其它幾種數(shù)據(jù)結(jié)構(gòu)的使用例子及相關(guān)宏說明可以通過man命令查看。

man是Linux下的幫助命令。

我們輸入 man queue 即可查到queue.h的相關(guān)說明：

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

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

　　審核編輯：湯梓紅