draft/man3/queue.3

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