爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!
爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!
当前所在位置:主页 > 脚本 > linux shell >
  • 魔艺客提供SEO\SEM推广整合营销服务
  • 提供整套互联网营销整合方案-魔艺客
  • 魔艺客高端网站建设开发服务十一大优惠服务
  • 资深的网站建设开发经验,一对一服务-魔艺客高
  • 一站式服务,从服务器到网站,三站何以尽在魔
爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!

Linux内核链表实现过程

发布时间:2017-09-08 19:17    作者:爱开发联盟    浏览:次    来源:aikaifa.com.cn 分享:

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

代码如下:

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)

网友评论

分类排行榜联系我们

好文推荐联系我们

爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!
爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!

当前最新内容联系我们

爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!

在线手册

网站地图导航

前端 HTML/Xhtml HTML5 CSS XML/XSLT Dreamweaver教程 Frontpage教程 心得技巧 编程 JavaScript ASP.NET PHP编程 正则表达式 AJAX相关 ASP编程 JSP编程 Flex 脚本加解密 web2.0 XML/RSS 网页编辑器 相关技巧 安全相关 网页播放器 Dart 其它综合 脚本 VBS DOS/BAT HTA HTC Python perl 游戏相关 vba 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 脚本下载 广告代码 js框架 批处理 网页相关 源码下载 数据库 MsSql Mysql mariadb oracle DB2 mssql2008 mssql2005 SQLite PostgreSQL MongoDB Redis Access 数据库文摘 数据库其它 CMS dedecms ecshop z-blog UcHome UCenter 风讯CMS 科汛cms discuz 新云cms phpwind 动易cms phpcms 帝国cms WordPress drupal 其它cms 设计 photoshop教程 摄影教程 Fireworks教程 CorelDraw教程 Illustrator教程 Painter教程 Freehand教程 Indesign 设计素材 平面其它 微信相关 微信公众号 小程序 操作系统 bios 系统安装 系统进程 Windows系列 LINUX RedHat/Centos Ubuntu/Debian Fedora Solaris 麒麟系统 红旗Linux Unix/BSD 苹果MAC 注册表 其它系统 网站运营 建站经验 微信营销 网站优化 网站策划 网络赚钱 网络创业 站长故事 alexa域名 其它相关 网络安全 黑客教程 安全设置 杀毒防毒 病毒查杀 脚本攻防 黑客入侵 工具使用 业界动态 Exploit 漏洞分析 加密解密 手机黑客 安全其它 在线手册 网页制作 脚本编程 数据库相关 软件编程 系统相关 其它相关 源码下载

友情链接申请加入

51CTO 上海魔艺客 猫鼬设计开发 Erlo网站开发 猫鼬设计工作室 新发现全球资讯 信息安全与IT资讯
爱开发联盟是国内专业的网站建设资源、脚本编程学习类网站,提供asp、php、asp.net、javascript、jquery、vbscript、dos批处理、网页制作、网络编程、网站建设等编程资料。让开发变得简单起来!

283882409