Return to Question

/* 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-1);
  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);
      }
    }
  }
}

/* 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 *))
{
  int32_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-1);
  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);
      }
    }
  }
}

I'd be especially interested in any comment about speed. Currently this is just a little slower than gcc's qsort() (e.g. 1.6ms vs 1.2ms to sort an array of 1 million random integers).

I'd be especially interested in any comment about speed. Currently this is just a little slower than gcc's qsort() (e.g. 1.6ms vs 1.2ms to sort an array of 10 million random integers).

/* 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);
      }
    }
  }
}

/* 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-1);
  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);
      }
    }
  }
}