«

Linux内核链表实现过程

时间:2024-3-2 15:38     作者:韩俊     分类: Linux


关于双链表实现,一般教科书上定义一个双向链表节点的方法如下:


struct list_node{
stuct list_node *pre;
stuct list_node *next;
ElemType data;
}

即一个链表节点包含:一个指向前向节点的指针、一个指向后续节点的指针,以及数据域共三部分。
但查看linux内核代码中的list实现时,会发现其与教科书上的方法有很大的差别。
来看看linux是如何实现双链表。
双链表节点定义

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

发现链表节点中根本就没有数据域,这样的链表有什么用?linux内核中定义这样的链表原因何在?
这是因为linux中是通过独立定义一个链表结构,并在结构体中内嵌一个链表节点来实现链表结构的。这样有一个好处就是能达到链表与结构体分离的目的。如此一来,我们构建好一个链表后,其结构示意图如下:

链表的定义及初始化宏定义:

#define LIST_HEAD_INIT(name){&(name),&(name)}
#define LIST_HEAD(name)
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do {
(ptr)->next = (ptr); (ptr)->prev = (ptr);
} while (0)

LIST_HEAD(name)宏用来定义一个链表头,并使他的两个指针都指向自己。我们可以在程序的变量声明处,直接调用LIST_HEAD(name)宏,来定义并初始化一个名为name的链表。也可以先声明一个链表,然后再使用INIT_LIST_HEAD来初始化这个链表。
也即:

LIST_HEAD(mylist);

struct list_head mylist;
INIT_LIST_HEAD(&mylist);

是等价的。

插入操作


/*仅供内部调用
  * Insert a new entry between two known consecutive entries.
  * This is only for internal list manipulation where we know
  * the prev/next entries already!
  */
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);
}
//在尾节点后插入一个节点
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}


删除操作

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);
}

删除链表节点的操作很简单,是通过将要删除的节点的前一个节点与后一个节点链接到一起。
链表节点替换操作

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;
}


链表遍历操作(重点在这里)
首先来看一个如何根据链表节点地址得到其所在结构体的地址。

#define list_entry(ptr, type, member) container_of(ptr, type, member)
//container_of宏的定义如下:
#define container_of(ptr, type, member)({
const typeof(((type *)0)->member ) *__mptr = (ptr);
(type *)( (char *)__mptr - offsetof(type,member) );})
//offsetof的宏定义如下:
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
将上述简化一下成为下面这样:
#define list_entry(ptr, type, member)
((type *)((char *)(ptr)-(size_t)(&((type *)0)->member)))

是一个带3个参数的宏,该宏的作用是获取链表节点(ptr)所在结构体的起始地址。有了这个宏,我们只要知道某一个链表节点指针,就可以通过该链表节点得到其所在结构体的指针,从而,我们遍历链表,也便可以达到遍历我们自己定义的结构体。第一个参数为一个地址,他是结构体链表节点元素的地址,第二个参数是结构体类型,第三个参数是链表节点元素在结构体中的名字。
来仔细分析一下这个宏:
最外面的一层括号可以去掉,这是为了防止宏扩展的,去掉如下:
(type *) ((char *)(ptr)-(size_t)(&((type *)0)->member))
现在就比较清楚了,首先(type *)是C强制转换操作,就是将后面的的数据转化成type结构的指针。而后面的操作可以再分解
(char *)(ptr) - (size_t)(&((type *)0)->member)
这样就是一个减法的操作,前面是一个指针,我们传过去的结构体链表节点元素的指针,这里被转化成指向字符的。而后面是一个整形,可以再分解
(size_t) (&((type *)0)->member)
显然这个整形是一个指针转化的,而这个指针又可以再分解,
&((type *)0)->member
可以看出这个指针是一个变量取地址得到的,这个变量又是什么呢
((type *)0)->member
看起来有点奇怪,不过这个操作是整个宏中最精妙的,他将地址0转化成type类型,接下来又取得这个结构的member元素,member就是我们传进来的参数:元素在结构体中的命名。其实((type *)0)->member取的变量是内容是什么一点都不重要,重要的我们要取这个变量的地址。取完这个地址将它转换成size_t类型,这样这个数据就是((type *)0)->member相对与地址0的偏移。回到上面的那个减法,将结构体中链表节点元素的地址与他与结构体首地址的偏移相减,不就得到了结构体的地址了吗。)(&((type *)0)->member)))
最外面的一层括号可以去掉,这是为了防止宏扩展的,去掉如下:
(type *) ((char *)(ptr)-(size_t)(&((type *)0)->member))
现在就比较清楚了,首先(type *)是C强制转换操作,就是将后面的数据转化成type结构的指针。而后面的操作可以再分解
(char *)(ptr) - (size_t)(&((type *)0)->member)
这样就是一个减法的操作,前面是一个指针,我们传过去的结构体元素的指针,这里被转化成指向字符的。而后面是一个长整形,可以再分解
(size_t) (&((type *)0)->member)
显然这个长整形是一个指针转化的,而这个指针又可以再分解,
&((type *)0)->member
可以看出这个指针是一个变量取地址得到的,这个变量又是什么呢?
((type *)0)->member
起来有点奇怪,不过这个操作是整个宏中最精妙的,他将地址0转化成type类型,接下来又取得这个结构的member元素,member就是我们传进来的参数:元素在结构体中的命名。其实((type *)0)->member取的变量是内容是什么一点都不重要,重要的我们要取这个变量的地址。取完这个地址将它转换成size_t类型,这样这个数据就是((type *)0)->member相对与地址0的偏移。回到上面的那个减法,将结构体中元素的地址与他与结构体首地址的偏移相减,便得到了结构体的地址了。
链表的遍历操作时通过一个宏来实现的:

#define list_for_each(pos, head)
for(pos = (head)->next, prefetch(pos->next);pos!=(head);
pos = pos->next,prefetch(pos->next))

其中prefetch是用于性能优化,暂时不用去管它。
从上述链表遍历宏可以看出,其只是一次获得了链表节点指针,在实际应用中,我们都需要获取链表节点所在结构体的数据项,因此,通常将list_for_each和list_entry一起使用。为此,linux的list实现提供了另外一个接口如下:

#define list_for_each_entry(pos, head, member)
for(pos = list_entry((head)->next, typeof(*pos), member);
prefetch(pos->member.next), &pos->member != (head);
pos = list_entry(pos->member.next, typeof(*pos), member))

有了这个接口,我们就可以通过链表结构来遍历我们实际的结构体数据域了。
例如,我们定义了一个结构体如下:

struct mystruct{
ElemType1 data1;
ElemType2 data2;
strcut list_head anchor;//通常我们称结构体内的链表节点为链表锚,因为它有定位的作用。
}

那么我们遍历链表的代码如下:

struct mystruct *pos;
list_for_each_entry(pos,head,anchor){
mystruct *pStruct=pos;
//do something with pStruct.....
}

此外Linux链表还提供了两个对应于基本遍历操作的"_safe"接口:list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member),它们要求调用者另外提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。
当然,linux链表不止提供上述接口,还有

list_for_each_prev(pos, head)
list_for_each_prev_safe(pos, n, head)
list_for_each_entry_reverse(pos, head, member)
list_prepare_entry(pos, head, member)
static inline int list_empty_careful(const struct list_head *head)
static inline void list_del_init(struct list_head *entry)
static inline void list_move(struct list_head *list, struct list_head *head)
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
static inline int list_empty(const struct list_head *head)

标签: linux

热门推荐