PandA-2024.02
qsort.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 
31 static inline int pntz(size_t p[2]) {
32  int r = ntz(p[0] - 1);
33  if(r != 0 || (r = 8*sizeof(size_t) + ntz(p[1])) != 8*sizeof(size_t)) {
34  return r;
35  }
36  return 0;
37 }
38 
39 static void cycle(size_t width, unsigned char* ar[], int n)
40 {
41  unsigned char tmp[256];
42  size_t l;
43  int i;
44 
45  if(n < 2) {
46  return;
47  }
48 
49  ar[n] = tmp;
50  while(width) {
51  l = sizeof(tmp) < width ? sizeof(tmp) : width;
52  memcpy(ar[n], ar[0], l);
53  for(i = 0; i < n; i++) {
54  memcpy(ar[i], ar[i + 1], l);
55  ar[i] += l;
56  }
57  width -= l;
58  }
59 }
60 
61 /* shl() and shr() need n > 0 */
62 static inline void shl(size_t p[2], int n)
63 {
64  if(n >= 8 * sizeof(size_t)) {
65  n -= 8 * sizeof(size_t);
66  p[1] = p[0];
67  p[0] = 0;
68  }
69  p[1] <<= n;
70  p[1] |= p[0] >> (sizeof(size_t) * 8 - n);
71  p[0] <<= n;
72 }
73 
74 static inline void shr(size_t p[2], int n)
75 {
76  if(n >= 8 * sizeof(size_t)) {
77  n -= 8 * sizeof(size_t);
78  p[0] = p[1];
79  p[1] = 0;
80  }
81  p[0] >>= n;
82  p[0] |= p[1] << (sizeof(size_t) * 8 - n);
83  p[1] >>= n;
84 }
85 
86 static void sift(unsigned char *head, size_t width, int (*cmp)(const void *, const void *), int pshift, size_t lp[])
87 {
88  unsigned char *rt, *lf;
89  unsigned char *ar[14 * sizeof(size_t) + 1];
90  int i = 1;
91 
92  ar[0] = head;
93  while(pshift > 1) {
94  rt = head - width;
95  lf = head - width - lp[pshift - 2];
96 
97  if((*cmp)(ar[0], lf) >= 0 && (*cmp)(ar[0], rt) >= 0) {
98  break;
99  }
100  if((*cmp)(lf, rt) >= 0) {
101  ar[i++] = lf;
102  head = lf;
103  pshift -= 1;
104  } else {
105  ar[i++] = rt;
106  head = rt;
107  pshift -= 2;
108  }
109  }
110  cycle(width, ar, i);
111 }
112 
113 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[])
114 {
115  unsigned char *stepson,
116  *rt, *lf;
117  size_t p[2];
118  unsigned char *ar[14 * sizeof(size_t) + 1];
119  int i = 1;
120  int trail;
121 
122  p[0] = pp[0];
123  p[1] = pp[1];
124 
125  ar[0] = head;
126  while(p[0] != 1 || p[1] != 0) {
127  stepson = head - lp[pshift];
128  if((*cmp)(stepson, ar[0]) <= 0) {
129  break;
130  }
131  if(!trusty && pshift > 1) {
132  rt = head - width;
133  lf = head - width - lp[pshift - 2];
134  if((*cmp)(rt, stepson) >= 0 || (*cmp)(lf, stepson) >= 0) {
135  break;
136  }
137  }
138 
139  ar[i++] = stepson;
140  head = stepson;
141  trail = pntz(p);
142  shr(p, trail);
143  pshift += trail;
144  trusty = 0;
145  }
146  if(!trusty) {
147  cycle(width, ar, i);
148  sift(head, width, cmp, pshift, lp);
149  }
150 }
151 
152 void qsort(void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
153 {
154  size_t lp[12*sizeof(size_t)];
155  size_t i, size = width * nel;
156  unsigned char *head, *high;
157  size_t p[2] = {1, 0};
158  int pshift = 1;
159  int trail;
160 
161  if (!size) return;
162 
163  head = base;
164  high = head + size - width;
165 
166  /* Precompute Leonardo numbers, scaled by element width */
167  for(lp[0]=lp[1]=width, i=2; (lp[i]=lp[i-2]+lp[i-1]+width) < size; i++);
168 
169  while(head < high) {
170  if((p[0] & 3) == 3) {
171  sift(head, width, cmp, pshift, lp);
172  shr(p, 2);
173  pshift += 2;
174  } else {
175  if(lp[pshift - 1] >= high - head) {
176  trinkle(head, width, cmp, p, pshift, 0, lp);
177  } else {
178  sift(head, width, cmp, pshift, lp);
179  }
180 
181  if(pshift == 1) {
182  shl(p, 1);
183  pshift = 0;
184  } else {
185  shl(p, pshift - 1);
186  pshift = 1;
187  }
188  }
189 
190  p[0] |= 1;
191  head += width;
192  }
193 
194  trinkle(head, width, cmp, p, pshift, 0, lp);
195 
196  while(pshift != 1 || p[0] != 1 || p[1] != 0) {
197  if(pshift <= 1) {
198  trail = pntz(p);
199  shr(p, trail);
200  pshift += trail;
201  } else {
202  shl(p, 2);
203  pshift -= 2;
204  p[0] ^= 7;
205  shr(p, 1);
206  trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp);
207  shl(p, 1);
208  p[0] |= 1;
209  trinkle(head - width, width, cmp, p, pshift, 1, lp);
210  }
211  head -= width;
212  }
213 }
static void shl(size_t p[2], int n)
Definition: qsort.c:62
char base
This version is stamped on May 10, 2016.
Definition: nussinov.c:24
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[])
Definition: qsort.c:113
void qsort(void *base, size_t nel, size_t width, int(*cmp)(const void *, const void *))
Definition: qsort.c:152
#define ntz(x)
Definition: qsort.c:27
static int pntz(size_t p[2])
Definition: qsort.c:31
static void shr(size_t p[2], int n)
Definition: qsort.c:74
static void cycle(size_t width, unsigned char *ar[], int n)
Definition: qsort.c:39
int(* cmpfun)(const void *, const void *)
Definition: qsort.c:29
static void sift(unsigned char *head, size_t width, int(*cmp)(const void *, const void *), int pshift, size_t lp[])
Definition: qsort.c:86
unsigned int size_t
Definition: qsort.c:24

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