linuxカーネルが提供するリストの使い方について

linux

linuxカーネルではlinux/list.hでリストを提供している。
リストはlist_head構造体と、その構造体のオブジェクトを操作するための関数によって構成される。
list_head構造体は以下のように定義されているため、一見しただけでは任意のデータをリストとしてどのように使用すればいいのかわからない。

struct list_head {
	struct list_head *next, *prev;
};

以下にリストの使い方を説明する。

1. リストの要素となる構造体を宣言する。

linuxカーネルの提供するリストを使う場合には、リストの要素となる構造体を宣言する。
リストの要素となる構造体は、struct list_head型のオブジェクトをメンバーに持つ。
例えば、int型の変数idをリストで扱う場合には以下のように構造体を宣言する。

struct test_data {
	int no;
	struct list_head list;
};

2. リストを初期化する。

struct list_headのオブジェクトは、struct list_head型のポインタをメンバに持つ。
それらポインタを初期化して、リストを使えるようにするためには、INIT_LIST_HEADマクロを使用する。

例えば、struct test_data型のグローバル変数headを定義して、headをリストの要素として使用する場合には、
以下のようにして初期化する。

struct list_head head;

static int listtest_init(void)
{
        INIT_LIST_HEAD(&head.list);
        return 0;
}

初期化されたstruct list_head型オブジェクトのメンバは、それらメンバを所有するオブジェクトの先頭アドレスで初期化される。
上記の例では、&head.listで初期化される。

3. リストに要素を追加する

リストに要素を追加する場合には、list_addを使用する。
第一引数には、新しい要素のメンバで、struct list_head型オブジェクトへのポインタを指定する。
第二引数には、struct list_head型のオブジェクトへのポインタを指定する。
第一引数で指定したオブジェクトは、第二引数で指定したオブジェクトの後ろに連結される。

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
void list_add(struct list_head *new, struct list_head *head);

例えば、グローバル変数headに新しい要素を追加する場合には、以下のようにする。

struct list_head head;

static int listtest_init(void)
{
        struct test_data *ptr;
        struct test_data *new_data;

        INIT_LIST_HEAD(&head.list);
        new_data = kmalloc(sizeof(struct test_data), GFP_KERNEL);
        new_data->no = 1;
        list_add(&new_data->list, &head.list);
        return 0;
}

リストの一番後ろに挿入する場合には、list_add_tail()を使う事が出来る。

4. リストから要素を参照する

リストからデータを参照する場合には、list_entryマクロを使用する。
list_entryは以下のように定義されている。

/**
 * list_entry - get the struct for this entry
 * @ptr:        the &struct list_head pointer.
 * @type:       the type of the struct this is embedded in.
 * @member:     the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
        container_of(ptr, type, member)

第一引数はstruct list_head型のポインタで、取り出したい要素の持つstruct list_head型オブジェクトへのポインタを指定する。
第二引数には、要素の構造体の名前を指定する。
第三引数には、要素の構造体が持つstruct list_head型オブジェクトの名前を指定する。
list_entryで上記引数を指定すると、参照したい要素へのポインタが、戻り値として得られる。

例えば、headの次の要素(test_data型)へのポインタを取得する場合には以下のようにする。

struct list_head head;

static int listtest_init(void)
{
        struct test_data *ptr;
        struct test_data *new_data;

        INIT_LIST_HEAD(&head.list);
        new_data = kmalloc(sizeof(struct test_data), GFP_KERNEL);
        new_data->no = 1;
        list_add(&new_data->list, &head.list);
        ptr = list_entry(head.list.next, struct test_data, list);
        return 0;
}

list_entryは、gccの提供するoffsetofマクロによって、要素のポインタを取得している。
offsetofマクロは、指定したメンバが構造体の先頭から何バイト目に保存されているか調べ、そのオフセット値を返す。
list_entryの第一引数で、struct list_head構造体のオブジェクトがメモリ空間のどこに存在するかわかるため、
offsetofマクロと合わせることで、要素のアドレスを取得する事が出来る。

5. リストから要素を削除する

リストから要素を削除する場合には、list_delを使用する。
引数に削除したい要素のポインタを渡す。

struct list_head head;

static int listtest_init(void)
{
        struct test_data *ptr;
        struct test_data *new_data;

        INIT_LIST_HEAD(&head.list);
        new_data = kmalloc(sizeof(struct test_data), GFP_KERNEL);
        new_data->no = 1;
        list_add(&new_data->list, &head.list);
        ptr = list_entry(head.list.next, struct test_data, list);
        list_del(head.list.next);
        kfree(ptr);
        return 0;
}

list_delによって削除されたstruct list_head型オブジェクトのメンバは無効なアドレスを指すように更新される。

6. リストをループで処理する

リストを順番に辿って行き、順番に処理する場合にはlist_for_eachマクロを使う。
このマクロを使うと、for文のようにループ処理を書くことが出来る。

static void listtest_show_list(void)
{
        struct list_head *listptr;
        struct test_data *entry;
        printk(KERN_ALERT "show_list\n");
        list_for_each(listptr, &head.list) {
                entry = list_entry(listptr, struct test_data, list);
                printk(KERN_ALERT "no = %d (list %p, prev = %p, next = %p)\n", 
                       entry->no, &entry->list, entry->list.prev, entry->list.next);
        }
}

list_for_each以外にも、list_entryまで実行してくれるlist_for_each_entry等がある。