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如下