2 .\" The Regents of the University of California. All rights reserved.
4 .\" %%%LICENSE_START(BSD_4_CLAUSE_UCB)
5 .\" Redistribution and use in source and binary forms, with or without
6 .\" modification, are permitted provided that the following conditions
8 .\" 1. Redistributions of source code must retain the above copyright
9 .\" notice, this list of conditions and the following disclaimer.
10 .\" 2. Redistributions in binary form must reproduce the above copyright
11 .\" notice, this list of conditions and the following disclaimer in the
12 .\" documentation and/or other materials provided with the distribution.
13 .\" 3. All advertising materials mentioning features or use of this software
14 .\" must display the following acknowledgement:
15 .\" This product includes software developed by the University of
16 .\" California, Berkeley and its contributors.
17 .\" 4. Neither the name of the University nor the names of its contributors
18 .\" may be used to endorse or promote products derived from this software
19 .\" without specific prior written permission.
21 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 .\" @(#)queue.3 8.2 (Berkeley) 1/24/94
37 .\" 2007-12-08, mtk, Converted from mdoc to man macros
39 .\"*******************************************************************
41 .\" This file was generated with po4a. Translate the source file.
43 .\"*******************************************************************
45 .\" Japanese Version Copyright (c) 2004 Yuichi SATO
46 .\" all rights reserved.
47 .\" Translated Thu Sep 2 04:41:11 JST 2004
48 .\" by Yuichi SATO <ysato444@yahoo.co.jp>
50 .TH QUEUE 3 2007\-12\-28 Linux "Linux Programmer's Manual"
52 LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_HEAD,
53 LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_INIT, TAILQ_INSERT_AFTER,
54 TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, CIRCLEQ_ENTRY,
55 CIRCLEQ_HEAD, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE,
56 CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLEQ_REMOVE \- リスト・テール (tail)
60 \fB#include <sys/queue.h>\fP
62 \fBLIST_ENTRY(\fP\fITYPE\fP\fB);\fP
63 \fBLIST_HEAD(\fP\fIHEADNAME\fP\fB, \fP\fITYPE\fP\fB);\fP
64 \fBLIST_INIT(LIST_HEAD *\fP\fIhead\fP\fB);\fP
65 \fBLIST_INSERT_AFTER(LIST_ENTRY *\fP\fIlistelm\fP\fB, \fP
66 \fB TYPE *\fP\fIelm\fP\fB, LIST_ENTRY \fP\fINAME\fP\fB);\fP
67 \fBLIST_INSERT_HEAD(LIST_HEAD *\fP\fIhead\fP\fB, \fP
68 \fB TYPE *\fP\fIelm\fP\fB, LIST_ENTRY \fP\fINAME\fP\fB);\fP
69 \fBLIST_REMOVE(TYPE *\fP\fIelm\fP\fB, LIST_ENTRY \fP\fINAME\fP\fB);\fP
71 \fBTAILQ_ENTRY(\fP\fITYPE\fP\fB);\fP
72 \fBTAILQ_HEAD(\fP\fIHEADNAME\fP\fB, \fP\fITYPE\fP\fB);\fP
73 \fBTAILQ_INIT(TAILQ_HEAD *\fP\fIhead\fP\fB);\fP
74 \fBTAILQ_INSERT_AFTER(TAILQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIlistelm\fP\fB, \fP
75 \fB TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
76 \fBTAILQ_INSERT_HEAD(TAILQ_HEAD *\fP\fIhead\fP\fB, \fP
77 \fB TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
78 \fBTAILQ_INSERT_TAIL(TAILQ_HEAD *\fP\fIhead\fP\fB, \fP
79 \fB TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
80 \fBTAILQ_REMOVE(TAILQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
82 \fBCIRCLEQ_ENTRY(\fP\fITYPE\fP\fB);\fP
83 \fBCIRCLEQ_HEAD(\fP\fIHEADNAME\fP\fB, \fP\fITYPE\fP\fB);\fP
84 \fBCIRCLEQ_INIT(CIRCLEQ_HEAD *\fP\fIhead\fP\fB);\fP
85 \fBCIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIlistelm\fP\fB, \fP
86 \fB TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
87 \fBCIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIlistelm\fP\fB, \fP
88 \fB TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
89 \fBCIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, \fP
90 \fB TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
91 \fBCIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, \fP
92 \fB TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
93 \fBCIRCLEQ_REMOVE(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, \fP
94 \fB TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
97 これらのマクロは、次の 3 つのデータ構造を定義して操作する: リスト・テールキュー・循環キュー。 3
98 つのデータ構造すべてにおいて以下の機能がサポートされている:
105 新たなエントリをリストのどの要素よりも後に挿入する。
113 リストは 3 つのデータ構造の中で最も単純であり、 上記の機能のみをサポートする。
126 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
128 各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
130 リストと比べて、コードサイズは 15% 大きくなり、操作は 20% 遅くなる。
152 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
154 各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
158 リストと比べて、コードサイズは 40% 大きくなり、操作は 45% 遅くなる。
162 マクロ定義において \fITYPE\fP はユーザ定義構造体の名前であり、 \fBLIST_ENTRY\fP, \fBTAILQ_ENTRY\fP,
163 \fBCIRCLEQ_ENTRY\fP の何れか型のフィールドと 指定された \fINAME\fP を含まなければならない。 引き数 \fIHEADNAME\fP
164 はユーザ定義構造体の名前であり、 マクロ \fBLIST_HEAD\fP, \fBTAILQ_HEAD\fP, \fBCIRCLEQ_HEAD\fP
165 を用いて宣言されなければならない。 これらのマクロがどのように使われるかについての更なる説明は、 以下の例を参照すること。
167 リストの先頭には、 \fBLIST_HEAD\fP マクロで定義される構造体が置かれる。 この構造体はリストの最初の要素へのポインタを 1 つ含む。 要素は
168 2 重にリンクされており、 任意の要素はリストを辿らずに削除できる。 新しい要素は既存の要素の後またはリストの先頭に追加できる。
169 \fBLIST_HEAD\fP 構造体は以下のように宣言されている:
173 LIST_HEAD(HEADNAME, TYPE) head;
177 ここで \fIHEADNAME\fP は定義される構造体の名前であり、 \fITYPE\fP はリンク内でリンクされる要素の型である。
178 リストの先頭へのポインタは、その後で次のように宣言される:
182 struct HEADNAME *headp;
186 (名前 \fIhead\fP と \fIheadp\fP はユーザが選択できる。)
188 マクロ \fBLIST_ENTRY\fP はリストの要素を接続する構造体を宣言する。
190 マクロ \fBLIST_INIT\fP は \fIhead\fP で参照されるリストを初期化する。
192 マクロ \fBLIST_INSERT_HEAD\fP は新たな要素 \fIelm\fP をリストの先頭に挿入する。
194 マクロ \fBLIST_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の後に挿入する。
196 マクロ \fBLIST_REMOVE\fP は要素 \fIelm\fP をリストから削除する。
199 LIST_HEAD(listhead, entry) head;
200 struct listhead *headp; /* リストの先頭。*/
203 LIST_ENTRY(entry) entries; /* リスト。 */
207 LIST_INIT(&head); /* リストを初期化する。*/
209 n1 = malloc(sizeof(struct entry)); /* 先頭に挿入する。*/
210 LIST_INSERT_HEAD(&head, n1, entries);
212 n2 = malloc(sizeof(struct entry)); /* 後ろに挿入する。*/
213 LIST_INSERT_AFTER(n1, n2, entries);
215 for (np = head.lh_first; np != NULL; np = np\->entries.le_next)
218 .\" FIXME http://sourceware.org/bugzilla/show_bug.cgi?id=1506
219 while (head.lh_first != NULL) /* 削除する。*/
220 LIST_REMOVE(head.lh_first, entries);
223 テールキューの先頭には \fBTAILQ_HEAD\fP マクロで定義される構造体が置かれる。 この構造体は 1 組のポインタを含んでいる。 1
224 つはテールキューの最初の要素へのポインタであり、 もう 1 つはテールキューの最後の要素へのポインタである。 要素は 2 重にリンクされており、
225 任意の要素はテールキューを辿らずに削除できる。 新しい要素は既存の要素の後またはテールキューの先頭または末尾に追加できる。 \fBTAILQ_HEAD\fP
230 TAILQ_HEAD(HEADNAME, TYPE) head;
234 ここで \fIHEADNAME\fP は定義される構造体の名前であり、 \fITYPE\fP はテールキュー内でリンクされる要素の型である。
235 テールキューの先頭へのポインタは、その後で次のように宣言される:
239 struct HEADNAME *headp;
243 (名前 \fIhead\fP と \fIheadp\fP はユーザが選択できる。)
245 マクロ \fBTAILQ_ENTRY\fP はテールキューの要素を接続する構造体を宣言する。
247 マクロ \fBTAILQ_INIT\fP は \fIhead\fP で参照されるテールキューを初期化する。
249 マクロ \fBTAILQ_INSERT_HEAD\fP は新たな要素 \fIelm\fP をテールキューの先頭に挿入する。
251 マクロ \fBTAILQ_INSERT_TAIL\fP は新たな要素 \fIelm\fP をテールキューの末尾に挿入する。
253 マクロ \fBTAILQ_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の後に挿入する。
255 マクロ \fBTAILQ_REMOVE\fP は要素 \fIelm\fP をテールキューから削除する。
258 TAILQ_HEAD(tailhead, entry) head;
259 struct tailhead *headp; /* テールキューの先頭。*/
262 TAILQ_ENTRY(entry) entries; /* テールキュー。*/
266 TAILQ_INIT(&head); /* キューを初期化する。*/
268 n1 = malloc(sizeof(struct entry)); /* 先頭に挿入する。*/
269 TAILQ_INSERT_HEAD(&head, n1, entries);
271 n1 = malloc(sizeof(struct entry)); /* 末尾に挿入する。*/
272 TAILQ_INSERT_TAIL(&head, n1, entries);
274 n2 = malloc(sizeof(struct entry)); /* 後ろに挿入する。*/
275 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
277 for (np = head.tqh_first; np != NULL; np = np\->entries.tqe_next)
280 while (head.tqh_first != NULL)
281 TAILQ_REMOVE(&head, head.tqh_first, entries);
284 循環キューの先頭には \fBCIRCLEQ_HEAD\fP マクロで定義される構造体が置かれる。 この構造体は 1 組のポインタを含んでいる。 1
285 つは循環キューの最初の要素へのポインタであり、 もう 1 つは循環キューの最後の要素へのポインタである。 要素は 2 重にリンクされており、
286 任意の要素はキューを辿らずに削除できる。 新しい要素は、既存の要素の後または前、またはキューの先頭または末尾に追加できる。 A
287 \fBCIRCLEQ_HEAD\fP 構造体は以下のように定義されている:
291 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
295 ここで \fIHEADNAME\fP は定義される構造体の名前であり、 \fITYPE\fP は循環キュー内でリンクされる要素の型である。
296 循環キューの先頭へのポインタは、その後で次のように宣言される:
300 struct HEADNAME *headp;
304 (名前 \fIhead\fP と \fIheadp\fP はユーザが選択できる。)
306 マクロ \fBCIRCLEQ_ENTRY\fP は循環キューの要素を接続する構造体を宣言する。
308 マクロ \fBCIRCLEQ_INIT\fP は \fIhead\fP で参照される循環キューを初期化する。
310 マクロ \fBCIRCLEQ_INSERT_HEAD\fP は新たな要素 \fIelm\fP を循環キューの先頭に挿入する。
312 マクロ \fBCIRCLEQ_INSERT_TAIL\fP は新たな要素 \fIelm\fP を循環キューの末尾に挿入する。
314 マクロ \fBCIRCLEQ_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の後に挿入する。
316 マクロ \fBCIRCLEQ_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の前に挿入する。
318 マクロ \fBCIRCLEQ_REMOVE\fP は要素 \fIelm\fP を循環キューから削除する。
321 CIRCLEQ_HEAD(circleq, entry) head;
322 struct circleq *headp; /* 循環キューの先頭。*/
325 CIRCLEQ_ENTRY(entry) entries; /* 循環キュー。*/
329 CIRCLEQ_INIT(&head); /* 循環キューを初期化する。*/
331 n1 = malloc(sizeof(struct entry)); /* 先頭に挿入する。*/
332 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
334 n1 = malloc(sizeof(struct entry)); /* 末尾に挿入する。*/
335 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
337 n2 = malloc(sizeof(struct entry)); /* 後ろに挿入する。*/
338 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
340 n2 = malloc(sizeof(struct entry)); /* 前に挿入する。*/
341 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
343 for (np = head.cqh_first; np != (void *)&head; np = np\->entries.cqe_next)
346 for (np = head.cqh_last; np != (void *)&head; np = np\->entries.cqe_prev)
349 while (head.cqh_first != (void *)&head)
350 CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
353 POSIX.1\-2001 にはない。 BSD 系に存在する。 queue 関数は 4.4BSD で初めて登場した。
355 この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.63 の一部
356 である。プロジェクトの説明とバグ報告に関する情報は
357 http://www.kernel.org/doc/man\-pages/ に書かれている。