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 backwards, 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 ¤Ç½é¤á¤ÆÅÐ¾ì¤·¤¿¡£