日本語 man コマンド類 (ja-man-1.1j_5) と日本語 man ドキュメント (ja-man-doc-5.4 (5.4-RELEASE 用) など) をインストールすると、以下のような man コマンド閲覧、キーワード検索が コンソールからできるようになります。
4.11-RELEASE-K, 5.4-RELEASE-K, 5.5-RELEASE-K, 6.0-RELEASE-K から 6.4-RELEASE-K, 7.0-RELEASE-K から 7.4-RELEASE-K, 8.0-RELEASE-K から 8.4-RELEASE-K, 9.0-RELEASE-K から 9.3-RELEASE-K, 10.0-RELEASE-K から 10.3-RELEASE-K, 11.0-RELEASE-K から 11.4-RELEASE-K, 12.0-RELEASE-K, 12.1-RELEASE-K は、 プライベート版 (小金丸が編集してまとめたもの) ですが、 より多くの翻訳したファイルが含まれています。 (5.4-RELEASE-K から 6.4-RELEASE-K, 7.0-RELEASE-K から 7.4-RELEASE-K, 8.0-RELEASE-K から 8.4-RELEASE-K, 9.0-RELEASE-K から 9.3-RELEASE-K, 10.0-RELEASE-K から 10.3-RELEASE-K, 11.0-RELEASE-K から 11.4-RELEASE-K, 12.0-RELEASE-K から 12.3-RELEASE-K, 13.0-RELEASE-K から 13.2-RELEASE-K は、全翻訳済み)
13.3-STABLE-K, 15.0-CURRENT-K は現在、作成中で日々更新されています。
Table of Contents
QUEUE(3) FreeBSD ライブラリ関数マニュアル QUEUE(3) 名称 SLIST_CLASS_ENTRY, SLIST_CLASS_HEAD, SLIST_CONCAT, SLIST_EMPTY, SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_FOREACH_FROM, SLIST_FOREACH_FROM_SAFE, SLIST_FOREACH_SAFE, SLIST_HEAD, SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER, SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE, SLIST_REMOVE_AFTER, SLIST_REMOVE_HEAD, SLIST_SWAP, STAILQ_CLASS_ENTRY, STAILQ_CLASS_HEAD, STAILQ_CONCAT, STAILQ_EMPTY, STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH, STAILQ_FOREACH_FROM, STAILQ_FOREACH_FROM_SAFE, STAILQ_FOREACH_SAFE, STAILQ_HEAD, STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER, STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_LAST, STAILQ_NEXT, STAILQ_REMOVE, STAILQ_REMOVE_AFTER, STAILQ_REMOVE_HEAD, STAILQ_SWAP, LIST_CLASS_ENTRY, LIST_CLASS_HEAD, LIST_CONCAT, LIST_EMPTY, LIST_ENTRY, LIST_FIRST, LIST_FOREACH, LIST_FOREACH_FROM, LIST_FOREACH_FROM_SAFE, LIST_FOREACH_SAFE, LIST_HEAD, LIST_HEAD_INITIALIZER, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT, LIST_PREV, LIST_REMOVE, LIST_SWAP, TAILQ_CLASS_ENTRY, TAILQ_CLASS_HEAD, TAILQ_CONCAT, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH, TAILQ_FOREACH_FROM, TAILQ_FOREACH_FROM_SAFE, TAILQ_FOREACH_REVERSE, TAILQ_FOREACH_REVERSE_FROM, TAILQ_FOREACH_REVERSE_FROM_SAFE, TAILQ_FOREACH_REVERSE_SAFE, TAILQ_FOREACH_SAFE, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER, TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_LAST, TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE, TAILQ_SWAP -- 単一リンクリスト、単 一リンクテールキュー、リストとテールキューの実装 書式 #include <sys/queue.h> SLIST_CLASS_ENTRY(CLASSTYPE); SLIST_CLASS_HEAD(HEADNAME, CLASSTYPE); SLIST_CONCAT(SLIST_HEAD *head1, SLIST_HEAD *head2, TYPE, SLIST_ENTRY NAME); SLIST_EMPTY(SLIST_HEAD *head); SLIST_ENTRY(TYPE); SLIST_FIRST(SLIST_HEAD *head); SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME); SLIST_FOREACH_FROM(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME); SLIST_FOREACH_FROM_SAFE(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME, TYPE *temp_var); SLIST_FOREACH_SAFE(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME, TYPE *temp_var); SLIST_HEAD(HEADNAME, TYPE); SLIST_HEAD_INITIALIZER(SLIST_HEAD head); SLIST_INIT(SLIST_HEAD *head); SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SLIST_ENTRY NAME); SLIST_INSERT_HEAD(SLIST_HEAD *head, TYPE *elm, SLIST_ENTRY NAME); SLIST_NEXT(TYPE *elm, SLIST_ENTRY NAME); SLIST_REMOVE(SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME); SLIST_REMOVE_AFTER(TYPE *elm, SLIST_ENTRY NAME); SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME); SLIST_SWAP(SLIST_HEAD *head1, SLIST_HEAD *head2, TYPE); STAILQ_CLASS_ENTRY(CLASSTYPE); STAILQ_CLASS_HEAD(HEADNAME, CLASSTYPE); STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2); STAILQ_EMPTY(STAILQ_HEAD *head); STAILQ_ENTRY(TYPE); STAILQ_FIRST(STAILQ_HEAD *head); STAILQ_FOREACH(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME); STAILQ_FOREACH_FROM(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME); STAILQ_FOREACH_FROM_SAFE(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME, TYPE *temp_var); STAILQ_FOREACH_SAFE(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME, TYPE *temp_var); STAILQ_HEAD(HEADNAME, TYPE); STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head); STAILQ_INIT(STAILQ_HEAD *head); STAILQ_INSERT_AFTER(STAILQ_HEAD *head, TYPE *listelm, TYPE *elm, STAILQ_ENTRY NAME); STAILQ_INSERT_HEAD(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME); STAILQ_INSERT_TAIL(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME); STAILQ_LAST(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME); STAILQ_NEXT(TYPE *elm, STAILQ_ENTRY NAME); STAILQ_REMOVE(STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME); STAILQ_REMOVE_AFTER(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME); STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME); STAILQ_SWAP(STAILQ_HEAD *head1, STAILQ_HEAD *head2, TYPE); LIST_CLASS_ENTRY(CLASSTYPE); LIST_CLASS_HEAD(HEADNAME, CLASSTYPE); LIST_CONCAT(LIST_HEAD *head1, LIST_HEAD *head2, TYPE, LIST_ENTRY NAME); LIST_EMPTY(LIST_HEAD *head); LIST_ENTRY(TYPE); LIST_FIRST(LIST_HEAD *head); LIST_FOREACH(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME); LIST_FOREACH_FROM(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME); LIST_FOREACH_FROM_SAFE(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME, TYPE *temp_var); LIST_FOREACH_SAFE(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME, TYPE *temp_var); LIST_HEAD(HEADNAME, TYPE); LIST_HEAD_INITIALIZER(LIST_HEAD head); LIST_INIT(LIST_HEAD *head); LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME); LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME); LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME); LIST_NEXT(TYPE *elm, LIST_ENTRY NAME); LIST_PREV(TYPE *elm, LIST_HEAD *head, TYPE, LIST_ENTRY NAME); LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME); LIST_SWAP(LIST_HEAD *head1, LIST_HEAD *head2, TYPE, LIST_ENTRY NAME); TAILQ_CLASS_ENTRY(CLASSTYPE); TAILQ_CLASS_HEAD(HEADNAME, CLASSTYPE); TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TAILQ_ENTRY NAME); TAILQ_EMPTY(TAILQ_HEAD *head); TAILQ_ENTRY(TYPE); TAILQ_FIRST(TAILQ_HEAD *head); TAILQ_FOREACH(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME); TAILQ_FOREACH_FROM(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME); TAILQ_FOREACH_FROM_SAFE(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME, TYPE *temp_var); TAILQ_FOREACH_REVERSE(TYPE *var, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY NAME); TAILQ_FOREACH_REVERSE_FROM(TYPE *var, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY NAME); TAILQ_FOREACH_REVERSE_FROM_SAFE(TYPE *var, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY NAME, TYPE *temp_var); TAILQ_FOREACH_REVERSE_SAFE(TYPE *var, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY NAME, TYPE *temp_var); TAILQ_FOREACH_SAFE(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME, TYPE *temp_var); TAILQ_HEAD(HEADNAME, TYPE); TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head); TAILQ_INIT(TAILQ_HEAD *head); TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME); TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME); TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME); TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME); TAILQ_LAST(TAILQ_HEAD *head, HEADNAME); TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME); TAILQ_PREV(TYPE *elm, HEADNAME, TAILQ_ENTRY NAME); TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME); TAILQ_SWAP(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TYPE, TAILQ_ENTRY NAME); 解説 これらのマクロは、C と C++ ソースコードの両方で使用することができる 4 つ のタイプのデータ構造で定義し操作します。 1. リスト 2. 単一リンクリスト 3. 単一リンクテールキュー 4. テールキュー 4 つの構造は、すべて次の機能をサポートします: 1. リストの先頭に新しいエントリの挿入。 2. リスト中の任意のエントリの後に新しいエントリの挿入。 3. リストの先頭からエントリの O(1) 削除。 4. リストを通して前方にたどる。 5. 2 つのリストの内容を交換。 単一リンクリストは、4 つのデータ構造の中で最も単純で、上記の機能だけをサ ポートします。単一リンクリストは、大きなデータセットと削除が有るか無しか のアプリケーションにとって、または LIFO キューの実装にとって理想的です。 単一リンクリストは、次の機能も加わります: 1. リスト中の任意のエントリの O(n) 削除。 2. 2 つのリストの O(n) 連結。 単一リンクのテールキューは、次の機能を追加します: 1. リストの終わりにエントリを追加することができます。 2. リスト中の任意のエントリの O(n) 削除。 3. それらを連結することができます。 しかしながら: 1. リスト挿入は、すべてリストの先頭を指定しなければなりません。 2. 各先頭のエントリは、1 つではなく 2 つのポインタを要求します。 3. 単一リンクリストより、コードサイズは、約 15% 大きくなり、動作 は、20% 遅くなります。 単一リンクテールキューは、大きなデータセットと削除が有るか無しかのアプリ ケーションにとって、または LIFO キューの実装にとって理想的です。 すべての二重リンクタイプのデータ構造 (リストとテールキュー) は、さらに次 も許可します: 1. リスト中の任意の要素の前に新しいエントリを挿入。 2. リスト中の任意のエントリを O(1) 削除。 しかしながら: 1. 各要素は、1 つではなく 2 つのポインタを要求します。 2. 単一リンクデータ構造より、コードサイズと (削除を除いて) 動作の 実行時間は、およそ 2 倍になります。 リンクリストは、二重リンクのデータ構造の中で最も単純です。それらは、上記 のものに次の機能性を追加します: 1. 2 つのリストの O(n) 連結。 2. それらは、後方に横断されます。 しかしながら: 1. 後方に横断するためには、横断を始めるエントリとそれが含まれてい るリストを指定しなければなりません。 テールキューは、次の機能も加わります: 1. エントリは、リストの終わりに加えることができます。 2. それらは、末尾から先頭へ逆にたどることができます。 3. それらは、連結することができます。 しかしながら: 1. リスト挿入と削除は、すべて、リストの先頭を指定しなければなりま せん。 2. 各先頭のエントリは、1 つではなく 2 つのポインタを要求します。 3. 単一リンクリストより、コードサイズは、約 15% 大きくなり、動作 は、20% 遅くなります。 マクロの定義で、TYPE は、ユーザが定義した構造体の名前です。構造体は、タイ プ SLIST_ENTRY, STAILQ_ENTRY, LIST_ENTRY または TAILQ_ENTRY である NAME と呼ばれるフィールドを含んでいなければなりません。マクロの定義で、 CLASSTYPE は、ユーザ定義されたクラスの名前です。クラスは、タイプ SLIST_CLASS_ENTRY, STAILQ_CLASS_ENTRY, LIST_CLASS_ENTRY または TAILQ_CLASS_ENTRY である NAME と呼ばれるフィールドを含んでいなければなり ません。引数 HEADNAME は、マクロ SLIST_HEAD, SLIST_CLASS_HEAD, STAILQ_HEAD, STAILQ_CLASS_HEAD, LIST_HEAD, LIST_CLASS_HEAD, TAILQ_HEAD ま たは TAILQ_CLASS_HEAD を使用して宣言されなければならないユーザ定義の構造 体の名前です。これらのマクロがどのように使用されるかのさらなる説明に関し ては、下記の例を参照してください。 単一リンクリスト 単一リンクリストは、SLIST_HEAD マクロによって定義された構造体を先頭としま す。この構造体は、リストの最初の要素への単一のポインタを含んでいます。要 素は、任意の要素のための O(n) 削除を犠牲にして最小の空間とポインタ操作の オーバヘッドのために個々にリンクされます。新しい要素は、既存の要素の後、 またはリストの先頭にリストに追加することができます。SLIST_HEAD 構造体は、 次のように宣言されます: SLIST_HEAD(HEADNAME, TYPE) head; ここで、HEADNAME は、定義される構造体の名前で、TYPE は、テールキューにリ ンクされる要素のタイプです。テールキューの先頭へのポインタは、後で次のよ うに宣言することができます: struct HEADNAME *headp; (名前 head と headp は、ユーザが選択できます。) マクロ SLIST_HEAD_INITIALIZER は、リスト head のための初期化子を評価しま す。 マクロ SLIST_CONCAT は、前者からすべてのエントリを削除して、head1 を先頭 とするものの終わりに head2 を先頭とするリストを連結します。このマクロの使 用は、head1 リストの全体をたどるので避けられるべきです。単一リンクテール キューは、このマクロが高度使用法 (high-usage) コードパスまたは長いリスト で操作する必要があるなら、使用されるべきです。 マクロ SLIST_EMPTY は、リストに要素がないなら、真と評価します。 マクロ SLIST_ENTRY は、リストの要素を接続する構造体を宣言します。 マクロ SLIST_FIRST は、リストの最初の要素を返すか、またはリストが空である なら、NULL を返します。 マクロ SLIST_FOREACH は、各要素を順に var に代入して順方向で head によっ て参照されるリストをたどります。 マクロ SLIST_FOREACH_FROM は、var が NULL であるとき、SLIST_FOREACH と同 様に振る舞います、そうでなければ、以前に SLIST 要素を見つけたように、var を扱い、head によって参照される SLIST の最初の要素の代わりに var でループ を始めます。 マクロ SLIST_FOREACH_SAFE は、各要素を順に var に代入して順方向で head に よって参照されるリストをたどります。しかしながら、ここで SLIST_FOREACH() と異なって、たどることを妨げないで安全にループ内からそれを解放するのと同 様に var を削除することが許されます。 マクロ SLIST_FOREACH_FROM_SAFE は、var が NULL であるとき、 SLIST_FOREACH_SAFE と同様に振る舞います、そうでなければ、以前に SLIST 要 素を見つけたように、var を扱い、head によって参照される SLIST の最初の要 素の代わりに var でループを始めます。 マクロ SLIST_INIT は、head によって参照されるリストを初期化します。 マクロ SLIST_INSERT_HEAD は、リストの先頭に新しい要素 elm を挿入します。 マクロ SLIST_INSERT_AFTER は、要素 listelm の後に新しい要素 elm を挿入し ます。 マクロ SLIST_NEXT は、リストの次の要素を返します。 マクロ SLIST_REMOVE_AFTER は、リストから elm の後の要素を削除します。 SLIST_REMOVE と異なって、このマクロは、全体のリストをたどりません。 マクロ SLIST_REMOVE_HEAD は、リストの先頭から要素 elm を削除します。最適 な効率のために、リストの先頭頭から削除されている要素は、一般的な SLIST_REMOVE マクロの代わりに、このマクロを明示的に使用するべきです。 マクロ SLIST_REMOVE は、リストから要素 elm を削除します。このマクロの使用 は、全体のリストをたどるので避けられるべきです。二重リンクリストは、この マクロが高度使用法 (high-usage) コードパスまたは長いリストで操作する必要 があるなら、使用されるべきです。 マクロ SLIST_SWAP は、head1 と head2 の内容を交換します。 単一リンクリストの使用例 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-> ... /* 安全に前方にたどる */ SLIST_FOREACH_SAFE(np, &head, entries, np_temp) { np->do_stuff(); ... SLIST_REMOVE(&head, np, entry, entries); free(np); } while (!SLIST_EMPTY(&head)) { /* リストの削除 */ n1 = SLIST_FIRST(&head); SLIST_REMOVE_HEAD(&head, entries); free(n1); } 単一リンクテールキュー 単一リンクテールキューは、STAILQ_HEAD マクロによって定義された構造体を先 頭とします。この構造体は、テールキューの最初の要素へのポインタとテール キューの最後の要素へのポインタの 2 つのポインタを含んでいます。要素は、任 意の要素のための O(n) 削除を犠牲にして空間とポインタ操作のオーバヘッドを 最小となるように単一にリンクされます。既存の要素の後に、テールキューの先 頭またはテールキューの終わりに新しい要素を追加することができます。 STAILQ_HEAD 構造体は、次のように宣言されます: STAILQ_HEAD(HEADNAME, TYPE) head; ここで HEADNAME は、定義される構造体の名前で、TYPE は、テールキューにリン クされる要素のタイプです。テールキューの先頭へのポインタは、後で次のよう に宣言することができます: struct HEADNAME *headp; (名前 head と headp は、ユーザが選択できます。) マクロ STAILQ_HEAD_INITIALIZER は、テールキュー head のための初期化を評価 します。 マクロ STAILQ_CONCAT は、head2 を先頭にするテールキューと、前者からすべて のエントリを取り除く head1 を先頭にするキューの終わりを連結します。 マクロ STAILQ_EMPTY は、テールキューに項目がないなら、真と評価します。 マクロ STAILQ_ENTRY は、テールキューの要素を接続する構造体を宣言します。 マクロ STAILQ_FIRST は、テールキューの最初の項目を返すか、またはテール キューが空であるなら、NULL を返します。 マクロ STAILQ_FOREACH は、各要素を順に var に代入して順方向で head によっ て参照されるテールキューをたどります。 マクロ STAILQ_FOREACH_FROM は、var が NULL であるとき、STAILQ_FOREACH と 同様に振る舞います、そうでなければ、以前に STAILQ 要素を見つけたように、 var を扱い、head によって参照される STAILQ の最初の要素の代わりに var で ループを始めます。 マクロ STAILQ_FOREACH_SAFE は、各要素を順に var に代入して順方向で head によって参照されるリストをたどります。しかしながら、ここで STAILQ_FOREACH() と異なって、たどることを妨げないで安全にループ内からそれ を解放するのと同様に var を削除することが許されます。 マクロ STAILQ_FOREACH_FROM_SAFE は、var が NULL であるとき、 STAILQ_FOREACH_SAFE と同様に振る舞います、そうでなければ、以前に STAILQ 要素を見つけたように、var を扱い、head によって参照される STAILQ の最初の 要素の代わりに var でループを始めます。 マクロ STAILQ_INIT は、head によって参照されるテールキューを初期化しま す。 マクロ STAILQ_INSERT_HEAD は、テールキューの先頭に新しい要素 elm を挿入し ます。 マクロ STAILQ_INSERT_TAIL は、テールキューの終わりに新しい要素 elm を挿入 します。 マクロ STAILQ_INSERT_AFTER は、要素 listelm の後に新しい要素 elm を挿入し ます。 マクロ STAILQ_LAST は、テールキューの最後の項目を返します。テールキューが 空ならば、返り値は、NULL です。 マクロ STAILQ_NEXT は、テールキューの次の項目を返すか、この項目が最後なら NULL を返します。 マクロ STAILQ_REMOVE_AFTER は、テールキューから elm の後の要素を削除しま す。STAILQ_REMOVE と異なって、このマクロは、全体のテールキューをたどりま せん。 マクロ STAILQ_REMOVE_HEAD は、テールキューの先頭の要素を削除します。最適 な効率のために、テールキューの先頭から削除されている要素は、一般的な STAILQ_REMOVE マクロではなく、このマクロを明示的に使用するべきです。 マクロ STAILQ_REMOVE は、テールキューから要素 elm を削除します。このマク ロの使用は、全体のリストをたどるので避けられるべきです。二重リンクテール キューは、このマクロが高度使用法 (high-usage) コードパスまたは長いリスト で操作する必要があるなら、使用されるべきです。 マクロ STAILQ_SWAP は、head1 と head2 の内容を交換します。 単一リンクテールキューの使用例 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-> ... /* 安全に前方にたどる */ STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { np->do_stuff(); ... STAILQ_REMOVE(&head, np, entry, entries); free(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); リスト リストは、LIST_HEAD マクロによって定義された構造体を先頭とします。この構 造体は、リストの最初の要素への単一のポインタを含んでいます。要素は、任意 の要素がリストをたどらずに削除することができるように、二重にリンクされま す。新しい要素は、既存の要素の後で、既存の要素の前で、またはリストの先頭 でリストに追加することができます。LIST_HEAD 構造体は、次のように宣言され ます: LIST_HEAD(HEADNAME, TYPE) head; ここで、HEADNAME は、定義される構造体の名前で、TYPE は、リストにリンクさ れる要素のタイプです。リストの先頭へのポインタは、後で次のように宣言でき ます: struct HEADNAME *headp; (名前 head と headp は、ユーザが選択できます。) マクロ LIST_HEAD_INITIALIZER は、リスト head のための初期化子を評価しま す。 マクロ LIST_CONCAT は、前者からすべてのエントリを削除して、head1 を先頭と するものの終わりに head2 を先頭とするリストを連結します。このマクロの使用 は、head1 リストの全体をたどるので避けられるべきです。テールキューは、こ のマクロが高度使用法 (high-usage) コードパスまたは長いリストで操作する必 要があるなら、使用されるべきです。 マクロ LIST_EMPTY は、リストに要素がないなら、真と評価します。 マクロ LIST_ENTRY は、リストの要素を接続する構造体を宣言します。 マクロ LIST_FIRST は、リストの最初の要素を返すか、またはリストが空である なら、NULL を返します。 マクロ LIST_FOREACH は、各要素を順に var に代入して順方向で head によって 参照されるリストをたどります。 マクロ LIST_FOREACH_FROM は、var が NULL であるとき、LIST_FOREACH と同様 に振る舞います、そうでなければ、以前に LIST 要素を見つけたように、var を 扱い、head によって参照される LIST の最初の要素の代わりに var でループを 始めます。 マクロ LIST_FOREACH_SAFE は、各要素を順に var に代入して順方向で head に よって参照されるリストをたどります。しかしながら、ここで LIST_FOREACH() と異なって、たどることを妨げないで安全にループ内からそれを解放するのと同 様に var を削除することが許されます。 マクロ LIST_FOREACH_FROM_SAFE は、var が NULL であるとき、 LIST_FOREACH_SAFE と同様に振る舞います、そうでなければ、以前に LIST 要素 を見つけたように、var を扱い、head によって参照される LIST の最初の要素の 代わりに var でループを始めます。 マクロ LIST_INIT は、head によって参照されるリストを初期化します。 マクロ LIST_INSERT_HEAD は、リストの先頭に新しい要素 elm を挿入します。 マクロ LIST_INSERT_AFTER は、要素 listelm の後に新しい要素 elm を挿入しま す。 マクロ LIST_INSERT_BEFORE は、要素 listelm の前に新しい要素 elm を挿入し ます。 マクロ LIST_NEXT は、リストの次の要素を返すか、またはこれが、最後であるな ら、NULL を返します。 マクロ LIST_PREV は、リストの前の要素を返すか、またはこれが、最初であるな ら、NULL を返します。リスト head は、要素 elm を含んでいなければなりませ ん。 マクロ LIST_REMOVE は、リストから要素 elm を削除します。 マクロ LIST_SWAP は、head1 と head2 の内容を交換します。 リストの使用例 LIST_HEAD(listhead, entry) head = LIST_HEAD_INITIALIZER(head); struct listhead *headp; /* リストの先頭 */ struct entry { ... LIST_ENTRY(entry) entries; /* リスト */ ... } *n1, *n2, *n3, *np, *np_temp; 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-> ... /* 安全に前方にたどる */ LIST_FOREACH_SAFE(np, &head, entries, np_temp) { np->do_stuff(); ... LIST_REMOVE(np, entries); free(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); テールキュー テールキューは、TAILQ_HEAD マクロによって定義された構造体を先頭とします。 この構造体は、テールキューの最初の要素へのポインタとテールキューの最後の 要素へのポインタの 2 つのポインタを含んでいます。テールキューをたどらず に、任意の要素を削除できるように、要素は二重にリンクされます。新しい要素 は、既存の要素の後に、既存の要素の前に、テールキューの先頭に、あるいは テールキューの終わりにテールキューに追加できます。TAILQ_HEAD 構造体は、次 のように宣言されます: TAILQ_HEAD(HEADNAME, TYPE) head; ここで HEADNAME は、定義される構造体の名前で、TYPE は、テールキューにリン クされる要素のタイプです。テールキューの先頭へのポインタは、後で次のよう に宣言することができます: struct HEADNAME *headp; (名前 head と headp は、ユーザが選択できます。) マクロ TAILQ_HEAD_INITIALIZER は、テールキュー head のための初期化子を評 価します。 マクロ TAILQ_CONCAT は、head2 を先頭にするテールキューと、前者からすべて のエントリを取り除く head1 を先頭にするキューの終わりを連結します。 マクロ TAILQ_EMPTY は、テールキューに項目がないなら、真と評価します。 マクロ TAILQ_ENTRY は、テールキューの要素を接続する構造体を宣言します。 マクロ TAILQ_FIRST は、テールキューの最初の項目を返すか、またはテール キューが空であるなら、NULL を返します。 マクロ TAILQ_FOREACH は、各要素を順に var に代入して順方向で head によっ て参照されるテールキューをたどります。通常、ループが完全かまたは要素がな かったなら、var は、NULL に設定されます。 マクロ TAILQ_FOREACH_FROM は、var が NULL であるとき、TAILQ_FOREACH と同 様に振る舞います、そうでなければ、以前に TAILQ 要素を見つけたように、var を扱い、head によって参照される TAILQ の最初の要素の代わりに var でループ を始めます。 マクロ TAILQ_FOREACH_REVERSE は、各要素を順に var に代入して逆方向で head によって参照されるテールキューをたどります。 マクロ TAILQ_FOREACH_REVERSE_FROM は、var が NULL であるとき、 TAILQ_FOREACH_REVERSE と同様に振る舞います、そうでなければ、以前に TAILQ 要素を見つけたように、var を扱い、head によって参照される TAILQ の最初の 要素の代わりに var でループを始めます。 マクロ TAILQ_FOREACH_SAFE と TAILQ_FOREACH_REVERSE_SAFE は、各要素を順に var に代入して、それぞれ順方向で head によって参照されるテールキューをた どりるか、反対の方向へたどります。しかしながら、対応する安全でない TAILQ_FOREACH と TAILQ_FOREACH_REVERSE と異なって、たどることを妨げないで 安全にループ内からそれを解放するのと同様に var を削除することが許されま す。 マクロ TAILQ_FOREACH_FROM_SAFE は、var が NULL であるとき、 TAILQ_FOREACH_SAFE と同様に振る舞います、そうでなければ、以前に TAILQ 要 素を見つけたように、var を扱い、head によって参照される TAILQ の最初の要 素の代わりに var でループを始めます。 マクロ TAILQ_FOREACH_REVERSE_FROM_SAFE は、var が NULL であるとき、 TAILQ_FOREACH_REVERSE_SAFE と同様に振る舞います、そうでなければ、以前に TAILQ 要素を見つけたように、var を扱い、head によって参照される TAILQ の 最初の要素の代わりに var でループを始めます。 マクロ TAILQ_INIT は、head によって参照されるテールキューを初期化します。 マクロ TAILQ_INSERT_HEAD は、テールキューの先頭で新しい要素 elm を挿入し ます。 マクロ TAILQ_INSERT_TAIL は、テールキューの終わりに新しい要素 elm を挿入 します。 マクロ TAILQ_INSERT_AFTER は、要素 listelm の後に新しい要素 elm を挿入し ます。 マクロ TAILQ_INSERT_BEFORE は、要素 listelm の前に新しい要素 elm を挿入し ます。 マクロ TAILQ_LAST は、テールキューの最後の項目を返します。テールキューが 空であるなら、返り値は、NULL です。 マクロ TAILQ_NEXT は、テールキューの次の項目を返すか、またはこの項目が最 後であるなら、NULL を返します。 マクロ TAILQ_PREV は、テールキューの前の項目を返すか、またはこの項目が最 初であるなら、NUL を返しますL。 マクロ TAILQ_REMOVE は、テールキューから要素 elm を削除します。 マクロ TAILQ_SWAP は、head1 と head2 の内容を交換します。 テールキューの使用例 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_SAFE(np, &head, entries, np_temp) { np->do_stuff(); ... TAILQ_REMOVE(&head, np, entries); free(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); 診断 queue(3) をデバッグするとき、キューの変化をトレースすることに役に立ちま す。トレースを有効にするために、コンパイル時にマクロ QUEUE_MACRO_DEBUG_TRACE を定義します。 また、削除の後の使用を検出するために、キューからアンリンクされたポインタ を破壊することに役に立ちます。ポインタの破壊を有効にするために、コンパイ ル時にマクロ QUEUE_MACRO_DEBUG_TRASH を定義します。マクロ QMD_IS_TRASHED(void *ptr) は、ptr が QUEUE_MACRO_DEBUG_TRASH オプションに よって破壊されたなら、真を返します。 (有効にされた INVARIANTS がある) カーネルで、SLIST_REMOVE_PREVPTR() マク ロは、デバッグを援助するために利用可能です: SLIST_REMOVE_PREVPTR(TYPE **prev, TYPE *elm, SLIST_ENTRY NAME) &SLIST_NEXT() が prev である要素に直接続いていなければなら ない、elm を SLIST から削除します。このマクロは、elm が INVARIANTS モードの prev に続いていることを確認します。 関連項目 tree(3) 歴史 queue 関数は、4.4BSD ではじめて登場しました。 FreeBSD 12.2 September 8, 2016 FreeBSD 12.2