heapsort.c File Reference

#include <stddef.h>
#include <stdlib.h>

Include dependency graph for heapsort.c:

Go to the source code of this file.

Macros
#define	SWAP(a, b, count, size, tmp)
#define	COPY(a, b, count, size, tmp1, tmp2)
#define	CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp)
#define	SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2)

Functions
int	heapsort (void *vbase, size_t nmemb, size_t size, int *compar)

Macro Definition Documentation

COPY

#define COPY	(		a,
			b,
			count,
			size,
			tmp1,
			tmp2
	)

Value:

{                                       \
        count = size;                       \
        tmp1 = a;                           \
        tmp2 = b;                           \
        do                                  \
        {                                   \
            *tmp1++ = *tmp2++;              \
        } while(--count);                   \
    }

Definition at line 55 of file heapsort.c.

CREATE

#define CREATE	(		initval,
			nmemb,
			par_i,
			child_i,
			par,
			child,
			size,
			count,
			tmp
	)

Value:

{                                                                         \
        for(par_i = initval; (child_i = par_i * 2) <= nmemb; par_i = child_i) \
        {                                                                     \
            child = base + child_i * size;                                    \
            if(child_i < nmemb && compar(child, child + size) < 0)            \
            {                                                                 \
                child += size;                                                \
                ++child_i;                                                    \
            }                                                                 \
            par = base + par_i * size;                                        \
            if(compar(child, par) <= 0)                                       \
                break;                                                        \
            SWAP(par, child, count, size, tmp);                               \
        }                                                                     \
    }

Definition at line 73 of file heapsort.c.

SELECT

#define SELECT	(		par_i,
			child_i,
			nmemb,
			par,
			child,
			size,
			k,
			count,
			tmp1,
			tmp2
	)

Value:

{                                                                         \
        for(par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i)       \
        {                                                                     \
            child = base + child_i * size;                                    \
            if(child_i < nmemb && compar(child, child + size) < 0)            \
            {                                                                 \
                child += size;                                                \
                ++child_i;                                                    \
            }                                                                 \
            par = base + par_i * size;                                        \
            COPY(par, child, count, size, tmp1, tmp2);                        \
        }                                                                     \
        for(;;)                                                               \
        {                                                                     \
            child_i = par_i;                                                  \
            par_i = child_i / 2;                                              \
            child = base + child_i * size;                                    \
            par = base + par_i * size;                                        \
            if(child_i == 1 || compar(k, par) < 0)                            \
            {                                                                 \
                COPY(child, k, count, size, tmp1, tmp2);                      \
                break;                                                        \
            }                                                                 \
            COPY(child, par, count, size, tmp1, tmp2);                        \
        }                                                                     \
    }

Definition at line 107 of file heapsort.c.

SWAP

#define SWAP	(		a,
			b,
			count,
			size,
			tmp
	)

Value:

{                                \
        count = size;                \
        do                           \
        {                            \
            tmp = *a;                \
            *a++ = *b;               \
            *b++ = tmp;              \
        } while(--count);            \
    }

Definition at line 43 of file heapsort.c.

Function Documentation

heapsort()

int heapsort	(	void*	vbase,
		size_t	nmemb,
		size_t	size,
		int *	compar
	)

Definition at line 142 of file heapsort.c.

{
    size_t cnt, i, j, l;
    char tmp, *tmp1, *tmp2;
    char *base, *k, *p, *t;

    if(nmemb <= 1)
    {
        {
            return (0);
        }
    }

    if(!size)
    {
        // errno = EINVAL;
        return (-1);
    }

    if((k = malloc(size)) == NULL)
    {
        {
            return (-1);
        }
    }

    /*
     * Items are numbered from 1 to nmemb, so offset from size bytes
     * below the starting address.
     */
    base = (char*)vbase - size;

    for(l = nmemb / 2 + 1; --l;)
        CREATE(l, nmemb, i, j, t, p, size, cnt, tmp);

    /*
     * For each element of the heap, save the largest element into its
     * final slot, save the displaced element (k), then recreate the
     * heap.
     */
    while(nmemb > 1)
    {
        COPY(k, base + nmemb * size, cnt, size, tmp1, tmp2);
        COPY(base + nmemb * size, base + size, cnt, size, tmp1, tmp2);
        --nmemb;
        SELECT(i, j, nmemb, t, p, size, k, cnt, tmp1, tmp2);
    }
    free(k);
    return (0);
}

References COPY, CREATE, free(), malloc(), NULL, and SELECT.