linux内核双向链表源码分析

1. 双向链表定义:

在内核include/linux/types.h里定义了双向链表结构体类型:

Struct list_head

{

Struct list_head *next,*prev;

};

2. 链表处理

2.1:链表初始化:

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

#define LIST_HEAD(name)

struct list_head name = LIST_HEAD_INIT(name)

通过LIST_HEAD(list_name)宏申明并初始化

2.2:添加元素:

2.2.1:list_add(struct list_head *new, struct list_head *head)

在现存的head元素之后，紧接着插入new元素

static inline void __list_add(struct list_head *new,

struct list_head *prev,

struct list_head *next)

{

next->prev = new;

new->next = next;

new->prev = prev;

prev->next = new;

}

static inline void list_add(struct list_head *new, struct list_head *head)

{

__list_add(new, head, head->next);

}

2.2.2：list_add_tail(struct list_head *new, struct list_head *head)

在现存数据之前添加数据

static inline void list_add_tail(struct list_head *new, struct list_head *head)

{

__list_add(new, head->prev, head);

}

2.3删除数据:

static inline void __list_del(struct list_head * prev, struct list_head * next)

{

next->prev = prev;

prev->next = next;

}

static inline void list_del(struct list_head *entry)

{

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

entry->next = LIST_POISON1;

entry->prev = LIST_POISON2;

}

2.4．检测链表是否为空

static inline int list_empty(const struct list_head *head)

{

return head->next == head;

}

2.5. 合并两个链表

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;

}

static inline void list_splice(const struct list_head *list,

struct list_head *head)

{

if (!list_empty(list))

__list_splice(list, head, head->next);

}

2.6:查找链表元素:

#define list_entry(ptr, type, member)

container_of(ptr, type, member)