點擊上方藍色“后端開發雜談”關注我們, 專注于后端日常開發技術分享

map 迭代

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

迭代器初始化

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

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

????//?hiter?的大小是?12?個系統指針大小.?在?cmd/compile/internal/gc/reflect.go:hiter()?當中有這樣的體現
????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

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

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

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

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

????mapiternext(it)
}

迭代操作

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

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

????//?并發訪問和寫入問題
????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?{
????????//?當前的?bucket?是開始的?bucket?并且已經遍歷過了
????????if?bucket?==?it.startBucket?&&?it.wrapped?{
????????????it.key?=?nil
????????????it.elem?=?nil
????????????return
????????}

????????//?獲取?b?(*bmap)?的真實值
????????if?h.growing()?&&?it.B?==?h.B?{
????????????//?迭代器是在擴容過程中啟動的,?并且擴容過程尚未完成.
????????????//?如果我們要查看的存儲桶尚未裝滿(即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?{
????????????//?迭代器目前處于正常狀態(擴容結束或者沒有擴容發生)
????????????b?=?(*bmap)(add(it.buckets,?bucket*uintptr(t.bucketsize)))
????????????checkBucket?=?noCheck
????????}

????????bucket++

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

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

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

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

????????//?后續的處理工作
????????it.bucket?=?bucket?//?當前的?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源碼解讀之數據結構

• Go Map源碼解讀之Map創建

• Go Map源碼解讀之Map插入數據

• Go Map源碼解讀之Map擴容

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

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。