キューは先に入れたデータが、先に出てくるデータ構造であり、First In, First Out(FIFO)と呼ばれる事もあります。また特殊なキューとして優先順位付きキュー[priority queue]などがあります。
Simple queueの構造
キューは先に入れたデータが、先に出てくるデータ構造であり、First In, First Out(FIFO)と呼ばれる事もあります。また特殊なキューとして優先順位付きキュー[priority queue]などがあります。
SIMPLEQ構造を使用するには、まずSIMPLEQ形式のデータ構造を定義する必要があります。
SIMPLEQ_ENTRYはSIMPLEQ形式のデータ構造を定義します。 各エレメントに数字が１つだけ入っているSIMPLEQ構造、SimpleQを定義してみると、下記のようになります。
struct SimpleQ {
SIMPLEQ_ENTRY(SimpleQ) squeue_ptr;
int32_t data;
};
これは、次のように展開されます。
struct SimpleQ {
struct {
struct SimpleQ *sqe_next;
} squeue_ptr;
int32_t data;
};
これは定義だけで、まだ実体は無いことに注意してください。
SIMPLEQ_HEADは、エレメントの先頭アドレスが入る構造体を定義します。
SIMPLEQ_HEAD(SimpleQHead, SimpleQ);
これは、次のように展開されます。
struct SimpleQHead { struct SimpleQ *sqh_first; struct SimpleQ **sqh_last; };
これも定義だけで、まだ実体は無いことに注意してください。
SIMPLEQ_HEAD_INITIALIZERは、SIMPLEQ_HEADを初期化します。次のように使用します。
// SIMPLEQヘッダの実体を定義
struct SimpleQHead squeue_head = SIMPLEQ_HEAD_INITIALIZER(&squeue_head);
SIMPLEQ_INITは、SIMPLEQを初期化します。次のように使用します。
if(!(SIMPLEQ_EMPTY(&squeue_head))) // SIMPLEQが空であるかチェック SIMPLEQ_INIT(&squeue_head); // SIMPLEQの初期化
SIMPLEQ_FIRSTは、SIMPLEQの先頭エレメントのポインタを返します。
arithmetic = SIMPLEQ_FIRST(&squeue_head);
SIMPLEQ_ENDは、NULLを返します。
SIMPLEQ_EMPTYは、SIMPLEQが空か調べます。
SIMPLEQ_NEXTは、エレメント(elm)に連結されている次エレメントのポインタを返します。
arithmetic_next = SIMPLEQ_NEXT(arithmetic,squeue_ptr);
SIMPLEQ_INSERT_HEADは、新しいエレメント(elm)をSIMPLEQ(head)の先頭に追加します。
for(i=0;i<5;i++){
number[i].data = i;
number[i].squeue_ptr.sqe_next = NULL;
}
SIMPLEQ_INSERT_HEAD(&squeue_head, &number[0], squeue_ptr); // 先頭に追加
SIMPLEQ_INSERT_AFTERは、指定したエレメント(listelm)の後に、新しいエレメント(elm)を追加します。
SIMPLEQ_INSERT_AFTER(&squeue_head,&number[0],&number[1],squeue_ptr); // 後ろに追加
結果は次のようになります。
SIMPLEQ_INSERT_TAILは、新しいエレメント(elm)をSIMPLEQ(head)の一番最後に追加します。
SIMPLEQ_INSERT_TAIL(&squeue_head,&number[2],squeue_ptr); // 最後に追加
結果は次のようになります。
SIMPLEQ_FOREACHは、headに格納されたエレメントを最初から終りまでループして、varにポインタを返します。
// エレメントの最初から終わりまでループ
SIMPLEQ_FOREACH(arithmetic, &squeue_head, squeue_ptr){
printf("%d\n",arithmetic->data);
}
結果は、下記のようになります。
0
1
2
SIMPLEQ_REMOVE_HEADは、SIMPLEQ(head)の先頭エレメントを削除します。
// エレメントが空になるまで削除します
while (SIMPLEQ_FIRST(&squeue_head))
SIMPLEQ_REMOVE_HEAD(&squeue_head,squeue_ptr);
SIMPLEQデータの操作sampleです。