首页 > 代码库 > linux内核中对双向链表的操作函数
linux内核中对双向链表的操作函数
在linux内核中用的非常多的一种链表是：双向链表。内核中对所用的进程的管理就是通过双向链表来实现的。所以对链表的操作非常的常用也非常的重要，因此内核通过提供一个通用的方法来帮助我们方便的对双链表实现各种操作。
struct list_head {struct list_head *next, *prev;}
0,对双向链表中的某个项进行初始化操作的函数： INIT_LIST_HEAD(struct list_head *entry)
INIT_LIST_HEAD()的实现方法：
static inline void INIT_LIST_HEAD(struct list_head *entry)
{
entry->next = entry;
entry->prev = entry;
}
1,双向链表头节点的初始化操作：LIST_HEAD(name);
LIST_HEAD 的实现方法：
#define INIT_LIST_HEAD(name) {&(name),&(name)}
#define LIST_HEAD(name) \
struct list_head name = INIT_LIST_HEAD(name)
来看看如何使用：
static int __init list_head_init(void)
{
LIST_HEAD(name);
}
上面的代码在编译时，会被编译器翻译成如下的形式代码：
static int __init list_head_init(void)
{
struct list_head name = {&name,&name};
}
2,双向链表的头部添加元素操作: list_add(struct list_head *new, struct list_head *head)
list_add()函数用于实现向双向链表的头节点后面添加一个元素，可以用来实现数据结构中的栈的操作，每次添加一个新的数据到栈的顶部；
list_add(struct list_head *new, struct list_head *head)的实现方法：
static inline void list_add(struct list_head *new, struct list_head *head)
{ __list_add(new, head,head->next);}
从面向对象的角度来看：list_add是对__list_add的封装，所以来看看__list_add是怎么通过对双向链表的操作来实现入栈操作的。
static inline void __list_add(struct list_head *new, struct list_head *prev,
struct list_head *next)
{
new->next = next; // new->next 指向双向链表中的原第一个节点；
new->prev = prev; // new->prev 指向双向链表的头节点；
prev->next = new; // 双线链表的头节点指向new节点；
next->prev = new; // 双向链表的原第一个节点指向new节点；
}
3,双向链表的尾部添加元素的操作：list_add_tail(struct list_head *new,
struct list_head *head)
list_add_tail()函数用于实现向双线链表的尾部添加一个元素，可以用于实现数据结构中的队列操作，每次添加一个新的数据到队列的尾部；
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);}
同样 list_add_tail()也是对l __list_add()的封装；
4,用于删除双向链表中的某个数据的操作： list_del(struct list_head *entry)
static list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = NULL;
entry->prev = NULL;
}
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
prev->next = next;
next->prev = prev;
}
5, 删除双向链表中某个节点并对其进行初始化：list_del_init(struct list_head *entry)
static inline void list_del_init(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry); // 等价于 entry->next = entry; entry->prev = entry;
}
6, 用一个新的数据代替双向链表中的某个旧的数据：list_replace(struct list_head *old,
struct list_head *new)
static inline void list_replace(struct list_head *old, struct list_head *new)
{
new->next = old->next;
new->prev = old->prev;
old->next->prev = new;
old->prev->next = new;
}
7,用一个新的数据代替双向链表中的某个旧的数据并对旧的数据进行初始化：
static inline list_replace_init(struct list_head *old, struct list_head *new)
{
list_replace(old, new);
INIT_LIST_HEAD(old);
}
8,将双向链表中的某个数据移到另一个双向链表的第一个元素之前：
static inline void list_move(struct list_head *entry, struct list_head *head)
{
__list_del(entry->prev, entry->next); // 将entry从双向链表中删除；
list_add(entry, head); // 将entry 加入到head双向链表中；
}
9,将双向链表中的某个数据移动到另一个双向链表的尾部：
static inline void list_move_tail(struct list_head *entry, struct list_head *head)
{
__list_del(entry->prev, entry->next) ;
list_add_tail(entry,head);
}
10,测试一个双向链表是否为空: list_empty(struct list_head *head)
static inline int list_empty(struct list_head *head)
{
return head->next == head;
}
可知：如果链表为空的话， list_empty()返回 1，否则返回 0；
11,测试一个双向链表中的某个数据是否是在双向链表的末尾：
static inline list_is_last(struct list_head *entry, struct list_head *head)
{
return entry->next == head;
}
可知：如果一个数据是在双向链表的末尾，那么list_is_last()返回 1， 否则返回 0；
12,将一个双向链表从其中的某个项切开，将其分割成两个单独的双向链表：
static inline void list_cut_position(struct head_list *list, struct head_list *entry,
struct head_list *head);
参数说明： list 是从head双向链表中分割出来的链表的头部；
entry 是双向链表head的分割点；
list_cut_position()是对 static inline void __list_cut_position()的封装；
来看看 __list_cut_position()是如何对双向链表进行切割的：
static inline void __list_cut_position(struct list_head *list,struct list_head *entry,
struct list_head *head)
{
struct list_head *new_first = entry->next; // 确定entry的后面数据；
list->next = head->next ; // list 指向原head双向链表中的第一项；
list->next->prev = list; // 原head双向链表中的第一项指向list；
list->prev = entry;
entry->next = list;
head->next = new_first;
new_first->prev = head;
}
总结一下：LIST_HEAD(entry);
INIT_LIST_HEAD(struct list_head *entry);
list_add(struct list_head *new, struct list_head *head);
list_add_tail(struct list_head *new, struct list_head *head);
list_del(struct list_head *entry);
list_del_init(struct list_head *entry);
list_replace(struct list_head *old, struct list_head *new);
list_replace_init(struct list_head *old, struct list_head *new);
list_move(struct list_head *entry, struct list_head *head);
list_move_tail(struct list_head *entry, struct list_head *head);
list_empty(struct list_head *head);
list_is_last(struct list_head *entry, struct list_head *head);
list_cut_position(struct list_head *list, struct list_head *entry,
struct list_head *head);
本文出自 “阿辉仔” 博客，请务必保留此出处http://weiguozhihui.blog.51cto.com/3060615/1565131
linux内核中对双向链表的操作函数