Linux利用list_head结构实现双向链表
原文地址:http://www.cnblogs.com/bastard/archive/2012/10/19/2731107.html
通常实现双向链表的数据结构:
struct list_node1{
struct list_node1 *next,*prev;
type1 m1;
type2 m2;
};
struct list_node2{
struct list_node2 *next,*prev;
type1 m1;
type2 m2;
};
……
对于每一种数据结构都定义了其特定的实现链表的结构和对应的方法(add/del)操作链表;
但对于具有大量不同数据结构,都要使用链表的系统中,如果为每一种数据结构定义特定的结构,和操作方法,
无疑使代码变得重复和臃肿,需要实现一种通用的双向链表方法,对各种数据结构都能适用。
C语言中又没有C++里面的模板,该如何实现呢?
linux内核中大量使用如下数据结构实现双向链表:
struct list_head {
struct list_head *next, *prev;
};
如果需要有某种数据结构的双向队列,就在这种结构内部放一个list_head数据结构成员。
struct kobject {
const char *name;
struct list_head entry;
struct kobject *parent;
struct kset *kset;
}
形成了如下结构:
如何通过kobject 链表结构中的 list_head 成员entry访问下一个成员呢?
系统提供了宏list_entry:
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
//访问链表成员
kobject *obj = objList;
kobject *nextObj = (kobject *)list_entry(obj->entry->next,struct kobject,entry);
这个list_entry是什么道理呢:
ptr:是指向当前kobject结构对象中的数据成员entry,(char *)(ptr):entry成员地址 ——AddrA;
(unsigned long)(&((type *)0)->member)):将地址0转化为类型为type(struct kobject )对象,取member(entry)成员的地址——AddrB。
(type *)(AddrA - AddrB):得到kobject结构对象的首地址,转化为kobject对象。
这里需要关注的就是AddrB:将地址0转化为类型为type(struct kobject )对象,取member(entry)成员的地址。
表示当struct kobject 对象首地址为0时,得到成员member(entry)的地址,相对首地址的偏移地址。
通过struct kobject 对象中member(entry)的地址 ,以及相对首地址的偏移量,就能计算出struct kobject 对象的首地址。
如下结构:
充分利用了C语言中直接操作内存地址的特性。
最新文章
- nodejs 中自定义事件
- DOM常用操作总结
- 19.创建如下三个类:(People类中的三个方法分别输出一些信息,ChinaPeople 和AmericanPeople类重写父类的三个方法)。
- Liferay7 BPM门户开发之26: 集成Activiti到Liferay7
- Linux Linux程序练习五
- 数字图像去噪典型算法及matlab实现
- THINKPHP之控制器
- Hacking HackDay: Albania
- 文本处理三剑客之awk(No.1)
- Google SketchUp Cookbook: (Chapter 5) Roofs: Constraints and Inferences
- 子元素position:absolute定位之后脱离文档流,怎么使子元素撑开父元素
- [PA2014]Lustra
- PHP实现的简单组词算法
- maven 引入外部jar包的几种方式
- Android 显示Dialog的同时自动弹出软键盘;
- 1.如何修改oracle的密码
- Python解析Wav文件并绘制波形的方法
- Python开发【模块】:Urllib(二)
- Java堆空间溢出解决方法 Exception in thread ";main"; java.lang.OutOfMemoryError: Java heap space
- HTTP接口开发专题二(发送http请求的接口工具类)
热门文章
- 【集训试题】exam 信心考 最小割
- 文件名的查找——find
- 时间戳转换成日期的js
- RxJS &; Angular
- SPOJ DQUERY (主席树求区间不同数个数)
- 【BZOJ 1770 】 [Usaco2009 Nov]lights 燈 dfs+异或方程组
- BZOJ 2707: [SDOI2012]走迷宫 拓扑+高斯消元+期望概率dp+Tarjan
- bzoj2002: [Hnoi2010]Bounce 弹飞绵羊 分块
- SCOI 股票交易 单调队列优化dp
- Java的Properties使用及格式定义