go 數(shù)組切片的底層實現(xiàn)
go的切片也就是所謂的可變數(shù)組，當創(chuàng)建的時候，會發(fā)現(xiàn)大小只為24，原因就是他本質(zhì)是一個結(jié)構(gòu)體，存放著3個字段
type arr struct {
Data unsafe.Pointer
Len int
Cap int
}
從上面可以看出來，分別存放指針，長度，以及大小，可這些究竟是干什么用的呢？
- data：存放的是數(shù)組第一個元素的指針
- len：該數(shù)組的長度
- cap：該數(shù)組內(nèi)存大小
要想實現(xiàn)切片，除了這些，還需要了解的是，數(shù)組內(nèi)存是一段連續(xù)的內(nèi)存空間，并且go是不允許直接在內(nèi)存地址上進行計算偏移后取值的，于是我們需要引用C的3個函數(shù)
好了，廢話不多說了，上代碼。
package data
/*
#include <stdlib.h>
*/
import "C"
import (
"fmt"
"unsafe"
)
type arr struct {
Data unsafe.Pointer
Len int
Cap int
}
// 設(shè)置每個元素的內(nèi)存地址大小
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
}
//開辟內(nèi)存
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)
}
// 擴容內(nèi)存
func (a *arr) Dilatation() {
a.Data = C.realloc(a.Data, C.size_t(a.Cap)*2*Tag)
a.Cap *= 2
}
// 獲取對應(yīng)下標的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
}
// 查詢對應(yīng)值的下標
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++ {
//重新分配內(nè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
// 獲取添加前數(shù)組元素最后位置的指針地址
p2 := uintptr(a.Data)
p2 += uintptr(a.Len-1) * Tag
// 挪動已有在index的數(shù)據(jù)到尾巴處
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)
}
// 刪除數(shù)組
func (a *arr) Delect(index int) {
a.DelectLen(index, 1)
}
// 刪除全部數(shù)組
func (a *arr) DelectAll() {
a.Len = 0
}
// 刪除固定范圍數(shù)組
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()
}
