diff options
author | Aki <please@ignore.pl> | 2024-03-12 22:07:03 +0100 |
---|---|---|
committer | Aki <please@ignore.pl> | 2024-03-12 22:07:36 +0100 |
commit | 81bb6873f1c0291fecbf6e429ad15ac3db66a4c0 (patch) | |
tree | fd7552ecabeeffb45a1fbe3730ab62bc7a64dd85 /third-party/Opcode/Ice/IceRevisitedRadix.h | |
parent | f43d32d6d2cc7ecd04f4f06f20d5a6fc2c87c9ae (diff) | |
download | starshatter-81bb6873f1c0291fecbf6e429ad15ac3db66a4c0.zip starshatter-81bb6873f1c0291fecbf6e429ad15ac3db66a4c0.tar.gz starshatter-81bb6873f1c0291fecbf6e429ad15ac3db66a4c0.tar.bz2 |
Legal notices updated
Rename contrib -> third-party intendes to express the origin and purpose
of that part of the code better. I plan to readd contrib/ again but with
more in-project things like bash-completions, dev workflow scripts etc.
Diffstat (limited to 'third-party/Opcode/Ice/IceRevisitedRadix.h')
-rw-r--r-- | third-party/Opcode/Ice/IceRevisitedRadix.h | 65 |
1 files changed, 65 insertions, 0 deletions
diff --git a/third-party/Opcode/Ice/IceRevisitedRadix.h b/third-party/Opcode/Ice/IceRevisitedRadix.h new file mode 100644 index 0000000..3bdfc22 --- /dev/null +++ b/third-party/Opcode/Ice/IceRevisitedRadix.h @@ -0,0 +1,65 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +/** + * Contains source code from the article "Radix Sort Revisited". + * \file IceRevisitedRadix.h + * \author Pierre Terdiman + * \date April, 4, 2000 + */ +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Include Guard +#ifndef __ICERADIXSORT_H__ +#define __ICERADIXSORT_H__ + + //! Allocate histograms & offsets locally + #define RADIX_LOCAL_RAM + + enum RadixHint + { + RADIX_SIGNED, //!< Input values are signed + RADIX_UNSIGNED, //!< Input values are unsigned + + RADIX_FORCE_DWORD = 0x7fffffff + }; + + class ICECORE_API RadixSort + { + public: + // Constructor/Destructor + RadixSort(); + ~RadixSort(); + // Sorting methods + RadixSort& Sort(const udword* input, udword nb, RadixHint hint=RADIX_SIGNED); + RadixSort& Sort(const float* input, udword nb); + + //! Access to results. mRanks is a list of indices in sorted order, i.e. in the order you may further process your data + inline_ const udword* GetRanks() const { return mRanks; } + + //! mIndices2 gets trashed on calling the sort routine, but otherwise you can recycle it the way you want. + inline_ udword* GetRecyclable() const { return mRanks2; } + + // Stats + udword GetUsedRam() const; + //! Returns the total number of calls to the radix sorter. + inline_ udword GetNbTotalCalls() const { return mTotalCalls; } + //! Returns the number of eraly exits due to temporal coherence. + inline_ udword GetNbHits() const { return mNbHits; } + + private: +#ifndef RADIX_LOCAL_RAM + udword* mHistogram; //!< Counters for each byte + udword* mOffset; //!< Offsets (nearly a cumulative distribution function) +#endif + udword mCurrentSize; //!< Current size of the indices list + udword* mRanks; //!< Two lists, swapped each pass + udword* mRanks2; + // Stats + udword mTotalCalls; //!< Total number of calls to the sort routine + udword mNbHits; //!< Number of early exits due to coherence + // Internal methods + void CheckResize(udword nb); + bool Resize(udword nb); + }; + +#endif // __ICERADIXSORT_H__ |