sigv4_quicksort.c File Reference

Implements an Iterative Quicksort Algorithm for the SigV4 Library. More...

#include "sigv4_quicksort.h"
#include <string.h>
#include <assert.h>

Macros
#define	PUSH_STACK(valueToPush, stack, index)
	Push a value to the stack.
#define	POP_STACK(valueToPop, stack, index)
	Pop a value from the stack.

Functions
static void	swap (void *pFirstItem, void *pSecondItem, size_t itemSize)
	A helper function to swap the value of two pointers given their sizes.
static void	quickSortHelper (void *pArray, size_t low, size_t high, size_t itemSize, ComparisonFunc_t comparator)
	A helper function to perform quicksort on a subarray.
static size_t	partition (void *pArray, size_t low, size_t high, size_t itemSize, ComparisonFunc_t comparator)
	A helper function to partition a subarray using the last element of the array as the pivot. All items smaller than the pivot end up at its left while all items greater than end up at its right.
void	quickSort (void *pArray, size_t numItems, size_t itemSize, ComparisonFunc_t comparator)
	Perform quicksort on an array.

Detailed Description

Implements an Iterative Quicksort Algorithm for the SigV4 Library.

Macro Definition Documentation

PUSH_STACK

#define PUSH_STACK	(		valueToPush,
			stack,
			index
	)

Value:

    {                                             \
        ( stack )[ ( index ) ] = ( valueToPush ); \
        ++( index );                              \
    }

Push a value to the stack.

POP_STACK

#define POP_STACK	(		valueToPop,
			stack,
			index
	)

Value:

    {                                            \
        --( index );                             \
        ( valueToPop ) = ( stack )[ ( index ) ]; \
    }

Pop a value from the stack.

Function Documentation

swap()

static void swap ( void *  pFirstItem, void *  pSecondItem, size_t  itemSize  )

static

A helper function to swap the value of two pointers given their sizes.

Parameters

[in]	pFirstItem	The item to swap with pSecondItem.
[in]	pSecondItem	The item to swap with pFirstItem.
[in]	itemSize	The amount of memory per entry in the array.

quickSortHelper()

static void quickSortHelper ( void *  pArray, size_t  low, size_t  high, size_t  itemSize, ComparisonFunc_t  comparator  )

static

A helper function to perform quicksort on a subarray.

Parameters

[in]	pArray	The array to be sorted.
[in]	low	The low index of the array.
[in]	high	The high index of the array.
[in]	itemSize	The amount of memory per entry in the array.
[out]	comparator	The comparison function to determine if one item is less than another.

partition()

static size_t partition ( void *  pArray, size_t  low, size_t  high, size_t  itemSize, ComparisonFunc_t  comparator  )

static

A helper function to partition a subarray using the last element of the array as the pivot. All items smaller than the pivot end up at its left while all items greater than end up at its right.

Parameters

[in]	pArray	The array to be sorted.
[in]	low	The low index of the array.
[in]	high	The high index of the array.
[in]	itemSize	The amount of memory per entry in the array.
[out]	comparator	The comparison function to determine if one item is less than another.

Returns

The index of the pivot

quickSort()

void quickSort	(	void *	pArray,
		size_t	numItems,
		size_t	itemSize,
		ComparisonFunc_t	comparator
	)

Perform quicksort on an array.

Parameters

[in]	pArray	The array to be sorted.
[in]	numItems	The number of items in an array.
[in]	itemSize	The amount of memory per entry in the array.
[out]	comparator	The comparison function to determine if one item is less than another.