链表之STAILQ
文章目錄
- STAILQ 示意圖
- 接口和實(shí)現(xiàn)
- 舉例
- 代碼分析
- STAILQ_ENTRY 和 STAILQ_HEAD
- STAILQ_INIT 和 STAILQ_INSERT_HEAD
- STAILQ_INSERT_TAIL
- STAILQ_INSERT_AFTER
- STAILQ_REMOVE
- STAILQ_FIRST 和 STAILQ_REMOVE_HEAD
- STAILQ_FOREACH
- STAILQ_NEXT
- STAILQ_EMPTY
- STAILQ_LAST
STAILQ 示意圖
STAILQ 和 LIST 的不同是，head 里面有個(gè)指針 stqh_last，指向最后一個(gè)節(jié)點(diǎn)的 stqe_next
注意：有的地方也把 STAILQ 叫 simple queue，將接口前綴改為 SIMPLEQ_
接口和實(shí)現(xiàn)
先貼代碼。（注意：不同版本的代碼可能不同）
/** Singly-linked Tail queue declarations.*/ #define STAILQ_HEAD(name, type) \ struct name { \struct type *stqh_first;/* first element */ \struct type **stqh_last;/* addr of last next element */ \ }#define STAILQ_HEAD_INITIALIZER(head) \{ NULL, &(head).stqh_first }#define STAILQ_ENTRY(type) \ struct { \struct type *stqe_next; /* next element */ \ }/** Singly-linked Tail queue functions.*/ #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)#define STAILQ_FIRST(head) ((head)->stqh_first)#define STAILQ_FOREACH(var, head, field) \for((var) = STAILQ_FIRST((head)); \(var); \(var) = STAILQ_NEXT((var), field))#define STAILQ_INIT(head) do { \STAILQ_FIRST((head)) = NULL; \(head)->stqh_last = &STAILQ_FIRST((head)); \ } while (0)#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\(head)->stqh_last = &STAILQ_NEXT((elm), field); \STAILQ_NEXT((tqelm), field) = (elm); \ } while (0)#define STAILQ_INSERT_HEAD(head, elm, field) do { \if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \(head)->stqh_last = &STAILQ_NEXT((elm), field); \STAILQ_FIRST((head)) = (elm); \ } while (0)#define STAILQ_INSERT_TAIL(head, elm, field) do { \STAILQ_NEXT((elm), field) = NULL; \*(head)->stqh_last = (elm); \(head)->stqh_last = &STAILQ_NEXT((elm), field); \ } while (0)#define STAILQ_LAST(head, type, field) \(STAILQ_EMPTY(head) ? \NULL : \((struct type *) \((char *)((head)->stqh_last) - offsetof(struct type, field))))#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)#define STAILQ_REMOVE(head, elm, type, field) do { \if (STAILQ_FIRST((head)) == (elm)) { \STAILQ_REMOVE_HEAD(head, field); \} \else { \struct type *curelm = STAILQ_FIRST((head)); \while (STAILQ_NEXT(curelm, field) != (elm)) \curelm = STAILQ_NEXT(curelm, field); \if ((STAILQ_NEXT(curelm, field) = \STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\(head)->stqh_last = &STAILQ_NEXT((curelm), field);\} \ } while (0)#define STAILQ_REMOVE_HEAD(head, field) do { \if ((STAILQ_FIRST((head)) = \STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \(head)->stqh_last = &STAILQ_FIRST((head)); \ } while (0)#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \(head)->stqh_last = &STAILQ_FIRST((head)); \ } while (0)#define STAILQ_REMOVE_AFTER(head, elm, field) do { \if ((STAILQ_NEXT(elm, field) = \STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \(head)->stqh_last = &STAILQ_NEXT((elm), field); \ } while (0)舉例
咱們看個(gè)例子，例子來(lái)自：https://manpages.courier-mta.org/htmlman3/stailq.3.html
#include <stddef.h> #include <stdio.h> #include <stdlib.h> #include <sys/queue.h>struct entry {int data;STAILQ_ENTRY(entry) entries; /* Singly linked tail queue */ };STAILQ_HEAD(stailhead, entry);int main(void) {struct entry *n1, *n2, *n3, *np;struct stailhead head; /* Singly linked tail queuehead */STAILQ_INIT(&head); /* Initialize the queue */n1 = malloc(sizeof(struct entry)); /* Insert at the head */STAILQ_INSERT_HEAD(&head, n1, entries);n1 = malloc(sizeof(struct entry)); /* Insert at the tail */STAILQ_INSERT_TAIL(&head, n1, entries);n2 = malloc(sizeof(struct entry)); /* Insert after */STAILQ_INSERT_AFTER(&head, n1, n2, entries);STAILQ_REMOVE(&head, n2, entry, entries); /* Deletion */free(n2);n3 = STAILQ_FIRST(&head);STAILQ_REMOVE_HEAD(&head, entries); /* Deletion from the head */free(n3);n1 = STAILQ_FIRST(&head);n1->data = 0;for (int i = 1; i < 5; i++) {n1 = malloc(sizeof(struct entry));STAILQ_INSERT_HEAD(&head, n1, entries);n1->data = i;}/* Forward traversal */STAILQ_FOREACH(np, &head, entries)printf("%i\n", np->data);/* TailQ deletion */n1 = STAILQ_FIRST(&head);while (n1 != NULL) {n2 = STAILQ_NEXT(n1, entries);free(n1);n1 = n2;}STAILQ_INIT(&head);exit(EXIT_SUCCESS); }代碼分析
STAILQ_ENTRY 和 STAILQ_HEAD
struct entry {int data;STAILQ_ENTRY(entry) entries; /* Singly linked tail queue */ };STAILQ_HEAD(stailhead, entry);宏替換后是
struct entry {int data;struct { struct entry *stqe_next; } entries; };struct stailhead { struct entry *stqh_first; struct entry **stqh_last; };其實(shí)和 SLIST 差不多，唯一的不同是第 10 行，多了一個(gè)指向尾節(jié)點(diǎn)的指針（準(zhǔn)確地說(shuō)是指向尾節(jié)點(diǎn)的 stqe_next）
STAILQ_INIT 和 STAILQ_INSERT_HEAD
struct entry *n1, *n2, *n3, *np;struct stailhead head; /* Singly linked tail queuehead */STAILQ_INIT(&head); /* Initialize the queue */n1 = malloc(sizeof(struct entry)); /* Insert at the head */STAILQ_INSERT_HEAD(&head, n1, entries);5：宏展開(kāi)是
(&head)->stqh_first = ((void *)0); (&head)->stqh_last = &(&head)->stqh_first;鏈表的初始化為空，stqh_first 等于 NULL，stqh_last 指向自己的 stqh_first
8：宏展開(kāi)是
if (((n1)->entries.stqe_next = (&head)->stqh_first) == ((void *)0)) (&head)->stqh_last = &(n1)->entries.stqe_next; (&head)->stqh_first = (n1);把 n1 插入鏈表的第一個(gè)位置，會(huì)影響哪個(gè)指針的值呢？
第 1 行解決了 2
第 2 行解決了 3
第 3 行解決了 1
STAILQ_INSERT_TAIL
n1 = malloc(sizeof(struct entry)); /* Insert at the tail */STAILQ_INSERT_TAIL(&head, n1, entries);2：宏替換是
(n1)->entries.stqe_next = ((void *)0); *(&head)->stqh_last = (n1); (&head)->stqh_last = &(n1)->entries.stqe_next;把 n1 插入鏈表的最后一個(gè)位置，會(huì)影響哪些指針的值呢？
第 1 行解決了 2
第 2 行有點(diǎn)麻煩，(&head)->stqh_last 指向 n8 節(jié)點(diǎn)的 stqe_next，*(&head)->stqh_last 就是 n8 節(jié)點(diǎn)的 stqe_next，賦值 n1 給它，解決了 3
第 3 行解決了 1
STAILQ_INSERT_AFTER
n2 = malloc(sizeof(struct entry)); /* Insert after */STAILQ_INSERT_AFTER(&head, n1, n2, entries);第 2 行的意思是把 n2 插入到 n1 的后面
代碼展開(kāi)后是
if (((n2)->entries.stqe_next = (n1)->entries.stqe_next) == ((void *)0)) (&head)->stqh_last = &(n2)->entries.stqe_next; (n1)->entries.stqe_next = (n2);把 n2 插入到 n1 的后面，會(huì)影響哪些指針的值呢？
第 1 行的 (n2)->entries.stqe_next = (n1)->entries.stqe_next) 解決了 2
第 3 行解決了 1
第 2 行解決了 3
STAILQ_REMOVE
STAILQ_REMOVE(&head, n2, entry, entries); /* Deletion */free(n2);第 1 行展開(kāi)是，有點(diǎn)長(zhǎng)
if ((&head)->stqh_first == (n2)) { if ((((&head))->stqh_first = ((&head))->stqh_first->entries.stqe_next) == ((void *)0)) ((&head))->stqh_last = &((&head))->stqh_first; } else { struct entry *curelm = (&head)->stqh_first; while (curelm->entries.stqe_next != (n2)) curelm = curelm->entries.stqe_next; if ((curelm->entries.stqe_next = curelm->entries.stqe_next->entries.stqe_next) == ((void *)0)) (&head)->stqh_last = &(curelm)->entries.stqe_next; }分 2 種情況。n2 是不是第一個(gè)節(jié)點(diǎn)（第 1 行代碼），如果是，需要修改的指針有
第 2 行的前半句解決了 1
第 3 行解決了 2
如果 n2 不是第一個(gè)節(jié)點(diǎn)，那就執(zhí)行 5-10，先查找 n2 (6-7 行)，當(dāng)找到的時(shí)候， curelm 代表 n2 前面的那個(gè)節(jié)點(diǎn)。此時(shí)需要修改的指針有：
第 8 行的前半句解決了 1
第 9 行解決了 2
STAILQ_FIRST 和 STAILQ_REMOVE_HEAD
n3 = STAILQ_FIRST(&head);STAILQ_REMOVE_HEAD(&head, entries); /* Deletion from the head */free(n3);STAILQ_FIRST 比較簡(jiǎn)單，就是取鏈表的第一個(gè)節(jié)點(diǎn)，注意，不是刪除
第 1 行展開(kāi)：n3 = ((&head)->stqh_first);
STAILQ_REMOVE_HEAD 是刪除第一個(gè)節(jié)點(diǎn)
第 2 行展開(kāi)：
if (((&head)->stqh_first = (&head)->stqh_first->entries.stqe_next) == ((void *)0)) (&head)->stqh_last = &(&head)->stqh_first;如果刪除之前，僅有一個(gè)節(jié)點(diǎn)，那么需要修改 stqh_last，也就是第 2 行
如果有多個(gè)節(jié)點(diǎn)，那么只需要修改 stqh_first（第 1 行的前半句）
STAILQ_FOREACH
/* Forward traversal */ STAILQ_FOREACH(np, &head, entries)printf("%i\n", np->data);STAILQ_FOREACH(np, &head, entries) 用來(lái)遍歷鏈表的每個(gè)節(jié)點(diǎn)。第一個(gè)參數(shù)是臨時(shí)變量，指向當(dāng)前的節(jié)點(diǎn)，第二個(gè)參數(shù)是表頭的地址，第三個(gè) entries 是無(wú)標(biāo)簽結(jié)構(gòu)體的成員名。
第 2 行展開(kāi)：
for ((np) = ((&head)->stqh_first); (np); (np) = ((np)->entries.stqe_next))printf("%i\n", np->data);典型的遍歷。注意，這種遍歷是不能刪除的，因?yàn)槿绻?np 指向的節(jié)點(diǎn)刪除了，
(np)->entries.stqe_next 這句就不對(duì)了。
STAILQ_NEXT
/* TailQ deletion */n1 = STAILQ_FIRST(&head);while (n1 != NULL) {n2 = STAILQ_NEXT(n1, entries);free(n1);n1 = n2;}STAILQ_NEXT(n1, entries) 表示取 n1 的下一個(gè)節(jié)點(diǎn)
第 4 行展開(kāi)是 n2 = ((n1)->entries.stqe_next); 比較簡(jiǎn)單。
這段代碼也展示了如何刪除整個(gè)鏈表。
還有幾個(gè)宏，例子里面沒(méi)有用到，我們也看一下。
STAILQ_EMPTY
#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)這個(gè)很好理解，不解釋了。
STAILQ_LAST
#define STAILQ_LAST(head, type, field) \(STAILQ_EMPTY(head) ? \NULL : \((struct type *) \((char *)((head)->stqh_last) - offsetof(struct type, field))))注意，我的 Linux 操作系統(tǒng)上，并不包含這個(gè)宏，所以，如果要用，需要手工把這段代碼包含進(jìn)去。
這個(gè)宏的意思找到隊(duì)列的最后一個(gè)節(jié)點(diǎn)。它是這么用的：
n1 = STAILQ_LAST(&head, entry, entries);
本文開(kāi)始的時(shí)候，有
struct entry {int data;STAILQ_ENTRY(entry) entries; /* Singly linked tail queue */ };STAILQ_HEAD(stailhead, entry);n1 = STAILQ_LAST(&head, entry, entries) 的后兩個(gè)參數(shù)要對(duì)應(yīng)第 3 行的定義。
我們回頭看 STAILQ_LAST 的代碼
#define STAILQ_LAST(head, type, field) \(STAILQ_EMPTY(head) ? \NULL : \((struct type *) \((char *)((head)->stqh_last) - offsetof(struct type, field))))如果鏈表為空，就返回 NULL，如果不為空呢？當(dāng)然是順著 (head)->stqh_last 找對(duì)最后一個(gè)節(jié)點(diǎn)。
問(wèn)題是，(head)->stqh_last 指向的是最后一個(gè)節(jié)點(diǎn)的 entries.stqe_next 域
struct entry {int data;struct { struct entry *stqe_next; } entries; };也就是第 4 行，(head)->stqh_last 的值是 struct entry *stqe_next 的地址，而不是 struct entry 的地址，所以需要轉(zhuǎn)換一下。轉(zhuǎn)換需要用到
offsetof(struct type, field)
這也是一個(gè)宏，代碼大概在 /usr/src/linux-headers-4.8.0-36-generic/include/linux/stddef.h
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)這里的 TYPE 表示某個(gè)結(jié)構(gòu)體類型，MEMBER 表示結(jié)構(gòu)體中的一個(gè)成員，這個(gè)宏求出了成員在結(jié)構(gòu)體中的位置偏移（以字節(jié)為單位）
假設(shè)一個(gè)結(jié)構(gòu)體變量（類型是 struct entry）的起始地址是 0x1234，它里面有個(gè)成員是 data，請(qǐng)問(wèn) data 變量的地址是多少？
可以這樣求：
&((struct entry *)0x1234)->data
->比類型轉(zhuǎn)換的優(yōu)先級(jí)高，所以要加括號(hào)。((struct entry *)0x1234)->data 就得到了成員，再取地址，得到成員的地址，再來(lái)一個(gè)類型轉(zhuǎn)換，轉(zhuǎn)成無(wú)符號(hào)整形：
(size_t)&((struct entry *)0x1234)->data
終于得到成員的起始地址了，這時(shí)候我們看看它對(duì)于結(jié)構(gòu)體變量的起始地址的偏移是多少？也就是用成員的地址減去結(jié)構(gòu)體變量的地址：
(size_t)&((struct entry *)0x1234)->data - 0x1234
不難看出，這里的 0x1234 換成什么數(shù)字都可以，因?yàn)槠剖且粋€(gè)相對(duì)量，和起始地址無(wú)關(guān)
為了簡(jiǎn)單，那就把 0x1234 換成 0 吧。
我們做一般化的處理，把 struct entry 叫 TYPE，把 data 叫 MEMBER，所以就有了
((size_t)&((TYPE *)0)->MEMBER)咱們回到正題上來(lái)，(head)->stqh_last 的值是 struct entry *stqe_next 的地址，而不是 struct entry 的地址，*如果我們知道 struct entry stqe_next 相對(duì)于 struct entry 的偏移 x，那么用 (head)->stqh_last 減去 x 就可以了。
利用 offsetof(struct type, field) 來(lái)求偏移，同時(shí)注意到 struct entry *stqe_next 和 entries 是同一個(gè)地址，所以偏移是：offsetof(struct entry , entries )
最后一個(gè)節(jié)點(diǎn)的地址是：
(struct entry *)((char*)((head)->stqh_last) - offsetof(struct entry, entries)))把上面這個(gè)式子一般化，entry 換成 type，entries 換成 field，就得到了代碼中的：
((struct type *) \((char *)((head)->stqh_last) - offsetof(struct type, field))))其實(shí)還有更簡(jiǎn)單的方法，直接利用內(nèi)核里面的 container_of 宏，這里只做個(gè)提示，就不展開(kāi)了。
【end】
總結(jié)
- 上一篇： 链表之LIST
- 下一篇： 编写程序，对用户输入的n个整数，统计其最