//========= Copyright Valve Corporation, All rights reserved. ============//
/******************************************************************/

/* qsort.c  --  Non-Recursive ANSI Quicksort function             */

/*                                                                */

/* Public domain by Raymond Gardner, Englewood CO  February 1991  */

/*                                                                */

/* Usage:                                                         */

/*     qsort(base, nbr_elements, width_bytes, compare_function);  */

/*        void *base;                                             */

/*        size_t nbr_elements, width_bytes;                       */

/*        int (*compare_function)(const void *, const void *);    */

/*                                                                */

/* Sorts an array starting at base, of length nbr_elements, each  */

/* element of size width_bytes, ordered via compare_function,     */

/* which is called as  (*compare_function)(ptr_to_element1,       */

/* ptr_to_element2) and returns < 0 if element1 < element2,       */

/* 0 if element1 = element2, > 0 if element1 > element2.          */

/* Most refinements are due to R. Sedgewick. See "Implementing    */

/* Quicksort Programs", Comm. ACM, Oct. 1978, and Corrigendum,    */

/* Comm. ACM, June 1979.                                          */

/******************************************************************/



// modified to take (and use) a context object, ala Microsoft's qsort_s

// "extension" to the stdlib



#include <stddef.h>                     /* for size_t definition  */



/*

**  swap nbytes between a and b

*/



static void swap_bytes(char *a, char *b, size_t nbytes)

{

   char tmp;

   do {

      tmp = *a; *a++ = *b; *b++ = tmp;

   } while ( --nbytes );

}



#define  SWAP(a, b)  (swap_bytes((char *)(a), (char *)(b), size))



#define  COMP(ctx, a, b)  ((*comp)((void *)ctx, (void *)(a), (void *)(b)))



#define  T           7    /* subfiles of T or fewer elements will */

                          /* be sorted by a simple insertion sort */

                          /* Note!  T must be at least 3          */



extern "C" void qsort_s(void *basep, size_t nelems, size_t size,

           int (*comp)(void *, const void *, const void *),

	   void *ctx)

{

   char *stack[40], **sp;       /* stack and stack pointer        */

   char *i, *j, *limit;         /* scan and limit pointers        */

   size_t thresh;               /* size of T elements in bytes    */

   char *base;                  /* base pointer as char *         */



   base = (char *)basep;        /* set up char * base pointer     */

   thresh = T * size;           /* init threshold                 */

   sp = stack;                  /* init stack pointer             */

   limit = base + nelems * size;/* pointer past end of array      */

   for ( ;; ) {                 /* repeat until break...          */

      if ( limit - base > thresh ) {  /* if more than T elements  */

                                      /*   swap base with middle  */

         SWAP((((limit-base)/size)/2)*size+base, base);

         i = base + size;             /* i scans left to right    */

         j = limit - size;            /* j scans right to left    */

         if ( COMP(ctx, i, j) > 0 )   /* Sedgewick's              */

            SWAP(i, j);               /*    three-element sort    */

         if ( COMP(ctx, base, j) > 0 )/*        sets things up    */

            SWAP(base, j);            /*            so that       */

         if ( COMP(ctx, i, base) > 0 )/*      *i <= *base <= *j   */

            SWAP(i, base);            /* *base is pivot element   */

         for ( ;; ) {                 /* loop until break         */

            do                        /* move i right             */

               i += size;             /*        until *i >= pivot */

            while ( COMP(ctx, i, base) < 0 );

            do                        /* move j left              */

               j -= size;             /*        until *j <= pivot */

            while ( COMP(ctx, j, base) > 0 );

            if ( i > j )              /* if pointers crossed      */

               break;                 /*     break loop           */

            SWAP(i, j);       /* else swap elements, keep scanning*/

         }

         SWAP(base, j);         /* move pivot into correct place  */

         if ( j - base > limit - i ) {  /* if left subfile larger */

            sp[0] = base;             /* stack left subfile base  */

            sp[1] = j;                /*    and limit             */

            base = i;                 /* sort the right subfile   */

         } else {                     /* else right subfile larger*/

            sp[0] = i;                /* stack right subfile base */

            sp[1] = limit;            /*    and limit             */

            limit = j;                /* sort the left subfile    */

         }

         sp += 2;                     /* increment stack pointer  */

      } else {      /* else subfile is small, use insertion sort  */

         for ( j = base, i = j+size; i < limit; j = i, i += size )

            for ( ; COMP(ctx, j, j+size) > 0; j -= size ) {

               SWAP(j, j+size);

               if ( j == base )

                  break;

            }

         if ( sp != stack ) {         /* if any entries on stack  */

            sp -= 2;                  /* pop the base and limit   */

            base = sp[0];

            limit = sp[1];

         } else                       /* else stack empty, done   */

            break;

      }

   }

}





