Functions | Variables
cgul_radix_sort.h File Reference

radix sort More...

#include "cgul_common.h"
#include "cgul_exception.h"
#include "cgul_int.h"
Include dependency graph for cgul_radix_sort.h:
This graph shows which files directly or indirectly include this file:

Functions

CGUL_EXPORT void cgul_radix_sort (cgul_exception_t *cex, void *v, size_t v_count, size_t element_size, int ascending_order, cgul_radix_sort__enumerate_t ef, int are_enumerations_signed)
 
CGUL_EXPORT void cgul_radix_sort_pointers (cgul_exception_t *cex, void **v, size_t v_count, int ascending_order, cgul_radix_sort__enumerate_t ef, int are_enumerations_signed)
 
CGUL_EXPORT void cgul_radix_sort_schar (cgul_exception_t *cex, signed char *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_uchar (cgul_exception_t *cex, unsigned char *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_short (cgul_exception_t *cex, short int *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_ushort (cgul_exception_t *cex, unsigned short int *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_int (cgul_exception_t *cex, int *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_uint (cgul_exception_t *cex, unsigned int *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_long (cgul_exception_t *cex, long int *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_ulong (cgul_exception_t *cex, unsigned long int *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_int8 (cgul_exception_t *cex, cgul_int8_t *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_uint8 (cgul_exception_t *cex, cgul_uint8_t *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_int16 (cgul_exception_t *cex, cgul_int16_t *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_uint16 (cgul_exception_t *cex, cgul_uint16_t *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_int32 (cgul_exception_t *cex, cgul_int32_t *v, size_t v_count, int ascending_order)
 
CGUL_EXPORT void cgul_radix_sort_uint32 (cgul_exception_t *cex, cgul_uint32_t *v, size_t v_count, int ascending_order)
 

Variables

CGUL_BEGIN_C typedef unsigned long int(* cgul_radix_sort__enumerate_t )(const void *element)
 

Detailed Description

Radix sort an array.

Author
Paul Serice

Function Documentation

§ cgul_radix_sort()

CGUL_EXPORT void cgul_radix_sort ( cgul_exception_t *  cex,
void *  v,
size_t  v_count,
size_t  element_size,
int  ascending_order,
cgul_radix_sort__enumerate_t  ef,
int  are_enumerations_signed 
)

Perform an in-place radix sort on the array v which holds v_count instances of values having size element_size (in bytes). To sort the array of values, the client must supply the enumeration function ef that maps each value to an integer. This function sorts the values in ascending order of their enumerations if ascending_order is true or in descending order otherwise. If are_enumerations_signed is true, the enumeration returned by ef will be treated is a signed type and sorted accordingly; otherwise, it will be treated as an unsigned type. Because of all the callbacks, this function is about 5x slower than the functions (below) that are optimized for sorting arrays of integers. (This function uses cgul_radix_sort_pointers(), but it can be faster than cgul_radix_sort_pointers() because calling this function means all the values are located in contigous memory which improves locality of reference.) This functions internally allocates (and releases) an extra array large enough to hold a copy of v. If an error occurs, an exception is thrown.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]element_sizesize of each element in v (in bytes)
[in]ascending_orderwhether to sort in ascending order
[in]efenumeration function
[in]are_enumerations_signedwhether the enumerations are signed

§ cgul_radix_sort_pointers()

CGUL_EXPORT void cgul_radix_sort_pointers ( cgul_exception_t *  cex,
void **  v,
size_t  v_count,
int  ascending_order,
cgul_radix_sort__enumerate_t  ef,
int  are_enumerations_signed 
)

Perform an in-place radix sort on the array v which holds v_count instances of pointers to values. To sort the array of pointers, the client must supply the enumeration function ef that maps each pointer to an integer. This function sorts the pointers in ascending order of their enumerations if ascending_order is true or in descending order otherwise. If are_enumerations_signed is true, the enumeration returned by ef will be treated is a signed type and sorted accordingly; otherwise, it will be treated as an unsigned type. Because of all the callbacks, this function is about 10x slower than the functions (below) that are optimized for sorting arrays of integers. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. If an error occurs, an exception is thrown.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order
[in]efenumeration function
[in]are_enumerations_signedwhether the enumerations are signed

§ cgul_radix_sort_schar()

CGUL_EXPORT void cgul_radix_sort_schar ( cgul_exception_t *  cex,
signed char *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of signed char values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. This function assumes the computer represents negative values using two's complement (which should be true for the vast majority of computers). If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_uchar()

CGUL_EXPORT void cgul_radix_sort_uchar ( cgul_exception_t *  cex,
unsigned char *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of unsigned char values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_short()

CGUL_EXPORT void cgul_radix_sort_short ( cgul_exception_t *  cex,
short int *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of short values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. This function assumes the computer represents negative values using two's complement (which should be true for the vast majority of computers). If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_ushort()

CGUL_EXPORT void cgul_radix_sort_ushort ( cgul_exception_t *  cex,
unsigned short int *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of unsigned short values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_int()

CGUL_EXPORT void cgul_radix_sort_int ( cgul_exception_t *  cex,
int *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of int values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. This function assumes the computer represents negative values using two's complement (which should be true for the vast majority of computers). If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_uint()

CGUL_EXPORT void cgul_radix_sort_uint ( cgul_exception_t *  cex,
unsigned int *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of unsigned int values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_long()

CGUL_EXPORT void cgul_radix_sort_long ( cgul_exception_t *  cex,
long int *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of long values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. This function assumes the computer represents negative values using two's complement (which should be true for the vast majority of computers). If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_ulong()

CGUL_EXPORT void cgul_radix_sort_ulong ( cgul_exception_t *  cex,
unsigned long int *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of unsigned long values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_int8()

CGUL_EXPORT void cgul_radix_sort_int8 ( cgul_exception_t *  cex,
cgul_int8_t *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of cgul_int8_t values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. This function assumes the computer represents negative values using two's complement (which should be true for the vast majority of computers). If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_uint8()

CGUL_EXPORT void cgul_radix_sort_uint8 ( cgul_exception_t *  cex,
cgul_uint8_t *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of cgul_uint8_t values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_int16()

CGUL_EXPORT void cgul_radix_sort_int16 ( cgul_exception_t *  cex,
cgul_int16_t *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of cgul_int16_t values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. This function assumes the computer represents negative values using two's complement (which should be true for the vast majority of computers). If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_uint16()

CGUL_EXPORT void cgul_radix_sort_uint16 ( cgul_exception_t *  cex,
cgul_uint16_t *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of cgul_uint16_t values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_int32()

CGUL_EXPORT void cgul_radix_sort_int32 ( cgul_exception_t *  cex,
cgul_int32_t *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of cgul_int32_t values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. This function assumes the computer represents negative values using two's complement (which should be true for the vast majority of computers). If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

§ cgul_radix_sort_uint32()

CGUL_EXPORT void cgul_radix_sort_uint32 ( cgul_exception_t *  cex,
cgul_uint32_t *  v,
size_t  v_count,
int  ascending_order 
)

Perform an in-place radix sort on the array v which holds v_count instances of cgul_uint32_t values. On return, v will be in ascending order if ascending_order is true or in descending order otherwise. This functions internally allocates (and releases) an extra array large enough to hold a copy of v. If an error occurs, an exception is thrown.

If another sort order is desired, use cgul_radix_sort() or cgul_radix_sort_pointers(), but they are much slower than this function.

Parameters
[in,out]cexc-style exception
[in]varray of elements to sort
[in]v_countnumber of elements in v
[in]ascending_orderwhether to sort in ascending order

Variable Documentation

§ cgul_radix_sort__enumerate_t

CGUL_BEGIN_C typedef unsigned long int(* cgul_radix_sort__enumerate_t) (const void *element)

This typedef is the interface the client must define in order for cgul_radix_sort() or cgul_radix_sort_pointers() to sort an array. This function will be called repeatedly during the sorting process, and it should consistently return the same unsigned long value that is associated with the element element from the array being sorted. The elements from the array will then be sorted in ascending order of the enumerations.

If a signed enumeration is more natural for the array being sorted, just have your enumeration function cast the signed enumeration to an unsigned long and use the are_enumerations_signed parameter that is provided for all functions that accept an enumeration function. Alternatively, your enumeration function could just shift the signed values into the unsigned range and return only unsigned values. If the shifted sort order is the same as the original sort order, the end result will be the same.

Parameters
[in]elementelement from the array being sorted
Returns
enumeration for element