Go源码: slice
发布于 2018-05-07 · 本文总共 11851 字 · 阅读大约需要
34 分钟
数据结构
// SliceHeader is the runtime representation of a slice.
// It cannot be used safely or portably and its representation may
// change in a later release.
// Moreover, the Data field is not sufficient to guarantee the data
// it references will not be garbage collected, so programs must keep
// a separate, correctly typed pointer to the underlying data.
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
初始化
1.通过下标的方式获得数组或者切片的一部分；
slice0 := s[:]
2.使用字面量初始化新的切片；
slice1 := []int{1,2,3}
3.使用关键字 make 创建切片：
slice2 := make([]int, 3) len:3, cap:3
slice3 := make([]int, 0, 3) len: 0, cap: 3
不同初始化方式slice的len和cap：
func TestSliceInit(t *testing.T) {
s := []int{}
fmt.Printf("slice init, len: %d, cap: %d, value: %+v, address: %p.\n", len(s), cap(s), s, s)
// slice init, len: 0, cap: 0, value: [], address: 0x1264148.
var s1 []int
fmt.Printf("slice init, len: %d, cap: %d, value: %+v, address: %p.\n", len(s1), cap(s1), s1, s1)
// slice init, len: 0, cap: 0, value: [], address: 0x0.
s3 := make([]int, 10)
fmt.Printf("slice init, len: %d, cap: %d, value: %+v, address: %p.\n", len(s3), cap(s3), s3, s3)
// slice init, len: 10, cap: 10, value: [0 0 0 0 0 0 0 0 0 0], address: 0xc0000fc000.
s4 := make([]int, 1, 10)
fmt.Printf("slice init, len: %d, cap: %d, value: %+v, address: %p.\n", len(s4), cap(s4), s4, s4)
// slice init, len: 1, cap: 10, value: [0], address: 0xc0000ee140.
s5 := []int{1, 2, 3, 4, 5}
fmt.Printf("slice init, len: %d, cap: %d, value: %+v, address: %p.\n", len(s5), cap(s5), s5, s5)
// slice init, len: 5, cap: 5, value: [1 2 3 4 5], address: 0xc0000fe000.
}
make源码
// The make built-in function allocates and initializes an object of type
// slice, map, or chan (only). Like new, the first argument is a type, not a
// value. Unlike new, make's return type is the same as the type of its
// argument, not a pointer to it. The specification of the result depends on
// the type:
// Slice: The size specifies the length. The capacity of the slice is
// equal to its length. A second integer argument may be provided to
// specify a different capacity; it must be no smaller than the
// length. For example, make([]int, 0, 10) allocates an underlying array
// of size 10 and returns a slice of length 0 and capacity 10 that is
// backed by this underlying array.
// Map: An empty map is allocated with enough space to hold the
// specified number of elements. The size may be omitted, in which case
// a small starting size is allocated.
// Channel: The channel's buffer is initialized with the specified
// buffer capacity. If zero, or the size is omitted, the channel is
// unbuffered.
func make(t Type, size ...IntegerType) Type
Slice: The size specifies the length. The capacity of the slice is equal to its length. A second integer argument may be provided to specify a different capacity; it must be no smaller than the length. For example, make([]int, 0, 10) allocates an underlying array of size 10 and returns a slice of length 0 and capacity 10 that is backed by this underlying array.
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 {
// NOTE: Produce 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 golang.org/issue/4085.
mem, overflow := math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}
return mallocgc(mem, et, true)
}
注意
- make初始化时，如果只指定一个参数，默认len和cap相等且为指定值
s := make([]int, 10)
func TestSliceTest2(t *testing.T) {
s := make([]int, 10)
fmt.Println(len(s), cap(s), s)
// 10 10 [0 0 0 0 0 0 0 0 0 0]
for i := 0;i< 10; i++{
s = append(s, i)
}
fmt.Println(s)
}
// [0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9]
- 值传递和引用传递
slice是struct，struct是值传递
func AppendSlice(s []int) {
s = append(s, 100)
}
func AppendSlice1(s *[]int) {
*s = append(*s, 100)
}
func TestSliceTest3(t *testing.T) {
s := make([]int, 0, 10)
fmt.Println(len(s), cap(s), s)
// 0 10 []
s = append(s, 1)
fmt.Println(len(s), cap(s), s)
// 1 10 [1]
AppendSlice(s)
fmt.Println(len(s), cap(s), s)
// 1 10 [1]
AppendSlice1(&s)
fmt.Println(len(s), cap(s), s)
// 2 10 [1 100]
}
test case2
func AppendSlice(s []int) {
s[0] = 100
s = append(s, 100)
}
func AppendSlice1(s *[]int) {
*s = append(*s, 100)
}
func TestSliceTest3(t *testing.T) {
s := make([]int, 0, 10)
fmt.Println(len(s), cap(s), s)
// 0 10 []
s = append(s, 1)
fmt.Println(len(s), cap(s), s)
// 1 10 [1]
AppendSlice(s)
fmt.Println(len(s), cap(s), s)
// 1 10 [100]
AppendSlice1(&s)
fmt.Println(len(s), cap(s), s)
// 2 10 [100 100]
}
扩容
func CapOfSlice() {
s := []int{}
// len: 0 cap: 0
preCap := 0
for i := 0; i < 1000; i++ {
s = append(s, i)
if cap(s) != preCap {
fmt.Println("len: ", len(s), " cap: ", cap(s))
preCap = cap(s)
}
}
// len: 1 cap: 1
// len: 2 cap: 2
// len: 3 cap: 4
// len: 5 cap: 8
// len: 9 cap: 16
// len: 17 cap: 32
// len: 33 cap: 64
// len: 65 cap: 128
// len: 129 cap: 256
// len: 257 cap: 512
// len: 513 cap: 1024
}
1.如果期望容量大于当前容量的两倍就会使用期望容量；
2.如果当前切片容量小于 1024 就会将容量翻倍；
3.如果当前切片容量大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；
// growslice handles slice growth during append.
// It is passed the slice element type, the old slice, and the desired new minimum capacity,
// and it returns a new slice with at least that capacity, with the old data
// copied into it.
// The new slice's length is set to the old slice's length,
// NOT to the new requested capacity.
// This is for codegen convenience. The old slice's length is used immediately
// to calculate where to write new values during an append.
// TODO: When the old backend is gone, reconsider this decision.
// The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
func growslice(et *_type, old slice, cap int) slice {
if raceenabled {
callerpc := getcallerpc()
racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
}
if msanenabled {
msanread(old.array, uintptr(old.len*int(et.size)))
}
if cap < old.cap {
panic(errorString("growslice: cap out of range"))
}
if et.size == 0 {
// append should not create a slice with nil pointer but non-zero len.
// We assume that append doesn't need to preserve old.array in this case.
return slice{unsafe.Pointer(&zerobase), old.len, cap}
}
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
}
}
}
var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.size.
// For 1 we don't need any division/multiplication.
// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
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 == sys.PtrSize:
lenmem = uintptr(old.len) * sys.PtrSize
newlenmem = uintptr(cap) * sys.PtrSize
capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
newcap = int(capmem / sys.PtrSize)
case isPowerOfTwo(et.size):
var shift uintptr
if sys.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)
}
// The check of overflow in addition to capmem > maxAlloc is needed
// to prevent an overflow which can be used to trigger a segfault
// on 32bit architectures with this example program:
//
// type T [1<<27 + 1]int64
//
// var d T
// var s []T
//
// func main() {
// s = append(s, d, d, d, d)
// print(len(s), "\n")
// }
if overflow || capmem > maxAlloc {
panic(errorString("growslice: cap out of range"))
}
var p unsafe.Pointer
if et.ptrdata == 0 {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
// Only clear the part that will not be overwritten.
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in old.array since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
}
}
memmove(p, old.array, lenmem)
return slice{p, old.len, newcap}
}
- append添加数据， 超过切片的容量，切片地址可能会改变
func TestSliceTest4(t *testing.T) {
s := make([]int, 0, 10)
for i := 0; i < 11; i++ {
s = append(s, i)
fmt.Printf("slice append, len: %d, cap: %d, value: %+v, address: %p.\n", len(s), cap(s), s, s)
}
fmt.Printf("slice append, len: %d, cap: %d, value: %+v, address: %p.\n", len(s), cap(s), s, s)
}
// slice append, len: 1, cap: 10, value: [0], address: 0xc0000f6000.
// slice append, len: 2, cap: 10, value: [0 1], address: 0xc0000f6000.
// slice append, len: 3, cap: 10, value: [0 1 2], address: 0xc0000f6000.
// slice append, len: 4, cap: 10, value: [0 1 2 3], address: 0xc0000f6000.
// slice append, len: 5, cap: 10, value: [0 1 2 3 4], address: 0xc0000f6000.
// slice append, len: 6, cap: 10, value: [0 1 2 3 4 5], address: 0xc0000f6000.
// slice append, len: 7, cap: 10, value: [0 1 2 3 4 5 6], address: 0xc0000f6000.
// slice append, len: 8, cap: 10, value: [0 1 2 3 4 5 6 7], address: 0xc0000f6000.
// slice append, len: 9, cap: 10, value: [0 1 2 3 4 5 6 7 8], address: 0xc0000f6000.
// slice append, len: 10, cap: 10, value: [0 1 2 3 4 5 6 7 8 9], address: 0xc0000f6000.
// slice append, len: 11, cap: 20, value: [0 1 2 3 4 5 6 7 8 9 10], address: 0xc0000fe000.
// slice append, len: 11, cap: 20, value: [0 1 2 3 4 5 6 7 8 9 10], address: 0xc0000fe000.
cap成倍增长，切片地址会改变： slice append, len: 10, cap: 10, value: [0 1 2 3 4 5 6 7 8 9], address: 0xc0000f6000. slice append, len: 11, cap: 20, value: [0 1 2 3 4 5 6 7 8 9 10], address: 0xc0000fe000.
切片切割
切片切割之后的len和cap
func TestSlice(t *testing.T) {
s := []int{0,1,2,3,4,5,6}
s1 := s[2:4]
fmt.Printf("slice slice, len: %d, cap: %d, value: %+v, address: %p.\n", len(s1), cap(s1), s1, s1)
// slice slice, len: 2, cap: 5, value: [2 3], address: 0xc0000fa010.
s2 := s[2:5]
fmt.Printf("slice slice, len: %d, cap: %d, value: %+v, address: %p.\n", len(s2), cap(s2), s2, s2)
// slice slice, len: 3, cap: 5, value: [2 3 4], address: 0xc0000fa010.
ss1 := s1[0:5]
fmt.Printf("slice slice, len: %d, cap: %d, value: %+v, address: %p.\n", len(ss1), cap(ss1), ss1, ss1)
// slice slice, len: 5, cap: 5, value: [2 3 4 5 6], address: 0xc0000fa010.
// ss2 := s1[0:6]
// fmt.Printf("slice init, len: %d, cap: %d, value: %+v, address: %p.\n", len(ss2), cap(ss2), ss2, ss2)
// panic
}
切片切割之后append，是否会改变原切片
func TestSlice(t *testing.T) {
s := []int{0,1,2,3,4,5,6}
fmt.Printf("slice s, len: %d, cap: %d, value: %+v, address: %p.\n", len(s), cap(s), s, s)
s1 := s[2:4]
fmt.Printf("slice s1, len: %d, cap: %d, value: %+v, address: %p.\n", len(s1), cap(s1), s1, s1)
s2 := s[2:5]
fmt.Printf("slice s2, len: %d, cap: %d, value: %+v, address: %p.\n", len(s2), cap(s2), s2, s2)
ss1 := s1[0:5]
fmt.Printf("slice ss1, len: %d, cap: %d, value: %+v, address: %p.\n", len(ss1), cap(ss1), ss1, ss1)
ss1 = append(ss1, 100)
fmt.Printf("slice ss1, len: %d, cap: %d, value: %+v, address: %p.\n", len(ss1), cap(ss1), ss1, ss1)
fmt.Printf("slice s, len: %d, cap: %d, value: %+v, address: %p.\n", len(s), cap(s), s, s)
s2 = append(s2, 101)
fmt.Printf("slice s2, len: %d, cap: %d, value: %+v, address: %p.\n", len(s2), cap(s2), s2, s2)
s2 = append(s2, 100)
fmt.Printf("slice s2, len: %d, cap: %d, value: %+v, address: %p.\n", len(s2), cap(s2), s2, s2)
s2 = append(s2, 100)
fmt.Printf("slice s2, len: %d, cap: %d, value: %+v, address: %p.\n", len(s2), cap(s2), s2, s2)
s2 = append(s2, 100)
fmt.Printf("slice s2, len: %d, cap: %d, value: %+v, address: %p.\n", len(s2), cap(s2), s2, s2)
fmt.Printf("slice s, len: %d, cap: %d, value: %+v, address: %p.\n", len(s), cap(s), s, s)
// slice s, len: 7, cap: 7, value: [0 1 2 3 4 5 6], address: 0xc000106000.
// slice s1, len: 2, cap: 5, value: [2 3], address: 0xc000106010.
// slice s2, len: 3, cap: 5, value: [2 3 4], address: 0xc000106010.
// slice ss1, len: 5, cap: 5, value: [2 3 4 5 6], address: 0xc000106010.
// slice ss1, len: 6, cap: 10, value: [2 3 4 5 6 100], address: 0xc00010c000.
// slice s, len: 7, cap: 7, value: [0 1 2 3 4 5 6], address: 0xc000106000.
// slice s2, len: 4, cap: 5, value: [2 3 4 101], address: 0xc000106010.
// slice s2, len: 5, cap: 5, value: [2 3 4 101 100], address: 0xc000106010.
// slice s2, len: 6, cap: 10, value: [2 3 4 101 100 100], address: 0xc00010c050.
// slice s2, len: 7, cap: 10, value: [2 3 4 101 100 100 100], address: 0xc00010c050.
// slice s, len: 7, cap: 7, value: [0 1 2 3 4 101 100], address: 0xc000106000.
}
go版本
go version go1.13.6 darwin/amd64