當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

链表之SLIST

發(fā)布時間：2025/3/15 编程问答 23 豆豆

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

文章目錄

- 背景
- SLIST 簡介
- 接口和實現(xiàn)
- 舉例
- 代碼分析
- - SLIST_ENTRY 和 SLIST_HEAD
  - SLIST_INIT
  - SLIST_INSERT_HEAD
  - SLIST_INSERT_AFTER
  - SLIST_REMOVE
  - SLIST_FIRST 和 SLIST_REMOVE_HEAD
  - SLIST_FOREACH
  - SLIST_EMPTY 和 SLIST_INIT
- 附錄 queue.h
- 參考資料

背景

對于 C 語言，在編程中需要用到鏈表時，通常需要程序員重新設計鏈表的結構體。這樣做不僅麻煩，且需要驗證代碼的正確性，對于每個閱讀代碼的人，還需要重新理解。

如果有統(tǒng)一的接口，豈不是更好？

在 FreeBSD 中有 queue.h 這樣一個頭文件（Linux 也有，文件路徑是 /usr/include/x86_64-linux-gnu/sys/queue.h，可以查閱 manual 手冊的queue(3) ）。

頭文件 queue.h 為 C 語言中的鏈表提供了更加標準規(guī)范的編程接口。如今的版本多為伯克利加州大學1994年8月的8.5版本（8.5 (Berkeley) 8/20/94）。

queue 分為 SLIST、LIST、STAILQ、TAILQ、CIRCLEQ ，不同的鏈表有著不同的功能支持。queue 的所有源碼都是宏定義，因此完全包含于queue.h當中，無需編譯為庫文件。

我拿到的 queue.h 一共 500 多行，代碼會在本文的末尾附上，不同的版本可能不太一樣。

建議：如果你想在你的項目中使用它，最好的選擇是將你最喜歡的一個復制到你的項目中并使用它。不要依賴操作系統(tǒng)。它只是一個帶有一堆宏的頭文件，不需要庫或任何依賴項即可工作。

SLIST 簡介

SLIST 是 Singly-linked List 的縮寫，意為單向無尾鏈表。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-WuRai1gC-1644726064142)(pics/image-20220101164926598.png)]

SLIST 是最簡單的結構，它適合數(shù)據(jù)量非常大而幾乎不需要刪除數(shù)據(jù)的場合，又或者當做棧使用。

接口和實現(xiàn)

/** Singly-linked List declarations.*/ #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_EMPTY(head) ((head)->slh_first == NULL)#define SLIST_FIRST(head) ((head)->slh_first)#define SLIST_FOREACH(var, head, field) \for ((var) = SLIST_FIRST((head)); \(var); \(var) = SLIST_NEXT((var), field))#define SLIST_INIT(head) do { \SLIST_FIRST((head)) = NULL; \ } while (0)#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \SLIST_NEXT((slistelm), field) = (elm); \ } while (0)#define SLIST_INSERT_HEAD(head, elm, field) do { \SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \SLIST_FIRST((head)) = (elm); \ } while (0)#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)#define SLIST_REMOVE(head, elm, type, field) do { \if (SLIST_FIRST((head)) == (elm)) { \SLIST_REMOVE_HEAD((head), field); \} \else { \struct type *curelm = SLIST_FIRST((head)); \while (SLIST_NEXT(curelm, field) != (elm)) \curelm = SLIST_NEXT(curelm, field); \SLIST_NEXT(curelm, field) = \SLIST_NEXT(SLIST_NEXT(curelm, field), field); \} \ } while (0)#define SLIST_REMOVE_HEAD(head, field) do { \SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ } while (0)

舉例

光看代碼可能會頭暈，我們用例子來說明。

例子來自 https://man7.org/linux/man-pages/man3/SLIST_ENTRY.3.html

#include <stddef.h> #include <stdio.h> #include <stdlib.h> #include <sys/queue.h>struct entry {int data;SLIST_ENTRY(entry) entries; };SLIST_HEAD(slisthead, entry);int main(void) {struct entry *n1, *n2, *n3, *np;struct slisthead head; /* Singly linked list head */SLIST_INIT(&head); /* Initialize the queue */n1 = malloc(sizeof(struct entry)); /* Insert at the head */SLIST_INSERT_HEAD(&head, n1, entries);n2 = malloc(sizeof(struct entry)); /* Insert after */SLIST_INSERT_AFTER(n1, n2, entries);SLIST_REMOVE(&head, n2, entry, entries);/* Deletion */free(n2);// 刪除第一個節(jié)點n3 = SLIST_FIRST(&head);SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head */free(n3);for (int i = 0; i < 5; i++) {n1 = malloc(sizeof(struct entry));SLIST_INSERT_HEAD(&head, n1, entries);n1->data = i;}/* Forward traversal */SLIST_FOREACH(np, &head, entries)printf("%i\n", np->data);while (!SLIST_EMPTY(&head)) { /* List deletion */n1 = SLIST_FIRST(&head);SLIST_REMOVE_HEAD(&head, entries);free(n1);}SLIST_INIT(&head);exit(EXIT_SUCCESS); }

代碼分析

我們一點一點分析。

SLIST_ENTRY 和 SLIST_HEAD

先看結構體的定義

struct entry {int data;SLIST_ENTRY(entry) entries; }; SLIST_HEAD(slisthead, entry);

需要注意，上面有 3 個 entry，不管叫什么名字，必須一致；

int data; 是用戶數(shù)據(jù)，根據(jù)需要添加；

entries 是

struct { struct entry *sle_next; }

類型的成員（注：這個結構體沒有標簽），entries 也可以換成別的名字；

slisthead 是鏈表頭結構體的標簽名。

宏替換后就是

struct entry {int data;struct { struct entry *sle_next; } entries; };struct slisthead { struct entry *slh_first; };

可以看到，和我們初學時定義的不太一樣，初學者不太可能把第 4、9 行用結構體包起來。

SLIST_INIT

我們繼續(xù)看。

struct entry *n1, *n2, *n3, *np;struct slisthead head; /* Singly linked list head */SLIST_INIT(&head); /* Initialize the queue */

1：定義了 3 個指向節(jié)點的指針；

2：定義表示表頭的結構體變量 head，slisthead 要和前面的一致；

3：宏替換后是 (&head)->slh_first = NULL; 意思是初始化為一個空的鏈表，頭指針指向 NULL

SLIST_INSERT_HEAD

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

1：為節(jié)點分配內存，這里省略了對返回指的檢查；

2：宏替換后是

(n1)->entries.sle_next = (&head)->slh_first; (&head)->slh_first = (n1);

典型的頭插。SLIST_INSERT_HEAD(&head, n1, entries) 的意思是：把 n1 節(jié)點插入到鏈表 head 的頭部；第一個參數(shù)是表頭的地址，第二參數(shù)是待插入的節(jié)點的地址，第三個參數(shù)是無標簽結構體的成員名，和之前的要一致。

SLIST_INSERT_AFTER

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

2：宏替換后是

(n2)->entries.sle_next = (n1)->entries.sle_next; (n1)->entries.sle_next = (n2);

用大白話說就是把 n1 后面的節(jié)點接在 n2 后面，再把 n2 接到 n1 后面，所以：

SLIST_INSERT_AFTER(n1, n2, entries) 的意思是把節(jié)點 n2 插入到 n1 的后面。n1、n2 都是節(jié)點的地址，entries 是無標簽結構體的成員名，和之前的要一致。

SLIST_REMOVE

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

這個宏替換有點復雜：

if ((&head)->slh_first == (n2)) { ((&head))->slh_first = ((&head))->slh_first->entries.sle_next; } else { struct entry *curelm = (&head)->slh_first; while(curelm->entries.sle_next != (n2)) curelm = curelm->entries.sle_next; curelm->entries.sle_next = curelm->entries.sle_next->entries.sle_next; }

1：看看要刪除的節(jié)點是不是第一個節(jié)點，如果是，就刪除；如果不是，走 else 分支

5：取第一個節(jié)點為當前節(jié)點

6：判斷當前節(jié)點的下一個節(jié)點是不是要刪除的節(jié)點，如果是，while 語句結束，執(zhí)行第 8 行，刪除之。

總結，SLIST_REMOVE(&head, n2, entry, entries) 的意思是：

第一個參數(shù)是表頭的地址，第二參數(shù)是待刪除的節(jié)點的地址，第三和第四個參數(shù)要和最開始定義結構體的時候保持一致，比如 SLIST_ENTRY(entry) entries 中的 entry、entries

SLIST_FIRST 和 SLIST_REMOVE_HEAD

n3 = SLIST_FIRST(&head);SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head */free(n3);

宏替換是：

n3 = ((&head)->slh_first); (&head)->slh_first = (&head)->slh_first->entries.sle_next;

SLIST_FIRST (&head) 這個宏就是取第一個節(jié)點的地址，參數(shù)是表頭的地址；

2：刪除第一個節(jié)點

為什么會有第 1 行呢？如果不在這個時候保存第一個節(jié)點的地址，那么刪除后，就無法獲得其地址了，也就無法執(zhí)行第 3 行的釋放空間了。所以，這個例子給我們提供了標準的頭刪操作。

SLIST_REMOVE_HEAD(&head, entries) 這個宏的意思是刪除第一個節(jié)點，第一個參數(shù)是表頭的地址，entries 是無標簽結構體的成員名，和之前的要一致。

SLIST_FOREACH

for (int i = 0; i < 5; i++) {n1 = malloc(sizeof(struct entry));SLIST_INSERT_HEAD(&head, n1, entries);n1->data = i;}/* Forward traversal */SLIST_FOREACH(np, &head, entries)printf("%i\n", np->data);

3：SLIST_INSERT_HEAD 這個在前面說了，就是頭插

4：宏替換后，是

for((np) = (&head)->slh_first; (np); (np) = (np)->entries.sle_next)printf("%i\n", np->data);

典型的遍歷。注意，這種遍歷是不能刪除的，因為如果把 np 指向的節(jié)點刪除了，

(np)->entries.sle_next 這句就不對了。

SLIST_FOREACH(np, &head, entries) 用來遍歷鏈表的每個節(jié)點。第一個參數(shù)是臨時變量，指向當前的節(jié)點，第二個參數(shù)是表頭的地址，第三個 entries 是無標簽結構體的成員名，和之前的一致。

這個例子就這一個地方是有打印，打印的結果是：

4 3 2 1 0

因為是頭插，所以先插入的會在鏈表的末尾。遍歷的順序是從頭到尾，所以順序是 4，3，2，1，0

SLIST_EMPTY 和 SLIST_INIT

while (!SLIST_EMPTY(&head)) { /* List deletion */n1 = SLIST_FIRST(&head);SLIST_REMOVE_HEAD(&head, entries);free(n1);}

2-4 行就不解釋了，前文說過了。

SLIST_EMPTY(&head) 宏展開是：

(&head)->slh_first == NULL，就是判斷鏈表是否為空。

附錄 queue.h

/** Copyright (c) 1991, 1993* The Regents of the University of California. All rights reserved.** Redistribution and use in source and binary forms, with or without* modification, are permitted provided that the following conditions* are met:* 1. Redistributions of source code must retain the above copyright* notice, this list of conditions and the following disclaimer.* 2. Redistributions in binary form must reproduce the above copyright* notice, this list of conditions and the following disclaimer in the* documentation and/or other materials provided with the distribution.* 4. Neither the name of the University nor the names of its contributors* may be used to endorse or promote products derived from this software* without specific prior written permission.** THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF* SUCH DAMAGE.** @(#)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 $*/#ifndef _QUEUE_H_ #define _QUEUE_H_#ifdef __cplusplus extern "C" { #endif/** This file defines five types of data structures: singly-linked lists,* singly-linked tail queues, lists, tail queues, and circular queues.** A singly-linked list is headed by a single forward pointer. The elements* are singly linked for minimum space and pointer manipulation overhead at* the expense of O(n) removal for arbitrary elements. New elements can be* added to the list after an existing element or at the head of the list.* Elements being removed from the head of the list should use the explicit* macro for this purpose for optimum efficiency. A singly-linked list may* only be traversed in the forward direction. Singly-linked lists are ideal* for applications with large datasets and few or no removals or for* implementing a LIFO queue.** A singly-linked tail queue is headed by a pair of pointers, one to the* head of the list and the other to the tail of the list. The elements are* singly linked for minimum space and pointer manipulation overhead at the* expense of O(n) removal for arbitrary elements. New elements can be added* to the list after an existing element, at the head of the list, or at the* end of the list. Elements being removed from the head of the tail queue* should use the explicit macro for this purpose for optimum efficiency.* A singly-linked tail queue may only be traversed in the forward direction.* Singly-linked tail queues are ideal for applications with large datasets* and few or no removals or for implementing a FIFO queue.** A list is headed by a single forward pointer (or an array of forward* pointers for a hash table header). The elements are doubly linked* so that an arbitrary element can be removed without a need to* traverse the list. New elements can be added to the list before* or after an existing element or at the head of the list. A list* may only be traversed in the forward direction.** A tail queue is headed by a pair of pointers, one to the head of the* list and the other to the tail of the list. The elements are doubly* linked so that an arbitrary element can be removed without a need to* traverse the list. New elements can be added to the list before or* after an existing element, at the head of the list, or at the end of* the list. A tail queue may be traversed in either direction.** A circle queue is headed by a pair of pointers, one to the head of the* list and the other to the tail of the list. The elements are doubly* linked so that an arbitrary element can be removed without a need to* traverse the list. New elements can be added to the list before or after* an existing element, at the head of the list, or at the end of the list.* A circle queue may be traversed in either direction, but has a more* complex end of list detection.** For details on the use of these macros, see the queue(3) manual page.*** SLIST LIST STAILQ TAILQ CIRCLEQ* _HEAD + + + + +* _HEAD_INITIALIZER + + + + +* _ENTRY + + + + +* _INIT + + + + +* _EMPTY + + + + +* _FIRST + + + + +* _NEXT + + + + +* _PREV - - - + +* _LAST - - + + +* _FOREACH + + + + +* _FOREACH_REVERSE - - - + +* _INSERT_HEAD + + + + +* _INSERT_BEFORE - + - + +* _INSERT_AFTER + + + + +* _INSERT_TAIL - - + + +* _REMOVE_HEAD + - + - -* _REMOVE + + + + +**//** Singly-linked List declarations.*/ #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_EMPTY(head) ((head)->slh_first == NULL)#define SLIST_FIRST(head) ((head)->slh_first)#define SLIST_FOREACH(var, head, field) \for ((var) = SLIST_FIRST((head)); \(var); \(var) = SLIST_NEXT((var), field))#define SLIST_INIT(head) do { \SLIST_FIRST((head)) = NULL; \ } while (0)#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \SLIST_NEXT((slistelm), field) = (elm); \ } while (0)#define SLIST_INSERT_HEAD(head, elm, field) do { \SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \SLIST_FIRST((head)) = (elm); \ } while (0)#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)#define SLIST_REMOVE(head, elm, type, field) do { \if (SLIST_FIRST((head)) == (elm)) { \SLIST_REMOVE_HEAD((head), field); \} \else { \struct type *curelm = SLIST_FIRST((head)); \while (SLIST_NEXT(curelm, field) != (elm)) \curelm = SLIST_NEXT(curelm, field); \SLIST_NEXT(curelm, field) = \SLIST_NEXT(SLIST_NEXT(curelm, field), field); \} \ } while (0)#define SLIST_REMOVE_HEAD(head, field) do { \SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ } while (0)/** 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)/** List declarations.*/ #define LIST_HEAD(name, type) \ struct name { \struct type *lh_first; /* first element */ \ }#define LIST_HEAD_INITIALIZER(head) \{ NULL }#define LIST_ENTRY(type) \ struct { \struct type *le_next; /* next element */ \struct type **le_prev; /* address of previous next element */ \ }/** List functions.*/#define LIST_EMPTY(head) ((head)->lh_first == NULL)#define LIST_FIRST(head) ((head)->lh_first)#define LIST_FOREACH(var, head, field) \for ((var) = LIST_FIRST((head)); \(var); \(var) = LIST_NEXT((var), field))#define LIST_INIT(head) do { \LIST_FIRST((head)) = NULL; \ } while (0)#define LIST_INSERT_AFTER(listelm, elm, field) do { \if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\LIST_NEXT((listelm), field)->field.le_prev = \&LIST_NEXT((elm), field); \LIST_NEXT((listelm), field) = (elm); \(elm)->field.le_prev = &LIST_NEXT((listelm), field); \ } while (0)#define LIST_INSERT_BEFORE(listelm, elm, field) do { \(elm)->field.le_prev = (listelm)->field.le_prev; \LIST_NEXT((elm), field) = (listelm); \*(listelm)->field.le_prev = (elm); \(listelm)->field.le_prev = &LIST_NEXT((elm), field); \ } while (0)#define LIST_INSERT_HEAD(head, elm, field) do { \if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\LIST_FIRST((head)) = (elm); \(elm)->field.le_prev = &LIST_FIRST((head)); \ } while (0)#define LIST_NEXT(elm, field) ((elm)->field.le_next)#define LIST_REMOVE(elm, field) do { \if (LIST_NEXT((elm), field) != NULL) \LIST_NEXT((elm), field)->field.le_prev = \(elm)->field.le_prev; \*(elm)->field.le_prev = LIST_NEXT((elm), field); \ } while (0)/** 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)/** Circular queue declarations.*/ #define CIRCLEQ_HEAD(name, type) \ struct name { \struct type *cqh_first; /* first element */ \struct type *cqh_last; /* last element */ \ }#define CIRCLEQ_HEAD_INITIALIZER(head) \{ (void *)&(head), (void *)&(head) }#define CIRCLEQ_ENTRY(type) \ struct { \struct type *cqe_next; /* next element */ \struct type *cqe_prev; /* previous element */ \ }/** Circular queue functions.*/ #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))#define CIRCLEQ_FIRST(head) ((head)->cqh_first)#define CIRCLEQ_FOREACH(var, head, field) \for ((var) = CIRCLEQ_FIRST((head)); \(var) != (void *)(head) || ((var) = NULL); \(var) = CIRCLEQ_NEXT((var), field))#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \for ((var) = CIRCLEQ_LAST((head)); \(var) != (void *)(head) || ((var) = NULL); \(var) = CIRCLEQ_PREV((var), field))#define CIRCLEQ_INIT(head) do { \CIRCLEQ_FIRST((head)) = (void *)(head); \CIRCLEQ_LAST((head)) = (void *)(head); \ } while (0)#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \CIRCLEQ_NEXT((elm), field) = CIRCLEQ_NEXT((listelm), field); \CIRCLEQ_PREV((elm), field) = (listelm); \if (CIRCLEQ_NEXT((listelm), field) == (void *)(head)) \CIRCLEQ_LAST((head)) = (elm); \else \CIRCLEQ_PREV(CIRCLEQ_NEXT((listelm), field), field) = (elm);\CIRCLEQ_NEXT((listelm), field) = (elm); \ } while (0)#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \CIRCLEQ_NEXT((elm), field) = (listelm); \CIRCLEQ_PREV((elm), field) = CIRCLEQ_PREV((listelm), field); \if (CIRCLEQ_PREV((listelm), field) == (void *)(head)) \CIRCLEQ_FIRST((head)) = (elm); \else \CIRCLEQ_NEXT(CIRCLEQ_PREV((listelm), field), field) = (elm);\CIRCLEQ_PREV((listelm), field) = (elm); \ } while (0)#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \CIRCLEQ_NEXT((elm), field) = CIRCLEQ_FIRST((head)); \CIRCLEQ_PREV((elm), field) = (void *)(head); \if (CIRCLEQ_LAST((head)) == (void *)(head)) \CIRCLEQ_LAST((head)) = (elm); \else \CIRCLEQ_PREV(CIRCLEQ_FIRST((head)), field) = (elm); \CIRCLEQ_FIRST((head)) = (elm); \ } while (0)#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \CIRCLEQ_NEXT((elm), field) = (void *)(head); \CIRCLEQ_PREV((elm), field) = CIRCLEQ_LAST((head)); \if (CIRCLEQ_FIRST((head)) == (void *)(head)) \CIRCLEQ_FIRST((head)) = (elm); \else \CIRCLEQ_NEXT(CIRCLEQ_LAST((head)), field) = (elm); \CIRCLEQ_LAST((head)) = (elm); \ } while (0)#define CIRCLEQ_LAST(head) ((head)->cqh_last)#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)#define CIRCLEQ_REMOVE(head, elm, field) do { \if (CIRCLEQ_NEXT((elm), field) == (void *)(head)) \CIRCLEQ_LAST((head)) = CIRCLEQ_PREV((elm), field); \else \CIRCLEQ_PREV(CIRCLEQ_NEXT((elm), field), field) = \CIRCLEQ_PREV((elm), field); \if (CIRCLEQ_PREV((elm), field) == (void *)(head)) \CIRCLEQ_FIRST((head)) = CIRCLEQ_NEXT((elm), field); \else \CIRCLEQ_NEXT(CIRCLEQ_PREV((elm), field), field) = \CIRCLEQ_NEXT((elm), field); \ } while (0)#ifdef __cplusplus } #endif#endif /* !_SYS_QUEUE_H_ */

參考資料

【1】https://blog.csdn.net/tissar/article/details/86978743

【2】http://manpages.courier-mta.org/htmlman3/slist.3.html

【3】https://wizardforcel.gitbooks.io/100-gcc-tips/content/inhibit-linemarkers.html

【4】where to find Linux version sys/queue.h header file? - Stack Overflow

總結

以上是生活随笔為你收集整理的链表之SLIST的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

链表
slist

上一篇： wireshark网卡权限_设置网卡属性
下一篇： linux命令找目录,linux中何种指