File Coverage

qsort-r.c
Criterion Covered Total %
statement 11 80 13.7
branch 12 100 12.0
condition n/a
subroutine n/a
pod n/a
total 23 180 12.7


line stmt bran cond sub pod time code
1             /*
2             qsort_r.c from freebsd source code, original file:
3              
4             https://www.leidinger.net/FreeBSD/dox/libkern/html/d7/da4/qsort_8c_source.html
5             */
6              
7              
8             typedef int json_create_cmp_t(void *, const void *, const void *);
9             static inline char *json_create_med3(char *, char *, char *, json_create_cmp_t *, void *);
10             static inline void json_create_swapfunc(char *, char *, size_t, int, int);
11              
12             #define json_create_swapcode(TYPE, parmi, parmj, n) { \
13             size_t i = (n) / sizeof (TYPE); \
14             TYPE *pi = (TYPE *) (parmi); \
15             TYPE *pj = (TYPE *) (parmj); \
16             do { \
17             TYPE t = *pi; \
18             *pi++ = *pj; \
19             *pj++ = t; \
20             } while (--i > 0); \
21             }
22              
23             #define JSON_CREATE_SWAPINIT(TYPE, a, es) swaptype_ ## TYPE = \
24             ((char *)a - (char *)0) % sizeof(TYPE) || \
25             es % sizeof(TYPE) ? 2 : es == sizeof(TYPE) ? 0 : 1;
26              
27             #define JSON_CREATE_MIN(a,b) (((a)<(b))?(a):(b))
28              
29             static inline void
30 0           json_create_swapfunc(char *a, char *b, size_t n, int swaptype_long, int swaptype_int)
31             {
32 0 0         if (swaptype_long <= 1)
33 0 0         json_create_swapcode(long, a, b, n)
34 0 0         else if (swaptype_int <= 1)
35 0 0         json_create_swapcode(int, a, b, n)
36             else
37 0 0         json_create_swapcode(char, a, b, n)
38 0           }
39              
40             #define json_create_swap(a, b) \
41             if (swaptype_long == 0) { \
42             long t = *(long *)(a); \
43             *(long *)(a) = *(long *)(b); \
44             *(long *)(b) = t; \
45             } else if (swaptype_int == 0) { \
46             int t = *(int *)(a); \
47             *(int *)(a) = *(int *)(b); \
48             *(int *)(b) = t; \
49             } else \
50             json_create_swapfunc(a, b, es, swaptype_long, swaptype_int)
51              
52             #define json_create_vecswap(a, b, n) \
53             if ((n) > 0) json_create_swapfunc(a, b, n, swaptype_long, swaptype_int)
54              
55             static inline char *
56 0           json_create_med3(char *a, char *b, char *c, json_create_cmp_t *cmp, void *thunk)
57             {
58 0           return cmp(thunk, a, b) < 0 ?
59 0 0         (cmp(thunk, b, c) < 0 ? b : (cmp(thunk, a, c) < 0 ? c : a ))
    0          
60 0 0         :(cmp(thunk, b, c) > 0 ? b : (cmp(thunk, a, c) < 0 ? a : c ));
    0          
    0          
61             }
62              
63             void
64 2           json_create_qsort_r(void *a, size_t n, size_t es, void *thunk, json_create_cmp_t *cmp)
65             {
66             char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
67             size_t d1, d2;
68             int cmp_result;
69             int swaptype_long, swaptype_int, swap_cnt;
70              
71 2 50         loop: JSON_CREATE_SWAPINIT(long, a, es);
    50          
72 2 50         JSON_CREATE_SWAPINIT(int, a, es);
    50          
73 2           swap_cnt = 0;
74 2 50         if (n < 7) {
75 7 100         for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
76 13 100         for (pl = pm;
77 10 100         pl > (char *)a && cmp(thunk, pl - es, pl) > 0;
78 8           pl -= es)
79 8 50         json_create_swap(pl, pl - es);
    0          
80 2           return;
81             }
82 0           pm = (char *)a + (n / 2) * es;
83 0 0         if (n > 7) {
84 0           pl = a;
85 0           pn = (char *)a + (n - 1) * es;
86 0 0         if (n > 40) {
87 0           size_t d = (n / 8) * es;
88              
89 0           pl = json_create_med3(pl, pl + d, pl + 2 * d, cmp, thunk);
90 0           pm = json_create_med3(pm - d, pm, pm + d, cmp, thunk);
91 0           pn = json_create_med3(pn - 2 * d, pn - d, pn, cmp, thunk);
92             }
93 0           pm = json_create_med3(pl, pm, pn, cmp, thunk);
94             }
95 0 0         json_create_swap(a, pm);
    0          
96 0           pa = pb = (char *)a + es;
97              
98 0           pc = pd = (char *)a + (n - 1) * es;
99             for (;;) {
100 0 0         while (pb <= pc && (cmp_result = cmp(thunk, pb, a)) <= 0) {
    0          
101 0 0         if (cmp_result == 0) {
102 0           swap_cnt = 1;
103 0 0         json_create_swap(pa, pb);
    0          
104 0           pa += es;
105             }
106 0           pb += es;
107             }
108 0 0         while (pb <= pc && (cmp_result = cmp(thunk, pc, a)) >= 0) {
    0          
109 0 0         if (cmp_result == 0) {
110 0           swap_cnt = 1;
111 0 0         json_create_swap(pc, pd);
    0          
112 0           pd -= es;
113             }
114 0           pc -= es;
115             }
116 0 0         if (pb > pc)
117 0           break;
118 0 0         json_create_swap(pb, pc);
    0          
119 0           swap_cnt = 1;
120 0           pb += es;
121 0           pc -= es;
122 0           }
123 0 0         if (swap_cnt == 0) { /* Switch to insertion sort */
124 0 0         for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
125 0 0         for (pl = pm;
126 0 0         pl > (char *)a && cmp(thunk, pl - es, pl) > 0;
127 0           pl -= es)
128 0 0         json_create_swap(pl, pl - es);
    0          
129 0           return;
130             }
131              
132 0           pn = (char *)a + n * es;
133 0           d1 = JSON_CREATE_MIN(pa - (char *)a, pb - pa);
134 0 0         json_create_vecswap(a, pb - d1, d1);
135 0           d1 = JSON_CREATE_MIN(pd - pc, pn - pd - es);
136 0 0         json_create_vecswap(pb, pn - d1, d1);
137              
138 0           d1 = pb - pa;
139 0           d2 = pd - pc;
140 0 0         if (d1 <= d2) {
141             /* Recurse on left partition, then iterate on right partition */
142 0 0         if (d1 > es) {
143 0           json_create_qsort_r(a, d1 / es, es, thunk, cmp);
144             }
145 0 0         if (d2 > es) {
146             /* Iterate rather than recurse to save stack space */
147             /* qsort(pn - d2, d2 / es, es, cmp); */
148 0           a = pn - d2;
149 0           n = d2 / es;
150 0           goto loop;
151             }
152             } else {
153             /* Recurse on right partition, then iterate on left partition */
154 0 0         if (d2 > es) {
155 0           json_create_qsort_r(pn - d2, d2 / es, es, thunk, cmp);
156             }
157 0 0         if (d1 > es) {
158             /* Iterate rather than recurse to save stack space */
159             /* qsort(a, d1 / es, es, cmp); */
160 0           n = d1 / es;
161 0           goto loop;
162             }
163             }
164             }
165              
166             #undef JSON_CREATE_MIN
167             #undef json_create_swap
168             #undef json_create_swapcode
169             #undef JSON_CREATE_SWAPINIT
170             #undef json_create_vecswap