搜索
Linux内核通用链表linux/list.h阅读2008-10-2322:43#ifndef_LINUX_LIST_H#define_LINUX_LIST_H//宏定义，不做过多解释，就是检查是否包含了linux/list.h#ifdef__KERNEL__#includelinux/stddef.h#includelinux/prefetch.h#includeasm/system.h/**Thesearenon-NULLpointersthatwillresultinpagefaults*undernormalcircumstances,usedtoverifythatnobodyuses*non-initializedlistentries.*/这些非空的指针会导致页错误，在正常环境下，用来验证无人使用为初始化的链表节点，入口．也有解释说能引起中断，或者关于这个地址的处理内核处理的很简单,要么打印日志信息报错,要么直接不处理.#defineLIST_POISON1((void*)0x00100100)#defineLIST_POISON2((void*)0x00200200)/**Simpledoublylinkedlistimplementation.**Someoftheinternalfunctions(__xxx)areusefulwhen*manipulatingwholelistsratherthansingleentries,as*sometimeswealreadyknowthenext/preventriesandwecan*generatebettercodebyusingthemdirectlyratherthan*usingthegenericsingle-entryroutines.*/entry似乎应该翻译成表或者节点。简单的双向链表实现：一些内部函数在熟练操作整个链表比单个入口更有用，当我们已经知道next/prev入口，通过使用直接它们比使用一般的单入口程序产生更好的代码。structlist_head{structlist_head*next,*prev;};#defineLIST_HEAD_INIT(name){&(name),&(name)}#defineLIST_HEAD(name)\structlist_headname=LIST_HEAD_INIT(name)如果一开始没有看懂LIST_HEAD_INIT宏定义的话，上面这个应该可以让人豁然开朗，初始化一个name链表，让头和尾都指向自己。#defineINIT_LIST_HEAD(ptr)do{\(ptr)-next=(ptr);(ptr)-prev=(ptr);\}while(0)/**Insertanewentrybetweentwoknownconsecutiveentries.**Thisisonlyforinternallistmanipulationwhereweknow*theprev/nextentriesalready!*/在已知的连续节点中间插入一个新的节点staticinlinevoid__list_add(structlist_head*new,structlist_head*prev,structlist_head*next){next-prev=new;new-next=next;new-prev=prev;prev-next=new;}/***list_add-addanewentry*@new:newentrytobeadded*@head:listheadtoadditafter**Insertanewentryafterthespecifiedhead.*Thisisgoodforimplementingstacks.*/在制订head节点之后插入一个新的节点，这个适用于栈staticinlinevoidlist_add(structlist_head*new,structlist_head*head){__list_add(new,head,head-next);}/***list_add_tail-addanewentry*@new:newentrytobeadded*@head:listheadtoadditbefore**Insertanewentrybeforethespecifiedhead.*Thisisusefulforimplementingqueues.*/在指定节点前插入一个新节点，适用于队列staticinlinevoidlist_add_tail(structlist_head*new,structlist_head*head){__list_add(new,head-prev,head);}/**Insertanewentrybetweentwoknownconsecutiveentries.**Thisisonlyforinternallistmanipulationwhereweknow*theprev/nextentriesalready!*/此函数仅供内置链表操作，就是只用于此头文件中所有的关于链表操作的函数就是要已知prev/next节点staticinlinevoid__list_add_rcu(structlist_head*new,structlist_head*prev,structlist_head*next){new-next=next;new-prev=prev;smp_wmb();next-prev=new;prev-next=new;}/***list_add_rcu-addanewentrytorcu-protectedlist*@new:newentrytobeadded*@head:listheadtoadditafter**Insertanewentryafterthespecifiedhead.*Thisisgoodforimplementingstacks.**Thecallermusttakewhateverprecautionsarenecessary*(suchasholdingappropriatelocks)toavoidracing*withanotherlist-mutationprimitive,suchaslist_add_rcu()*orlist_del_rcu(),runningonthissamelist.*However,itisperfectlylegaltorunconcurrentlywith*the_rculist-traversalprimitives,suchas*list_for_each_entry_rcu().*/调用必须提供任何的必要的防范措施（比如固定适当的锁）来避免在运行于同一个链表时和另一个原始的链表操作竞争，比如list_add_rcu()*orlist_del_rcu(),但是和_rcu原始的链表遍历同时运行是完全合法的。staticinlinevoidlist_add_rcu(structlist_head*new,structlist_head*head){__list_add_rcu(new,head,head-next);}/***list_add_tail_rcu-addanewentrytorcu-protectedlist*@new:newentrytobeadded*@head:listheadtoadditbefore**Insertanewentrybeforethespecifiedhead.*Thisisusefulforimplementingqueues.**Thecallermusttakewhateverprecautionsarenecessary*(suchasholdingappropriatelocks)toavoidracing*withanotherlist-mutationprimitive,suchaslist_add_tail_rcu()*orlist_del_rcu(),runningonthissamelist.*However,itisperfectlylegaltorunconcurrentlywith*the_rculist-traversalprimitives,suchas*list_for_each_entry_rcu().*/staticinlinevoidlist_add_tail_rcu(structlist_head*new,structlist_head*head){__list_add_rcu(new,head-prev,head);}/**Deletealistentrybymakingtheprev/nextentries*pointtoeachother.**Thisisonlyforinternallistmanipulationwhereweknow*theprev/nextentriesalready!*/看不懂此函数可以看下面就明白了，删除已知节点，需要知道节点的后继和前趋staticinlinevoid__list_del(structlist_head*prev,structlist_head*next){next-prev=prev;prev-next=next;}/***list_del-deletesentryfromlist.*@entry:theelementtodeletefromthelist.*Note:list_emptyonentrydoesnotreturntrueafterthis,theentryis*inanundefinedstate.*/staticinlinevoidlist_del(structlist_head*entry){__list_del(entry-prev,entry-next);entry-next=LIST_POISON1;entry-prev=LIST_POISON2;}常规的方法是entry-next置空，这里做什么为了什么还有待于参考。/***list_del_rcu-deletesentryfromlistwithoutre-initialization*@entry:theelementtodeletefromthelist.**Note:list_emptyonentrydoesnotreturntrueafterthis,*theentryisinanundefinedstate.ItisusefulforRCUbased*lockfreetraversal.*注意：list_empty函数作用在节点后并不返回真，节电处于为定义状态，这对于RCU无锁定的遍历状态很有用*Inparticular,itmeansthatwecannotpoisontheforward*pointersthatmaystillbeusedforwalkingthelist.*特别注意，这就意味着我们不能断开前趋指针，前趋指针对遍历链表还是很有用滴．*Thecallermusttakewhateverprecautionsarenecessary*(suchasholdingappropriatelocks)toavoidracing*withanotherlist-mutationprimitive,suchaslist_del_rcu()*orlist_add_rcu(),runningonthissamelist.*However,itisperfectlylegaltorunconcurrentlywith*the_rculist-traversalprimitives,suchas*list_for_each_entry_rcu().**Note