如果想出发,就不要等到明天!
全部博文(317)
分类: LINUX
2014-11-05 18:10:23
原文地址:Linux内核【链表】整理笔记(1) 作者:wjlkoorey258
我们都知道Linux内核里的双向链表和学校里教给我们的那种数据结构还是些不一样。Linux采用了一种更通用的设计,将链表以及其相关操作函数从数据本身进行剥离,这样我们在使用链表的时候就不用自己去实现诸如节点的插入、删除、遍历等操作了。当然,Linux也是从2.1.x内核开始才对链表进行了这样的统一,和我们目前看到的样子几乎差不多:
点击(此处)折叠或打开
在2.6.21里这个数据结构定义在include/liinux/list.h头文件里,但是在3.4.1内核里,以及后面要介绍的哈希链表的定义都放在include/linux/types.h头文件里。而本文将以3.4.1内核为例进行介绍,其实对链表来说内核的版本号几乎没什么影响,只要掌握了Linux设计链表的精髓,万变不离其宗。
今天我们首先来聊聊链表。从上述定义代码我们可以看出,Linux内核的链表是双向链表,如果我们要将自己的数据结构以链表的形式进行组织,那么只要在我们自己的数据结构里,增加一个struct list_head{}类型的结构体成员对象就可以了,这样,我们就可以很方便地使用内核提供给我们的一组标准接口来对链表进行各种操作。
如果我们需要定义一个链表,内核有LIST_HEAD(name)这样的函数供我们使用:
点击(此处)折叠或打开
点击(此处)折叠或打开
点击(此处)折叠或打开
假如,我们现在要定义一个学生的结构体,并让其组织成链表的形式,可以这样做:
点击(此处)折叠或打开
点击(此处)折叠或打开
点击(此处)折叠或打开
有了数据节点,接下来就要对其进行操作了,内核提供了一组常用接口用于对双向链表操作,如下。
还有关于链表的分割list_cut_position(*list,*head,*entry)以及合并list_splice(*list,*head)、list_splice_init
(*list,*head)、list_splice_tail (*list,*head)、list_splice_tail_init
(*list,*head)这几个API用法也都非常简单,对照内核源码的注释很轻松就可以上手了。
需要注意的是,上述所有链表操作函数的入参都是struct list_head{}的指针类型,这一点需要时刻牢记在心。
未完,待续…