Singly-linked List(SLIST)

単方向リスト[Singly-linked List]は、データの一部に次データのポインターをもつデータ形式で、データをポインターにより連結させたデータ形式です。この形式のデータは、各データのポインタを操作するだけで、データの追加や追加が出来るので、配列に比べ比較的簡単にデータの操作が可能になります。

単方向リストの構造

SLIST 構造体の定義

SLIST構造を使用するには、まずSLIST形式のデータ構造を定義する必要があります。

SLIST_ENTRY(type)

SLIST_ENTRYは、SLIST形式のデータ構造を定義します。各エレメントに数字が１つだけ入っているSLIST構造、Slistsを定義してみると、下記のようになります。

struct  Slists {
    SLIST_ENTRY(Slists) slist_ptr;
                       int32_t  data;
};

これは、次のように展開されます。

struct Slists {
    struct {
	struct Slists *sle_next;
    } list;
                       int32_t data;
};

これは定義だけで、まだ実体は無いことに注意してください。

SLIST_HEAD(name, type)

SLIST_HEADは、エレメントの先頭アドレスが入る構造体を定義します。

SLIST_HEAD(SlistsHead, Slists);

これは、次のように展開されます。

struct SlistsHead { struct Slists *slh_first; };

これも定義だけで、まだ実体は無いことに注意してください。

SLIST 構造体の初期化

SLIST_HEAD_INITIALIZER(head)

SLIST_HEAD_INITIALIZERは、SLIST_HEADを初期化します。次のように使用します。

// SLISTヘッダの実体を定義
struct SlistsHead slists_head = SLIST_HEAD_INITIALIZER(&slists_head);

SLIST_INIT(head)

SLIST_INITは、SLISTを初期化します。次のように使用します。

if(!(SLIST_EMPTY(&slists_head)))         // SLISTが空であるかチェック
    SLIST_INIT(&slists_head);            // SLISTの初期化

SLIST Access Methods

SLIST_FIRST(head)

SLIST_FIRSTは、SLISTの先頭エレメントを返します。

arithmetic = SLIST_FIRST(&slists_head);

SLIST_END(head)

SLIST_ENDは、NULLを返します。

SLIST_EMPTY(head)

SLIST_EMPTYは、SLISTが空であるか調べます。

SLIST_NEXT(elm, field)

SLIST_NEXTは、エレメント(elm)に連結されている次エレメントを返します。

arithmetic_next = SLIST_NEXT(arithmetic,list_ptr);

SLIST Insert Methods

SLIST_INSERT_HEAD(head, elm, field)

SLIST_INSERT_HEADは、新しいエレメント(elm)をSLIST(head)に追加します。

// データ作成
for(i=0;i<5;i++){
    number[i].data = i;
}
// 作成したデータをslistにセット
for(i=1;i<4;i++){
    SLIST_INSERT_HEAD(&slists_head, &number[i], slist_ptr);
}

この結果は、次のようになります。

SLIST_INSERT_HEADの結果

SLIST_INSERT_AFTER(slistelm, elm, field)

SLIST_INSERT_AFTERは、指定されたエレメント(slistelm)の後に、新しいエレメント(elm)を追加します。

SLIST_INSERT_AFTER(&number[1],&number[0],list_ptr); // 1の後ろに0を挿入

この結果は、1の後ろに0が追加されます。

SLIST_INSERT_AFTERの結果

SLIST Loop Methods

SLIST_FOREACH(var, head, field)

SLIST_FOREACHは、headに格納されたエレメントを最初から終りまでループして、varにポインタを返します。

// エレメントの最初から終わりまでループ
SLIST_FOREACH(arithmetic, &slists_head, list_ptr){
   printf("%d\n",arithmetic->data);
}

結果は、下記のようになります。

SLIST_FOREACH_PREVPTR(var, varp, head, field)

SLIST_FOREACH_PREVPTRは、headに格納されたSLISTエレメントを最初から終りまでループして、varにポインタを返します。そしてvarpに前エレメントのポインタを返します。

SLIST_FOREACH_PREVPTR(arithmetic,arithmetic_prev,&slists_head,slist_ptr){
    printf("0x%x 0x%x\n",arithmetic,arithmetic_prev);
}

結果は、下記のようになります。

0xcfbf1c44 0xcfbf1c1c
0xcfbf1c3c 0xcfbf1c44
0xcfbf1c34 0xcfbf1c3c
0xcfbf1c2c 0xcfbf1c34

SLIST Remove Methods

SLIST_REMOVE_NEXT(head, elm, field)

SLIST_REMOVE_NEXTは、指定されたエレメント(elm)の次エレメントを削除します。

arithmetic      = SLIST_FIRST(&slists_head);               // 最初のエレメント (data=3)
arithmetic_next = SLIST_NEXT(arithmetic,slist_ptr);        // 次エレメント(data=2)
SLIST_REMOVE_NEXT(&slists_head,arithmetic_next,slist_ptr); // 指定エレメントの次エレメント(data=1)を削除

この結果は、1が格納されているデータが削除されます。

SLIST_REMOVE_NEXTの結果

SLIST_REMOVE(head, elm, type, field)

SLIST_REMOVEは、指定されたエレメント(elm)をSLIST(head)から削除します。

SLIST_REMOVE(&slists_head,arithmetic_next,Slists,list_ptr);   // 指定したエレメント(data=2)を削除

この結果は、2が格納されているデータが削除されます。

SLIST_REMOVEの結果

SLIST_REMOVE_HEAD(head, field)

SLIST_REMOVE_HEADは、先頭エレメントを削除します。

// 空になるまで削除
while(!(SLIST_EMPTY(&slists_head)))
    SLIST_REMOVE_HEAD(&slists_head,slist_ptr); // 先頭エレメントを削除