Search and Sort

Typedefs
typedef int(*	M_sort_compar_t) (const void *arg1, const void *arg2, void *thunk)

Functions
size_t	M_sort_binary_insert_idx (const void *base, size_t nmemb, size_t esize, const void *key, M_bool stable, M_sort_compar_t compar, void *thunk)
M_bool	M_sort_binary_search (const void *base, size_t nmemb, size_t esize, const void *key, M_bool stable, M_sort_compar_t compar, void *thunk, size_t *idx)
void	M_sort_qsort (void *base, size_t nmemb, size_t esize, M_sort_compar_t compar, void *thunk)
void	M_sort_mergesort (void *base, size_t nmemb, size_t esize, M_sort_compar_t compar, void *thunk)
int	M_sort_compar_str (const void *arg1, const void *arg2, void *thunk)
int	M_sort_compar_str_desc (const void *arg1, const void *arg2, void *thunk)
int	M_sort_compar_str_casecmp (const void *arg1, const void *arg2, void *thunk)
int	M_sort_compar_str_casecmp_desc (const void *arg1, const void *arg2, void *thunk)
int	M_sort_compar_u64 (const void *arg1, const void *arg2, void *thunk)
int	M_sort_compar_u64_desc (const void *arg1, const void *arg2, void *thunk)
int	M_sort_compar_binwraped (const void *arg1, const void *arg2, void *thunk)
int	M_sort_compar_vp (const void *arg1, const void *arg2, void *thunk)
int	M_sort_compar_vp_desc (const void *arg1, const void *arg2, void *thunk)

Detailed Description

Searching and sorting operations.

Typedef Documentation

M_sort_compar_t

typedef int(* M_sort_compar_t) (const void *arg1, const void *arg2, void *thunk)

Comparision function prototype.

Used the same as qsort or bsearch!

The internal array holding the data elements is a void pointer which means the compar function has a reference to the index of the array (void **). That means you may need to dereference more time than you think if base is an array of pointer. E.g:

Array: my_type_t **data;
Deref: my_type_t *t1 = *((my_type_t * const *)arg1);

Array: M_uint64 **data;
Deref: M_uint64 i1 = *(*((M_uint64 * const *)arg1));

If base is an arrary of fixed data. E.g:

my_type_t *data;
data = M_malloc_zero(sizeof(*data) * cnt));
data[0].v1 = "a";
data[0].v2 = "b";
...
Deref: const my_type_t *t1 = arg1;


M_uint64 *data = { 1, 2, 3 };
Deref: M_uint64 i1 = *((M_uint64 const *)arg1);

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

Function Documentation

M_sort_binary_insert_idx()

size_t M_sort_binary_insert_idx	(	const void *	base,
		size_t	nmemb,
		size_t	esize,
		const void *	key,
		M_bool	stable,
		M_sort_compar_t	compar,
		void *	thunk
	)

Find the index the key should be inserted at in a sorted array.

Parameters

[in]	base	The array of elements to search.
[in]	nmemb	The number of elements in the array.
[in]	esize	The size of each element in the array.
[in]	key	The element to be inserted.
[in]	stable	Should the insert find and use the last matching element. This can cause performance to degrade to worst case O(n/2).
[in]	compar	The comparision function.
[in]	thunk	Additional data to pass to the comparison function.

Returns

The index the item should be inserted at. If the the key is <= the first element, will always return 0. If the key is >= the last element, will always return nmemb.

M_sort_binary_search()

M_bool M_sort_binary_search	(	const void *	base,
		size_t	nmemb,
		size_t	esize,
		const void *	key,
		M_bool	stable,
		M_sort_compar_t	compar,
		void *	thunk,
		size_t *	idx
	)

Find and element in a sorted array.

Parameters

[in]	base	The array of elements to search.
[in]	nmemb	The number of elements in the array.
[in]	esize	The size of each element in the array.
[in]	key	The element to be inserted.
[in]	stable	Should the insert find and use the last matching element. This can cause performance to degrade to worst case O(n/2).
[in]	compar	The comparision function.
[in]	thunk	Additional data to pass to the comparison function.
[out]	idx	The index of the items location.

Returns

True if the item was found. Otherwise false.

M_sort_qsort()

void M_sort_qsort	(	void *	base,
		size_t	nmemb,
		size_t	esize,
		M_sort_compar_t	compar,
		void *	thunk
	)

Sort elements in array in ascending order according to comparison function.

This is an unstable sort.

Parameters

[in,out]	base	The array of elements to sort.
[in]	nmemb	The number of elements in the array.
[in]	esize	The size of each element in the array.
[in]	compar	The comparison function.
[in]	thunk	Additional data to pass to the comparison function.

M_sort_mergesort()

void M_sort_mergesort	(	void *	base,
		size_t	nmemb,
		size_t	esize,
		M_sort_compar_t	compar,
		void *	thunk
	)

Sort elements in array in ascending order according to comparison function.

This is a stable sort.

Parameters

[in,out]	base	The array of elements to sort.
[in]	nmemb	The number of elements in the array.
[in]	esize	The size of each element in the array.
[in]	compar	The comparison function.
[in]	thunk	Additional data to pass to the comparison function.

M_sort_compar_str()

int M_sort_compar_str	(	const void *	arg1,
		const void *	arg2,
		void *	thunk
	)

qsort style string comparison in ascending order.

Base must be an array of pointers to values.

const char **array;

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

See also

M_sort_compar_t

M_sort_compar_str_desc()

int M_sort_compar_str_desc	(	const void *	arg1,
		const void *	arg2,
		void *	thunk
	)

qsort style string comparison in descending order.

Base must be an array of pointers to values.

const char **array;

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

See also

M_sort_compar_t

M_sort_compar_str_casecmp()

int M_sort_compar_str_casecmp	(	const void *	arg1,
		const void *	arg2,
		void *	thunk
	)

qsort style string comparison in ascending order case insensitive.

Base must be an array of pointers to values.

const char **array;

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

See also

M_sort_compar_t

M_sort_compar_str_casecmp_desc()

int M_sort_compar_str_casecmp_desc	(	const void *	arg1,
		const void *	arg2,
		void *	thunk
	)

qsort style string comparison in descending order case insensitive.

Base must be an array of pointers to values.

const char **array;

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

See also

M_sort_compar_t

M_sort_compar_u64()

int M_sort_compar_u64	(	const void *	arg1,
		const void *	arg2,
		void *	thunk
	)

qsort style unsigned integer comparison in ascending order.

Base must be an array of pointers to values.

M_uint64 **array;

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

See also

M_sort_compar_t

M_sort_compar_u64_desc()

int M_sort_compar_u64_desc	(	const void *	arg1,
		const void *	arg2,
		void *	thunk
	)

qsort style unsigned integer comparison in descending order.

Base must be an array of pointers to values.

M_uint64 **array;

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

See also

M_sort_compar_t

M_sort_compar_binwraped()

int M_sort_compar_binwraped	(	const void *	arg1,
		const void *	arg2,
		void *	thunk
	)

qsort style wrapped binary data comparison for data that has been wrapped using M_bin_wrap.

The binary data will be compared using M_mem_cmpsort.

Base must be an array of pointers to values.

M_uint8 **array;

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

See also

M_sort_compar_t

M_mem_cmpsort

M_bin_wrap

M_sort_compar_vp()

int M_sort_compar_vp	(	const void *	arg1,
		const void *	arg2,
		void *	thunk
	)

qsort style unsigned integer comparison in ascending order.

The pointer themselves are compared; not the value they point to.

Base must be an array of pointers to values.

void **array;

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

See also

M_sort_compar_t

M_sort_compar_vp_desc()

int M_sort_compar_vp_desc	(	const void *	arg1,
		const void *	arg2,
		void *	thunk
	)

qsort style unsigned integer comparison in descending order.

The pointer themselves are compared; not the value they point to.

Base must be an array of pointers to values.

void **array;

Parameters

[in]	arg1	The first arg to compare.
[in]	arg2	The second arg to compare.
[in]	thunk	Additional data to use for comparison.

Returns

-1, 0, 1 for arg1 < arg2, arg1 == arg2, arg1 > arg2.

See also

M_sort_compar_t