# 2.6 实战: 封装qsort

qsort快速排序函数是C语言的高阶函数，支持用于自定义排序比较函数，可以对任意类型的数组进行排序。本节我们尝试基于C语言的qsort函数封装一个Go语言版本的qsort函数。

## 2.6.1 认识qsort函数

qsort快速排序函数有`<stdlib.h>`标准库提供，函数的声明如下：

``````void qsort(
void* base, size_t num, size_t size,
int (*cmp)(const void*, const void*)
);``````

``````#include <stdio.h>
#include <stdlib.h>

#define DIM(x) (sizeof(x)/sizeof((x)[0]))

static int cmp(const void* a, const void* b) {
const int* pa = (int*)a;
const int* pb = (int*)b;
return *pa - *pb;
}

int main() {
int values[] = { 42, 8, 109, 97, 23, 25 };
int i;

qsort(values, DIM(values), sizeof(values[0]), cmp);

for(i = 0; i < DIM(values); i++) {
printf ("%d ",values[i]);
}
return 0;
}``````

cmp是用于排序时比较两个元素大小的回调函数。为了避免对全局名字空间的污染，我们将cmp回调函数定义为仅当前文件内可访问的静态函数。

## 2.6.2 将qsort函数从Go包导出

``````package qsort

//typedef int (*qsort_cmp_func_t)(const void* a, const void* b);
import "C"
import "unsafe"

func Sort(
base unsafe.Pointer, num, size C.size_t,
cmp C.qsort_cmp_func_t,
) {
C.qsort(base, num, size, cmp)
}``````

``````func Sort(
base unsafe.Pointer, num, size _Ctype_size_t,
cmp _Ctype_qsort_cmp_func_t,
)``````

``````/*
#include <stdlib.h>

typedef int (*qsort_cmp_func_t)(const void* a, const void* b);
*/
import "C"
import "unsafe"

type CompareFunc C.qsort_cmp_func_t

func Sort(base unsafe.Pointer, num, size int, cmp CompareFunc) {
C.qsort(base, C.size_t(num), C.size_t(size), C.qsort_cmp_func_t(cmp))
}``````

``````package main

//extern int go_qsort_compare(void* a, void* b);
import "C"

import (
"fmt"
"unsafe"

qsort "."
)

//export go_qsort_compare
func go_qsort_compare(a, b unsafe.Pointer) C.int {
pa, pb := (*C.int)(a), (*C.int)(b)
return C.int(*pa - *pb)
}

func main() {
values := []int32{42, 9, 101, 95, 27, 25}

qsort.Sort(unsafe.Pointer(&values[0]),
len(values), int(unsafe.Sizeof(values[0])),
qsort.CompareFunc(C.go_qsort_compare),
)
fmt.Println(values)
}``````

## 2.6.3 改进：闭包函数作为比较函数

``func Slice(slice interface{}, less func(i, j int) bool)``

``````import "sort"

func main() {
values := []int32{42, 9, 101, 95, 27, 25}

sort.Slice(values, func(i, j int) bool {
return values[i] < values[j]
})

fmt.Println(values)
}``````

``````package qsort

func Sort(base unsafe.Pointer, num, size int, cmp func(a, b unsafe.Pointer) int)``````

``````var go_qsort_compare_info struct {
fn func(a, b unsafe.Pointer) int
sync.Mutex
}

//export _cgo_qsort_compare
func _cgo_qsort_compare(a, b unsafe.Pointer) C.int {
return C.int(go_qsort_compare_info.fn(a, b))
}``````

``````/*
#include <stdlib.h>

typedef int (*qsort_cmp_func_t)(const void* a, const void* b);
extern int _cgo_qsort_compare(void* a, void* b);
*/
import "C"

func Sort(base unsafe.Pointer, num, size int, cmp func(a, b unsafe.Pointer) int) {
go_qsort_compare_info.Lock()
defer go_qsort_compare_info.Unlock()

go_qsort_compare_info.fn = cmp

C.qsort(base, C.size_t(num), C.size_t(size),
C.qsort_cmp_func_t(C._cgo_qsort_compare),
)
}``````

``````func main() {
values := []int32{42, 9, 101, 95, 27, 25}

qsort.Sort(unsafe.Pointer(&values[0]), len(values), int(unsafe.Sizeof(values[0])),
func(a, b unsafe.Pointer) int {
pa, pb := (*int32)(a), (*int32)(b)
return int(*pa - *pb)
},
)

fmt.Println(values)
}``````

## 2.6.4 改进：消除用户对unsafe包的依赖

``````package qsort

func Slice(slice interface{}, less func(a, b int) bool)``````

``````var go_qsort_compare_info struct {
base     unsafe.Pointer
elemnum  int
elemsize int
less     func(a, b int) bool
sync.Mutex
}``````

``````//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
}
}``````

``````
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),
)
}``````

``````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)
}``````