1. ホーム
  2. list

[解決済み] list_for_each_entry と list_for_each_entry_safe について説明する。

2022-02-07 15:57:15

質問

Linuxのlist_for_each_entryと...entry_safeループの動作を説明できる方いらっしゃいますか? それは次のようなものです。

list_for_each_entry(type *cursor, struct list_head *list, member)

list_for_each_entry_safe(type *cursor, type *next, struct list_head *list,member)

これらのパラメータはどのような役割を果たし、どのようにリストを走査するのに使われるのでしょうか。

ありがとうございました。

解決方法は?

EDIT: すみません、遅くなりました、誤字脱字が多いです。

純粋に楽しいんです! :) 違いは list_for_each_entry はリストを反復している間に何かを削除すると壊れてしまいますし list_for_each_entry_safe は、そうではありません(もちろん、いくつかの余分なCPU命令を犠牲にして)。

カーネルは2重リンクリストに落ち着きましたが(これはあなたが理解していると思いますが)、list.hには1重リンクリストの実装があります。

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

リストのquot;head"と各ノードには同じ構造体が使用されていることに注意してください。リストが空の場合、headの nextprev のメンバーは、単にhead自身を指しているに過ぎない。 したがって、リストの反復処理は、単にheadの next メンバと同じアドレスでない限り、そのメンバをノードと呼びます。 prev (停止するとき)です。 そうでなければ、あなたの for のボディが呼び出され container_of() マクロで実際の構造体へのポインタを取得し、それを使って遊びます。 そして、3番目のフィールドである for に移動し、次の next .

EDIT: おっと、失礼しました。パラメータの説明を求められていたのですね。 まあ、私があなただったら、誰かの言葉を鵜呑みにするのではなく、直接調べますね。 そのような場合、私は カーネル API ドキュメント 少なくともリンクリストライブラリについては存在します。 私は、赤黒木ライブラリにもそれを追加するパッチセットを通そうとしているのですが、何かを通すのはかなり大変な作業です。

また、注目すべきは http://kernelnewbies.org/FAQ/LinkedLists

簡単な例を挙げます。

struct list_head my_actual_list;
struct my_struct {
    struct list_head node;
    /* some other members */
};

/* in a function body somewhere... */
struct list_head *i;
list_for_each(i, &my_actual_list) {
    struct my_struct *obj = list_entry(i, struct my_struct, node);
    // do something with obj
}

list_entry の単なるエイリアスです。 container_of

EDIT #2

OK、ではコメントでの質問に対する答えですが、私の答えをそのまま拡大解釈します。C++のSTLコンテナやCの配列などと比べると、奇妙な点がいくつかあるので、この概念を理解するのが難しいのは事実ですが、イディオムに慣れれば、ごく自然に思えるようになります。将来的には、構造体や関数、マクロの定義を自分で調べて、理解してから質問することをお勧めします。

まず最初に、リストの各ノードは、型 struct list_head とリスト それ自身 は、型 struct list_head . したがって、この場合、誰がコンテナで誰が含まれるかは、単に使い方によるが、典型的には、これらのメンバに与えられた名前で表現される。 イテレータの型は struct list_head * . 以下はその例で、通常の関数 & マクロ呼び出しは、それに相当するコードに置き換えておきます。

struct my_container {
    struct list_head list;
    int some_member;
    /* etc. */
};

struct my_obj {
    struct list_head node;
    int some_member;
    /* etc. */
};

void func() {
    struct my_container container;
    struct my_obj obj1, obj2;
    struct list_head *i;

    /* INIT_LIST_HEAD(&container.list); */
    container.list.next = &container.list;
    container.list.prev = &container.list;

    /* list_add_tail(&obj1.node); */
    container.list.prev = &obj1.node;
    obj1.node.next = &container.list;
    obj1.node.prev = &container.list;
    container.list.next = &obj1.node;

    /* list_add_tail(&obj2.node); */
    container.list.prev = &obj2.node;
    obj2.node.next = &container.list;
    obj2.node.prev = &obj1.node;
    obj1.node.next = &obj2.node;

    /* list_for_each(i, &container.list) { */
    for (i = container.list.next; i != &container.list; i = i->next) {
        struct my_obj *obj = list_entry(i, struct my_obj, node);
        /* do stuff */
    }

}

さあ、読みに行こう! :)