Go源码分析(5) - 数据结构

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

func makeslice(et *_type, len, cap int) slice {
    // NOTE: The len > maxElements check here is not strictly necessary,
    // but it produces a 'len out of range' error instead of a 'cap out of range' error
    // when someone does make([]T, bignumber). 'cap out of range' is true too,
    // but since the cap is only being supplied implicitly, saying len is clearer.
    // See issue 4085.
    maxElements := maxSliceCap(et.size)
    if len < 0 || uintptr(len) > maxElements {
        panic(errorString("makeslice: len out of range"))
    }

    if cap < len || uintptr(cap) > maxElements {
        panic(errorString("makeslice: cap out of range"))
    }

    p := mallocgc(et.size*uintptr(cap), et, true)
    return slice{p, len, cap}
}

func main() {
	array := new([]int)
	(*array)[0] = 1 // nil[0] = 1     err
	println(array)
}

func growslice(et *_type, old slice, cap int) slice {
    
	// 省略一些判断...

    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
    // 省略一些后续...
}

func slicecopy(to, fm slice, width uintptr) int {
	if fm.len == 0 || to.len == 0 {
		return 0
	}

	n := fm.len
	if to.len < n {
		n = to.len
	}

	if width == 0 {
		return n
	}

	if raceenabled {
		callerpc := getcallerpc()
		pc := funcPC(slicecopy)
		racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
		racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
	}
	if msanenabled {
		msanwrite(to.array, uintptr(n*int(width)))
		msanread(fm.array, uintptr(n*int(width)))
	}

	size := uintptr(n) * width
	if size == 1 { // common case worth about 2x to do here
		// TODO: is this still worth it with new memmove impl?
		*(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
	} else {
		memmove(to.array, fm.array, size)
	}
	return n
}

type hchan struct {
	qcount   uint           // total data in the queue
	dataqsiz uint           // size of the circular queue
	buf      unsafe.Pointer // points to an array of dataqsiz elements
	elemsize uint16
	closed   uint32
	elemtype *_type // element type
	sendx    uint   // send index
	recvx    uint   // receive index
	recvq    waitq  // list of recv waiters
	sendq    waitq  // list of send waiters
	lock mutex
}

type waitq struct {
    first *sudog
    last  *sudog
}

type sudog struct {
    // The following fields are protected by the hchan.lock of the
    // channel this sudog is blocking on. shrinkstack depends on
    // this for sudogs involved in channel ops.

    g *g

    // isSelect indicates g is participating in a select, so
    // g.selectDone must be CAS'd to win the wake-up race.
    isSelect bool
    next     *sudog
    prev     *sudog
    elem     unsafe.Pointer // data element (may point to stack)

    // The following fields are never accessed concurrently.
    // For channels, waitlink is only accessed by g.
    // For semaphores, all fields (including the ones above)
    // are only accessed when holding a semaRoot lock.

    acquiretime int64
    releasetime int64
    ticket      uint32
    parent      *sudog // semaRoot binary tree
    waitlink    *sudog // g.waiting list or semaRoot
    waittail    *sudog // semaRoot
    c           *hchan // channel
}

func makechan(t *chantype, size int64) *hchan {
    elem := t.elem

    // compiler checks this but be safe.
   // 异常判断 元素类型大小限制
    if elem.size >= 1<<16 {
        throw("makechan: invalid channel element type")
    }
  // 异常判断 对齐限制
    if hchanSize%maxAlign != 0 || elem.align > maxAlign {
        throw("makechan: bad alignment")
    }
  // maxAlloc 是 Arena 区域的最大值,缓冲元素的大小与hchan相加不能超过 缓冲槽大小
    if size < 0 || int64(uintptr(size)) != size || (elem.size > 0 && uintptr(size) > (_MaxMem-hchanSize)/elem.size) {
        panic(plainError("makechan: size out of range"))
    }

    var c *hchan
    // 不是指针类型
    if elem.kind&kindNoPointers != 0 || size == 0 {
        // 在一个调用中分配内存。       
        // 在这种情况下,Hchan不包含GC感兴趣的指针：
        // buf指向相同的分配,elemtype是持久的。
        // SudoG从它们自己的线程中引用,因此无法将其收集。
        // TODO（dvyukov,rlh）：重新考虑何时收集器可以移动分配的对象。
        c = (*hchan)(mallocgc(hchanSize+uintptr(size)*elem.size, nil, true))
        if size > 0 && elem.size != 0 {
            c.buf = add(unsafe.Pointer(c), hchanSize)
        } else {
            // 竞争检测器使用此位置进行同步
            // 还可以防止我们超出分配范围（请参见问题9401）。
            c.buf = unsafe.Pointer(c)
        }
    } else {
        // 是指针类型 分配hchan结构体 buf单独分配
        c = new(hchan)
        c.buf = newarray(elem, int(size))
    }
    // 初始化元素类型的大小
    c.elemsize = uint16(elem.size)
  // 初始化元素的类型
    c.elemtype = elem
  // 初始化 channel 的容量
    c.dataqsiz = uint(size)
    if debugChan {
        print("makechan: chan=", c, "; elemsize=", elem.size, "; elemalg=", elem.alg, "; dataqsiz=", size, "\n")
    }
    return c
}

// entry point for c <- x from compiled code
//go:nosplit
func chansend1(c *hchan, elem unsafe.Pointer) {
    chansend(c, elem, true, getcallerpc(unsafe.Pointer(&c)))
}

func chansend(c *hchan, ep unsafe.Pointer, block bool, callerpc uintptr) bool {
    if c == nil {
        if !block {
            return false
        }
        gopark(nil, nil, "chan send (nil chan)", traceEvGoStop, 2)
        throw("unreachable")
    }
    ...
    
    if !block && c.closed == 0 && ((c.dataqsiz == 0 && c.recvq.first == nil) ||
        (c.dataqsiz > 0 && c.qcount == c.dataqsiz)) {
        return false
    }

    var t0 int64
    if blockprofilerate > 0 {
        t0 = cputicks()
    }

    lock(&c.lock)

    if c.closed != 0 {
        unlock(&c.lock)
        panic(plainError("send on closed channel"))
    }
    // 1
    if sg := c.recvq.dequeue(); sg != nil {
        // Found a waiting receiver. We pass the value we want to send
        // directly to the receiver, bypassing the channel buffer (if any).
        send(c, sg, ep, func() { unlock(&c.lock) }, 3)
        return true
    }

    // 2
    if c.qcount < c.dataqsiz {
        // Space is available in the channel buffer. Enqueue the element to send.
        qp := chanbuf(c, c.sendx)
        if raceenabled {
            raceacquire(qp)
            racerelease(qp)
        }
        typedmemmove(c.elemtype, qp, ep)
        c.sendx++
        if c.sendx == c.dataqsiz {
            c.sendx = 0
        }
        c.qcount++
        unlock(&c.lock)
        return true
    }

    if !block {
        unlock(&c.lock)
        return false
    }

    // Block on the channel. Some receiver will complete our operation for us.
    gp := getg()
    mysg := acquireSudog()
    mysg.releasetime = 0
    if t0 != 0 {
        mysg.releasetime = -1
    }
    // No stack splits between assigning elem and enqueuing mysg
    // on gp.waiting where copystack can find it.
    mysg.elem = ep
    mysg.waitlink = nil
    mysg.g = gp
    mysg.selectdone = nil
    mysg.c = c
    gp.waiting = mysg
    gp.param = nil
    c.sendq.enqueue(mysg)
    goparkunlock(&c.lock, "chan send", traceEvGoBlockSend, 3)

    // someone woke us up.
    if mysg != gp.waiting {
        throw("G waiting list is corrupted")
    }
    gp.waiting = nil
    if gp.param == nil {
        if c.closed == 0 {
            throw("chansend: spurious wakeup")
        }
        panic(plainError("send on closed channel"))
    }
    gp.param = nil
    if mysg.releasetime > 0 {
        blockevent(mysg.releasetime-t0, 2)
    }
    mysg.c = nil
    releaseSudog(mysg)
    return true
}

func send(c *hchan, sg *sudog, ep unsafe.Pointer, unlockf func(), skip int) {
    if raceenabled {
        if c.dataqsiz == 0 {
            racesync(c, sg)
        } else {
            // Pretend we go through the buffer, even though
            // we copy directly. Note that we need to increment
            // the head/tail locations only when raceenabled.
            qp := chanbuf(c, c.recvx)
            raceacquire(qp)
            racerelease(qp)
            raceacquireg(sg.g, qp)
            racereleaseg(sg.g, qp)
            c.recvx++
            if c.recvx == c.dataqsiz {
                c.recvx = 0
            }
            c.sendx = c.recvx // c.sendx = (c.sendx+1) % c.dataqsiz
        }
    }
  // 写入的数据不为空
    if sg.elem != nil {
    // 将数据拷贝到 hchan
        sendDirect(c.elemtype, sg, ep)
    // sudog 中数据置为 nil
        sg.elem = nil
    }
  // 取数 goroutine
    gp := sg.g
    unlockf()
  // 传入 sudug 使 param 不为空
    gp.param = unsafe.Pointer(sg)
    if sg.releasetime != 0 {
        sg.releasetime = cputicks()
    }
  // 唤醒 goroutine 
    goready(gp, skip+1)
}

func chanrecv(c *hchan, ep unsafe.Pointer, block bool) (selected, received bool) {
	// raceenabled: don't need to check ep, as it is always on the stack
	// or is new memory allocated by reflect.

	if debugChan {
		print("chanrecv: chan=", c, "\n")
	}

	if c == nil {
		if !block {
			return
		}
		gopark(nil, nil, waitReasonChanReceiveNilChan, traceEvGoStop, 2)
		throw("unreachable")
	}

	// Fast path: check for failed non-blocking operation without acquiring the lock.
	//
	// After observing that the channel is not ready for receiving, we observe that the
	// channel is not closed. Each of these observations is a single word-sized read
	// (first c.sendq.first or c.qcount, and second c.closed).
	// Because a channel cannot be reopened, the later observation of the channel
	// being not closed implies that it was also not closed at the moment of the
	// first observation. We behave as if we observed the channel at that moment
	// and report that the receive cannot proceed.
	//
	// The order of operations is important here: reversing the operations can lead to
	// incorrect behavior when racing with a close.
	if !block && (c.dataqsiz == 0 && c.sendq.first == nil ||
		c.dataqsiz > 0 && atomic.Loaduint(&c.qcount) == 0) &&
		atomic.Load(&c.closed) == 0 {
		return
	}

	var t0 int64
	if blockprofilerate > 0 {
		t0 = cputicks()
	}

	lock(&c.lock)

	if c.closed != 0 && c.qcount == 0 {
		if raceenabled {
			raceacquire(c.raceaddr())
		}
		unlock(&c.lock)
		if ep != nil {
			typedmemclr(c.elemtype, ep)
		}
		return true, false
	}

	if sg := c.sendq.dequeue(); sg != nil {
		// Found a waiting sender. If buffer is size 0, receive value
		// directly from sender. Otherwise, receive from head of queue
		// and add sender's value to the tail of the queue (both map to
		// the same buffer slot because the queue is full).
		recv(c, sg, ep, func() { unlock(&c.lock) }, 3)
		return true, true
	}

	if c.qcount > 0 {
		// Receive directly from queue
		qp := chanbuf(c, c.recvx)
		if raceenabled {
			raceacquire(qp)
			racerelease(qp)
		}
		if ep != nil {
			typedmemmove(c.elemtype, ep, qp)
		}
		typedmemclr(c.elemtype, qp)
		c.recvx++
		if c.recvx == c.dataqsiz {
			c.recvx = 0
		}
		c.qcount--
		unlock(&c.lock)
		return true, true
	}

	if !block {
		unlock(&c.lock)
		return false, false
	}

	gp := getg()
	mysg := acquireSudog()
	mysg.releasetime = 0
	if t0 != 0 {
		mysg.releasetime = -1
	}
    //在分配elem和排队mysg之间没有堆栈拆分
    //在gp.waiting上copystack可以找到它的地方。
	mysg.elem = ep
	mysg.waitlink = nil
	gp.waiting = mysg
	mysg.g = gp
	mysg.isSelect = false
	mysg.c = c
	gp.param = nil
	c.recvq.enqueue(mysg)
	goparkunlock(&c.lock, waitReasonChanReceive, traceEvGoBlockRecv, 3)

	// someone woke us up
	if mysg != gp.waiting {
		throw("G waiting list is corrupted")
	}
	gp.waiting = nil
	if mysg.releasetime > 0 {
		blockevent(mysg.releasetime-t0, 2)
	}
	closed := gp.param == nil
	gp.param = nil
	mysg.c = nil
	releaseSudog(mysg)
	return true, !closed
}

func recv(c *hchan, sg *sudog, ep unsafe.Pointer, unlockf func(), skip int) {
  // 缓存队列不为空,直接从生产者获取数据
    if c.dataqsiz == 0 {
        if raceenabled {
            racesync(c, sg)
        }
        if ep != nil {
            // copy data from sender
            recvDirect(c.elemtype, sg, ep)
        }
    } else {
        // Queue is full. Take the item at the
        // head of the queue. Make the sender enqueue
        // its item at the tail of the queue. Since the
        // queue is full, those are both the same slot.
    // 有 send 阻塞在这里,从 buf 中获取数据
        qp := chanbuf(c, c.recvx)
        if raceenabled {
            raceacquire(qp)
            racerelease(qp)
            raceacquireg(sg.g, qp)
            racereleaseg(sg.g, qp)
        }
        // copy data from queue to receiver
        if ep != nil {
      // 将 buf 中未读的当前位置数据拷贝给消费者
        typedmemmove(c.elemtype, ep, qp)
        }
        // 将阻塞的生产者数据拷贝此位置
        typedmemmove(c.elemtype, qp, sg.elem)
    // 接收元素索引向后移动
        c.recvx++
    // 环形队列如果已经加到最大就置 0
        if c.recvx == c.dataqsiz {
            c.recvx = 0
        }
    // 环形队列读取的索引位置就是写入数据环形的末端
        c.sendx = c.recvx // c.sendx = (c.sendx+1) % c.dataqsiz
    }
  // 数据置为 nil
    sg.elem = nil
  // 获取 SudoG 中的 goroutine 传递给 param 参数
    gp := sg.g
    unlockf()
    gp.param = unsafe.Pointer(sg)
    if sg.releasetime != 0 {
        sg.releasetime = cputicks()
    }
  // 唤醒 sendq 里面 SudoG 对应的 g
    goready(gp, skip+1)
}

func closechan(c *hchan) {
	if c == nil {
		panic(plainError("close of nil channel"))
	}

	lock(&c.lock)
	if c.closed != 0 {
		unlock(&c.lock)
		panic(plainError("close of closed channel"))
	}

	if raceenabled {
		callerpc := getcallerpc()
		racewritepc(c.raceaddr(), callerpc, funcPC(closechan))
		racerelease(c.raceaddr())
	}

	c.closed = 1

	var glist gList

	// release all readers
	for {
		sg := c.recvq.dequeue()
		if sg == nil {
			break
		}
		if sg.elem != nil {
			typedmemclr(c.elemtype, sg.elem)
			sg.elem = nil
		}
		if sg.releasetime != 0 {
			sg.releasetime = cputicks()
		}
		gp := sg.g
		gp.param = nil
		if raceenabled {
			raceacquireg(gp, c.raceaddr())
		}
		glist.push(gp)
	}

	// release all writers (they will panic)
	for {
		sg := c.sendq.dequeue()
		if sg == nil {
			break
		}
		sg.elem = nil
		if sg.releasetime != 0 {
			sg.releasetime = cputicks()
		}
		gp := sg.g
		gp.param = nil
		if raceenabled {
			raceacquireg(gp, c.raceaddr())
		}
		glist.push(gp)
	}
	unlock(&c.lock)

	// Ready all Gs now that we've dropped the channel lock.
	for !glist.empty() {
		gp := glist.pop()
		gp.schedlink = 0
		goready(gp, 3)
	}
}

// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
	flags     uint8
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	hash0     uint32 // hash seed
	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
	extra *mapextra // optional fields
}

// mapextra holds fields that are not present on all maps.
type mapextra struct {
	// If both key and value do not contain pointers and are inline, then we mark bucket
	// type as containing no pointers. This avoids scanning such maps.
	// However, bmap.overflow is a pointer. In order to keep overflow buckets
	// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
	// overflow and oldoverflow are only used if key and value do not contain pointers.
	// overflow contains overflow buckets for hmap.buckets.
	// oldoverflow contains overflow buckets for hmap.oldbuckets.
	// The indirection allows to store a pointer to the slice in hiter.
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap
}

type struct Bucket {
    // tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt values.
	// NOTE: packing all the keys together and then all the values together makes the
	// code a bit more complicated than alternating key/value/key/value/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
};

       LOAD    %overflow  bytes/entry     hitprobe    missprobe
       4.00         2.13        20.77         3.00         4.00
       4.50         4.05        17.30         3.25         4.50
       5.00         6.85        14.77         3.50         5.00
       5.50        10.55        12.94         3.75         5.50
       6.00        15.27        11.67         4.00         6.00
       6.50        20.90        10.79         4.25         6.50
       7.00        27.14        10.15         4.50         7.00
       7.50        34.03         9.73         4.75         7.50
       8.00        41.10         9.40         5.00         8.00

%overflow   = percentage of buckets which have an overflow bucket
bytes/entry = overhead bytes used per key/value pair
hitprobe    = # of entries to check when looking up a present key
missprobe   = # of entries to check when looking up an absent key

func makemap_small() *hmap {            
    h := new(hmap)
    h.hash0 = fastrand()          /* 创建哈希种子 */
    return h
}

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

    if h == nil {
        h = new(hmap)                /* 新建hmap结构 */
    }
    h.hash0 = fastrand()             /* 产生哈希种子 */

    B := uint8(0)
    for overLoadFactor(hint, B) {    /* 确定B的值 */
        B++
    }
    h.B = B

    if h.B != 0 {                    /* B != 0 时初始化桶指针buckets */
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)    /* 初始化桶指针 buckets并分配空间 */
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow         /* 设置溢出桶 */
        }
    }
    return h
}

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := funcPC(mapaccess1)
        racereadpc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled && h != nil {
        msanread(key, t.key.size)
    }
    if h == nil || h.count == 0 {            /* 判断哈希表中是否含有数据 */
        if t.hashMightPanic() {
            t.key.alg.hash(key, 0) // see issue 23734
        }
        return unsafe.Pointer(&zeroVal[0])
    }
    if h.flags&hashWriting != 0 {         /* 是否并发写 */
        throw("concurrent map read and map write")
    }
    alg := t.key.alg
    hash := alg.hash(key, uintptr(h.hash0))      /* 计算键的哈希值 */
    m := bucketMask(h.B)                                /* 1<<h.B -1 ,低B位掩码*/
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))    /* 找到相应的桶,hash&m为第n个桶 */
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    top := tophash(hash)            /* 计算该键tophash的值 */
bucketloop:
    for ; b != nil; b = b.overflow(t) {                            /* 依次查找桶或溢出桶的元素 */
        for i := uintptr(0); i < bucketCnt; i++ {          /* 依次遍历桶中的每个key, bucketCnt=8 */
            if b.tophash[i] != top {                          /* 如果找到top值,则比较第i个key */
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))  /* 求key地址 */
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            if alg.equal(key, k) {   /* 比较键是否相等。如果相等,则找到key对应的值 */
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                if t.indirectvalue() {
                    v = *((*unsafe.Pointer)(v))
                }
                return v
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    if raceenabled {
        callerpc := getcallerpc()
        pc := funcPC(mapassign)
        racewritepc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled {
        msanread(key, t.key.size)
    }
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    alg := t.key.alg
    hash := alg.hash(key, uintptr(h.hash0))  //1

    h.flags ^= hashWriting     //给falgs上标记

    if h.buckets == nil {
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }

again:
    bucket := hash & bucketMask(h.B)   //2
    if h.growing() {
        growWork(t, h, bucket)
    }
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
    top := tophash(hash)      //取tophash

    var inserti *uint8
    var insertk unsafe.Pointer
    var val unsafe.Pointer
bucketloop:
    for {
        for i := uintptr(0); i < bucketCnt; i++ {                        /* 遍历桶中的8个key */
            if b.tophash[i] != top {
                if isEmpty(b.tophash[i]) && inserti == nil {        //4.找到插入的位置
                    inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    val = add(unsafe.Pointer(b),  dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                }
                if b.tophash[i] == emptyRest {        
                    break bucketloop
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            if !alg.equal(key, k) {
                continue
            }
            if t.needkeyupdate() {      //3.更新
                typedmemmove(t.key, k, key)
            }
            val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            goto done
        }
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
    }

    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }

    if inserti == nil {
        newb := h.newoverflow(t, b)             //5
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        val = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectvalue() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(val) = vmem
    }
    typedmemmove(t.key, insertk, key)
    *inserti = top
    h.count++

done:
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting
    if t.indirectvalue() {
        val = *((*unsafe.Pointer)(val))
    }
    return val
}

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		pc := funcPC(mapdelete)
		racewritepc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled && h != nil {
		msanread(key, t.key.size)
	}
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.key.alg.hash(key, 0) // see issue 23734
		}
		return
	}
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}

	alg := t.key.alg
	hash := alg.hash(key, uintptr(h.hash0))

	// Set hashWriting after calling alg.hash, since alg.hash may panic,
	// in which case we have not actually done a write (delete).
	h.flags ^= hashWriting

	bucket := hash & bucketMask(h.B)
	if h.growing() {
		growWork(t, h, bucket)
	}
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
	bOrig := b
	top := tophash(hash)
search:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break search
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			k2 := k
			if t.indirectkey() {
				k2 = *((*unsafe.Pointer)(k2))
			}
			if !alg.equal(key, k2) {
				continue
			}
			// Only clear key if there are pointers in it.
			if t.indirectkey() {
				*(*unsafe.Pointer)(k) = nil
			} else if t.key.kind&kindNoPointers == 0 {
				memclrHasPointers(k, t.key.size)
			}
			v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
			if t.indirectvalue() {
				*(*unsafe.Pointer)(v) = nil
			} else if t.elem.kind&kindNoPointers == 0 {
				memclrHasPointers(v, t.elem.size)
			} else {
				memclrNoHeapPointers(v, t.elem.size)
			}
			b.tophash[i] = emptyOne
			// If the bucket now ends in a bunch of emptyOne states,
			// change those to emptyRest states.
			// It would be nice to make this a separate function, but
			// for loops are not currently inlineable.
			if i == bucketCnt-1 {
				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
					goto notLast
				}
			} else {
				if b.tophash[i+1] != emptyRest {
					goto notLast
				}
			}
			for {
				b.tophash[i] = emptyRest
				if i == 0 {
					if b == bOrig {
						break // beginning of initial bucket, we're done.
					}
					// Find previous bucket, continue at its last entry.
					c := b
					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
					}
					i = bucketCnt - 1
				} else {
					i--
				}
				if b.tophash[i] != emptyOne {
					break
				}
			}
		notLast:
			h.count--
			break search
		}
	}

	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting
}

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets.
// Note that most of these overflow buckets must be in sparse use;
// if use was dense, then we'd have already triggered regular map growth.
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	// If the threshold is too low, we do extraneous work.
	// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
	// "too many" means (approximately) as many overflow buckets as regular buckets.
	// See incrnoverflow for more details.
	if B > 15 {
		B = 15
	}
	// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
	return noverflow >= uint16(1)<<(B&15)
}

func hashGrow(t *maptype, h *hmap) {
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {    /* 判断是2倍空间扩容还是等量空间扩容 */
        bigger = 0
        h.flags |= sameSizeGrow             /* 等量空间扩容,bigger=0 */
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)   /* 分配桶空间 */

    flags := h.flags &^ (iterator | oldIterator)      /* 将buckets和oldbuckets迭代标志置0 */
    if h.flags&iterator != 0 {
        flags |= oldIterator
    }

    h.B += bigger                      /* 增量扩容为h.B+1,等量扩容为h.B */
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0                  /* 搬迁状态为0表示未进行迁移 */
    h.noverflow = 0

        /* 当key/value不是指针时,用extramap中的指针存储溢出桶,而不用bmap中的        
         * overflow。overflow表示hmap结构buckets中的溢出桶,oldoverflow表示hmap中
         * oldbuckets中的溢出桶 ,nextoverflow预分配溢出桶空间 。
         */
    if h.extra != nil && h.extra.overflow != nil {
        if h.extra.oldoverflow != nil {
            throw("oldoverflow is not nil")
        }
        h.extra.oldoverflow = h.extra.overflow
        h.extra.overflow = nil
    }
    if nextOverflow != nil {
        if h.extra == nil {
             h.extra = new(mapextra)
        }
        h.extra.nextOverflow = nextOverflow
    }
}

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
     b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))  /* oldbucket为旧桶的索引 */
     newbit := h.noldbuckets()                         /* 与原来旧桶分配的容量相等 */
     if !evacuated(b) { 
         var xy [2]evacDst   /*xy 包含x和y的 (low and high)疏散目的地.*/
         x := &xy[0]                                   /* 等量扩容或2倍扩容的前一部分（X,和原来相等） */
         x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
         x.k = add(unsafe.Pointer(x.b), dataOffset)    /* key的地址 */
         x.v = add(x.k, bucketCnt*uintptr(t.keysize))  /* value得地址 */

         if !h.sameSizeGrow() {             //如果不是等量扩容
             y := &xy[1]                               /* 若为2倍扩容,需要后一部分,即增长的空间 */
             y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))  /* 后一部分桶的索引 */
             y.k = add(unsafe.Pointer(y.b), dataOffset)
             y.v = add(y.k, bucketCnt*uintptr(t.keysize))
         }

         for ; b != nil; b = b.overflow(t) {              /* 遍历最后一个bmap及溢出桶 */
             k := add(unsafe.Pointer(b), dataOffset)      /* key的地址 */
             v := add(k, bucketCnt*uintptr(t.keysize))    /* value的地址 */
             for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {  /* 遍历桶中的元素 */
                 top := b.tophash[i]                      /* 获取tophash的值 */
                 if isEmpty(top) {                        /* 如果tophash为空,标记为已被搬迁状态 */
                     b.tophash[i] = evacuatedEmpty  
                     continue
                 }
                 if top < minTopHash {                    /* tophash的值为hash+minTopHash */
                     throw("bad map state")
                 }
                 k2 := k
                 if t.indirectkey() {
                     k2 = *((*unsafe.Pointer)(k2))
                 }
                 var useY uint8                          /* useY用来判断是落在oldbucket还是newbit */
                 if !h.sameSizeGrow() {                  /* 如果为2倍扩容,h.B增大1,桶的位置发生变化 */
                     hash := t.key.alg.hash(k2, uintptr(h.hash0))
                     if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.alg.equal(k2,k2) {
                         useY = top & 1
                         top = tophash(hash)
                     } else {
                         if hash&newbit != 0 {
                             useY = 1
                         }
                     }
                 }

                 /* evacuatedY = evacuatedX + 1 */
                 if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
                     throw("bad evacuatedN")
                 }

                 b.tophash[i] = evacuatedX + useY  /* 搬迁为X或者Y状态 */
                 dst := &xy[useY]                  /* useY=0表示搬迁到前半部分, 否则到后半部分*/

                 if dst.i == bucketCnt {           /* 当桶中元素数量达到最大8时,需要溢出桶 */
                     dst.b = h.newoverflow(t, dst.b)
                     dst.i = 0
                     dst.k = add(unsafe.Pointer(dst.b), dataOffset)
                     dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
                 }
                 dst.b.tophash[dst.i&(bucketCnt-1)] = top
                 if t.indirectkey() {
                     *(*unsafe.Pointer)(dst.k) = k2   /* key为指针时,复制指针 */
                 } else {
                     typedmemmove(t.key, dst.k, k)
                 }
                 if t.indirectvalue() {
                     *(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v) /* value为指针时,复制指针 */
                 } else {
                     typedmemmove(t.elem, dst.v, v)
                 }
                 /* 进行下一个元素的搬迁 */
                 dst.i++
                 dst.k = add(dst.k, uintptr(t.keysize))
                 dst.v = add(dst.v, uintptr(t.valuesize))
             }
         }

         /* 遍历完桶后,如果没有其他goroutine使用该桶,就把该桶清空 */
         if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
             b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
             ptr := add(b, dataOffset)
             n := uintptr(t.bucketsize) - dataOffset
             memclrHasPointers(ptr, n)
         }
     }

     if oldbucket == h.nevacuate {
         advanceEvacuationMark(h, t, newbit)
     }
 }

 /* 确定桶的搬迁进度,如果搬迁完成进行后续操作 */
 func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
     h.nevacuate++
     stop := h.nevacuate + 1024
     if stop > newbit {
         stop = newbit
     }
     for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {  /*如果搬迁没有完成将搬迁进度nevacuate加1 */
         h.nevacuate++
     }
     if h.nevacuate == newbit {
         h.oldbuckets = nil                /* 搬迁完成,将oldbuckets置nil */
         if h.extra != nil {
             h.extra.oldoverflow = nil     /* 溢出桶置为nil */
         }
         h.flags &^= sameSizeGrow          /* 等量扩容位置0 */
     }
 }