注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

学习笔记

正确的方法如同学习书法,开始的时候要临摹,临摹好了然后创造自己的风格。

 
 
 

日志

 
 

[Linux笔记]内核中的链表  

2011-06-08 16:52:11|  分类: Linux |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

自:Linux kernel development

1. Linux内核中链表的实现

       Linux内核使用了一种独一无二的方法遍历链表。在遍历链表时,从任何元素开始访问都可以!重要的是,要遍历每一个元素。其实,我们甚至可以抛开头节点和尾节点这些概念,如果环形链表包含的是一些无序数据的话,那么任何一个元素都可以作为头节点。遍历链表,仅仅需要从某个节点开始,沿指针访问下一个节点,直到又重新回到最初这个节点就可以了,因此并没需要一个指向链表中某个元素的指针——任何元素,就可操作链表了。

       链表在内核中的使用相当的频繁,其实任何其他复杂的程序都会用到它。比如内核就是用链表来存放任务队列的(每个进程的task_struct结构体都作为链表的一个元素)。

       链表结构体定义在文件<linux/list.h>中,形式很简单:

struct list_head{

       struct list_head *next , *prev;

};

 

#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->prev = list;

}

 

       注意list_head这个名字,它暗示了链表不存在头节点。但是由于可以从链表中的任何一个节点开始遍历,所以任何一个节点都可以起到头节点的效果,因此每个独立节点都可以被称作为链表头。指针next指向链表中的下一个元素,指针prev指向链表中的上一个元素。由于内核链表的实现方法没有用到链表头的概念,所以我们可以忽略首尾节点的概念。

       一个list_head结构体本身没有什么意义;通常需要把它嵌入到你自己的结构体中:

struct my_struct{

       struct list_head list;

       unsigned long dog;

       void *cat;

}

       链表在使用前需要先初始化。由于多数元素都是被动态的创建,所以常见的情况是,在运行时初始化链表。

struct my_struct *p;

/*分配my_struct*/

p->dog = 0;

p->cat = NULL;

INIT_LIST_HEAD(&p->list);

       如果在编译时静态创建链表,并且直接使用它,那么可以使用如下方法:

struct my_struct mine = {

       .list=LIST_HEAD_INIT(mine.list),

       .dog=0,

       .cat=NULL;

};

       直接声明并初始化一个静态链表:

static LIST_HEAD(fox);

       上述函数声明并初始化名为fox的静态链表。不需要与任何链表的内部成员打交道,你仅仅将链表结构插入到你自己的数据中就可以了,此后,你就可以使用链表提供的接口方便地操作和检索你的数据了。

 

2. 操作链表

       内核中提供了一组函数来操作链表,这些函数都要使用一个或多个list_head结构体指针来做参数。因为函数都是用C语言以内联函数形式实现的,所以它们的原形都在文件include/linux/list.h中。

       有趣的是,所有这些函数的复杂度都为O(1)。这意味着,无论这些函数操作的链表大小如何何,无论它们得到的参数如何,它们都会在恒定的时间内完成。

 

★list_add(struct list_head *new , struct list_head *head)

       该函数向指定链表head节点后插入new节点。因为链表是循环的,而且通常没有首尾节点的概念,所以你可以将任何节点传递给head。但是如果传递最后一个函数给head,那么该函数可以用来实现一个栈。

 

★list_add_tail(struct list_head *new , struct list_head *head)

       该函数向指定链表head节点前插入new节点。和list_add函数类似,因为链表是环形的,而且可以将任何节点传递给head。但是如果传递给第一个元素给head,那么, 该函数可以用来实现一个队列。

 

★list_del(struct list_head *entry)

       该函数从链表中删除entry元素。注意,该操作并不会释放entry或释放包含entry的数据结构所占用的内存;该函数仅仅是将entry元素从链表中移走,所以该函数被调用后,通常还需要再销毁包含entry的数据结构体和其中的entry项。

 

★list_del_init(struct list_head *entry)

       该函数除了还需要再次初始化entry以外,和list_del()函数类似。这样做是因为:虽然链表不再需要entry项,但是还可以再次使用包含entry的数据结构体。

 

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

       该函数从一个链表中摘除list项,然后再将其加入另一链表的head节点后。

 

★list_move_tail(struct list_head *list , struct list_head *head)

       该函数从一个链表中摘除list项,然后再将其加入另一链表的head节点前。

 

★list_empty(struct list_head *head)

       如果指定的链表为空,该函数返回非0值,否则返回0。

 

★list_splice(struct list_head *list , struct list_head *head)

       该函数合并两个链表,它将list指向的链表插入到指定链表中的head元素后。

 

★list_splice_init(struct list_head *list , struct list_head *head)

       该函数和list_splice()函数一样,唯一不同的是由list指向的链表要被重新初始化。

 

3. 遍历链表

       链表仅仅是个能够包含你重要数据的容器,我们必须利用链表移动并访问包含我们数据的结构体。内核为我们提供了一组非常有用接口,可以用来遍历链表和引用链表中的数据结构体。

       注意,和链表操作不同,遍历链表的复杂度为O(n)——n就是链表中所包含的元素数目。遍历链表最简单的方法是使用list_for_each()宏,该宏使用两个list_head类型的参数,第一个参数在链表中不断移动,直到链表中的所有元素都被访问为止。用法如下:

 

struct list_head *p;

list_for_each(){

       /*p指向链表中的元素*/

}

       虽然能够遍历链表,但仅仅能得到指向list_head结构体的指针是没有用的,我们所需要的是一个能够指向包含链表的结构体指针。比如前面例子中的my_struct结构体,我们需要的是一个能指向每个my_struct的指针,而不是一个指向其中链表中的指针。宏list_entry可以帮助我们取得包含list_head的结构体,它包含三个参数:一个是指向给定的链表元素的指针,一个是其中嵌入了链表的结构体类型引用,另一个是结构体中链表成员的名称。

       比如:

struct list_head *p;

struct my_struct *my;

 

list_for_each(p,mine->list){

       my=list_entry(p , struct my_struct , list);

       /*

        *     my指针指向嵌入链表的结构体

        */

}      

       list_for_each()宏扩展开来是一个简单的循环,比如上述语句扩展开来就是:

for(p=mine->list-next ; p!=mine->list; p=p->next)

       唯一与上面展开循环的不同的地方在于,宏list_for_each()还会使用处理器预取功能,如果处理器支持预取功能,那么该宏会预取链表中后续的项存入内存。如果不希望执行预取操作,可以使用__list_for_each()宏只实现简单的循环。但是除非你能确定链表很小或者是空的,否则都应该使用有预取功能的宏。还要注意,决不要使用循环硬编码,一定要使用内核提供的宏。
       如果需要向前遍历链表,可以使用list_for_each_prev()宏,该宏沿向前指针代替向后指针执行遍历。
       注意,在遍历链表时,没有什么特别的东西来阻止对链表执行删除操作。通常链表都需要用一些能避免并发访问的锁来保护。宏list_for_each_safe()使用临时存放的方法使得检索链表时不被删除操作破坏。
struct list_head *p , *n;

struct my_struct *my;

 

list_for_each_safe(p, n, mine->list){

       my=list_entry(p , struct my_struct , list);

       /*

        *     my指针指向嵌入链表的结构体

        */

}    

       注意,这个宏只能防止链表删除操作,为了防止并发访问实际的链表数据,应该使用其他的锁。

  评论这张
 
阅读(647)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018