Standard search-and-sort routines. More...

#include <LSSTDSearch.h>

Public Types
typedef LSINT32(LSE_CCALL *	PfBSearchFunc )(LSVOID _pvContext, const LSVOID _pvLeft, const LSVOID *_pvRight)
typedef LSINT32(LSE_CCALL *	PfSortFunc )(LSVOID _pvContext, const LSVOID _pvLeft, const LSVOID *_pvRight)
Static Public Member Functions
static LSVOID *LSE_CALL	BSearch (const LSVOID _pvKey, const LSVOID _pvBase, LSUINTPTR _uiptrNum, LSUINTPTR _uiptrWidth, PfBSearchFunc _pbsfFunc, LSVOID *_pvContext)
static LSVOID LSE_CALL	QSort (LSVOID _pvBase, LSUINTPTR _uiptrNum, LSUINTPTR _uiptrWidth, PfSortFunc _psfFunc, LSVOID _pvContext)
static LSVOID LSE_CALL	MergeSort (LSVOID _pvBase, LSUINTPTR _uiptrNum, LSUINTPTR _uiptrWidth, PfSortFunc _psfFunc, LSVOID _pvContext)
static LSVOID LSE_CALL	ShortSort (LSUINT8 _pui8Low, LSUINT8 _pui8High, LSUINTPTR _uiptrWidth, PfSortFunc _psfFunc, LSVOID *_pvContext)
Static Protected Member Functions
static LSVOID LSE_CALL	ShortSwap (LSUINT8 _pui8A, LSUINT8 _pui8B, LSUINTPTR _uiptrSize)
static LSVOID LSE_CALL	Merge (LSUINT8 _pui8Left, LSUINT32 _ui32LeftTotal, LSUINT8 _pui8Right, LSUINT32 _ui32RightTotal, LSVOID _pvDest, LSUINTPTR _uiptrWidth, PfSortFunc _psfFunc, LSVOID _pvContext)

Detailed Description

Standard search-and-sort routines.

Class CSearch Description: Standard search-and-sort routines.

Member Typedef Documentation

typedef LSINT32(LSE_CCALL * lsstd::CSearch::PfBSearchFunc)(LSVOID *_pvContext, const LSVOID *_pvLeft, const LSVOID *_pvRight)

BSearch callback function prototype.

typedef LSINT32(LSE_CCALL * lsstd::CSearch::PfSortFunc)(LSVOID *_pvContext, const LSVOID *_pvLeft, const LSVOID *_pvRight)

MergeSort, QSort and ShortSort callback function prototype.

Member Function Documentation

static LSVOID* LSE_CALL lsstd::CSearch::BSearch	(	const LSVOID *	_pvKey,
		const LSVOID *	_pvBase,
		LSUINTPTR	_uiptrNum,
		LSUINTPTR	_uiptrWidth,
		PfBSearchFunc	_pbsfFunc,
		LSVOID *	_pvContext
	)		`[static]`

Perform a binary search on an array of data in memory.

Parameters:

_pvKey	Object for which to search.
_pvBase	Pointer to the base of the data to search.
_uiptrNum	Number of elements in the data to which _pvBase points.
_uiptrWidth	Width of the elements in the data to which _pvBase points.
_pbsfFunc	Callback function that compares two elements. The first argument is the _pvContext pointer. The second argument is a pointer to the _pvKey for the search. The third argument is a pointer to the array element to be compared with _pvKey.
_pvContext	A pointer to an object that can be accessed in the comparison function.

Returns:: Returns a pointer to an occurrence of _pvKey in the array to which _pvBase points. If _pvKey is not found, the function returns NULL. If the array is not in ascending sort order or contains duplicate records with identical keys, the result is unpredictable.

static LSVOID LSE_CALL lsstd::CSearch::Merge	(	LSUINT8 *	_pui8Left,
		LSUINT32	_ui32LeftTotal,
		LSUINT8 *	_pui8Right,
		LSUINT32	_ui32RightTotal,
		LSVOID *	_pvDest,
		LSUINTPTR	_uiptrWidth,
		PfSortFunc	_psfFunc,
		LSVOID *	_pvContext
	)		`[static, protected]`

Merge buckets in a merge sort.

Parameters:

_pui8Left	Pointer to the first item in the left bucket.
_ui32LeftTotal	Total items in the left bucket.
_pui8Right	Pointer to the first item in the right bucket.
_ui32RightTotal	Total items in the right bucket.
_pvDest	Destination where to copy the items.
_uiptrWidth	Element size in bytes.
_psfFunc	Comparison function. The first argument is the context pointer. The second argument is a pointer to the left element to compare. The third argument is a pointer to the right element to be compared against the left.
_pvContext	A pointer to a context, which can be any object that the compare routine needs to access.

static LSVOID LSE_CALL lsstd::CSearch::MergeSort	(	LSVOID *	_pvBase,
		LSUINTPTR	_uiptrNum,
		LSUINTPTR	_uiptrWidth,
		PfSortFunc	_psfFunc,
		LSVOID *	_pvContext
	)		`[static]`

A stable in-place merge sort. Avoid recursion and makes only one allocation for the whole operation.

Parameters:

_pvBase	Start of target array.
_uiptrNum	Array size in elements.
_uiptrWidth	Element size in bytes.
_psfFunc	Comparison function. The first argument is the context pointer. The second argument is a pointer to the left element to compare. The third argument is a pointer to the right element to be compared against the left.
_pvContext	A pointer to a context, which can be any object that the compare routine needs to access.

static LSVOID LSE_CALL lsstd::CSearch::QSort	(	LSVOID *	_pvBase,
		LSUINTPTR	_uiptrNum,
		LSUINTPTR	_uiptrWidth,
		PfSortFunc	_psfFunc,
		LSVOID *	_pvContext
	)		`[static]`

A quick sort.

Parameters:

_pvBase	Start of target array.
_uiptrNum	Array size in elements.
_uiptrWidth	Element size in bytes.
_psfFunc	Comparison function. The first argument is the context pointer. The second argument is a pointer to the left element to compare. The third argument is a pointer to the right element to be compared against the left.
_pvContext	A pointer to a context, which can be any object that the compare routine needs to access.

static LSVOID LSE_CALL lsstd::CSearch::ShortSort	(	LSUINT8 *	_pui8Low,
		LSUINT8 *	_pui8High,
		LSUINTPTR	_uiptrWidth,
		PfSortFunc	_psfFunc,
		LSVOID *	_pvContext
	)		`[static]`

A short sort. This works faster on smaller data sets. QSort() calls this automatically, so there is no need to use this directly unless you know your data is always under 9 elements in length.

Parameters:

_pui8Low	Start of target array.
_pui8High	End of the array.
_uiptrWidth	Element size in bytes.
_psfFunc	Comparison function. The first argument is the context pointer. The second argument is a pointer to the left element to compare. The third argument is a pointer to the right element to be compared against the left.
_pvContext	A pointer to a context, which can be any object that the compare routine needs to access.

LSE_INLINE LSVOID LSE_CALL lsstd::CSearch::ShortSwap	(	LSUINT8 *	_pui8A,
		LSUINT8 *	_pui8B,
		LSUINTPTR	_uiptrSize
	)		`[static, protected]`

Perform a byte-by-byte swap to avoid alignment issues.

Parameters:

_pui8A	The first element.
_pui8B	The second element.
_uiptrSize	Size of the elements to be swapped.

The documentation for this class was generated from the following file:

F:/My Projects/LSEngine/Modules/LSStandardLib/Src/Search/LSSTDSearch.h

lsstd::CSearch Class Reference

Public Types

Static Public Member Functions

Static Protected Member Functions

Detailed Description

Member Typedef Documentation

Member Function Documentation