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