當(dāng)前位置：首頁(yè) > 人工智能 > ChatGpt >内容正文

ChatGpt

链表之TAILQ

發(fā)布時(shí)間：2025/3/15 ChatGpt 35 豆豆

生活随笔收集整理的這篇文章主要介紹了链表之TAILQ 小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

文章目錄

- TAILQ 介紹
- 頭文件
- 舉例
- 代碼分析
- - TAILQ_ENTRY 和 TAILQ_HEAD
  - TAILQ_INIT
  - TAILQ_INSERT_HEAD
  - TAILQ_INSERT_TAIL
  - TAILQ_INSERT_AFTER
  - TAILQ_INSERT_BEFORE
  - TAILQ_REMOVE
  - TAILQ_FOREACH
  - TAILQ_FOREACH_REVERSE
- 參考資料

TAILQ 介紹

TAILQ 隊(duì)列是 FreeBSD 內(nèi)核中的一種隊(duì)列數(shù)據(jù)結(jié)構(gòu)，在一些著名的開源庫(kù)中(如 DPDK、libevent)有廣泛的應(yīng)用。

TAILQ 和Linux中l(wèi)ist的組織方式不一樣，后者是單純地將 struct list_head 作為鏈表的掛接點(diǎn)，并沒有用戶的信息，它們的差別如下圖。

Linux中的list只將struct list_head作為用戶元素的掛接點(diǎn)，因此在正向遍歷鏈表時(shí)，需要使用container_of這類接口才能獲取用戶的數(shù)據(jù)，而TAILQ由于tqe_next指針直接指向用戶元素，所以理論上，正向遍歷TAILQ比list更快.

頭文件

頭文件來自我最近看的項(xiàng)目：apache-mynewt-core-1.9.0\sys\sys\include\sys\queue.h

僅截取部分。

// "bsd_queue.h" 為了測(cè)試，我重新起了名字/** @(#)queue.h 8.5 (Berkeley) 8/20/94* $FreeBSD: src/sys/sys/queue.h,v 1.32.2.7 2002/04/17 14:21:02 des Exp $*//** Tail queue declarations.*/ #define TAILQ_HEAD(name, type) \ struct name { \struct type *tqh_first; /* first element */ \struct type **tqh_last; /* addr of last next element */ \ }#define TAILQ_HEAD_INITIALIZER(head) \{ NULL, &(head).tqh_first }#define TAILQ_ENTRY(type) \ struct { \struct type *tqe_next; /* next element */ \struct type **tqe_prev; /* address of previous next element */ \ }/** Tail queue functions.*/ #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)#define TAILQ_FIRST(head) ((head)->tqh_first)#define TAILQ_FOREACH(var, head, field) \for ((var) = TAILQ_FIRST((head)); \(var); \(var) = TAILQ_NEXT((var), field))#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \for ((var) = TAILQ_LAST((head), headname); \(var); \(var) = TAILQ_PREV((var), headname, field))#define TAILQ_INIT(head) do { \TAILQ_FIRST((head)) = NULL; \(head)->tqh_last = &TAILQ_FIRST((head)); \ } while (0)#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\TAILQ_NEXT((elm), field)->field.tqe_prev = \&TAILQ_NEXT((elm), field); \else \(head)->tqh_last = &TAILQ_NEXT((elm), field); \TAILQ_NEXT((listelm), field) = (elm); \(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ } while (0)#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \TAILQ_NEXT((elm), field) = (listelm); \*(listelm)->field.tqe_prev = (elm); \(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ } while (0)#define TAILQ_INSERT_HEAD(head, elm, field) do { \if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \TAILQ_FIRST((head))->field.tqe_prev = \&TAILQ_NEXT((elm), field); \else \(head)->tqh_last = &TAILQ_NEXT((elm), field); \TAILQ_FIRST((head)) = (elm); \(elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ } while (0)#define TAILQ_INSERT_TAIL(head, elm, field) do { \TAILQ_NEXT((elm), field) = NULL; \(elm)->field.tqe_prev = (head)->tqh_last; \*(head)->tqh_last = (elm); \(head)->tqh_last = &TAILQ_NEXT((elm), field); \ } while (0)#define TAILQ_LAST(head, headname) \(*(((struct headname *)((head)->tqh_last))->tqh_last))#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)#define TAILQ_PREV(elm, headname, field) \(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))#define TAILQ_REMOVE(head, elm, field) do { \if ((TAILQ_NEXT((elm), field)) != NULL) \TAILQ_NEXT((elm), field)->field.tqe_prev = \(elm)->field.tqe_prev; \else \(head)->tqh_last = (elm)->field.tqe_prev; \*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ } while (0)

舉例

來自 https://manpages.courier-mta.org/htmlman3/tailq.3.html

#include <stddef.h> #include <stdio.h> #include <stdlib.h> #include "bsd_queue.h" //沒有用 Linux 的，換成了我自己的struct entry {int data;TAILQ_ENTRY(entry) entries; /* Tail queue */ };TAILQ_HEAD(tailhead, entry);int main(void) {struct entry *n1, *n2, *n3, *np;struct tailhead head; /* Tail queue head */int i;TAILQ_INIT(&head); /* Initialize the queue */n1 = malloc(sizeof(struct entry)); /* Insert at the head */TAILQ_INSERT_HEAD(&head, n1, entries);n1 = malloc(sizeof(struct entry)); /* Insert at the tail */TAILQ_INSERT_TAIL(&head, n1, entries);n2 = malloc(sizeof(struct entry)); /* Insert after */TAILQ_INSERT_AFTER(&head, n1, n2, entries);n3 = malloc(sizeof(struct entry)); /* Insert before */TAILQ_INSERT_BEFORE(n2, n3, entries);TAILQ_REMOVE(&head, n2, entries); /* Deletion */free(n2);/* Forward traversal */i = 0;TAILQ_FOREACH(np, &head, entries)np->data = i++;/* Reverse traversal */TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)printf("%i\n", np->data);/* TailQ deletion */n1 = TAILQ_FIRST(&head);while (n1 != NULL) {n2 = TAILQ_NEXT(n1, entries);free(n1);n1 = n2;}TAILQ_INIT(&head);exit(EXIT_SUCCESS); }

代碼分析

TAILQ_ENTRY 和 TAILQ_HEAD

struct entry {int data;TAILQ_ENTRY(entry) entries; /* Tail queue */ };TAILQ_HEAD(tailhead, entry);

TAILQ_ENTRY(entry) entries 中的 entry 由用戶指定，是外層大結(jié)構(gòu)體的標(biāo)簽，宏展開后就是下面的第 1,4,5 行中的 entry；entries 也由用戶指定，是無標(biāo)簽結(jié)構(gòu)體的成員名，宏展開后是下面第 6 行中的 entries

struct entry {int data;struct { struct entry *tqe_next; struct entry **tqe_prev; } entries; };struct tailhead { struct entry *tqh_first; struct entry **tqh_last; };

TAILQ_HEAD(tailhead, entry) 中的 tailhead 由用戶指定，是表頭結(jié)構(gòu)體的標(biāo)簽，如上面第 9 行的 tailhead，entry 要和 TAILQ_ENTRY 中的第一個(gè)參數(shù)保持一致。

struct entry **tqh_last 和 struct entry **tqe_prev 看起來有點(diǎn)詭異，為什么是二級(jí)指針？

改成一級(jí)的行不行？

如果把第 5 行改成 struct entry *tqe_prev，肯定不行，如果它的前面是頭節(jié)點(diǎn)怎么辦，頭節(jié)點(diǎn)的定義里面沒有 struct entry 啊！

再仔細(xì)看看，不管是頭節(jié)點(diǎn)還是普通節(jié)點(diǎn)，都有 struct entry * 這個(gè)類型，那就定義一個(gè)類型為 struct entry ** 的變量好了。這樣前插的時(shí)候就可以統(tǒng)一處理了，例子見 TAILQ_INSERT_BEFORE

總結(jié)一下，定義 TAILQ 的時(shí)候，有 3 個(gè)基本要素：

結(jié)構(gòu)體 struct entry：TAILQ_ENTRY() 的參數(shù)和 TAILQ_HEAD() 的第二個(gè)參數(shù)

結(jié)構(gòu)體 struct tailhead：TAILQ_HEAD() 的第一個(gè)參數(shù)

變量 entries：緊跟在 TAILQ_ENTRY() 后面

TAILQ_INIT

struct entry *n1, *n2, *n3, *np;struct tailhead head; /* Tail queue head */int i;TAILQ_INIT(&head); /* Initialize the queue */

第 5 行，宏展開是

(((&head))->tqh_first) = ((void *)0); (&head)->tqh_last = &(((&head))->tqh_first);

意思是表頭的 tqh_first 為 NULL，tqh_last 指向自己的 tqh_first

TAILQ_INSERT_HEAD

n1 = malloc(sizeof(struct entry)); /* Insert at the head */TAILQ_INSERT_HEAD(&head, n1, entries);

2:宏展開

if (((((n1))->entries.tqe_next) = (((&head))->tqh_first)) != ((void *)0)) (((&head))->tqh_first)->entries.tqe_prev = &(((n1))->entries.tqe_next); else (&head)->tqh_last = &(((n1))->entries.tqe_next); (((&head))->tqh_first) = (n1); (n1)->entries.tqe_prev = &(((&head))->tqh_first);

要把 n1 插入到隊(duì)列的第一個(gè)位置，需要修改哪些指針呢？

n1 的 entries.tqe_next

n1 的 entries.tqe_prev

(&head))->tqh_first

之前第一個(gè)節(jié)點(diǎn)的 entries.tqe_prev

如果 n1 是唯一的節(jié)點(diǎn)，還需要修改 (&head)->tqh_last

好，我們看代碼是如何解決的。

第 1 行解決了 1

第 2 行解決了 4，這個(gè)要解釋一下，(((&head))->tqh_first)->entries.tqe_prev 表示插入 n1 之前的第一個(gè)節(jié)點(diǎn)的 tqe_prev，插入后，它應(yīng)該指向 n1 的 tqe_next

第 4 行解決了 5

第 6 行解決了 3

第 7 行解決了 2

TAILQ_INSERT_TAIL

n1 = malloc(sizeof(struct entry)); /* Insert at the tail */TAILQ_INSERT_TAIL(&head, n1, entries);

把 n1 插入到隊(duì)列的末尾，需要修改哪些指針呢？

(&head)->tqh_last

n1 的 entries.tqe_next 應(yīng)該為 NULL

n1 的 entries.tqe_prev

n1 插入之前最后一個(gè)節(jié)點(diǎn)（叫 n0 吧）的 entries.tqe_next

第 2 行，展開宏

(((n1))->entries.tqe_next) = ((void *)0); (n1)->entries.tqe_prev = (&head)->tqh_last; *(&head)->tqh_last = (n1); (&head)->tqh_last = &(((n1))->entries.tqe_next);

第 1 行解決了 2

第 2 行解決了 3

第 3 行解決了 4，因?yàn)椴迦胫?(&head)->tqh_last 指向 n0 的 entries.tqe_next，對(duì) (&head)->tqh_last 解引用，就得到變量 n0 的 entries.tqe_next，它應(yīng)該等于 n1

第 4 行解決了 1

TAILQ_INSERT_AFTER

n2 = malloc(sizeof(struct entry)); /* Insert after */TAILQ_INSERT_AFTER(&head, n1, n2, entries);

把 n2 插入到 n1 的后面，需要修改哪些指針呢？

n1 的 entries.tqe_next

n2 的 entries.tqe_prev

n2 的 entries.tqe_next

插入 n2 之前，如果 n1 后面有個(gè) n3，則需要修改 n3 的 entries.tqe_prev；

插入 n2 之前，如果 n1 是最后一個(gè)節(jié)點(diǎn)，則要修改 (&head)->tqh_last

第 2 行宏展開：

if (((((n2))->entries.tqe_next) = (((n1))->entries.tqe_next)) != ((void *)0)) (((n2))->entries.tqe_next)->entries.tqe_prev = &(((n2))->entries.tqe_next); else (&head)->tqh_last = &(((n2))->entries.tqe_next); (((n1))->entries.tqe_next) = (n2); (n2)->entries.tqe_prev = &(((n1))->entries.tqe_next);

第 1 行解決了 3

第 2 行解決了 4

第 4 行解決了 5

第 6 行解決了1

第 7 行解決了 2

TAILQ_INSERT_BEFORE

n3 = malloc(sizeof(struct entry)); /* Insert before */TAILQ_INSERT_BEFORE(n2, n3, entries);

把 n3 插入到 n2 的前面，需要修改哪些指針呢？

n3 的 entries.tqe_next

n2 的 entries.tqe_prev

n3 的 entries.tqe_prev

插入 n3 之前，如果 n2 的前面有個(gè) n1，則需要修改 n1 的 entries.tqe_next，

即 (n1)->entries.tqe_next = n3;

插入 n3 之前，如果 n2 是第一個(gè)節(jié)點(diǎn)，則要修改 (&head)->tqh_first，

即 (&head)->tqh_first = n3;

第 2 行宏展開

(n3)->entries.tqe_prev = (n2)->entries.tqe_prev; (((n3))->entries.tqe_next) = (n2); *(n2)->entries.tqe_prev = (n3); (n2)->entries.tqe_prev = &(((n3))->entries.tqe_next);

第 1 行解決了 3

第 2 行解決了 1

第 3 行解決了 4 和 5（馬上會(huì)解釋）

第 4 行解決了 2

解釋：

插入 n3 之前，如果 n2 的前面有個(gè) n1，

那么 *(n2)->entries.tqe_prev 代表變量 (n1)->entries.tqe_next

插入 n3 之前，如果 n2 是第一個(gè)節(jié)點(diǎn)，

那么 *(n2)->entries.tqe_prev 代表變量 (&head)->tqh_first

所以這兩種情況可以合并，寫成

*(n2)->entries.tqe_prev = (n3);

TAILQ_REMOVE

TAILQ_REMOVE(&head, n2, entries); /* Deletion */free(n2);

要把 n2 從鏈表移除，需要修改哪些指針呢？

n2 前面那個(gè)節(jié)點(diǎn)（假設(shè)是 n1）的 entries.tqe_next

n2 后面那個(gè)節(jié)點(diǎn)（假設(shè)是 n3）的 entries.tqe_prev

如果 n2 是最后一個(gè)節(jié)點(diǎn)，那么要修改 (&head)->tqh_last

第 1 行宏展開

if (((((n2))->entries.tqe_next)) != ((void *)0)) (((n2))->entries.tqe_next)->entries.tqe_prev = (n2)->entries.tqe_prev; else (&head)->tqh_last = (n2)->entries.tqe_prev; *(n2)->entries.tqe_prev = (((n2))->entries.tqe_next);

第 1 行判斷 n2 是否為最后一個(gè)節(jié)點(diǎn)

第 2 行解決了 2

第 4 行解決了 3

第 5 行解決了 1，這個(gè)解釋一下。(n2)->entries.tqe_prev 指向的是 n1 的 entries.tqe_next，對(duì) (n2)->entries.tqe_prev 解引用，得到變量 (n1)->entries.tqe_next，需要給它賦值為 n3 的地址，即 (n2)->entries.tqe_next；如果 (n2)->entries.tqe_prev 指向表頭的 tqh_first，第 5 行也是成立的

TAILQ_FOREACH

i = 0;/* Forward traversal */TAILQ_FOREACH(np, &head, entries)np->data = i++;

第 2 行就是

for ((np) = (((&head))->tqh_first); (np); (np) = (((np))->entries.tqe_next))

比較簡(jiǎn)單，不需要解釋。

TAILQ_FOREACH_REVERSE

/* Reverse traversal */TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)printf("%i\n", np->data);

這次我們換個(gè)思路，不看展開后是什么，而是看看宏的定義

#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \for ((var) = TAILQ_LAST((head), headname); \(var); \(var) = TAILQ_PREV((var), headname, field))#define TAILQ_LAST(head, headname) \(*(((struct headname *)((head)->tqh_last))->tqh_last))#define TAILQ_PREV(elm, headname, field) \(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

第 7 行，可以得到最后一個(gè)節(jié)點(diǎn)的地址。解釋一下：

(head)->tqh_last 是最后一個(gè)節(jié)點(diǎn)的 entries.tqe_next 的地址，可是這個(gè)地址不是用戶想要的，用戶要的是節(jié)點(diǎn)的地址，就是大結(jié)構(gòu)體（ struct entry ）的地址，所以只好曲線救國(guó)，如下圖，從 1 到 2 再到 3

從 entries.tqe_next 的地址怎么得到 entries.tqe_prev 的值呢？

其實(shí)也不難，雖然 struct entry 里面 entries 這個(gè)結(jié)構(gòu)體變量沒有標(biāo)簽，但是它的元素構(gòu)成和 struct headname 完全一樣，都是一個(gè) struct entry * 和一個(gè) struct entry **，所以可以把 entries.tqe_next 的地址強(qiáng)制轉(zhuǎn)換為 (struct headname *) 類型: (struct headname *)((head)->tqh_last)

然后訪問它的 tqh_last 成員（也就是圖中的 prev）：

((struct headname *)((head)->tqh_last))->tqh_last

這樣就得到了前一個(gè)節(jié)點(diǎn)的 entries.tqe_next 的地址，再對(duì)它解引用：

*(((struct headname *)((head)->tqh_last))->tqh_last)

就得到了 entries.tqe_next 變量，這恰好是大結(jié)構(gòu)體（ struct entry ）的地址

我們?cè)倏?TAILQ_PREV 這個(gè)宏，道理類似。

如圖所示，從 1 到 2 再到 3

設(shè)當(dāng)前節(jié)點(diǎn)的地址是 elm（圖中用最后這個(gè)節(jié)點(diǎn)來示意），(elm)->field.tqe_prev ，表示順著 1，得到它前面那個(gè)節(jié)點(diǎn)的 next 的地址，對(duì)這個(gè)地址強(qiáng)制轉(zhuǎn)換為 struct headname *，即

(struct headname *)((elm)->field.tqe_prev)

再訪問 prev，也就是順著 2，得到了 elm 前面的前面的節(jié)點(diǎn)的 next 地址

即 ((struct headname *)((elm)->field.tqe_prev))->tqh_last

對(duì)它解引用，就得到 elm 前面的前面的節(jié)點(diǎn)的 next，即

*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)

它剛好是 3 這個(gè)指針表示的地址。

其他的宏比較簡(jiǎn)單，就不介紹了

參考資料

https://manpages.courier-mta.org/htmlman3/tailq.3.html

TAILQ 隊(duì)列之一二事 - SegmentFault 思否

總結(jié)

以上是生活随笔為你收集整理的链表之TAILQ的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

链表
TAILQ

上一篇：编写程序，对用户输入的n个整数，统计其最
下一篇：链表之CIRCLEQ