日本語 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, SLIST_ENTRY NAME);
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, STAILQ_ENTRY NAME);
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);
関連項目
tree(3)
歴史
queue 関数は、4.4BSD ではじめて登場しました。
FreeBSD 11.2 August 15, 2016 FreeBSD 11.2