點(diǎn)擊上方藍(lán)色“后端開發(fā)雜談”關(guān)注我們, 專注于后端日常開發(fā)技術(shù)分享

map 迭代

本文主要是針對map迭代部分的源碼分析, 可能篇幅有些過長,且全部是代碼, 請耐心閱讀. 源碼位置?src/runtime/map.go

迭代器初始化

//?mapiterinit?初始化用于在?map?上進(jìn)行遍歷的hiter結(jié)構(gòu).
//?it?指向的hiter結(jié)構(gòu)由編譯器順序傳遞在堆棧上分配,?或者由?reflect_mapiterinit?在堆上分配.
//?由于結(jié)構(gòu)包含指針,?因此兩者都需要將hiter歸零.
func?mapiterinit(t?*maptype,?h?*hmap,?it?*hiter)?{
?????//?如果開啟了競態(tài)檢測?-race
????if?raceenabled?&&?h?!=?nil?{
????????callerpc?:=?getcallerpc()
????????racereadpc(unsafe.Pointer(h),?callerpc,?funcPC(mapiterinit))
????}

????//?hmap?不存在?或者?hmap?沒有存儲數(shù)據(jù)
????if?h?==?nil?||?h.count?==?0?{
????????return
????}

????//?hiter?的大小是?12?個(gè)系統(tǒng)指針大小.?在?cmd/compile/internal/gc/reflect.go:hiter()?當(dāng)中有這樣的體現(xiàn)
????if?unsafe.Sizeof(hiter{})/sys.PtrSize?!=?12?{
????????throw("hash_iter?size?incorrect")?//?see?cmd/compile/internal/gc/reflect.go
????}
????it.t?=?t
????it.h?=?h

????//?抓取桶狀態(tài)快照
????it.B?=?h.B
????it.buckets?=?h.buckets
????if?t.bucket.ptrdata?==?0?{
????????//?重新分配?overflow,?并在?hiter?中存儲指向?overflow?和?oldoverflow.
????????//?這樣在迭代的過程中,?可以讓?overflow?bucket?處于活動(dòng)狀態(tài),?不論?table?的增長?and/or?新的?overflow
????????//?buckets?被添加到table當(dāng)中
????????h.createOverflow()
????????it.overflow?=?h.extra.overflow
????????it.oldoverflow?=?h.extra.oldoverflow
????}

????//?確定從哪里開始遍歷,?這也是map遍歷每次結(jié)果都一樣的原因
????r?:=?uintptr(fastrand())?//?隨機(jī)生成一個(gè)整數(shù)
????if?h.B?>?31-bucketCntBits?{?
????????r?+=?uintptr(fastrand())?<31?//?在B>28時(shí),?增加一個(gè)偏移量
????}
????it.startBucket?=?r?&?bucketMask(h.B)?//?開始?bucket?的?index
????it.offset?=?uint8(r?>>?h.B?&?(bucketCnt?-?1))?//?開始的?cell?位置(也是隨機(jī)數(shù)[0-7])

????//?iterator?state
????it.bucket?=?it.startBucket

????//?多個(gè)迭代器可以同事運(yùn)行.
????if?old?:=?h.flags;?old&(iterator|oldIterator)?!=?iterator|oldIterator?{
????????atomic.Or8(&h.flags,?iterator|oldIterator)?//?或操作
????}

????mapiternext(it)
}

迭代操作

//?迭代
func?mapiternext(it?*hiter)?{
????h?:=?it.h

????//?如果開啟了競態(tài)檢測?-race
????if?raceenabled?{
????????callerpc?:=?getcallerpc()
????????racereadpc(unsafe.Pointer(h),?callerpc,?funcPC(mapiternext))
????}

????//?并發(fā)訪問和寫入問題
????if?h.flags&hashWriting?!=?0?{
????????throw("concurrent?map?iteration?and?map?write")
????}
????t?:=?it.t
????bucket?:=?it.bucket
????b?:=?it.bptr
????i?:=?it.i
????checkBucket?:=?it.checkBucket

next:
????//?迭代操作
????//?current?bucket?為?nil,?第一次或者最后一次迭代
????if?b?==?nil?{
????????//?當(dāng)前的?bucket?是開始的?bucket?并且已經(jīng)遍歷過了
????????if?bucket?==?it.startBucket?&&?it.wrapped?{
????????????it.key?=?nil
????????????it.elem?=?nil
????????????return
????????}

????????//?獲取?b?(*bmap)?的真實(shí)值
????????if?h.growing()?&&?it.B?==?h.B?{
????????????//?迭代器是在擴(kuò)容過程中啟動(dòng)的,?并且擴(kuò)容過程尚未完成.
????????????//?如果我們要查看的存儲桶尚未裝滿(即old?bucket尚未搬移),?則我們需要遍歷old?bucket,?只返回將要遷移到
????????????//?該?bucket?的?cell.
????????????oldbucket?:=?bucket?&?it.h.oldbucketmask()
????????????b?=?(*bmap)(add(h.oldbuckets,?oldbucket*uintptr(t.bucketsize)))
????????????if?!evacuated(b)?{
????????????????checkBucket?=?bucket
????????????}?else?{
????????????????b?=?(*bmap)(add(it.buckets,?bucket*uintptr(t.bucketsize)))
????????????????checkBucket?=?noCheck
????????????}
????????}?else?{
????????????//?迭代器目前處于正常狀態(tài)(擴(kuò)容結(jié)束或者沒有擴(kuò)容發(fā)生)
????????????b?=?(*bmap)(add(it.buckets,?bucket*uintptr(t.bucketsize)))
????????????checkBucket?=?noCheck
????????}

????????bucket++

????????//?所有的?bucket?已經(jīng)遍歷完成
????????if?bucket?==?bucketShift(it.B)?{
????????????bucket?=?0
????????????it.wrapped?=?true?
????????}
????????i?=?0
????}

????//?遍歷選擇的?b,?返回一對?k,v
????for?;?i?????????offi?:=?(i?+?it.offset)?&?(bucketCnt?-?1)
????????//?當(dāng)前的?cell?狀態(tài)是?emptyRest,?emptyOne(空),?evacuatedEmpty(遷移前是emptyRest,?emptyOne).
????????if?isEmpty(b.tophash[offi])?||?b.tophash[offi]?==?evacuatedEmpty?{
????????????continue
????????}

????????//?獲取k,e?分別對應(yīng)?key?和?value?的內(nèi)存地址
????????k?:=?add(unsafe.Pointer(b),?dataOffset+uintptr(offi)*uintptr(t.keysize))
????????if?t.indirectkey()?{
????????????k?=?*((*unsafe.Pointer)(k))
????????}

????????e?:=?add(unsafe.Pointer(b),?dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))

????????//?去掉需要忽略的對象?
????????if?checkBucket?!=?noCheck?&&?!h.sameSizeGrow()?{
????????????//?特殊情況:?迭代器是在增長到更大的大小期間啟動(dòng)的,?尚未完成擴(kuò)容.?
????????????//?
????????????//?正在處理尚未搬移的oldbucket的存儲桶.?至少,?當(dāng)啟動(dòng)存儲桶時(shí),?它并沒有被搬移.
????????????//?因此,?正在遍歷oldbucket,?需要跳過將要轉(zhuǎn)到另一個(gè)新bucket的所有鍵?(在增長過程中,?每個(gè)oldbucket會擴(kuò)
????????????//?展為兩個(gè)bucket).
????????????//?
????????????//?reflexivekey()?//?true?if?k==k?for?all?keys
????????????if?t.reflexivekey()?||?t.key.equal(k,?k)?{
????????????????//?如果oldbucket中的?cell?不是搬移到迭代中的當(dāng)前新存儲桶的,?則將其跳過.
????????????????hash?:=?t.hasher(k,?uintptr(h.hash0))
????????????????if?hash&bucketMask(it.B)?!=?checkBucket?{
????????????????????continue
????????????????}
????????????}?else?{
????????????????//?如果k！= k(NaNs), 則 hash 不可重復(fù). 我們需要對遷移期間發(fā)送NaN的方向進(jìn)行可重復(fù)且隨機(jī)的選擇.
????????????????//?這里將使用低位的?tophash?來決定NaN的走法.
????????????????//?注意:?這種情況就是為什么我們需要兩個(gè)遷移值,?即evacuatedX和evacuatedY,?它們的低位不同.
????????????????if?checkBucket>>(it.B-1)?!=?uintptr(b.tophash[offi]&1)?{
????????????????????continue
????????????????}
????????????}
????????}

????????//?遍歷,?獲取對應(yīng)的?k,?v????????
????????if?(b.tophash[offi]?!=?evacuatedX?&&?b.tophash[offi]?!=?evacuatedY)?||
????????????!(t.reflexivekey()?||?t.key.equal(k,?k))?{
????????????//?特殊情況:?
????????????//?在正常狀況(沒有發(fā)生map擴(kuò)容[增量方式])下進(jìn)行遍歷?[也成為?golden?data];?
????????????//?或者
????????????//?key?!=?key?(只能發(fā)生?key=NANs?的狀況下),?這些key是沒法更新和刪除的,?只能在遍歷的時(shí)候返回.
????????????it.key?=?k
????????????if?t.indirectelem()?{
????????????????e?=?*((*unsafe.Pointer)(e))
????????????}
????????????it.elem?=?e
????????}?else?{
????????????//?在擴(kuò)容的狀況下,?開啟迭代
????????????//?增量擴(kuò)容已經(jīng)完成,?并且k全是正常的key(非NANs)
????????????rk,?re?:=?mapaccessK(t,?h,?k)
????????????if?rk?==?nil?{
????????????????continue?//?key?has?been?deleted,?需要再遍歷一次
????????????}
????????????it.key?=?rk
????????????it.elem?=?re
????????}

????????//?后續(xù)的處理工作
????????it.bucket?=?bucket?//?當(dāng)前的?bucket?
????????if?it.bptr?!=?b?{?//?avoid?unnecessary?write?barrier;?see?issue?14921
????????????it.bptr?=?b
????????}
????????it.i?=?i?+?1?//?cell?迭代器
????????it.checkBucket?=?checkBucket
????????return
????}

????b?=?b.overflow(t)?//?overflow?bucket
????i?=?0
????goto?next
}

推薦閱讀

• Go Map源碼解讀之?dāng)?shù)據(jù)結(jié)構(gòu)

• Go Map源碼解讀之Map創(chuàng)建

• Go Map源碼解讀之Map插入數(shù)據(jù)

• Go Map源碼解讀之Map擴(kuò)容

• Go Map源碼解讀之Map查詢和刪除

總結(jié)

以上是生活随笔為你收集整理的源码解读_Go Map源码解读之Map迭代的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。