qsortr_s.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 361 行 · 第 1/2 页

            *p = *q;
            *q = byte;
        }
    }
#endif


FUNCTION_LINKAGE errno_t FUNCTION_NAME( PTRATTR void *in_base,
                                        rsize_t n, rsize_t size,
               int (*compar)( const void *, const void *, void * ),
                                        void *context )
/*****************************************************************/
{
    PTRATTR char        *base = (PTRATTR char*) in_base;
    PTRATTR char        *p1;
    PTRATTR char        *p2;
    PTRATTR char        *pa;
    PTRATTR char        *pb;
    PTRATTR char        *pc;
    PTRATTR char        *pd;
    PTRATTR char        *pn;
    PTRATTR char        *pv;
    PTRATTR char        *mid;
    WORD                v;              /* used in pivot initialization */
    WORD                t;              /* used in exch() macro */
    int                 comparison, swaptype, shell;
    size_t              count, r, s;
    unsigned            sp;
    auto char           *base_stack[MAXDEPTH];
    unsigned            n_stack[MAXDEPTH];
    qcomp               *cmp = (qcomp*)compar;
    errno_t             rc = -1;

    /* runtime-constraints */
    // n     <= RSIZE_MAX
    // size  <= RSIZE_MAX
    // if n  > 0  then in_base, compar not NULL
    if( __check_constraint_maxsize( n ) &&
        __check_constraint_maxsize( size ) &&
        ((n == 0) || __check_constraint_nullptr( in_base ) &&
                     __check_constraint_nullptr( compar )) ) {

        if( n == 0 ) {                              /* empty array - nothing to do */
            return( 0 );
        }

        /*
            Initialization of the swaptype variable, which determines which
            type of swapping should be performed when swap() is called.
            0 for single-word swaps, 1 for general swapping by words, and
            2 for swapping by bytes.  W (it's a macro) = sizeof(WORD).
        */
        swaptype = ( ( base - (char *)0 ) | size ) % W ? 2 : size > W ? 1 : 0;
        sp = 0;
        for( ;; ) {
            while( n > 1 ) {
                if( n < 16 ) {      /* 2-shell sort on smallest arrays */
                    for( shell = (size * SHELL) ;
                         shell > 0 ;
                         shell -= ((SHELL-1) * size) ) {
                        p1 = base + shell;
                        for( ; p1 < base + n * size; p1 += shell ) {
                            for( p2 = p1;
                                 p2 > base && cmp( p2 - shell, p2, context ) > 0;
                                 p2 -= shell ) {
                                swap( p2, p2 - shell );
                            }
                        }
                    }
                    break;
                } else {    /* n >= 16 */
                    /* Small array (15 < n < 30), mid element */
                    mid = base + (n >> 1) * size;
                    if( n > 29 ) {
                        p1 = base;
                        p2 = base + ( n - 1 ) * size;
                        if( n > 42 ) {      /* Big array, pseudomedian of 9 */
                            s = (n >> 3) * size;
                            p1  = MED3( p1, p1 + s, p1 + (s << 1), cmp, context );
                            mid = MED3( mid - s, mid, mid + s, cmp, context );
                            p2  = MED3( p2 - (s << 1), p2 - s, p2, cmp, context );
                        }
                        /* Mid-size (29 < n < 43), med of 3 */
                        mid = MED3( p1, mid, p2, cmp, context );
                    }
                    /*
                        The following sets up the pivot (pv) for partitioning.
                        It's better to store the pivot value out of line
                        instead of swapping it to base. However, it's
                        inconvenient in C unless the element size is fixed.
                        So, only the important special case of word-size
                        objects has utilized it.
                    */
                    if( swaptype != 0 ) { /* Not word-size objects */
                        pv = base;
                        swap( pv, mid );
                    } else {        /* Storing the pivot out of line (at v) */
                        pv = (char *)&v;
                        v = *(WORD *)mid;
                    }

                    pa = pb = base;
                    pc = pd = base + ( n - 1 ) * size;
                    count = n;
                    /*
                        count keeps track of how many entries we have
                        examined.  Once we have looked at all the entries
                        then we know that the partitioning is complete.
                        We use count to terminate the looping, rather than
                        a pointer comparison, to handle 16bit pointer
                        limitations that may lead pb or pc to wrap.
                        i.e. pc  = 0x0000;
                             pc -= 0x0004;
                             pc == 0xfffc;
                             pc is no longer less that 0x0000;
                    */
                    for( ;; ) {
                        while( count && (comparison = cmp(pb, pv, context )) <= 0 ) {
                            if( comparison == 0 ) {
                                swap( pa, pb );
                                pa += size;
                            }
                            pb += size;
                            count--;
                        }
                        while( count && (comparison = cmp(pc, pv, context )) >= 0 ) {
                            if( comparison == 0 ) {
                                swap( pc, pd );
                                pd -= size;
                            }
                            pc -= size;
                            count--;
                        }
                        if( !count ) break;
                        swap( pb, pc );
                        pb += size;
                        count--;
                        if( !count ) break;
                        pc -= size;
                        count--;
                    }
                    pn = base + n * size;
                    s = min( pa - base, pb - pa );
                    if( s > 0 ) {
                        inline_swap( base, pb - s, s );
                    }
                    s = min( pd - pc, pn - pd - size);
                    if( s > 0 ) {
                        inline_swap( pb, pn - s, s );
                    }
                    /* Now, base to (pb-pa) needs to be sorted              */
                    /* Also, pn-(pd-pc) needs to be sorted                  */
                    /* The middle 'chunk' contains all elements=pivot value */
                    r = pb - pa;
                    s = pd - pc;
                    if( s >= r ) {          /* Stack up the larger chunk */
                        base_stack[sp] = pn - s;    /* Stack up base            */
                        n_stack[sp] = s / size;     /* Stack up n               */
                        n = r / size;               /* Set up n for next 'call' */
                                                    /* next base is still base  */
                    } else {
                        if( r <= size ) break;
                        base_stack[sp] = base;      /* Stack up base            */
                        n_stack[sp] = r / size;     /* Stack up n               */
                        base = pn - s;              /* Set up base and n for    */
                        n = s / size;               /* next 'call'              */
                    }
                    ++sp;
                }
            }
            if( sp == 0 ) break;
            --sp;
            base = base_stack[sp];
            n    = n_stack[sp];
        }
        rc = 0;
    }
    return( rc );
}