release/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 .\" Japanese Version Copyright (c) 2004 Yuichi SATO
  38 .\"         all rights reserved.
  39 .\" Translated Thu Sep  2 04:41:11 JST 2004
  40 .\"         by Yuichi SATO <ysato444@yahoo.co.jp>
  41 .\"
  42 .\"WORD:        circular queue  循環キュー
  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, \
  47 LIST_INSERT_HEAD, LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, \
  48 TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, \
  49 TAILQ_REMOVE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_INIT, \
  50 CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, \
  51 CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, \
  52 CIRCLEQ_REMOVE \- リスト・テール (tail) キュー・循環キューの実装
  53 .SH 書式
  54 .nf
  55 .B #include <sys/queue.h>
  56
  57 .BI "LIST_ENTRY(" TYPE );
  58 .BI "LIST_HEAD(" HEADNAME ", " TYPE );
  59 .BI "LIST_INIT(LIST_HEAD *" head );
  60 .BI "LIST_INSERT_AFTER(LIST_ENTRY *" listelm ", "
  61 .BI "                TYPE *" elm ", LIST_ENTRY " NAME );
  62 .BI "LIST_INSERT_HEAD(LIST_HEAD *" head ", "
  63 .BI "                TYPE *" elm ", LIST_ENTRY " NAME );
  64 .BI "LIST_REMOVE(TYPE *" elm ", LIST_ENTRY " NAME );
  65
  66 .BI "TAILQ_ENTRY(" TYPE );
  67 .BI "TAILQ_HEAD("HEADNAME ", " TYPE );
  68 .BI "TAILQ_INIT(TAILQ_HEAD *" head );
  69 .BI "TAILQ_INSERT_AFTER(TAILQ_HEAD *" head ", TYPE *" listelm ", "
  70 .BI "                TYPE *" elm ", TAILQ_ENTRY " NAME );
  71 .BI "TAILQ_INSERT_HEAD(TAILQ_HEAD *" head ", "
  72 .BI "                TYPE *" elm ", TAILQ_ENTRY " NAME );
  73 .BI "TAILQ_INSERT_TAIL(TAILQ_HEAD *" head ", "
  74 .BI "                TYPE *" elm ", TAILQ_ENTRY " NAME );
  75 .BI "TAILQ_REMOVE(TAILQ_HEAD *" head ", TYPE *" elm ", TAILQ_ENTRY " NAME );
  76
  77 .BI CIRCLEQ_ENTRY( TYPE );
  78 .BI "CIRCLEQ_HEAD(" HEADNAME ", " TYPE );
  79 .BI "CIRCLEQ_INIT(CIRCLEQ_HEAD *" head );
  80 .BI "CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *" head ", TYPE *" listelm ", "
  81 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  82 .BI "CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *" head ", TYPE *" listelm ", "
  83 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  84 .BI "CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *" head ", "
  85 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  86 .BI "CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *" head ", "
  87 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  88 .BI "CIRCLEQ_REMOVE(CIRCLEQ_HEAD *" head ", "
  89 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  90 .fi
  91 .SH 説明
  92 これらのマクロは、次の 3 つのデータ構造を定義して操作する:
  93 リスト・テールキュー・循環キュー。
  94 3 つのデータ構造すべてにおいて以下の機能がサポートされている:
  95 .sp
  96 .RS 4
  97 .PD 0
  98 .IP * 4
  99 新たなエントリをリストの先頭に挿入する。
 100 .IP *
 101 新たなエントリをリストのどの要素よりも後に挿入する。
 102 .IP *
 103 リストの任意のエントリを削除する。
 104 .IP *
 105 リストを順方向に辿る。
 106 .PD
 107 .RE
 108 .PP
 109 リストは 3 つのデータ構造の中で最も単純であり、
 110 上記の機能のみをサポートする。
 111
 112 テールキューは以下の機能を追加する:
 113 .RS 4
 114 .IP * 4
 115 エントリをリストの最後に追加できる。
 116 .RE
 117 .PP
 118 ただし:
 119 .sp
 120 .RS 4
 121 .PD 0
 122 .IP 1. 4
 123 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
 124 .IP 2.
 125 各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
 126 .IP 3.
 127 リストと比べて、コードサイズは 15% 大きくなり、操作は 20% 遅くなる。
 128 .PD
 129 .RE
 130 .PP
 131 循環キューは以下の機能を追加する:
 132 .sp
 133 .RS 4
 134 .PD 0
 135 .IP * 4
 136 エントリをリストの最後に追加できる。
 137 .IP *
 138 エントリを他のエントリの前に追加できる。
 139 .IP *
 140 逆方向に末尾から先頭へ辿ることができる。
 141 .PD
 142 .RE
 143 .PP
 144 ただし:
 145 .sp
 146 .RS 4
 147 .PD 0
 148 .IP 1. 4
 149 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
 150 .IP 2.
 151 各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
 152 .IP 3.
 153 辿る際の終了条件がより複雑である。
 154 .IP 4.
 155 リストと比べて、コードサイズは 40% 大きくなり、操作は 45% 遅くなる。
 156 .PD
 157 .RE
 158 .PP
 159 マクロ定義において
 160 .I TYPE
 161 はユーザ定義構造体の名前であり、
 162 .BR LIST_ENTRY ,
 163 .BR TAILQ_ENTRY ,
 164 .BR CIRCLEQ_ENTRY
 165 の何れか型のフィールドと
 166 指定された
 167 .I NAME
 168 を含まなければならない。
 169 引き数
 170 .I HEADNAME
 171 はユーザ定義構造体の名前であり、
 172 マクロ
 173 .BR LIST_HEAD ,
 174 .BR TAILQ_HEAD ,
 175 .BR CIRCLEQ_HEAD
 176 を用いて宣言されなければならない。
 177 これらのマクロがどのように使われるかについての更なる説明は、
 178 以下の例を参照すること。
 179 .SS リスト
 180 リストの先頭には、
 181 .B LIST_HEAD
 182 マクロで定義される構造体が置かれる。
 183 この構造体はリストの最初の要素へのポインタを 1 つ含む。
 184 要素は 2 重にリンクされており、
 185 任意の要素はリストを辿らずに削除できる。
 186 新しい要素は既存の要素の後またはリストの先頭に追加できる。
 187 .B LIST_HEAD
 188 構造体は以下のように宣言されている:
 189 .in +4n
 190 .nf
 191
 192 LIST_HEAD(HEADNAME, TYPE) head;
 193 .fi
 194 .in
 195 .PP
 196 ここで
 197 .I HEADNAME
 198 は定義される構造体の名前であり、
 199 .I TYPE
 200 はリンク内でリンクされる要素の型である。
 201 リストの先頭へのポインタは、その後で次のように宣言される:
 202 .in +4n
 203 .nf
 204
 205 struct HEADNAME *headp;
 206 .fi
 207 .in
 208 .PP
 209 (名前
 210 .IR "head"
 211 と
 212 .IR "headp"
 213 はユーザが選択できる。)
 214 .PP
 215 マクロ
 216 .B LIST_ENTRY
 217 はリストの要素を接続する構造体を宣言する。
 218 .PP
 219 マクロ
 220 .B LIST_INIT
 221 は
 222 .I head
 223 で参照されるリストを初期化する。
 224 .PP
 225 マクロ
 226 .B LIST_INSERT_HEAD
 227 は新たな要素
 228 .I elm
 229 をリストの先頭に挿入する。
 230 .PP
 231 マクロ
 232 .B LIST_INSERT_AFTER
 233 は新たな要素
 234 .I elm
 235 を要素
 236 .I listelm
 237 の後に挿入する。
 238 .PP
 239 マクロ
 240 .B LIST_REMOVE
 241 は要素
 242 .I elm
 243 をリストから削除する。
 244 .SS リストの例
 245 .nf
 246
 247 LIST_HEAD(listhead, entry) head;
 248 struct listhead *headp;                 /* リストの先頭。*/
 249 struct entry {
 250     ...
 251     LIST_ENTRY(entry) entries;          /* リスト。 */
 252     ...
 253 } *n1, *n2, *np;
 254
 255 LIST_INIT(&head);                       /* リストを初期化する。*/
 256
 257 n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
 258 LIST_INSERT_HEAD(&head, n1, entries);
 259
 260 n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
 261 LIST_INSERT_AFTER(n1, n2, entries);
 262                                         /* 順方向に辿る。*/
 263 for (np = head.lh_first; np != NULL; np = np\->entries.le_next)
 264     np\-> ...
 265
 266 while (head.lh_first != NULL)           /* 削除する。*/
 267     LIST_REMOVE(head.lh_first, entries);
 268 .fi
 269 .SS テールキュー
 270 テールキューの先頭には
 271 .B TAILQ_HEAD
 272 マクロで定義される構造体が置かれる。
 273 この構造体は 1 組のポインタを含んでいる。
 274 1 つはテールキューの最初の要素へのポインタであり、
 275 もう 1 つはテールキューの最後の要素へのポインタである。
 276 要素は 2 重にリンクされており、
 277 任意の要素はテールキューを辿らずに削除できる。
 278 新しい要素は既存の要素の後またはテールキューの先頭または末尾に追加できる。
 279 .B TAILQ_HEAD
 280 構造体は以下のように定義されている:
 281 .in +4n
 282 .nf
 283
 284 TAILQ_HEAD(HEADNAME, TYPE) head;
 285 .fi
 286 .in
 287 .PP
 288 ここで
 289 .Li HEADNAME
 290 は定義される構造体の名前であり、
 291 .Li TYPE
 292 はテールキュー内でリンクされる要素の型である。
 293 テールキューの先頭へのポインタは、その後で次のように宣言される:
 294 .in +4n
 295 .nf
 296
 297 struct HEADNAME *headp;
 298 .fi
 299 .in
 300 .PP
 301 (名前
 302 .IR "head"
 303 と
 304 .IR "headp"
 305 はユーザが選択できる。)
 306 .PP
 307 マクロ
 308 .B TAILQ_ENTRY
 309 はテールキューの要素を接続する構造体を宣言する。
 310 .PP
 311 マクロ
 312 .B TAILQ_INIT
 313 は
 314 .I head
 315 で参照されるテールキューを初期化する。
 316 .PP
 317 マクロ
 318 .B TAILQ_INSERT_HEAD
 319 は新たな要素
 320 .I elm
 321 をテールキューの先頭に挿入する。
 322 .PP
 323 マクロ
 324 .B TAILQ_INSERT_TAIL
 325 は新たな要素
 326 .I elm
 327 をテールキューの末尾に挿入する。
 328 .PP
 329 マクロ
 330 .B TAILQ_INSERT_AFTER
 331 は新たな要素
 332 .I elm
 333 を要素
 334 .Fa listelm
 335 の後に挿入する。
 336 .PP
 337 マクロ
 338 .B TAILQ_REMOVE
 339 は要素
 340 .I elm
 341 をテールキューから削除する。
 342 .SS テールキューの例
 343 .nf
 344
 345 TAILQ_HEAD(tailhead, entry) head;
 346 struct tailhead *headp;                 /* テールキューの先頭。*/
 347 struct entry {
 348     ...
 349     TAILQ_ENTRY(entry) entries;         /* テールキュー。*/
 350     ...
 351 } *n1, *n2, *np;
 352
 353 TAILQ_INIT(&head);                      /* キューを初期化する。*/
 354
 355 n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
 356 TAILQ_INSERT_HEAD(&head, n1, entries);
 357
 358 n1 = malloc(sizeof(struct entry));      /* 末尾に挿入する。*/
 359 TAILQ_INSERT_TAIL(&head, n1, entries);
 360
 361 n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
 362 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
 363                                         /* 順方向に辿る。*/
 364 for (np = head.tqh_first; np != NULL; np = np\->entries.tqe_next)
 365     np\-> ...
 366                                         /* 削除する。*/
 367 while (head.tqh_first != NULL)
 368     TAILQ_REMOVE(&head, head.tqh_first, entries);
 369 .fi
 370 .SS 循環キュー
 371 循環キューの先頭には
 372 .B CIRCLEQ_HEAD
 373 マクロで定義される構造体が置かれる。
 374 この構造体は 1 組のポインタを含んでいる。
 375 1 つは循環キューの最初の要素へのポインタであり、
 376 もう 1 つは循環キューの最後の要素へのポインタである。
 377 要素は 2 重にリンクされており、
 378 任意の要素はキューを辿らずに削除できる。
 379 新しい要素は、既存の要素の後または前、またはキューの先頭または末尾に追加できる。
 380 A
 381 .B CIRCLEQ_HEAD
 382 構造体は以下のように定義されている:
 383 .in +4n
 384 .nf
 385
 386 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
 387 .fi
 388 .in
 389 .PP
 390 ここで
 391 .IR "HEADNAME"
 392 は定義される構造体の名前であり、
 393 .IR "TYPE"
 394 は循環キュー内でリンクされる要素の型である。
 395 循環キューの先頭へのポインタは、その後で次のように宣言される:
 396 .in +4n
 397 .nf
 398
 399 struct HEADNAME *headp;
 400 .fi
 401 .in
 402 .PP
 403 (名前
 404 .I head
 405 と
 406 .I headp
 407 はユーザが選択できる。)
 408 .PP
 409 マクロ
 410 .B CIRCLEQ_ENTRY
 411 は循環キューの要素を接続する構造体を宣言する。
 412 .PP
 413 マクロ
 414 .B CIRCLEQ_INIT
 415 は
 416 .I head
 417 で参照される循環キューを初期化する。
 418 .PP
 419 マクロ
 420 .B CIRCLEQ_INSERT_HEAD
 421 は新たな要素
 422 .I elm
 423 を循環キューの先頭に挿入する。
 424 .PP
 425 マクロ
 426 .B CIRCLEQ_INSERT_TAIL
 427 は新たな要素
 428 .I elm
 429 を循環キューの末尾に挿入する。
 430 .PP
 431 マクロ
 432 .B CIRCLEQ_INSERT_AFTER
 433 は新たな要素
 434 .I elm
 435 を要素
 436 .I listelm
 437 の後に挿入する。
 438 .PP
 439 マクロ
 440 .B CIRCLEQ_INSERT_AFTER
 441 は新たな要素
 442 .I elm
 443 を要素
 444 .I listelm
 445 の前に挿入する。
 446 .PP
 447 マクロ
 448 .B CIRCLEQ_REMOVE
 449 は要素
 450 .I elm
 451 を循環キューから削除する。
 452 .SS 循環キューの例
 453 .nf
 454
 455 CIRCLEQ_HEAD(circleq, entry) head;
 456 struct circleq *headp;                  /* 循環キューの先頭。*/
 457 struct entry {
 458     ...
 459     CIRCLEQ_ENTRY(entry) entries;       /* 循環キュー。*/
 460     ...
 461 } *n1, *n2, *np;
 462
 463 CIRCLEQ_INIT(&head);                    /* 循環キューを初期化する。*/
 464
 465 n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
 466 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
 467
 468 n1 = malloc(sizeof(struct entry));      /* 末尾に挿入する。*/
 469 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
 470
 471 n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
 472 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
 473
 474 n2 = malloc(sizeof(struct entry));      /* 前に挿入する。*/
 475 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
 476                                         /* 順方向に辿る。*/
 477 for (np = head.cqh_first; np != (void *)&head; np = np\->entries.cqe_next)
 478     np\-> ...
 479                                         /* 逆方向に辿る。*/
 480 for (np = head.cqh_last; np != (void *)&head; np = np\->entries.cqe_prev)
 481     np\-> ...
 482                                         /* 削除する。*/
 483 while (head.cqh_first != (void *)&head)
 484     CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
 485 .fi
 486 .SH 準拠
 487 POSIX.1-2001 にはない。
 488 BSD 系に存在する。
 489 queue 関数は 4.4BSD で初めて登場した。