draft/man3/queue.3

   1 .\" Copyright (c) 1993
   2 .\"     The Regents of the University of California.  All rights reserved.
   3 .\"
   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
   7 .\" are met:
   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.
  20 .\"
  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
  31 .\" SUCH DAMAGE.
  32 .\" %%%LICENSE_END
  33 .\"
  34 .\"     @(#)queue.3     8.2 (Berkeley) 1/24/94
  35 .\"
  36 .\" hch, 2002-03-25
  37 .\" 2007-12-08, mtk, Converted from mdoc to man macros
  38 .\"
  39 .\"*******************************************************************
  40 .\"
  41 .\" This file was generated with po4a. Translate the source file.
  42 .\"
  43 .\"*******************************************************************
  44 .TH QUEUE 3 2007\-12\-28 Linux "Linux Programmer's Manual"
  45 .SH 名前
  46 LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_HEAD,
  47 LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_INIT, TAILQ_INSERT_AFTER,
  48 TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, CIRCLEQ_ENTRY,
  49 CIRCLEQ_HEAD, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE,
  50 CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLEQ_REMOVE \- リスト・テール (tail)
  51 キュー・循環キューの実装
  52 .SH 書式
  53 .nf
  54 \fB#include <sys/queue.h>\fP
  55
  56 \fBLIST_ENTRY(\fP\fITYPE\fP\fB);\fP
  57 \fBLIST_HEAD(\fP\fIHEADNAME\fP\fB, \fP\fITYPE\fP\fB);\fP
  58 \fBLIST_INIT(LIST_HEAD *\fP\fIhead\fP\fB);\fP
  59 \fBLIST_INSERT_AFTER(LIST_ENTRY *\fP\fIlistelm\fP\fB, \fP
  60 \fB                TYPE *\fP\fIelm\fP\fB, LIST_ENTRY \fP\fINAME\fP\fB);\fP
  61 \fBLIST_INSERT_HEAD(LIST_HEAD *\fP\fIhead\fP\fB, \fP
  62 \fB                TYPE *\fP\fIelm\fP\fB, LIST_ENTRY \fP\fINAME\fP\fB);\fP
  63 \fBLIST_REMOVE(TYPE *\fP\fIelm\fP\fB, LIST_ENTRY \fP\fINAME\fP\fB);\fP
  64
  65 \fBTAILQ_ENTRY(\fP\fITYPE\fP\fB);\fP
  66 \fBTAILQ_HEAD(\fP\fIHEADNAME\fP\fB, \fP\fITYPE\fP\fB);\fP
  67 \fBTAILQ_INIT(TAILQ_HEAD *\fP\fIhead\fP\fB);\fP
  68 \fBTAILQ_INSERT_AFTER(TAILQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIlistelm\fP\fB, \fP
  69 \fB                TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
  70 \fBTAILQ_INSERT_HEAD(TAILQ_HEAD *\fP\fIhead\fP\fB, \fP
  71 \fB                TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
  72 \fBTAILQ_INSERT_TAIL(TAILQ_HEAD *\fP\fIhead\fP\fB, \fP
  73 \fB                TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
  74 \fBTAILQ_REMOVE(TAILQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIelm\fP\fB, TAILQ_ENTRY \fP\fINAME\fP\fB);\fP
  75
  76 \fBCIRCLEQ_ENTRY(\fP\fITYPE\fP\fB);\fP
  77 \fBCIRCLEQ_HEAD(\fP\fIHEADNAME\fP\fB, \fP\fITYPE\fP\fB);\fP
  78 \fBCIRCLEQ_INIT(CIRCLEQ_HEAD *\fP\fIhead\fP\fB);\fP
  79 \fBCIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIlistelm\fP\fB, \fP
  80 \fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
  81 \fBCIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, TYPE *\fP\fIlistelm\fP\fB, \fP
  82 \fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
  83 \fBCIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, \fP
  84 \fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
  85 \fBCIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, \fP
  86 \fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
  87 \fBCIRCLEQ_REMOVE(CIRCLEQ_HEAD *\fP\fIhead\fP\fB, \fP
  88 \fB                TYPE *\fP\fIelm\fP\fB, CIRCLEQ_ENTRY \fP\fINAME\fP\fB);\fP
  89 .fi
  90 .SH 説明
  91 これらのマクロは、次の 3 つのデータ構造を定義して操作する: リスト・テールキュー・循環キュー。 3
  92 つのデータ構造すべてにおいて以下の機能がサポートされている:
  93 .sp
  94 .RS 4
  95 .PD 0
  96 .IP * 4
  97 新たなエントリをリストの先頭に挿入する。
  98 .IP *
  99 新たなエントリをリストのどの要素よりも後に挿入する。
 100 .IP *
 101 リストの任意のエントリを削除する。
 102 .IP *
 103 リストを順方向に辿る。
 104 .PD
 105 .RE
 106 .PP
 107 リストは 3 つのデータ構造の中で最も単純であり、 上記の機能のみをサポートする。
 108
 109 テールキューは以下の機能を追加する:
 110 .RS 4
 111 .IP * 4
 112 エントリをリストの最後に追加できる。
 113 .RE
 114 .PP
 115 ただし:
 116 .sp
 117 .RS 4
 118 .PD 0
 119 .IP 1. 4
 120 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
 121 .IP 2.
 122 各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
 123 .IP 3.
 124 リストと比べて、コードサイズは 15% 大きくなり、操作は 20% 遅くなる。
 125 .PD
 126 .RE
 127 .PP
 128 循環キューは以下の機能を追加する:
 129 .sp
 130 .RS 4
 131 .PD 0
 132 .IP * 4
 133 エントリをリストの最後に追加できる。
 134 .IP *
 135 エントリを他のエントリの前に追加できる。
 136 .IP *
 137 逆方向に末尾から先頭へ辿ることができる。
 138 .PD
 139 .RE
 140 .PP
 141 ただし:
 142 .sp
 143 .RS 4
 144 .PD 0
 145 .IP 1. 4
 146 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
 147 .IP 2.
 148 各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
 149 .IP 3.
 150 辿る際の終了条件がより複雑である。
 151 .IP 4.
 152 リストと比べて、コードサイズは 40% 大きくなり、操作は 45% 遅くなる。
 153 .PD
 154 .RE
 155 .PP
 156 マクロ定義において \fITYPE\fP はユーザ定義構造体の名前であり、 \fBLIST_ENTRY\fP, \fBTAILQ_ENTRY\fP,
 157 \fBCIRCLEQ_ENTRY\fP の何れか型のフィールドと 指定された \fINAME\fP を含まなければならない。 引き数 \fIHEADNAME\fP
 158 はユーザ定義構造体の名前であり、 マクロ \fBLIST_HEAD\fP, \fBTAILQ_HEAD\fP, \fBCIRCLEQ_HEAD\fP
 159 を用いて宣言されなければならない。 これらのマクロがどのように使われるかについての更なる説明は、 以下の例を参照すること。
 160 .SS リスト
 161 リストの先頭には、 \fBLIST_HEAD\fP マクロで定義される構造体が置かれる。 この構造体はリストの最初の要素へのポインタを 1 つ含む。 要素は
 162 2 重にリンクされており、 任意の要素はリストを辿らずに削除できる。 新しい要素は既存の要素の後またはリストの先頭に追加できる。
 163 \fBLIST_HEAD\fP 構造体は以下のように宣言されている:
 164 .in +4n
 165 .nf
 166
 167 LIST_HEAD(HEADNAME, TYPE) head;
 168 .fi
 169 .in
 170 .PP
 171 ここで \fIHEADNAME\fP は定義される構造体の名前であり、 \fITYPE\fP はリンク内でリンクされる要素の型である。
 172 リストの先頭へのポインタは、その後で次のように宣言される:
 173 .in +4n
 174 .nf
 175
 176 struct HEADNAME *headp;
 177 .fi
 178 .in
 179 .PP
 180 (名前 \fIhead\fP と \fIheadp\fP はユーザが選択できる。)
 181 .PP
 182 マクロ \fBLIST_ENTRY\fP はリストの要素を接続する構造体を宣言する。
 183 .PP
 184 マクロ \fBLIST_INIT\fP は \fIhead\fP で参照されるリストを初期化する。
 185 .PP
 186 マクロ \fBLIST_INSERT_HEAD\fP は新たな要素 \fIelm\fP をリストの先頭に挿入する。
 187 .PP
 188 マクロ \fBLIST_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の後に挿入する。
 189 .PP
 190 マクロ \fBLIST_REMOVE\fP は要素 \fIelm\fP をリストから削除する。
 191 .SS リストの例
 192 .nf
 193 LIST_HEAD(listhead, entry) head;
 194 struct listhead *headp;                 /* リストの先頭。*/
 195 struct entry {
 196     ...
 197     LIST_ENTRY(entry) entries;          /* リスト。 */
 198     ...
 199 } *n1, *n2, *np;
 200
 201 LIST_INIT(&head);                       /* リストを初期化する。*/
 202
 203 n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
 204 LIST_INSERT_HEAD(&head, n1, entries);
 205
 206 n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
 207 LIST_INSERT_AFTER(n1, n2, entries);
 208                                         /* 順方向に辿る。*/
 209 for (np = head.lh_first; np != NULL; np = np\->entries.le_next)
 210     np\-> ...
 211
 212 .\" FIXME http://sourceware.org/bugzilla/show_bug.cgi?id=1506
 213 while (head.lh_first != NULL)           /* 削除する。*/
 214     LIST_REMOVE(head.lh_first, entries);
 215 .fi
 216 .SS テールキュー
 217 テールキューの先頭には \fBTAILQ_HEAD\fP マクロで定義される構造体が置かれる。 この構造体は 1 組のポインタを含んでいる。 1
 218 つはテールキューの最初の要素へのポインタであり、 もう 1 つはテールキューの最後の要素へのポインタである。 要素は 2 重にリンクされており、
 219 任意の要素はテールキューを辿らずに削除できる。 新しい要素は既存の要素の後またはテールキューの先頭または末尾に追加できる。 \fBTAILQ_HEAD\fP
 220 構造体は以下のように定義されている:
 221 .in +4n
 222 .nf
 223
 224 TAILQ_HEAD(HEADNAME, TYPE) head;
 225 .fi
 226 .in
 227 .PP
 228 ここで \fIHEADNAME\fP は定義される構造体の名前であり、 \fITYPE\fP はテールキュー内でリンクされる要素の型である。
 229 テールキューの先頭へのポインタは、その後で次のように宣言される:
 230 .in +4n
 231 .nf
 232
 233 struct HEADNAME *headp;
 234 .fi
 235 .in
 236 .PP
 237 (名前 \fIhead\fP と \fIheadp\fP はユーザが選択できる。)
 238 .PP
 239 マクロ \fBTAILQ_ENTRY\fP はテールキューの要素を接続する構造体を宣言する。
 240 .PP
 241 マクロ \fBTAILQ_INIT\fP は \fIhead\fP で参照されるテールキューを初期化する。
 242 .PP
 243 マクロ \fBTAILQ_INSERT_HEAD\fP は新たな要素 \fIelm\fP をテールキューの先頭に挿入する。
 244 .PP
 245 マクロ \fBTAILQ_INSERT_TAIL\fP は新たな要素 \fIelm\fP をテールキューの末尾に挿入する。
 246 .PP
 247 マクロ \fBTAILQ_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の後に挿入する。
 248 .PP
 249 マクロ \fBTAILQ_REMOVE\fP は要素 \fIelm\fP をテールキューから削除する。
 250 .SS テールキューの例
 251 .nf
 252 TAILQ_HEAD(tailhead, entry) head;
 253 struct tailhead *headp;                 /* テールキューの先頭。*/
 254 struct entry {
 255     ...
 256     TAILQ_ENTRY(entry) entries;         /* テールキュー。*/
 257     ...
 258 } *n1, *n2, *np;
 259
 260 TAILQ_INIT(&head);                      /* キューを初期化する。*/
 261
 262 n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
 263 TAILQ_INSERT_HEAD(&head, n1, entries);
 264
 265 n1 = malloc(sizeof(struct entry));      /* 末尾に挿入する。*/
 266 TAILQ_INSERT_TAIL(&head, n1, entries);
 267
 268 n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
 269 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
 270                                         /* 順方向に辿る。*/
 271 for (np = head.tqh_first; np != NULL; np = np\->entries.tqe_next)
 272     np\-> ...
 273                                         /* 削除する。*/
 274 while (head.tqh_first != NULL)
 275     TAILQ_REMOVE(&head, head.tqh_first, entries);
 276 .fi
 277 .SS 循環キュー
 278 循環キューの先頭には \fBCIRCLEQ_HEAD\fP マクロで定義される構造体が置かれる。 この構造体は 1 組のポインタを含んでいる。 1
 279 つは循環キューの最初の要素へのポインタであり、 もう 1 つは循環キューの最後の要素へのポインタである。 要素は 2 重にリンクされており、
 280 任意の要素はキューを辿らずに削除できる。 新しい要素は、既存の要素の後または前、またはキューの先頭または末尾に追加できる。 A
 281 \fBCIRCLEQ_HEAD\fP 構造体は以下のように定義されている:
 282 .in +4n
 283 .nf
 284
 285 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
 286 .fi
 287 .in
 288 .PP
 289 ここで \fIHEADNAME\fP は定義される構造体の名前であり、 \fITYPE\fP は循環キュー内でリンクされる要素の型である。
 290 循環キューの先頭へのポインタは、その後で次のように宣言される:
 291 .in +4n
 292 .nf
 293
 294 struct HEADNAME *headp;
 295 .fi
 296 .in
 297 .PP
 298 (名前 \fIhead\fP と \fIheadp\fP はユーザが選択できる。)
 299 .PP
 300 マクロ \fBCIRCLEQ_ENTRY\fP は循環キューの要素を接続する構造体を宣言する。
 301 .PP
 302 マクロ \fBCIRCLEQ_INIT\fP は \fIhead\fP で参照される循環キューを初期化する。
 303 .PP
 304 マクロ \fBCIRCLEQ_INSERT_HEAD\fP は新たな要素 \fIelm\fP を循環キューの先頭に挿入する。
 305 .PP
 306 マクロ \fBCIRCLEQ_INSERT_TAIL\fP は新たな要素 \fIelm\fP を循環キューの末尾に挿入する。
 307 .PP
 308 マクロ \fBCIRCLEQ_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の後に挿入する。
 309 .PP
 310 マクロ \fBCIRCLEQ_INSERT_AFTER\fP は新たな要素 \fIelm\fP を要素 \fIlistelm\fP の前に挿入する。
 311 .PP
 312 マクロ \fBCIRCLEQ_REMOVE\fP は要素 \fIelm\fP を循環キューから削除する。
 313 .SS 循環キューの例
 314 .nf
 315 CIRCLEQ_HEAD(circleq, entry) head;
 316 struct circleq *headp;                  /* 循環キューの先頭。*/
 317 struct entry {
 318     ...
 319     CIRCLEQ_ENTRY(entry) entries;       /* 循環キュー。*/
 320     ...
 321 } *n1, *n2, *np;
 322
 323 CIRCLEQ_INIT(&head);                    /* 循環キューを初期化する。*/
 324
 325 n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
 326 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
 327
 328 n1 = malloc(sizeof(struct entry));      /* 末尾に挿入する。*/
 329 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
 330
 331 n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
 332 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
 333
 334 n2 = malloc(sizeof(struct entry));      /* 前に挿入する。*/
 335 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
 336                                         /* 順方向に辿る。*/
 337 for (np = head.cqh_first; np != (void *)&head; np = np\->entries.cqe_next)
 338     np\-> ...
 339                                         /* 逆方向に辿る。*/
 340 for (np = head.cqh_last; np != (void *)&head; np = np\->entries.cqe_prev)
 341     np\-> ...
 342                                         /* 削除する。*/
 343 while (head.cqh_first != (void *)&head)
 344     CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
 345 .fi
 346 .SH 準拠
 347 POSIX.1\-2001 にはない。 BSD 系に存在する。 queue 関数は 4.4BSD で初めて登場した。
 348 .SH この文書について
 349 この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.52 の一部
 350 である。プロジェクトの説明とバグ報告に関する情報は
 351 http://www.kernel.org/doc/man\-pages/ に書かれている。