NAME

hsort(3) - generic heap sort

SYNOPSIS

#include <slack/std.h>
#include <slack/hsort.h>

typedef int hsort_cmp_t(const void *a, const void *b);
typedef int hsort_closure_cmp_t(const void *a, const void *b, const void *data);

void hsort(void *base, size_t n, size_t size, hsort_cmp_t *cmp);
void hsort_closure(void *base, size_t n, size_t size, hsort_closure_cmp_t *cmp, const void *data);

DESCRIPTION

hsort(3) is an implementation of the heap sort algorithm. It sorts a table of data in place. base points to the element at the base of the table. n is the number of elements in the table. size is the size of the elements in bytes. cmp is the comparison function, which is called with two arguments that point to the elements being compared. As the function must return an integer less than, equal to, or greater than zero, so must the first argument to be considered be less than, equal to, or greater than the second. This is a drop-in replacement for qsort(3). hsort_closure(3) is the same but it supports passing arbitrary data to the comparison function.

NOTES

The comparison function need not compare every byte, so arbitrary data may be contained in the elements in addition to the values being compared.

The order in the output of two items which compare as equal is unpredictable.

MT-Level

MT-Safe

Note that the array being sorted will still have to be write-locked during hsort(3) if it is accessed by other threads.

EXAMPLE

This examples sorts and prints an array of strings.

#include <slack/std.h>
#include <slack/hsort.h>

int cmp(const char **p1, const char **p2)
{
    return strcmp(*p1, *p2);
}

int main(int ac, char **av)
{
    char *string[4] = { "jkl", "ghi", "def", "abc" };
    int i;

    hsort(string, 4, sizeof string[0], (hsort_cmp_t *)cmp);

    for (i = 0; i < 4; ++i)
        printf("%s\n", string[i]);

    return EXIT_SUCCESS;
}

SEE ALSO

qsort(3)

AUTHOR

Stephen Russell, Department of Computer Science,
University of Sydney, 2006.
Australia
1988 April 28

Header file, test code and manpage by raf <raf@raf.org>