.\" Copyright (c) 1993
.\"     The Regents of the University of California.  All rights reserved.
.\"
.\" %%%LICENSE_START(BSD_4_CLAUSE_UCB)
.\" 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.
.\" 3. All advertising materials mentioning features or use of this software
.\"    must display the following acknowledgement:
.\"     This product includes software developed by the University of
.\"     California, Berkeley and its contributors.
.\" 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.
.\" %%%LICENSE_END
.\"
.\"     @(#)queue.3     8.2 (Berkeley) 1/24/94
.\"
.\" hch, 2002-03-25
.\" 2007-12-08, mtk, Converted from mdoc to man macros
.\"
.\"*******************************************************************
.\"
.\" This file was generated with po4a. Translate the source file.
.\"
.\"*******************************************************************
.\"
.\" Japanese Version Copyright (c) 2004 Yuichi SATO
.\"         all rights reserved.
.\" Translated Thu Sep  2 04:41:11 JST 2004
.\"         by Yuichi SATO <ysato444@yahoo.co.jp>
.\"
.TH QUEUE 3 2007\-12\-28 Linux "Linux Programmer's Manual"
.SH 名前
LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_HEAD,
LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_INIT, TAILQ_INSERT_AFTER,
TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, CIRCLEQ_ENTRY,
CIRCLEQ_HEAD, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE,
CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLEQ_REMOVE \- リスト・テール (tail)
キュー・循環キューの実装
.SH 書式
.nf
\fB#include <sys/queue.h>\fP

\fBLIST_ENTRY(\fP\fITYPE\fP\fB);\fP
\fBLIST_HEAD(\fP\fIHEADNAME\fP\fB, \fP\fITYPE\fP\fB);\fP
\fBLIST_INIT(LIST_HEAD *\fP\fIhead\fP\fB);\fP
\fBLIST_INSERT_AFTER(LIST_ENTRY *\fP\fIlistelm\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, LIST_ENTRY \fP\fINAME\fP\fB);\fP
\fBLIST_INSERT_HEAD(LIST_HEAD *\fP\fIhead\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, LIST_ENTRY \fP\fINAME\fP\fB);\fP
\fBLIST_REMOVE(TYPE *\fP\fIelm\fP\fB, LIST_ENTRY \fP\fINAME\fP\fB);\fP

\fBTAILQ_ENTRY(\fP\fITYPE\fP\fB);\fP
\fBTAILQ_HEAD(\fP\fIHEADNAME\fP\fB, \fP\fITYPE\fP\fB);\fP
\fBTAILQ_INIT(TAILQ_HEAD *\fP\fIhead\fP\fB);\fP
\fBTAILQ_INSERT_AFTER(TAILQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIlistelm\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
\fBTAILQ_INSERT_HEAD(TAILQ_HEAD *\fP\fIhead\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
\fBTAILQ_INSERT_TAIL(TAILQ_HEAD *\fP\fIhead\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
\fBTAILQ_REMOVE(TAILQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP

\fBCIRCLEQ_ENTRY(\fP\fITYPE\fP\fB);\fP
\fBCIRCLEQ_HEAD(\fP\fIHEADNAME\fP\fB, \fP\fITYPE\fP\fB);\fP
\fBCIRCLEQ_INIT(CIRCLEQ_HEAD *\fP\fIhead\fP\fB);\fP
\fBCIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIlistelm\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
\fBCIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIlistelm\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
\fBCIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
\fBCIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
\fBCIRCLEQ_REMOVE(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, \fP
\fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
.fi
.SH 説明
これらのマクロは、次の 3 つのデータ構造を定義して操作する: リスト・テールキュー・循環キュー。 3
つのデータ構造すべてにおいて以下の機能がサポートされている:
.sp
.RS 4
.PD 0
.IP * 4
新たなエントリーをリストの先頭に挿入する。
.IP *
新たなエントリーをリストのどの要素よりも後に挿入する。
.IP *
リストの任意のエントリーを削除する。
.IP *
リストを順方向に辿る。
.PD
.RE
.PP
リストは 3 つのデータ構造の中で最も単純であり、 上記の機能のみをサポートする。

テールキューは以下の機能を追加する:
.RS 4
.IP * 4
エントリーをリストの最後に追加できる。
.RE
.PP
ただし:
.sp
.RS 4
.PD 0
.IP 1. 4
全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
.IP 2.
各先頭エントリーは 1 つではなく 2 つのポインターを必要とする。
.IP 3.
リストと比べて、コードサイズは 15% 大きくなり、操作は 20% 遅くなる。
.PD
.RE
.PP
循環キューは以下の機能を追加する:
.sp
.RS 4
.PD 0
.IP * 4
エントリーをリストの最後に追加できる。
.IP *
エントリーを他のエントリーの前に追加できる。
.IP *
逆方向に末尾から先頭へ辿ることができる。
.PD
.RE
.PP
ただし:
.sp
.RS 4
.PD 0
.IP 1. 4
全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
.IP 2.
各先頭エントリーは 1 つではなく 2 つのポインターを必要とする。
.IP 3.
辿る際の終了条件がより複雑である。
.IP 4.
リストと比べて、コードサイズは 40% 大きくなり、操作は 45% 遅くなる。
.PD
.RE
.PP
マクロ定義において \fITYPE\fP はユーザー定義構造体の名前であり、 \fBLIST_ENTRY\fP, \fBTAILQ_ENTRY\fP,
\fBCIRCLEQ_ENTRY\fP の何れか型のフィールドと 指定された \fINAME\fP を含まなければならない。 引き数 \fIHEADNAME\fP
はユーザー定義構造体の名前であり、 マクロ \fBLIST_HEAD\fP, \fBTAILQ_HEAD\fP, \fBCIRCLEQ_HEAD\fP
を用いて宣言されなければならない。 これらのマクロがどのように使われるかについての更なる説明は、 以下の例を参照すること。
.SS リスト
リストの先頭には、 \fBLIST_HEAD\fP マクロで定義される構造体が置かれる。 この構造体はリストの最初の要素へのポインターを 1 つ含む。 要素は
2 重にリンクされており、 任意の要素はリストを辿らずに削除できる。 新しい要素は既存の要素の後またはリストの先頭に追加できる。
\fBLIST_HEAD\fP 構造体は以下のように宣言されている:
.in +4n
.nf

LIST_HEAD(HEADNAME, TYPE) head;
.fi
.in
.PP
ここで \fIHEADNAME\fP は定義される構造体の名前であり、 \fITYPE\fP はリンク内でリンクされる要素の型である。
リストの先頭へのポインターは、その後で次のように宣言される:
.in +4n
.nf

struct HEADNAME *headp;
.fi
.in
.PP
(名前 \fIhead\fP と \fIheadp\fP はユーザーが選択できる。)
.PP
マクロ \fBLIST_ENTRY\fP はリストの要素を接続する構造体を宣言する。
.PP
マクロ \fBLIST_INIT\fP は \fIhead\fP で参照されるリストを初期化する。
.PP
マクロ \fBLIST_INSERT_HEAD\fP は新たな要素 \fIelm\fP をリストの先頭に挿入する。
.PP
マクロ \fBLIST_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の後に挿入する。
.PP
マクロ \fBLIST_REMOVE\fP は要素 \fIelm\fP をリストから削除する。
.SS リストの例
.nf
LIST_HEAD(listhead, entry) head;
struct listhead *headp;                 /* リストの先頭。*/
struct entry {
    ...
    LIST_ENTRY(entry) entries;          /* リスト。 */
    ...
} *n1, *n2, *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);
                                        /* 順方向に辿る。*/
for (np = head.lh_first; np != NULL; np = np\->entries.le_next)
    np\-> ...

.\" FIXME . http://sourceware.org/bugzilla/show_bug.cgi?id=1506
while (head.lh_first != NULL)           /* 削除する。*/
    LIST_REMOVE(head.lh_first, entries);
.fi
.SS テールキュー
テールキューの先頭には \fBTAILQ_HEAD\fP マクロで定義される構造体が置かれる。 この構造体は 1 組のポインターを含んでいる。 1
つはテールキューの最初の要素へのポインターであり、 もう 1 つはテールキューの最後の要素へのポインターである。 要素は 2 重にリンクされており、
任意の要素はテールキューを辿らずに削除できる。 新しい要素は既存の要素の後またはテールキューの先頭または末尾に追加できる。 \fBTAILQ_HEAD\fP
構造体は以下のように定義されている:
.in +4n
.nf

TAILQ_HEAD(HEADNAME, TYPE) head;
.fi
.in
.PP
ここで \fIHEADNAME\fP は定義される構造体の名前であり、 \fITYPE\fP はテールキュー内でリンクされる要素の型である。
テールキューの先頭へのポインターは、その後で次のように宣言される:
.in +4n
.nf

struct HEADNAME *headp;
.fi
.in
.PP
(名前 \fIhead\fP と \fIheadp\fP はユーザーが選択できる。)
.PP
マクロ \fBTAILQ_ENTRY\fP はテールキューの要素を接続する構造体を宣言する。
.PP
マクロ \fBTAILQ_INIT\fP は \fIhead\fP で参照されるテールキューを初期化する。
.PP
マクロ \fBTAILQ_INSERT_HEAD\fP は新たな要素 \fIelm\fP をテールキューの先頭に挿入する。
.PP
マクロ \fBTAILQ_INSERT_TAIL\fP は新たな要素 \fIelm\fP をテールキューの末尾に挿入する。
.PP
マクロ \fBTAILQ_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の後に挿入する。
.PP
マクロ \fBTAILQ_REMOVE\fP は要素 \fIelm\fP をテールキューから削除する。
.SS テールキューの例
.nf
TAILQ_HEAD(tailhead, entry) head;
struct tailhead *headp;                 /* テールキューの先頭。*/
struct entry {
    ...
    TAILQ_ENTRY(entry) entries;         /* テールキュー。*/
    ...
} *n1, *n2, *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);
                                        /* 順方向に辿る。*/
for (np = head.tqh_first; np != NULL; np = np\->entries.tqe_next)
    np\-> ...
                                        /* 削除する。*/
while (head.tqh_first != NULL)
    TAILQ_REMOVE(&head, head.tqh_first, entries);
.fi
.SS 循環キュー
循環キューの先頭には \fBCIRCLEQ_HEAD\fP マクロで定義される構造体が置かれる。 この構造体は 1 組のポインターを含んでいる。 1
つは循環キューの最初の要素へのポインターであり、 もう 1 つは循環キューの最後の要素へのポインターである。 要素は 2 重にリンクされており、
任意の要素はキューを辿らずに削除できる。 新しい要素は、既存の要素の後または前、またはキューの先頭または末尾に追加できる。 A
\fBCIRCLEQ_HEAD\fP 構造体は以下のように定義されている:
.in +4n
.nf

CIRCLEQ_HEAD(HEADNAME, TYPE) head;
.fi
.in
.PP
ここで \fIHEADNAME\fP は定義される構造体の名前であり、 \fITYPE\fP は循環キュー内でリンクされる要素の型である。
循環キューの先頭へのポインターは、その後で次のように宣言される:
.in +4n
.nf

struct HEADNAME *headp;
.fi
.in
.PP
(名前 \fIhead\fP と \fIheadp\fP はユーザーが選択できる。)
.PP
マクロ \fBCIRCLEQ_ENTRY\fP は循環キューの要素を接続する構造体を宣言する。
.PP
マクロ \fBCIRCLEQ_INIT\fP は \fIhead\fP で参照される循環キューを初期化する。
.PP
マクロ \fBCIRCLEQ_INSERT_HEAD\fP は新たな要素 \fIelm\fP を循環キューの先頭に挿入する。
.PP
マクロ \fBCIRCLEQ_INSERT_TAIL\fP は新たな要素 \fIelm\fP を循環キューの末尾に挿入する。
.PP
マクロ \fBCIRCLEQ_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の後に挿入する。
.PP
マクロ \fBCIRCLEQ_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の前に挿入する。
.PP
マクロ \fBCIRCLEQ_REMOVE\fP は要素 \fIelm\fP を循環キューから削除する。
.SS 循環キューの例
.nf
CIRCLEQ_HEAD(circleq, entry) 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);
                                        /* 順方向に辿る。*/
for (np = head.cqh_first; np != (void *)&head; np = np\->entries.cqe_next)
    np\-> ...
                                        /* 逆方向に辿る。*/
for (np = head.cqh_last; np != (void *)&head; np = np\->entries.cqe_prev)
    np\-> ...
                                        /* 削除する。*/
while (head.cqh_first != (void *)&head)
    CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
.fi
.SH 準拠
POSIX.1\-2001 にはない。 BSD 系に存在する。 queue 関数は 4.4BSD で初めて登場した。
.SH この文書について
この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.79 の一部
である。プロジェクトの説明とバグ報告に関する情報は
http://www.kernel.org/doc/man\-pages/ に書かれている。