Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/* Quick and dirty PRNG (xorshift) */
static uint32_t utl_rnd()
{
static uint32_t rnd = 0;
while (rnd == 0) rnd = (uint32_t)time(0);
rnd ^= rnd << 13;
rnd ^= rnd >> 17;
rnd ^= rnd << 5;
return rnd;
}
#define utl_dpqswap(a,b) do { if (a!=b) { \
uint32_t sz = esz;\
uint8_t tmp8; \
uint32_t tmp32; \
uint8_t *pa = ((uint8_t *)a); \
uint8_t *pb = ((uint8_t *)b); \
while (sz >= 4) { \
tmp32 = *(uint32_t *)pa; \
*(uint32_t *)pa = *(uint32_t *)pb;\
*(uint32_t *)pb = tmp32;\
sz-=4; pa+=4; pb+=4;\
}\
switch (sz) {\
case 3: tmp8=*pa; *pa=*pb; *pb=tmp8; pa--; pb--;\
case 2: tmp8=*pa; *pa=*pb; *pb=tmp8; pa--; pb--;\
case 1: tmp8=*pa; *pa=*pb; *pb=tmp8; pa--; pb--;\
}\
}\
} while (0)
#define utl_dpqptr(k) ((uint8_t *)base+(k)*esz)
#define utl_dpqpush(l,r) do {stack[stack_top][0]=(l); stack[stack_top][1]=(r); stack_top++; } while(0)
#define utl_dpqpop(l,r) do {stack_top--; l=stack[stack_top][0]; r=stack[stack_top][1];} while(0)
/* Dropin replacement for qsort() using double pivot quicksort */
void utl_dpqsort(void *base, uint32_t nel, uint32_t esz, int (*cmp)(const void *, const void *))
{
uint32_t left,right;
uint8_t *leftptr, *rightptr;
uint32_t L,K,G;
int32_t stack[128][2]; // Enough for 2^31 max elements in the array
int16_t stack_top = 0;
utl_dpqpush(0,nel);
while (stack_top > 0) {
utl_dpqpop(left, right);
if (left < right) {
if ((right - left) <= 16) { // Use insertion sort
for (int32_t i = left+1; i<=right; i++) {
rightptr = utl_dpqptr(i);
leftptr = rightptr - esz;
for (int32_t j=i; j>0 && cmp(leftptr, rightptr) > 0; j--) {
utl_dpqswap(rightptr, leftptr);
rightptr = leftptr;
leftptr = rightptr - esz;
}
}
}
else {
leftptr = utl_dpqptr(left);
rightptr = utl_dpqptr(right);
/* Randomize pivot to avoid worst case (already sorted array) */
L = left + (utl_rnd() % (right-left));
G = left + (utl_rnd() % (right-left));
utl_dpqswap(utl_dpqptr(L),leftptr);
utl_dpqswap(utl_dpqptr(G),rightptr);
if (cmp(leftptr, rightptr) > 0) {
utl_dpqswap(leftptr, rightptr);
}
L=left+1; K=L; G=right-1;
while (K <= G) {
if (cmp(utl_dpqptr(K), leftptr) < 0) {
utl_dpqswap(utl_dpqptr(K), utl_dpqptr(L));
L++;
}
else if (cmp(utl_dpqptr(K), rightptr) > 0) {
while ((cmp(utl_dpqptr(G), rightptr) > 0) && (K<G))
G--;
utl_dpqswap(utl_dpqptr(K), utl_dpqptr(G));
G--;
if (cmp(utl_dpqptr(K), leftptr) < 0) {
utl_dpqswap(utl_dpqptr(K), utl_dpqptr(L));
L++;
}
}
K++;
}
L--; G++;
utl_dpqswap(leftptr, utl_dpqptr(L));
utl_dpqswap(rightptr, utl_dpqptr(G));
utl_dpqpush(G+1, right);
utl_dpqpush(L+1, G-1);
utl_dpqpush(left, L-1);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.