QUEUE(3)

名称
SLIST_EMPTY, SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_HEAD, SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER, SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE_HEAD, SLIST_REMOVE, STAILQ_EMPTY, STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH, STAILQ_HEAD, STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER, STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_LAST, STAILQ_NEXT, STAILQ_REMOVE_HEAD, STAILQ_REMOVE, LIST_EMPTY, LIST_ENTRY, LIST_FIRST, LIST_FOREACH, LIST_HEAD, LIST_HEAD_INITIALIZER, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT, LIST_REMOVE, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH, TAILQ_FOREACH_REVERSE, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER, TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_LAST, TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE, CIRCLEQ_EMPTY, CIRCLEQ_ENTRY, CIRCLEQ_FIRST, CIRCLEQ_FOREACH, CIRCLEQ_FOREACH_REVERSE, CIRCLEQ_HEAD, CIRCLEQ_HEAD_INITIALIZER, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLE_LAST, CIRCLE_NEXT, CIRCLE_PREV, CIRCLEQ_REMOVE - 単一リンクリスト、単一リンクテールキュー、リスト、テールキュー、 循環キューの実装

書式
<sys/queue.h> SLIST_EMPTY(SLIST_HEAD *head) SLIST_ENTRY(TYPE) SLIST_FIRST(SLIST_HEAD *head) SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME) SLIST_HEAD(HEADNAME, TYPE) SLIST_HEAD_INITIALIZER(SLIST_HEAD head) SLIST_INIT(SLIST_HEAD *head) SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SLIST_ENTRY NAME) SLIST_INSERT_HEAD(SLIST_HEAD *head, TYPE *elm, SLIST_ENTRY NAME) SLIST_NEXT(TYPE *elm, SLIST_ENTRY NAME) SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME) SLIST_REMOVE(SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME) STAILQ_EMPTY(STAILQ_HEAD *head) STAILQ_ENTRY(TYPE) STAILQ_FIRST(STAILQ_HEAD *head) STAILQ_FOREACH(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME) STAILQ_HEAD(HEADNAME, TYPE) STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head) STAILQ_INIT(STAILQ_HEAD *head) STAILQ_INSERT_AFTER(STAILQ_HEAD *head, TYPE *listelm, TYPE *elm, STAILQ_ENTRY NAME) STAILQ_INSERT_HEAD(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME) STAILQ_INSERT_TAIL(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME) STAILQ_LAST(STAILQ_HEAD *head, TYPE, STAILQ_ENTRY NAME) STAILQ_NEXT(TYPE *elm, STAILQ_ENTRY NAME) STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME) STAILQ_REMOVE(STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME) LIST_EMPTY(LIST_HEAD *head) LIST_ENTRY(TYPE) LIST_FIRST(LIST_HEAD *head) LIST_FOREACH(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME) LIST_HEAD(HEADNAME, TYPE) LIST_HEAD_INITIALIZER(LIST_HEAD head) LIST_INIT(LIST_HEAD *head) LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME) LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME) LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME) LIST_NEXT(TYPE *elm, LIST_ENTRY NAME) LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME) TAILQ_EMPTY(TAILQ_HEAD *head) TAILQ_ENTRY(TYPE) TAILQ_FIRST(TAILQ_HEAD *head) TAILQ_FOREACH(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME) TAILQ_FOREACH_REVERSE(TYPE *var, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY NAME) TAILQ_HEAD(HEADNAME, TYPE) TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head) TAILQ_INIT(TAILQ_HEAD *head) TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME) TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME) TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME) TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME) TAILQ_LAST(TAILQ_HEAD *head, HEADNAME) TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME) TAILQ_PREV(TYPE *elm, HEADNAME, TAILQ_ENTRY NAME) TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME) CIRCLEQ_EMPTY(CIRCLEQ_HEAD *head) CIRCLEQ_ENTRY(TYPE) CIRCLEQ_FIRST(CIRCLEQ_HEAD *head) CIRCLEQ_FOREACH(TYPE *var, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME) CIRCLEQ_FOREACH_REVERSE(TYPE *var, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME) CIRCLEQ_HEAD(HEADNAME, TYPE) CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD head) CIRCLEQ_INIT(CIRCLEQ_HEAD *head) CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_LAST(CIRCLEQ_HEAD *head) CIRCLEQ_NEXT(TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLE_PREV(TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME)

解説
このマクロは、単一リンクリスト、単一リンクテールキュー、リスト、 テールキュー、循環キューという、5 種類のデータ構造を定義してそこで動作します。 5 つのデータ構造はすべて、以下の機能をサポートします。
1.  リストの先頭に新しいエントリを挿入する。
2.  リストに存在する任意の要素の後ろに新しいエントリを挿入する。
3.  リストの先頭からエントリを O(1) 削除する。
4.  リストの任意のエントリを O(n) 削除する。
5.  リストを前から走査する。

単一リンクリストは、5 つのデータ構造の中で最も単純で、上の 5つの機能し かサポートしません。 単一リンクリストは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または LIFO キューの実装に理想的です。

単一リンクテールキューには以下の機能もあります。
1.  リストの末尾にエントリを追加する。
しかし以下に注意してください。
1.  リストの挿入では、リストのヘッドを必ず指定する必要がある。
2.  各ヘッドエントリでは、1 つではなく 2 つのポインタが必要である。
3.  単一リンクリストより、コードサイズは約 15% 大きく、動作は約 20% 遅い。

単一リンクテールキューは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または FIFO キューの実装に理想的です。

二重リンクタイプのすべてのデータ構造 (リスト、テールキュー、循環キュー) には 以下の機能もあります。
1.  リストに存在する任意の要素の前に新しいエントリを挿入する。
2.  リストの任意のエントリを O(1) 削除する。
しかし以下に注意してください。
1.  各要素には、1 つではなく 2 つのポインタが必要である。
2.  単一リンクデータ構造より、コードサイズと実行時間 (削除は除く) が約 2 倍に なる。

リンクリストは、二重リンクデータ構造の中で最も単純で、単一リンクリストの 機能に加えて上の機能しかサポートしません。

テールキューには以下の機能もあります。
1.  リストの末尾にエントリを追加する。
2.  末尾から先頭へと逆に走査する。
しかし以下に注意してください。
1.  リストの挿入と削除では、リストのヘッドを必ず指定する必要がある。
2.  各ヘッドエントリでは、1 つではなく 2 つのポインタが必要である。
3.  単一リンクリストより、コードサイズは約 15% 大きく、処理時間は約 20% 長い。

循環キューには以下の機能もあります。
1.  リストの末尾にエントリを追加する。
2.  末尾から先頭へと逆に走査する。
しかし以下に注意してください。
1.  リストの挿入と削除では、リストのヘッドを必ず指定する必要がある。
2.  各ヘッドエントリでは、1 つではなく 2 つのポインタが必要である。
3.  走査の終了条件がより複雑である。
4.  リストより、コードサイズは約 40% 大きく、処理時間は約 45% 長い。

マクロ定義では、 TYPE はユーザが定義した構造体の名前です。この構造体には、 NAME という名前が付いた、 SLIST_ENTRY, STAILQ_ENTRY, LIST_ENTRY, TAILQ_ENTRY, CIRCLEQ_ENTRY という型のフィールドを含める必要があります。 引数 HEADNAME は マクロ SLIST_HEAD, STAILQ_HEAD, LIST_HEAD, TAILQ_HEAD, CIRCLEQ_HEAD で宣言する必要のある、ユーザが定義した構造体の名前です。 このマクロの使用法の詳細については、以下の使用例を参照してください。

単一リンクリスト
単一リンクリストの最初には、 SLIST_HEAD マクロで定義される構造体が付きます。 この構造体には、リストの先頭の要素を指すポインタが 1 つ含まれます。 要素は、任意の要素の O(n) 削除を犠牲にして、 スペースとポインタ操作のオーバヘッドが最小になるように単一リンクされます。 新しい要素は、既存の要素の後ろ、リストの先頭でリストに追加できます。 SLIST_HEAD 構造体は以下のように宣言されます。

    SLIST_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE はリストにリンクする要素の型です。 リストのヘッドのポインタは、後で以下のように宣言できます。

    struct HEADNAME *headp;

(名前 head と headp は、ユーザが選べます。)

マクロ SLIST_HEAD_INITIALIZER はリストの head を初期化します。

マクロ SLIST_EMPTY はリストに要素がない場合に真になります。

マクロ SLIST_ENTRY はリストの要素を接続する構造体を宣言します。

マクロ SLIST_FIRST はリストの先頭の要素を、リストが空なら NULL を返します。

マクロ SLIST_FOREACH は head で参照されるリストを、各要素を順に var に割り当てて順方向に走査します。

マクロ SLIST_INIT は head が参照するリストを初期化します。

マクロ SLIST_INSERT_HEAD は新しい要素 elm をリストの先頭に挿入します。

マクロ SLIST_INSERT_AFTER は要素 listelm の後ろに新しい要素 elm を挿入します。

マクロ SLIST_NEXT はリストの次の要素を返します。

マクロ SLIST_REMOVE_HEAD はリストの先頭から要素 elm を削除します。 最適な効率を得るために、リストの先頭から要素を削除する場合には 一般的な SLIST_REMOVE マクロの代わりにこのマクロを明示的に使用すべきです。

マクロ SLIST_REMOVE はリストから要素 elm を削除します。

単一リンクリストの使用例

    SLIST_HEAD(slisthead, entry) head =
        SLIST_HEAD_INITIALIZER(head);
    struct slisthead *headp;		/* 単一リンクリストヘッド */
    struct entry {
    	...
    	SLIST_ENTRY(entry) entries;	/* 単一リンクリスト */
    	...
    } *n1, *n2, *n3, *np;
    SLIST_INIT(&head);			/* リストを初期化 */
    n1 = malloc(sizeof(struct entry));	/* 先頭に挿入 */
    SLIST_INSERT_HEAD(&head, n1, entries);
    n2 = malloc(sizeof(struct entry));	/* 後ろに挿入 */
    SLIST_INSERT_AFTER(n1, n2, entries);
    SLIST_REMOVE(&head, n2, entry, entries);/* 削除 */
    free(n2);
    n3 = SLIST_FIRST(&head);
    SLIST_REMOVE_HEAD(&head, entries);	/* 先頭から削除 */
    free(n3);
    					/* 順走査 */
    SLIST_FOREACH(np, &head, entries)
    	np-> ...
    while (!SLIST_EMPTY(&head)) {		/* リストの削除 */
    	n1 = SLIST_FIRST(&head);
    	SLIST_REMOVE_HEAD(&head, entries);
    	free(n1);
    }

単一リンクテールキュー
単一リンクテールキューの最初には、 STAILQ_HEAD マクロで定義される構造体がつきます。 この構造体にはテールキューの先頭の要素を指すポインタと テールキューの末尾の要素を指すポインタの 2 つが含まれます。 要素は、任意の要素の O(n) 削除を犠牲にして、 スペースとポインタ操作のオーバヘッドが最小になるように単一リンクされます。 新しい要素は、既存の要素の後ろ、テールキューの先頭、テールキューの末尾で テールキューに追加できます。 STAILQ_HEAD 構造体は以下のように宣言されます。

    STAILQ_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE はテールキューにリンクする要素の型です。 テールキューのヘッドのポインタは、後で以下のように宣言できます。

    struct HEADNAME *headp;

(名前 head と headp は、ユーザが選べます。)

マクロ STAILQ_HEAD_INITIALIZER はテールキューの head を初期化します。

マクロ STAILQ_EMPTY はテールキューに要素がない場合に真になります。

マクロ STAILQ_ENTRY はテールキューの要素を接続する構造体を宣言します。

マクロ STAILQ_FIRST はテールキューの先頭の要素を、テールキューが空なら NULL を返します。

マクロ STAILQ_FOREACH は head で参照されるテールキューを、各要素を順に var に割り当てて順方向に走査します。

マクロ STAILQ_INIT は head が参照するテールキューを初期化します。

マクロ STAILQ_INSERT_HEAD は新しい要素 elm をテールキューの先頭に挿入します。

マクロ STAILQ_INSERT_TAIL は新しい要素 elm をテールキューの末尾に挿入します。

マクロ STAILQ_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。

マクロ STAILQ_LAST はテールキューの末尾の要素を返します。 テールキューが空なら、戻り値は未定義です。

マクロ STAILQ_NEXT はテールキューの次の要素を、この要素が末尾なら NULL を返します。

マクロ STAILQ_REMOVE_HEAD はテールキューの先頭から要素 を削除します。 最適な効率を得るために、テールキューの先頭から要素を削除する場合には 一般的な STAILQ_REMOVE マクロよりもこのマクロを明示的に使用すべきです。

マクロ STAILQ_REMOVE はテールキューから要素 elm を削除します。

単一リンクテールキューの使用例

    STAILQ_HEAD(stailhead, entry) head =
        STAILQ_HEAD_INITIALIZER(head);
    struct stailhead *headp;		/* 単一リンクテールキューヘッド */
    struct entry {
    	...
    	STAILQ_ENTRY(entry) entries;	/* テールキュー */
    	...
    } *n1, *n2, *n3, *np;
    STAILQ_INIT(&head);			/* キューを初期化 */
    n1 = malloc(sizeof(struct entry));	/* 先頭に挿入 */
    STAILQ_INSERT_HEAD(&head, n1, entries);
    n1 = malloc(sizeof(struct entry));	/* 末尾に挿入 */
    STAILQ_INSERT_TAIL(&head, n1, entries);
    n2 = malloc(sizeof(struct entry));	/* 後ろに挿入 */
    STAILQ_INSERT_AFTER(&head, n1, n2, entries);
    					/* 削除 */
    STAILQ_REMOVE(&head, n2, entry, entries);
    free(n2);
    					/* 先頭から削除 */
    n3 = STAILQ_FIRST(&head);
    STAILQ_REMOVE_HEAD(&head, entries);
    free(n3);
    					/* 順走査 */
    STAILQ_FOREACH(np, &head, entries)
    	np-> ...
    					/* テールキューの削除 */
    while (!STAILQ_EMPTY(&head)) {
    	n1 = STAILQ_FIRST(&head);
    	STAILQ_REMOVE_HEAD(&head, entries);
    	free(n1);
    }
    					/* テールキューの高速な削除 */
    n1 = STAILQ_FIRST(&head);
    while (n1 != NULL) {
    	n2 = STAILQ_NEXT(n1, entries);
    	free(n1);
    	n1 = n2;
    }
    STAILQ_INIT(&head);

リスト
リストの最初には、 LIST_HEAD マクロで定義される構造体が付きます。 この構造体には、リストの先頭の要素を指すポインタが 1 つ含まれます。 要素は二重にリンクされているので、リストを走査せずに任意の要素を削除できます。 新しい要素は、既存の要素の前、既存の要素の後、リストの先頭で リストに追加できます。 LIST_HEAD 構造体は、以下のように宣言されます。

    LIST_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE はリストにリンクする要素の型です。 リストのヘッドのポインタは、後で以下のように宣言できます。

    struct HEADNAME *headp;

(名前 head と headp は、ユーザが選べます。)

マクロ LIST_HEAD_INITIALIZER はリストの head を初期化します。

マクロ LIST_EMPTY はリストに要素がない場合に真になります。

マクロ LIST_ENTRY はリストの要素を接続する構造体を宣言します。

マクロ LIST_FIRST はリストの最初の要素を、リストが空なら NULL を返します。

マクロ LIST_FOREACH は head で参照されるリストを、各要素を順に var に割り当てて順方向に走査します。

マクロ LIST_INIT は head が参照するリストを初期化します。

マクロ LIST_INSERT_HEAD は新しい要素 elm をリストの先頭に挿入します。

マクロ LIST_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。

マクロ LIST_INSERT_BEFORE は新しい要素 elm を要素 listelm の前に挿入します。

マクロ LIST_NEXT はリストの次の要素を、この要素が末尾なら NULL を返します。

マクロ LIST_REMOVE は要素 elm をリストから削除します。

リストの使用例

    LIST_HEAD(listhead, entry) head =
        LIST_HEAD_INITIALIZER(head);
    struct listhead *headp;			/* リストヘッド */
    struct entry {
    	...
    	LIST_ENTRY(entry) entries;	/* リスト */
    	...
    } *n1, *n2, *n3, *np;
    LIST_INIT(&head);			/* リストを初期化 */
    n1 = malloc(sizeof(struct entry));	/* 先頭に挿入 */
    LIST_INSERT_HEAD(&head, n1, entries);
    n2 = malloc(sizeof(struct entry));	/* 後ろに挿入 */
    LIST_INSERT_AFTER(n1, n2, entries);
    n3 = malloc(sizeof(struct entry));	/* 前に挿入 */
    LIST_INSERT_BEFORE(n2, n3, entries);
    LIST_REMOVE(n2, entries);		/* 削除 */
    free(n2);
    					/* 順走査 */
    LIST_FOREACH(np, &head, entries)
    	np-> ...
    while (!LIST_EMPTY(&head)) {		/* リストの削除 */
    	n1 = LIST_FIRST(&head);
    	LIST_REMOVE(n1, entries);
    	free(n1);
    }
    n1 = LIST_FIRST(&head);			/* リストの高速な削除 */
    while (n1 != NULL) {
    	n2 = LIST_NEXT(n1, entries);
    	free(n1);
    	n1 = n2;
    }
    LIST_INIT(&head);

テールキュー
テールキューの最初には、 TAILQ_HEAD マクロで定義される構造体が付きます。 この構造体には、テールキューの最初の要素を指すポインタと テールキューの先頭の要素を指すポインタの 2 つが含まれます。 要素は二重にリンクされているので、テールキューを走査せずに 任意の要素を削除できます。 新しい要素は、既存の要素の前、既存の要素の後、テールキューの先頭、 テールキューの末尾でテールキューに追加できます。 TAILQ_HEAD 構造体は、以下のように宣言されています。

    TAILQ_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE はテールキューにリンクする要素の型です。 テールキューのヘッドのポインタは、後で以下のように宣言されます。

    struct HEADNAME *headp;

(名前 head と headp は、ユーザが選べます。)

マクロ TAILQ_HEAD_INITIALIZER はテールキューの head を初期化します。

マクロ TAILQ_EMPTY はテールキューに要素がない場合に真になります。

マクロ TAILQ_ENTRY はテールキューの要素を接続する構造体を宣言します。

マクロ TAILQ_FIRST はテールキューの最初の要素を、テールキューが空なら NULL を返します。

マクロ TAILQ_FOREACH は head で参照されるテールキューを、各要素を順に var に割り当てて順方向に走査します。

マクロ TAILQ_FOREACH_REVERSE は head で参照されるテールキューを、各要素を順に var に割り当てて逆方向に走査します。

マクロ TAILQ_INIT は head が参照するテールキューを初期化します。

マクロ TAILQ_INSERT_HEAD は新しい要素 elm をテールキューの先頭に挿入します。

マクロ TAILQ_INSERT_TAIL は新しい要素 elm をテールキューの末尾に挿入します。

マクロ TAILQ_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。

マクロ TAILQ_INSERT_BEFORE は新しい要素 elm を要素 listelm の前に挿入します。

マクロ TAILQ_LAST はテールキューの末尾の要素を返します。 テールキューが空の場合、戻り値は未定義です。

マクロ TAILQ_NEXT はテールキューの次の要素を、その要素が末尾の場合は NULL を返します。

マクロ TAILQ_PREV はテールキューの前の要素を、その要素が先頭の場合は NULL を返します。

マクロ TAILQ_REMOVE は要素 elm をテールキューから削除します。

テールキューの使用例

    TAILQ_HEAD(tailhead, entry) head =
        TAILQ_HEAD_INITIALIZER(head);
    struct tailhead *headp;			/* テールキューヘッド */
    struct entry {
    	...
    	TAILQ_ENTRY(entry) entries;	/* テールキュー */
    	...
    } *n1, *n2, *n3, *np;
    TAILQ_INIT(&head);			/* キューを初期化 */
    n1 = malloc(sizeof(struct entry));	/* 先頭に挿入 */
    TAILQ_INSERT_HEAD(&head, n1, entries);
    n1 = malloc(sizeof(struct entry));	/* 末尾に挿入 */
    TAILQ_INSERT_TAIL(&head, n1, entries);
    n2 = malloc(sizeof(struct entry));	/* 後ろに挿入 */
    TAILQ_INSERT_AFTER(&head, n1, n2, entries);
    n3 = malloc(sizeof(struct entry));	/* 前に挿入 */
    TAILQ_INSERT_BEFORE(n2, n3, entries);
    TAILQ_REMOVE(&head, n2, entries);	/* 削除 */
    free(n2);
    					/* 順走査 */
    TAILQ_FOREACH(np, &head, entries)
    	np-> ...
    					/* 逆走査 */
    TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
    	np-> ...
    					/* テールキューの削除 */
    while (!TAILQ_EMPTY(&head)) {
    	n1 = TAILQ_FIRST(&head);
    	TAILQ_REMOVE(&head, n1, entries);
    	free(n1);
    }
    					/* テールキューの高速な削除 */
    n1 = TAILQ_FIRST(&head);
    while (n1 != NULL) {
    	n2 = TAILQ_NEXT(n1, entries);
    	free(n1);
    	n1 = n2;
    }
    TAILQ_INIT(&head);

循環キュー
循環キューの最初には、 CIRCLEQ_HEAD マクロで定義される構造体が付きます。 この構造体には、循環キューの先頭の要素を指すポインタと 循環キューの末尾の要素を指すポインタの 2 つが含まれます。 要素は二重にリンクされているので、キューを走査せずに 任意の要素を削除できます。 新しい要素は、既存の要素の前、既存の要素の後ろ、循環キューの先頭、 循環キューの末尾で循環キューに追加できます。 CIRCLEQ_HEAD 構造体は以下のように宣言されます。

    CIRCLEQ_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義する構造体の名前で、 TYPE は循環キューにリンクする要素の型です。 循環キューのヘッドのポインタは、後で以下のように宣言できます。

    struct HEADNAME *headp;

(名前 head と headp は、ユーザが選べます。)

マクロ CIRCLEQ_HEAD_INITIALIZER は循環キューの head を初期化します。

マクロ CIRCLEQ_EMPTY は循環キューに要素がない場合に真になります。

マクロ CIRCLEQ_ENTRY は循環キューの要素を接続する構造体を宣言します。

マクロ CIRCLEQ_FIRST は循環キューの先頭の要素を返します。

マクロ CICRLEQ_FOREACH は head で参照される循環キューを、各要素を順に var に割り当てて順方向に走査します。

マクロ CICRLEQ_FOREACH_REVERSE は head で参照される循環キューを、各要素を順に var に割り当てて逆方向に走査します。

マクロ CIRCLEQ_INIT は head が参照する循環キューを初期化します。

マクロ CIRCLEQ_INSERT_HEAD は新しい要素 elm を循環キューの先頭に挿入します。

マクロ CIRCLEQ_INSERT_TAIL は新しい要素 elm を循環キューの末尾に挿入します。

マクロ CIRCLEQ_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。

マクロ CIRCLEQ_INSERT_BEFORE は新しい要素 elm を要素 listelm の前に挿入します。

マクロ CIRCLEQ_LAST は循環キューの末尾の要素を返します。

マクロ CIRCLEQ_NEXT は循環キューの次の要素を返します。

マクロ CIRCLEQ_PREV は循環キューの前の要素を返します。

マクロ CIRCLEQ_REMOVE は要素 elm を循環キューから削除します。

循環キューの使用例

    CIRCLEQ_HEAD(circlehead, entry) head =
        CIRCLEQ_HEAD_INITIALIZER(head);
    struct circleq *headp;			/* 循環キューヘッド */
    struct entry {
    	...
    	CIRCLEQ_ENTRY(entry) entries;	/* 循環キュー */
    	...
    } *n1, *n2, *np;
    CIRCLEQ_INIT(&head);			/* 循環キューを初期化 */
    n1 = malloc(sizeof(struct entry));	/* 先頭に挿入 */
    CIRCLEQ_INSERT_HEAD(&head, n1, entries);
    n1 = malloc(sizeof(struct entry));	/* 末尾に挿入 */
    CIRCLEQ_INSERT_TAIL(&head, n1, entries);
    n2 = malloc(sizeof(struct entry));	/* 後ろに挿入 */
    CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
    n2 = malloc(sizeof(struct entry));	/* 前に挿入 */
    CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
    CIRCLEQ_REMOVE(&head, n1, entries);	/* 削除 */
    free(n1);
    					/* 順走査 */
    CIRCLEQ_FOREACH(np, &head, entries)
    	np-> ...
    					/* 逆走査 */
    CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
    	np-> ...
    					/* 循環キューの削除 */
    while (CIRCLEQ_FIRST(&head) != (void *)&head) {
    	n1 = CIRCLEQ_HEAD(&head);
    	CIRCLEQ_REMOVE(&head, n1, entries);
    	free(n1);
    }
    					/* 循環キューの高速な削除 */
    n1 = CIRCLEQ_FIRST(&head);
    while (n1 != (void *)&head) {
    	n2 = CIRCLEQ_NEXT(n1, entries);
    	free(n1);
    	n1 = n2;
    }
    CIRCLEQ_INIT(&head);

歴史
queue 関数は 4.4BSD ではじめて登場しました。