Debian Codegraph @

gcc/testsuite/gcc.target/avr/torture/lra-pr116325.c

raw
1 typedef __SIZE_TYPE__ size_t;
2 typedef __UINT8_TYPE__ uint8_t;
3
4 void swapfunc (char *a, char *b, int n)
5 {
6 do
7 {
8 char t = *a;
9 *a++ = *b;
10 *b++ = t;
11 } while (--n > 0);
12 }
13
14
15 typedef int cmp_t (const void*, const void*);
16
17 #define min(a, b) ((a) < (b) ? (a) : (b))
18
19 #define swap(a, b) \
20 swapfunc (a, b, es)
21
22 #define vecswap(a, b, n) \
23 if ((n) > 0) swapfunc (a, b, n)
24
25 static char*
26 med3 (char *a, char *b, char *c, cmp_t *cmp)
27 {
28 return cmp (a, b) < 0
29 ? (cmp (b, c) < 0 ? b : (cmp (a, c) < 0 ? c : a ))
30 : (cmp (b, c) > 0 ? b : (cmp (a, c) < 0 ? a : c ));
31 }
32
33 void
34 qsort (void *a, size_t n, size_t es, cmp_t *cmp)
35 {
36 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
37 int d, r, swap_cnt;
38
39 loop:
40 swap_cnt = 0;
41 if (n < 7)
42 {
43 for (pm = (char*) a + es; pm < (char*) a + n * es; pm += es)
44 for (pl = pm; pl > (char*) a && cmp (pl - es, pl) > 0; pl -= es)
45 swap (pl, pl - es);
46 return;
47 }
48 pm = (char*) a + (n / 2) * es;
49 if (n > 7)
50 {
51 pl = a;
52 pn = (char*) a + (n - 1) * es;
53 if (n > 40)
54 {
55 d = (n / 8) * es;
56 pl = med3 (pl, pl + d, pl + 2 * d, cmp);
57 pm = med3 (pm - d, pm, pm + d, cmp);
58 pn = med3 (pn - 2 * d, pn - d, pn, cmp);
59 }
60 pm = med3 (pl, pm, pn, cmp);
61 }
62 swap (a, pm);
63 pa = pb = (char*) a + es;
64
65 pc = pd = (char*) a + (n - 1) * es;
66 for (;;)
67 {
68 while (pb <= pc && (r = cmp (pb, a)) <= 0)
69 {
70 if (r == 0)
71 {
72 swap_cnt = 1;
73 swap (pa, pb);
74 pa += es;
75 }
76 pb += es;
77 }
78 while (pb <= pc && (r = cmp (pc, a)) >= 0)
79 {
80 if (r == 0)
81 {
82 swap_cnt = 1;
83 swap (pc, pd);
84 pd -= es;
85 }
86 pc -= es;
87 }
88 if (pb > pc)
89 break;
90 swap (pb, pc);
91 swap_cnt = 1;
92 pb += es;
93 pc -= es;
94 }
95 if (swap_cnt == 0)
96 {
97 for (pm = (char*) a + es; pm < (char*) a + n * es; pm += es)
98 for (pl = pm; pl > (char*) a && cmp (pl - es, pl) > 0; pl -= es)
99 swap (pl, pl - es);
100 return;
101 }
102
103 pn = (char*) a + n * es;
104 r = min (pa - (char*) a, pb - pa);
105 vecswap (a, pb - r, r);
106 r = min (pd - pc, (int) (pn - pd - es));
107 vecswap (pb, pn - r, r);
108 if ((r = pb - pa) > (int) es)
109 qsort(a, r / es, es, cmp);
110 if ((r = pd - pc) > (int) es)
111 {
112 /* Iterate rather than recurse to save stack space */
113 a = pn - r;
114 n = r / es;
115 goto loop;
116 }
117 }