.\" Copyright (c) 1993
.\"     The Regents of the University of California.  All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\" 3. All advertising materials mentioning features or use of this software
.\"    must display the following acknowledgement:
.\"     This product includes software developed by the University of
.\"     California, Berkeley and its contributors.
.\" 4. Neither the name of the University nor the names of its contributors
.\"    may be used to endorse or promote products derived from this software
.\"    without specific prior written permission.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
.\"     @(#)queue.3     8.2 (Berkeley) 1/24/94
.\"
.\" hch, 2002-03-25
.\" 2007-12-08, mtk, Converted from mdoc to man macros
.\"
.\" Japanese Version Copyright (c) 2004 Yuichi SATO
.\"         all rights reserved.
.\" Translated Thu Sep  2 04:41:11 JST 2004
.\"         by Yuichi SATO <ysato444@yahoo.co.jp>
.\"
.\"WORD:	circular queue	۴ĥ塼
.\"
.TH QUEUE 3 2007-12-28 "Linux" "Linux Programmer's Manual"
.SH ̾
LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, \
LIST_INSERT_HEAD, LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, \
TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, \
TAILQ_REMOVE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_INIT, \
CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, \
CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, \
CIRCLEQ_REMOVE \- ꥹȡơ (tail) 塼۴ĥ塼μ
.SH 
.nf
.B #include <sys/queue.h>

.BI "LIST_ENTRY(" TYPE );
.BI "LIST_HEAD(" HEADNAME ", " TYPE );
.BI "LIST_INIT(LIST_HEAD *" head );
.BI "LIST_INSERT_AFTER(LIST_ENTRY *" listelm ", "
.BI "                TYPE *" elm ", LIST_ENTRY " NAME );
.BI "LIST_INSERT_HEAD(LIST_HEAD *" head ", "
.BI "                TYPE *" elm ", LIST_ENTRY " NAME );
.BI "LIST_REMOVE(TYPE *" elm ", LIST_ENTRY " NAME );

.BI "TAILQ_ENTRY(" TYPE );
.BI "TAILQ_HEAD("HEADNAME ", " TYPE );
.BI "TAILQ_INIT(TAILQ_HEAD *" head );
.BI "TAILQ_INSERT_AFTER(TAILQ_HEAD *" head ", TYPE *" listelm ", "
.BI "                TYPE *" elm ", TAILQ_ENTRY " NAME );
.BI "TAILQ_INSERT_HEAD(TAILQ_HEAD *" head ", "
.BI "                TYPE *" elm ", TAILQ_ENTRY " NAME );
.BI "TAILQ_INSERT_TAIL(TAILQ_HEAD *" head ", "
.BI "                TYPE *" elm ", TAILQ_ENTRY " NAME );
.BI "TAILQ_REMOVE(TAILQ_HEAD *" head ", TYPE *" elm ", TAILQ_ENTRY " NAME );

.BI CIRCLEQ_ENTRY( TYPE );
.BI "CIRCLEQ_HEAD(" HEADNAME ", " TYPE );
.BI "CIRCLEQ_INIT(CIRCLEQ_HEAD *" head );
.BI "CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *" head ", TYPE *" listelm ", "
.BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
.BI "CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *" head ", TYPE *" listelm ", "
.BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
.BI "CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *" head ", "
.BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
.BI "CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *" head ", "
.BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
.BI "CIRCLEQ_REMOVE(CIRCLEQ_HEAD *" head ", "
.BI "                TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
.fi
.SH 
Υޥϡ 3 ĤΥǡ¤:
ꥹȡơ륭塼۴ĥ塼
3 ĤΥǡ¤٤ƤˤưʲεǽݡȤƤ:
.sp
.RS 4
.PD 0
.IP * 4
ʥȥꥹȤƬ롣
.IP *
ʥȥꥹȤΤɤǤ롣
.IP *
ꥹȤǤդΥȥ롣
.IP *
ꥹȤé롣
.PD
.RE
.PP
ꥹȤ 3 ĤΥǡ¤ǺǤñǤꡢ
嵭εǽΤߤ򥵥ݡȤ롣

ơ륭塼ϰʲεǽɲä:
.RS 4
.IP * 4
ȥꥹȤκǸɲäǤ롣
.RE
.PP
:
.sp
.RS 4
.PD 0
.IP 1. 4
ƤΥꥹȺˤơꥹȤƬꤷʤФʤʤ
.IP 2.
Ƭȥ 1 ĤǤϤʤ 2 ĤΥݥ󥿤ɬפȤ롣
.IP 3.
ꥹȤ٤ơɥ 15% 礭ʤꡢ 20% ٤ʤ롣
.PD
.RE
.PP
۴ĥ塼ϰʲεǽɲä:
.sp
.RS 4
.PD 0
.IP * 4
ȥꥹȤκǸɲäǤ롣
.IP *
ȥ¾ΥȥɲäǤ롣
.IP *
Ƭé뤳ȤǤ롣
.PD
.RE
.PP
:
.sp
.RS 4
.PD 0
.IP 1. 4
ƤΥꥹȺˤơꥹȤƬꤷʤФʤʤ
.IP 2.
Ƭȥ 1 ĤǤϤʤ 2 ĤΥݥ󥿤ɬפȤ롣
.IP 3.
éݤνλ郎ʣǤ롣
.IP 4.
ꥹȤ٤ơɥ 40% 礭ʤꡢ 45% ٤ʤ롣
.PD
.RE
.PP
ޥˤ
.I TYPE
ϥ桼¤Τ̾Ǥꡢ
.BR LIST_ENTRY ,
.BR TAILQ_ENTRY ,
.BR CIRCLEQ_ENTRY
β줫Υեɤ
ꤵ줿
.I NAME
ޤޤʤФʤʤ

.I HEADNAME
ϥ桼¤Τ̾Ǥꡢ
ޥ
.BR LIST_HEAD ,
.BR TAILQ_HEAD ,
.BR CIRCLEQ_HEAD
ѤʤФʤʤ
ΥޥɤΤ褦˻Ȥ뤫ˤĤƤιʤϡ
ʲ򻲾Ȥ뤳ȡ
.SS ꥹ
ꥹȤƬˤϡ
LIST_HEAD
ޥ빽¤Τ֤롣
ι¤ΤϥꥹȤκǽǤؤΥݥ󥿤 1 Ĵޤࡣ
Ǥ 2 Ť˥󥯤Ƥꡢ
ǤդǤϥꥹȤé餺˺Ǥ롣
Ǥϴ¸ǤθޤϥꥹȤƬɲäǤ롣
.B LIST_HEAD
¤ΤϰʲΤ褦Ƥ:
.in +4n
.nf

LIST_HEAD(HEADNAME, TYPE) head;
.fi
.in
.PP

.I HEADNAME
빽¤Τ̾Ǥꡢ
.I TYPE
ϥǥ󥯤ǤηǤ롣
ꥹȤƬؤΥݥ󥿤ϡθǼΤ褦:
.in +4n
.nf

struct HEADNAME *headp;
.fi
.in
.PP
(̾
.IR "head"

.IR "headp"
ϥ桼Ǥ롣)
.PP
ޥ
.B LIST_ENTRY
ϥꥹȤǤ³빽¤Τ롣
.PP
ޥ
.B LIST_INIT

.I head
ǻȤꥹȤ롣
.PP
ޥ
.B LIST_INSERT_HEAD
Ͽ
.I elm
ꥹȤƬ롣
.PP
ޥ
.B LIST_INSERT_AFTER
Ͽ
.I elm

.I listelm
θ롣
.PP
ޥ
.B LIST_REMOVE

.I elm
ꥹȤ롣
.SS ꥹȤ
.nf

LIST_HEAD(listhead, entry) head;
struct listhead *headp;                 /* ꥹȤƬ*/
struct entry {
    ...
    LIST_ENTRY(entry) entries;          /* ꥹȡ */
    ...
} *n1, *n2, *np;

LIST_INIT(&head);                       /* ꥹȤ롣*/

n1 = malloc(sizeof(struct entry));      /* Ƭ롣*/
LIST_INSERT_HEAD(&head, n1, entries);

n2 = malloc(sizeof(struct entry));      /* 롣*/
LIST_INSERT_AFTER(n1, n2, entries);
                                        /* é롣*/
for (np = head.lh_first; np != NULL; np = np\->entries.le_next)
    np\-> ...

while (head.lh_first != NULL)           /* 롣*/
    LIST_REMOVE(head.lh_first, entries);
.fi
.SS ơ륭塼
ơ륭塼Ƭˤ
.B TAILQ_HEAD
ޥ빽¤Τ֤롣
ι¤Τ 1 ȤΥݥ󥿤ޤǤ롣
1 Ĥϥơ륭塼κǽǤؤΥݥ󥿤Ǥꡢ
⤦ 1 Ĥϥơ륭塼κǸǤؤΥݥ󥿤Ǥ롣
Ǥ 2 Ť˥󥯤Ƥꡢ
ǤդǤϥơ륭塼é餺˺Ǥ롣
Ǥϴ¸Ǥθޤϥơ륭塼ƬޤɲäǤ롣
.B TAILQ_HEAD
¤ΤϰʲΤ褦Ƥ:
.in +4n
.nf

TAILQ_HEAD(HEADNAME, TYPE) head;
.fi
.in
.PP

.Li HEADNAME
빽¤Τ̾Ǥꡢ
.Li TYPE
ϥơ륭塼ǥ󥯤ǤηǤ롣
ơ륭塼ƬؤΥݥ󥿤ϡθǼΤ褦:
.in +4n
.nf

struct HEADNAME *headp;
.fi
.in
.PP
(̾
.IR "head"

.IR "headp"
ϥ桼Ǥ롣)
.PP
ޥ
.B TAILQ_ENTRY
ϥơ륭塼Ǥ³빽¤Τ롣
.PP
ޥ
.B TAILQ_INIT

.I head
ǻȤơ륭塼롣
.PP
ޥ
.B TAILQ_INSERT_HEAD
Ͽ
.I elm
ơ륭塼Ƭ롣
.PP
ޥ
.B TAILQ_INSERT_TAIL
Ͽ
.I elm
ơ륭塼롣
.PP
ޥ
.B TAILQ_INSERT_AFTER
Ͽ
.I elm

.Fa listelm
θ롣
.PP
ޥ
.B TAILQ_REMOVE

.I elm
ơ륭塼롣
.SS ơ륭塼
.nf

TAILQ_HEAD(tailhead, entry) head;
struct tailhead *headp;                 /* ơ륭塼Ƭ*/
struct entry {
    ...
    TAILQ_ENTRY(entry) entries;         /* ơ륭塼*/
    ...
} *n1, *n2, *np;

TAILQ_INIT(&head);                      /* 塼롣*/

n1 = malloc(sizeof(struct entry));      /* Ƭ롣*/
TAILQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));      /* 롣*/
TAILQ_INSERT_TAIL(&head, n1, entries);

n2 = malloc(sizeof(struct entry));      /* 롣*/
TAILQ_INSERT_AFTER(&head, n1, n2, entries);
                                        /* é롣*/
for (np = head.tqh_first; np != NULL; np = np\->entries.tqe_next)
    np\-> ...
                                        /* 롣*/
while (head.tqh_first != NULL)
    TAILQ_REMOVE(&head, head.tqh_first, entries);
.fi
.SS ۴ĥ塼
۴ĥ塼Ƭˤ
.B CIRCLEQ_HEAD
ޥ빽¤Τ֤롣
ι¤Τ 1 ȤΥݥ󥿤ޤǤ롣
1 ĤϽ۴ĥ塼κǽǤؤΥݥ󥿤Ǥꡢ
⤦ 1 ĤϽ۴ĥ塼κǸǤؤΥݥ󥿤Ǥ롣
Ǥ 2 Ť˥󥯤Ƥꡢ
ǤդǤϥ塼é餺˺Ǥ롣
Ǥϡ¸Ǥθޤޤϥ塼ƬޤɲäǤ롣
A
.B CIRCLEQ_HEAD
¤ΤϰʲΤ褦Ƥ:
.in +4n
.nf

CIRCLEQ_HEAD(HEADNAME, TYPE) head;
.fi
.in
.PP

.IR "HEADNAME"
빽¤Τ̾Ǥꡢ
.IR "TYPE"
Ͻ۴ĥ塼ǥ󥯤ǤηǤ롣
۴ĥ塼ƬؤΥݥ󥿤ϡθǼΤ褦:
.in +4n
.nf

struct HEADNAME *headp;
.fi
.in
.PP
(̾
.I head

.I headp
ϥ桼Ǥ롣)
.PP
ޥ
.B CIRCLEQ_ENTRY
Ͻ۴ĥ塼Ǥ³빽¤Τ롣
.PP
ޥ
.B CIRCLEQ_INIT

.I head
ǻȤ۴ĥ塼롣
.PP
ޥ
.B CIRCLEQ_INSERT_HEAD
Ͽ
.I elm
۴ĥ塼Ƭ롣
.PP
ޥ
.B CIRCLEQ_INSERT_TAIL
Ͽ
.I elm
۴ĥ塼롣
.PP
ޥ
.B CIRCLEQ_INSERT_AFTER
Ͽ
.I elm

.I listelm
θ롣
.PP
ޥ
.B CIRCLEQ_INSERT_AFTER
Ͽ
.I elm

.I listelm
롣
.PP
ޥ
.B CIRCLEQ_REMOVE

.I elm
۴ĥ塼롣
.SS ۴ĥ塼
.nf

CIRCLEQ_HEAD(circleq, entry) head;
struct circleq *headp;                  /* ۴ĥ塼Ƭ*/
struct entry {
    ...
    CIRCLEQ_ENTRY(entry) entries;       /* ۴ĥ塼*/
    ...
} *n1, *n2, *np;

CIRCLEQ_INIT(&head);                    /* ۴ĥ塼롣*/

n1 = malloc(sizeof(struct entry));      /* Ƭ롣*/
CIRCLEQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));      /* 롣*/
CIRCLEQ_INSERT_TAIL(&head, n1, entries);

n2 = malloc(sizeof(struct entry));      /* 롣*/
CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);

n2 = malloc(sizeof(struct entry));      /* 롣*/
CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
                                        /* é롣*/
for (np = head.cqh_first; np != (void *)&head; np = np\->entries.cqe_next)
    np\-> ...
                                        /* é롣*/
for (np = head.cqh_last; np != (void *)&head; np = np\->entries.cqe_prev)
    np\-> ...
                                        /* 롣*/
while (head.cqh_first != (void *)&head)
    CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
.fi
.SH 
POSIX.1-2001 ˤϤʤ
BSD Ϥ¸ߤ롣
queue ؿ 4.4BSD ǽо줷