Linux内核链表

一、内核链表简介
链表是一种常用的数据结构，它通过指针将一系列数据节点连接成一条数据链。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。

二、内核链表结构

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

list_head结构包含两个指向list_head结构的指针
prev和next，由此可见，内核的链表具备双链表功能，实际上，通常它都组织成双向循环链表。

三、内核链表-函数
1.INIT_LIST_HEAD:创建链表
原型：void INIT_LIST_HEAD(struct list_head *list)
*list:要初始化的list指针地址。

#define LIST_HEAD_INIT(name) { &(name), &(name) }

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

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;                                //将list->next指向list
    list->prev = list;                                //将list->prev指向list
}

2. list_add：在链表头插入节点
原型：void list_add(struct list_head *new, struct list_head *head);
*new:新增加的链表结构
*head:需要新增的链表位置（后）

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries
 */
#ifndef CONFIG_DEBUG_LIST
static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    next->prev = new;                        //head的后面链表的prev指针指向new
    new->next = next;                        //new的next指向head的next结构地址
    new->prev = prev;                        //new的prev指向head的结构地址
    prev->next = new;                        //head的next指向new的结构地址
}
#else
extern void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next);
#endif

/**
 * 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.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

3. list_add_tail：在链表尾插入节点
原型：list_add_tail(struct list_head *new, struct list_head *head);
*new:新增的结构位置
*head:开始的位置

/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);                         //这里head->prev指向的就是最后的一个lis_head结构
}

4. list_del：删除节点
原型：void list_del(struct list_head *entry);
*entry需要删除的结构位置

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;                //把后面的指向前面的
    prev->next = next;                //把前面的指向了后面的
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
#ifndef CONFIG_DEBUG_LIST
static inline void __list_del_entry(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
}

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}
#else
extern void __list_del_entry(struct list_head *entry);
extern void list_del(struct list_head *entry);
#endif

5. list_entry：取出节点
原型：list_entry(ptr, type, member);
ptr:链表中某个成员的list_head的位置
type:链表中内嵌的结构，用户自己的
member:用户结构中的list_head的成员名字

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:    the pointer to the member.
 * @type:    the type of the container struct this is embedded in.
 * @member:    the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({            \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})


/**
 * 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)

6. list_for_each：遍历链表
原型：list_for_each(pos,head)
pos：搜索的到位置
head：起始位置

/**
 * list_for_each    -    iterate over a list
 * @pos:    the &struct list_head to use as a loop cursor.
 * @head:    the head for your list.
 */
#define list_for_each(pos, head) \
    for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            pos = pos->next)

四、代码编写学习
mylist.c

#include <linux/init.h>
#include <linux/module.h>
#include <linux/list.h>

struct score
{
    int num;
    int english;
    int math;
    struct list_head list;
};

struct list_head score_head;
struct list_head *pos;
struct score stu1,stu2,stu3;
struct score *tmp;

static int mylist_init()
{
    /*初始化链表*/
    INIT_LIST_HEAD(&score_head);

    stu1.num = 1;
    stu1.english = 90;
    stu1.math = 89;
    /*将链表连入score_head尾部*/
    list_add_tail(&(stu1.list), &score_head);

    stu2.num = 2;
    stu2.english = 92;
    stu2.math = 91;
    list_add_tail(&(stu2.list), &score_head);

    stu3.num = 3;
    stu3.english = 94;
    stu3.math = 95;
    list_add_tail(&(stu3.list), &score_head);
    /*遍历链表*/
    list_for_each(pos, &score_head)
    {
        /*找到链表对应的结构体节点*/
        tmp = list_entry(pos, struct score, list);
    printk("No %d, english is %d, math is %d\n",tmp->num,tmp->english,tmp->math);
    }

    return 0;
}

static void mylist_exit()
{
    list_del(&(stu1.list));
    list_del(&(stu2.list));
}

module_init(mylist_init);
module_exit(mylist_exit);