單鏈表的極致寫法：STAILQ 宏實現高效隊列操作

編輯：關於C語言

單鏈表的極致寫法：STAILQ 宏實現高效隊列操作

在 C 語言中實現單鏈表時，手寫指針操作既繁瑣又容易出錯。BSD 系統提供的 STAILQ 宏集合（單向尾隊列）讓我們能以極簡潔、高效的方式完成鏈表的插入、遍歷等操作。本文通過一個完整示例，展示如何利用這組宏構建高性能的單鏈表。

核心宏定義解析

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define STAILQ_ENTRY(type) \
struct { \
    struct type *stqe_next; \
}

struct mbuf {
    uint32_t magic;           /* mbuf magic (const) */
    STAILQ_ENTRY(mbuf) next;  /* next mbuf */
    uint8_t *pos;             /* read marker */
    uint8_t *last;            /* write marker */
    uint8_t *start;           /* start of buffer (const) */
    uint8_t *end;             /* end of buffer (const) */
};

#define STAILQ_HEAD(name, type) \
struct name { \
    struct type *stqh_first; \
    struct type **stqh_last; \
}

STAILQ_HEAD(mhdr, mbuf);

#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)

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

關鍵點說明

STAILQ_ENTRY：在結構體中嵌入指向下一個節點的指針，實現無侵入式鏈表節點。
STAILQ_HEAD：定義隊列頭，包含首節點指針和尾節點指針的地址（雙重指針），使尾部插入達到 O(1)。
STAILQ_INSERT_TAIL：利用尾指針的地址直接掛接新節點，無需遍歷整個鏈表。

完整示例程序

int main(void) {
    struct mhdr *mhdr = malloc(sizeof(struct mhdr));
    mhdr->stqh_first = NULL;
    mhdr->stqh_last = &mhdr->stqh_first;

    int i;
    for (i = 0; i < 16; i++) {
        struct mbuf *mbuf = malloc(sizeof(struct mbuf));
        STAILQ_INSERT_TAIL(mhdr, mbuf, next);
        printf("%p ", mbuf);
    }
    printf("\n");

    for (i = 0; i < 16; i++) {
        struct mbuf *mbuf = mhdr->stqh_first;
        printf("%p ", mbuf);
        mhdr->stqh_first = mhdr->stqh_first->next.stqe_next;
    }
    printf("\n");
    return 0;
}

運行結果

[jabari@hbase-rs2-test ~]$ gcc a.c
[jabari@hbase-rs2-test ~]$ ./a.out
0x1804030 0x1804070 0x18040b0 0x18040f0 0x1804130 0x1804170 0x18041b0 0x18041f0 0x1804230 0x1804270 0x18042b0 0x18042f0 0x1804330 0x1804370 0x18043b0 0x18043f0
0x1804030 0x1804070 0x18040b0 0x18040f0 0x1804130 0x1804170 0x18041b0 0x18041f0 0x1804230 0x1804270 0x18042b0 0x18042f0 0x1804330 0x1804370 0x18043b0 0x18043f0

輸出顯示 16 個節點依序插入並遍歷，地址完全一致，驗證了隊列操作的正確性。這種寫法不僅代碼精簡，而且運行效率極高，是系統級開發中單鏈表的最佳實踐之一。