2.6.4 改进:消除用户对unsafe包的依赖
前一个版本的qsort.Sort包装函数已经比最初的C语言版本的qsort易用很多,但是依然保留了很多C语言底层数据结构的细节。 现在我们将继续改进包装函数,尝试消除对unsafe包的依赖,并实现一个类似标准库中sort.Slice的排序函数。
新的包装函数声明如下:
package qsort
func Slice(slice interface{}, less func(a, b int) bool)
首先,我们将slice作为接口类型参数传入,这样可以适配不同的切片类型。 然后切片的首个元素的地址、元素个数和元素大小可以通过reflect反射包从切片中获取。
为了保存必要的排序上下文信息,我们需要在全局包变量增加要排序数组的地址、元素个数和元素大小等信息,比较函数改为less:
var go_qsort_compare_info struct {
base unsafe.Pointer
elemnum int
elemsize int
less func(a, b int) bool
sync.Mutex
}
同样比较函数需要根据元素指针、排序数组的开始地址和元素的大小计算出元素对应数组的索引下标, 然后根据less函数的比较结果返回qsort函数需要格式的比较结果。
//export _cgo_qsort_compare
func _cgo_qsort_compare(a, b unsafe.Pointer) C.int {
var (
// array memory is locked
base = uintptr(go_qsort_compare_info.base)
elemsize = uintptr(go_qsort_compare_info.elemsize)
)
i := int((uintptr(a) - base) / elemsize)
j := int((uintptr(b) - base) / elemsize)
switch {
case go_qsort_compare_info.less(i, j): // v[i] < v[j]
return -1
case go_qsort_compare_info.less(j, i): // v[i] > v[j]
return +1
default:
return 0
}
}
新的Slice函数的实现如下:
func Slice(slice interface{}, less func(a, b int) bool) {
sv := reflect.ValueOf(slice)
if sv.Kind() != reflect.Slice {
panic(fmt.Sprintf("qsort called with non-slice value of type %T", slice))
}
if sv.Len() == 0 {
return
}
go_qsort_compare_info.Lock()
defer go_qsort_compare_info.Unlock()
defer func() {
go_qsort_compare_info.base = nil
go_qsort_compare_info.elemnum = 0
go_qsort_compare_info.elemsize = 0
go_qsort_compare_info.less = nil
}()
// baseMem = unsafe.Pointer(sv.Index(0).Addr().Pointer())
// baseMem maybe moved, so must saved after call C.fn
go_qsort_compare_info.base = unsafe.Pointer(sv.Index(0).Addr().Pointer())
go_qsort_compare_info.elemnum = sv.Len()
go_qsort_compare_info.elemsize = int(sv.Type().Elem().Size())
go_qsort_compare_info.less = less
C.qsort(
go_qsort_compare_info.base,
C.size_t(go_qsort_compare_info.elemnum),
C.size_t(go_qsort_compare_info.elemsize),
C.qsort_cmp_func_t(C._cgo_qsort_compare),
)
}
首先需要判断传入的接口类型必须是切片类型。然后通过反射获取qsort函数需要的切片信息,并调用C语言的qsort函数。
基于新包装的函数我们可以采用和标准库相似的方式排序切片:
import (
"fmt"
qsort "."
)
func main() {
values := []int64{42, 9, 101, 95, 27, 25}
qsort.Slice(values, func(i, j int) bool {
return values[i] < values[j]
})
fmt.Println(values)
}
为了避免在排序过程中,排序数组的上下文信息go_qsort_compare_info
被修改,我们进行了全局加锁。 因此目前版本的qsort.Slice函数是无法并发执行的,读者可以自己尝试改进这个限制。
学员评价