Provided by: manpages-ja-dev_0.5.0.0.20161015+dfsg-1_all 
名前
LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_HEAD, LIST_REMOVE, TAILQ_ENTRY,
TAILQ_HEAD, TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE,
CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE,
CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLEQ_REMOVE - リスト・テール (tail) キュー・循環キューの実装
書式
#include <sys/queue.h>
LIST_ENTRY(TYPE);
LIST_HEAD(HEADNAME, TYPE);
LIST_INIT(LIST_HEAD *head);
LIST_INSERT_AFTER(LIST_ENTRY *listelm,
TYPE *elm, LIST_ENTRY NAME);
LIST_INSERT_HEAD(LIST_HEAD *head,
TYPE *elm, LIST_ENTRY NAME);
LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);
TAILQ_ENTRY(TYPE);
TAILQ_HEAD(HEADNAME, TYPE);
TAILQ_INIT(TAILQ_HEAD *head);
TAILQ_INSERT_AFTER(TAILQ_HEAD *head, 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_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
CIRCLEQ_ENTRY(TYPE);
CIRCLEQ_HEAD(HEADNAME, TYPE);
CIRCLEQ_INIT(CIRCLEQ_HEAD *head);
CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, TYPE *listelm,
TYPE *elm, CIRCLEQ_ENTRY NAME);
CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, TYPE *listelm,
TYPE *elm, CIRCLEQ_ENTRY NAME);
CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head,
TYPE *elm, CIRCLEQ_ENTRY NAME);
CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head,
TYPE *elm, CIRCLEQ_ENTRY NAME);
CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head,
TYPE *elm, CIRCLEQ_ENTRY NAME);
説明
これらのマクロは、次の 3 つのデータ構造を定義して操作する: リスト・テールキュー・循環キュー。 3 つのデー
タ構造すべてにおいて以下の機能がサポートされている:
* 新たなエントリーをリストの先頭に挿入する。
* 新たなエントリーをリストのどの要素よりも後に挿入する。
* リストの任意のエントリーを削除する。
* リストを順方向に辿る。
リストは 3 つのデータ構造の中で最も単純であり、 上記の機能のみをサポートする。
テールキューは以下の機能を追加する:
* エントリーをリストの最後に追加できる。
ただし:
1. 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
2. 各先頭エントリーは 1 つではなく 2 つのポインターを必要とする。
3. リストと比べて、コードサイズは 15% 大きくなり、操作は 20% 遅くなる。
循環キューは以下の機能を追加する:
* エントリーをリストの最後に追加できる。
* エントリーを他のエントリーの前に追加できる。
* 逆方向に末尾から先頭へ辿ることができる。
ただし:
1. 全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
2. 各先頭エントリーは 1 つではなく 2 つのポインターを必要とする。
3. 辿る際の終了条件がより複雑である。
4. リストと比べて、コードサイズは 40% 大きくなり、操作は 45% 遅くなる。
マクロ定義において TYPE はユーザー定義構造体の名前であり、 LIST_ENTRY, TAILQ_ENTRY, CIRCLEQ_ENTRY の何れ
か型のフィールドと 指定された NAME を含まなければならない。 引き数 HEADNAME はユーザー定義構造体の名前で
あり、 マクロ LIST_HEAD, TAILQ_HEAD, CIRCLEQ_HEAD を用いて宣言されなければならない。 これらのマクロがどの
ように使われるかについての更なる説明は、 以下の例を参照すること。
リスト
リストの先頭には、 LIST_HEAD マクロで定義される構造体が置かれる。 この構造体はリストの最初の要素へのポイ
ンターを 1 つ含む。 要素は 2 重にリンクされており、 任意の要素はリストを辿らずに削除できる。 新しい要素は
既存の要素の後またはリストの先頭に追加できる。 LIST_HEAD 構造体は以下のように宣言されている:
LIST_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義される構造体の名前であり、 TYPE はリンク内でリンクされる要素の型である。 リストの先
頭へのポインターは、その後で次のように宣言される:
struct HEADNAME *headp;
(名前 head と headp はユーザーが選択できる。)
マクロ LIST_ENTRY はリストの要素を接続する構造体を宣言する。
マクロ LIST_INIT は head で参照されるリストを初期化する。
マクロ LIST_INSERT_HEAD は新たな要素 elm をリストの先頭に挿入する。
マクロ LIST_INSERT_AFTER は新たな要素 elm を要素 listelm の後に挿入する。
マクロ LIST_REMOVE は要素 elm をリストから削除する。
リストの例
LIST_HEAD(listhead, entry) head;
struct listhead *headp; /* リストの先頭。*/
struct entry {
...
LIST_ENTRY(entry) entries; /* リスト。 */
...
} *n1, *n2, *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);
/* 順方向に辿る。*/
for (np = head.lh_first; np != NULL; np = np->entries.le_next)
np-> ...
while (head.lh_first != NULL) /* 削除する。*/
LIST_REMOVE(head.lh_first, entries);
テールキュー
テールキューの先頭には TAILQ_HEAD マクロで定義される構造体が置かれる。 この構造体は 1 組のポインターを含
んでいる。 1 つはテールキューの最初の要素へのポインターであり、 もう 1 つはテールキューの最後の要素へのポ
インターである。 要素は 2 重にリンクされており、 任意の要素はテールキューを辿らずに削除できる。 新しい要
素は既存の要素の後またはテールキューの先頭または末尾に追加できる。 TAILQ_HEAD 構造体は以下のように定義さ
れている:
TAILQ_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義される構造体の名前であり、 TYPE はテールキュー内でリンクされる要素の型である。 テー
ルキューの先頭へのポインターは、その後で次のように宣言される:
struct HEADNAME *headp;
(名前 head と headp はユーザーが選択できる。)
マクロ TAILQ_ENTRY はテールキューの要素を接続する構造体を宣言する。
マクロ TAILQ_INIT は head で参照されるテールキューを初期化する。
マクロ TAILQ_INSERT_HEAD は新たな要素 elm をテールキューの先頭に挿入する。
マクロ TAILQ_INSERT_TAIL は新たな要素 elm をテールキューの末尾に挿入する。
マクロ TAILQ_INSERT_AFTER は新たな要素 elm を要素 listelm の後に挿入する。
マクロ TAILQ_REMOVE は要素 elm をテールキューから削除する。
テールキューの例
TAILQ_HEAD(tailhead, entry) head;
struct tailhead *headp; /* テールキューの先頭。*/
struct entry {
...
TAILQ_ENTRY(entry) entries; /* テールキュー。*/
...
} *n1, *n2, *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);
/* 順方向に辿る。*/
for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)
np-> ...
/* 削除する。*/
while (head.tqh_first != NULL)
TAILQ_REMOVE(&head, head.tqh_first, entries);
循環キュー
循環キューの先頭には CIRCLEQ_HEAD マクロで定義される構造体が置かれる。 この構造体は 1 組のポインターを含
んでいる。 1 つは循環キューの最初の要素へのポインターであり、 もう 1 つは循環キューの最後の要素へのポイン
ターである。 要素は 2 重にリンクされており、 任意の要素はキューを辿らずに削除できる。 新しい要素は、既存
の要素の後または前、またはキューの先頭または末尾に追加できる。 A CIRCLEQ_HEAD 構造体は以下のように定義さ
れている:
CIRCLEQ_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義される構造体の名前であり、 TYPE は循環キュー内でリンクされる要素の型である。 循環
キューの先頭へのポインターは、その後で次のように宣言される:
struct HEADNAME *headp;
(名前 head と headp はユーザーが選択できる。)
マクロ CIRCLEQ_ENTRY は循環キューの要素を接続する構造体を宣言する。
マクロ CIRCLEQ_INIT は head で参照される循環キューを初期化する。
マクロ CIRCLEQ_INSERT_HEAD は新たな要素 elm を循環キューの先頭に挿入する。
マクロ CIRCLEQ_INSERT_TAIL は新たな要素 elm を循環キューの末尾に挿入する。
マクロ CIRCLEQ_INSERT_AFTER は新たな要素 elm を要素 listelm の後に挿入する。
マクロ CIRCLEQ_INSERT_AFTER は新たな要素 elm を要素 listelm の前に挿入する。
マクロ CIRCLEQ_REMOVE は要素 elm を循環キューから削除する。
循環キューの例
CIRCLEQ_HEAD(circleq, entry) 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);
/* 順方向に辿る。*/
for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)
np-> ...
/* 逆方向に辿る。*/
for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
np-> ...
/* 削除する。*/
while (head.cqh_first != (void *)&head)
CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
準拠
POSIX.1-2001 にはない。 BSD 系に存在する。 queue 関数は 4.4BSD で初めて登場した。
この文書について
この man ページは Linux man-pages プロジェクトのリリース 3.79 の一部 である。プロジェクトの説明とバグ報告
に関する情報は http://www.kernel.org/doc/man-pages/ に書かれている。