path: root/ja_JP.eucJP/man/man3/queue.3

.\" 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
.\"	%Id: queue.3,v 1.13 1998/06/06 05:50:50 jkoshy Exp %
.\"
.\" $FreeBSD$
.Dd January 24, 1994
.Dt QUEUE 3
.Os BSD 4
.Sh 名称
.Nm SLIST_EMPTY ,
.Nm SLIST_ENTRY ,
.Nm SLIST_FIRST ,
.Nm SLIST_HEAD ,
.Nm SLIST_INIT ,
.Nm SLIST_INSERT_AFTER ,
.Nm SLIST_INSERT_HEAD ,
.Nm SLIST_NEXT ,
.Nm SLIST_REMOVE_HEAD ,
.Nm SLIST_REMOVE ,
.Nm STAILQ_ENTRY ,
.Nm STAILQ_HEAD ,
.Nm STAILQ_INIT ,
.Nm STAILQ_INSERT_AFTER ,
.Nm STAILQ_INSERT_HEAD ,
.Nm STAILQ_INSERT_TAIL ,
.Nm STAILQ_REMOVE_HEAD ,
.Nm STAILQ_REMOVE ,
.Nm LIST_ENTRY ,
.Nm LIST_HEAD ,
.Nm LIST_INIT ,
.Nm LIST_INSERT_AFTER ,
.Nm LIST_INSERT_BEFORE ,
.Nm LIST_INSERT_HEAD ,
.Nm LIST_REMOVE ,
.Nm TAILQ_EMPTY ,
.Nm TAILQ_ENTRY ,
.Nm TAILQ_FIRST ,
.Nm TAILQ_HEAD ,
.Nm TAILQ_INIT ,
.Nm TAILQ_INSERT_AFTER ,
.Nm TAILQ_INSERT_BEFORE ,
.Nm TAILQ_INSERT_HEAD ,
.Nm TAILQ_INSERT_TAIL ,
.Nm TAILQ_LAST ,
.Nm TAILQ_NEXT ,
.Nm TAILQ_REMOVE ,
.Nm CIRCLEQ_ENTRY ,
.Nm CIRCLEQ_HEAD ,
.Nm CIRCLEQ_INIT ,
.Nm CIRCLEQ_INSERT_AFTER ,
.Nm CIRCLEQ_INSERT_BEFORE ,
.Nm CIRCLEQ_INSERT_HEAD ,
.Nm CIRCLEQ_INSERT_TAIL ,
.Nm CIRCLEQ_REMOVE
.Nd 単一リンクリスト、単一リンクテールキュー、リスト、テールキュー、循
環キューのシステム  
.Sh 書式
.Fd #include <sys/queue.h>
.\"
.Fn SLIST_EMPTY "SLIST_HEAD *head"
.Fn SLIST_ENTRY "TYPE"
.Fn SLIST_FIRST "SLIST_HEAD *head"
.Fn SLIST_HEAD "HEADNAME" "TYPE"
.Fn SLIST_INIT "SLIST_HEAD *head"
.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
.\"
.Fn STAILQ_ENTRY "TYPE"
.Fn STAILQ_HEAD "HEADNAME" "TYPE"
.Fn STAILQ_INIT "STAILQ_HEAD *head"
.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
.\"
.Fn LIST_ENTRY "TYPE"
.Fn LIST_HEAD "HEADNAME" "TYPE"
.Fn LIST_INIT "LIST_HEAD *head"
.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
.\"
.Fn TAILQ_EMPTY "TAILQ_HEAD *head"
.Fn TAILQ_ENTRY "TYPE"
.Fn TAILQ_FIRST "TAILQ_HEAD *head"
.Fn TAILQ_HEAD "HEADNAME" "TYPE"
.Fn TAILQ_INIT "TAILQ_HEAD *head"
.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_LAST "TAILQ_HEAD *head"
.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.\"
.Fn CIRCLEQ_ENTRY "TYPE"
.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
.Sh 解説
このマクロは、単一リンクリスト、単一リンクテールキュー、リスト、テール
キュー、循環キューという、5 種類のデータ構造を定義してそこで動作します。
このすべてのデータ構造では、以下の機能がサポートされています。 
.Bl -enum -compact -offset indent
.It
リストの最初に新しいエントリを挿入する。
.It
リストに存在する任意のエレメントの後ろに新しいエントリを挿入する。
.It
リストの最初からエントリを O(1) 削除する。
.It
リストの任意のエントリを O(n) 削除する。
.It
リストでトラバースを転送する。
.El
.Pp
単一リンクリストは、5 つのデータ構造の中で最も単純で、上の 5つの機能し
かサポートしません。データセットが大きく、削除がほとんどないアプリケー
ション、または LIFO キューの実現に最適です。
.Pp
単一リンクテールキューには以下の機能もあります。
.Bl -enum -compact -offset indent
.It
リストの最後にエントリを追加する。
.El
しかし以下に注意してください。
.Bl -enum -compact -offset indent
.It
リストの挿入では、リストのヘッドを必ず指定する必要がある。
.It
各ヘッドエントリでは、1つではなく 2つのポインタが必要。
.It
単一リンクリストより、コードサイズは約 15% 大きく、処理時間は約 20% 長
い。
.El
.Pp
単一リンクテールキューは、データセットが大きく、削除がほとんどない
アプリケーション、または FIFO キューの実現に最適です。
.Pp
二重リンクタイプのすべてのデータ構造(リスト、テールキュー、循環キュー)
には以下の機能もあります。
.Bl -enum -compact -offset indent
.It 
リストに存在する任意のエレメントの前に新しいエントリを挿入する。
.It
リストの任意のエントリを O(1) 削除する。
.El
しかし以下に注意してください。
.Bl -enum -compact -offset indent
.It
各エレメントには、1つではなく 2つのポインタが必要。
.It
単一リンクデータ構造より、コードサイズと実行時間(削除は除く)が約 2倍に
なる。
.El 
.Pp
リンクリストは、二重リンクデータ構造の中で最も単純で、単一リンクリスト
の機能に加えて上の機能しかサポートしません。
.Pp
テールキューには以下の機能もあります。
.Bl -enum -compact -offset indent
.It
リストの最後にエントリを追加する。
.El
しかし以下に注意してください。
.Bl -enum -compact -offset indent
.It
リストの挿入と削除では、リストのヘッドを必ず指定する必要がある。
.It 
各ヘッドエントリでは、1つではなく 2つのポインタが必要。
.It
単一リンクリストより、コードサイズは約 15%大きく、処理時間は約 20%長い。
.El
.Pp
循環キューには以下の機能もあります。
.Bl -enum -compact -offset indent
.It
リストの最後にエントリを追加する。
.It
テールからヘッドへ逆順で横断する。
.El
しかし以下に注意してください。
.Bl -enum -compact -offset indent
.It
リストの挿入と削除では、リストのヘッドを必ず指定する必要がある。
.It
各ヘッドエントリでは、1つではなく 2つのポインタが必要。
.It
トラバースの終了条件が複雑。
.It
リストより、コードサイズは約 40%大きく、処理時間は約 45%長い。
.El
.Pp
マクロ定義では、
.Fa TYPE
はユーザが定義した構造体の名前です。この構造体には、
.Fa NAME
という名前が付いた、
.Li SLIST_ENTRY
か
.Li STAILQ_ENTRY ,
.Li LIST_ENTRY ,
.Li TAILQ_ENTRY ,
.Li CIRCLEQ_ENTRY
というタイプのフィールドを含める必要があります。引数
.Fa HEADNAME
は、
.Li SLIST_HEAD
マクロか
.Li STAILQ_HEAD
マクロ、
.Li LIST_HEAD
マクロ、
.Li TAILQ_HEAD
マクロ、
.Li CIRCLEQ_HEAD
マクロで宣言する必要がある、ユーザが定義した構造体の名前です。このマク
ロの使用法については、以下の使用例を参照してください。
.Sh 単一リンクリスト
単一リンクリストの最初には、
.Nm SLIST_HEAD
マクロが定義する構造体が付きます。この構造体には、リストの最初のエレメ
ントを指す1 つのポインタが含まれます。エレメントは、任意のエレメントの 
O(n) 削除を犠牲にして、最低スペースとポインタ操作オーバヘッドに単一リ
ンクされます。新しいエレメントは、既存エレメントの後ろかリストの最初で
リストに追加できます。 
.Fa SLIST_HEAD
構造体は、以下のように宣言されます。
.Bd -literal -offset indent
SLIST_HEAD(HEADNAME, TYPE) head;
.Ed
.Pp
.Li HEADNAME
は定義する構造体の名前で、
.Li TYPE
はリストにリンクするエレメントのタイプです。リストのヘッドのポインタは、
後で以下のように宣言されます。 
.Bd -literal -offset indent
struct HEADNAME *headp;
.Ed
.Pp
(ユーザは、名前
.Li head
と
.Li headp
を選択できます。)
.Pp
マクロ
.Nm SLIST_ENTRY
は、リストのエレメントを接続する構造体を宣言します。
.Pp
マクロ
.Nm SLIST_INIT
は、
.Fa head
が参照するリストを初期化します。
.Pp
マクロ
.Nm SLIST_INSERT_HEAD
は、新しいエレメント
.Fa elm
をリストの最初に挿入します。
.Pp
マクロ
.Nm SLIST_INSERT_AFTER
は、エレメント
.Fa listelm
の後に新しいエレメント
.Fa elm
を挿入します。
.Pp
マクロ
.Nm SLIST_REMOVE_HEAD
は、リストの最初からエレメント
.Fa elm
を削除します。能率を上げるには、リストの最初から削除するエレメントで、
一般的な 
.Fa SLIST_REMOVE
マクロの代わりにこのマクロを明示的に使用してください。
.Pp
マクロ
.Fa SLIST_REMOVE
は、リストからエレメント
.Fa elm
を削除します。
.Sh 単一リンクリストの使用例
.Bd -literal
SLIST_HEAD(slisthead, entry) head;
struct slisthead *headp;		/* Singly-linked List head. */
struct entry {
	...
	SLIST_ENTRY(entry) entries;	/* Singly-linked List. */
	...
} *n1, *n2, *n3, *np;

SLIST_INIT(&head);			/* Initialize the list. */

n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
SLIST_INSERT_HEAD(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Insert after. */
SLIST_INSERT_AFTER(n1, n2, entries);

SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
free(n2);

n3 = head.slh_first;
SLIST_REMOVE_HEAD(&head, entries);	/* Deletion. */
free(n3);

					/* Forward traversal. */
for (np = head.slh_first; np != NULL; np = np->entries.sle_next)
	np-> ...

while (head.slh_first != NULL) {	/* List Deletion. */
	n1 = head.slh_first;
	SLIST_REMOVE_HEAD(&head, entries);
	free(n1);
}
.Ed
.Sh 単一リンクテールキュー
単一リンクテールキューの最初には、
.Nm STAILQ_HEAD
マクロが定義する構造体が付きます。この構造体には、テールキューの最初の
エレメントを指すポインタとテールキューの最後のエレメントを指すポインタ
が含まれます。エレメントは、任意のエレメントの O(n) 削除を犠牲にして、
最低スペースとポインタ操作オーバヘッドに単一リンクされます。新しいエレ
メントは、既存エレメントの後ろ、またはテールキューの最初か最後に追加で
きます。 
.Fa STAILQ_HEAD
構造は、以下のように宣言されます。
.Bd -literal -offset indent
STAILQ_HEAD(HEADNAME, TYPE) head;
.Ed
.Pp
.Li HEADNAME
は定義する構造体の名前で、
.Li TYPE
はテールキューにリンクするエレメントのタイプです。テールキューのヘッド
のポインタは、後で以下のように宣言されます。
.Bd -literal -offset indent
struct HEADNAME *headp;
.Ed
.Pp
(ユーザは、名前
.Li head
と
.Li headp
を選択できます。)
.Pp
マクロ
.Nm STAILQ_ENTRY
は、テールキューのエレメントを接続する構造体を宣言します。
.Pp
マクロ
.Nm STAILQ_INIT
は、
.Fa head
が参照するテールキューを初期化します。
.Pp
マクロ
.Nm STAILQ_INSERT_HEAD
は、新しいエレメント
.Fa elm
をテールキューの最初に挿入します。
.Pp
マクロ
.Nm STAILQ_INSERT_TAIL
は、新しいエレメント
.Fa elm
をテールキューの最後に挿入します。
.Pp
マクロ
.Nm STAILQ_INSERT_AFTER
は、新しいエレメント
.Fa elm
をエレメント
.Fa listelm
の後ろに挿入します。
.Pp
マクロ
.Nm STAILQ_REMOVE_HEAD
は、テールキューの最初からエレメント
.Fa elm
を削除します。能率を上げるには、テールキューの最初から削除するエレメン
トで、一般的な
.Fa STAILQ_REMOVE
マクロの代わりにこのマクロを明示的に使用してください。
.Pp
マクロ
.Fa STAILQ_REMOVE
は、テールキューからエレメント
.Fa elm
を削除します。
.Sh 単一リンクテールキューの使用例
.Bd -literal
STAILQ_HEAD(stailhead, entry) head;
struct stailhead *headp;		/* Singly-linked tail queue head. */
struct entry {
	...
	STAILQ_ENTRY(entry) entries;	/* Tail queue. */
	...
} *n1, *n2, *n3, *np;

STAILQ_INIT(&head);			/* Initialize the queue. */

n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
STAILQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
STAILQ_INSERT_TAIL(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Insert after. */
STAILQ_INSERT_AFTER(&head, n1, n2, entries);

					/* Deletion. */
STAILQ_REMOVE(&head, n2, entry, entries);
free(n2);

					/* Deletion from the head */
n3 = head.stqh_first;
STAILQ_REMOVE_HEAD(&head, entries);
free(n3);

					/* Forward traversal. */
for (np = head.stqh_first; np != NULL; np = np->entries.stqe_next)
	np-> ...
					/* TailQ Deletion. */
while (head.stqh_first != NULL) {
	n1 = head.stqh_first;
	TAILQ_REMOVE_HEAD(&head, entries);
	free(n1);
}
					/* Faster TailQ Deletion. */
n1 = head.stqh_first;
while (n1 != NULL) {
	n2 = n1->entries.stqe_next;
	free(n1);
	n1 = n2;
}
STAILQ_INIT(&head);
.Ed
.Sh リスト
リストの最初には、
.Nm LIST_HEAD
マクロが定義する構造体が付きます。この構造体には、リストの最初のエレメ
ントを指す 1つのポインタが含まれます。エレメントは二重にリンクされてい
るので、リストを横断せずに任意のエレメントを削除できます。新しいエレメ
ントは、既存エレメントの前後かリストの最初でリストに追加できます。
.Fa LIST_HEAD
構造体は、以下のように宣言されます。
.Bd -literal -offset indent
LIST_HEAD(HEADNAME, TYPE) head;
.Ed
.Pp
.Fa HEADNAME
は定義する構造体の名前で、
.Fa TYPE
はリストにリンクするエレメントのタイプです。リストのヘッドのポインタは、
後で以下のように宣言されます。
.Bd -literal -offset indent 
struct HEADNAME *headp;
.Ed
.Pp
(ユーザは、名前
.Li head
と
.Li headp
を選択できます。)
.Pp
マクロ
.Nm LIST_ENTRY
は、リストのエレメントを接続する構造体を宣言します。
.Pp
マクロ
.Nm LIST_INIT
は、
.Fa head
が参照するリストを初期化します。
.Pp
マクロ
.Nm LIST_INSERT_HEAD
は、新しいエレメント
.Fa elm
をリストの最初に挿入します。
.Pp
マクロ
.Nm LIST_INSERT_AFTER
は、新しいエレメント
.Fa elm
をエレメント
.Fa listelm
の後ろに挿入します。
.Pp
マクロ
.Nm LIST_INSERT_BEFORE
は、新しいエレメント
.Fa elm
をエレメント
.Fa listelm
の前に挿入します。
.Pp
マクロ
.Nm LIST_REMOVE
は、エレメント
.Fa elm
をリストから削除します。
.Sh リストの使用例
.Bd -literal
LIST_HEAD(listhead, entry) head;
struct listhead *headp;		/* List head. */
struct entry {
	...
	LIST_ENTRY(entry) entries;	/* List. */
	...
} *n1, *n2, *n3, *np;

LIST_INIT(&head);			/* Initialize the list. */

n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
LIST_INSERT_HEAD(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Insert after. */
LIST_INSERT_AFTER(n1, n2, entries);

n3 = malloc(sizeof(struct entry));	/* Insert before. */
LIST_INSERT_BEFORE(n2, n3, entries);

LIST_REMOVE(n2, entries);		/* Deletion. */
free(n2);

					/* Forward traversal. */
for (np = head.lh_first; np != NULL; np = np->entries.le_next)
	np-> ...

while (head.lh_first != NULL) {		/* List Deletion. */
	n1 = head.lh_first;
	LIST_REMOVE(n1, entries);
	free(n1);
}

n1 = head.lh_first;			/* Faster List Delete. */
while (n1 != NULL) {
	n2 = n1->entries.le_next;
	free(n1);
	n1 = n2;
}
LIST_INIT(&head);

.Ed
.Sh テールキュー
テールキューの最初には、
.Nm TAILQ_HEAD
マクロが定義する構造体が付きます。この構造体には、テールキューの最初の
エレメントを指すポインタとテールキューの最後のエレメントを指すポインタ
が含まれます。エレメントは二重にリンクされているので、テールキューを横
断せずに任意のエレメントを削除できます。新しいエレメントは、既存エレメ
ントの前後、テールキューの最初と最後でテールキューに追加できます。
.Fa TAILQ_HEAD
構造体は、以下のように宣言されます。
.Bd -literal -offset indent
TAILQ_HEAD(HEADNAME, TYPE) head;
.Ed
.Pp
.Li HEADNAME
は定義する構造体の名前で、
.Li TYPE
はテールキューにリンクするエレメントのタイプです。テールキューのヘッド
のポインタは、後で以下のように宣言されます。
.Bd -literal -offset indent
struct HEADNAME *headp;
.Ed
.Pp
(ユーザは、名前
.Li head
と
.Li headp
を選択できます。)
.Pp
マクロ
.Nm TAILQ_EMPTY
は、テールキューにアイテムがない場合に真を戻します。
.Pp
マクロ
.Nm TAILQ_ENTRY
は、テールキューのエレメントを接続する構造体を宣言します。
.Pp
マクロ
.Nm TAILQ_FIRST
は、テールキューの最初のアイテムを戻します。テールキューにアイテムがな
い場合は NULL を戻します。
.Pp
マクロ
.Nm TAILQ_INIT
は、
.Fa head
が参照するテールキューを初期化します。
.Pp
マクロ
.Nm TAILQ_INSERT_HEAD
は、新しいエレメント
.Fa elm
をテールキューの最初に挿入します。
.Pp
マクロ
.Nm TAILQ_INSERT_TAIL
は、新しいエレメント
.Fa elm
をテールキューの最後に挿入します。
.Pp
マクロ
.Nm TAILQ_INSERT_AFTER
は、新しいエレメント
.Fa elm
をエレメント
.Fa listelm
の後ろに挿入します。
.Pp
マクロ
.Nm TAILQ_INSERT_BEFORE
は、新しいエレメント
.Fa elm
をエレメント
.Fa listelm
の前に挿入します。
.Pp
マクロ
.Nm TAILQ_LAST
は、テールキューの最後のアイテムを戻します。テールキューにアイテムがな
い場合の戻り値は不定です。 
.Pp
マクロ
.Nm TAILQ_NEXT
は、テールキューの次のアイテムを戻します。そのアイテムが最後の場合は 
NULL を戻します。 
.Pp
マクロ
.Nm TAILQ_REMOVE
は、エレメント
.Fa elm
をテールキューから削除します。
.Sh テールキューの使用例
.Bd -literal
TAILQ_HEAD(tailhead, entry) head;
struct tailhead *headp;		/* Tail queue head. */
struct entry {
	...
	TAILQ_ENTRY(entry) entries;	/* Tail queue. */
	...
} *n1, *n2, *n3, *np;

TAILQ_INIT(&head);			/* Initialize the queue. */

n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
TAILQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
TAILQ_INSERT_TAIL(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* Insert after. */
TAILQ_INSERT_AFTER(&head, n1, n2, entries);

n3 = malloc(sizeof(struct entry));	/* Insert before. */
TAILQ_INSERT_BEFORE(n2, n3, entries);

TAILQ_REMOVE(&head, n2, entries);	/* Deletion. */
free(n2);
					/* Forward traversal. */
for (np = TAILQ_FIRST(&head); np != NULL; np = TAILQ_NEXT(np, entries))
	np-> ...
					/* TailQ Deletion. */
while (!TAILQ_EMPTY(head)) {
	n1 = TAILQ_FIRST(&head);
	TAILQ_REMOVE(&head, head.tqh_first, entries);
	free(n1);
}
					/* Faster TailQ Deletion. */

n1 = TAILQ_FIRST(&head);
while (n1 != NULL) {
	n2 = TAILQ_NEXT(n1, entries);
	free(n1);
	n1 = n2;
}
TAILQ_INIT(&head);
.Ed
.Sh 循環キュー
循環キューの最初には、
.Nm CIRCLEQ_HEAD
マクロが定義する構造体が付きます。この構造体には、循環キューの最初のエ
レメントを指すポインタと循環キューの最後のエレメントを指すポインタが含
まれます。エレメントは二重にリンクされているので、キューを横断せずに任
意のエレメントを削除できます。新しいエレメントは、既存エレメントの前後、
またはキューの最初と最後でキューに追加できます。
.Fa CIRCLEQ_HEAD
構造は、以下のように宣言されます。
.Bd -literal -offset indent
CIRCLEQ_HEAD(HEADNAME, TYPE) head;
.Ed
.Pp
.Li HEADNAME
は定義する構造体の名前で、
.Li TYPE
は循環キューにリンクするエレメントのタイプです。循環キューのヘッドのポ
インタは、後で以下のように宣言されます。
.Bd -literal -offset indent
struct HEADNAME *headp;
.Ed
.Pp
(ユーザは、名前
.Li head
と
.Li headp
を選択できます。)
.Pp
マクロ
.Nm CIRCLEQ_ENTRY
は、循環キューのエレメントを接続する構造体を宣言します。
.Pp
マクロ
.Nm CIRCLEQ_INIT
は、
.Fa head
が参照する循環キューを初期化します。
.Pp
マクロ
.Nm CIRCLEQ_INSERT_HEAD
は、新しいエレメント
.Fa elm
を循環キューの最初に挿入します。
.Pp
マクロ
.Nm CIRCLEQ_INSERT_TAIL
は、新しいエレメント
.Fa elm
を循環キューの最後に挿入します。
.Pp
マクロ
.Nm CIRCLEQ_INSERT_AFTER
は、新しいエレメント
.Fa elm
をエレメント
.Fa listelm
の後ろに挿入します。
.Pp
マクロ
.Nm CIRCLEQ_INSERT_BEFORE
は、新しいエレメント
.Fa elm
をエレメント
.Fa listelm
の前に挿入します。
.Pp
マクロ
.Nm CIRCLEQ_REMOVE
は、エレメント
.Fa elm
を循環キューから削除します。
.Sh 循環キューの使用例
.Bd -literal
CIRCLEQ_HEAD(circleq, entry) head;
struct circleq *headp;			/* Circular queue head. */
struct entry {
	...
	CIRCLEQ_ENTRY(entry) entries;	/* Circular queue. */
	...
} *n1, *n2, *np;

CIRCLEQ_INIT(&head);			/* Initialize the circular queue. */

n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
CIRCLEQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
CIRCLEQ_INSERT_TAIL(&head, n1, entries);

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

n2 = malloc(sizeof(struct entry));	/* Insert before. */
CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);

CIRCLEQ_REMOVE(&head, n1, entries);	/* Deletion. */
free(n1);
					/* Forward traversal. */
for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
	np-> ...
					/* Reverse traversal. */
for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
	np-> ...
					/* CircleQ Deletion. */
while (head.cqh_first != (void *)&head) {
	n1 = head.cqh_first;
	CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
	free(n1);
}
					/* Faster CircleQ Deletion. */
n1 = head.cqh_first;
while (n1 != (void *)&head) {
	n2 = n1->entries.cqh_next;
	free(n1);
	n1 = n2;
}
CIRCLEQ_INIT(&head);
.Ed
.Sh 歴史
.Nm queue
関数は、
.Bx 4.4
に最初に登場しました。