|
1
|
1 #include "pfc-lite.h"
|
|
|
2 #include "sort.h"
|
|
|
3 #include "sort2.h"
|
|
|
4 #include "bit_array_impl.h"
|
|
|
5 #include "ref_counter.h"
|
|
|
6
|
|
|
7 #if defined(_M_IX86) || defined(_M_IX64)
|
|
|
8 #include <intrin.h>
|
|
|
9 #define PFC_HAVE_RDTSC
|
|
|
10 #endif
|
|
|
11
|
|
|
12 namespace pfc {
|
|
|
13
|
|
|
14 void swap_void(void * item1,void * item2,t_size width)
|
|
|
15 {
|
|
|
16 unsigned char * ptr1 = (unsigned char*)item1, * ptr2 = (unsigned char*)item2;
|
|
|
17 t_size n;
|
|
|
18 unsigned char temp;
|
|
|
19 for(n=0;n<width;n++)
|
|
|
20 {
|
|
|
21 temp = *ptr2;
|
|
|
22 *ptr2 = *ptr1;
|
|
|
23 *ptr1 = temp;
|
|
|
24 ptr1++;
|
|
|
25 ptr2++;
|
|
|
26 }
|
|
|
27 }
|
|
|
28
|
|
|
29 void reorder(reorder_callback & p_callback,const t_size * p_order,t_size p_count)
|
|
|
30 {
|
|
|
31 t_size done_size = bit_array_bittable::g_estimate_size(p_count);
|
|
|
32 pfc::array_hybrid_t<unsigned char,1024> done;
|
|
|
33 done.set_size(done_size);
|
|
|
34 pfc::memset_t(done,(unsigned char)0);
|
|
|
35 t_size n;
|
|
|
36 for(n=0;n<p_count;n++)
|
|
|
37 {
|
|
|
38 t_size next = p_order[n];
|
|
|
39 if (next!=n && !bit_array_bittable::g_get(done,n))
|
|
|
40 {
|
|
|
41 t_size prev = n;
|
|
|
42 do
|
|
|
43 {
|
|
|
44 PFC_ASSERT(!bit_array_bittable::g_get(done,next));
|
|
|
45 PFC_ASSERT(next>n);
|
|
|
46 PFC_ASSERT(n<p_count);
|
|
|
47 p_callback.swap(prev,next);
|
|
|
48 bit_array_bittable::g_set(done,next,true);
|
|
|
49 prev = next;
|
|
|
50 next = p_order[next];
|
|
|
51 } while(next!=n);
|
|
|
52 //bit_array_bittable::g_set(done,n,true);
|
|
|
53 }
|
|
|
54 }
|
|
|
55 }
|
|
|
56
|
|
|
57 void reorder_void(void * data,t_size width,const t_size * order,t_size num,void (*swapfunc)(void * item1,void * item2,t_size width))
|
|
|
58 {
|
|
|
59 unsigned char * base = (unsigned char *) data;
|
|
|
60 t_size done_size = bit_array_bittable::g_estimate_size(num);
|
|
|
61 pfc::array_hybrid_t<unsigned char,1024> done;
|
|
|
62 done.set_size(done_size);
|
|
|
63 pfc::memset_t(done,(unsigned char)0);
|
|
|
64 t_size n;
|
|
|
65 for(n=0;n<num;n++)
|
|
|
66 {
|
|
|
67 t_size next = order[n];
|
|
|
68 if (next!=n && !bit_array_bittable::g_get(done,n))
|
|
|
69 {
|
|
|
70 t_size prev = n;
|
|
|
71 do
|
|
|
72 {
|
|
|
73 PFC_ASSERT(!bit_array_bittable::g_get(done,next));
|
|
|
74 PFC_ASSERT(next>n);
|
|
|
75 PFC_ASSERT(n<num);
|
|
|
76 swapfunc(base+width*prev,base+width*next,width);
|
|
|
77 bit_array_bittable::g_set(done,next,true);
|
|
|
78 prev = next;
|
|
|
79 next = order[next];
|
|
|
80 } while(next!=n);
|
|
|
81 //bit_array_bittable::g_set(done,n,true);
|
|
|
82 }
|
|
|
83 }
|
|
|
84 }
|
|
|
85
|
|
|
86 namespace {
|
|
|
87
|
|
|
88 class sort_callback_impl_legacy : public sort_callback
|
|
|
89 {
|
|
|
90 public:
|
|
|
91 sort_callback_impl_legacy(
|
|
|
92 void * p_base,t_size p_width,
|
|
|
93 int (*p_comp)(const void *, const void *),
|
|
|
94 void (*p_swap)(void *, void *, t_size)
|
|
|
95 ) :
|
|
|
96 m_base((char*)p_base), m_width(p_width),
|
|
|
97 m_comp(p_comp), m_swap(p_swap)
|
|
|
98 {
|
|
|
99 }
|
|
|
100
|
|
|
101
|
|
|
102 int compare(t_size p_index1, t_size p_index2) const
|
|
|
103 {
|
|
|
104 return m_comp(m_base + p_index1 * m_width, m_base + p_index2 * m_width);
|
|
|
105 }
|
|
|
106
|
|
|
107 void swap(t_size p_index1, t_size p_index2)
|
|
|
108 {
|
|
|
109 m_swap(m_base + p_index1 * m_width, m_base + p_index2 * m_width, m_width);
|
|
|
110 }
|
|
|
111
|
|
|
112 private:
|
|
|
113 char * m_base;
|
|
|
114 t_size m_width;
|
|
|
115 int (*m_comp)(const void *, const void *);
|
|
|
116 void (*m_swap)(void *, void *, t_size);
|
|
|
117 };
|
|
|
118 }
|
|
|
119
|
|
|
120 void sort_void_ex (
|
|
|
121 void *base,
|
|
|
122 t_size num,
|
|
|
123 t_size width,
|
|
|
124 int (*comp)(const void *, const void *),
|
|
|
125 void (*swap)(void *, void *, t_size) )
|
|
|
126 {
|
|
|
127 sort_callback_impl_legacy cb(base,width,comp,swap);
|
|
|
128 sort(cb,num);
|
|
|
129 }
|
|
|
130
|
|
|
131 static void squaresort(pfc::sort_callback & p_callback,t_size const p_base,t_size const p_count) {
|
|
|
132 const t_size max = p_base + p_count;
|
|
|
133 for(t_size walk = p_base + 1; walk < max; ++walk) {
|
|
|
134 for(t_size prev = p_base; prev < walk; ++prev) {
|
|
|
135 p_callback.swap_check(prev,walk);
|
|
|
136 }
|
|
|
137 }
|
|
|
138 }
|
|
|
139
|
|
|
140
|
|
|
141 inline static void __sort_2elem_helper(pfc::sort_callback & p_callback,t_size & p_elem1,t_size & p_elem2) {
|
|
|
142 if (p_callback.compare(p_elem1,p_elem2) > 0) pfc::swap_t(p_elem1,p_elem2);
|
|
|
143 }
|
|
|
144
|
|
|
145
|
|
|
146 #ifdef PFC_HAVE_RDTSC
|
|
|
147 static inline t_uint64 uniqueVal() {return __rdtsc();}
|
|
|
148 #else
|
|
|
149 static counter uniqueValCounter;
|
|
|
150 static counter::t_val uniqueVal() {
|
|
|
151 return ++uniqueValCounter;
|
|
|
152 }
|
|
|
153 #endif
|
|
|
154
|
|
|
155 static t_size myrand(t_size count) {
|
|
|
156 const uint64_t rm = (uint64_t)RAND_MAX + 1;
|
|
|
157 uint64_t m = 1;
|
|
|
158 uint64_t v = 0;
|
|
|
159 for(;;) {
|
|
|
160 v += rand() * m;
|
|
|
161 m *= rm;
|
|
|
162 if (m >= count) break;
|
|
|
163 }
|
|
|
164 v ^= uniqueVal();
|
|
|
165 return (t_size)(v % count);
|
|
|
166 }
|
|
|
167
|
|
|
168 inline static t_size __pivot_helper(pfc::sort_callback & p_callback,t_size const p_base,t_size const p_count) {
|
|
|
169 PFC_ASSERT(p_count > 2);
|
|
|
170
|
|
|
171 //t_size val1 = p_base, val2 = p_base + (p_count / 2), val3 = p_base + (p_count - 1);
|
|
|
172
|
|
|
173 t_size val1 = myrand(p_count), val2 = myrand(p_count-1), val3 = myrand(p_count-2);
|
|
|
174 if (val2 >= val1) val2++;
|
|
|
175 if (val3 >= val1) val3++;
|
|
|
176 if (val3 >= val2) val3++;
|
|
|
177
|
|
|
178 val1 += p_base; val2 += p_base; val3 += p_base;
|
|
|
179
|
|
|
180 __sort_2elem_helper(p_callback,val1,val2);
|
|
|
181 __sort_2elem_helper(p_callback,val1,val3);
|
|
|
182 __sort_2elem_helper(p_callback,val2,val3);
|
|
|
183
|
|
|
184 return val2;
|
|
|
185 }
|
|
|
186
|
|
|
187 static void newsort(pfc::sort_callback & p_callback,t_size const p_base,t_size const p_count) {
|
|
|
188 if (p_count <= 4) {
|
|
|
189 squaresort(p_callback,p_base,p_count);
|
|
|
190 return;
|
|
|
191 }
|
|
|
192
|
|
|
193 t_size pivot = __pivot_helper(p_callback,p_base,p_count);
|
|
|
194
|
|
|
195 {
|
|
|
196 const t_size target = p_base + p_count - 1;
|
|
|
197 if (pivot != target) {
|
|
|
198 p_callback.swap(pivot,target); pivot = target;
|
|
|
199 }
|
|
|
200 }
|
|
|
201
|
|
|
202
|
|
|
203 t_size partition = p_base;
|
|
|
204 {
|
|
|
205 bool asdf = false;
|
|
|
206 for(t_size walk = p_base; walk < pivot; ++walk) {
|
|
|
207 const int comp = p_callback.compare(walk,pivot);
|
|
|
208 bool trigger = false;
|
|
|
209 if (comp == 0) {
|
|
|
210 trigger = asdf;
|
|
|
211 asdf = !asdf;
|
|
|
212 } else if (comp < 0) {
|
|
|
213 trigger = true;
|
|
|
214 }
|
|
|
215 if (trigger) {
|
|
|
216 if (partition != walk) p_callback.swap(partition,walk);
|
|
|
217 partition++;
|
|
|
218 }
|
|
|
219 }
|
|
|
220 }
|
|
|
221 if (pivot != partition) {
|
|
|
222 p_callback.swap(pivot,partition); pivot = partition;
|
|
|
223 }
|
|
|
224
|
|
|
225 newsort(p_callback,p_base,pivot-p_base);
|
|
|
226 newsort(p_callback,pivot+1,p_count-(pivot+1-p_base));
|
|
|
227 }
|
|
|
228
|
|
|
229 void sort(pfc::sort_callback & p_callback,t_size p_num) {
|
|
|
230 srand((unsigned int)(uniqueVal() ^ p_num));
|
|
|
231 newsort(p_callback,0,p_num);
|
|
|
232 }
|
|
|
233
|
|
|
234
|
|
|
235 void sort_void(void * base,t_size num,t_size width,int (*comp)(const void *, const void *) )
|
|
|
236 {
|
|
|
237 sort_void_ex(base,num,width,comp,swap_void);
|
|
|
238 }
|
|
|
239
|
|
|
240
|
|
|
241
|
|
|
242
|
|
|
243 sort_callback_stabilizer::sort_callback_stabilizer(sort_callback & p_chain,t_size p_count)
|
|
|
244 : m_chain(p_chain)
|
|
|
245 {
|
|
|
246 m_order.set_size(p_count);
|
|
|
247 t_size n;
|
|
|
248 for(n=0;n<p_count;n++) m_order[n] = n;
|
|
|
249 }
|
|
|
250
|
|
|
251 int sort_callback_stabilizer::compare(t_size p_index1, t_size p_index2) const
|
|
|
252 {
|
|
|
253 int ret = m_chain.compare(p_index1,p_index2);
|
|
|
254 if (ret == 0) ret = pfc::sgn_t((t_ssize)m_order[p_index1] - (t_ssize)m_order[p_index2]);
|
|
|
255 return ret;
|
|
|
256 }
|
|
|
257
|
|
|
258 void sort_callback_stabilizer::swap(t_size p_index1, t_size p_index2)
|
|
|
259 {
|
|
|
260 m_chain.swap(p_index1,p_index2);
|
|
|
261 pfc::swap_t(m_order[p_index1],m_order[p_index2]);
|
|
|
262 }
|
|
|
263
|
|
|
264
|
|
|
265 void sort_stable(sort_callback & p_callback,t_size p_count)
|
|
|
266 {
|
|
|
267 sort_callback_stabilizer cb(p_callback,p_count);
|
|
|
268 sort(cb,p_count);
|
|
|
269 }
|
|
|
270
|
|
|
271
|
|
|
272
|
|
|
273 permutation_t make_identitiy(size_t count) {
|
|
|
274 permutation_t ret; ret.set_size_discard(count);
|
|
|
275 for (size_t walk = 0; walk < count; ++walk) {
|
|
|
276 ret[walk] = walk;
|
|
|
277 }
|
|
|
278 return ret;
|
|
|
279 }
|
|
|
280
|
|
|
281 }
|
|
|
282
|
