1
func makemap(t *maptype, hint int, h *hmap) *hmap {
2
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
3
    if overflow || mem > maxAlloc {
4
        hint = 0
5
    }
6

7
    if h == nil {
8
        h = new(hmap)
9
    }
10
    h.hash0 = fastrand()
11

12
    B := uint8(0)
13
    for overLoadFactor(hint, B) {
14
        B++
15
    }
16
    h.B = B
17

18
    if h.B != 0 {
19
        var nextOverflow *bmap
20
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
21
        if nextOverflow != nil {
22
            h.extra = new(mapextra)
23
            h.extra.nextOverflow = nextOverflow
24
        }
25
    }
26

27
    return h
28
}

1
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
2
    base := bucketShift(b)
3
    nbuckets := base
4
    if b >= 4 {
5
        nbuckets += bucketShift(b - 4)
6
    }
7

8
    buckets = newarray(t.bucket, int(nbuckets))
9

10
    if base != nbuckets {
11
        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
12
        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
13
        last.setoverflow(t, (*bmap)(buckets))
14
    }
15
    return buckets, nextOverflow
16
}

1
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
2
    if h == nil || h.count == 0 {
3
        return unsafe.Pointer(&zeroVal[0])
4
    }
5
    if h.flags&hashWriting != 0 {
6
        fatal("concurrent map read and map write")
7
    }
8
    hash := t.hasher(key, uintptr(h.hash0))
9
    m := bucketMask(h.B)
10
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
11
    if c := h.oldbuckets; c != nil {
12
        if !h.sameSizeGrow() {
13
            m >>= 1
14
        }
15
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
16
        if !evacuated(oldb) {
17
            b = oldb
18
        }
19
    }
20
    top := tophash(hash)
21
bucketloop:
22
    for ; b != nil; b = b.overflow(t) {
23
        for i := uintptr(0); i < bucketCnt; i++ {
24
            if b.tophash[i] != top {
25
                if b.tophash[i] == emptyRest {
26
                    break bucketloop
27
                }
28
                continue
29
            }
30
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
31
            if t.indirectkey() {
32
                k = *((*unsafe.Pointer)(k))
33
            }
34
            if t.key.equal(key, k) {
35
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
36
                if t.indirectelem() {
37
                    e = *((*unsafe.Pointer)(e))
38
                }
39
                return e
40
            }
41
        }
42
    }
43
    return unsafe.Pointer(&zeroVal[0])
44
}

1
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
2
    if h == nil {
3
        panic(plainError("assignment to entry in nil map"))
4
    }
5
    if h.flags&hashWriting != 0 {
6
        fatal("concurrent map writes")
7
    }
8
    hash := t.hasher(key, uintptr(h.hash0))
9

10
    h.flags ^= hashWriting
11

12
    if h.buckets == nil {
13
        h.buckets = newobject(t.bucket)
14
    }
15

16
again:
17
    bucket := hash & bucketMask(h.B)
18
    if h.growing() {
19
        growWork(t, h, bucket)
20
    }
21
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
22
    top := tophash(hash)
23

24
    var inserti *uint8
25
    var insertk unsafe.Pointer
26
    var elem unsafe.Pointer
27
bucketloop:
28
    for {
29
        for i := uintptr(0); i < bucketCnt; i++ {
30
            if b.tophash[i] != top {
31
                if isEmpty(b.tophash[i]) && inserti == nil {
32
                    inserti = &b.tophash[i]
33
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
34
                    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
35
                }
36
                if b.tophash[i] == emptyRest {
37
                    break bucketloop
38
                }
39
                continue
40
            }
41
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
42
            if t.indirectkey() {
43
                k = *((*unsafe.Pointer)(k))
44
            }
45
            if !t.key.equal(key, k) {
46
                continue
47
            }
48
            if t.needkeyupdate() {
49
                typedmemmove(t.key, k, key)
50
            }
51
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
52
            goto done
53
        }
54
        ovf := b.overflow(t)
55
        if ovf == nil {
56
            break
57
        }
58
        b = ovf
59
    }
60

61
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
62
        hashGrow(t, h)
63
        goto again
64
    }
65

66
    if inserti == nil {
67
        newb := h.newoverflow(t, b)
68
        inserti = &newb.tophash[0]
69
        insertk = add(unsafe.Pointer(newb), dataOffset)
70
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
71
    }
72

73
    if t.indirectkey() {
74
        kmem := newobject(t.key)
75
        *(*unsafe.Pointer)(insertk) = kmem
76
        insertk = kmem
77
    }
78
    if t.indirectelem() {
79
        vmem := newobject(t.elem)
80
        *(*unsafe.Pointer)(elem) = vmem
81
    }
82
    typedmemmove(t.key, insertk, key)
83
    *inserti = top
84
    h.count++
85

86
done:
87
    if h.flags&hashWriting == 0 {
88
        fatal("concurrent map writes")
89
    }
90
    h.flags &^= hashWriting
91
    if t.indirectelem() {
92
        elem = *((*unsafe.Pointer)(elem))
93
    }
94
    return elem
95
}

1
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
2
    if h == nil || h.count == 0 {
3
        return
4
    }
5
    if h.flags&hashWriting != 0 {
6
        fatal("concurrent map writes")
7
    }
8

9
    hash := t.hasher(key, uintptr(h.hash0))
10

11
    h.flags ^= hashWriting
12

13
    bucket := hash & bucketMask(h.B)
14
    if h.growing() {
15
        growWork(t, h, bucket)
16
    }
17
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
18
    bOrig := b
19
    top := tophash(hash)
20
search:
21
    for ; b != nil; b = b.overflow(t) {
22
        for i := uintptr(0); i < bucketCnt; i++ {
23
            if b.tophash[i] != top {
24
                if b.tophash[i] == emptyRest {
25
                    break search
26
                }
27
                continue
28
            }
29
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
30
            k2 := k
31
            if t.indirectkey() {
32
                k2 = *((*unsafe.Pointer)(k2))
33
            }
34
            if !t.key.equal(key, k2) {
35
                continue
36
            }
37
            // Only clear key if there are pointers in it.
38
            if t.indirectkey() {
39
                *(*unsafe.Pointer)(k) = nil
40
            } else if t.key.ptrdata != 0 {
41
                memclrHasPointers(k, t.key.size)
42
            }
43
            e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
44
            if t.indirectelem() {
45
                *(*unsafe.Pointer)(e) = nil
46
            } else if t.elem.ptrdata != 0 {
47
                memclrHasPointers(e, t.elem.size)
48
            } else {
49
                memclrNoHeapPointers(e, t.elem.size)
50
            }
51
            b.tophash[i] = emptyOne
52
            // 如果是末位或后续为空，则向前合并为 emptyRest
53
            if i == bucketCnt-1 {
54
                if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
55
                    goto notLast
56
                }
57
            } else {
58
                if b.tophash[i+1] != emptyRest {
59
                    goto notLast
60
                }
61
            }
62
            for {
63
                b.tophash[i] = emptyRest
64
                if i == 0 {
65
                    if b == bOrig {
66
                        break
67
                    }
68
                    c := b
69
                    for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
70
                    }
71
                    i = bucketCnt - 1
72
                } else {
73
                    i--
74
                }
75
                if b.tophash[i] != emptyOne {
76
                    break
77
                }
78
            }
79
        notLast:
80
            h.count--
81
            if h.count == 0 {
82
                h.hash0 = fastrand()
83
            }
84
            break search
85
        }
86
    }
87

88
    if h.flags&hashWriting == 0 {
89
        fatal("concurrent map writes")
90
    }
91
    h.flags &^= hashWriting
92
}

1
type hiter struct {
2
    key         unsafe.Pointer
3
    elem        unsafe.Pointer
4
    t           *maptype
5
    h           *hmap
6
    buckets     unsafe.Pointer
7
    bptr        *bmap
8
    overflow    *[]*bmap
9
    oldoverflow *[]*bmap
10
    startBucket uintptr
11
    offset      uint8
12
    wrapped     bool
13
    B           uint8
14
    i           uint8
15
    bucket      uintptr
16
    checkBucket uintptr
17
}