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 .\" 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 .\"O .SH NAME
  46 .SH 名前
  47 .\"O LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, \
  48 .\"O LIST_INSERT_HEAD, LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, \
  49 .\"O TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, \
  50 .\"O TAILQ_REMOVE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_INIT, \
  51 .\"O CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, \
  52 .\"O CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, \
  53 .\"O CIRCLEQ_REMOVE \- implementations of lists, tail queues, and circular queues
  54 LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, \
  55 LIST_INSERT_HEAD, LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, \
  56 TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, \
  57 TAILQ_REMOVE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_INIT, \
  58 CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, \
  59 CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, \
  60 CIRCLEQ_REMOVE \- リスト・テール (tail) キュー・循環キューの実装
  61 .\"Osato:
  62 .\"Osato: tail queue の良い訳語が分からないので、とりあえずカタカナにする。
  63 .\"Osato:
  64 .\"O .SH SYNOPSIS
  65 .SH 書式
  66 .nf
  67 .B #include <sys/queue.h>
  68
  69 .BI "LIST_ENTRY(" TYPE );
  70 .BI "LIST_HEAD(" HEADNAME ", " TYPE );
  71 .BI "LIST_INIT(LIST_HEAD *" head );
  72 .BI "LIST_INSERT_AFTER(LIST_ENTRY *" listelm ", "
  73 .BI "                TYPE *" elm ", LIST_ENTRY " NAME );
  74 .BI "LIST_INSERT_HEAD(LIST_HEAD *" head ", "
  75 .BI "                TYPE *" elm ", LIST_ENTRY " NAME );
  76 .BI "LIST_REMOVE(TYPE *" elm ", LIST_ENTRY " NAME );
  77
  78 .BI "TAILQ_ENTRY(" TYPE );
  79 .BI "TAILQ_HEAD("HEADNAME ", " TYPE );
  80 .BI "TAILQ_INIT(TAILQ_HEAD *" head );
  81 .BI "TAILQ_INSERT_AFTER(TAILQ_HEAD *" head ", TYPE *" listelm ", "
  82 .BI "                TYPE *" elm ", TAILQ_ENTRY " NAME );
  83 .BI "TAILQ_INSERT_HEAD(TAILQ_HEAD *" head ", "
  84 .BI "                TYPE *" elm ", TAILQ_ENTRY " NAME );
  85 .BI "TAILQ_INSERT_TAIL(TAILQ_HEAD *" head ", "
  86 .BI "                TYPE *" elm ", TAILQ_ENTRY " NAME );
  87 .BI "TAILQ_REMOVE(TAILQ_HEAD *" head ", TYPE *" elm ", TAILQ_ENTRY " NAME );
  88
  89 .BI CIRCLEQ_ENTRY( TYPE );
  90 .BI "CIRCLEQ_HEAD(" HEADNAME ", " TYPE );
  91 .BI "CIRCLEQ_INIT(CIRCLEQ_HEAD *" head );
  92 .BI "CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *" head ", TYPE *" listelm ", "
  93 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  94 .BI "CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *" head ", TYPE *" listelm ", "
  95 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  96 .BI "CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *" head ", "
  97 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
  98 .BI "CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *" head ", "
  99 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
 100 .BI "CIRCLEQ_REMOVE(CIRCLEQ_HEAD *" head ", "
 101 .BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
 102 .fi
 103 .\"O .SH DESCRIPTION
 104 .SH 説明
 105 .\"O These macros define and operate on three types of data structures:
 106 .\"O lists, tail queues, and circular queues.
 107 .\"O All three structures support the following functionality:
 108 これらのマクロは、次の 3 つのデータ構造を定義して操作する:
 109 リスト・テールキュー・循環キュー。
 110 3 つのデータ構造すべてにおいて以下の機能がサポートされている:
 111 .sp
 112 .RS 4
 113 .PD 0
 114 .IP * 4
 115 .\"O Insertion of a new entry at the head of the list.
 116 新たなエントリをリストの先頭に挿入する。
 117 .IP *
 118 .\"O Insertion of a new entry after any element in the list.
 119 新たなエントリをリストのどの要素よりも後に挿入する。
 120 .IP *
 121 .\"O Removal of any entry in the list.
 122 リストの任意のエントリを削除する。
 123 .IP *
 124 .\"O Forward traversal through the list.
 125 リストを順方向に辿る。
 126 .PD
 127 .RE
 128 .PP
 129 .\"O Lists are the simplest of the three data structures and support
 130 .\"O only the above functionality.
 131 リストは 3 つのデータ構造の中で最も単純であり、
 132 上記の機能のみをサポートする。
 133
 134 .\"O Tail queues add the following functionality:
 135 テールキューは以下の機能を追加する:
 136 .RS 4
 137 .IP * 4
 138 .\"O Entries can be added at the end of a list.
 139 エントリをリストの最後に追加できる。
 140 .RE
 141 .PP
 142 .\"O However:
 143 ただし:
 144 .sp
 145 .RS 4
 146 .PD 0
 147 .IP 1. 4
 148 .\"O All list insertions and removals must specify the head of the list.
 149 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
 150 .IP 2.
 151 .\"O Each head entry requires two pointers rather than one.
 152 各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
 153 .IP 3.
 154 .\"O Code size is about 15% greater and operations run about 20% slower
 155 .\"O than lists.
 156 リストと比べて、コードサイズは 15% 大きくなり、操作は 20% 遅くなる。
 157 .PD
 158 .RE
 159 .PP
 160 .\"O Circular queues add the following functionality:
 161 循環キューは以下の機能を追加する:
 162 .sp
 163 .RS 4
 164 .PD 0
 165 .IP * 4
 166 .\"O Entries can be added at the end of a list.
 167 エントリをリストの最後に追加できる。
 168 .IP *
 169 .\"O Entries can be added before another entry.
 170 エントリを他のエントリの前に追加できる。
 171 .IP *
 172 .\"O They may be traversed backward, from tail to head.
 173 逆方向に末尾から先頭へ辿ることができる。
 174 .PD
 175 .RE
 176 .PP
 177 .\"O However:
 178 ただし:
 179 .sp
 180 .RS 4
 181 .PD 0
 182 .IP 1. 4
 183 .\"O All list insertions and removals must specify the head of the list.
 184 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
 185 .IP 2.
 186 .\"O Each head entry requires two pointers rather than one.
 187 各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
 188 .IP 3.
 189 .\"O The termination condition for traversal is more complex.
 190 辿る際の終了条件がより複雑である。
 191 .IP 4.
 192 .\"O Code size is about 40% greater and operations run about 45% slower
 193 .\"O than lists.
 194 リストと比べて、コードサイズは 40% 大きくなり、操作は 45% 遅くなる。
 195 .PD
 196 .RE
 197 .PP
 198 .\"O In the macro definitions,
 199 .\"O .I TYPE
 200 .\"O is the name of a user-defined structure,
 201 .\"O that must contain a field of type
 202 .\"O .BR LIST_ENTRY ,
 203 .\"O .BR TAILQ_ENTRY ,
 204 .\"O or
 205 .\"O .BR CIRCLEQ_ENTRY ,
 206 .\"O named
 207 .\"O .IR NAME .
 208 マクロ定義において
 209 .I TYPE
 210 はユーザ定義構造体の名前であり、
 211 .BR LIST_ENTRY ,
 212 .BR TAILQ_ENTRY ,
 213 .BR CIRCLEQ_ENTRY
 214 の何れか型のフィールドと
 215 指定された
 216 .I NAME
 217 を含まなければならない。
 218 .\"O The argument
 219 .\"O .I HEADNAME
 220 .\"O is the name of a user-defined structure that must be declared
 221 .\"O using the macros
 222 .\"O .BR LIST_HEAD ,
 223 .\"O .BR TAILQ_HEAD ,
 224 .\"O or
 225 .\"O .BR CIRCLEQ_HEAD .
 226 引き数
 227 .I HEADNAME
 228 はユーザ定義構造体の名前であり、
 229 マクロ
 230 .BR LIST_HEAD ,
 231 .BR TAILQ_HEAD ,
 232 .BR CIRCLEQ_HEAD
 233 を用いて宣言されなければならない。
 234 .\"O See the examples below for further explanation of how these
 235 .\"O macros are used.
 236 これらのマクロがどのように使われるかについての更なる説明は、
 237 以下の例を参照すること。
 238 .\"O .SS LISTS
 239 .SS リスト
 240 .\"O A list is headed by a structure defined by the
 241 .\"O .B LIST_HEAD
 242 .\"O macro.
 243 リストの先頭には、
 244 .B LIST_HEAD
 245 マクロで定義される構造体が置かれる。
 246 .\"O This structure contains a single pointer to the first element
 247 .\"O on the list.
 248 この構造体はリストの最初の要素へのポインタを 1 つ含む。
 249 .\"O The elements are doubly linked so that an arbitrary element can be
 250 .\"O removed without traversing the list.
 251 要素は 2 重にリンクされており、
 252 任意の要素はリストを辿らずに削除できる。
 253 .\"O New elements can be added to the list after an existing element or
 254 .\"O at the head of the list.
 255 新しい要素は既存の要素の後またはリストの先頭に追加できる。
 256 .\"O A
 257 .\"O .B LIST_HEAD
 258 .\"O structure is declared as follows:
 259 .B LIST_HEAD
 260 構造体は以下のように宣言されている:
 261 .in +4n
 262 .nf
 263
 264 LIST_HEAD(HEADNAME, TYPE) head;
 265 .fi
 266 .in
 267 .PP
 268 .\"O where
 269 .\"O .I HEADNAME
 270 .\"O is the name of the structure to be defined, and
 271 .\"O .I TYPE
 272 .\"O is the type of the elements to be linked into the list.
 273 ここで
 274 .I HEADNAME
 275 は定義される構造体の名前であり、
 276 .I TYPE
 277 はリンク内でリンクされる要素の型である。
 278 .\"O A pointer to the head of the list can later be declared as:
 279 リストの先頭へのポインタは、その後で次のように宣言される:
 280 .in +4n
 281 .nf
 282
 283 struct HEADNAME *headp;
 284 .fi
 285 .in
 286 .PP
 287 .\"O (The names
 288 .\"O .IR "head"
 289 .\"O and
 290 .\"O .IR "headp"
 291 .\"O are user selectable.)
 292 (名前
 293 .IR "head"
 294 と
 295 .IR "headp"
 296 はユーザが選択できる。)
 297 .PP
 298 .\"O The macro
 299 .\"O .B LIST_ENTRY
 300 .\"O declares a structure that connects the elements in
 301 .\"O the list.
 302 マクロ
 303 .B LIST_ENTRY
 304 はリストの要素を接続する構造体を宣言する。
 305 .PP
 306 .\"O The macro
 307 .\"O .B LIST_INIT
 308 .\"O initializes the list referenced by
 309 .\"O .IR head .
 310 マクロ
 311 .B LIST_INIT
 312 は
 313 .I head
 314 で参照されるリストを初期化する。
 315 .PP
 316 .\"O The macro
 317 .\"O .B LIST_INSERT_HEAD
 318 .\"O inserts the new element
 319 .\"O .I elm
 320 .\"O at the head of the list.
 321 マクロ
 322 .B LIST_INSERT_HEAD
 323 は新たな要素
 324 .I elm
 325 をリストの先頭に挿入する。
 326 .PP
 327 .\"O The macro
 328 .\"O .B LIST_INSERT_AFTER
 329 .\"O inserts the new element
 330 .\"O .I elm
 331 .\"O after the element
 332 .\"O .I listelm .
 333 マクロ
 334 .B LIST_INSERT_AFTER
 335 は新たな要素
 336 .I elm
 337 を要素
 338 .I listelm
 339 の後に挿入する。
 340 .PP
 341 .\"O The macro
 342 .\"O .B LIST_REMOVE
 343 .\"O removes the element
 344 .\"O .I elm
 345 .\"O from the list.
 346 マクロ
 347 .B LIST_REMOVE
 348 は要素
 349 .I elm
 350 をリストから削除する。
 351 .\"O .SS LIST EXAMPLE
 352 .SS リストの例
 353 .nf
 354
 355 LIST_HEAD(listhead, entry) head;
 356 .\"O struct listhead *headp;                 /* List head. */
 357 struct listhead *headp;                 /* リストの先頭。*/
 358 struct entry {
 359 .\"O     ...
 360 .\"O     LIST_ENTRY(entry) entries;          /* List. */
 361 .\"O     ...
 362     ...
 363     LIST_ENTRY(entry) entries;          /* リスト。 */
 364     ...
 365 } *n1, *n2, *np;
 366
 367 .\"O LIST_INIT(&head);                       /* Initialize the list. */
 368 LIST_INIT(&head);                       /* リストを初期化する。*/
 369
 370 .\"O n1 = malloc(sizeof(struct entry));     /* Insert at the head. */
 371 n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
 372 LIST_INSERT_HEAD(&head, n1, entries);
 373
 374 .\"O n2 = malloc(sizeof(struct entry));     /* Insert after. */
 375 n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
 376 LIST_INSERT_AFTER(n1, n2, entries);
 377 .\"O                                         /* Forward traversal. */
 378                                         /* 順方向に辿る。*/
 379 for (np = head.lh_first; np != NULL; np = np\->entries.le_next)
 380     np\-> ...
 381
 382 .\"O while (head.lh_first != NULL)           /* Delete. */
 383 while (head.lh_first != NULL)           /* 削除する。*/
 384     LIST_REMOVE(head.lh_first, entries);
 385 .fi
 386 .\"O .SS Tail Queues
 387 .SS テールキュー
 388 .\"O A tail queue is headed by a structure defined by the
 389 .\"O .B TAILQ_HEAD
 390 .\"O macro.
 391 テールキューの先頭には
 392 .B TAILQ_HEAD
 393 マクロで定義される構造体が置かれる。
 394 .\"O This structure contains a pair of pointers,
 395 .\"O one to the first element in the tail queue and the other to
 396 .\"O the last element in the tail queue.
 397 この構造体は 1 組のポインタを含んでいる。
 398 1 つはテールキューの最初の要素へのポインタであり、
 399 もう 1 つはテールキューの最後の要素へのポインタである。
 400 .\"O The elements are doubly linked so that an arbitrary element can be
 401 .\"O removed without traversing the tail queue.
 402 要素は 2 重にリンクされており、
 403 任意の要素はテールキューを辿らずに削除できる。
 404 .\"O New elements can be added to the tail queue after an existing element,
 405 .\"O at the head of the tail queue, or at the end of the tail queue.
 406 新しい要素は既存の要素の後またはテールキューの先頭または末尾に追加できる。
 407 .\"O A
 408 .\"O .B TAILQ_HEAD
 409 .\"O structure is declared as follows:
 410 .B TAILQ_HEAD
 411 構造体は以下のように定義されている:
 412 .in +4n
 413 .nf
 414
 415 TAILQ_HEAD(HEADNAME, TYPE) head;
 416 .fi
 417 .in
 418 .PP
 419 .\"O where
 420 .\"O .IR "HEADNAME"
 421 .\"O is the name of the structure to be defined, and
 422 .\"O .IR "TYPE"
 423 .\"O is the type of the elements to be linked into the tail queue.
 424 ここで
 425 .Li HEADNAME
 426 は定義される構造体の名前であり、
 427 .Li TYPE
 428 はテールキュー内でリンクされる要素の型である。
 429 .\"O A pointer to the head of the tail queue can later be declared as:
 430 テールキューの先頭へのポインタは、その後で次のように宣言される:
 431 .in +4n
 432 .nf
 433
 434 struct HEADNAME *headp;
 435 .fi
 436 .in
 437 .PP
 438 .\"O (The names
 439 .\"O .IR "head"
 440 .\"O and
 441 .\"O .IR "headp"
 442 .\"O are user selectable.)
 443 (名前
 444 .IR "head"
 445 と
 446 .IR "headp"
 447 はユーザが選択できる。)
 448 .PP
 449 .\"O The macro
 450 .\"O .B TAILQ_ENTRY
 451 .\"O declares a structure that connects the elements in
 452 .\"O the tail queue.
 453 マクロ
 454 .B TAILQ_ENTRY
 455 はテールキューの要素を接続する構造体を宣言する。
 456 .PP
 457 .\"O The macro
 458 .\"O .B TAILQ_INIT
 459 .\"O initializes the tail queue referenced by
 460 .\"O .IR head .
 461 マクロ
 462 .B TAILQ_INIT
 463 は
 464 .I head
 465 で参照されるテールキューを初期化する。
 466 .PP
 467 .\"O The macro
 468 .\"O .B TAILQ_INSERT_HEAD
 469 .\"O inserts the new element
 470 .\"O .I elm
 471 .\"O at the head of the tail queue.
 472 マクロ
 473 .B TAILQ_INSERT_HEAD
 474 は新たな要素
 475 .I elm
 476 をテールキューの先頭に挿入する。
 477 .PP
 478 .\"O The macro
 479 .\"O .B TAILQ_INSERT_TAIL
 480 .\"O inserts the new element
 481 .\"O .I elm
 482 .\"O at the end of the tail queue.
 483 マクロ
 484 .B TAILQ_INSERT_TAIL
 485 は新たな要素
 486 .I elm
 487 をテールキューの末尾に挿入する。
 488 .PP
 489 .\"O The macro
 490 .\"O .B TAILQ_INSERT_AFTER
 491 .\"O inserts the new element
 492 .\"O .I elm
 493 .\"O after the element
 494 .\"O .I listelm .
 495 マクロ
 496 .B TAILQ_INSERT_AFTER
 497 は新たな要素
 498 .I elm
 499 を要素
 500 .Fa listelm
 501 の後に挿入する。
 502 .PP
 503 .\"O The macro
 504 .\"O .B TAILQ_REMOVE
 505 .\"O removes the element
 506 .\"O .I elm
 507 .\"O from the tail queue.
 508 マクロ
 509 .B TAILQ_REMOVE
 510 は要素
 511 .I elm
 512 をテールキューから削除する。
 513 .\"O .SS Tail Queue Example
 514 .SS テールキューの例
 515 .nf
 516
 517 TAILQ_HEAD(tailhead, entry) head;
 518 .\"O struct tailhead *headp;                 /* Tail queue head. */
 519 struct tailhead *headp;                 /* テールキューの先頭。*/
 520 struct entry {
 521     ...
 522 .\"O    TAILQ_ENTRY(entry) entries;          /* Tail queue. */
 523     TAILQ_ENTRY(entry) entries;         /* テールキュー。*/
 524     ...
 525 } *n1, *n2, *np;
 526
 527 .\"O TAILQ_INIT(&head);                      /* Initialize the queue. */
 528 TAILQ_INIT(&head);                      /* キューを初期化する。*/
 529
 530 .\"O n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 531 n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
 532 TAILQ_INSERT_HEAD(&head, n1, entries);
 533
 534 .\"O n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 535 n1 = malloc(sizeof(struct entry));      /* 末尾に挿入する。*/
 536 TAILQ_INSERT_TAIL(&head, n1, entries);
 537
 538 .\"O n2 = malloc(sizeof(struct entry));      /* Insert after. */
 539 n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
 540 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
 541 .\"O                                         /* Forward traversal. */
 542                                         /* 順方向に辿る。*/
 543 for (np = head.tqh_first; np != NULL; np = np\->entries.tqe_next)
 544     np\-> ...
 545 .\"O                                         /* Delete. */
 546                                         /* 削除する。*/
 547 while (head.tqh_first != NULL)
 548     TAILQ_REMOVE(&head, head.tqh_first, entries);
 549 .fi
 550 .\"O .SS Circular Queues
 551 .SS 循環キュー
 552 .\"O A circular queue is headed by a structure defined by the
 553 .\"O .B CIRCLEQ_HEAD
 554 .\"O macro.
 555 循環キューの先頭には
 556 .B CIRCLEQ_HEAD
 557 マクロで定義される構造体が置かれる。
 558 .\"O This structure contains a pair of pointers,
 559 .\"O one to the first element in the circular queue and the other to the
 560 .\"O last element in the circular queue.
 561 この構造体は 1 組のポインタを含んでいる。
 562 1 つは循環キューの最初の要素へのポインタであり、
 563 もう 1 つは循環キューの最後の要素へのポインタである。
 564 .\"O The elements are doubly linked so that an arbitrary element can be
 565 .\"O removed without traversing the queue.
 566 要素は 2 重にリンクされており、
 567 任意の要素はキューを辿らずに削除できる。
 568 .\"O New elements can be added to the queue after an existing element,
 569 .\"O before an existing element, at the head of the queue, or at the end
 570 .\"O of the queue.
 571 新しい要素は、既存の要素の後または前、またはキューの先頭または末尾に追加できる。
 572 A
 573 .\"O .B CIRCLEQ_HEAD
 574 .\"O structure is declared as follows:
 575 .B CIRCLEQ_HEAD
 576 構造体は以下のように定義されている:
 577 .in +4n
 578 .nf
 579
 580 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
 581 .fi
 582 .in
 583 .PP
 584 .\"O where
 585 .\"O .IR "HEADNAME"
 586 .\"O is the name of the structure to be defined, and
 587 .\"O .IR "TYPE"
 588 .\"O is the type of the elements to be linked into the circular queue.
 589 ここで
 590 .IR "HEADNAME"
 591 は定義される構造体の名前であり、
 592 .IR "TYPE"
 593 は循環キュー内でリンクされる要素の型である。
 594 .\"O A pointer to the head of the circular queue can later be declared as:
 595 循環キューの先頭へのポインタは、その後で次のように宣言される:
 596 .in +4n
 597 .nf
 598
 599 struct HEADNAME *headp;
 600 .fi
 601 .in
 602 .PP
 603 .\"O (The names
 604 .\"O .IR "head"
 605 .\"O and
 606 .\"O .IR "headp"
 607 .\"O are user selectable.)
 608 (名前
 609 .I head
 610 と
 611 .I headp
 612 はユーザが選択できる。)
 613 .PP
 614 .\"O The macro
 615 .\"O .B CIRCLEQ_ENTRY
 616 .\"O declares a structure that connects the elements in
 617 .\"O the circular queue.
 618 マクロ
 619 .B CIRCLEQ_ENTRY
 620 は循環キューの要素を接続する構造体を宣言する。
 621 .PP
 622 .\"O The macro
 623 .\"O .B CIRCLEQ_INIT
 624 .\"O initializes the circular queue referenced by
 625 .\"O .IR head .
 626 マクロ
 627 .B CIRCLEQ_INIT
 628 は
 629 .I head
 630 で参照される循環キューを初期化する。
 631 .PP
 632 .\"O The macro
 633 .\"O .B CIRCLEQ_INSERT_HEAD
 634 .\"O inserts the new element
 635 .\"O .I elm
 636 .\"O at the head of the circular queue.
 637 マクロ
 638 .B CIRCLEQ_INSERT_HEAD
 639 は新たな要素
 640 .I elm
 641 を循環キューの先頭に挿入する。
 642 .PP
 643 .\"O The macro
 644 .\"O .B CIRCLEQ_INSERT_TAIL
 645 .\"O inserts the new element
 646 .\"O .I elm
 647 .\"O at the end of the circular queue.
 648 マクロ
 649 .B CIRCLEQ_INSERT_TAIL
 650 は新たな要素
 651 .I elm
 652 を循環キューの末尾に挿入する。
 653 .PP
 654 .\"O The macro
 655 .\"O .B CIRCLEQ_INSERT_AFTER
 656 .\"O inserts the new element
 657 .\"O .I elm
 658 .\"O after the element
 659 .\"O .IR listelm .
 660 マクロ
 661 .B CIRCLEQ_INSERT_AFTER
 662 は新たな要素
 663 .I elm
 664 を要素
 665 .I listelm
 666 の後に挿入する。
 667 .PP
 668 .\"O The macro
 669 .\"O .B CIRCLEQ_INSERT_BEFORE
 670 .\"O inserts the new element
 671 .\"O .I elm
 672 .\"O before the element
 673 .\"O .IR listelm .
 674 マクロ
 675 .B CIRCLEQ_INSERT_AFTER
 676 は新たな要素
 677 .I elm
 678 を要素
 679 .I listelm
 680 の前に挿入する。
 681 .PP
 682 .\"O The macro
 683 .\"O .B CIRCLEQ_REMOVE
 684 .\"O removes the element
 685 .\"O .I elm
 686 .\"O from the circular queue.
 687 マクロ
 688 .B CIRCLEQ_REMOVE
 689 は要素
 690 .I elm
 691 を循環キューから削除する。
 692 .\"O .SS Circular Queue Example
 693 .SS 循環キューの例
 694 .nf
 695
 696 CIRCLEQ_HEAD(circleq, entry) head;
 697 .\"O struct circleq *headp;                  /* Circular queue head. */
 698 struct circleq *headp;                  /* 循環キューの先頭。*/
 699 struct entry {
 700     ...
 701 .\"O    CIRCLEQ_ENTRY(entry) entries;        /* Circular queue. */
 702     CIRCLEQ_ENTRY(entry) entries;       /* 循環キュー。*/
 703     ...
 704 } *n1, *n2, *np;
 705
 706 .\"O CIRCLEQ_INIT(&head);                    /* Initialize the circular queue. */
 707 CIRCLEQ_INIT(&head);                    /* 循環キューを初期化する。*/
 708
 709 .\"O n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 710 n1 = malloc(sizeof(struct entry));      /* 先頭に挿入する。*/
 711 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
 712
 713 .\"O n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 714 n1 = malloc(sizeof(struct entry));      /* 末尾に挿入する。*/
 715 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
 716
 717 .\"O n2 = malloc(sizeof(struct entry));      /* Insert after. */
 718 n2 = malloc(sizeof(struct entry));      /* 後ろに挿入する。*/
 719 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
 720
 721 .\"O n2 = malloc(sizeof(struct entry));      /* Insert before. */
 722 n2 = malloc(sizeof(struct entry));      /* 前に挿入する。*/
 723 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
 724 .\"O                                         /* Forward traversal. */
 725                                         /* 順方向に辿る。*/
 726 for (np = head.cqh_first; np != (void *)&head; np = np\->entries.cqe_next)
 727     np\-> ...
 728 .\"O                                         /* Reverse traversal. */
 729                                         /* 逆方向に辿る。*/
 730 for (np = head.cqh_last; np != (void *)&head; np = np\->entries.cqe_prev)
 731     np\-> ...
 732 .\"O                                         /* Delete. */
 733                                         /* 削除する。*/
 734 while (head.cqh_first != (void *)&head)
 735     CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
 736 .fi
 737 .\"O .SH "CONFORMING TO"
 738 .SH 準拠
 739 .\"O Not in POSIX.1-2001.
 740 .\"O Present on the BSDs.
 741 .\"O The
 742 .\"O queue functions first appeared in
 743 .\"O 4.4BSD.
 744 POSIX.1-2001 にはない。
 745 BSD 系に存在する。
 746 queue 関数は 4.4BSD で初めて登場した。