Line data Source code
1 : /*
2 : Stable sort routines
3 :
4 : Copyright © Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
5 :
6 : ** NOTE! The following LGPL license applies to this file which is used by
7 : ** the ldb library. This does NOT imply that all of Samba is released
8 : ** under the LGPL.
9 :
10 : This library is free software; you can redistribute it and/or
11 : modify it under the terms of the GNU Lesser General Public
12 : License as published by the Free Software Foundation; either
13 : version 3 of the License, or (at your option) any later version.
14 :
15 : This library is distributed in the hope that it will be useful,
16 : but WITHOUT ANY WARRANTY; without even the implied warranty of
17 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 : Lesser General Public License for more details.
19 :
20 : You should have received a copy of the GNU Lesser General Public
21 : License along with this library; if not, see <http://www.gnu.org/licenses/>.
22 : */
23 :
24 : #include <stdint.h>
25 : #include <stdlib.h>
26 : #include <string.h>
27 : #include <unistd.h>
28 : #include <talloc.h>
29 : #include "replace.h"
30 : #include "stable_sort.h"
31 :
32 544883 : static void sort_few(char *array, char *aux,
33 : size_t n,
34 : size_t s,
35 : samba_compare_with_context_fn_t cmpfn,
36 : void *opaque)
37 : {
38 : /* a kind of insertion sort for small n. */
39 518996 : int i, j, dist;
40 518996 : int cmp;
41 518996 : char *a, *b;
42 :
43 3812550 : for (i = 1; i < n; i++) {
44 3267667 : a = &array[i * s];
45 : /* leftwards is sorted. look until we find this one's place */
46 7146919 : for (j = i - 1; j >= 0; j--) {
47 6608816 : b = &array[j * s];
48 6608816 : cmp = cmpfn(a, b, opaque);
49 6608816 : if (cmp >= 0) {
50 157977 : break;
51 : }
52 : }
53 3267667 : dist = i - 1 - j;
54 3267667 : if (dist == 0) {
55 : /* a is already in the right place */
56 1642109 : continue;
57 : }
58 :
59 1625558 : b = &array[(i - dist) * s];
60 1625558 : memcpy(aux, a, s);
61 1625558 : memmove(b + s, b, s * dist);
62 3122460 : memcpy(b, aux, s);
63 : }
64 544883 : }
65 :
66 :
67 540545 : static void merge(char *dest,
68 : char *a, size_t alen,
69 : char *b, size_t blen,
70 : size_t s,
71 : samba_compare_with_context_fn_t cmpfn,
72 : void *opaque)
73 : {
74 540545 : size_t ai = 0;
75 540545 : size_t bi = 0;
76 540545 : size_t di = 0;
77 55546012 : while (ai < alen && bi < blen) {
78 55005467 : int cmp = cmpfn(&a[ai * s], &b[bi * s], opaque);
79 55005467 : if (cmp <= 0) {
80 28747543 : memcpy(&dest[di * s], &a[ai * s], s);
81 28747543 : ai++;
82 : } else {
83 26257924 : memcpy(&dest[di * s], &b[bi * s], s);
84 26257924 : bi++;
85 : }
86 55005467 : di++;
87 : }
88 540545 : if (ai < alen) {
89 214567 : memcpy(&dest[di * s], &a[ai * s], s * (alen - ai));
90 325978 : } else if (bi < blen) {
91 325978 : memcpy(&dest[di * s], &b[bi * s], s * (blen - bi));
92 : }
93 540545 : }
94 :
95 :
96 4340 : bool stable_sort_r(void *array, void *aux,
97 : size_t n,
98 : size_t s,
99 : samba_compare_with_context_fn_t cmpfn,
100 : void * opaque)
101 : {
102 4340 : char *src = array, *dest = aux, *tmp = NULL;
103 2777 : size_t i, j, k;
104 2777 : size_t runsize;
105 4340 : if (array == NULL || aux == NULL) {
106 0 : return false;
107 : }
108 :
109 4339 : if (n < 20) {
110 1993 : sort_few(array, aux, n, s, cmpfn, opaque);
111 1993 : return true;
112 : }
113 :
114 2346 : if (n > SIZE_MAX / s) {
115 : /*
116 : * We will have an integer overflow if we continue.
117 : *
118 : * This means that the *supposed* size of the allocated buffer
119 : * is greater than SIZE_MAX, which is not possible in theory
120 : * or practice, and is a sign the caller has got very
121 : * confused.
122 : */
123 0 : return false;
124 : }
125 :
126 : /*
127 : * This is kind of a bottom-up merge sort.
128 : *
129 : * We start but sorting into a whole lot of little runs, using an
130 : * insertion sort which is efficient for small numbers. Empirically,
131 : * on 2 machines, a run size of around 8 seems optimal, but the peak
132 : * is wide, and it seems worth adapting the size to avoid an
133 : * unbalanced final merge at the top. That is, if we pick the right
134 : * runsize now, we will finish with a merge of roughly n/2:n/2, and
135 : * not have to follow that with an merge of roughly n:[a few], which
136 : * we would sometimes do with a fixed size at the lowest level.
137 : *
138 : * The aim is a runsize of n / (a power of 2) rounded up, in the
139 : * target range.
140 : */
141 :
142 834 : runsize = n;
143 13156 : while (runsize > 10) {
144 10811 : runsize++;
145 10811 : runsize >>= 1;
146 : }
147 :
148 545235 : for (i = 0; i < n; i += runsize) {
149 542890 : size_t nn = MIN(n - i, runsize);
150 542890 : sort_few(&src[i * s], aux, nn, s, cmpfn, opaque);
151 : }
152 :
153 13156 : while (runsize < n) {
154 551356 : for (i = 0; i < n; i += runsize * 2) {
155 542209 : j = i + runsize;
156 542209 : if (j >= n) {
157 : /*
158 : * first run doesn't fit, meaning this chunk
159 : * is already sorted. We just need to copy
160 : * it.
161 : */
162 1664 : size_t nn = n - i;
163 1664 : memcpy(&dest[i * s], &src[i * s], nn * s);
164 382 : break;
165 : }
166 540545 : k = j + runsize;
167 540545 : if (k > n) {
168 8777 : merge(&dest[i * s],
169 8777 : &src[i * s], runsize,
170 8777 : &src[j * s], n - j,
171 : s,
172 : cmpfn, opaque);
173 : } else {
174 531768 : merge(&dest[i * s],
175 531768 : &src[i * s], runsize,
176 531768 : &src[j * s], runsize,
177 : s,
178 : cmpfn, opaque);
179 : }
180 : }
181 :
182 10811 : tmp = src;
183 10811 : src = dest;
184 10811 : dest = tmp;
185 10811 : runsize *= 2;
186 : }
187 : /*
188 : * We have sorted the array into src, which is either array or aux.
189 : */
190 2345 : if (src != array) {
191 1399 : memcpy(array, src, n * s);
192 : }
193 834 : return true;
194 : }
195 :
196 :
197 :
198 : /*
199 : * A wrapper that allocates (and frees) the temporary buffer if necessary.
200 : *
201 : * returns false on allocation error, true otherwise.
202 : */
203 :
204 873 : bool stable_sort_talloc_r(TALLOC_CTX *mem_ctx,
205 : void *array,
206 : size_t n,
207 : size_t s,
208 : samba_compare_with_context_fn_t cmpfn,
209 : void *opaque)
210 : {
211 169 : bool ok;
212 873 : char *mem = talloc_array_size(mem_ctx, s, n);
213 873 : if (mem == NULL) {
214 0 : return false;
215 : }
216 873 : ok = stable_sort_r(array, mem, n, s, cmpfn, opaque);
217 873 : talloc_free(mem);
218 873 : return ok;
219 : }
220 :
221 :
222 3467 : bool stable_sort(void *array, void *aux,
223 : size_t n,
224 : size_t s,
225 : samba_compare_fn_t cmpfn)
226 : {
227 : /*
228 : * What is this magic, casting cmpfn into a different type that takes
229 : * an extra parameter? Is that allowed?
230 : *
231 : * A: Yes. It's fine. The extra argument will be passed on the stack
232 : * or (more likely) a register, and the cmpfn will remain blissfully
233 : * unaware.
234 : */
235 3467 : return stable_sort_r(array, aux, n, s,
236 : (samba_compare_with_context_fn_t)cmpfn,
237 : NULL);
238 : }
239 :
240 :
241 6 : bool stable_sort_talloc(TALLOC_CTX *mem_ctx,
242 : void *array,
243 : size_t n,
244 : size_t s,
245 : samba_compare_fn_t cmpfn)
246 : {
247 6 : return stable_sort_talloc_r(mem_ctx, array, n, s,
248 : (samba_compare_with_context_fn_t)cmpfn,
249 : NULL);
250 : }
|
