Linux内核中双向链表的经典实现
概要
本文对双向链表进行探讨，介绍的内容是Linux内核中双向链表的经典实现和用法。其中，也会涉及到Linux内核中非常常用的两个经典宏定义offsetof和container_of。内容包括：
1.Linux中的两个经典宏定义
2.Linux中双向链表的经典实现
Linux中的两个经典宏定义
倘若你查看过LinuxKernel的源码，那么你对offsetof和container_of这两个宏应该不陌生。这两个宏最初是极客写出的，后来在Linux内核中被推广使用。
1.offsetof
1.1offsetof介绍
定义：offsetof在linux内核的include/linux/stddef.h中定义。
1#defineoffsetof(TYPE,MEMBER)((size_t)&((TYPE)0)->MEMBER) 说明：获得结构体(TYPE)的变量成员(MEMBER)在此结构体中的偏移量。 (01)((TYPE
(02)((TYPE)0)->MEMBER访问结构中的数据成员。
(03)&(((TYPE)0)->MEMBER)取出数据成员的地址。由于TYPE的地址是0，这里获取到的地址就是相对MEMBER在TYPE中的偏移。(04)(size_t)(&(((TYPE)0)->MEMBER))结果转换类型。对于32位系统而言，size_t是unsignedint类型；对于64位系统而言，size_t是unsignedlong类型。
1.2offsetof示例
代码(offset_test.c):
1#include<stdio.h>2//获得结构体(TYPE)的变量成员(MEMBER)在此结构体中的偏移量。3#defineoffsetof(TYPE,MEMBER)((size_t)&((TYPE)0)->MEMBER)4structstudent5{6chargender;7intid;8intage;9charname[20];10};1112voidmain()13{14intgender_offset,id_offset,age_offset,name_offset;15gender_offset=offsetof(structstudent,gender);16id_offset=offsetof(structstudent,id);17age_offset=offsetof(structstudent,age);18name_offset=offsetof(structstudent,name);19printf(“gender_offset=%d\n”,gender_offset);20printf(“id_offset=%d\n”,id_offset);21printf(“age_offset=%d\n”,age_offset);22printf(“name_offset=%d\n”,name_offset);23}
结果：
1gender_offset=02id_offset=43age_offset=84name_offset=12
说明：简单说说”为什么id的偏移值是4，而不是1”。我的运行环境是linux系统，32位的x86架构。这就意味着cpu的数据总线宽度为32，每次能够读取4字节数据。gcc对代码进行处理的时候，是按照4字节对齐的。所以，即使gender是char(一个字节)类型，但是它仍然是4字节对齐的！
1.3offsetof图解
TYPE是结构体，它代表”整体”；而MEMBER是成员，它是整体中的某一部分。
将offsetof看作一个数学问题来看待，问题就相当简单了：已知’整体’和该整体中’某一个部分’，而计算该部分在整体中的偏移
2.container_of
2.1container_of介绍
定义：container_of在linux内核的include/linux/kernel.h中定义。
1#definecontainer_of(ptr,type,member)({\2consttypeof(((type)0)->member)mptr=(ptr);\3(type)((char)mptr-offsetof(type,member));})
说明：根据”结构体(type)变量”中的”域成员变量(member)的指针(ptr)“来获取指向整个结构体变量的指针。
(01)typeof(((type)0)->member)取出member成员的变量类型。
(02)consttypeof(((type)0)->member)mptr=(ptr)定义变量mptr指针，并将ptr赋值给mptr。经过这一步，mptr为member数据类型的常量指针，其指向ptr所指向的地址。
(04)(char)mptr将mptr转换为字节型指针。
(05)offsetof(type,member))就是获取”member成员”在”结构体type”中的位置偏移。
(06)(char*)mptr-offsetof(type,member))就是用来获取”结构体type”的指针的起始地址（为char型指针）。
(07)(type)((char*)mptr-offsetof(type,member))就是将”char*类型的结构体type的指针”转换为”type类型的结构体type的指针”。
2.2container_of示例
代码(container_test.c):
1#include<stdio.h>2#include<string.h>3//获得结构体(TYPE)的变量成员(MEMBER)在此结构体中的偏移量。4#defineoffsetof(TYPE,MEMBER)((size_t)&((TYPE)0)->MEMBER)5//根据”结构体(type)变量”中的”域成员变量(member)的指针(ptr)“来获取指向整个结构体变量的指针6#definecontainer_of(ptr,type,member)({\7consttypeof(((type)0)->member)mptr=(ptr);\8(type)((char)mptr-offsetof(type,member));})9structstudent10{11chargender;12intid;13intage;14charname[20];15};1617voidmain()18{19structstudentstu;20structstudent*pstu;21stu.gender=‘1’;22stu.id=9527;23stu.age=24;24strcpy(stu.name,“zhouxingxing”);25//根据”id地址”获取”结构体的地址”。26pstu=container_of(&stu.id,structstudent,id);27//根据获取到的结构体student的地址，访问其它成员28printf(“gender=%c\n”,pstu->gender);29printf(“age=%d\n”,pstu->age);30printf(“name=%s\n”,pstu->name);31}
结果：
1gender=12age=243name=zhouxingxing
2.3container_of图解
type是结构体，它代表”整体”；而member是成员，它是整体中的某一部分，而且member的地址是已知的。
将offsetof看作一个数学问题来看待，问题就相当简单了：已知’整体’和该整体中’某一个部分’，要根据该部分的地址，计算出整体的地址。
Linux中双向链表的经典实现
1.Linux中双向链表介绍
Linux双向链表的定义主要涉及到两个文件：
include/linux/types.h
include/linux/list.h
Linux中双向链表的使用思想
它是将双向链表节点嵌套在其它的结构体中；在遍历链表的时候，根据双链表节点的指针获取”它所在结构体的指针”，从而再获取数据。
我举个例子来说明，可能比较容易理解。假设存在一个社区中有很多人，每个人都有姓名和年龄。通过双向链表将人进行关联的模型图如下：
person代表人，它有name和age属性。为了通过双向链表对person进行链接，我们在person中添加了list_head属性。通过list_head，我们就将person关联起来了。
1structperson2{3intage;4charname[20];5structlist_headlist;6};
2.Linux中双向链表的源码分析
(01).节点定义
1structlist_head{2structlist_head*next,*prev;3};
虽然名称list_head，但是它既是双向链表的表头，也代表双向链表的节点。
(02).初始化节点
1#defineLIST_HEAD_INIT(name){&(name),&(name)}2#defineLIST_HEAD(name)\3structlist_headname=LIST_HEAD_INIT(name)4staticinlinevoidINIT_LIST_HEAD(structlist_head*list)5{6list->next=list;7list->prev=list;8}
LIST_HEAD的作用是定义表头(节点)：新建双向链表表头name，并设置name的前继节点和后继节点都是指向name本身。
LIST_HEAD_INIT的作用是初始化节点：设置name节点的前继节点和后继节点都是指向name本身。
INIT_LIST_HEAD和LIST_HEAD_INIT一样，是初始化节点：将list节点的前继节点和后继节点都是指向list本身。
(03).添加节点
1staticinlinevoidlist_add(structlist_head*new,2structlist_head*prev,3structlist_head*next)4{5next->prev=new;6new->next=next;7new->prev=prev;8prev->next=new;9}1011staticinlinevoidlist_add(structlist_head*new,structlist_head*head)12{13list_add(new,head,head->next);14}1516staticinlinevoidlist_add_tail(structlist_head*new,structlist_head*head)17{18list_add(new,head->prev,head);19} list_add(new,prev,next)的作用是添加节点：将new插入到prev和next之间。在linux中，以”“开头的函数意味着是内核的内部接口，外部不应该调用该接口。 list_add(new,head)的作用是添加new节点：将new添加到head之后，是new称为head的后继节点。 list_add_tail(new,head)的作用是添加new节点：将new添加到head之前，即将new添加到双链表的末尾。 (04).删除节点 1staticinlinevoid
list_del(prev,next)和list_del_entry(entry)都是linux内核的内部接口。
list_del(prev,next)的作用是从双链表中删除prev和next之间的节点。
list_del_entry(entry)的作用是从双链表中删除entry节点。
list_del(entry)和list_del_init(entry)是linux内核的对外接口。
list_del(entry)的作用是从双链表中删除entry节点。
list_del_init(entry)的作用是从双链表中删除entry节点，并将entry节点的前继节点和后继节点都指向entry本身。
(05).替换节点
1staticinlinevoidlist_replace(structlist_head*old,2structlist_head*new)3{4new->next=old->next;5new->next->prev=new;6new->prev=old->prev;7new->prev->next=new;8}
list_replace(old,new)的作用是用new节点替换old节点。
(06).判断双链表是否为空
1staticinlineintlist_empty(conststructlist_head*head)2{3returnhead->next==head;4}
list_empty(head)的作用是判断双链表是否为空。它是通过区分”表头的后继节点”是不是”表头本身”来进行判断的。
(07).获取节点
1#definelist_entry(ptr,type,member)\2container_of(ptr,type,member)
list_entry(ptr,type,member)实际上是调用的container_of宏。
它的作用是：根据”结构体(type)变量”中的”域成员变量(member)的指针(ptr)“来获取指向整个结构体变量的指针。
(08).遍历节点
1#definelist_for_each(pos,head)\2for(pos=(head)->next;pos!=(head);pos=pos->next)34#definelist_for_each_safe(pos,n,head)\5for(pos=(head)->next,n=pos->next;pos!=(head);\6pos=n,n=pos->next)
list_for_each(pos,head)和list_for_each_safe(pos,n,head)的作用都是遍历链表。但是它们的用途不一样！
list_for_each(pos,head)通常用于获取节点，而不能用到删除节点的场景。
list_for_each_safe(pos,n,head)通常删除节点的场景。
3.Linux中双向链表的使用示例
双向链表代码(list.h):
1#ifndef_LIST_HEAD_H2#define_LIST_HEAD_H3//双向链表节点4structlist_head{5structlist_head*next,*prev;6};78//初始化节点：设置name节点的前继节点和后继节点都是指向name本身。9#defineLIST_HEAD_INIT(name){&(name),&(name)}10//定义表头(节点)：新建双向链表表头name，并设置name的前继节点和后继节点都是指向name本身。11#defineLIST_HEAD(name)\12structlist_headname=LIST_HEAD_INIT(name)13//初始化节点：将list节点的前继节点和后继节点都是指向list本身。14staticinlinevoidINIT_LIST_HEAD(structlist_head*list)15{16list->next=list;17list->prev=list;18}1920//添加节点：将new插入到prev和next之间。21staticinlinevoidlist_add(structlist_head*new,22structlist_head*prev,23structlist_head*next)24{25next->prev=new;26new->next=next;27new->prev=prev;28prev->next=new;29}3031//添加new节点：将new添加到head之后，是new称为head的后继节点。32staticinlinevoidlist_add(structlist_head*new,structlist_head*head)33{34list_add(new,head,head->next);35}3637//添加new节点：将new添加到head之前，即将new添加到双链表的末尾。38staticinlinevoidlist_add_tail(structlist_head*new,structlist_head*head)39{40list_add(new,head->prev,head);41}4243//从双链表中删除entry节点。44staticinlinevoidlist_del(structlist_head*prev,structlist_head*next)45{46next->prev=prev;47prev->next=next;48}4950//从双链表中删除entry节点。51staticinlinevoidlist_del(structlist_head*entry)52{53list_del(entry->prev,entry->next);54}5556//从双链表中删除entry节点。57staticinlinevoidlist_del_entry(structlist_head*entry)58{59list_del(entry->prev,entry->next);60}6162//从双链表中删除entry节点，并将entry节点的前继节点和后继节点都指向entry本身。63staticinlinevoidlist_del_init(structlist_head*entry)64{65list_del_entry(entry);66INIT_LIST_HEAD(entry);67}6869//用new节点取代old节点70staticinlinevoidlist_replace(structlist_head*old,71structlist_head*new)72{73new->next=old->next;74new->next->prev=new;75new->prev=old->prev;76new->prev->next=new;77}7879//双链表是否为空80staticinlineintlist_empty(conststructlist_headhead)81{82returnhead->next==head;83}84//获取”MEMBER成员”在”结构体TYPE”中的位置偏移85#defineoffsetof(TYPE,MEMBER)((size_t)&((TYPE)0)->MEMBER)86//根据”结构体(type)变量”中的”域成员变量(member)的指针(ptr)“来获取指向整个结构体变量的指针87#definecontainer_of(ptr,type,member)({\88consttypeof(((type)0)->member)mptr=(ptr);\89(type)((char)mptr-offsetof(type,member));})90//遍历双向链表91#definelist_for_each(pos,head)\92for(pos=(head)->next;pos!=(head);pos=pos->next)93#definelist_for_each_safe(pos,n,head)\94for(pos=(head)->next,n=pos->next;pos!=(head);\95pos=n,n=pos->next)96#definelist_entry(ptr,type,member)\97container_of(ptr,type,member)98#endif
双向链表测试代码(test.c):
1#include<stdio.h>2#include<stdlib.h>3#include<string.h>4#include”list.h”5structperson6{7intage;8charname[20];9structlist_headlist;10};1112voidmain(intargc,char*argv[])13{14structperson*pperson;15structpersonperson_head;16structlist_head*pos,next;17inti;18//初始化双链表的表头19INIT_LIST_HEAD(&person_head.list);20//添加节点21for(i=0;i<5;i++)22{23pperson=(structperson)malloc(sizeof(structperson));24pperson->age=(i+1)*10;25sprintf(pperson->name,“%d”,i+1);26//将节点链接到链表的末尾27//如果想把节点链接到链表的表头后面，则使用list_add28list_add_tail(&(pperson->list),&(person_head.list));29}3031//遍历链表32printf(“====1stiteratord-link====\n”);33list_for_each(pos,&person_head.list)34{35pperson=list_entry(pos,structperson,list);36printf(“name:%-2s,age:%d\n”,pperson->name,pperson->age);37}3839//删除节点age为20的节点40printf(“====deletenode(age:20)====\n”);41list_for_each_safe(pos,next,&person_head.list)42{43pperson=list_entry(pos,structperson,list);44if(pperson->age==20)45{46list_del_init(pos);47free(pperson);48}49}5051//再次遍历链表52printf(“====2nditeratord-link====\n”);53list_for_each(pos,&person_head.list)54{55pperson=list_entry(pos,structperson,list);56printf(“name:%-2s,age:%d\n”,pperson->name,pperson->age);57}5859//释放资源60list_for_each_safe(pos,next,&person_head.list)61{62pperson=list_entry(pos,structperson,list);63list_del_init(pos);64free(pperson);65}66}
运行结果：
1====1stiteratord-link====2name:1,age:103name:2,age:204name:3,age:305name:4,age:406name:5,age:507====deletenode(age:20)====8====2nditeratord-link====9name:1,age:1010name:3,age:3011name:4,age:4012name:5,age:50
文章来源：
http://www.cnblogs.com/skywang12345/p/3562146.html
