Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef __CSUTIL_RADIX_SORT_H__
00021 #define __CSUTIL_RADIX_SORT_H__
00022
00027 #include "csextern.h"
00028
00029
00030 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00031 # undef new
00032 #endif
00033 #include <new>
00034
00040 class CS_CRYSTALSPACE_EXPORT csRadixSorter
00041 {
00042 public:
00043 csRadixSorter();
00044 ~csRadixSorter();
00045
00051 void Sort(uint32* array, size_t size);
00052
00058 void Sort(int32* array, size_t size);
00059
00065 void Sort(float* array, size_t size);
00066
00070 inline size_t* GetRanks() const
00071 {
00072 return ranks1;
00073 }
00074
00078 template<class T>
00079 void ReorderInplace (T* source, size_t size)
00080 {
00081 if(size*sizeof(T) < 0x4000)
00082 {
00083
00084 CS_ALLOC_STACK_ARRAY(uint8, tmpStorage, size*sizeof(T));
00085 T* dest = (T*)tmpStorage;
00086 for(size_t i = 0; i < size; i++)
00087 {
00088 new (&dest[i]) T(source[ranks1[i]]);
00089 }
00090 for(size_t i = 0; i < size; i++)
00091 {
00092 source[i] = dest[i];
00093 dest[i].~T();
00094 }
00095 }
00096 else
00097 {
00098
00099 uint8* tmpStorage = (uint8*)cs_malloc(size*sizeof(T));
00100 T* dest = (T*)tmpStorage;
00101 for(size_t i = 0; i < size; i++)
00102 {
00103 new (&dest[i]) T(source[ranks1[i]]);
00104 }
00105 for(size_t i = 0; i < size; i++)
00106 {
00107 source[i] = dest[i];
00108 dest[i].~T();
00109 }
00110 cs_free(tmpStorage);
00111 }
00112 }
00113
00118 template<class T>
00119 bool Reorder(const T* source, T* dest, size_t size)
00120 {
00121
00122 #ifdef _DEBUG
00123 if((source + size - dest > 0 && dest - source < size) ||
00124 (dest + size - source > 0 && source - dest < size))
00125 return false;
00126 #endif
00127
00128 for(size_t i = 0; i < size; i++)
00129 {
00130 dest[i] = source[ranks1[i]];
00131 }
00132 return true;
00133 }
00134
00135 private:
00136
00137 void Resize(size_t size);
00138
00139
00140 template<class T>
00141 bool CreateHistogram(T* data, size_t size, uint32* histogram);
00142
00143
00144 template<class T>
00145 bool DoPass(size_t pass, T* data, size_t size, uint32* histogram);
00146
00147 size_t currentSize;
00148 size_t* ranks1;
00149 size_t* ranks2;
00150
00151 bool ranksValid;
00152 };
00153
00154 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00155 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00156 #endif
00157
00158 #endif