内核中链表(Linked List)的实现

• • • • 前言
      • 比较简单的链表
      • linux 内核中双向链表的实现
      • 内核中链表的使用
      • 自己手写的链表实验

前言

内核中链表是比较简单的数据结构，通过两个指针元素实现双向链表。
链表相比其他数据结构的优点是不占用连续的内存，可以动态的插入和删除节点。

比较简单的链表

链表中前后指针元素和数据元素在同一个结构体中。通过指针可以直接找到数据。

单向链表

    struct  list_element {
        void *data;
        struct list_element *next;
    }

双向链表

    struct  list_element {
        void *data;
        struct list_element *next;
        struct list_element *prev;
    }

linux 内核中双向链表的实现

linux 内核中的链表数据结构中存放的是链表节点，而不是数据节点，通过链表指针来查找数据元素。

存放数据的结构体

    struct fox { 
            unsigned long tail_length; /* length in centimeters of tail */ 
            unsigned long weight; /* weight in kilograms */ 
            bool is_fantastic; /* is this fox fantastic? */ 
            struct list_head list; /* list of all fox structures */
    };

存放链表指针的结构体

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

container_of()宏

链表数据结构中只存放 list_head 类型的数据结构，那么怎么通过 list_head 元素得到所在的数据呢，通过container_of()宏,使用 list_head 的地址已经数据元素的偏移量来获取数据内容

#define container_of(ptr, type, member) 
({ \const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})

强制转换 ptr 格式，ptr 是 list_head 地址，type fox 结构体的类型,类型不同偏移量可能不同，Member list_head 的名字

上述内核代码在 linux/list.h 中声明

内核中链表的使用

下面是内核中一些已经定义好的增删便利的函数。

static LIST_HEAD(fox_list);

list_add(struct list_head *new, struct list_head *head)
list_add(&f->list, &fox_list);
list_add_tail(struct list_head *new, struct list_head *head)

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

list_move(struct list_head *list, struct list_head *head)

struct list_head *p; 
struct fox *f;
list_for_each(p, &fox_list) { 
/* f points to the structure in which the list is embedded */ 
f = list_entry(p, struct fox, list);
}

自己手写的链表实验

#include <stddef.h>
#include <stdio.h>

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

struct fox {
        unsigned long l; /* length in centimeters of tail */
        int w; /* weight in kilograms */
        struct list_head list;
        char asd;
};

struct dog {
        int a ;
        int b ;
        struct list_head dogList;
};

static void add_list(struct list_head *new,struct list_head *head){
        new->next = head->next;
        head->next->prev = new;
        head->next = new;
        new->prev = head;

}

#define container_of(ptr,type,member) ({       \
        const typeof (((type *)0)->member) *_mptr = (ptr);    \
        (type *)((char *)_mptr - offsetof(type,member)) ;       \
})


/* static inline struct list_head  LIST_HEAD_INIT(struct list_head list){
        list.next = &list;
        list.prev = &list;
        return list;
}
*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }


int main() {

        struct fox fox1 = {
                .l = 40,
                .w = 20,
                .list = LIST_HEAD_INIT(fox1.list),
        };
        struct dog wang = {1,2,LIST_HEAD_INIT(wang.dogList)};
        add_list(&wang.dogList,&fox1.list);
        printf("%lx\n",(long)&fox1);
        printf("%lx\n",(long)&fox1.list);
        printf("%ld\n",(long)sizeof(struct fox));
        printf("%lx\n",(long)container_of(&fox1.list,struct fox,list));
        printf("%lx\n",(long)container_of(fox1.list.next,struct dog,dogList));
        printf("%d\n",(container_of(fox1.list.next,struct dog,dogList))->b);
        return 0;
}