IceRevisitedRadix.cpp File Reference

#include "Stdafx.h"

Include dependency graph for IceRevisitedRadix.cpp:

Go to the source code of this file.

Macros
#define	CHECK_PASS_VALIDITY(pass)
#define	CHECK_RESIZE(n)
#define	CREATE_HISTOGRAMS(type, buffer)
#define	CURRENT_SIZE   (mCurrentSize&0x7fffffff)
#define	INVALID_RANKS   (mCurrentSize&0x80000000)
#define	INVALIDATE_RANKS   mCurrentSize|=0x80000000
#define	VALIDATE_RANKS   mCurrentSize&=0x7fffffff

Detailed Description

Contains source code from the article "Radix Sort Revisited".

Author

Pierre Terdiman

Date

April, 4, 2000

Definition in file IceRevisitedRadix.cpp.

Macro Definition Documentation

#define CHECK_PASS_VALIDITY

(

pass

)

Value:

/* Shortcut to current counters */                                                                                                              \
	udword* CurCount = &mHistogram[pass<<8];                                                                                               \
                                                                                                                                                                                        \
        /* Reset flag. The sorting pass is supposed to be performed. (default) */                               \
        bool PerformPass = true;                                                                                                                                \
                                                                                                                                                                                        \
        /* Check pass validity */                                                                                                                               \
                                                                                                                                                                                        \
        /* If all values have the same byte, sorting is useless. */                                                             \
        /* It may happen when sorting bytes or words instead of dwords. */                                              \
        /* This routine actually sorts words faster than dwords, and bytes */                                   \
        /* faster than words. Standard running time (O(4*n))is reduced to O(2*n) */                             \
        /* for words and O(n) for bytes. Running time for floats depends on actual values... */ \
                                                                                                                                                                                        \
        /* Get first byte */                                                                                                                                    \
	ubyte UniqueVal = *(((ubyte*)input)+pass);                                                                                             \
                                                                                                                                                                                        \
        /* Check that byte's counter */                                                                                                                 \
        if(CurCount[UniqueVal]==nb)     PerformPass=false;

Definition at line 144 of file IceRevisitedRadix.cpp.

#define CHECK_RESIZE

(

n

)

Value:

if(n!=mPreviousSize)                                                                                                                                    \
        {                                                                                                                                                                               \
                                if(n>mCurrentSize)      Resize(n);                                                                                              \
                else                                            ResetRanks();                                                                                   \
                mPreviousSize = n;                                                                                                                                      \
        }

Definition at line 61 of file IceRevisitedRadix.cpp.

#define CREATE_HISTOGRAMS	(		type,
			buffer
	)

Definition at line 69 of file IceRevisitedRadix.cpp.

#define CURRENT_SIZE   (mCurrentSize&0x7fffffff)

Definition at line 58 of file IceRevisitedRadix.cpp.

#define INVALID_RANKS   (mCurrentSize&0x80000000)

Definition at line 59 of file IceRevisitedRadix.cpp.

#define INVALIDATE_RANKS   mCurrentSize|=0x80000000

Definition at line 56 of file IceRevisitedRadix.cpp.

#define VALIDATE_RANKS   mCurrentSize&=0x7fffffff

Definition at line 57 of file IceRevisitedRadix.cpp.