PandA-2024.02
qsort-specialized.c
Go to the documentation of this file.
1 /* Copyright (C) 2011 by Valentin Ochs
2  *
3  * Permission is hereby granted, free of charge, to any person obtaining a copy
4  * of this software and associated documentation files (the "Software"), to
5  * deal in the Software without restriction, including without limitation the
6  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
7  * sell copies of the Software, and to permit persons to whom the Software is
8  * furnished to do so, subject to the following conditions:
9  *
10  * The above copyright notice and this permission notice shall be included in
11  * all copies or substantial portions of the Software.
12  *
13  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
18  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
19  * IN THE SOFTWARE.
20  */
21 
22 /* Minor changes by Rich Felker for integration in musl, 2011-04-27. */
23 
24 typedef unsigned int size_t;
25 
26 #include "atomic.h"
27 #define ntz(x) a_ctz_l((x))
28 
29 typedef int (*cmpfun)(const void *, const void *);
30 int less (const void * a, const void * b);
31 
32 static inline int pntz(size_t p[2]) {
33  int r = ntz(p[0] - 1);
34  if(r != 0 || (r = 8*sizeof(size_t) + ntz(p[1])) != 8*sizeof(size_t)) {
35  return r;
36  }
37  return 0;
38 }
39 
40 static void cycle(size_t width, unsigned char* ar[], int n)
41 {
42  unsigned char tmp[256];
43  size_t l;
44  int i;
45 
46  if(n < 2) {
47  return;
48  }
49 
50  ar[n] = tmp;
51  while(width) {
52  l = sizeof(tmp) < width ? sizeof(tmp) : width;
53  memcpy(ar[n], ar[0], l);
54  for(i = 0; i < n; i++) {
55  memcpy(ar[i], ar[i + 1], l);
56  ar[i] += l;
57  }
58  width -= l;
59  }
60 }
61 
62 /* shl() and shr() need n > 0 */
63 static inline void shl(size_t p[2], int n)
64 {
65  if(n >= 8 * sizeof(size_t)) {
66  n -= 8 * sizeof(size_t);
67  p[1] = p[0];
68  p[0] = 0;
69  }
70  p[1] <<= n;
71  p[1] |= p[0] >> (sizeof(size_t) * 8 - n);
72  p[0] <<= n;
73 }
74 
75 static inline void shr(size_t p[2], int n)
76 {
77  if(n >= 8 * sizeof(size_t)) {
78  n -= 8 * sizeof(size_t);
79  p[0] = p[1];
80  p[1] = 0;
81  }
82  p[0] >>= n;
83  p[0] |= p[1] << (sizeof(size_t) * 8 - n);
84  p[1] >>= n;
85 }
86 
87 static void sift(unsigned char *head, size_t width, int (*cmp)(const void *, const void *), int pshift, size_t lp[])
88 {
89  unsigned char *rt, *lf;
90  unsigned char *ar[14 * sizeof(size_t) + 1];
91  int i = 1;
92 
93  ar[0] = head;
94  while(pshift > 1) {
95  rt = head - width;
96  lf = head - width - lp[pshift - 2];
97 
98  if(less(ar[0], lf) >= 0 && less(ar[0], rt) >= 0) {
99  break;
100  }
101  if(less(lf, rt) >= 0) {
102  ar[i++] = lf;
103  head = lf;
104  pshift -= 1;
105  } else {
106  ar[i++] = rt;
107  head = rt;
108  pshift -= 2;
109  }
110  }
111  cycle(width, ar, i);
112 }
113 
114 static void trinkle(unsigned char *head, size_t width, int (*cmp)(const void *, const void *), size_t pp[2], int pshift, int trusty, size_t lp[])
115 {
116  unsigned char *stepson,
117  *rt, *lf;
118  size_t p[2];
119  unsigned char *ar[14 * sizeof(size_t) + 1];
120  int i = 1;
121  int trail;
122 
123  p[0] = pp[0];
124  p[1] = pp[1];
125 
126  ar[0] = head;
127  while(p[0] != 1 || p[1] != 0) {
128  stepson = head - lp[pshift];
129  if(less(stepson, ar[0]) <= 0) {
130  break;
131  }
132  if(!trusty && pshift > 1) {
133  rt = head - width;
134  lf = head - width - lp[pshift - 2];
135  if(less(rt, stepson) >= 0 || less(lf, stepson) >= 0) {
136  break;
137  }
138  }
139 
140  ar[i++] = stepson;
141  head = stepson;
142  trail = pntz(p);
143  shr(p, trail);
144  pshift += trail;
145  trusty = 0;
146  }
147  if(!trusty) {
148  cycle(width, ar, i);
149  sift(head, width, cmp, pshift, lp);
150  }
151 }
152 
153 void qsort(void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
154 {
155  size_t lp[12*sizeof(size_t)];
156  size_t i, size = width * nel;
157  unsigned char *head, *high;
158  size_t p[2] = {1, 0};
159  int pshift = 1;
160  int trail;
161 
162  if (!size) return;
163 
164  head = base;
165  high = head + size - width;
166 
167  /* Precompute Leonardo numbers, scaled by element width */
168  for(lp[0]=lp[1]=width, i=2; (lp[i]=lp[i-2]+lp[i-1]+width) < size; i++);
169 
170  while(head < high) {
171  if((p[0] & 3) == 3) {
172  sift(head, width, cmp, pshift, lp);
173  shr(p, 2);
174  pshift += 2;
175  } else {
176  if(lp[pshift - 1] >= high - head) {
177  trinkle(head, width, cmp, p, pshift, 0, lp);
178  } else {
179  sift(head, width, cmp, pshift, lp);
180  }
181 
182  if(pshift == 1) {
183  shl(p, 1);
184  pshift = 0;
185  } else {
186  shl(p, pshift - 1);
187  pshift = 1;
188  }
189  }
190 
191  p[0] |= 1;
192  head += width;
193  }
194 
195  trinkle(head, width, cmp, p, pshift, 0, lp);
196 
197  while(pshift != 1 || p[0] != 1 || p[1] != 0) {
198  if(pshift <= 1) {
199  trail = pntz(p);
200  shr(p, trail);
201  pshift += trail;
202  } else {
203  shl(p, 2);
204  pshift -= 2;
205  p[0] ^= 7;
206  shr(p, 1);
207  trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp);
208  shl(p, 1);
209  p[0] |= 1;
210  trinkle(head - width, width, cmp, p, pshift, 1, lp);
211  }
212  head -= width;
213  }
214 }
static void sift(unsigned char *head, size_t width, int(*cmp)(const void *, const void *), int pshift, size_t lp[])
void qsort(void *base, size_t nel, size_t width, int(*cmp)(const void *, const void *))
unsigned int size_t
char base
This version is stamped on May 10, 2016.
Definition: nussinov.c:24
static void cycle(size_t width, unsigned char *ar[], int n)
static void shl(size_t p[2], int n)
int less(const void *, const void *, void *)
Definition: less.c:4
#define ntz(x)
static int pntz(size_t p[2])
int(* cmpfun)(const void *, const void *)
static void trinkle(unsigned char *head, size_t width, int(*cmp)(const void *, const void *), size_t pp[2], int pshift, int trusty, size_t lp[])
static void shr(size_t p[2], int n)

Generated on Mon Feb 12 2024 13:02:49 for PandA-2024.02 by doxygen 1.8.13