.\" 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 .\" %FreeBSD: src/share/man/man3/queue.3,v 1.15.2.7 2001/12/18 10:09:02 ru Exp % .\" $FreeBSD$ .\" .Dd January 24, 1994 .Dt QUEUE 3 .Os .Sh 名称 .Nm SLIST_EMPTY , .Nm SLIST_ENTRY , .Nm SLIST_FIRST , .Nm SLIST_FOREACH , .Nm SLIST_HEAD , .Nm SLIST_HEAD_INITIALIZER , .Nm SLIST_INIT , .Nm SLIST_INSERT_AFTER , .Nm SLIST_INSERT_HEAD , .Nm SLIST_NEXT , .Nm SLIST_REMOVE_HEAD , .Nm SLIST_REMOVE , .Nm STAILQ_EMPTY , .Nm STAILQ_ENTRY , .Nm STAILQ_FIRST , .Nm STAILQ_FOREACH , .Nm STAILQ_HEAD , .Nm STAILQ_HEAD_INITIALIZER , .Nm STAILQ_INIT , .Nm STAILQ_INSERT_AFTER , .Nm STAILQ_INSERT_HEAD , .Nm STAILQ_INSERT_TAIL , .Nm STAILQ_LAST , .Nm STAILQ_NEXT , .Nm STAILQ_REMOVE_HEAD , .Nm STAILQ_REMOVE , .Nm LIST_EMPTY , .Nm LIST_ENTRY , .Nm LIST_FIRST , .Nm LIST_FOREACH , .Nm LIST_HEAD , .Nm LIST_HEAD_INITIALIZER , .Nm LIST_INIT , .Nm LIST_INSERT_AFTER , .Nm LIST_INSERT_BEFORE , .Nm LIST_INSERT_HEAD , .Nm LIST_NEXT , .Nm LIST_REMOVE , .Nm TAILQ_EMPTY , .Nm TAILQ_ENTRY , .Nm TAILQ_FIRST , .Nm TAILQ_FOREACH , .Nm TAILQ_FOREACH_REVERSE , .Nm TAILQ_HEAD , .Nm TAILQ_HEAD_INITIALIZER , .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_PREV , .Nm TAILQ_REMOVE , .Nm CIRCLEQ_EMPTY , .Nm CIRCLEQ_ENTRY , .Nm CIRCLEQ_FIRST , .Nm CIRCLEQ_FOREACH , .Nm CIRCLEQ_FOREACH_REVERSE , .Nm CIRCLEQ_HEAD , .Nm CIRCLEQ_HEAD_INITIALIZER , .Nm CIRCLEQ_INIT , .Nm CIRCLEQ_INSERT_AFTER , .Nm CIRCLEQ_INSERT_BEFORE , .Nm CIRCLEQ_INSERT_HEAD , .Nm CIRCLEQ_INSERT_TAIL , .Nm CIRCLE_LAST , .Nm CIRCLE_NEXT , .Nm CIRCLE_PREV , .Nm CIRCLEQ_REMOVE .Nd 単一リンクリスト、単一リンクテールキュー、リスト、テールキュー、 循環キューの実装 .Sh 書式 .In sys/queue.h .\" .Fn SLIST_EMPTY "SLIST_HEAD *head" .Fn SLIST_ENTRY "TYPE" .Fn SLIST_FIRST "SLIST_HEAD *head" .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" .Fn SLIST_HEAD "HEADNAME" "TYPE" .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" .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_EMPTY "STAILQ_HEAD *head" .Fn STAILQ_ENTRY "TYPE" .Fn STAILQ_FIRST "STAILQ_HEAD *head" .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" .Fn STAILQ_HEAD "HEADNAME" "TYPE" .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" .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_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME" .Fn STAILQ_NEXT "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_EMPTY "LIST_HEAD *head" .Fn LIST_ENTRY "TYPE" .Fn LIST_FIRST "LIST_HEAD *head" .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" .Fn LIST_HEAD "HEADNAME" "TYPE" .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" .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_NEXT "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_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_HEAD "HEADNAME" "TYPE" .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" .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" "HEADNAME" .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" .\" .Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head" .Fn CIRCLEQ_ENTRY "TYPE" .Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head" .Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" .Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" .Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" .Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head" .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_LAST "CIRCLEQ_HEAD *head" .Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME" .Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME" .Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" .Sh 解説 このマクロは、単一リンクリスト、単一リンクテールキュー、リスト、 テールキュー、循環キューという、5 種類のデータ構造を定義してそこで動作します。 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 リストの末尾にエントリを追加する。 .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 ここで .Fa HEADNAME は定義する構造体の名前で、 .Fa TYPE はリストにリンクする要素の型です。 リストのヘッドのポインタは、後で以下のように宣言できます。 .Bd -literal -offset indent struct HEADNAME *headp; .Ed .Pp (名前 .Li head と .Li headp は、ユーザが選べます。) .Pp マクロ .Nm SLIST_HEAD_INITIALIZER はリストの .Fa head を初期化します。 .Pp マクロ .Nm SLIST_EMPTY はリストに要素がない場合に真になります。 .Pp マクロ .Nm SLIST_ENTRY はリストの要素を接続する構造体を宣言します。 .Pp マクロ .Nm SLIST_FIRST はリストの先頭の要素を、リストが空なら NULL を返します。 .Pp マクロ .Nm SLIST_FOREACH は .Fa head で参照されるリストを、各要素を順に .Fa var に割り当てて順方向に走査します。 .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_NEXT はリストの次の要素を返します。 .Pp マクロ .Nm SLIST_REMOVE_HEAD はリストの先頭から要素 .Fa elm を削除します。 最適な効率を得るために、リストの先頭から要素を削除する場合には 一般的な .Fa SLIST_REMOVE マクロの代わりにこのマクロを明示的に使用すべきです。 .Pp マクロ .Nm SLIST_REMOVE はリストから要素 .Fa elm を削除します。 .Sh 単一リンクリストの使用例 .Bd -literal SLIST_HEAD(slisthead, entry) head = SLIST_HEAD_INITIALIZER(head); struct slisthead *headp; /* 単一リンクリストヘッド */ struct entry { ... SLIST_ENTRY(entry) entries; /* 単一リンクリスト */ ... } *n1, *n2, *n3, *np; SLIST_INIT(&head); /* リストを初期化 */ n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */ SLIST_INSERT_HEAD(&head, n1, entries); n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */ SLIST_INSERT_AFTER(n1, n2, entries); SLIST_REMOVE(&head, n2, entry, entries);/* 削除 */ free(n2); n3 = SLIST_FIRST(&head); SLIST_REMOVE_HEAD(&head, entries); /* 先頭から削除 */ free(n3); /* 順走査 */ SLIST_FOREACH(np, &head, entries) np-> ... while (!SLIST_EMPTY(&head)) { /* リストの削除 */ n1 = SLIST_FIRST(&head); SLIST_REMOVE_HEAD(&head, entries); free(n1); } .Ed .Sh 単一リンクテールキュー 単一リンクテールキューの最初には、 .Nm STAILQ_HEAD マクロで定義される構造体がつきます。 この構造体にはテールキューの先頭の要素を指すポインタと テールキューの末尾の要素を指すポインタの 2 つが含まれます。 要素は、任意の要素の 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_HEAD_INITIALIZER はテールキューの .Fa head を初期化します。 .Pp マクロ .Nm STAILQ_EMPTY はテールキューに要素がない場合に真になります。 .Pp マクロ .Nm STAILQ_ENTRY はテールキューの要素を接続する構造体を宣言します。 .Pp マクロ .Nm STAILQ_FIRST はテールキューの先頭の要素を、テールキューが空なら NULL を返します。 .Pp マクロ .Nm STAILQ_FOREACH は .Fa head で参照されるテールキューを、各要素を順に .Fa var に割り当てて順方向に走査します。 .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_LAST はテールキューの末尾の要素を返します。 テールキューが空なら、戻り値は未定義です。 .Pp マクロ .Nm STAILQ_NEXT はテールキューの次の要素を、この要素が末尾なら NULL を返します。 .Pp マクロ .Nm STAILQ_REMOVE_HEAD はテールキューの先頭から要素 を削除します。 最適な効率を得るために、テールキューの先頭から要素を削除する場合には 一般的な .Fa STAILQ_REMOVE マクロよりもこのマクロを明示的に使用すべきです。 .Pp マクロ .Nm STAILQ_REMOVE はテールキューから要素 .Fa elm を削除します。 .Sh 単一リンクテールキューの使用例 .Bd -literal STAILQ_HEAD(stailhead, entry) head = STAILQ_HEAD_INITIALIZER(head); struct stailhead *headp; /* 単一リンクテールキューヘッド */ struct entry { ... STAILQ_ENTRY(entry) entries; /* テールキュー */ ... } *n1, *n2, *n3, *np; STAILQ_INIT(&head); /* キューを初期化 */ n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */ STAILQ_INSERT_HEAD(&head, n1, entries); n1 = malloc(sizeof(struct entry)); /* 末尾に挿入 */ STAILQ_INSERT_TAIL(&head, n1, entries); n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */ STAILQ_INSERT_AFTER(&head, n1, n2, entries); /* 削除 */ STAILQ_REMOVE(&head, n2, entry, entries); free(n2); /* 先頭から削除 */ n3 = STAILQ_FIRST(&head); STAILQ_REMOVE_HEAD(&head, entries); free(n3); /* 順走査 */ STAILQ_FOREACH(np, &head, entries) np-> ... /* テールキューの削除 */ while (!STAILQ_EMPTY(&head)) { n1 = STAILQ_FIRST(&head); STAILQ_REMOVE_HEAD(&head, entries); free(n1); } /* テールキューの高速な削除 */ n1 = STAILQ_FIRST(&head); while (n1 != NULL) { n2 = STAILQ_NEXT(n1, entries); 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_HEAD_INITIALIZER はリストの .Fa head を初期化します。 .Pp マクロ .Nm LIST_EMPTY はリストに要素がない場合に真になります。 .Pp マクロ .Nm LIST_ENTRY はリストの要素を接続する構造体を宣言します。 .Pp マクロ .Nm LIST_FIRST はリストの最初の要素を、リストが空なら NULL を返します。 .Pp マクロ .Nm LIST_FOREACH は .Fa head で参照されるリストを、各要素を順に .Fa var に割り当てて順方向に走査します。 .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_NEXT はリストの次の要素を、この要素が末尾なら NULL を返します。 .Pp マクロ .Nm LIST_REMOVE は要素 .Fa elm をリストから削除します。 .Sh リストの使用例 .Bd -literal LIST_HEAD(listhead, entry) head = LIST_HEAD_INITIALIZER(head); struct listhead *headp; /* リストヘッド */ struct entry { ... LIST_ENTRY(entry) entries; /* リスト */ ... } *n1, *n2, *n3, *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); n3 = malloc(sizeof(struct entry)); /* 前に挿入 */ LIST_INSERT_BEFORE(n2, n3, entries); LIST_REMOVE(n2, entries); /* 削除 */ free(n2); /* 順走査 */ LIST_FOREACH(np, &head, entries) np-> ... while (!LIST_EMPTY(&head)) { /* リストの削除 */ n1 = LIST_FIRST(&head); LIST_REMOVE(n1, entries); free(n1); } n1 = LIST_FIRST(&head); /* リストの高速な削除 */ while (n1 != NULL) { n2 = LIST_NEXT(n1, entries); free(n1); n1 = n2; } LIST_INIT(&head); .Ed .Sh テールキュー テールキューの最初には、 .Nm TAILQ_HEAD マクロで定義される構造体が付きます。 この構造体には、テールキューの最初の要素を指すポインタと テールキューの先頭の要素を指すポインタの 2 つが含まれます。 要素は二重にリンクされているので、テールキューを走査せずに 任意の要素を削除できます。 新しい要素は、既存の要素の前、既存の要素の後、テールキューの先頭、 テールキューの末尾でテールキューに追加できます。 .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_HEAD_INITIALIZER はテールキューの .Fa head を初期化します。 .Pp マクロ .Nm TAILQ_EMPTY はテールキューに要素がない場合に真になります。 .Pp マクロ .Nm TAILQ_ENTRY はテールキューの要素を接続する構造体を宣言します。 .Pp マクロ .Nm TAILQ_FIRST はテールキューの最初の要素を、テールキューが空なら NULL を返します。 .Pp マクロ .Nm TAILQ_FOREACH は .Fa head で参照されるテールキューを、各要素を順に .Fa var に割り当てて順方向に走査します。 .Pp マクロ .Nm TAILQ_FOREACH_REVERSE は .Fa head で参照されるテールキューを、各要素を順に .Fa var に割り当てて逆方向に走査します。 .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_PREV はテールキューの前の要素を、その要素が先頭の場合は NULL を返します。 .Pp マクロ .Nm TAILQ_REMOVE は要素 .Fa elm をテールキューから削除します。 .Sh テールキューの使用例 .Bd -literal TAILQ_HEAD(tailhead, entry) head = TAILQ_HEAD_INITIALIZER(head); struct tailhead *headp; /* テールキューヘッド */ struct entry { ... TAILQ_ENTRY(entry) entries; /* テールキュー */ ... } *n1, *n2, *n3, *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); n3 = malloc(sizeof(struct entry)); /* 前に挿入 */ TAILQ_INSERT_BEFORE(n2, n3, entries); TAILQ_REMOVE(&head, n2, entries); /* 削除 */ free(n2); /* 順走査 */ TAILQ_FOREACH(np, &head, entries) np-> ... /* 逆走査 */ TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) np-> ... /* テールキューの削除 */ while (!TAILQ_EMPTY(&head)) { n1 = TAILQ_FIRST(&head); TAILQ_REMOVE(&head, n1, entries); free(n1); } /* テールキューの高速な削除 */ n1 = TAILQ_FIRST(&head); while (n1 != NULL) { n2 = TAILQ_NEXT(n1, entries); free(n1); n1 = n2; } TAILQ_INIT(&head); .Ed .Sh 循環キュー 循環キューの最初には、 .Nm CIRCLEQ_HEAD マクロで定義される構造体が付きます。 この構造体には、循環キューの先頭の要素を指すポインタと 循環キューの末尾の要素を指すポインタの 2 つが含まれます。 要素は二重にリンクされているので、キューを走査せずに 任意の要素を削除できます。 新しい要素は、既存の要素の前、既存の要素の後ろ、循環キューの先頭、 循環キューの末尾で循環キューに追加できます。 .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_HEAD_INITIALIZER は循環キューの .Fa head を初期化します。 .Pp マクロ .Nm CIRCLEQ_EMPTY は循環キューに要素がない場合に真になります。 .Pp マクロ .Nm CIRCLEQ_ENTRY は循環キューの要素を接続する構造体を宣言します。 .Pp マクロ .Nm CIRCLEQ_FIRST は循環キューの先頭の要素を返します。 .Pp マクロ .Nm CICRLEQ_FOREACH は .Fa head で参照される循環キューを、各要素を順に .Fa var に割り当てて順方向に走査します。 .Pp マクロ .Nm CICRLEQ_FOREACH_REVERSE は .Fa head で参照される循環キューを、各要素を順に .Fa var に割り当てて逆方向に走査します。 .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_LAST は循環キューの末尾の要素を返します。 .Pp マクロ .Nm CIRCLEQ_NEXT は循環キューの次の要素を返します。 .Pp マクロ .Nm CIRCLEQ_PREV は循環キューの前の要素を返します。 .Pp マクロ .Nm CIRCLEQ_REMOVE は要素 .Fa elm を循環キューから削除します。 .Sh 循環キューの使用例 .Bd -literal CIRCLEQ_HEAD(circlehead, entry) head = CIRCLEQ_HEAD_INITIALIZER(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); CIRCLEQ_REMOVE(&head, n1, entries); /* 削除 */ free(n1); /* 順走査 */ CIRCLEQ_FOREACH(np, &head, entries) np-> ... /* 逆走査 */ CIRCLEQ_FOREACH_REVERSE(np, &head, entries) np-> ... /* 循環キューの削除 */ while (CIRCLEQ_FIRST(&head) != (void *)&head) { n1 = CIRCLEQ_HEAD(&head); CIRCLEQ_REMOVE(&head, n1, entries); free(n1); } /* 循環キューの高速な削除 */ n1 = CIRCLEQ_FIRST(&head); while (n1 != (void *)&head) { n2 = CIRCLEQ_NEXT(n1, entries); free(n1); n1 = n2; } CIRCLEQ_INIT(&head); .Ed .Sh 歴史 .Nm queue 関数は .Bx 4.4 ではじめて登場しました。