linux内核的链循环双链表简单使用

　　linux内核的循环双链表是非常经典的代码实现方式，个人总结如下：API多，像nginx（二者原理一致）、redis的链表在api数目上还差一点扩展性强，比如可以实现一个LRU、和线程池结合使用都可以，而redis的链表还差了点
　　demo代码如下：includestdio。hincludestdlib。hincludeincludelist。hdefineMAXELENUMS（5）structStu｛unsignedintulId；structlistheadstN｝；structStuList｛structlistheadstLi；｝；打印单个Node信息staticDLPrintNode（charpcPrefix，structStupstStu）｛assert（（NULL！pcPrefix）（NULL！pstStu））；printf（s，id：u，addr：p，node：p，pcPrefix，pstStuulId，pstStu，（pstStustNode））；｝释放链表的所有数据voidDLClearStuLi（structlistheadpstHead）｛assert（NULL！pstHead）；structStupstStuNULL；structStupstNextStuNULL；listforeachentrysafe（pstStu，pstNextStu，pstHead，stNode）｛listdel（（pstStustNode））；DLPrintNode（free，pstStu）；free（（void）pstStu）；｝｝打印链表数据voidDLPrintStuLi（structlistheadpstHead，intlReverse）｛assert（NULL！pstHead）；structStupstStuNULL；structStupstNextStuNULL；if（lReverse）｛listforeachentrysafereverse（pstStu，pstNextStu，pstHead，stNode）｛DLPrintNode（showbackward，pstStu）；｝｝else｛listforeachentrysafe（pstStu，pstNextStu，pstHead，stNode）｛DLPrintNode（showforward，pstStu）；｝｝｝批量添加至链表中voidDLBatchAddStuLiNodes（structlistheadpstHead，structStuppstStus，unsignedintulNodeNum，intlAddTail）｛assert（（NULL！pstHead）（NULL！ppstStus））；structStupstStuNULL；if（lAddTail）｛for（unsignedinti0；iulNodeNi）｛pstStuppstStus〔i〕；listaddtail（（pstStustNode），pstHead）；｝｝else｛for（unsignedinti0；iulNodeNi）｛pstStuppstStus〔i〕；listadd（（pstStustNode），pstHead）；｝｝｝voidDLBatchCreateNodes（structStuppstStus，unsignedintulNodeNum，unsignedintulStartId）｛assert（NULL！ppstStus）；for（unsignedinti0；iulNodeNi）｛ppstStus〔i〕（structStu）malloc（sizeof（structStu））；assert（NULL！ppstStus〔i〕）；ppstStus〔i〕ulIdulStartId；DLPrintNode（create，ppstStus〔i〕）；ulStartId；｝｝从给定的元素开始遍历，包括给定的元素voidDLIterateIncludeGivenEntry（structlistheadpstHead，structStupstStu，intlReverse）｛assert（（NULL！pstHead）（NULL！pstStu））；structStupstNextStuNULL；if（lReverse）｛listforeachentryfromreverse（pstStu，pstHead，stNode）｛DLPrintNode（showbackward，pstStu）；｝｝else｛listforeachentrysafefrom（pstStu，pstNextStu，pstHead，stNode）｛DLPrintNode（showforward，pstStu）；｝｝｝从给定的元素开始遍历，voidDLIterateExcludeGivenEntry（structlistheadpstHead，structStupstStu，intlReverse）｛assert（（NULL！pstHead）（NULL！pstStu））；structStupstNextStuNULL；if（lReverse）｛listforeachentrycontinuereverse（pstStu，pstHead，stNode）｛DLPrintNode（showbackward，pstStu）；｝｝else｛listforeachentrysafecontinue（pstStu，pstNextStu，pstHead，stNode）｛DLPrintNode（showforward，pstStu）；｝｝｝voidDLCreateNoEmptyList（structlistheadpstHead，unsignedintulNodeNum）｛assert（（NULL！pstHead）（0！ulNodeNum））；structStuppstStusNULL；ppstStus（structStu）malloc（sizeof（structStu）ulNodeNum）；assert（NULL！ppstStus）；INITLISTHEAD（pstHead）；DLBatchCreateNodes（ppstStus，ulNodeNum，0）；DLBatchAddStuLiNodes（pstHead，ppstStus，ulNodeNum，1）；free（（void）ppstStus）；｝voidDLIterateGivenPoint（）｛分配空间structStuapstStus〔MAXELENUMS〕｛0｝；DLBatchCreateNodes（apstStus，MAXELENUMS，0）；初始化链表structStuListstList｛0｝；INITLISTHEAD（（stList。stLi））；链表尾部添加DLBatchAddStuLiNodes（（stList。stLi），apstStus，MAXELENUMS，1）；DLIterateIncludeGivenEntry（（stList。stLi），apstStus〔2〕，1）；DLIterateExcludeGivenEntry（（stList。stLi），apstStus〔2〕，1）；释放链表所有数据DLClearStuLi（（stList。stLi））；｝简单使用voidDLBasic（）｛分配空间structStuapstStus〔MAXELENUMS〕｛0｝；DLBatchCreateNodes（apstStus，MAXELENUMS，0）；初始化链表structStuListstList｛0｝；INITLISTHEAD（（stList。stLi））；无数据，为空printf（init，listemtpy：s，listempty（（stList。stLi））？yes：no）；链表尾部添加DLBatchAddStuLiNodes（（stList。stLi），apstStus，MAXELENUMS，1）；有数据不为空printf（AfterAdd，listemtpy：s，listempty（（stList。stLi））？yes：no）；structStupstStuNULL；structlistheadpstNodeNULL；structlistheadpstNextNodeNULL；打印所有的链表数据DLPrintStuLi（（stList。stLi），0）；释放链表所有数据DLClearStuLi（（stList。stLi））；｝voidshowBasicListInfo（）｛structStuapstStus〔MAXELENUMS〕｛0｝；DLBatchCreateNodes（apstStus，MAXELENUMS，0）；initliststructStuListstList｛0｝；INITLISTHEAD（（stList。stLi））；nodata，isemptyprintf（init，listemtpy：s，listempty（（stList。stLi））？yes：no）；addnodetolisttailfor（unsignedinti0；iMAXELENUMS；i）｛listaddtail（（apstStus〔i〕stNode），（stList。stLi））；printf（listempty：s，listsingular：s，listfirst：s，listlast：s，entryishead：s，listempty（（stList。stLi））？yes：no，listissingular（（stList。stLi））？yes：no，listisfirst（（apstStus〔i〕stNode），（stList。stLi））？yes：no，listislast（（apstStus〔i〕stNode），（stList。stLi））？yes：no，listentryishead（apstStus〔i〕，（stList。stLi），stNode）？yes：no）；｝printf（listfirst：ulistlast：u，listfirstentryornull（（stList。stLi），structStu，stNode）ulId，listlastentry（（stList。stLi），structStu，stNode）ulId）；DLPrintStuLi（（stList。stLi），0）；DLClearStuLi（（stList。stLi））；｝structInvalidStruct｛intulIunsignedlonglongdulDoubleIcharszName〔20〕；floatfDataF｝；intmain（）｛showBasicListInfo（）；return0；｝
　　为此，提取的代码如下，可直接复制粘贴供以后使用，由于代码中使用了new作为变量名，在C中会报错，可以自行将new替换掉其他变量名即可。SPDXLicenseIdentifier：GPL2。0ifndefR2MLISTHdefineR2MLISTHincludestdbool。hifndefoffsetofdefineoffsetof（TYPE，MEMBER）（（sizet）（（TYPE）0）MEMBER）endifcontainerofcastamemberofastructureouttothecontainingstructureptr：thepointertothemember。type：thetypeofthecontainerstructthisisembeddedin。member：thenameofthememberwithinthestruct。ifndefcontainerofdefinecontainerof（ptr，type，member）（｛voidmptr（void）（ptr）；（（type）（mptroffsetof（type，member）））；｝）endifdefinePOISONPOINTERDELTA0ThesearenonNULLpointersthatwillresultinpagefaultsundernormalcircumstances，usedtoverifythatnobodyusesnoninitializedlistentries。defineLISTPOISON1（（void）0x100POISONPOINTERDELTA）defineLISTPOISON2（（void）0x122POISONPOINTERDELTA）Circulardoublylinkedlistimplementation。Someoftheinternalfunctions（xxx）areusefulwhenmanipulatingwholelistsratherthansingleentries，assometimeswealreadyknowthenextpreventriesandwecangeneratebettercodebyusingthemdirectlyratherthanusingthegenericsingleentryroutines。structlisthead｛structlistheadnext，｝；defineLISTHEADINIT（name）｛（name），（name）｝defineLISTHEAD（name）structlistheadnameLISTHEADINIT（name）INITLISTHEADInitializealistheadstructurelist：listheadstructuretobeinitialized。Initializesthelistheadtopointtoitself。Ifitisalistheader，theresultisanemptylist。staticinlinevoidINITLISTHEAD（structlistheadlist）｛｝ifdefCONFIGDEBUGLISTexternboollistaddvalid（structlistheadnew，structlistheadprev，structlistheadnext）；externboollistdelentryvalid（structlistheadentry）；elsestaticinlineboollistaddvalid（structlistheadnew，structlistheadprev，structlistheadnext）｛｝staticinlineboollistdelentryvalid（structlistheadentry）｛｝endifInsertanewentrybetweentwoknownconsecutiveentries。Thisisonlyforinternallistmanipulationwhereweknowtheprevnextentriesalready！staticinlinevoidlistadd（structlistheadnew，structlistheadprev，structlistheadnext）｛if（！listaddvalid（new，prev，next））｝listaddaddanewentrynew：newentrytobeaddedhead：listheadtoadditafterInsertanewentryafterthespecifiedhead。Thisisgoodforimplementingstacks。staticinlinevoidlistadd（structlistheadnew，structlistheadhead）｛listadd（new，head，headnext）；｝listaddtailaddanewentrynew：newentrytobeaddedhead：listheadtoadditbeforeInsertanewentrybeforethespecifiedhead。Thisisusefulforimplementingqueues。staticinlinevoidlistaddtail（structlistheadnew，structlistheadhead）｛listadd（new，headprev，head）；｝Deletealistentrybymakingtheprevnextentriespointtoeachother。Thisisonlyforinternallistmanipulationwhereweknowtheprevnextentriesalready！staticinlinevoidlistdel（structlistheadprev，structlistheadnext）｛｝Deletealistentryandcleartheprevpointer。Thisisaspecialpurposelistclearingmethodusedinthenetworkingcodeforlistsallocatedaspercpu，wherewedontwanttoincurtheextraWRITEONCE（）overheadofaregularlistdelinit（）。Thecodethatusesthisneedstocheckthenodeprevpointerinsteadofcallinglistempty（）。staticinlinevoidlistdelclearprev（structlistheadentry）｛listdel（entryprev，entrynext）；entryprevNULL；｝staticinlinevoidlistdelentry（structlistheadentry）｛if（！listdelentryvalid（entry））listdel（entryprev，entrynext）；｝listdeldeletesentryfromlist。entry：theelementtodeletefromthelist。Note：listempty（）onentrydoesnotreturntrueafterthis，theentryisinanundefinedstate。staticinlinevoidlistdel（structlistheadentry）｛listdelentry（entry）；entrynextLISTPOISON1；entryprevLISTPOISON2；｝listreplacereplaceoldentrybynewoneold：theelementtobereplacednew：thenewelementtoinsertIfoldwasempty，itwillbeoverwritten。staticinlinevoidlistreplace（structlistheadold，structlistheadnew）｛｝listreplaceinitreplaceoldentrybynewoneandinitializetheoldoneold：theelementtobereplacednew：thenewelementtoinsertIfoldwasempty，itwillbeoverwritten。staticinlinevoidlistreplaceinit（structlistheadold，structlistheadnew）｛listreplace（old，new）；INITLISTHEAD（old）；｝listswapreplaceentry1withentry2andreaddentry1atentry2spositionentry1：thelocationtoplaceentry2entry2：thelocationtoplaceentry1staticinlinevoidlistswap（structlistheadentry1，structlistheadentry2）｛structlistheadposentry2listdel（entry2）；listreplace（entry1，entry2）；if（posentry1）posentry2；listadd（entry1，pos）；｝listdelinitdeletesentryfromlistandreinitializeit。entry：theelementtodeletefromthelist。staticinlinevoidlistdelinit（structlistheadentry）｛listdelentry（entry）；INITLISTHEAD（entry）；｝listmovedeletefromonelistandaddasanothersheadlist：theentrytomovehead：theheadthatwillprecedeourentrystaticinlinevoidlistmove（structlistheadlist，structlistheadhead）｛listdelentry（list）；listadd（list，head）；｝listmovetaildeletefromonelistandaddasanotherstaillist：theentrytomovehead：theheadthatwillfollowourentrystaticinlinevoidlistmovetail（structlistheadlist，structlistheadhead）｛listdelentry（list）；listaddtail（list，head）；｝listbulkmovetailmoveasubsectionofalisttoitstailhead：theheadthatwillfollowourentryfirst：firstentrytomovelast：lastentrytomove，canbethesameasfirstMoveallentriesbetweenfirstandincludinglastbeforehead。Allthreeentriesmustbelongtothesamelinkedlist。staticinlinevoidlistbulkmovetail（structlistheadhead，structlistheadfirst，structlistheadlast）｛｝listisfirsttestswhetherlististhefirstentryinlistheadlist：theentrytotesthead：theheadoftheliststaticinlineintlistisfirst（conststructlistheadlist，conststructlistheadhead）｛｝listislasttestswhetherlististhelastentryinlistheadlist：theentrytotesthead：theheadoftheliststaticinlineintlistislast（conststructlistheadlist，conststructlistheadhead）｛｝listemptytestswhetheralistisemptyhead：thelisttotest。staticinlineintlistempty（conststructlistheadhead）｛｝listdelinitcarefuldeletesentryfromlistandreinitializeit。entry：theelementtodeletefromthelist。Thisisthesameaslistdelinit（），exceptdesignedtobeusedtogetherwithlistemptycareful（）inawaytoguaranteeorderingofothermemoryoperations。Anymemoryoperationsdonebeforealistdelinitcareful（）areguaranteedtobevisibleafteralistemptycareful（）test。staticinlinevoidlistdelinitcareful（structlistheadentry）｛unsupportedif0listdelentry（entry）；smpstorerelease（entrynext，entry）；endif｝listemptycarefultestswhetheralistisemptyandnotbeingmodifiedhead：thelisttotestDescription：testswhetheralistisemptyandchecksthatnootherCPUmightbeintheprocessofmodifyingeithermember（nextorprev）NOTE：usinglistemptycareful（）withoutsynchronizationcanonlybesafeiftheonlyactivitythatcanhappentothelistentryislistdelinit（）。Eg。itcannotbeusedifanotherCPUcouldrelistadd（）it。staticinlineintlistemptycareful（conststructlistheadhead）｛unsupportedif0structlistheadnextsmploadacquire（headnext）；return（nexthead）（nextheadprev）；endifreturn0；｝listrotateleftrotatethelisttothelefthead：theheadoftheliststaticinlinevoidlistrotateleft（structlistheadhead）｛if（！listempty（head））｛listmovetail（first，head）；｝｝listrotatetofront（）Rotatelisttospecificitem。list：Thedesirednewfrontofthelist。head：Theheadofthelist。Rotateslistsothatlistbecomesthenewfrontofthelist。staticinlinevoidlistrotatetofront（structlistheadlist，structlistheadhead）｛Deletesthelistheadfromthelistdenotedbyheadandplacesitasthetailoflist，thiseffectivelyrotatesthelistsothatlistisatthefront。listmovetail（head，list）；｝listissingulartestswhetheralisthasjustoneentry。head：thelisttotest。staticinlineintlistissingular（conststructlistheadhead）｛return！listempty（head）（headnextheadprev）；｝staticinlinevoidlistcutposition（structlistheadlist，structlistheadhead，structlistheadentry）｛｝listcutpositioncutalistintotwolist：anewlisttoaddallremovedentrieshead：alistwithentriesentry：anentrywithinhead，couldbetheheaditselfandifsowewontcutthelistThishelpermovestheinitialpartofhead，uptoandincludingentry，fromheadtolist。Youshouldpassonentryanelementyouknowisonhead。listshouldbeanemptylistoralistyoudonotcareaboutlosingitsdata。staticinlinevoidlistcutposition（structlistheadlist，structlistheadhead，structlistheadentry）｛if（listempty（head））if（listissingular（head）（headnext！entryhead！entry））if（entryhead）INITLISTHEAD（list）；elselistcutposition（list，head，entry）；｝listcutbeforecutalistintotwo，beforegivenentrylist：anewlisttoaddallremovedentrieshead：alistwithentriesentry：anentrywithinhead，couldbetheheaditselfThishelpermovestheinitialpartofhead，uptobutexcludingentry，fromheadtolist。Youshouldpassinentryanelementyouknowisonhead。listshouldbeanemptylistoralistyoudonotcareaboutlosingitsdata。Ifentryhead，allentriesonheadaremovedtolist。staticinlinevoidlistcutbefore（structlistheadlist，structlistheadhead，structlistheadentry）｛if（headnextentry）｛INITLISTHEAD（list）；｝｝staticinlinevoidlistsplice（conststructlistheadlist，structlistheadprev，structlistheadnext）｛｝listsplicejointwolists，thisisdesignedforstackslist：thenewlisttoadd。head：theplacetoadditinthefirstlist。staticinlinevoidlistsplice（conststructlistheadlist，structlistheadhead）｛if（！listempty（list））listsplice（list，head，headnext）；｝listsplicetailjointwolists，eachlistbeingaqueuelist：thenewlisttoadd。head：theplacetoadditinthefirstlist。staticinlinevoidlistsplicetail（structlistheadlist，structlistheadhead）｛if（！listempty（list））listsplice（list，headprev，head）；｝listspliceinitjointwolistsandreinitialisetheemptiedlist。list：thenewlisttoadd。head：theplacetoadditinthefirstlist。Thelistatlistisreinitialisedstaticinlinevoidlistspliceinit（structlistheadlist，structlistheadhead）｛if（！listempty（list））｛listsplice（list，head，headnext）；INITLISTHEAD（list）；｝｝listsplicetailinitjointwolistsandreinitialisetheemptiedlistlist：thenewlisttoadd。head：theplacetoadditinthefirstlist。Eachofthelistsisaqueue。Thelistatlistisreinitialisedstaticinlinevoidlistsplicetailinit（structlistheadlist，structlistheadhead）｛if（！listempty（list））｛listsplice（list，headprev，head）；INITLISTHEAD（list）；｝｝listentrygetthestructforthisentryptr：thestructlistheadpointer。type：thetypeofthestructthisisembeddedin。member：thenameofthelistheadwithinthestruct。definelistentry（ptr，type，member）containerof（ptr，type，member）listfirstentrygetthefirstelementfromalistptr：thelistheadtotaketheelementfrom。type：thetypeofthestructthisisembeddedin。member：thenameofthelistheadwithinthestruct。Note，thatlistisexpectedtobenotempty。definelistfirstentry（ptr，type，member）listentry（（ptr）next，type，member）listlastentrygetthelastelementfromalistptr：thelistheadtotaketheelementfrom。type：thetypeofthestructthisisembeddedin。member：thenameofthelistheadwithinthestruct。Note，thatlistisexpectedtobenotempty。definelistlastentry（ptr，type，member）listentry（（ptr）prev，type，member）listfirstentryornullgetthefirstelementfromalistptr：thelistheadtotaketheelementfrom。type：thetypeofthestructthisisembeddedin。member：thenameofthelistheadwithinthestruct。Notethatifthelistisempty，itreturnsNULL。definelistfirstentryornull（ptr，type，member）（｛structlistheadhead（ptr）；pos！head？listentry（pos，type，member）：NULL；｝）listnextentrygetthenextelementinlistpos：thetypetocursormember：thenameofthelistheadwithinthestruct。definelistnextentry（pos，member）listentry（（pos）member。next，typeof（（pos）），member）listpreventrygettheprevelementinlistpos：thetypetocursormember：thenameofthelistheadwithinthestruct。definelistpreventry（pos，member）listentry（（pos）member。prev，typeof（（pos）），member）listforeachiterateoveralistpos：thestructlistheadtouseasaloopcursor。head：theheadforyourlist。definelistforeach（pos，head）for（pos（head）pos！（head）；posposnext）listforeachcontinuecontinueiterationoveralistpos：thestructlistheadtouseasaloopcursor。head：theheadforyourlist。Continuetoiterateoveralist，continuingafterthecurrentposition。definelistforeachcontinue（pos，head）for（pos！（head）；posposnext）listforeachpreviterateoveralistbackwardspos：thestructlistheadtouseasaloopcursor。head：theheadforyourlist。definelistforeachprev（pos，head）for（pos（head）pos！（head）；posposprev）listforeachsafeiterateoveralistsafeagainstremovaloflistentrypos：thestructlistheadtouseasaloopcursor。n：anotherstructlistheadtouseastemporarystoragehead：theheadforyourlist。definelistforeachsafe（pos，n，head）for（pos（head）next，pos！（head）；posn，nposnext）listforeachprevsafeiterateoveralistbackwardssafeagainstremovaloflistentrypos：thestructlistheadtouseasaloopcursor。n：anotherstructlistheadtouseastemporarystoragehead：theheadforyourlist。definelistforeachprevsafe（pos，n，head）for（pos（head）prev，pos！（head）；posn，nposprev）listentryisheadtestiftheentrypointstotheheadofthelistpos：thetypetocursorhead：theheadforyourlist。member：thenameofthelistheadwithinthestruct。definelistentryishead（pos，head，member）（posmember（head））listforeachentryiterateoverlistofgiventypepos：thetypetouseasaloopcursor。head：theheadforyourlist。member：thenameofthelistheadwithinthestruct。definelistforeachentry（pos，head，member）for（poslistfirstentry（head，typeof（pos），member）；！listentryishead（pos，head，member）；poslistnextentry（pos，member））listforeachentryreverseiteratebackwardsoverlistofgiventype。pos：thetypetouseasaloopcursor。head：theheadforyourlist。member：thenameofthelistheadwithinthestruct。definelistforeachentryreverse（pos，head，member）for（poslistlastentry（head，typeof（pos），member）；！listentryishead（pos，head，member）；poslistpreventry（pos，member））listprepareentryprepareaposentryforuseinlistforeachentrycontinue（）pos：thetypetouseasastartpointhead：theheadofthelistmember：thenameofthelistheadwithinthestruct。Preparesaposentryforuseasastartpointinlistforeachentrycontinue（）。definelistprepareentry（pos，head，member）（（pos）？：listentry（head，typeof（pos），member））listforeachentrycontinuecontinueiterationoverlistofgiventypepos：thetypetouseasaloopcursor。head：theheadforyourlist。member：thenameofthelistheadwithinthestruct。Continuetoiterateoverlistofgiventype，continuingafterthecurrentposition。definelistforeachentrycontinue（pos，head，member）for（poslistnextentry（pos，member）；！listentryishead（pos，head，member）；poslistnextentry（pos，member））listforeachentrycontinuereverseiteratebackwardsfromthegivenpointpos：thetypetouseasaloopcursor。head：theheadforyourlist。member：thenameofthelistheadwithinthestruct。Starttoiterateoverlistofgiventypebackwards，continuingafterthecurrentposition。definelistforeachentrycontinuereverse（pos，head，member）for（poslistpreventry（pos，member）；！listentryishead（pos，head，member）；poslistpreventry（pos，member））listforeachentryfromiterateoverlistofgiventypefromthecurrentpointpos：thetypetouseasaloopcursor。head：theheadforyourlist。member：thenameofthelistheadwithinthestruct。Iterateoverlistofgiventype，continuingfromcurrentposition。definelistforeachentryfrom（pos，head，member）for（；！listentryishead（pos，head，member）；poslistnextentry（pos，member））listforeachentryfromreverseiteratebackwardsoverlistofgiventypefromthecurrentpointpos：thetypetouseasaloopcursor。head：theheadforyourlist。member：thenameofthelistheadwithinthestruct。Iteratebackwardsoverlistofgiventype，continuingfromcurrentposition。definelistforeachentryfromreverse（pos，head，member）for（；！listentryishead（pos，head，member）；poslistpreventry（pos，member））listforeachentrysafeiterateoverlistofgiventypesafeagainstremovaloflistentrypos：thetypetouseasaloopcursor。n：anothertypetouseastemporarystoragehead：theheadforyourlist。member：thenameofthelistheadwithinthestruct。definelistforeachentrysafe（pos，n，head，member）for（poslistfirstentry（head，typeof（pos），member），nlistnextentry（pos，member）；！listentryishead（pos，head，member）；posn，nlistnextentry（n，member））listforeachentrysafecontinuecontinuelistiterationsafeagainstremovalpos：thetypetouseasaloopcursor。n：anothertypetouseastemporarystoragehead：theheadforyourlist。member：thenameofthelistheadwithinthestruct。Iterateoverlistofgiventype，continuingaftercurrentpoint，safeagainstremovaloflistentry。definelistforeachentrysafecontinue（pos，n，head，member）for（poslistnextentry（pos，member），nlistnextentry（pos，member）；！listentryishead（pos，head，member）；posn，nlistnextentry（n，member））listforeachentrysafefromiterateoverlistfromcurrentpointsafeagainstremovalpos：thetypetouseasaloopcursor。n：anothertypetouseastemporarystoragehead：theheadforyourlist。member：thenameofthelistheadwithinthestruct。Iterateoverlistofgiventypefromcurrentpoint，safeagainstremovaloflistentry。definelistforeachentrysafefrom（pos，n，head，member）for（nlistnextentry（pos，member）；！listentryishead（pos，head，member）；posn，nlistnextentry（n，member））listforeachentrysafereverseiteratebackwardsoverlistsafeagainstremovalpos：thetypetouseasaloopcursor。n：anothertypetouseastemporarystoragehead：theheadforyourlist。member：thenameofthelistheadwithinthestruct。Iteratebackwardsoverlistofgiventype，safeagainstremovaloflistentry。definelistforeachentrysafereverse（pos，n，head，member）for（poslistlastentry（head，typeof（pos），member），nlistpreventry（pos，member）；！listentryishead（pos，head，member）；posn，nlistpreventry（n，member））listsaferesetnextresetastalelistforeachentrysafelooppos：theloopcursorusedinthelistforeachentrysafeloopn：temporarystorageusedinlistforeachentrysafemember：thenameofthelistheadwithinthestruct。listsaferesetnextisnotsafetouseingeneralifthelistmaybemodifiedconcurrently（eg。thelockisdroppedintheloopbody）。Anexceptiontothisisifthecursorelement（pos）ispinnedinthelist，andlistsaferesetnextiscalledafterretakingthelockandbeforecompletingthecurrentiterationoftheloopbody。definelistsaferesetnext（pos，n，member）nlistnextentry（pos，member）Doublelinkedlistswithasinglepointerlisthead。Mostlyusefulforhashtableswherethetwopointerlistheadistoowasteful。YoulosetheabilitytoaccessthetailinO（1）。structhlisthead｛｝；structhlistnode｛structhlistnodenext，｝；defineHLISTHEADINIT｛。firstNULL｝defineHLISTHEAD（name）structhlistheadname｛。firstNULL｝defineINITHLISTHEAD（ptr）（（ptr）firstNULL）staticinlinevoidINITHLISTNODE（structhlistnodeh）｛hnextNULL；hpprevNULL；｝hlistunhashedHasnodebeenremovedfromlistandreinitialized？h：NodetobecheckedNotthatnotallremovalfunctionswillleaveanodeinunhashedstate。Forexample，hlistnullsdelinitrcu（）doesleavethenodeinunhashedstate，buthlistnullsdel（）doesnot。staticinlineinthlistunhashed（conststructhlistnodeh）｛return！｝hlistunhashedlocklessVersionofhlistunhashedforlocklessuseh：NodetobecheckedThisvariantofhlistunhashed（）mustbeusedinlocklesscontextstoavoidpotentialloadtearing。TheREADONCE（）ispairedwiththevariousWRITEONCE（）inhlisthelpersthataredefinedbelow。staticinlineinthlistunhashedlockless（conststructhlistnodeh）｛return！｝hlistemptyIsthespecifiedhlistheadstructureanemptyhlist？h：Structuretocheck。staticinlineinthlistempty（conststructhlistheadh）｛return！｝staticinlinevoidhlistdel（structhlistnoden）｛if（next）｝hlistdelDeletethespecifiedhlistnodefromitslistn：Nodetodelete。Notethatthisfunctionleavesthenodeinhashedstate。Usehlistdelinit（）orsimilarinsteadtounhashn。staticinlinevoidhlistdel（structhlistnoden）｛hlistdel（n）；nnextLISTPOISON1；npprevLISTPOISON2；｝hlistdelinitDeletethespecifiedhlistnodefromitslistandinitializen：Nodetodelete。Notethatthisfunctionleavesthenodeinunhashedstate。staticinlinevoidhlistdelinit（structhlistnoden）｛if（！hlistunhashed（n））｛hlistdel（n）；INITHLISTNODE（n）；｝｝hlistaddheadaddanewentryatthebeginningofthehlistn：newentrytobeaddedh：hlistheadtoadditafterInsertanewentryafterthespecifiedhead。Thisisgoodforimplementingstacks。staticinlinevoidhlistaddhead（structhlistnoden，structhlistheadh）｛if（first）｝hlistaddbeforeaddanewentrybeforetheonespecifiedn：newentrytobeaddednext：hlistnodetoadditbefore，whichmustbenonNULLstaticinlinevoidhlistaddbefore（structhlistnoden，structhlistnodenext）｛（npprev）n；｝hlistaddbehindaddanewentryaftertheonespecifiedn：newentrytobeaddedprev：hlistnodetoadditafter，whichmustbenonNULLstaticinlinevoidhlistaddbehind（structhlistnoden，structhlistnodeprev）｛if（nnext）｝hlistaddfakecreateafakehlistconsistingofasingleheadlessnoden：NodetomakeafakelistoutofThismakesnappeartobeitsownpredecessoronaheadlesshlist。Thepointofthisistoallowthingslikehlistdel（）toworkcorrectlyincaseswherethereisnolist。staticinlinevoidhlistaddfake（structhlistnoden）｛｝hlistfake：Isthisnodeafakehlist？h：Nodetocheckforbeingaselfreferentialfakehlist。staticinlineboolhlistfake（structhlistnodeh）｛｝hlistissingularnodeisnodetheonlyelementofthespecifiedhlist？n：Nodetocheckforsingularity。h：Headerforpotentiallysingularlist。Checkwhetherthenodeistheonlynodeoftheheadwithoutaccessinghead，thusavoidingunnecessarycachemisses。staticinlineboolhlistissingularnode（structhlistnoden，structhlistheadh）｛return！｝hlistmovelistMoveanhlistold：hlistheadforoldlist。new：hlistheadfornewlist。Movealistfromonelistheadtoanother。Fixupthepprevreferenceofthefirstentryifitexists。staticinlinevoidhlistmovelist（structhlistheadold，structhlistheadnew）｛if（newfirst）oldfirstNULL；｝definehlistentry（ptr，type，member）containerof（ptr，type，member）definehlistforeach（pos，head）for（pos（head）posposnext）definehlistforeachsafe（pos，n，head）for（pos（head）pos（｛1；｝）；posn）definehlistentrysafe（ptr，type，member）（｛typeof（ptr）ptr（ptr）；ptr？hlistentry（ptr，type，member）：NULL；｝）hlistforeachentryiterateoverlistofgiventypepos：thetypetouseasaloopcursor。head：theheadforyourlist。member：thenameofthehlistnodewithinthestruct。definehlistforeachentry（pos，head，member）for（poshlistentrysafe（（head）first，typeof（（pos）），member）；poshlistentrysafe（（pos）member。next，typeof（（pos）），member））hlistforeachentrycontinueiterateoverahlistcontinuingaftercurrentpointpos：thetypetouseasaloopcursor。member：thenameofthehlistnodewithinthestruct。definehlistforeachentrycontinue（pos，member）for（poshlistentrysafe（（pos）member。next，typeof（（pos）），member）；poshlistentrysafe（（pos）member。next，typeof（（pos）），member））hlistforeachentryfromiterateoverahlistcontinuingfromcurrentpointpos：thetypetouseasaloopcursor。member：thenameofthehlistnodewithinthestruct。definehlistforeachentryfrom（pos，member）for（；poshlistentrysafe（（pos）member。next，typeof（（pos）），member））hlistforeachentrysafeiterateoverlistofgiventypesafeagainstremovaloflistentrypos：thetypetouseasaloopcursor。n：astructhlistnodetouseastemporarystoragehead：theheadforyourlist。member：thenameofthehlistnodewithinthestruct。definehlistforeachentrysafe（pos，n，head，member）for（poshlistentrysafe（（head）first，typeof（pos），member）；pos（｛nposmember。1；｝）；poshlistentrysafe（n，typeof（pos），member））endif