go 切片的底层实现

go 数组切片的底层实现

go的切片也就是所谓的可变数组，当创建的时候，会发现大小只为24，原因就是他本质是一个结构体，存放着3个字段

type arr struct {
   Data unsafe.Pointer
   Len  int
   Cap  int
}

从上面可以看出来，分别存放指针，长度，以及大小，可这些究竟是干什么用的呢？

• data：存放的是数组第一个元素的指针
• len：该数组的长度
• cap：该数组内存大小

要想实现切片，除了这些，还需要了解的是，数组内存是一段连续的内存空间，并且go是不允许直接在内存地址上进行计算偏移后取值的，于是我们需要引用C的3个函数

好了，废话不多说了，上代码。

package data

/*
#include <stdlib.h>
*/
import "C"
import (
   "fmt"
   "unsafe"
)

type arr struct {
   Data unsafe.Pointer
   Len  int
   Cap  int
}
// 设置每个元素的内存地址大小
const Tag = 8
// 初始化
func (a *arr) New(l, c int, data ...int) {
   if a == nil {
      return
   }
   if data == nil {
      return
   }
   if l < 0 || c < 0 || l > c || len(data) > l {
      return
   }
  //开辟内存
   a.Data = C.malloc(C.size_t(c) * Tag)
   a.Len = l
   a.Cap = c

   p := uintptr(a.Data)

   for i, v := range data {
      *(*int)(unsafe.Pointer(p + uintptr(i*Tag))) = v
   }
}
// 打印
func (a *arr) Printf() {

   if a == nil || a.Data == nil {
      return
   }
   p := uintptr(a.Data)
   for i := 0; i < a.Len; i++ {
      fmt.Printf("%d  ", *(*int)(unsafe.Pointer(p + uintptr(i*Tag))))
   }
   fmt.Println()
}
// 添加
func (a *arr) Add(data ...int) {
   if a == nil || a.Data == nil {
      return
   }
   for a.Cap < a.Len+len(data) {
      a.Dilatation()
   }
   p := uintptr(a.Data)
   p += Tag * uintptr(a.Len)
   for i, v := range data {
      *(*int)(unsafe.Pointer(p + uintptr(i*Tag))) = v
   }
   a.Len += len(data)
}
// 扩容内存
func (a *arr) Dilatation() {
   a.Data = C.realloc(a.Data, C.size_t(a.Cap)*2*Tag)
   a.Cap *= 2
}
// 获取对应下标的int指针
func (a *arr)referIntPrt(i int)*int  {
   err := -1
   if a.Data == nil || a == nil {
      return &err
   }
   if i < 0 || i >= a.Len {
      return &err
   }
   p := uintptr(a.Data)
   p += uintptr(i) * Tag
   return (*int)(unsafe.Pointer(p))
}
// 查询
func (a *arr) ReferIndex(i int) int {
   return *a.referIntPrt(i)
}
// 修改
func (a *arr)Alter(index ,value int){
   *a.referIntPrt(index) = value
}
// 查询对应值的下标
func (a *arr) ReferValue(value int) int {
   if a.Data == nil || a == nil {
      return -1
   }
   p := uintptr(a.Data)

   for i := 0; i < a.Len; i++ {
     //重新分配内存
      v := *(*int)(unsafe.Pointer(p + uintptr(i)*Tag))
      if v == value {
         return i
      }
   }
   return -1
}
//指定位置之后添加  or 插入
func (a *arr) AddIndex(index int, data ...int) {
   if a.Data == nil || a == nil {
      return
   }
   if index < 0 {
      return
   }
   if index >= a.Len-1 {
      for _, v := range data {
         a.Add(v)
      }
      return
   }
   for a.Len+len(data) > a.Cap {
      a.Dilatation()
   }
   // 获取本次添加后最后元素的指针地址
   p := uintptr(a.Data)
   p += uintptr(a.Len+len(data)-1) * Tag
   // 获取添加前数组元素最后位置的指针地址
   p2 := uintptr(a.Data)
   p2 += uintptr(a.Len-1) * Tag
   // 挪动已有在index的数据到尾巴处
   for i := index; i < a.Len+len(data); i++ {
      *(*int)(unsafe.Pointer(p - uintptr(i-index)*Tag)) = *(*int)(unsafe.Pointer(p2 - uintptr(i-index)*Tag))
   }
   //获取需要复写元素的指针地址
   p3 := uintptr(a.Data)
   p3 += uintptr(index) * Tag
   // 开始复写,安放新添加的元素
   for i, v := range data {
      *(*int)(unsafe.Pointer(p3 + uintptr(i)*Tag)) = v
   }
   a.Len += len(data)

}
// 删除数组
func (a *arr) Delect(index int) {
   a.DelectLen(index, 1)
}
// 删除全部数组
func (a *arr) DelectAll() {
   a.Len = 0
}
// 删除固定范围数组
func (a *arr) DelectLen(index, len int) {
   if a == nil || a.Data == nil {
      return
   }
   if index < 0 || len < 0 {
      return
   }
   // 获取删除起始位置元素的地址
   p := uintptr(a.Data)
   p += uintptr(index) * Tag
   // 获取删除范围后的元素地址
   p1 := p + uintptr(len)*Tag
   for i := 0; i < a.Len-len-index; i++ {
      *(*int)(unsafe.Pointer(p + uintptr(i)*Tag)) = *(*int)(unsafe.Pointer(p1 + uintptr(i)*Tag))
   }
   a.Len -= len

}
// 删除指定值
func (a *arr) DelectValue(value int) {
   for {
      i := a.ReferValue(value)
      if i == -1 {
         return
      }
      a.Delect(i)
   }
}

func NewArr() {
   arr := new(arr)
   arr.New(3, 3, 1, 2, 3)
   arr.Printf()
   arr.Add(9, 8, 7, 5, 4, 3, 88, 66, 11, 55, 001,1,2,3)
   arr.Printf()
   fmt.Println(arr.ReferIndex(5))
   fmt.Println(arr.ReferValue(7))
   arr.AddIndex(4, 12, 13, 14)
   arr.Printf()
   arr.DelectValue(1)
   arr.Printf()
   arr.DelectLen(3,4)
   arr.Printf()
   arr.Alter(1,100)
   arr.Printf()
}