27 #define ntz(x) a_ctz_l((x)) 29 typedef int (*
cmpfun)(
const void *,
const void *);
30 int less (
const void * a,
const void * b);
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)) {
40 static void cycle(
size_t width,
unsigned char* ar[],
int n)
42 unsigned char tmp[256];
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);
63 static inline void shl(
size_t p[2],
int n)
65 if(n >= 8 *
sizeof(
size_t)) {
71 p[1] |= p[0] >> (
sizeof(
size_t) * 8 - n);
75 static inline void shr(
size_t p[2],
int n)
77 if(n >= 8 *
sizeof(
size_t)) {
83 p[0] |= p[1] << (
sizeof(
size_t) * 8 - n);
87 static void sift(
unsigned char *head,
size_t width,
int (*cmp)(
const void *,
const void *),
int pshift,
size_t lp[])
89 unsigned char *rt, *lf;
90 unsigned char *ar[14 *
sizeof(
size_t) + 1];
96 lf = head - width - lp[pshift - 2];
98 if(
less(ar[0], lf) >= 0 &&
less(ar[0], rt) >= 0) {
101 if(
less(lf, rt) >= 0) {
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[])
116 unsigned char *stepson,
119 unsigned char *ar[14 *
sizeof(
size_t) + 1];
127 while(p[0] != 1 || p[1] != 0) {
128 stepson = head - lp[pshift];
129 if(
less(stepson, ar[0]) <= 0) {
132 if(!trusty && pshift > 1) {
134 lf = head - width - lp[pshift - 2];
135 if(
less(rt, stepson) >= 0 ||
less(lf, stepson) >= 0) {
149 sift(head, width, cmp, pshift, lp);
153 void qsort(
void *
base,
size_t nel,
size_t width,
int (*cmp)(
const void *,
const void *))
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};
165 high = head + size - width;
168 for(lp[0]=lp[1]=width, i=2; (lp[i]=lp[i-2]+lp[i-1]+width) < size; i++);
171 if((p[0] & 3) == 3) {
172 sift(head, width, cmp, pshift, lp);
176 if(lp[pshift - 1] >= high - head) {
177 trinkle(head, width, cmp, p, pshift, 0, lp);
179 sift(head, width, cmp, pshift, lp);
195 trinkle(head, width, cmp, p, pshift, 0, lp);
197 while(pshift != 1 || p[0] != 1 || p[1] != 0) {
207 trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp);
210 trinkle(head - width, width, cmp, p, pshift, 1, lp);
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 *))
char base
This version is stamped on May 10, 2016.
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 *)
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)