本文会记录一些linux内核实现中使用到的一些小技巧,工具等等,会根据学习进度不定时更新本文......
双向循环链表
第一个想写的是linux的双向循环链表(写这个的原因是因为最近学习epoll的内核代码实现,进而需要了解linux的等待队列,这其中也用到了双向循环链表,稍后也会分析linux的等待队列)
linux的双向循环链表之于传统的双向循环链表,其优点是:将其从具体的数据结构中提取出来构成一种通用的循环链表实现,在linux中表现形式为:
struct list_head {
struct list_head * prev , * next;
}
其常见的使用方法为:若要定义某种特定类型的数据结构的双向循环链表,只需要在结构中包含该struct list_head ,就可以将各个对象链接起来;当对数据结构进行操作(增,删......)的时候,只需要设计针对struct list_head这种通用结构的通用接口即可,不用针对每种具体对象设计不同的接口
典型的结构如下(暂时不会作图,先盗用了等待队列的实现图):
一般实现一个具体对象的双向循环链表的时候会有一个头节点,只含有struct list_head(假设为struct list_head head;),没有具体对象的信息,若要判断是否队列为空,则只需判断head->prev==head (head->netx == head);具体实现如下:
static inline int list_empty(const struct list_head * head){
return head->next == head;
}
另一个比较很重要的操作就是通过list_head成员获取宿主对象的指针了,这个主要用到了宏:offsetof,container_of
#define offsetof(s,m) (size_t)&(((s *)0)->m)
//s为结构体,m为结构体中的成员,将地址0强制转换为对应的结构体类型,
//而成员m所在的地址减去结构体起始位置即为m在结构体中偏移量,
//此处基地址为0,则成员m所在地址即为偏移量
#define container_of(ptr, type, member) ({ /
const typeof( ((type *)0)->member ) *__mptr = (ptr); /
(type *)( (char *)__mptr - offsetof(type,member) );})
//作用:获得某成员所在结构体的入口地址
//实现:type为结构题的类型,member为结构体中的一个成员,
// ptr为指向成员member所属变量类型的一个变量的指针
// 故技重施,(type *)0将地址0强制转换为type结构体类型的地址,
// typeof( ((type *)0->member)获得了member的类型,
// 接着typeof( ((type *)0->member) * __mptr申明了一个该类型的变量并初始化为ptr的地址;
// (char *)__mptr将刚刚的地址转换为char* ,offsetof计算出了member成员在结构体中的偏移量,
// __mptr减去这个偏移刚好就是结构体的起始地址,然后用(type *)强制转换为相应的指针
l
有关等待队列的数据结构稍后补充......
本文出自 "流离and逍遥" 博客,请务必保留此出处http://liulixiaoyao.blog.51cto.com/1361095/535427
分享到:
相关推荐
linux内核链表的实现,包括内核链表的定义,以及内核链表相关的操作
使用Linux内核链表实现多客户端连接服务器,里面有三种功能,1、TCP多人连接客户端,服务器可以把信息发给多个用户;2、TCP多人连接客户端,可以把信息发给指定的某个用户;3、服务器接收多个客户端传送过来的文件。
linux内核链表源代码,是list.h是链表的实现,有兴趣的朋友可以下载分析。
将linux内核源码中list.h拿出来, 增删与遍历部分写了详细注释, 关于链表合并, 没用过所以没写. 源码版本是2.6.32, 不过链表的源码改动应该不是很大. 我的邮箱2253238252@qq.com, 代码有什么不对的欢迎发邮件给我
一、linux内核链表 1、普通链表的数据区域的局限性 之前定义数据区域时直接int data,我们认为我们的链表中需要存储的是一个int类型的数。但是实际上现实编程中链接中的节点不可能这么简单,而是多种多样的。 一般...
对linux内核的链表结构和对内核链表的操作进行超详细讲解
Linux内核链表移植和测试代码
贪吃蛇小游戏,用c语言和Linux内核链表实现,图行显示基于curses库,游戏界面有时钟计时器和当前分数、上一次游戏分数、历史最高分数显示。
详细的介绍了Linux内核中使用的最频繁的双向链表
剖析linux 内核 linux内核链表
博客详细讲解Linux内核链表,教你看懂Linux内核链表与普通链表有什么不一样,并且有测试代码
本文讲解Linux内核链表实现的过程,说了链表的定义及初始化宏定义、插入操作和删除操作等内容,详细看下面
linux内核中有关于list 、kfifo等数据结构的实现,从源码中抽取出list部分,可以在linux应用编程中使用。有详细的抽取过程原理,ubunt12.04上完成
链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表的一种重要实现方式。相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以...
linux2.4.18版本源码 内核链表 用户态移植 vc6.0下测试
吐血奉献,忍痛共享! 【最强悍的链表】Linux 内核链表源码
linux 内核链表在用户态的应用的实例,实现常见的链表的操作,
内核链表的构造与操作: 在Linux内核中使用了大量的链表结构来组织数据。这些链表大多数采用了include。/linux/list.h中实现的一套精彩的链表数据结构。 内核的链表具备双链表功能,实际上,通常它都的组织成双向...
linux内核链表插入,排序函数库,库里面包含了一些宏。可以进行链表的插入,,删减。与一般链表不同的是,可以连接不同类型的数据。
Linux内核链表及其在虚拟文件系统中的应用.pdf