typedef struct stackitem_S
{
   uint32_t index;
   struct stackitem_S* next;
} stackitem_T;

#define PUSH(i) \
{ \
   if (stack_items == '\0') \
   { \
      if ( (stack_new = (stackitem_T*)malloc(sizeof(stackitem_T))) == '\0') \
      { \
         while (stack_items != '\0') \
         { \
            stack_next = stack_items->next; \
            free(stack_items); \
            stack_items = stack_next; \
         } \
 \
         return -1; \
      } \
   } \
   else \
   { \
      stack_new = stack_items; \
      stack_items = stack_items->next; \
   } \
 \
   stack_new->index = i; \
   stack_new->next = stack; \
   stack = stack_new; \
}

#define POP(i) \
{ \
   stack_item = stack; \
   *(i) = stack_item->index; \
   stack = stack->next; \
   stack_item->next = stack_items; \
   stack_items = stack_item; \
}

/* Non-recursing imlementation of quicksort. Subfiles are stored
 * on a heap-based stack, so instead of running out of stack space it
 * is possible to run out of memory for some inputs.
 *
 * items is a pointer to an array on user-defined objects
 * count is the number of items
 * lt is a pointer to a function that returns 1 (true) if items[i1]
 *    is less then items[i2], 0 (false) otherwise.
 * swap is a pointer to a function that swaps the values items[l] and items[r].
 * 
 * The function returns 0 on success, -1 if there was a memory
 * allocation failure.
 */
int
qsort(void* items, uint32_t count,
      int (*lt)(void* items, uint32_t i1, uint32_t i2),
      void (*swap)(void* items, uint32_t l, uint32_t r))
{
   stackitem_T* stack_items = '\0';
   stackitem_T* stack = '\0';
   stackitem_T* stack_next;
   stackitem_T* stack_new;
   stackitem_T* stack_item;
   uint32_t l;
   uint32_t r;
   uint32_t i;
   uint32_t j;
   uint32_t lps; /* left partition size */
   uint32_t rps; /* right partition size */

   if (count <= 1)
      return 0;

   PUSH(count - 1);
   PUSH(0);

   while (stack != '\0')
   {
      POP(&l);
      POP(&r);

      for (;;)
      {
         /* Begin partition step. */
         /* Median of three partitioning. */
         if ((r - l + 1) >= 4)
         {
            swap(items, (l + r) >> 1, r - 1);
            if (lt(items, r - 1, l))
               swap(items, l, r - 1);
            if (lt(items, r, l))
               swap(items, l, r);
            if (lt(items, r, r - 1))
               swap(items, r - 1, r);
            i = l + 1;
            j = r;
         }
         else
         {
            i = l;
            j = r;
         }

         /* Main partition loop. */
         for (;;)
         {
            while (lt(items, i, r))
               ++i;
            while (lt(items, r, --j))
            {
               if (j == l)
                  break;
            }

            if (i >= j)
               break;

            swap(items, i, j);
         }

         swap(items, i, r);
         /* End partition step. */

         lps = i - l;
         rps = r - i;

         if (lps > rps)
         {
            if (lps > 1)
            {
               if (rps > 1)
               {
                  /* push left partition */
                  PUSH(i - 1);
                  PUSH(l);
                  /* set right partition manually */
                  l = i + 1;
                  /* r is already set */
               }
               else
               {
                  /* set left partition manually */
                  /* l is already set */
                  r = i - 1;
               }
            }
            else
               break;
         }
         else
         {
            if (rps > 1)
            {
               if (lps > 1)
               {
                  /* push right partition */
                  PUSH(r);
                  PUSH(i + 1);
                  /* set left partition manually */
                  r = i - 1;
                  /* l is already set */
               }
               else
               {
                  /* set right partition manually */
                  /* r is already set */
                  l = i + 1;
               }
            }
            else
               break;
         }
      }
   }

   /* Free the heap based stack items. */
   while (stack_items != '\0')
   {
      stack_next = stack_items->next;
      free(stack_items);
      stack_items = stack_next;
   }

   return 0;
}

/*
static int
lt(void* items, uint32_t i1, uint32_t i2)
{
   uint32_t* numbers = (uint32_t*)items;

   if (numbers[i1] < numbers[i2])
      return 1;
   else
      return 0;
}

static void
swap(void* items, uint32_t l, uint32_t r)
{
   uint32_t* numbers = (uint32_t*)items;
   uint32_t temp = numbers[l];

   numbers[l] = numbers[r];
   numbers[r] = temp;
}
*/