qsortrtn.c

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

            while( size > 1 ) {
                word = *(PTRATTR short *)p;
                *(PTRATTR short *)p = *(PTRATTR short *)q;
                *(PTRATTR short *)q = word;
                p += 2;
                q += 2;
                size -= 2;
            }
        #endif
        if( size ) {
            byte = *p;
            *p = *q;
            *q = byte;
        }
    }
#endif


FUNCTION_LINKAGE void FUNCTION_NAME(
                                     PTRATTR void *in_base, size_t n,
                                     size_t size,
                                     int (*compar)(const void *, const void *)
                                   )
/**********************************************************************/
{
    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 int        sp;
    auto char *         base_stack[MAXDEPTH];
    auto unsigned int   n_stack[MAXDEPTH];
    qcomp *             cmp = (qcomp*) compar;

    /*
        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 ) > 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 );
                        mid = MED3( mid - s, mid, mid + s, cmp );
                        p2  = MED3( p2 - (s << 1), p2 - s, p2, cmp );
                    }
                    /* Mid-size (29 < n < 43), med of 3 */
                    mid = MED3( p1, mid, p2, cmp );
                }
                /*
                    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)) <= 0) {
                        if( comparison == 0 ) {
                            swap( pa, pb );
                            pa += size;
                        }
                        pb += size;
                        count--;
                    }
                    while(count && (comparison = cmp(pc, pv)) >= 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];
    }
}