Linux下一個實用的頭文件

大家好，我是LinuxZn。

本次分享sys/queue.h：

什么是sys/queue.h？

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

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

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

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

SLIST：單向無尾鏈表

LIST：雙向無尾鏈表

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

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

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

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

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

刪除節(jié)點

遍歷節(jié)點

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

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

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

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

#define?ELEM_TYPE?int

/*?鏈表節(jié)點?*/
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)建一個頭結(jié)點：

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

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

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

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

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

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

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

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

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

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

④ 遍歷鏈表：

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

輸出為tmp_elm，訪問tmp_elm即可。

⑤ 刪除某個節(jié)點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

/*?鏈表節(jié)點?*/
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é)點并初始化?*/
????head_st?*head?=?(head_st?*)malloc(sizeof(head_st));
????SLIST_INIT(head);

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

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

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

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

編譯、運行：