qsort.c File Reference

#include <stdlib.h>
#include <search.h>

Include dependency graph for qsort.c:

Go to the source code of this file.

Macros
#define	long   intptr_t
#define	min(a, b)   (a) < (b) ? (a) : (b)
#define	swapcode(TYPE, parmi, parmj, n)
#define	SWAPINIT(a, es)
#define	swap(a, b)
#define	vecswap(a, b, n)   if ((n) > 0) swapfunc(a, b, n, swaptype)
#define	CMP(x, y)   (cmp((x), (y)))

Functions
static __inline void	swapfunc (char *a, char *b, intptr_t n, int swaptype)
static __inline char *	med3 (char *a, char *b, char *c, int(__cdecl *cmp)(const void *, const void *))
void __cdecl	qsort (void *a, size_t n, size_t es, int(__cdecl *cmp)(const void *, const void *))

Macro Definition Documentation

CMP

#define CMP	(		x,
			y
	)		(cmp((x), (y)))

Definition at line 73 of file qsort.c.

long

typedef void unsigned long   intptr_t

Definition at line 33 of file qsort.c.

Referenced by __do_global_ctors(), __debug_alloc< _Alloc >::__extra_after_chunk(), __debug_alloc< _Alloc >::__extra_before_chunk(), __remainder_piby2(), __remainder_piby2f(), __write_formatted_timeT(), _bdf_list_ensure(), _bdf_parse_glyphs(), _bdf_readstream(), _lrotl(), _lrotr(), _mm_movpi64_epi64(), _svcauth_des(), _svcauth_unix(), _tzset(), access_virt_barray(), access_virt_sarray(), CInternetToolbar::AddString(), adler32_combine_(), TrimRegion::advance(), APICCalibrateTimer(), BDF_Face_Init(), bit_read_long(), bmap(), CC_MouseCheckColorGraph(), CC_PaintCross(), CC_PaintTriangle(), check_file(), chm_openW(), convert_1970_to_filetime(), convert_utf16bom(), __debug_alloc< _Alloc >::deallocate(), decode_header(), DefineDosDeviceW(), deflateSetDictionary(), DGifDecompressInput(), DGifGetImageDesc(), do_barray_io(), do_div(), do_sarray_io(), doflag(), DrawStarField(), empty(), EndLog(), ext4_ext_rm_leaf(), fill_window(), fillbytes(), floor(), FT_FixedFromFIXED(), FT_Stream_Open(), generic_head_read(), TrimRegion::getGridExtent(), GetHostByName(), CInternetToolbar::GetState(), gettimeofday(), handle_apetag(), inflate_fast(), inflateMark(), Varray::init(), Uarray::init(), init_waitqueue_entry(), init_waitqueue_head(), initial_setup(), jinit_c_coef_controller(), jinit_c_main_controller(), jinit_compress_master(), jinit_d_coef_controller(), jinit_d_post_controller(), jinit_upsampler(), journal_bmap(), jpeg_add_quant_table(), jpeg_calc_output_dimensions(), jpeg_finish_compress(), jpeg_read_raw_data(), jpeg_read_scanlines(), jpeg_write_raw_data(), jpeg_write_scanlines(), main(), master_selection(), MCIQTZ_mciSetAudio(), movebytes(), mpg123_getpar(), mpg123_getstate(), output_pass_setup(), parse_arguments(), parse_new_id3(), per_scan_setup(), PrPhilBar(), CConsole::ReadLine(), realize_virt_arrays(), remainder(), rsa_exptmod(), Subdivider::samplingSplit(), SelectSetInit(), set_pointer(), Arc::setside(), START_TEST(), strtol(), strtoull(), synth_ntom_set_step(), test_assign(), transdecode_master_selection(), TRIO_ARGS2(), UDFInitializeFunctionPointers(), ui_create_colourmap(), vio_modern_query_vq_alloc(), WaitResponse(), wave_out_set_format(), wcstol(), wcstoul(), win32_tell_file_func(), xdr_int(), xdr_int16_t(), xdr_int32_t(), xdr_putint32(), xdr_short(), xdrrec_getlong(), xdrstdio_getlong(), xdrstdio_putlong(), xmlDictComputeFastQKey(), xmlHashComputeQKey(), xmlMemDisplayLast(), xsltGenerateIdFunction(), and zerobytes().

min

#define min	(		a,
			b
	)		(a) < (b) ? (a) : (b)

Definition at line 35 of file qsort.c.

swap

#define swap	(		a,
			b
	)

Value:

    if (swaptype == 0) {                \
        long t = *(long *)(a);          \
        *(long *)(a) = *(long *)(b);        \
        *(long *)(b) = t;           \
    } else                      \
        swapfunc(a, b, es, swaptype)

Definition at line 63 of file qsort.c.

swapcode

#define swapcode	(		TYPE,
			parmi,
			parmj,
			n
	)

Value:

    {       \
    long i = (n) / sizeof (TYPE);           \
    register TYPE *pi = (TYPE *) (parmi);       \
    register TYPE *pj = (TYPE *) (parmj);       \
    do {                        \
        register TYPE   t = *pi;        \
        *pi++ = *pj;                \
        *pj++ = t;              \
        } while (--i > 0);              \
}

Definition at line 40 of file qsort.c.

SWAPINIT

#define SWAPINIT	(		a,
			es
	)

Value:

    swaptype = ((char *)a - (char *)0) % sizeof(long) || \
    es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

Definition at line 51 of file qsort.c.

vecswap

#define vecswap	(		a,
			b,
			n
	)		if ((n) > 0) swapfunc(a, b, n, swaptype)

Definition at line 71 of file qsort.c.

Function Documentation

med3()

static __inline char * med3 ( char *  a, char *  b, char *  c, int(__cdecl *cmp)(const void *, const void *)    )

static

Definition at line 76 of file qsort.c.

{
    return CMP(a, b) < 0 ?
           (CMP(b, c) < 0 ? b : (CMP(a, c) < 0 ? c : a ))
              :(CMP(b, c) > 0 ? b : (CMP(a, c) < 0 ? a : c ));
}

Referenced by qsort().

qsort()

void __cdecl qsort	(	void *	a,
		size_t	n,
		size_t	es,
		int(__cdecl *cmp)(const void *, const void *)
	)

Definition at line 93 of file qsort.c.

{
    char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
    int swaptype, swap_cnt;
    intptr_t d, r;
 
loop:   SWAPINIT(a, es);
    swap_cnt = 0;
    if (n < 7) {
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
                 pl -= es)
                swap(pl, pl - es);
        return;
    }
    pm = (char *)a + (n / 2) * es;
    if (n > 7) {
        pl = a;
        pn = (char *)a + (n - 1) * es;
        if (n > 40) {
            d = (n / 8) * es;
            pl = med3(pl, pl + d, pl + 2 * d, cmp);
            pm = med3(pm - d, pm, pm + d, cmp);
            pn = med3(pn - 2 * d, pn - d, pn, cmp);
        }
        pm = med3(pl, pm, pn, cmp);
    }
    swap(a, pm);
    pa = pb = (char *)a + es;
 
    pc = pd = (char *)a + (n - 1) * es;
    for (;;) {
        while (pb <= pc && (r = CMP(pb, a)) <= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pa, pb);
                pa += es;
            }
            pb += es;
        }
        while (pb <= pc && (r = CMP(pc, a)) >= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pc, pd);
                pd -= es;
            }
            pc -= es;
        }
        if (pb > pc)
            break;
        swap(pb, pc);
        swap_cnt = 1;
        pb += es;
        pc -= es;
    }
    if (swap_cnt == 0) {  /* Switch to insertion sort */
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
                 pl -= es)
                swap(pl, pl - es);
        return;
    }
 
    pn = (char *)a + n * es;
    r = min(pa - (char *)a, pb - pa);
    vecswap(a, pb - r, r);
    r = min(pd - pc, pn - pd - es);
    vecswap(pb, pn - r, r);
    if ((r = pb - pa) > es)
        qsort(a, r / es, es, cmp);
    if ((r = pd - pc) > es) {
        /* Iterate rather than recurse to save stack space */
        a = pn - r;
        n = r / es;
        goto loop;
    }
}

Referenced by qsort().

swapfunc()

static __inline void swapfunc ( char *  a, char *  b, intptr_t  n, int  swaptype  )

static

Definition at line 55 of file qsort.c.

{
    if(swaptype <= 1)
        swapcode(long, a, b, n)
    else
        swapcode(char, a, b, n)
}