YOS OPENSONAR

  2. >
  3. freebsd
  4. >
  5. man
  6. >
  7. ja
  8. >
  9. man3
  2. >
  3. freebsd
  4. >
  5. man
  6. >
  7. ja
  8. >
  9. man3
EN JA
QUEUE(3)
QUEUE(3) FreeBSD Library Functions Manual QUEUE(3)

名称

SLIST_EMPTY, SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_FOREACH_FROM, SLIST_FOREACH_SAFE, SLIST_FOREACH_FROM_SAFE, SLIST_HEAD, SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER, SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE_AFTER, SLIST_REMOVE_HEAD, SLIST_REMOVE, SLIST_SWAP, STAILQ_CONCAT, STAILQ_EMPTY, STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH, STAILQ_FOREACH_FROM, STAILQ_FOREACH_SAFE, STAILQ_FOREACH_FROM_SAFE, STAILQ_HEAD, STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER, STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_LAST, STAILQ_NEXT, STAILQ_REMOVE_AFTER, STAILQ_REMOVE_HEAD, STAILQ_REMOVE, STAILQ_SWAP, LIST_EMPTY, LIST_ENTRY, LIST_FIRST, LIST_FOREACH, LIST_FOREACH_FROM, LIST_FOREACH_SAFE, LIST_FOREACH_FROM_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_CONCAT, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH, TAILQ_FOREACH_FROM, TAILQ_FOREACH_SAFE, TAILQ_FOREACH_FROM_SAFE, TAILQ_FOREACH_REVERSE, TAILQ_FOREACH_REVERSE_FROM, TAILQ_FOREACH_REVERSE_SAFE, TAILQ_FOREACH_REVERSE_FROM_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_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_SAFE( TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME, TYPE *temp_var);

SLIST_FOREACH_FROM_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_AFTER( TYPE *elm, SLIST_ENTRY NAME);

SLIST_REMOVE_HEAD( SLIST_HEAD *head, SLIST_ENTRY NAME);

SLIST_REMOVE( SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME);

SLIST_SWAP( SLIST_HEAD *head1, SLIST_HEAD *head2, SLIST_ENTRY NAME);

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_SAFE( TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME, TYPE *temp_var);

STAILQ_FOREACH_FROM_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, STAILQ_ENTRY NAME);

STAILQ_NEXT( TYPE *elm, STAILQ_ENTRY NAME);

STAILQ_REMOVE_AFTER( STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);

STAILQ_REMOVE_HEAD( STAILQ_HEAD *head, STAILQ_ENTRY NAME);

STAILQ_REMOVE( STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME);

STAILQ_SWAP( STAILQ_HEAD *head1, STAILQ_HEAD *head2, STAILQ_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_SAFE( TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME, TYPE *temp_var);

LIST_FOREACH_FROM_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_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_SAFE( TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME, TYPE *temp_var);

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_SAFE( TYPE *var, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY NAME, TYPE *temp_var);

TAILQ_FOREACH_REVERSE_FROM_SAFE( TYPE *var, TAILQ_HEAD *head, HEADNAME, 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);

解説

これらのマクロは、単一リンクリスト、単一リンクテールキュー、リストとテールキューの 4 つのタイプのデータ構造を定義し操作します。 4 つの構造は、すべて次の機能をサポートします:
  1. リストの先頭に新しいエントリの挿入。
  2. リスト中の任意のエントリの後に新しいエントリの挿入。
  3. リストの先頭からエントリの O(1) 削除。
  4. リストを通して前方にたどる。
  5. 2 つのリストの内容を交換。

単一リンクリストは、4 つのデータ構造の中で最も単純で、上記の機能だけをサポートします。単一リンクリストは、大きなデータセットと削除が有るか無しかのアプロケーションにとって、または LIFO キューの実装にとって理想的です。単一リンクリストは、次の機能も加わります:

  1. リスト中の任意のエントリの 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. それらは、後方に横断されます。

しかしながら:

  1. 後方に横断するためには、横断を始めるエントリとそれが含まれているリストを指定しなければなりません。

テールキューは、次の機能も加わります:

  1. エントリは、リストの終わりに加えることができます。
  2. それらは、末尾から先頭へ逆にたどることができます。
  3. それらは、連結することができます。

しかしながら:

  1. リスト挿入と削除は、すべて、リストの先頭を指定しなければなりません。
  2. 各先頭のエントリは、1 つではなく 2 つのポインタを要求します。
  3. 単一リンクリストより、コードサイズは、約 15% 大きくなり、動作は、20% 遅くなります。

マクロの定義では、 TYPE は、ユーザが定義した構造体です。それは、 NAME と名前がついたタイプ SLIST_ENTRY, STAILQ_ENTRY, LIST_ENTRY または TAILQ_ENTRY のフィールドを含んでいなければなりません。引数 HEADNAME は、マクロ SLIST_HEAD, STAILQ_HEAD, LIST_HEAD または TAILQ_HEAD を使用して宣言されなければならないユーザ定義の構造体の名前です。これらのマクロがどのように使用されるかのさらなる説明に関しては、下記の例を参照してください。

単一リンクリスト

単一リンクリストは、 SLIST_HEAD マクロによって定義された構造体を先頭とします。この構造体は、リストの最初の要素への単一のポインタを含んでいます。要素は、任意の要素のための O(n) 削除を犠牲にして最小の空間とポインタ操作のオーバヘッドのために個々にリンクされます。新しい要素は、既存の要素の後、またはリストの先頭にリストに追加することができます。 SLIST_HEAD 構造体は、次のように宣言されます: 

SLIST_HEAD(HEADNAME, TYPE) head;

ここで、 HEADNAME は、定義される構造体の名前で、 TYPE は、テールキューにリンクされる要素のタイプです。テールキューの先頭へのポインタは、後で次のように宣言することができます:

struct HEADNAME *headp;

(名前 head と headp は、ユーザが選択できます。)

マクロ SLIST_HEAD_INITIALIZER は、リスト head のための初期化指定子を評価します。

マクロ 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 を削除します。

マクロ 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 を削除します。

マクロ 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_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 は、テールキューの前のアイテムを返すか、このアイテムが最初なら NULL を返します。

マクロ 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 ではじめて登場しました。
June 17, 2013 FreeBSD