链表
链表是存放和操作可变数量元素的数据结构，它可在需要时动态创建结点并插入链表中，在编译时不需知道包含多少个元素，而且它在内存中也无须占用连续内存区
linux 内核的双向链表
Linux内核里的双向链表和学校里教给我们的那种数据结构还是些不一样。Linux采用了一种更通用的设计，将链表以及其相关操作函数从数据本身进行剥离，这样我们在使用链表的时候就不用自己去实现诸如节点的插入、删除、遍历等操作了。
链表数据结构的定义
Linux也是从2.1.x内核开始才对链表进行了这样的统一
以Ubuntu为例,其list.h存放于 /usr/include/linux下.形如
链表的声明和初始化
list.h 中提供了两种初始化方式, 声明和声明并初始化.
其中的 LIST_HEAD() 声明一个链表头并初始化.如果我们想定义一个链表 chat_list
只需要 LIST_HEAD(chat_list)即可,展开后等价于
struct list_head chat_list = {&(chat_list), &(chat_list)};
如果我们已经有了一个链表对象 chat_list,可以直接使用 LIST_HEAD_INIT 初始化.
LIST_HEAD(chat_list) 和下面的代码是等价的
struct list_head chat_list;
INIT_LIST_HEAD(&chat_list);
链表的实现原理
内核有许多链表的实现，而且还有其官方内核实现，所以在内核中使用链表时只要学习下官方实现即可.
需要理解的是内核不是将数据结构插进链表，而是将链表节点插入数据结构，也就是说我们自己定义的每个结构体里面都含有一个 struct list_head 结构体成员，用其指向链表的下一个节点和上一个节点，它并没有把数据本身插入到链表中。
而我们其实只对数据感兴趣，对于 struct list_head 来说只是一个链接前后节点的工具，那么如何取其数据呢？内核实现是把每个 struct list_head 和一个数据节点挂勾(也就每个节点中包含struct list_head 的原因)，通过 list_entry() 宏即可通过 struct list_head 结构取包含其的节点数据。
链表节点的定义
假如我现在要定义一个聊天消息结构体,并让其组织成链表的形式,可以这样做:
链表基本的操作
list.h 提供添加节点的方法如下
同时list.h提供了头插法和尾插法的双向链表的操作
要想明白这是一个双向链表，这里的头插法和尾插法都是类比，单向链表的创建法，双向链表从一个方向遍历，这两种方法就和单向链表一样了，这里的尾插法虽然是在head左边添加的节点，不过从前往后遍历还是顺序的。（单向链表的头插法和尾插法的区别就是头插法是逆序，尾插法是顺序
list.h 提供了方便的判空操作
思考:
1 static和inline的作用
static修饰函数，表明这个函数属于静态函数，用来限制函数的作用域的，表名该函数只能在本文件内使用。
inline在中也是一个关键字，它对编译程序可见，当编译程序调用内联函数的时候就展开。一般内联函数需要声明和定义在一起才有效，一般放在头文件中
参考链接:
ubuntu: /usr/include/linux/list.h
阅读(1850) | 评论(0) | 转发(0) |
