• linux kernel中的list估計(jì)已經(jīng)被各位前輩們寫爛了,但是我還是想在這里記錄一下;
• linux kernel里的很多數(shù)據(jù)結(jié)構(gòu)都很經(jīng)典, list鏈表就是其中之一
• 本篇要介紹的內(nèi)容:
  1. list的定義
  2. list提供的操作方法
  3. 注意事項(xiàng)
  4. 使用實(shí)例

List 所在文件:

• List的所有操作可以在 include/linux/list.h找到;
• List head的定義可以在 include/linux/types.h找到;

定義

• 實(shí)際上這就是一個(gè)雙向循環(huán)鏈表, 且有一個(gè)頭指針
• list head的定義:

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

• 這個(gè)定義中只有前向和后向指針,沒任何的數(shù)據(jù)部分, 那我們基本上就知道了, 它不是被單獨(dú)使用的,而是把它嵌入到用戶定義的struct中, 將用戶定義的數(shù)據(jù)結(jié)構(gòu)串起來(lái),作成list;
• 思想很巧妙, 對(duì)用戶定義的數(shù)據(jù)結(jié)構(gòu)侵入性很小, 實(shí)現(xiàn)了c++中std::List模板的功能;
• 雖然這個(gè)定義是叫head, 但其實(shí)嵌入到用戶定義的數(shù)據(jù)結(jié)構(gòu)中的也是這個(gè).

初始化

// 靜態(tài)初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

// 調(diào)用INIT_LIST_HEAD來(lái)初始化, **WRITE_ONCE**這個(gè)后面我們專門介紹
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    WRITE_ONCE(list->next, list);
    list->prev = list;
}

插入操作

• 將一個(gè)元素插入到兩個(gè)元素之間, 即將 new插入到prev和next中, 這個(gè)函數(shù)是下面在頭部和尾部插入的實(shí)現(xiàn)基礎(chǔ)

static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    if (!__list_add_valid(new, prev, next))
        return;

       // 前后向指針的改寫賦值
    next->prev = new;
    new->next = next;
    new->prev = prev;
    WRITE_ONCE(prev->next, new);
}

• 在頭部插入, 在頭指針和第一個(gè)元素間插入

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

• 在尾部插入,在最后一個(gè)元素間和頭指針間插入, 因?yàn)槭茄h(huán)鏈表嘛~

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

刪除操作

• 刪除兩個(gè)元素之間的元素

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    WRITE_ONCE(prev->next, next);
}

• 刪除一個(gè)已知元素entry

static inline void __list_del_entry(struct list_head *entry)
{
    if (!__list_del_entry_valid(entry))
        return;

    __list_del(entry->prev, entry->next);
}

替換操作

都是指針的變換

static inline void list_replace(struct list_head *old,
                struct list_head *new)
{
    new->next = old->next;
    new->next->prev = new;
    new->prev = old->prev;
    new->prev->next = new;
}

移動(dòng)操作

• 將一個(gè)元素移動(dòng)到另一個(gè)list的頭部

static inline void list_move(struct list_head *list, struct list_head *head)
{
       // 從原處的list后摘掉
    __list_del_entry(list);
       // 添加到新鏈表的頭部
    list_add(list, head);
}

• 將一個(gè)元素移動(dòng)到另一個(gè)list的隊(duì)尾

static inline void list_move_tail(struct list_head *list,
                  struct list_head *head)
{
       // 從原處的list后摘掉
    __list_del_entry(list);
       // 添加到新鏈表的隊(duì)尾
    list_add_tail(list, head);
}

拆分操作, 將一個(gè)隊(duì)列由指定的位置拆成兩個(gè)隊(duì)列

list是新隊(duì)列的head指針, 包括的元素從原h(huán)ead隊(duì)列的第一個(gè)元素到entry, head隊(duì)列僅包括余下的元素

static inline void __list_cut_position(struct list_head *list,
        struct list_head *head, struct list_head *entry)
{
    struct list_head *new_first = entry->next;
    list->next = head->next;
    list->next->prev = list;
    list->prev = entry;
    entry->next = list;
    head->next = new_first;
    new_first->prev = head;
}

合并操作:

• 將list列表中除了list本身插入到prev和next之間

static inline void __list_splice(const struct list_head *list,
                 struct list_head *prev,
                 struct list_head *next)
{
    struct list_head *first = list->next;
    struct list_head *last = list->prev;

    first->prev = prev;
    prev->next = first;

    last->next = next;
    next->prev = last;
}

• 將一個(gè)列表插入到另一個(gè)列表的頭部

static inline void list_splice(const struct list_head *list,
                struct list_head *head)
{
    if (!list_empty(list))
        __list_splice(list, head, head->next);
}

• 將一個(gè)列表插入到另一個(gè)列表的尾部

static inline void list_splice_tail(struct list_head *list,
                struct list_head *head)
{
    if (!list_empty(list))
        __list_splice(list, head->prev, head);
}

list_entry宏

按之前說(shuō)的, 這個(gè)list_head都有要嵌入到用戶定義的struct中,這個(gè)宏就是由這個(gè)list_head ptr來(lái)獲取當(dāng)前所處的struct對(duì)象的指針, 用了linux的經(jīng)典宏定義 container_of

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

一堆宏定義, 用來(lái)各種遍歷, 獲取entry

注意事項(xiàng)

• 只說(shuō)一個(gè),就是多線程操作同一個(gè)list, 還是需要加鎖

使用實(shí)例

typedef struct _Foo {                              
    int data_;                                     
    struct list_head link;                         
} Foo;                                             
                                                   
int main(int argn, char* argv[]) {                 
    LIST_HEAD(test_link);                          
                                                   
    Foo f1;                                        
    f1.data_ = 1;                                  
    LIST_HEAD_INIT(f1.link);                       
                                                   
    Foo f2;                                        
    f1.data_ = 2;                                  
    LIST_HEAD_INIT(f2.link);                       
                                                   
    list_add(&f1.link, &test_link)                 
    list_add(&f2.link, &test_link)                 
                                                   
    struct Foo* pos;                               
    list_for_each_entry(pos, &test_link, link) {   
        printf("%d\n", pos->data_);                
    }                                              
                                                   
    return 0;                                      
}