qsort.h File Reference

#include <libkern/libkern.h>

Go to the source code of this file.

Macros
#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)

Functions
void	qsort (void *a, size_t n, size_t es, int(*cmp)(const void *, const void *))
static char *	med3 (char *, char *, char *, int(*)(const void *, const void *))
static void	swapfunc (char *, char *, int, int)

Macro Definition Documentation

min

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

Definition at line 83 of file qsort.h.

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 111 of file qsort.h.

swapcode

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

Value:

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

Definition at line 88 of file qsort.h.

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 99 of file qsort.h.

vecswap

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

Definition at line 119 of file qsort.h.

Function Documentation

med3()

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

inlinestatic

Definition at line 122 of file qsort.h.

{
    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 ));
}

References a, b, c, and cmp().

Referenced by qsort().

qsort()

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

Definition at line 130 of file qsort.h.

{
    char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
    int d, swaptype, swap_cnt;
    int 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((size_t)(pd - pc), pn - pd - es);
    vecswap(pb, pn - r, r);
    if ((size_t)(r = pb - pa) > es)
        qsort(a, r / es, es, cmp);
    if ((size_t)(r = pd - pc) > es) { 
        /* Iterate rather than recurse to save stack space */
        a = pn - r;
        n = r / es;
        goto loop;
    }
/*      qsort(pn - r, r / es, es, cmp);*/
}

References a, cmp(), d, loop, med3(), min, n, pc, pl, r, swap, SWAPINIT, and vecswap.

Referenced by apprentice_load(), build_immediate_table(), build_opcode_table(), compare_zip(), ef_read(), main(), make_program_env(), print_insn_lanai(), print_insn_sparc(), scandir(), sdb_array_add_sorted(), sdb_array_sort(), sdb_array_sort_num(), and xtensa_isa_init().

swapfunc()

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

inlinestatic

Definition at line 103 of file qsort.h.

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

References a, b, n, and swapcode.