Android中的双向链表
1.看源代码必须搞懂Android的数据结构。在init源代码中双向链表listnode使用非常多,它仅仅有prev和next两个指针,没有不论什么数据成员。这个和linux内核的list_head如出一辙,由此可见安卓深受linux内核的影响的。本来来分析一下这个listnode数据结构。
这里须要考虑的一个问题是,链表操作都是通过listnode进行的,但是那只是是个连接件。假设我们手上有个宿主结构,那当然知道了它的某个listnode在哪里,从而以此为參数调用list_add和list_del函数。但是,反过来。当我们顺着链表取得当中一项的listnode结构时,又如何找到其宿主结构呢?在listnode结构中并没有指向其宿主结构的指针啊。毕竟。我们我真正关心的是宿主结构。而不是连接件。对于这个问题,我们举例内核中的list_head的样例来解决。内核的page结构体含有list_head成员,问题是:知道list_head的地址。如何获取page宿主的地址?以下是取自mm/page_alloc.c中的一行代码:
page = memlist_entry(curr, struct page, list);
这里的memlist_entry将一个list_head指针curr换算成其宿主结构的起始地址,也就是取得指向其宿主page结构的指针。读者可能会对memlist_entry()的实现感到困惑。
#define memlist_entry list_entry
而list_entry定义则在include/linux/list.h中
135 /**
136 * list_entry get
the struct for this entry
137 * @ptr: the &struct list_head pointer.
138 * @type: the type of the struct this is embedded in.
139 * @member: the name of the list_struct within the struct.
140 */
141 #define list_entry(ptr, type, member) \
142 ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
这样我们应该就明确了。curr是一个page结构内部成分list的地址,而我们所须要的却是那个page结构本身的地址,所以要从curr减去一个偏移量,即成分list在page内部的位移量。
那么这个位移量怎么求?&((struct page*)0)->list就表示当结构page正好在地址0上时其成分list的地址,这就是所求的偏移量。
2.測试代码
#include<stdio.h>
#include<stddef.h> typedef struct _listnode
{
struct _listnode *prev;
struct _listnode *next;
}listnode; #define node_to_item(node,container,member) \
(container*)(((char*)(node))-offsetof(container,member)) //向list双向链表尾部加入node节点,list始终指向双向链表的头部(这个头部仅仅含有prev/next)
void list_add_tail(listnode *list,listnode *node)
{
list->prev->next=node;
node->prev=list->prev;
node->next=list;
list->prev=node;
}
//定义一个測试的宿主结构
typedef struct _node
{
int data;
listnode list;
}node; int main()
{
node n1,n2,n3,*n;
listnode list,*p;
n1.data=1;
n2.data=2;
n3.data=3;
list.prev=&list;
list.next=&list;
list_add_tail(&list,&n1.list);
list_add_tail(&list,&n2.list);
list_add_tail(&list,&n3.list);
for(p=list.next;p!=&list;p=p->next)
{
n=node_to_item(p,node,list);
printf("%d\n",n->data);
}
return 0;
}
最新文章
- Electron笔记
- Python之路【番外篇】回顾&;类的静态字段
- 携程Android App插件化和动态加载实践
- hdu 猜数字
- (二)深入梯度下降(Gradient Descent)算法
- KVO机制
- BZOJ_1270_雷涛的小猫_(动态规划)
- 玩转iOS 9的UIDynamics(转)
- RMAN数据库恢复之丢失数据文件的恢复
- JSP 和 Servlet 有哪些相同点和不同点, 他们之间的联系是什么?
- Cocos2d-x实现简单的翻牌效果
- Spring MVC入门讲解
- angular内置provider之$compileProvider
- 内置对象Cookie和Session有何不同【常见面试题】
- 微信支付异常:appid and openid not match
- POJ 3368
- PAT Basic 1016
- c#中富文本编辑器Simditor带图片上传的全部过程(项目不是mvc架构)
- 【BZOJ】4380: [POI2015]Myjnie
- Jmeter入门--可执行元件