名 前
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/ に 書 か れ て い る 。