兄弟连区Go语言+区块链技术培训以太坊源码分析(25)core-txlist交易池的一些数据结构源码

1/21兄弟连区Go语言+区块链技术培训以太坊源码分析(25)core-txlist交易池的一些数据结构源码分析##nonceHeapnonceHeap实现了一个heap.Interface的数据结构，用来实现了一个堆的数据结构。在heap.Interface的文档介绍中，默认实现的是最小堆。如果h是一个数组，只要数组中的数据满足下面的要求。那么就认为h是一个最小堆。!h.Less(j,i)for0=ih.Len()and2*i+1=j=2*i+2andjh.Len()//把数组看成是一颗满的二叉树，第一个元素是树根，第二和第三个元素是树根的两个树枝，//这样依次推下去那么如果树根是i那么它的两个树枝就是2*i+2和2*i+2。//最小堆的定义是任意的树根不能比它的两个树枝大。也就是上面的代码描述的定义。heap.Interface的定义我们只需要定义满足下面接口的数据结构，就能够使用heap的一些方法来实现为堆结构。typeInterfaceinterface{sort.InterfacePush(xinterface{})//addxaselementLen()把x增加到最后Pop()interface{}//removeandreturnelementLen()-1.移除并返回最后的一个元素}nonceHeap的代码分析。//nonceHeapisaheap.Interfaceimplementationover64bitunsignedintegersfor//retrievingsortedtransactionsfromthepossiblygappedfuturequeue.typenonceHeap[]uint64func(hnonceHeap)Len()int{returnlen(h)}func(hnonceHeap)Less(i,jint)bool{returnh[i]h[j]}func(hnonceHeap)Swap(i,jint){h[i],h[j]=h[j],h[i]}2/21func(h*nonceHeap)Push(xinterface{}){*h=append(*h,x.(uint64))}func(h*nonceHeap)Pop()interface{}{old:=*hn:=len(old)x:=old[n-1]*h=old[0:n-1]returnx}##txSortedMaptxSortedMap,存储的是同一个账号下面的所有的交易。结构//txSortedMapisanonce-transactionhashmapwithaheapbasedindextoallow//iteratingoverthecontentsinanonce-incrementingway.//txSortedMap是一个具有基于堆的索引的nonce-交易的hashmap，//允许以nonce递增的方式迭代内容。typeTransactions[]*TransactiontypetxSortedMapstruct{itemsmap[uint64]*types.Transaction//Hashmapstoringthetransactiondataindex*nonceHeap//Heapofnoncesofallthestoredtransactions(non-strictmode)cachetypes.Transactions//Cacheofthetransactionsalreadysorted用来缓存已经排好序的交易。}Put和Get,Get用于获取指定nonce的交易，Put用来把交易插入到map中。//Getretrievesthecurrenttransactionsassociatedwiththegivennonce.func(m*txSortedMap)Get(nonceuint64)*types.Transaction{returnm.items[nonce]}3/21//Putinsertsanewtransactionintothemap,alsoupdatingthemap'snonce//index.Ifatransactionalreadyexistswiththesamenonce,it'soverwritten.//把一个新的事务插入到map中，同时更新map的nonce索引。如果一个事务已经存在，就把它覆盖。同时任何缓存的数据会被删除。func(m*txSortedMap)Put(tx*types.Transaction){nonce:=tx.Nonce()ifm.items[nonce]==nil{heap.Push(m.index,nonce)}m.items[nonce],m.cache=tx,nil}Forward用于删除所有nonce小于threshold的交易。然后返回所有被移除的交易。//Forwardremovesalltransactionsfromthemapwithanoncelowerthanthe//providedthreshold.Everyremovedtransactionisreturnedforanypost-removal//maintenance.func(m*txSortedMap)Forward(thresholduint64)types.Transactions{varremovedtypes.Transactions//Popoffheapitemsuntilthethresholdisreachedform.index.Len()0&&(*m.index)[0]threshold{nonce:=heap.Pop(m.index).(uint64)removed=append(removed,m.items[nonce])delete(m.items,nonce)}//Ifwehadacachedorder,shiftthefront//cache是排好序的交易。ifm.cache!=nil{m.cache=m.cache[len(removed):]}returnremoved}Filter,删除所有令filter函数调用返回true的交易，并返回那些交易。4/21//Filteriteratesoverthelistoftransactionsandremovesallofthemforwhich//thespecifiedfunctionevaluatestotrue.func(m*txSortedMap)Filter(filterfunc(*types.Transaction)bool)types.Transactions{varremovedtypes.Transactions//Collectallthetransactionstofilteroutfornonce,tx:=rangem.items{iffilter(tx){removed=append(removed,tx)delete(m.items,nonce)}}//Iftransactionswereremoved,theheapandcacheareruined//如果事务被删除，堆和缓存被毁坏iflen(removed)0{*m.index=make([]uint64,0,len(m.items))fornonce:=rangem.items{*m.index=append(*m.index,nonce)}//需要重建堆heap.Init(m.index)//设置cache为nilm.cache=nil}returnremoved}Cap对items里面的数量有限制，返回超过限制的所有交易。//Capplacesahardlimitonthenumberofitems,returningalltransactions//exceedingthatlimit.//Cap对items里面的数量有限制，返回超过限制的所有交易。func(m*txSortedMap)Cap(thresholdint)types.Transactions{//Shortcircuitifthenumberofitemsisunderthelimitiflen(m.items)=threshold{returnnil}//Otherwisegatheranddropthehighestnonce'dtransactionsvardropstypes.Transactions5/21sort.Sort(*m.index)//从小到大排序从尾部删除。forsize:=len(m.items);sizethreshold;size--{drops=append(drops,m.items[(*m.index)[size-1]])delete(m.items,(*m.index)[size-1])}*m.index=(*m.index)[:threshold]//重建堆heap.Init(m.index)//Ifwehadacache,shiftthebackifm.cache!=nil{m.cache=m.cache[:len(m.cache)-len(drops)]}returndrops}Remove//Removedeletesatransactionfromthemaintainedmap,returningwhetherthe//transactionwasfound.//func(m*txSortedMap)Remove(nonceuint64)bool{//Shortcircuitifnotransactionispresent_,ok:=m.items[nonce]if!ok{returnfalse}//Otherwisedeletethetransactionandfixtheheapindexfori:=0;im.index.Len();i++{if(*m.index)[i]==nonce{heap.Remove(m.index,i)break}}delete(m.items,nonce)m.cache=nilreturntrue}Ready函数6/21//Readyretrievesasequentiallyincreasinglistoftransactionsstartingatthe//providednoncethatisreadyforprocessing.Thereturnedtransactionswillbe//removedfromthelist.//Ready返回一个从指定nonce开始，连续的交易。返回的交易会被删除。//Note,alltransactionswithnonceslowerthanstartwillalsobereturnedto//preventgettingintoandinvalidstate.Thisisnotsomethingthatshouldever//happenbutbettertobeselfcorrectingthanfailing!//注意，请注意，所有具有低于start的nonce的交易也将被返回，以防止进入和无效状态。//这不是应该发生的事情，而是自我纠正而不是失败！func(m*txSortedMap)Ready(startuint64)types.Transactions{//Shortcircuitifnotransactionsareavailableifm.index.Len()==0||(*m.index)[0]start{returnnil}//Otherwisestartaccumulatingincrementaltransactionsvarreadytypes.Transactions//从最小的开始，一个一个的增加，for