link_list

In general, we will implement Link list like this:

structure LinkNode {
    void *data;
     LinkNode *prev, *next;
};

But in kernel, the implementation is like this:

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

structure Foo {
     list_head list;
     int data;
};

並且透過container_of這個macro來找出原本的structure

linux kernel 的 linked list 滿足兩個需求:
1. linked list 內可裝任何資料;習慣 OO 的人可看成任何結構都可藉由包含 list_head 來實作 linked list
介面,使用 linked list 的 methods
2. 要裝的資料與 prev, next pointer 在記憶體中相鄰,幫助快取利用。假設我們不用 list_head 而以 void* 指向資料:

struct Node {
 Node *prev, *next
 void *data;
};

則需多一次不連續的記憶體 load,所以我們想要記憶體中長這樣:

struct Node {
 int field1, field2, field3, field4 ...;
 Node *prev, *next;
};
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License