sort.go

package sort

import (
	"fmt"
	"reflect"
	"sort"
	"sync"
	"unsafe"
)

// Sort sorts the slice using less as the comparison
// function. slice must be a slice type, and less must
// be a function which takes two arguments - both poiners
// to slice's element type - and returns a bool.
// Effectively, the type signature is:
//  Sort(slice []T, less func(*T, *T) bool)
func Sort(slice, less interface{}) {
	styp, ltyp := reflect.TypeOf(slice), reflect.TypeOf(less)
	sk := sorterKey{styp, ltyp}
	sorters.RLock()
	sorter, ok := sorters.m[sk]
	sorters.RUnlock()
	if !ok {
		sorter = makeSorter(styp, ltyp)
		sorters.Lock()
		sorters.m[sk] = sorter
		sorters.Unlock()
	}

	s := makeSortable(sorter, slice, less)
	sort.Sort(&s)
}

var boolTyp = reflect.TypeOf(false)

func makeSorter(styp, ltyp reflect.Type) sorter {
	if styp.Kind() != reflect.Slice || ltyp.Kind() != reflect.Func ||
		ltyp.NumIn() != 2 || ltyp.NumOut() != 1 || ltyp.In(0) !=
		reflect.PtrTo(styp.Elem()) || ltyp.In(1) != reflect.PtrTo(styp.Elem()) ||
		ltyp.Out(0) != boolTyp {
		panic(fmt.Errorf("sort: Sort called like Sort(%v, %v); must be of the form Sort([]T, func(*T, *T) bool)", styp, ltyp))
	}

	return sorter{
		size: int(styp.Elem().Size()),
		elem: styp.Elem(),
		less: ltyp,
	}
}

// like reflect.SliceHeader, but the data
// field has type unsafe.Pointer so that
// the GC is aware of it
type sliceHeader struct {
	data unsafe.Pointer
	len  int
	cap  int
}

func makeSortable(s sorter, slice, less interface{}) sortable {
	var hdr sliceHeader
	slc := reflect.ValueOf(slice)
	hdr.len = slc.Len() * s.size
	hdr.cap = hdr.len
	hdr.data = unsafe.Pointer(slc.Index(0).UnsafeAddr())

	buf := *(*[]byte)(unsafe.Pointer(&hdr))

	lss := reflect.New(s.less).Elem()
	lss.Set(reflect.ValueOf(less))
	lessfn := *(*func(a, b unsafe.Pointer) bool)(unsafe.Pointer(lss.UnsafeAddr()))

	return sortable{
		len:  slc.Len(),
		size: s.size,
		buf:  buf,
		tmp:  make([]byte, s.size),
		less: lessfn,
	}
}

var sorters = struct {
	m map[sorterKey]sorter
	sync.RWMutex
}{m: make(map[sorterKey]sorter)}

// we use both the slice and reflect types
// as keys (technically unnecessary) so that
// we can avoid explicitly verifying the
// type soundness of the less function each
// time; this way, if the sorterKey is found
// in the map, all of the types have already
// been verified
type sorterKey struct {
	slice reflect.Type
	less  reflect.Type
}

type sorter struct {
	size int
	elem reflect.Type
	less reflect.Type
}

type sortable struct {
	len  int
	size int
	buf  []byte
	tmp  []byte
	less func(i, j unsafe.Pointer) bool
}

func (s *sortable) Len() int { return s.len }

func (s *sortable) Less(i, j int) bool {
	iidx, jidx := i*s.size, j*s.size
	iptr := unsafe.Pointer(&s.buf[iidx])
	jptr := unsafe.Pointer(&s.buf[jidx])
	return s.less(iptr, jptr)
}

func (s *sortable) Swap(i, j int) {
	iidx, jidx := i*s.size, j*s.size
	copy(s.tmp, s.buf[iidx:iidx+s.size])
	copy(s.buf[iidx:iidx+s.size], s.buf[jidx:jidx+s.size])
	copy(s.buf[jidx:jidx+s.size], s.tmp)
}