一文学习golang数据结构的底层实现

基本数据结构

map

原始map

基础

deletelen_type.alg.hash_type.alg.equal

实现

数据结构

type hmap struct {
    count        int  //元素个数
    flags        uint8   
    B            uint8 //扩容常量
    noverflow    uint16 //溢出 bucket 个数
    hash0        uint32 //hash 种子
    buckets      unsafe.Pointer //bucket 数组指针
    oldbuckets   unsafe.Pointer //扩容时旧的buckets 数组指针
    nevacuate    uintptr  //扩容搬迁进度
    extra        *mapextra //记录溢出相关
}

type bmap struct {
    tophash        [bucketCnt]uint8  
    // Followed by bucketCnt keys 
    //and then bucketan Cnt values  
    // Followed by overflow pointer.
}

sync.Map

HashTable

https://blog.csdn.net/u011957758/article/details/96633984

string

//拼接字符串直接通过 +
var a = "123"
var b = "321"
var c = a+b //123321

//删和改必须转为 []byte或者[]rune数组，然后再转回字符串
var a = "123"
var b = []byte(a)
b[0] = '2'
a = string(b)

//查：就是遍历或者下标访问string或[]byte
var a = "123"
var b = a[0]

var a = `123\n`
var b = "123\n"

strings包

• 这个包下定义了大量使用字符串的常见方法，非常

https://barry.blog.csdn.net/article/details/118034671?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-2-118034671-blog-123033345.pc_relevant_scanpaymentv1&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-2-118034671-blog-123033345.pc_relevant_scanpaymentv1&utm_relevant_index=5

Builder和Buffer

• 在go中可以通过strings.Builder拼接字符串或者使用bytes.Buffer，但是都不是线程安全的

slice

基础

var a = make([]int,2,5) //cap>len

a = append(a,12) //a走覆盖的路径，然后len变为3<5不需要扩容
b = append(b,10) //b走覆盖的路径，然后len也是3<5不需要扩容

//这时b[2]覆盖了a[2];导致丢失修改

数据结构

//切片数据结构
type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

//切片运行时表示
type slice struct {
	Data  uintptr
	len   int
	cap   int
}

扩容和缩容

appenda = append(a,1)appendappendlen

growslice

func growslice(et *_type, old slice, cap int) slice {
	if raceenabled {
		callerpc := getcallerpc()
		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, abi.FuncPCABIInternal(growslice))
	}

	//nil/空切片，进行初始化
	if et.size == 0 {
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}

	newcap := old.cap
	doublecap := newcap + newcap
    //模式1：大于两倍
	if cap > doublecap {
		//直接使用期待容量
        newcap = cap
	} else {
        //模式2：小于256，两倍扩容
		const threshold = 256
		if old.cap < threshold {
			newcap = doublecap
		} else {
			//模式3：每次1/4扩容
			for 0 < newcap && newcap < cap {
				newcap += (newcap + 3*threshold) / 4
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}

	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	//根据元素占用的字节数【1,2,8】进行内存对齐
	switch {
	case et.size == 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	case et.size == goarch.PtrSize:
		lenmem = uintptr(old.len) * goarch.PtrSize
		newlenmem = uintptr(cap) * goarch.PtrSize
		capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
		newcap = int(capmem / goarch.PtrSize)
	case isPowerOfTwo(et.size):
		var shift uintptr
		if goarch.PtrSize == 8 {
			// Mask shift for better code generation.
			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
		} else {
			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
		}
		lenmem = uintptr(old.len) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
	}

	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: cap out of range"))
	}

	var p unsafe.Pointer
	//覆盖
    if et.ptrdata == 0 {
		p = mallocgc(capmem, nil, false)
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
        //申请空间
		p = mallocgc(capmem, et, true)
		if lenmem > 0 && writeBarrier.enabled {
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
		}
	}
	memmove(p, old.array, lenmem)

	return slice{p, old.len, newcap}
}

makeslice

func makeslice(et *_type, len, cap int) unsafe.Pointer {
	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
	if overflow || mem > maxAlloc || len < 0 || len > cap {
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}
	//根据需要申请slice结构体（不包括数组）
	return mallocgc(mem, et, true)
}

channel

基础

select

数据结构

type hchan struct {
	//channel队列里面总的数据量
	qcount   uint           // total data in the queue
	// 循环队列的容量，如果是非缓冲的channel就是0
	dataqsiz uint           // size of the circular queue
	// 缓冲队列，数组类型。这是一个环形数组
	buf      unsafe.Pointer // points to an array of dataqsiz elements
    // 队列send索引。当前读到的位置
	sendx    uint   // send index
	// 队列receive索引。当前写入的位置
	recvx    uint   // receive index
	// 元素占用字节的size
	elemsize uint16
    
	// 当前队列关闭标志位，非零表示关闭
	closed   uint32
	// 队列里面元素类型
	elemtype *_type // element type
    
    
	// 等待channel的G队列。
	recvq    waitq  // list of recv waiters
	// 向channel发送数据的G队列。
	sendq    waitq  // list of send waiters

	// 全局锁
	lock mutex
}

send

<-runtime的chansendrunnextselectgopark

func chansend(c *hchan, ep unsafe.Pointer, block bool, callerpc uintptr) bool {

    //类似单例模式
	//无锁快速检测是否关闭
	if !block && c.closed == 0 && full(c) {
		return false
	}
	//加锁开始尝试操作
	lock(&c.lock)
	//再次检查
	if c.closed != 0 {
		unlock(&c.lock)
		panic(plainError("send on closed channel"))
	}
	//模式1：存在等待的接受者直接向接受者发送
	if sg := c.recvq.dequeue(); sg != nil {
		send(c, sg, ep, func() { unlock(&c.lock) }, 3)
		return true
	}
	//模式2：缓存区还未满，向缓存区发送
	if c.qcount < c.dataqsiz {
		qp := chanbuf(c, c.sendx)
		if raceenabled {
			racenotify(c, c.sendx, nil)
		}
		typedmemmove(c.elemtype, qp, ep)
		c.sendx++
		if c.sendx == c.dataqsiz {
			c.sendx = 0
		}
		c.qcount++
		unlock(&c.lock)
		return true
	}
	//模式3-2：非阻塞，释放锁，退出
	if !block {
		unlock(&c.lock)
		return false
	}

    //模式3-1：阻塞等待
	gp := getg()
	mysg := acquireSudog()
	mysg.releasetime = 0
	if t0 != 0 {
		mysg.releasetime = -1
	}
	
    //省略部分栈堆操作检查（即是否出现指针悬浮）
    
    //发送队列
	c.sendq.enqueue(mysg)
	atomic.Store8(&gp.parkingOnChan, 1)
    //放出调度权
	gopark(chanparkcommit, unsafe.Pointer(&c.lock), waitReasonChanSend, traceEvGoBlockSend, 2)


	return true
}

revice

• revice逻辑和send基本一样；大致如下
  • 首先检查能不能直接从发送队列获取消息
  • 再检查缓冲区是否有消息
  • 最后根据是否阻塞选择：返回或者阻塞等待

func chanrecv(c *hchan, ep unsafe.Pointer, block bool) (selected, received bool) {
    

    // 无锁判断
	if !block && empty(c) {
		if atomic.Load(&c.closed) == 0 {
			return
		}
		if empty(c) {
			if raceenabled {
				raceacquire(c.raceaddr())
			}
			if ep != nil {
				typedmemclr(c.elemtype, ep)
			}
			return true, false
		}
	}
    //加锁
	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
	}
	//模式1：发送队列非空，接收发送队列的消息
	if sg := c.sendq.dequeue(); sg != nil {
		recv(c, sg, ep, func() { unlock(&c.lock) }, 3)
		return true, true
	}
	//模式2：缓存区非空
	if c.qcount > 0 {
		// Receive directly from queue
		qp := chanbuf(c, c.recvx)
		if raceenabled {
			racenotify(c, c.recvx, nil)
		}
		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
	}

	//模式3
	c.recvq.enqueue(mysg)
	atomic.Store8(&gp.parkingOnChan, 1)
	gopark(chanparkcommit, unsafe.Pointer(&c.lock), waitReasonChanReceive, traceEvGoBlockRecv, 2)
	releaseSudog(mysg)
	return true, success
}

container包

• 在go的container中包含了：
  • list：双向链表
  • heap：栈
  • ring：循环链表

list

• 这个相当于java的LinkedList，可以用于模式Queue、Deque和Stack

• 常见API

  • 

  • Init、New	创建\初始化一个双向链表
    Back、Before	相当于getLast和getFirst
    InsertBefore、InsertAfter、PushBackList、PushFrontList	前/后插入元素或者链表（相当于add和addAll）
    MoveBefore、MoveAfter、Remove	删除
    MoveToFront、MoveToAfter	移动到前/后
    PushBefore、PushAfter	在XX前/后插入

heap

• 堆：可以通过实现：Len、Swap、Less实现堆，因为heap只提供了数据结构和Push、Pop等，但是需要传入Heap（因为需要前面三个方法）

• API

  

ring

• 双向、循环链表；API如下
  •