Simple queueにエレメントの次エレメントだけでなく前エレメントのポインタを持った構造で、前後に自由に移動することが出来ます。
Tail queueの構造
Simple queueにエレメントの次エレメントだけでなく前エレメントのポインタを持った構造で、前後に自由に移動することが出来ます。
TAILQ構造を使用するには、まずTAILQ形式のデータ構造を定義る必要があります。
TAILQ_ENTRYは、はTAILQ形式のデータ構造を定義します。各セルに数字が１つだけ入っているTAILQ構造、TailQを定義してみると、下記のようになります。
struct TailQ {
TAILQ_ENTRY(TailQ) tqueue_ptr;
int32_t data;
};
これは、次のように展開されます。
struct TailQ {
struct {
struct TailQ *tqe_next;
struct TailQ **tqe_prev;
} tqueue_ptr;
int32_t data;
};
これは定義だけで、まだ実体は無いことに注意してください。
TAILQ_HEADは、エレメントの先頭アドレスが入る構造体を定義します。
TAILQ_HEAD(TailQHead, TailQ);
これは、次のように展開されます。
struct TailQHead {
struct TailQ *tqh_first;
struct TailQ **tqh_last;
};
これも定義だけで、まだ実体は無いことに注意してください。
TAILQ_HEAD_INITIALIZERは、TAILQ_HEADを初期化します。次のように使用します。
// TAILQヘッダの実体を定義
struct TailQHead tqueue_head = TAILQ_HEAD_INITIALIZER(&tqueue_head);
TAILQ_INITは、TAILQを初期化します。次のように使用します。
if(!(TAILQ_EMPTY(&tqueue_head))) // TAILQが空であるかチェック TAILQ_INIT(&tqueue_head); // TAILQの初期化
TAILQ_FIRSTは、TAILQの先頭エレメントのポインタを返します。
arithmetic = TAILQ_FIRST(&tqueue_head); // 先頭elementを取得
TAILQ_LASTは、TAILQの最終のエレメントを返します。
arithmetic = TAILQ_LAST(&tqueue_head,TailQHead); // 最後のelementを取得
TAILQ_PREVは、指定エレメント(elm)に連結されている、直前のエレメントを返します。
arithmetic_prev = TAILQ_PREV(arithmetic,TailQHead,tqueue_ptr); // arithmeticの前elementを取得
TAILQ_NEXTは、エレメント(elm)に連結されている次エレメントのポインタを返します。
arithmetic_next = TAILQ_NEXT(arithmetic,tqueue_ptr); // arithmeticの次elementを取得
TAILQ_ENDは、NULLを返します。
TAILQ_EMPTYは、TAILQが空か調べます。
TAILQ_INSERT_HEADは、新しいエレメント(elm)をTAILQ(head)の先頭に追加します。
for(i=0;i<5;i++){
number[i].data = i;
}
TAILQ_INSERT_HEAD(&tqueue_head, &number[1], tqueue_ptr); // 1を先頭に挿入 (1)
TAILQ_INSERT_TAILは、新しいエレメント(elm)をTAILQ(head)の一番最後に追加します。
TAILQ_INSERT_TAIL(&tqueue_head,&number[3],tqueue_ptr); // 3を最後に挿入 (1 3)
結果は次のようになります。
TAILQ_INSERT_AFTERは、指定したエレメント(listelm)の後に、新しいエレメント(elm)を追加します。
TAILQ_INSERT_AFTER(&tqueue_head,&number[1],&number[2],tqueue_ptr); // 1の後に2を挿入 (1 2 3)
結果は次のようになります。
TAILQ_INSERT_BEFOREは、指定したエレメント(listelm)の前に、新しいエレメント(elm)を追加します。
TAILQ_INSERT_BEFORE(&tqueue_head,&number[1],&number[4],tqueue_ptr); // 1の前に4を挿入 (4 1 2 3)
結果は次のようになります。
TAILQ_REPLACEは、エレメント(elm)を、新しいエレメント(elm2)に置換えます。
TAILQ_REPLACE(&tqueue_head,&number[4],&number[0],tqueue_ptr); // 4を0にReplace (0 1 2 3)
結果はdata=4がdata=0に置き換わります。
TAILQ_FOREACHは、headに格納されたエレメントを最初から終りまでループして、varにポインタを返します。
// データの最初から終わりまでループ
TAILQ_FOREACH(arithmetic,&tqueue_head,tqueue_ptr){
printf("%d\n",arithmetic->data);
}
結果は、下記のようになります。
0
1
2
3
TAILQ_FOREACH_REVERSEは、headに格納されたエレメントを最後から最初まで逆にループして、varにポインタを返します。
// データの最後から最初までループ
TAILQ_FOREACH_REVERSE(arithmetic,&tqueue_head,TailQHead,tqueue_ptr){
printf("%d\n",arithmetic->data);
}
結果は、下記のようになります。
3
2
1
0
TAILQ_REMOVE_HEADは、TAILQ(head)の先頭エレメントを削除します。
// データが空になるまで削除します
while (TAILQ_FIRST(&tqueue_head))
TAILQ_REMOVE_HEAD(&tqueue_head,tqueue_ptr);
TAILQデータの操作sampleです。