Circular queueはTail queueとほぼ同じですが、最後のエレメントの次エレメントを示すポインタがNULL出なく、ヘッダを指し示している所が違います。
Circular queueの構造
Circular queueはTail queueとほぼ同じですが、最後のエレメントの次エレメントを示すポインタがNULL出なく、ヘッダを指し示している所が違います。
CIRCLEQ構造を使用するには、まずCIRCLEQ形式のデータ構造を定義る必要があります。
CIRCLEQ_ENTRYは、CIRCLEQ形式のデータ構造を定義します。各エレメントに数字が１つだけ入っているCIRCLEQ構造、CircleQを定義してみると、下記のようになります。
struct CircleQ {
CIRCLEQ_ENTRY(CircleQ) cqueue_ptr;
int32_t data;
};
この構造体内にあるCIRCLEQへのポインタを作成するマクロであり、展開されると次のようになります。
struct CircleQ {
struct {
struct TailQ *tqe_next;
struct TailQ **tqe_prev;
} cqueue_ptr;
int32_t data;
};
これは定義だけで、まだ実体は無いことに注意してください。
CIRCLEQ_HEADは、エレメントの先頭アドレスが入る構造体を定義します。
CIRCLEQ_HEAD(CircleQHead, CircleQ);
これは、展開されると次のようになります。
struct CircleQHead {
struct TailQ *tqh_first;
struct TailQ **tqh_last;
};
これも定義だけで、まだ実体は無いことに注意してください。
CIRCLEQ_HEAD_INITIALIZERは、CIRCLEQ_HEADを初期化します。次のように使用します。
// CIRCLEQヘッダの実体を定義
struct CircleQHead cqueue_head = CIRCLEQ_HEAD_INITIALIZER(&cqueue_head);
CIRCLEQ_INITは、CIRCLEQを初期化します。次のように使用します。
if(!(CIRCLEQ_EMPTY(&cqueue_head))) // CIRCLEQが空であるかチェック CIRCLEQ_INIT(&cqueue_head); // CIRCLEQの初期化
CIRCLEQ_FIRSTは、CIRCLEQの先頭エレメントのポインタを返します。
arithmetic = CIRCLEQ_FIRST(&cqueue_head); // 先頭elementを取得
CIRCLEQ_LASTは、CIRCLEQの最終のエレメントを返します。
arithmetic = CIRCLEQ_LAST(&cqueue_head); // 最後のelementを取得
CIRCLEQ_ENDは、NULLを返します。
CIRCLEQ_NEXTは、エレメント(elm)に連結されている次エレメントのポインタを返します。
arithmetic_next = CIRCLEQ_NEXT(arithmetic,cqueue_ptr); // arithmeticの次elementを取得
CIRCLEQ_PREVは、指定エレメント(elm)に連結されている、直前のエレメントを返します。
arithmetic_prev = CIRCLEQ_PREV(arithmetic,cqueue_ptr); // arithmeticの前elementを取得
CIRCLEQ_EMPTYは、CIRCLEQが空であるか調べます。
CIRCLEQ_INSERT_HEADは、新しいエレメント(elm)をCIRCLEQ(head)の先頭に追加します。
CIRCLEQ_INSERT_HEAD(&cqueue_head, &number[1], cqueue_ptr); // 1を先頭に挿入 (1)
CIRCLEQ_INSERT_TAILは、新しいエレメント(elm)をCIRCLEQ(head)の一番最後に追加します。
CIRCLEQ_INSERT_TAIL(&cqueue_head,&number[3],cqueue_ptr); // 3を最後に挿入 (1 3)
結果は次のようになります。
CIRCLEQ_INSERT_AFTERは、指定したエレメント(listelm)の後に、新しいエレメント(elm)を追加します。
CIRCLEQ_INSERT_AFTER(&cqueue_head,&number[0],&number[2],cqueue_ptr); // 1の後に2を挿入 (1 2 3)
結果は次のようになります。
CIRCLEQ_INSERT_BEFOREは、指定したエレメント(listelm)の前に、新しいエレメント(elm)を追加します。
CIRCLEQ_INSERT_BEFORE(&cqueue_head,&number[1],&number[4],cqueue_ptr); // 1の前に4を挿入 (4 1 2 3)
結果は次のようになります。
CIRCLEQ_REPLACEは、エレメント(elm)を、新しいエレメント(elm2)に置換えます。
CIRCLEQ_REPLACE(&cqueue_head,&number[4],&number[0],cqueue_ptr); // 4を0にReplace (0 1 2 3)
コンパイルエラーが出てしまいます，なんかバグってる気がする。
CIRCLEQ_FOREACHは、headに格納されたエレメントを最初から終りまでループして、varにポインタを返します。
// データの最初から終わりまでループ
CIRCLEQ_FOREACH(arithmetic,&cqueue_head,cqueue_ptr){
printf("%d\n",arithmetic->data);
}
結果は、下記のようになります。
0
1
2
3
CIRCLEQ_FOREACH_REVERSEは、headに格納されたエレメントを最後から最初まで逆にループして、varにポインタを返します。
// データの最後から最初までループ
CIRCLEQ_FOREACH_REVERSE(arithmetic,&cqueue_head,CircleQHead,cqueue_ptr){
printf("%d\n",arithmetic->data);
}
結果は、下記のようになります。
3
2
1
0
CIRCLEQ_REMOVEは、CIRCLEQ(head)の先頭エレメントを削除します。
// データが空になるまで削除します
while (CIRCLEQ_FIRST(&cqueue_head))
CIRCLEQ_REMOVE_HEAD(&cqueue_head,cqueue_ptr);
CIRCLEQデータの操作sampleです。