dymokomi/luce-js
Source of release 0.6.0
0.6.0 / src / cutils / rqsort.lucb
#==============================================================================================
#
# rqsort - A reentrant quicksort over untyped elements with a comparator and an opaque
#
# DESCRIPTION:
# Port of QuickJS cutils.c lines 340-641: the width-specialised exchange functions,
# heapsortx (the worst-case fallback), med3 and rqsort itself.
#
#==============================================================================================
## A comparator for `rqsort`: `(a, b, opaque)`, negative, zero or positive.
pub type CmpF = func(const void*, const void*, void*?) -> i32
type ExchangeF = func(void*, void*, usize) -> unit
# mark: Exchange functions ======================================================================
func exchange_bytes(a: void*, b: void*, size: usize):
var ap = (u8*)a
var bp = (u8*)b
var n = size
while n != 0:
n -= 1
let t = *ap
*ap = *bp
*bp = t
ap += 1
bp += 1
func exchange_one_byte(a: void*, b: void*, size: usize):
let ap = (u8*)a
let bp = (u8*)b
let t = *ap
*ap = *bp
*bp = t
func exchange_int16s(a: void*, b: void*, size: usize):
var ap = (u16*)a
var bp = (u16*)b
var n = size // memory.size_of(u16)
while n != 0:
n -= 1
let t = *ap
*ap = *bp
*bp = t
ap += 1
bp += 1
func exchange_one_int16(a: void*, b: void*, size: usize):
let ap = (u16*)a
let bp = (u16*)b
let t = *ap
*ap = *bp
*bp = t
func exchange_int32s(a: void*, b: void*, size: usize):
var ap = (u32*)a
var bp = (u32*)b
var n = size // memory.size_of(u32)
while n != 0:
n -= 1
let t = *ap
*ap = *bp
*bp = t
ap += 1
bp += 1
func exchange_one_int32(a: void*, b: void*, size: usize):
let ap = (u32*)a
let bp = (u32*)b
let t = *ap
*ap = *bp
*bp = t
func exchange_int64s(a: void*, b: void*, size: usize):
var ap = (u64*)a
var bp = (u64*)b
var n = size // memory.size_of(u64)
while n != 0:
n -= 1
let t = *ap
*ap = *bp
*bp = t
ap += 1
bp += 1
func exchange_one_int64(a: void*, b: void*, size: usize):
let ap = (u64*)a
let bp = (u64*)b
let t = *ap
*ap = *bp
*bp = t
func exchange_int128s(a: void*, b: void*, size: usize):
var ap = (u64*)a
var bp = (u64*)b
var n = size // (memory.size_of(u64) * 2)
while n != 0:
n -= 1
let t = ap[0]
let u = ap[1]
ap[0] = bp[0]
ap[1] = bp[1]
bp[0] = t
bp[1] = u
ap += 2
bp += 2
func exchange_one_int128(a: void*, b: void*, size: usize):
let ap = (u64*)a
let bp = (u64*)b
let t = ap[0]
let u = ap[1]
ap[0] = bp[0]
ap[1] = bp[1]
bp[0] = t
bp[1] = u
func exchange_func(base: const void*, size: usize) -> ExchangeF:
match ((usize)base | size) & 15:
0:
if size == memory.size_of(u64) * 2:
return exchange_one_int128
else:
return exchange_int128s
8:
if size == memory.size_of(u64):
return exchange_one_int64
else:
return exchange_int64s
4, 12:
if size == memory.size_of(u32):
return exchange_one_int32
else:
return exchange_int32s
2, 6, 10, 14:
if size == memory.size_of(u16):
return exchange_one_int16
else:
return exchange_int16s
_:
if size == 1:
return exchange_one_byte
else:
return exchange_bytes
# mark: Heapsort ================================================================================
func heapsortx(base: void*, nmemb: usize, size: usize, cmp: CmpF, opaque: void*?):
let basep = (u8*)base
let swap = exchange_func(base, size)
if nmemb > 1:
var i = (nmemb // 2) * size
let n = nmemb * size
while i > 0:
i -= size
var r = i
while true:
var c = r * 2 + size
if c >= n:
break
if c < n - size and cmp(basep + c, basep + c + size, opaque) <= 0:
c += size
if cmp(basep + r, basep + c, opaque) > 0:
break
swap(basep + r, basep + c, size)
r = c
i = n - size
while i > 0:
swap(basep, basep + i, size)
var r: usize = 0
while true:
var c = r * 2 + size
if c >= i:
break
if c < i - size and cmp(basep + c, basep + c + size, opaque) <= 0:
c += size
if cmp(basep + r, basep + c, opaque) > 0:
break
swap(basep + r, basep + c, size)
r = c
i -= size
func med3(a: u8*, b: u8*, c: u8*, cmp: CmpF, opaque: void*?) -> u8*:
if cmp(a, b, opaque) < 0:
return b if cmp(b, c, opaque) < 0 else (c if cmp(a, c, opaque) < 0 else a)
return b if cmp(b, c, opaque) > 0 else (a if cmp(a, c, opaque) < 0 else c)
# mark: rqsort ==================================================================================
struct RqsortSegment:
var base: u8*?
var count: usize
var depth: i32
## Sort `nmemb` elements of `size` bytes at `base` with `cmp(a, b, opaque)`. Not stable.
## (pointer based version with local stack and insertion sort threshhold)
pub func rqsort(base: void*, nmemb: usize, size: usize, cmp: CmpF, opaque: void*?):
var stack: RqsortSegment[50]
var sp: usize = 0
let swap = exchange_func(base, size)
let swap_block = exchange_func(base, size | 128)
if nmemb < 2 or size <= 0:
return
stack[sp] = RqsortSegment(base = (u8*)base, count = nmemb, depth = 0)
sp += 1
while sp > 0:
sp -= 1
var ptr = stack[sp].base else trap("rqsort: empty segment")
var n = stack[sp].count
var depth = stack[sp].depth
while n > 6:
depth += 1
if depth > 50:
# depth check to ensure worst case logarithmic time
heapsortx(ptr, n, size, cmp, opaque)
n = 0
break
# select median of 3 from 1/4, 1/2, 3/4 positions
# should use median of 5 or 9?
let m4 = (n >> 2) * size
let m = med3(ptr + m4, ptr + 2 * m4, ptr + 3 * m4, cmp, opaque)
swap(ptr, m, size) # move the pivot to the start or the array
var i: usize = 1
var lt: usize = 1
var pi = ptr + size
var plt = pi
var gt = n
let top = ptr + n * size
var pj = top
var pgt = top
while true:
while pi < pj:
let c = cmp(ptr, pi, opaque)
if c < 0:
break
if c == 0:
swap(plt, pi, size)
lt += 1
plt += size
i += 1
pi += size
while true:
pj -= size
if pi >= pj:
break
let c = cmp(ptr, pj, opaque)
if c > 0:
break
if c == 0:
gt -= 1
pgt -= size
swap(pgt, pj, size)
if pi >= pj:
break
swap(pi, pj, size)
i += 1
pi += size
# array has 4 parts:
# from 0 to lt excluded: elements identical to pivot
# from lt to pi excluded: elements smaller than pivot
# from pi to gt excluded: elements greater than pivot
# from gt to n excluded: elements identical to pivot
#
# move elements identical to pivot in the middle of the array:
# swap values in ranges [0..lt[ and [i-lt..i[
# swapping the smallest span between lt and i-lt is sufficient
var span = (usize)(plt - ptr)
var span2 = (usize)(pi - plt)
lt = i - lt
if span > span2:
span = span2
swap_block(ptr, pi - span, span)
# swap values in ranges [gt..top[ and [i..top-(top-gt)[
# swapping the smallest span between top-gt and gt-i is sufficient
span = (usize)(top - pgt)
span2 = (usize)(pgt - pi)
pgt = top - span2
gt = n - (gt - i)
if span > span2:
span = span2
swap_block(pi, top - span, span)
# now array has 3 parts:
# from 0 to lt excluded: elements smaller than pivot
# from lt to gt excluded: elements identical to pivot
# from gt to n excluded: elements greater than pivot
#
# stack the larger segment and keep processing the smaller one
# to minimize stack use for pathological distributions
if lt > n - gt:
stack[sp] = RqsortSegment(base = ptr, count = lt, depth = depth)
sp += 1
ptr = pgt
n -= gt
else:
stack[sp] = RqsortSegment(base = pgt, count = n - gt, depth = depth)
sp += 1
n = lt
# Use insertion sort for small fragments
var pi = ptr + size
let top = ptr + n * size
while pi < top:
var pj = pi
while pj > ptr and cmp(pj - size, pj, opaque) > 0:
swap(pj, pj - size, size)
pj -= size
pi += size