This source file includes following definitions.
- mpsort_into_tmp
- mpsort_with_tmp
- mpsort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 #include <config.h>
21
22 #include "mpsort.h"
23
24 #include <string.h>
25
26
27
28 typedef int (*comparison_function) (void const *, void const *);
29
30 static void mpsort_with_tmp (void const **restrict, size_t,
31 void const **restrict, comparison_function);
32
33
34
35
36 static void
37 mpsort_into_tmp (void const **restrict base, size_t n,
38 void const **restrict tmp,
39 comparison_function cmp)
40 {
41 size_t n1 = n / 2;
42 size_t n2 = n - n1;
43 size_t a = 0;
44 size_t alim = n1;
45 size_t b = n1;
46 size_t blim = n;
47 void const *ba;
48 void const *bb;
49
50 mpsort_with_tmp (base + n1, n2, tmp, cmp);
51 mpsort_with_tmp (base, n1, tmp, cmp);
52
53 ba = base[a];
54 bb = base[b];
55
56 for (;;)
57 if (cmp (ba, bb) <= 0)
58 {
59 *tmp++ = ba;
60 a++;
61 if (a == alim)
62 {
63 a = b;
64 alim = blim;
65 break;
66 }
67 ba = base[a];
68 }
69 else
70 {
71 *tmp++ = bb;
72 b++;
73 if (b == blim)
74 break;
75 bb = base[b];
76 }
77
78 memcpy (tmp, base + a, (alim - a) * sizeof *base);
79 }
80
81
82
83
84
85 static void
86 mpsort_with_tmp (void const **restrict base, size_t n,
87 void const **restrict tmp,
88 comparison_function cmp)
89 {
90 if (n <= 2)
91 {
92 if (n == 2)
93 {
94 void const *p0 = base[0];
95 void const *p1 = base[1];
96 if (! (cmp (p0, p1) <= 0))
97 {
98 base[0] = p1;
99 base[1] = p0;
100 }
101 }
102 }
103 else
104 {
105 size_t n1 = n / 2;
106 size_t n2 = n - n1;
107 size_t i;
108 size_t t = 0;
109 size_t tlim = n1;
110 size_t b = n1;
111 size_t blim = n;
112 void const *bb;
113 void const *tt;
114
115 mpsort_with_tmp (base + n1, n2, tmp, cmp);
116
117 if (n1 < 2)
118 tmp[0] = base[0];
119 else
120 mpsort_into_tmp (base, n1, tmp, cmp);
121
122 tt = tmp[t];
123 bb = base[b];
124
125 for (i = 0; ; )
126 if (cmp (tt, bb) <= 0)
127 {
128 base[i++] = tt;
129 t++;
130 if (t == tlim)
131 break;
132 tt = tmp[t];
133 }
134 else
135 {
136 base[i++] = bb;
137 b++;
138 if (b == blim)
139 {
140 memcpy (base + i, tmp + t, (tlim - t) * sizeof *base);
141 break;
142 }
143 bb = base[b];
144 }
145 }
146 }
147
148
149
150
151
152 void
153 mpsort (void const **base, size_t n, comparison_function cmp)
154 {
155 mpsort_with_tmp (base, n, base + n, cmp);
156 }