golang二级指针操作链表

golang利用二级指针操作链表

以下所有观点都是个人愚见,有不同建议或补充的的欢迎emial我aboutme

导读

之前开了个项目来看golang runtime源码https://github.com/zboya/golang_runtime_reading,发现实现全局P链表的代码挺有趣的,遂研究记录一下。

先看个例子

package ptplist

import (
	"log"
	"testing"
	"unsafe"
)

type puintptr uintptr

//go:nosplit
func (pp puintptr) ptr() *p { return (*p)(unsafe.Pointer(pp)) }

//go:nosplit
func (pp *puintptr) set(p *p) { *pp = puintptr(unsafe.Pointer(p)) }

type p struct {
	id   int
	link puintptr
}

var pidleList puintptr 

func pidleput(_p_ *p) {
	_p_.link = pidleList
	pidleList.set(_p_)
}

func pidleget() *p {
	_p_ := pidleList.ptr()
	if _p_ != nil {
		pidleList = _p_.link
	}
	return _p_
}

func TestPtoPList(t *testing.T) {
	for i := 0; i < 5; i++ {
		tp := p{id: i}
		pidleput(&tp)
		log.Printf("put p: %d", i)
	}
	log.Println("")
	for i := 0; i < 5; i++ {
		tp := pidleget()
		log.Printf("get p: %d", tp.id)
	}

}

结果:

=== RUN   TestPtoPList
2018/08/28 17:25:22 put p: 0
2018/08/28 17:25:22 put p: 1
2018/08/28 17:25:22 put p: 2
2018/08/28 17:25:22 put p: 3
2018/08/28 17:25:22 put p: 4
2018/08/28 17:25:22 
2018/08/28 17:25:22 get p: 4
2018/08/28 17:25:22 get p: 3
2018/08/28 17:25:22 get p: 2
2018/08/28 17:25:22 get p: 1
2018/08/28 17:25:22 get p: 0
--- PASS: TestPtoPList (0.00s)

分析

从结果上看pidleList实现了一个栈,pidleput把一个新的p push到pidleListpidleget是从pidleList pop出一个p。 具体看看这个怎么实现的:

type puintptr uintptr

首先我们定义了puintptr类型,底层类型为uintptr。uintptr是整型,可以足够保存指针的值得范围,在32平台下为4字节,在64位平台下是8字节,它和unsafe.Pointer可相互转换。 uintptr和unsafe.Pointer的区别就是:unsafe.Pointer只是单纯的通用指针类型,用于转换不同类型指针,它不可以参与指针运算;而uintptr是可用于指针运算的。

uintptr和unsafe.Pointer互转换

func TestUintprt1(t *testing.T) {
	var a int
	a = 2018
	b := (*int)(unsafe.Pointer(&a))
	t.Logf("a.addr=%p, b.addr=%p, *b=%d", &a, b, *b)
	buintptr := uintptr((unsafe.Pointer(&a)))
	t.Logf("buintptr=0x%x", buintptr)
}

output:

a.addr=0xc42008e1e0, b.addr=0xc42008e1e0, *b=2018
buintptr=0xc42008e1e0

buintptr的值就等于a的地址

uintptr的指针运算取数组

func TestUintprt2(t *testing.T) {
	var a [2]int
	a[0] = 2018
	a[1] = 2019

	t.Logf("a0.addr=%p, a1.addr=%p", &a[0], &a[1])
	auintptr := uintptr((unsafe.Pointer(&a)))
	t.Logf("auintptr=0x%x", auintptr)
	// 把auintptr的值加上一个指针的长度, 和C语言的p++一样
	a1uintptr := auintptr + unsafe.Sizeof(&a)
	a1pointer := unsafe.Pointer(a1uintptr)
	// 得到a[1]
	a1 := *(*int)(a1pointer)
	t.Logf("a1pointer=%p, a1=%d", a1pointer, a1)
}

output:

a0.addr=0xc42009c1e0, a1.addr=0xc42009c1e8
auintptr=0xc42009c1e0
a1pointer=0xc42009c1e8, a1=2019

获取到auintptr表示a数组的首地址,把它加上一个指针长度,就会得到a数组下一个元素。这个和C语言的p++是一样的,只不过golang不推崇指针运算,写起来很麻烦。

//go:nosplit
func (pp puintptr) ptr() *p { return (*p)(unsafe.Pointer(pp)) }

//go:nosplit
func (pp *puintptr) set(p *p) { *pp = puintptr(unsafe.Pointer(p)) }

接着给puintptr类型增加了两个方法,比如现有有个puintptr类型的值pl,那么:
ptr()方法,将pl变为p类型的指针返回,set(p *p)方法将p的地址转换为puintptr,并将这puintptr赋值给pl,也就是说pl的值等于p的地址。 这里的pp是pl的指针,*pl就是二级指针了。理解这两个方法就好理解代码了。

func pidleput(_p_ *p) {
    // 将pidleList赋值给link ,最开始的时候pidleList为0,但是之后pidleList是上个p的地址
    _p_.link = pidleList
    // pidleList保存_p_的地址
	pidleList.set(_p_)
}

接着定义put方法,_p_.link保存上个p的地址,pidleList保存当前_p_的地址,这里就构成了单向链表,看图最明显

/*
        p1                 p2
	+-------+           +-------+
	|   id  |<-----+    |   id  |<------ pidleList
	+-------+      |    +-------+
	| link  |      +----| link  |
	+-------+           +-------+
*/

所以每当pidleput时将当前p的link指向上个p,pidleList指向最新的p

func pidleget() *p {
    // 获取pidleList指向的p
    _p_ := pidleList.ptr()
    // _p_ 不等于0
	if _p_ != nil {
        // 将pidleList重新指向下一个p
		pidleList = _p_.link
	}
	return _p_
}

理解了上面的pidleget就简单了。

golang 源码

想具体看源码的话可以看下面的连接:

https://github.com/zboya/golang_runtime_reading/blob/master/src/runtime/proc.go

https://github.com/zboya/golang_runtime_reading/blob/master/src/runtime/runtime2.go

Go 
comments powered by Disqus