Actual source code: sortso.c
1: #include <petscsys.h>
2: #include <petsc/private/petscimpl.h>
4: static inline int Compare_PetscMPIInt_Private(const void *left, const void *right, PETSC_UNUSED void *ctx)
5: {
6: PetscMPIInt l = *(PetscMPIInt *)left, r = *(PetscMPIInt *)right;
7: return (l < r) ? -1 : (l > r);
8: }
10: static inline int Compare_PetscInt_Private(const void *left, const void *right, PETSC_UNUSED void *ctx)
11: {
12: PetscInt l = *(PetscInt *)left, r = *(PetscInt *)right;
13: return (l < r) ? -1 : (l > r);
14: }
16: static inline int Compare_PetscReal_Private(const void *left, const void *right, PETSC_UNUSED void *ctx)
17: {
18: PetscReal l = *(PetscReal *)left, r = *(PetscReal *)right;
19: return (l < r) ? -1 : (l > r);
20: }
22: #define MIN_GALLOP_CONST_GLOBAL 8
23: static PetscInt MIN_GALLOP_GLOBAL = MIN_GALLOP_CONST_GLOBAL;
24: typedef int (*CompFunc)(const void *, const void *, void *);
26: /* Mostly to force clang uses the builtins, but can't hurt to have gcc compilers also do the same */
27: #if !defined(PETSC_USE_DEBUG) && defined(__GNUC__)
28: static inline void COPYSWAPPY(char *a, char *b, char *t, size_t size)
29: {
30: __builtin_memcpy(t, b, size);
31: __builtin_memmove(b, a, size);
32: __builtin_memcpy(a, t, size);
33: return;
34: }
36: static inline void COPYSWAPPY2(char *al, char *ar, size_t asize, char *bl, char *br, size_t bsize, char *t)
37: {
38: __builtin_memcpy(t, ar, asize);
39: __builtin_memmove(ar, al, asize);
40: __builtin_memcpy(al, t, asize);
41: __builtin_memcpy(t, br, bsize);
42: __builtin_memmove(br, bl, bsize);
43: __builtin_memcpy(bl, t, bsize);
44: return;
45: }
47: static inline void Petsc_memcpy(char *dest, const char *src, size_t size)
48: {
49: __builtin_memcpy(dest, src, size);
50: return;
51: }
53: static inline void Petsc_memcpy2(char *adest, const char *asrc, size_t asize, char *bdest, const char *bsrc, size_t bsize)
54: {
55: __builtin_memcpy(adest, asrc, asize);
56: __builtin_memcpy(bdest, bsrc, bsize);
57: return;
58: }
60: static inline void Petsc_memmove(char *dest, const char *src, size_t size)
61: {
62: __builtin_memmove(dest, src, size);
63: return;
64: }
66: static inline void Petsc_memmove2(char *adest, const char *asrc, size_t asize, char *bdest, const char *bsrc, size_t bsize)
67: {
68: __builtin_memmove(adest, asrc, asize);
69: __builtin_memmove(bdest, bsrc, bsize);
70: return;
71: }
72: #else
73: static inline void COPYSWAPPY(char *a, char *b, char *t, size_t size)
74: {
75: PetscFunctionBegin;
76: PetscCallAbort(PETSC_COMM_SELF, PetscMemcpy(t, b, size));
77: PetscCallAbort(PETSC_COMM_SELF, PetscMemmove(b, a, size));
78: PetscCallAbort(PETSC_COMM_SELF, PetscMemcpy(a, t, size));
79: PetscFunctionReturnVoid();
80: }
82: static inline void COPYSWAPPY2(char *al, char *ar, size_t asize, char *bl, char *br, size_t bsize, char *t)
83: {
84: PetscFunctionBegin;
85: PetscCallAbort(PETSC_COMM_SELF, PetscMemcpy(t, ar, asize));
86: PetscCallAbort(PETSC_COMM_SELF, PetscMemmove(ar, al, asize));
87: PetscCallAbort(PETSC_COMM_SELF, PetscMemcpy(al, t, asize));
88: PetscCallAbort(PETSC_COMM_SELF, PetscMemcpy(t, br, bsize));
89: PetscCallAbort(PETSC_COMM_SELF, PetscMemmove(br, bl, bsize));
90: PetscCallAbort(PETSC_COMM_SELF, PetscMemcpy(bl, t, bsize));
91: PetscFunctionReturnVoid();
92: }
94: static inline void Petsc_memcpy(char *dest, const char *src, size_t size)
95: {
96: PetscFunctionBegin;
97: PetscCallAbort(PETSC_COMM_SELF, PetscMemcpy(dest, src, size));
98: PetscFunctionReturnVoid();
99: }
101: static inline void Petsc_memcpy2(char *adest, const char *asrc, size_t asize, char *bdest, const char *bsrc, size_t bsize)
102: {
103: PetscFunctionBegin;
104: PetscCallAbort(PETSC_COMM_SELF, PetscMemcpy(adest, asrc, asize));
105: PetscCallAbort(PETSC_COMM_SELF, PetscMemcpy(bdest, bsrc, bsize));
106: PetscFunctionReturnVoid();
107: }
109: static inline void Petsc_memmove(char *dest, const char *src, size_t size)
110: {
111: PetscFunctionBegin;
112: PetscCallAbort(PETSC_COMM_SELF, PetscMemmove(dest, src, size));
113: PetscFunctionReturnVoid();
114: }
116: static inline void Petsc_memmove2(char *adest, const char *asrc, size_t asize, char *bdest, const char *bsrc, size_t bsize)
117: {
118: PetscFunctionBegin;
119: PetscCallAbort(PETSC_COMM_SELF, PetscMemmove(adest, asrc, asize));
120: PetscCallAbort(PETSC_COMM_SELF, PetscMemmove(bdest, bsrc, bsize));
121: PetscFunctionReturnVoid();
122: }
123: #endif
125: /* Start left look right. Looking for e.g. B[0] in A or mergelo. l inclusive, r inclusive. Returns first m such that arr[m] >
126: x. Output also inclusive.
128: NOTE: Both gallopsearch functions CANNOT distinguish between inserting AFTER the entire array vs inserting at entry n!! For example for an array:
130: {0,1,2,3,4,5}
132: when looking to insert "5" this routine will return *m = 6, but when looking to insert "6" it will ALSO return *m = 6.
133: */
134: static inline PetscErrorCode PetscGallopSearchLeft_Private(const char *arr, size_t size, CompFunc cmp, void *ctx, PetscInt l, PetscInt r, const char *x, PetscInt *m)
135: {
136: PetscInt last = l, k = 1, mid, cur = l + 1;
138: PetscFunctionBegin;
139: *m = l;
140: PetscAssert(r >= l, PETSC_COMM_SELF, PETSC_ERR_PLIB, "r %" PetscInt_FMT " < l %" PetscInt_FMT " in PetscGallopSearchLeft", r, l);
141: if ((*cmp)(x, arr + r * size, ctx) >= 0) {
142: *m = r;
143: PetscFunctionReturn(PETSC_SUCCESS);
144: }
145: if ((*cmp)(x, (arr) + l * size, ctx) < 0 || PetscUnlikely(!(r - l))) PetscFunctionReturn(PETSC_SUCCESS);
146: while (PETSC_TRUE) {
147: if (PetscUnlikely(cur > r)) {
148: cur = r;
149: break;
150: }
151: if ((*cmp)(x, (arr) + cur * size, ctx) < 0) break;
152: last = cur;
153: cur += (k <<= 1) + 1;
154: ++k;
155: }
156: /* standard binary search but take last 0 mid 0 cur 1 into account*/
157: while (cur > last + 1) {
158: mid = last + ((cur - last) >> 1);
159: if ((*cmp)(x, (arr) + mid * size, ctx) < 0) {
160: cur = mid;
161: } else {
162: last = mid;
163: }
164: }
165: *m = cur;
166: PetscFunctionReturn(PETSC_SUCCESS);
167: }
169: /* Start right look left. Looking for e.g. A[-1] in B or mergehi. l inclusive, r inclusive. Returns last m such that arr[m]
170: < x. Output also inclusive */
171: static inline PetscErrorCode PetscGallopSearchRight_Private(const char *arr, size_t size, CompFunc cmp, void *ctx, PetscInt l, PetscInt r, const char *x, PetscInt *m)
172: {
173: PetscInt last = r, k = 1, mid, cur = r - 1;
175: PetscFunctionBegin;
176: *m = r;
177: PetscAssert(r >= l, PETSC_COMM_SELF, PETSC_ERR_PLIB, "r %" PetscInt_FMT " < l %" PetscInt_FMT " in PetscGallopSearchRight", r, l);
178: if ((*cmp)(x, arr + l * size, ctx) <= 0) {
179: *m = l;
180: PetscFunctionReturn(PETSC_SUCCESS);
181: }
182: if ((*cmp)(x, (arr) + r * size, ctx) > 0 || PetscUnlikely(!(r - l))) PetscFunctionReturn(PETSC_SUCCESS);
183: while (PETSC_TRUE) {
184: if (PetscUnlikely(cur < l)) {
185: cur = l;
186: break;
187: }
188: if ((*cmp)(x, (arr) + cur * size, ctx) > 0) break;
189: last = cur;
190: cur -= (k <<= 1) + 1;
191: ++k;
192: }
193: /* standard binary search but take last r-1 mid r-1 cur r-2 into account*/
194: while (last > cur + 1) {
195: mid = last - ((last - cur) >> 1);
196: if ((*cmp)(x, (arr) + mid * size, ctx) > 0) {
197: cur = mid;
198: } else {
199: last = mid;
200: }
201: }
202: *m = cur;
203: PetscFunctionReturn(PETSC_SUCCESS);
204: }
206: /* Mergesort where size of left half <= size of right half, so mergesort is done left to right. Arr should be pointer to
207: complete array, left is first index of left array, mid is first index of right array, right is last index of right
208: array */
209: static inline PetscErrorCode PetscTimSortMergeLo_Private(char *arr, char *tarr, size_t size, CompFunc cmp, void *ctx, PetscInt left, PetscInt mid, PetscInt right)
210: {
211: PetscInt i = 0, j = mid, k = left, gallopleft = 0, gallopright = 0;
212: const PetscInt llen = mid - left;
214: PetscFunctionBegin;
215: Petsc_memcpy(tarr, arr + (left * size), llen * size);
216: while ((i < llen) && (j <= right)) {
217: if ((*cmp)(tarr + (i * size), arr + (j * size), ctx) < 0) {
218: Petsc_memcpy(arr + (k * size), tarr + (i * size), size);
219: ++k;
220: gallopright = 0;
221: if (++i < llen && ++gallopleft >= MIN_GALLOP_GLOBAL) {
222: PetscInt l1, l2, diff1, diff2;
223: do {
224: if (MIN_GALLOP_GLOBAL > 1) --MIN_GALLOP_GLOBAL;
225: /* search temp for right[j], can move up to that of temp into arr immediately */
226: PetscCall(PetscGallopSearchLeft_Private(tarr, size, cmp, ctx, i, llen - 1, arr + (j * size), &l1));
227: diff1 = l1 - i;
228: Petsc_memcpy(arr + (k * size), tarr + (i * size), diff1 * size);
229: k += diff1;
230: i = l1;
231: /* search right for temp[i], can move up to that many of right into arr */
232: PetscCall(PetscGallopSearchLeft_Private(arr, size, cmp, ctx, j, right, tarr + (i * size), &l2));
233: diff2 = l2 - j;
234: Petsc_memmove((arr) + k * size, (arr) + j * size, diff2 * size);
235: k += diff2;
236: j = l2;
237: if (i >= llen || j > right) break;
238: } while (diff1 > MIN_GALLOP_GLOBAL || diff2 > MIN_GALLOP_GLOBAL);
239: ++MIN_GALLOP_GLOBAL;
240: }
241: } else {
242: Petsc_memmove(arr + (k * size), arr + (j * size), size);
243: ++k;
244: gallopleft = 0;
245: if (++j <= right && ++gallopright >= MIN_GALLOP_GLOBAL) {
246: PetscInt l1, l2, diff1, diff2;
247: do {
248: if (MIN_GALLOP_GLOBAL > 1) --MIN_GALLOP_GLOBAL;
249: /* search right for temp[i], can move up to that many of right into arr */
250: PetscCall(PetscGallopSearchLeft_Private(arr, size, cmp, ctx, j, right, tarr + (i * size), &l2));
251: diff2 = l2 - j;
252: Petsc_memmove(arr + (k * size), arr + (j * size), diff2 * size);
253: k += diff2;
254: j = l2;
255: /* search temp for right[j], can copy up to that of temp into arr immediately */
256: PetscCall(PetscGallopSearchLeft_Private(tarr, size, cmp, ctx, i, llen - 1, arr + (j * size), &l1));
257: diff1 = l1 - i;
258: Petsc_memcpy(arr + (k * size), tarr + (i * size), diff1 * size);
259: k += diff1;
260: i = l1;
261: if (i >= llen || j > right) break;
262: } while (diff1 > MIN_GALLOP_GLOBAL || diff2 > MIN_GALLOP_GLOBAL);
263: ++MIN_GALLOP_GLOBAL;
264: }
265: }
266: }
267: if (i < llen) Petsc_memcpy(arr + (k * size), tarr + (i * size), (llen - i) * size);
268: PetscFunctionReturn(PETSC_SUCCESS);
269: }
271: static inline PetscErrorCode PetscTimSortMergeLoWithArray_Private(char *arr, char *atarr, size_t asize, char *barr, char *btarr, size_t bsize, CompFunc cmp, void *ctx, PetscInt left, PetscInt mid, PetscInt right)
272: {
273: PetscInt i = 0, j = mid, k = left, gallopleft = 0, gallopright = 0;
274: const PetscInt llen = mid - left;
276: PetscFunctionBegin;
277: Petsc_memcpy2(atarr, arr + (left * asize), llen * asize, btarr, barr + (left * bsize), llen * bsize);
278: while ((i < llen) && (j <= right)) {
279: if ((*cmp)(atarr + (i * asize), arr + (j * asize), ctx) < 0) {
280: Petsc_memcpy2(arr + (k * asize), atarr + (i * asize), asize, barr + (k * bsize), btarr + (i * bsize), bsize);
281: ++k;
282: gallopright = 0;
283: if (++i < llen && ++gallopleft >= MIN_GALLOP_GLOBAL) {
284: PetscInt l1, l2, diff1, diff2;
285: do {
286: if (MIN_GALLOP_GLOBAL > 1) --MIN_GALLOP_GLOBAL;
287: /* search temp for right[j], can move up to that of temp into arr immediately */
288: PetscCall(PetscGallopSearchLeft_Private(atarr, asize, cmp, ctx, i, llen - 1, arr + (j * asize), &l1));
289: diff1 = l1 - i;
290: Petsc_memcpy2(arr + (k * asize), atarr + (i * asize), diff1 * asize, barr + (k * bsize), btarr + (i * bsize), diff1 * bsize);
291: k += diff1;
292: i = l1;
293: /* search right for temp[i], can move up to that many of right into arr */
294: PetscCall(PetscGallopSearchLeft_Private(arr, asize, cmp, ctx, j, right, atarr + (i * asize), &l2));
295: diff2 = l2 - j;
296: Petsc_memmove2(arr + (k * asize), arr + (j * asize), diff2 * asize, barr + (k * bsize), barr + (j * bsize), diff2 * bsize);
297: k += diff2;
298: j = l2;
299: if (i >= llen || j > right) break;
300: } while (diff1 > MIN_GALLOP_GLOBAL || diff2 > MIN_GALLOP_GLOBAL);
301: ++MIN_GALLOP_GLOBAL;
302: }
303: } else {
304: Petsc_memmove2(arr + (k * asize), arr + (j * asize), asize, barr + (k * bsize), barr + (j * bsize), bsize);
305: ++k;
306: gallopleft = 0;
307: if (++j <= right && ++gallopright >= MIN_GALLOP_GLOBAL) {
308: PetscInt l1, l2, diff1, diff2;
309: do {
310: if (MIN_GALLOP_GLOBAL > 1) --MIN_GALLOP_GLOBAL;
311: /* search right for temp[i], can move up to that many of right into arr */
312: PetscCall(PetscGallopSearchLeft_Private(arr, asize, cmp, ctx, j, right, atarr + (i * asize), &l2));
313: diff2 = l2 - j;
314: Petsc_memmove2(arr + (k * asize), arr + (j * asize), diff2 * asize, barr + (k * bsize), barr + (j * bsize), diff2 * bsize);
315: k += diff2;
316: j = l2;
317: /* search temp for right[j], can copy up to that of temp into arr immediately */
318: PetscCall(PetscGallopSearchLeft_Private(atarr, asize, cmp, ctx, i, llen - 1, arr + (j * asize), &l1));
319: diff1 = l1 - i;
320: Petsc_memcpy2(arr + (k * asize), atarr + (i * asize), diff1 * asize, barr + (k * bsize), btarr + (i * bsize), diff1 * bsize);
321: k += diff1;
322: i = l1;
323: if (i >= llen || j > right) break;
324: } while (diff1 > MIN_GALLOP_GLOBAL || diff2 > MIN_GALLOP_GLOBAL);
325: ++MIN_GALLOP_GLOBAL;
326: }
327: }
328: }
329: if (i < llen) Petsc_memcpy2(arr + (k * asize), atarr + (i * asize), (llen - i) * asize, barr + (k * bsize), btarr + (i * bsize), (llen - i) * bsize);
330: PetscFunctionReturn(PETSC_SUCCESS);
331: }
333: /* Mergesort where size of right half < size of left half, so mergesort is done right to left. Arr should be pointer to
334: complete array, left is first index of left array, mid is first index of right array, right is last index of right
335: array */
336: static inline PetscErrorCode PetscTimSortMergeHi_Private(char *arr, char *tarr, size_t size, CompFunc cmp, void *ctx, PetscInt left, PetscInt mid, PetscInt right)
337: {
338: PetscInt i = right - mid, j = mid - 1, k = right, gallopleft = 0, gallopright = 0;
339: const PetscInt rlen = right - mid + 1;
341: PetscFunctionBegin;
342: Petsc_memcpy(tarr, (arr) + mid * size, rlen * size);
343: while ((i >= 0) && (j >= left)) {
344: if ((*cmp)((tarr) + i * size, (arr) + j * size, ctx) > 0) {
345: Petsc_memcpy((arr) + k * size, (tarr) + i * size, size);
346: --k;
347: gallopleft = 0;
348: if (--i >= 0 && ++gallopright >= MIN_GALLOP_GLOBAL) {
349: PetscInt l1, l2, diff1, diff2;
350: do {
351: if (MIN_GALLOP_GLOBAL > 1) --MIN_GALLOP_GLOBAL;
352: /* search temp for left[j], can copy up to that many of temp into arr */
353: PetscCall(PetscGallopSearchRight_Private(tarr, size, cmp, ctx, 0, i, (arr) + j * size, &l1));
354: diff1 = i - l1;
355: Petsc_memcpy((arr) + (k - diff1 + 1) * size, (tarr) + (l1 + 1) * size, diff1 * size);
356: k -= diff1;
357: i = l1;
358: /* search left for temp[i], can move up to that many of left up arr */
359: PetscCall(PetscGallopSearchRight_Private(arr, size, cmp, ctx, left, j, (tarr) + i * size, &l2));
360: diff2 = j - l2;
361: Petsc_memmove((arr) + (k - diff2 + 1) * size, (arr) + (l2 + 1) * size, diff2 * size);
362: k -= diff2;
363: j = l2;
364: if (i < 0 || j < left) break;
365: } while (diff1 > MIN_GALLOP_GLOBAL || diff2 > MIN_GALLOP_GLOBAL);
366: ++MIN_GALLOP_GLOBAL;
367: }
368: } else {
369: Petsc_memmove((arr) + k * size, (arr) + j * size, size);
370: --k;
371: gallopright = 0;
372: if (--j >= left && ++gallopleft >= MIN_GALLOP_GLOBAL) {
373: PetscInt l1, l2, diff1, diff2;
374: do {
375: if (MIN_GALLOP_GLOBAL > 1) --MIN_GALLOP_GLOBAL;
376: /* search left for temp[i], can move up to that many of left up arr */
377: PetscCall(PetscGallopSearchRight_Private(arr, size, cmp, ctx, left, j, (tarr) + i * size, &l2));
378: diff2 = j - l2;
379: Petsc_memmove((arr) + (k - diff2 + 1) * size, (arr) + (l2 + 1) * size, diff2 * size);
380: k -= diff2;
381: j = l2;
382: /* search temp for left[j], can copy up to that many of temp into arr */
383: PetscCall(PetscGallopSearchRight_Private(tarr, size, cmp, ctx, 0, i, (arr) + j * size, &l1));
384: diff1 = i - l1;
385: Petsc_memcpy((arr) + (k - diff1 + 1) * size, (tarr) + (l1 + 1) * size, diff1 * size);
386: k -= diff1;
387: i = l1;
388: if (i < 0 || j < left) break;
389: } while (diff1 > MIN_GALLOP_GLOBAL || diff2 > MIN_GALLOP_GLOBAL);
390: ++MIN_GALLOP_GLOBAL;
391: }
392: }
393: }
394: if (i >= 0) Petsc_memcpy((arr) + left * size, tarr, (i + 1) * size);
395: PetscFunctionReturn(PETSC_SUCCESS);
396: }
398: static inline PetscErrorCode PetscTimSortMergeHiWithArray_Private(char *arr, char *atarr, size_t asize, char *barr, char *btarr, size_t bsize, CompFunc cmp, void *ctx, PetscInt left, PetscInt mid, PetscInt right)
399: {
400: PetscInt i = right - mid, j = mid - 1, k = right, gallopleft = 0, gallopright = 0;
401: const PetscInt rlen = right - mid + 1;
403: PetscFunctionBegin;
404: Petsc_memcpy2(atarr, (arr) + mid * asize, rlen * asize, btarr, (barr) + mid * bsize, rlen * bsize);
405: while ((i >= 0) && (j >= left)) {
406: if ((*cmp)((atarr) + i * asize, (arr) + j * asize, ctx) > 0) {
407: Petsc_memcpy2((arr) + k * asize, (atarr) + i * asize, asize, (barr) + k * bsize, (btarr) + i * bsize, bsize);
408: --k;
409: gallopleft = 0;
410: if (--i >= 0 && ++gallopright >= MIN_GALLOP_GLOBAL) {
411: PetscInt l1, l2, diff1, diff2;
412: do {
413: if (MIN_GALLOP_GLOBAL > 1) --MIN_GALLOP_GLOBAL;
414: /* search temp for left[j], can copy up to that many of temp into arr */
415: PetscCall(PetscGallopSearchRight_Private(atarr, asize, cmp, ctx, 0, i, (arr) + j * asize, &l1));
416: diff1 = i - l1;
417: Petsc_memcpy2((arr) + (k - diff1 + 1) * asize, (atarr) + (l1 + 1) * asize, diff1 * asize, (barr) + (k - diff1 + 1) * bsize, (btarr) + (l1 + 1) * bsize, diff1 * bsize);
418: k -= diff1;
419: i = l1;
420: /* search left for temp[i], can move up to that many of left up arr */
421: PetscCall(PetscGallopSearchRight_Private(arr, asize, cmp, ctx, left, j, (atarr) + i * asize, &l2));
422: diff2 = j - l2;
423: Petsc_memmove2((arr) + (k - diff2 + 1) * asize, (arr) + (l2 + 1) * asize, diff2 * asize, (barr) + (k - diff2 + 1) * bsize, (barr) + (l2 + 1) * bsize, diff2 * bsize);
424: k -= diff2;
425: j = l2;
426: if (i < 0 || j < left) break;
427: } while (diff1 > MIN_GALLOP_GLOBAL || diff2 > MIN_GALLOP_GLOBAL);
428: ++MIN_GALLOP_GLOBAL;
429: }
430: } else {
431: Petsc_memmove2((arr) + k * asize, (arr) + j * asize, asize, (barr) + k * bsize, (barr) + j * bsize, bsize);
432: --k;
433: gallopright = 0;
434: if (--j >= left && ++gallopleft >= MIN_GALLOP_GLOBAL) {
435: PetscInt l1, l2, diff1, diff2;
436: do {
437: if (MIN_GALLOP_GLOBAL > 1) --MIN_GALLOP_GLOBAL;
438: /* search left for temp[i], can move up to that many of left up arr */
439: PetscCall(PetscGallopSearchRight_Private(arr, asize, cmp, ctx, left, j, (atarr) + i * asize, &l2));
440: diff2 = j - l2;
441: Petsc_memmove2((arr) + (k - diff2 + 1) * asize, (arr) + (l2 + 1) * asize, diff2 * asize, (barr) + (k - diff2 + 1) * bsize, (barr) + (l2 + 1) * bsize, diff2 * bsize);
442: k -= diff2;
443: j = l2;
444: /* search temp for left[j], can copy up to that many of temp into arr */
445: PetscCall(PetscGallopSearchRight_Private(atarr, asize, cmp, ctx, 0, i, (arr) + j * asize, &l1));
446: diff1 = i - l1;
447: Petsc_memcpy2((arr) + (k - diff1 + 1) * asize, (atarr) + (l1 + 1) * asize, diff1 * asize, (barr) + (k - diff1 + 1) * bsize, (btarr) + (l1 + 1) * bsize, diff1 * bsize);
448: k -= diff1;
449: i = l1;
450: if (i < 0 || j < left) break;
451: } while (diff1 > MIN_GALLOP_GLOBAL || diff2 > MIN_GALLOP_GLOBAL);
452: ++MIN_GALLOP_GLOBAL;
453: }
454: }
455: }
456: if (i >= 0) Petsc_memcpy2((arr) + left * asize, atarr, (i + 1) * asize, (barr) + left * bsize, btarr, (i + 1) * bsize);
457: PetscFunctionReturn(PETSC_SUCCESS);
458: }
460: /* Left is inclusive lower bound of array slice, start is start location of unsorted section, right is inclusive upper
461: bound of array slice. If unsure of where unsorted section starts or if entire length is unsorted pass start = left */
462: static inline PetscErrorCode PetscInsertionSort_Private(char *arr, char *tarr, size_t size, CompFunc cmp, void *ctx, PetscInt left, PetscInt start, PetscInt right)
463: {
464: PetscInt i = start == left ? start + 1 : start;
466: PetscFunctionBegin;
467: for (; i <= right; ++i) {
468: PetscInt j = i - 1;
469: Petsc_memcpy(tarr, arr + (i * size), size);
470: while ((j >= left) && ((*cmp)(tarr, (arr) + j * size, ctx) < 0)) {
471: COPYSWAPPY(arr + (j + 1) * size, arr + j * size, tarr + size, size);
472: --j;
473: }
474: Petsc_memcpy((arr) + (j + 1) * size, tarr, size);
475: }
476: PetscFunctionReturn(PETSC_SUCCESS);
477: }
479: static inline PetscErrorCode PetscInsertionSortWithArray_Private(char *arr, char *atarr, size_t asize, char *barr, char *btarr, size_t bsize, CompFunc cmp, void *ctx, PetscInt left, PetscInt start, PetscInt right)
480: {
481: PetscInt i = start == left ? start + 1 : start;
483: PetscFunctionBegin;
484: for (; i <= right; ++i) {
485: PetscInt j = i - 1;
486: Petsc_memcpy2(atarr, arr + (i * asize), asize, btarr, barr + (i * bsize), bsize);
487: while ((j >= left) && ((*cmp)(atarr, arr + (j * asize), ctx) < 0)) {
488: COPYSWAPPY2(arr + (j + 1) * asize, arr + j * asize, asize, barr + (j + 1) * bsize, barr + j * bsize, bsize, atarr + asize);
489: --j;
490: }
491: Petsc_memcpy2(arr + (j + 1) * asize, atarr, asize, barr + (j + 1) * bsize, btarr, bsize);
492: }
493: PetscFunctionReturn(PETSC_SUCCESS);
494: }
496: /* See PetscInsertionSort_Private */
497: static inline PetscErrorCode PetscBinaryInsertionSort_Private(char *arr, char *tarr, size_t size, CompFunc cmp, void *ctx, PetscInt left, PetscInt start, PetscInt right)
498: {
499: PetscInt i = start == left ? start + 1 : start;
501: PetscFunctionBegin;
502: for (; i <= right; ++i) {
503: PetscInt l = left, r = i;
504: Petsc_memcpy(tarr, arr + (i * size), size);
505: do {
506: const PetscInt m = l + ((r - l) >> 1);
507: if ((*cmp)(tarr, arr + (m * size), ctx) < 0) {
508: r = m;
509: } else {
510: l = m + 1;
511: }
512: } while (l < r);
513: Petsc_memmove(arr + ((l + 1) * size), arr + (l * size), (i - l) * size);
514: Petsc_memcpy(arr + (l * size), tarr, size);
515: }
516: PetscFunctionReturn(PETSC_SUCCESS);
517: }
519: static inline PetscErrorCode PetscBinaryInsertionSortWithArray_Private(char *arr, char *atarr, size_t asize, char *barr, char *btarr, size_t bsize, CompFunc cmp, void *ctx, PetscInt left, PetscInt start, PetscInt right)
520: {
521: PetscInt i = start == left ? start + 1 : start;
523: PetscFunctionBegin;
524: for (; i <= right; ++i) {
525: PetscInt l = left, r = i;
526: Petsc_memcpy2(atarr, arr + (i * asize), asize, btarr, barr + (i * bsize), bsize);
527: do {
528: const PetscInt m = l + ((r - l) >> 1);
529: if ((*cmp)(atarr, arr + (m * asize), ctx) < 0) {
530: r = m;
531: } else {
532: l = m + 1;
533: }
534: } while (l < r);
535: Petsc_memmove2(arr + ((l + 1) * asize), arr + (l * asize), (i - l) * asize, barr + ((l + 1) * bsize), barr + (l * bsize), (i - l) * bsize);
536: Petsc_memcpy2(arr + (l * asize), atarr, asize, barr + (l * bsize), btarr, bsize);
537: }
538: PetscFunctionReturn(PETSC_SUCCESS);
539: }
541: typedef struct {
542: PetscInt size;
543: PetscInt start;
544: #if defined(__CRAY_AARCH64) /* segfaults with Cray compilers for aarch64 on a64FX */
545: } PetscTimSortStack;
546: #else
547: } PetscTimSortStack PETSC_ATTRIBUTEALIGNED(2 * sizeof(PetscInt));
548: #endif
550: typedef struct {
551: char *ptr PETSC_ATTRIBUTEALIGNED(PETSC_MEMALIGN);
552: size_t size;
553: size_t maxsize;
554: } PetscTimSortBuffer;
556: static inline PetscErrorCode PetscTimSortResizeBuffer_Private(PetscTimSortBuffer *buff, size_t newSize)
557: {
558: PetscFunctionBegin;
559: if (PetscLikely(newSize <= buff->size)) PetscFunctionReturn(PETSC_SUCCESS);
560: {
561: /* Can't be larger than n, there is merit to simply allocating buff to n to begin with */
562: size_t newMax = PetscMin(newSize * newSize, buff->maxsize);
563: PetscCall(PetscFree(buff->ptr));
564: PetscCall(PetscMalloc1(newMax, &buff->ptr));
565: buff->size = newMax;
566: }
567: PetscFunctionReturn(PETSC_SUCCESS);
568: }
570: static inline PetscErrorCode PetscTimSortForceCollapse_Private(char *arr, size_t size, CompFunc cmp, void *ctx, PetscTimSortBuffer *buff, PetscTimSortStack *stack, PetscInt stacksize)
571: {
572: PetscFunctionBegin;
573: for (; stacksize; --stacksize) {
574: /* A = stack[i-1], B = stack[i], if A[-1] <= B[0] means sorted */
575: if ((*cmp)(arr + (stack[stacksize].start - 1) * size, arr + (stack[stacksize].start) * size, ctx) > 0) {
576: PetscInt l, m = stack[stacksize].start, r;
577: /* Search A for B[0] insertion */
578: PetscCall(PetscGallopSearchLeft_Private(arr, size, cmp, ctx, stack[stacksize - 1].start, stack[stacksize].start - 1, (arr) + (stack[stacksize].start) * size, &l));
579: /* Search B for A[-1] insertion */
580: PetscCall(PetscGallopSearchRight_Private(arr, size, cmp, ctx, stack[stacksize].start, stack[stacksize].start + stack[stacksize].size - 1, (arr) + (stack[stacksize].start - 1) * size, &r));
581: if (m - l <= r - m) {
582: PetscCall(PetscTimSortResizeBuffer_Private(buff, (m - l + 1) * size));
583: PetscCall(PetscTimSortMergeLo_Private(arr, buff->ptr, size, cmp, ctx, l, m, r));
584: } else {
585: PetscCall(PetscTimSortResizeBuffer_Private(buff, (r - m + 1) * size));
586: PetscCall(PetscTimSortMergeHi_Private(arr, buff->ptr, size, cmp, ctx, l, m, r));
587: }
588: }
589: /* Update A with merge */
590: stack[stacksize - 1].size += stack[stacksize].size;
591: }
592: PetscFunctionReturn(PETSC_SUCCESS);
593: }
595: static inline PetscErrorCode PetscTimSortForceCollapseWithArray_Private(char *arr, size_t asize, char *barr, size_t bsize, CompFunc cmp, void *ctx, PetscTimSortBuffer *abuff, PetscTimSortBuffer *bbuff, PetscTimSortStack *stack, PetscInt stacksize)
596: {
597: PetscFunctionBegin;
598: for (; stacksize; --stacksize) {
599: /* A = stack[i-1], B = stack[i], if A[-1] <= B[0] means sorted */
600: if ((*cmp)(arr + (stack[stacksize].start - 1) * asize, arr + (stack[stacksize].start) * asize, ctx) > 0) {
601: PetscInt l, m = stack[stacksize].start, r;
602: /* Search A for B[0] insertion */
603: PetscCall(PetscGallopSearchLeft_Private(arr, asize, cmp, ctx, stack[stacksize - 1].start, stack[stacksize].start - 1, (arr) + (stack[stacksize].start) * asize, &l));
604: /* Search B for A[-1] insertion */
605: PetscCall(PetscGallopSearchRight_Private(arr, asize, cmp, ctx, stack[stacksize].start, stack[stacksize].start + stack[stacksize].size - 1, (arr) + (stack[stacksize].start - 1) * asize, &r));
606: if (m - l <= r - m) {
607: PetscCall(PetscTimSortResizeBuffer_Private(abuff, (m - l + 1) * asize));
608: PetscCall(PetscTimSortResizeBuffer_Private(bbuff, (m - l + 1) * bsize));
609: PetscCall(PetscTimSortMergeLoWithArray_Private(arr, abuff->ptr, asize, barr, bbuff->ptr, bsize, cmp, ctx, l, m, r));
610: } else {
611: PetscCall(PetscTimSortResizeBuffer_Private(abuff, (r - m + 1) * asize));
612: PetscCall(PetscTimSortResizeBuffer_Private(bbuff, (r - m + 1) * bsize));
613: PetscCall(PetscTimSortMergeHiWithArray_Private(arr, abuff->ptr, asize, barr, bbuff->ptr, bsize, cmp, ctx, l, m, r));
614: }
615: }
616: /* Update A with merge */
617: stack[stacksize - 1].size += stack[stacksize].size;
618: }
619: PetscFunctionReturn(PETSC_SUCCESS);
620: }
622: static inline PetscErrorCode PetscTimSortMergeCollapse_Private(char *arr, size_t size, CompFunc cmp, void *ctx, PetscTimSortBuffer *buff, PetscTimSortStack *stack, PetscInt *stacksize)
623: {
624: PetscInt i = *stacksize;
626: PetscFunctionBegin;
627: while (i) {
628: PetscInt l, m, r, itemp = i;
630: if (i == 1) {
631: /* A = stack[i-1], B = stack[i] */
632: if (stack[i - 1].size < stack[i].size) {
633: /* if A[-1] <= B[0] then sorted */
634: if ((*cmp)(arr + (stack[i].start - 1) * size, arr + (stack[i].start) * size, ctx) > 0) {
635: m = stack[i].start;
636: /* Search A for B[0] insertion */
637: PetscCall(PetscGallopSearchLeft_Private(arr, size, cmp, ctx, stack[i - 1].start, stack[i].start - 1, (arr) + stack[i].start * size, &l));
638: /* Search B for A[-1] insertion */
639: PetscCall(PetscGallopSearchRight_Private(arr, size, cmp, ctx, stack[i].start, stack[i].start + stack[i].size - 1, arr + (stack[i].start - 1) * size, &r));
640: if (m - l <= r - m) {
641: PetscCall(PetscTimSortResizeBuffer_Private(buff, (m - l + 1) * size));
642: PetscCall(PetscTimSortMergeLo_Private(arr, buff->ptr, size, cmp, ctx, l, m, r));
643: } else {
644: PetscCall(PetscTimSortResizeBuffer_Private(buff, (r - m + 1) * size));
645: PetscCall(PetscTimSortMergeHi_Private(arr, buff->ptr, size, cmp, ctx, l, m, r));
646: }
647: }
648: /* Update A with merge */
649: stack[i - 1].size += stack[i].size;
650: --i;
651: }
652: } else {
653: /* i > 2, i.e. C exists
654: A = stack[i-2], B = stack[i-1], C = stack[i]; */
655: if (stack[i - 2].size <= stack[i - 1].size + stack[i].size) {
656: if (stack[i - 2].size < stack[i].size) {
657: /* merge B into A, but if A[-1] <= B[0] then already sorted */
658: if ((*cmp)(arr + (stack[i - 1].start - 1) * size, arr + (stack[i - 1].start) * size, ctx) > 0) {
659: m = stack[i - 1].start;
660: /* Search A for B[0] insertion */
661: PetscCall(PetscGallopSearchLeft_Private(arr, size, cmp, ctx, stack[i - 2].start, stack[i - 1].start - 1, (arr) + (stack[i - 1].start) * size, &l));
662: /* Search B for A[-1] insertion */
663: PetscCall(PetscGallopSearchRight_Private(arr, size, cmp, ctx, stack[i - 1].start, stack[i - 1].start + stack[i - 1].size - 1, (arr) + (stack[i - 1].start - 1) * size, &r));
664: if (m - l <= r - m) {
665: PetscCall(PetscTimSortResizeBuffer_Private(buff, (m - l + 1) * size));
666: PetscCall(PetscTimSortMergeLo_Private(arr, buff->ptr, size, cmp, ctx, l, m, r));
667: } else {
668: PetscCall(PetscTimSortResizeBuffer_Private(buff, (r - m + 1) * size));
669: PetscCall(PetscTimSortMergeHi_Private(arr, buff->ptr, size, cmp, ctx, l, m, r));
670: }
671: }
672: /* Update A with merge */
673: stack[i - 2].size += stack[i - 1].size;
674: /* Push C up the stack */
675: stack[i - 1].start = stack[i].start;
676: stack[i - 1].size = stack[i].size;
677: } else {
678: /* merge C into B */
679: mergeBC:
680: /* If B[-1] <= C[0] then... you know the drill */
681: if ((*cmp)(arr + (stack[i].start - 1) * size, arr + (stack[i].start) * size, ctx) > 0) {
682: m = stack[i].start;
683: /* Search B for C[0] insertion */
684: PetscCall(PetscGallopSearchLeft_Private(arr, size, cmp, ctx, stack[i - 1].start, stack[i].start - 1, arr + stack[i].start * size, &l));
685: /* Search C for B[-1] insertion */
686: PetscCall(PetscGallopSearchRight_Private(arr, size, cmp, ctx, stack[i].start, stack[i].start + stack[i].size - 1, (arr) + (stack[i].start - 1) * size, &r));
687: if (m - l <= r - m) {
688: PetscCall(PetscTimSortResizeBuffer_Private(buff, (m - l + 1) * size));
689: PetscCall(PetscTimSortMergeLo_Private(arr, buff->ptr, size, cmp, ctx, l, m, r));
690: } else {
691: PetscCall(PetscTimSortResizeBuffer_Private(buff, (r - m + 1) * size));
692: PetscCall(PetscTimSortMergeHi_Private(arr, buff->ptr, size, cmp, ctx, l, m, r));
693: }
694: }
695: /* Update B with merge */
696: stack[i - 1].size += stack[i].size;
697: }
698: --i;
699: } else if (stack[i - 1].size <= stack[i].size) {
700: /* merge C into B */
701: goto mergeBC;
702: }
703: }
704: if (itemp == i) break;
705: }
706: *stacksize = i;
707: PetscFunctionReturn(PETSC_SUCCESS);
708: }
710: static inline PetscErrorCode PetscTimSortMergeCollapseWithArray_Private(char *arr, size_t asize, char *barr, size_t bsize, CompFunc cmp, void *ctx, PetscTimSortBuffer *abuff, PetscTimSortBuffer *bbuff, PetscTimSortStack *stack, PetscInt *stacksize)
711: {
712: PetscInt i = *stacksize;
714: PetscFunctionBegin;
715: while (i) {
716: PetscInt l, m, r, itemp = i;
718: if (i == 1) {
719: /* A = stack[i-1], B = stack[i] */
720: if (stack[i - 1].size < stack[i].size) {
721: /* if A[-1] <= B[0] then sorted */
722: if ((*cmp)(arr + (stack[i].start - 1) * asize, arr + (stack[i].start) * asize, ctx) > 0) {
723: m = stack[i].start;
724: /* Search A for B[0] insertion */
725: PetscCall(PetscGallopSearchLeft_Private(arr, asize, cmp, ctx, stack[i - 1].start, stack[i].start - 1, (arr) + stack[i].start * asize, &l));
726: /* Search B for A[-1] insertion */
727: PetscCall(PetscGallopSearchRight_Private(arr, asize, cmp, ctx, stack[i].start, stack[i].start + stack[i].size - 1, arr + (stack[i].start - 1) * asize, &r));
728: if (m - l <= r - m) {
729: PetscCall(PetscTimSortResizeBuffer_Private(abuff, (m - l + 1) * asize));
730: PetscCall(PetscTimSortResizeBuffer_Private(bbuff, (m - l + 1) * bsize));
731: PetscCall(PetscTimSortMergeLoWithArray_Private(arr, abuff->ptr, asize, barr, bbuff->ptr, bsize, cmp, ctx, l, m, r));
732: } else {
733: PetscCall(PetscTimSortResizeBuffer_Private(abuff, (r - m + 1) * asize));
734: PetscCall(PetscTimSortResizeBuffer_Private(bbuff, (r - m + 1) * bsize));
735: PetscCall(PetscTimSortMergeHiWithArray_Private(arr, abuff->ptr, asize, barr, bbuff->ptr, bsize, cmp, ctx, l, m, r));
736: }
737: }
738: /* Update A with merge */
739: stack[i - 1].size += stack[i].size;
740: --i;
741: }
742: } else {
743: /* i > 2, i.e. C exists
744: A = stack[i-2], B = stack[i-1], C = stack[i]; */
745: if (stack[i - 2].size <= stack[i - 1].size + stack[i].size) {
746: if (stack[i - 2].size < stack[i].size) {
747: /* merge B into A, but if A[-1] <= B[0] then already sorted */
748: if ((*cmp)(arr + (stack[i - 1].start - 1) * asize, arr + (stack[i - 1].start) * asize, ctx) > 0) {
749: m = stack[i - 1].start;
750: /* Search A for B[0] insertion */
751: PetscCall(PetscGallopSearchLeft_Private(arr, asize, cmp, ctx, stack[i - 2].start, stack[i - 1].start - 1, (arr) + (stack[i - 1].start) * asize, &l));
752: /* Search B for A[-1] insertion */
753: PetscCall(PetscGallopSearchRight_Private(arr, asize, cmp, ctx, stack[i - 1].start, stack[i - 1].start + stack[i - 1].size - 1, (arr) + (stack[i - 1].start - 1) * asize, &r));
754: if (m - l <= r - m) {
755: PetscCall(PetscTimSortResizeBuffer_Private(abuff, (m - l + 1) * asize));
756: PetscCall(PetscTimSortResizeBuffer_Private(bbuff, (m - l + 1) * bsize));
757: PetscCall(PetscTimSortMergeLoWithArray_Private(arr, abuff->ptr, asize, barr, bbuff->ptr, bsize, cmp, ctx, l, m, r));
758: } else {
759: PetscCall(PetscTimSortResizeBuffer_Private(abuff, (r - m + 1) * asize));
760: PetscCall(PetscTimSortResizeBuffer_Private(bbuff, (r - m + 1) * bsize));
761: PetscCall(PetscTimSortMergeHiWithArray_Private(arr, abuff->ptr, asize, barr, bbuff->ptr, bsize, cmp, ctx, l, m, r));
762: }
763: }
764: /* Update A with merge */
765: stack[i - 2].size += stack[i - 1].size;
766: /* Push C up the stack */
767: stack[i - 1].start = stack[i].start;
768: stack[i - 1].size = stack[i].size;
769: } else {
770: /* merge C into B */
771: mergeBC:
772: /* If B[-1] <= C[0] then... you know the drill */
773: if ((*cmp)(arr + (stack[i].start - 1) * asize, arr + (stack[i].start) * asize, ctx) > 0) {
774: m = stack[i].start;
775: /* Search B for C[0] insertion */
776: PetscCall(PetscGallopSearchLeft_Private(arr, asize, cmp, ctx, stack[i - 1].start, stack[i].start - 1, arr + stack[i].start * asize, &l));
777: /* Search C for B[-1] insertion */
778: PetscCall(PetscGallopSearchRight_Private(arr, asize, cmp, ctx, stack[i].start, stack[i].start + stack[i].size - 1, (arr) + (stack[i].start - 1) * asize, &r));
779: if (m - l <= r - m) {
780: PetscCall(PetscTimSortResizeBuffer_Private(abuff, (m - l + 1) * asize));
781: PetscCall(PetscTimSortResizeBuffer_Private(bbuff, (m - l + 1) * bsize));
782: PetscCall(PetscTimSortMergeLoWithArray_Private(arr, abuff->ptr, asize, barr, bbuff->ptr, bsize, cmp, ctx, l, m, r));
783: } else {
784: PetscCall(PetscTimSortResizeBuffer_Private(abuff, (r - m + 1) * asize));
785: PetscCall(PetscTimSortResizeBuffer_Private(bbuff, (r - m + 1) * bsize));
786: PetscCall(PetscTimSortMergeHiWithArray_Private(arr, abuff->ptr, asize, barr, bbuff->ptr, bsize, cmp, ctx, l, m, r));
787: }
788: }
789: /* Update B with merge */
790: stack[i - 1].size += stack[i].size;
791: }
792: --i;
793: } else if (stack[i - 1].size <= stack[i].size) {
794: /* merge C into B */
795: goto mergeBC;
796: }
797: }
798: if (itemp == i) break;
799: }
800: *stacksize = i;
801: PetscFunctionReturn(PETSC_SUCCESS);
802: }
804: /* March sequentially through the array building up a "run" of weakly increasing or strictly decreasing contiguous
805: elements. Decreasing runs are reversed by swapping. If the run is less than minrun, artificially extend it via either
806: binary insertion sort or regulat insertion sort */
807: static inline PetscErrorCode PetscTimSortBuildRun_Private(char *arr, char *tarr, size_t size, CompFunc cmp, void *ctx, PetscInt n, PetscInt minrun, PetscInt runstart, PetscInt *runend)
808: {
809: const PetscInt re = PetscMin(runstart + minrun, n - 1);
810: PetscInt ri = runstart;
812: PetscFunctionBegin;
813: if (PetscUnlikely(runstart == n - 1)) {
814: *runend = runstart;
815: PetscFunctionReturn(PETSC_SUCCESS);
816: }
817: /* guess whether run is ascending or descending and tally up the longest consecutive run. essentially a coinflip for random data */
818: if ((*cmp)((arr) + (ri + 1) * size, (arr) + ri * size, ctx) < 0) {
819: ++ri;
820: while (ri < n - 1) {
821: if ((*cmp)((arr) + (ri + 1) * size, (arr) + ri * size, ctx) >= 0) break;
822: ++ri;
823: }
824: {
825: PetscInt lo = runstart, hi = ri;
826: for (; lo < hi; ++lo, --hi) COPYSWAPPY(arr + lo * size, arr + hi * size, tarr, size);
827: }
828: } else {
829: ++ri;
830: while (ri < n - 1) {
831: if ((*cmp)((arr) + (ri + 1) * size, (arr) + ri * size, ctx) < 0) break;
832: ++ri;
833: }
834: }
835: if (ri < re) {
836: /* the attempt failed, this section likely contains random data. If ri got close to minrun (within 50%) then we try
837: binary search */
838: if (ri - runstart <= minrun >> 1) {
839: ++MIN_GALLOP_GLOBAL; /* didn't get close hedge our bets against random data */
840: PetscCall(PetscInsertionSort_Private(arr, tarr, size, cmp, ctx, runstart, ri, re));
841: } else {
842: PetscCall(PetscBinaryInsertionSort_Private(arr, tarr, size, cmp, ctx, runstart, ri, re));
843: }
844: *runend = re;
845: } else *runend = ri;
846: PetscFunctionReturn(PETSC_SUCCESS);
847: }
849: static inline PetscErrorCode PetscTimSortBuildRunWithArray_Private(char *arr, char *atarr, size_t asize, char *barr, char *btarr, size_t bsize, CompFunc cmp, void *ctx, PetscInt n, PetscInt minrun, PetscInt runstart, PetscInt *runend)
850: {
851: const PetscInt re = PetscMin(runstart + minrun, n - 1);
852: PetscInt ri = runstart;
854: PetscFunctionBegin;
855: if (PetscUnlikely(runstart == n - 1)) {
856: *runend = runstart;
857: PetscFunctionReturn(PETSC_SUCCESS);
858: }
859: /* guess whether run is ascending or descending and tally up the longest consecutive run. essentially a coinflip for random data */
860: if ((*cmp)((arr) + (ri + 1) * asize, arr + (ri * asize), ctx) < 0) {
861: ++ri;
862: while (ri < n - 1) {
863: if ((*cmp)((arr) + (ri + 1) * asize, (arr) + ri * asize, ctx) >= 0) break;
864: ++ri;
865: }
866: {
867: PetscInt lo = runstart, hi = ri;
868: for (; lo < hi; ++lo, --hi) COPYSWAPPY2(arr + lo * asize, arr + hi * asize, asize, barr + lo * bsize, barr + hi * bsize, bsize, atarr);
869: }
870: } else {
871: ++ri;
872: while (ri < n - 1) {
873: if ((*cmp)((arr) + (ri + 1) * asize, (arr) + ri * asize, ctx) < 0) break;
874: ++ri;
875: }
876: }
877: if (ri < re) {
878: /* the attempt failed, this section likely contains random data. If ri got close to minrun (within 50%) then we try
879: binary search */
880: if (ri - runstart <= minrun >> 1) {
881: ++MIN_GALLOP_GLOBAL; /* didn't get close hedge our bets against random data */
882: PetscCall(PetscInsertionSortWithArray_Private(arr, atarr, asize, barr, btarr, bsize, cmp, ctx, runstart, ri, re));
883: } else {
884: PetscCall(PetscBinaryInsertionSortWithArray_Private(arr, atarr, asize, barr, btarr, bsize, cmp, ctx, runstart, ri, re));
885: }
886: *runend = re;
887: } else *runend = ri;
888: PetscFunctionReturn(PETSC_SUCCESS);
889: }
891: /*@C
892: PetscTimSort - Sorts an array in place in increasing order using Tim Peters <https://bugs.python.org/file4451/timsort.txt> adaptive sorting algorithm.
894: Not Collective
896: Input Parameters:
897: + n - number of values
898: . arr - array to be sorted
899: . size - size in bytes of the datatype held in arr
900: . cmp - function pointer to comparison function
901: - ctx - optional context to be passed to comparison function, NULL if not needed
903: Output Parameter:
904: . arr - sorted array
906: Level: developer
908: Notes:
909: Timsort makes the assumption that input data is already likely partially ordered, or that it contains contiguous
910: sections (termed 'runs') where the data is locally ordered (but not necessarily globally ordered). It therefore aims to
911: select slices of the array in such a way that resulting mergesorts operate on near perfectly length-balanced arrays. To
912: do so it repeatedly triggers attempts throughout to merge adjacent runs.
914: Should one run continuously "win" a comparison the algorithm begins the "gallop" phase. It will aggressively search
915: the "winner" for the location of the "losers" next entry (and vice versa) to copy all preceding elements into place in
916: bulk. However if the data is truly unordered (as is the case with random data) the immense gains possible from these
917: searches are expected __not__ to repay their costs. While adjacent arrays are almost all nearly the same size, they
918: likely all contain similar data.
920: Example Usage:
921: The comparison function must follow the `qsort()` comparison function paradigm, returning the sign of the difference
922: between its arguments. If left < right : return -1, if left == right : return 0, if left > right : return 1. The user
923: may also
924: change or reverse the order of the sort by flipping the above. Note that stability of the sort is only guaranteed if
925: the comparison function forms a valid trigraph. For example when sorting an array of type "my_type" in increasing
926: order
928: .vb
929: int increasing_comparison_function(const void *left, const void *right, void *ctx) {
930: my_type l = *(my_type *) left, r = *(my_type *) right;
931: return (l < r) ? -1 : (l > r);
932: }
933: .ve
935: Note the context is unused here but you may use it to pass and subsequently access whatever information required
936: inside the comparison function. The context pointer will unaltered except for any changes made inside the comparison function.
937: Then pass the function
938: .vb
939: PetscTimSort(n, arr, sizeof(arr[0]), increasing_comparison_function, ctx)
940: .ve
942: Fortran Notes:
943: To use this from Fortran you must write a comparison subroutine with 4 arguments which accepts left, right, ctx and
944: returns result. For example
945: .vb
946: subroutine CompareIntegers(left,right,ctx,result)
947: implicit none
949: PetscInt,intent(in) :: left, right
950: type(UserCtx) :: ctx
951: integer,intent(out) :: result
953: if (left < right) then
954: result = -1
955: else if (left == right) then
956: result = 0
957: else
958: result = 1
959: end if
960: return
961: end subroutine CompareIntegers
962: .ve
964: .seealso: `PetscTimSortWithArray()`, `PetscIntSortSemiOrdered()`, `PetscRealSortSemiOrdered()`, `PetscMPIIntSortSemiOrdered()`
965: @*/
966: PetscErrorCode PetscTimSort(PetscInt n, void *arr, size_t size, int (*cmp)(const void *, const void *, void *), void *ctx)
967: {
968: PetscInt stacksize = 0, minrun, runstart = 0, runend = 0;
969: PetscTimSortStack runstack[128];
970: PetscTimSortBuffer buff;
971: /* stacksize = log_phi(n) = log_2(n)/log_2(phi), so 128 is enough for ~5.614e26 elements.
972: It is so unlikely that this limit is reached that this is __never__ checked for */
974: PetscFunctionBegin;
975: /* Compute minrun. Minrun should be (32, 65) such that N/minrun
976: is a power of 2 or one plus a power of 2 */
977: {
978: PetscInt t = n, r = 0;
979: /* r becomes 1 if the least significant bits contain at least one off bit */
980: while (t >= 64) {
981: r |= t & 1;
982: t >>= 1;
983: }
984: minrun = t + r;
985: }
986: if (PetscDefined(USE_DEBUG)) {
987: PetscCall(PetscInfo(NULL, "minrun = %" PetscInt_FMT "\n", minrun));
988: if (n < 64) {
989: PetscCall(PetscInfo(NULL, "n %" PetscInt_FMT " < 64, consider using PetscSortInt() instead\n", n));
990: } else PetscCheck(!(minrun < 32) && !(minrun > 65), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Calculated minrun %" PetscInt_FMT " not in range (32,65)", minrun);
991: }
992: PetscCall(PetscMalloc1((size_t)minrun * size, &buff.ptr));
993: buff.size = (size_t)minrun * size;
994: buff.maxsize = (size_t)n * size;
995: MIN_GALLOP_GLOBAL = MIN_GALLOP_CONST_GLOBAL;
996: while (runstart < n) {
997: /* Check if additional entries are at least partially ordered and build natural run */
998: PetscCall(PetscTimSortBuildRun_Private((char *)arr, buff.ptr, size, cmp, ctx, n, minrun, runstart, &runend));
999: runstack[stacksize].start = runstart;
1000: runstack[stacksize].size = runend - runstart + 1;
1001: PetscCall(PetscTimSortMergeCollapse_Private((char *)arr, size, cmp, ctx, &buff, runstack, &stacksize));
1002: ++stacksize;
1003: runstart = runend + 1;
1004: }
1005: /* Have been inside while, so discard last stacksize++ */
1006: --stacksize;
1007: PetscCall(PetscTimSortForceCollapse_Private((char *)arr, size, cmp, ctx, &buff, runstack, stacksize));
1008: PetscCall(PetscFree(buff.ptr));
1009: MIN_GALLOP_GLOBAL = MIN_GALLOP_CONST_GLOBAL;
1010: PetscFunctionReturn(PETSC_SUCCESS);
1011: }
1013: /*@C
1014: PetscTimSortWithArray - Sorts an array in place in increasing order using Tim Peters <https://bugs.python.org/file4451/timsort.txt> adaptive sorting algorithm and
1015: reorders a second array to match the first. The arrays need not be the same type.
1017: Not Collective
1019: Input Parameters:
1020: + n - number of values
1021: . asize - size in bytes of the datatype held in arr
1022: . bsize - size in bytes of the datatype held in barr
1023: . cmp - function pointer to comparison function
1024: - ctx - optional context to be passed to comparison function, NULL if not needed
1026: Input/Output Parameters:
1027: + arr - array to be sorted, on output it is sorted
1028: - barr - array to be reordered, on output it is reordered
1030: Level: developer
1032: Notes:
1033: The arrays need not be of the same type, however barr MUST contain at least as many elements as arr and the two CANNOT
1034: overlap.
1036: Timsort makes the assumption that input data is already likely partially ordered, or that it contains contiguous
1037: sections (termed 'runs') where the data is locally ordered (but not necessarily globally ordered). It therefore aims
1038: to select slices of the array in such a way that resulting mergesorts operate on near perfectly length-balanced
1039: arrays. To do so it repeatedly triggers attempts throughout to merge adjacent runs.
1041: Should one run continuously "win" a comparison the algorithm begins the "gallop" phase. It will aggressively search
1042: the "winner" for the location of the "losers" next entry (and vice versa) to copy all preceding elements into place in
1043: bulk. However if the data is truly unordered (as is the case with random data) the immense gains possible from these
1044: searches are expected __not__ to repay their costs. While adjacent arrays are almost all nearly the same size, they
1045: likely all contain similar data.
1047: Example Usage:
1048: The comparison function must follow the `qsort()` comparison function paradigm, returning the sign of the difference
1049: between its arguments. If left < right \: return -1, if left == right \: return 0, if left > right \: return 1. The user
1050: may also change or reverse the order of the sort by flipping the above. Note that stability of the sort is only
1051: guaranteed if the comparison function forms a valid trigraph. For example when sorting an array of type "my_type" in
1052: increasing order
1054: .vb
1055: int increasing_comparison_function(const void *left, const void *right, void *ctx) {
1056: my_type l = *(my_type *) left, r = *(my_type *) right;
1057: return (l < r) ? -1 : (l > r);
1058: }
1059: .ve
1061: Note the context is unused here but you may use it to pass and subsequently access whatever information required
1062: inside the comparison function. The context pointer will unaltered except for any changes made inside the comparison function.
1063: Then pass the function
1064: .vb
1065: PetscTimSortWithArray(n, arr, sizeof(arr[0]), barr, sizeof(barr[0]), increasing_comparison_function, ctx)
1066: .ve
1068: Fortran Notes:
1069: To use this from Fortran you must write a comparison subroutine with 4 arguments which accepts left, right, ctx and
1070: returns result. For example
1071: .vb
1072: subroutine CompareIntegers(left,right,ctx,result)
1073: implicit none
1075: PetscInt,intent(in) :: left, right
1076: type(UserCtx) :: ctx
1077: integer,intent(out) :: result
1079: if (left < right) then
1080: result = -1
1081: else if (left == right) then
1082: result = 0
1083: else
1084: result = 1
1085: end if
1086: return
1087: end subroutine CompareIntegers
1088: .ve
1090: .seealso: `PetscTimSort()`, `PetscIntSortSemiOrderedWithArray()`, `PetscRealSortSemiOrderedWithArrayInt()`, `PetscMPIIntSortSemiOrderedWithArray()`
1091: @*/
1092: PetscErrorCode PetscTimSortWithArray(PetscInt n, void *arr, size_t asize, void *barr, size_t bsize, int (*cmp)(const void *, const void *, void *), void *ctx)
1093: {
1094: PetscInt stacksize = 0, minrun, runstart = 0, runend = 0;
1095: PetscTimSortStack runstack[128];
1096: PetscTimSortBuffer abuff, bbuff;
1097: /* stacksize = log_phi(n) = log_2(n)/log_2(phi), so 128 is enough for ~5.614e26 elements.
1098: It is so unlikely that this limit is reached that this is __never__ checked for */
1100: PetscFunctionBegin;
1101: /* Compute minrun. Minrun should be (32, 65) such that N/minrun
1102: is a power of 2 or one plus a power of 2 */
1103: {
1104: PetscInt t = n, r = 0;
1105: /* r becomes 1 if the least significant bits contain at least one off bit */
1106: while (t >= 64) {
1107: r |= t & 1;
1108: t >>= 1;
1109: }
1110: minrun = t + r;
1111: }
1112: if (PetscDefined(USE_DEBUG)) {
1113: PetscCall(PetscInfo(NULL, "minrun = %" PetscInt_FMT "\n", minrun));
1114: PetscCheck(n < 64 || (minrun >= 32 && minrun <= 65), PETSC_COMM_SELF, PETSC_ERR_PLIB, "Calculated minrun %" PetscInt_FMT " not in range (32,65)", minrun);
1115: }
1116: PetscCall(PetscMalloc1((size_t)minrun * asize, &abuff.ptr));
1117: abuff.size = (size_t)minrun * asize;
1118: abuff.maxsize = (size_t)n * asize;
1119: PetscCall(PetscMalloc1((size_t)minrun * bsize, &bbuff.ptr));
1120: bbuff.size = (size_t)minrun * bsize;
1121: bbuff.maxsize = (size_t)n * bsize;
1122: MIN_GALLOP_GLOBAL = MIN_GALLOP_CONST_GLOBAL;
1123: while (runstart < n) {
1124: /* Check if additional entries are at least partially ordered and build natural run */
1125: PetscCall(PetscTimSortBuildRunWithArray_Private((char *)arr, abuff.ptr, asize, (char *)barr, bbuff.ptr, bsize, cmp, ctx, n, minrun, runstart, &runend));
1126: runstack[stacksize].start = runstart;
1127: runstack[stacksize].size = runend - runstart + 1;
1128: PetscCall(PetscTimSortMergeCollapseWithArray_Private((char *)arr, asize, (char *)barr, bsize, cmp, ctx, &abuff, &bbuff, runstack, &stacksize));
1129: ++stacksize;
1130: runstart = runend + 1;
1131: }
1132: /* Have been inside while, so discard last stacksize++ */
1133: --stacksize;
1134: PetscCall(PetscTimSortForceCollapseWithArray_Private((char *)arr, asize, (char *)barr, bsize, cmp, ctx, &abuff, &bbuff, runstack, stacksize));
1135: PetscCall(PetscFree(abuff.ptr));
1136: PetscCall(PetscFree(bbuff.ptr));
1137: MIN_GALLOP_GLOBAL = MIN_GALLOP_CONST_GLOBAL;
1138: PetscFunctionReturn(PETSC_SUCCESS);
1139: }
1141: /*@
1142: PetscIntSortSemiOrdered - Sorts an array of `PetscInt` in place in increasing order.
1144: Not Collective
1146: Input Parameters:
1147: + n - number of values
1148: - arr - array of integers
1150: Output Parameter:
1151: . arr - sorted array of integers
1153: Level: intermediate
1155: Notes:
1156: If the array is less than 64 entries long `PetscSortInt()` is automatically used.
1158: This function serves as an alternative to `PetscSortInt()`. While this function works for any array of integers it is
1159: significantly faster if the array is not totally random. There are exceptions to this and so it is __highly__
1160: recommended that the user benchmark their code to see which routine is fastest.
1162: .seealso: `PetscTimSort()`, `PetscSortInt()`, `PetscSortIntWithPermutation()`
1163: @*/
1164: PetscErrorCode PetscIntSortSemiOrdered(PetscInt n, PetscInt arr[])
1165: {
1166: PetscFunctionBegin;
1167: if (n <= 1) PetscFunctionReturn(PETSC_SUCCESS);
1168: PetscAssertPointer(arr, 2);
1169: if (n < 64) {
1170: PetscCall(PetscSortInt(n, arr));
1171: } else {
1172: PetscCall(PetscTimSort(n, arr, sizeof(PetscInt), Compare_PetscInt_Private, NULL));
1173: }
1174: PetscFunctionReturn(PETSC_SUCCESS);
1175: }
1177: /*@
1178: PetscIntSortSemiOrderedWithArray - Sorts an array of `PetscInt` in place in increasing order and reorders a second
1179: `PetscInt` array to match the first.
1181: Not Collective
1183: Input Parameter:
1184: . n - number of values
1186: Input/Output Parameters:
1187: + arr1 - array of integers to be sorted, modified on output
1188: - arr2 - array of integers to be reordered, modified on output
1190: Level: intermediate
1192: Notes:
1193: The arrays CANNOT overlap.
1195: This function serves as an alternative to `PetscSortIntWithArray()`. While this function works for any array of integers it is
1196: significantly faster if the array is not totally random. There are exceptions to this and so it is __highly__
1197: recommended that the user benchmark their code to see which routine is fastest.
1199: .seealso: `PetscTimSortWithArray()`, `PetscSortIntWithArray()`, `PetscSortIntWithPermutation()`
1200: @*/
1201: PetscErrorCode PetscIntSortSemiOrderedWithArray(PetscInt n, PetscInt arr1[], PetscInt arr2[])
1202: {
1203: PetscFunctionBegin;
1204: if (n <= 1) PetscFunctionReturn(PETSC_SUCCESS);
1205: PetscAssertPointer(arr1, 2);
1206: PetscAssertPointer(arr2, 3);
1207: /* cannot export out to PetscIntSortWithArray here since it isn't stable */
1208: PetscCall(PetscTimSortWithArray(n, arr1, sizeof(PetscInt), arr2, sizeof(PetscInt), Compare_PetscInt_Private, NULL));
1209: PetscFunctionReturn(PETSC_SUCCESS);
1210: }
1212: /*@
1213: PetscMPIIntSortSemiOrdered - Sorts an array of `PetscMPIInt` in place in increasing order.
1215: Not Collective
1217: Input Parameters:
1218: + n - number of values
1219: - arr - array of `PetscMPIInt`
1221: Output Parameter:
1222: . arr - sorted array of integers
1224: Level: intermediate
1226: Notes:
1227: If the array is less than 64 entries long `PetscSortMPIInt()` is automatically used.
1229: This function serves as an alternative to `PetscSortMPIInt()`. While this function works for any array of `PetscMPIInt` it is
1230: significantly faster if the array is not totally random. There are exceptions to this and so it is __highly__
1231: recommended that the user benchmark their code to see which routine is fastest.
1233: .seealso: `PetscTimSort()`, `PetscSortMPIInt()`
1234: @*/
1235: PetscErrorCode PetscMPIIntSortSemiOrdered(PetscInt n, PetscMPIInt arr[])
1236: {
1237: PetscFunctionBegin;
1238: if (n <= 1) PetscFunctionReturn(PETSC_SUCCESS);
1239: PetscAssertPointer(arr, 2);
1240: if (n < 64) {
1241: PetscCall(PetscSortMPIInt(n, arr));
1242: } else {
1243: PetscCall(PetscTimSort(n, arr, sizeof(PetscMPIInt), Compare_PetscMPIInt_Private, NULL));
1244: }
1245: PetscFunctionReturn(PETSC_SUCCESS);
1246: }
1248: /*@
1249: PetscMPIIntSortSemiOrderedWithArray - Sorts an array of `PetscMPIInt` in place in increasing order and reorders a second `PetscMPIInt`
1250: array to match the first.
1252: Not Collective
1254: Input Parameter:
1255: . n - number of values
1257: Input/Output Parameters:
1258: + arr1 - array of integers to be sorted, modified on output
1259: - arr2 - array of integers to be reordered, modified on output
1261: Level: intermediate
1263: Notes:
1264: The arrays CANNOT overlap.
1266: This function serves as an alternative to `PetscSortMPIIntWithArray()`. While this function works for any array of integers it is
1267: significantly faster if the array is not totally random. There are exceptions to this and so it is __highly__
1268: recommended that the user benchmark their code to see which routine is fastest.
1270: .seealso: `PetscTimSortWithArray()`, `PetscSortMPIIntWithArray()`, `PetscSortMPIIntWithPermutation()`
1271: @*/
1272: PetscErrorCode PetscMPIIntSortSemiOrderedWithArray(PetscInt n, PetscMPIInt arr1[], PetscMPIInt arr2[])
1273: {
1274: PetscFunctionBegin;
1275: if (n <= 1) PetscFunctionReturn(PETSC_SUCCESS);
1276: PetscAssertPointer(arr1, 2);
1277: PetscAssertPointer(arr2, 3);
1278: /* cannot export out to PetscMPIIntSortWithArray here since it isn't stable */
1279: PetscCall(PetscTimSortWithArray(n, arr1, sizeof(PetscMPIInt), arr2, sizeof(PetscMPIInt), Compare_PetscMPIInt_Private, NULL));
1280: PetscFunctionReturn(PETSC_SUCCESS);
1281: }
1283: /*@
1284: PetscRealSortSemiOrdered - Sorts an array of `PetscReal` in place in increasing order.
1286: Not Collective
1288: Input Parameters:
1289: + n - number of values
1290: - arr - array of `PetscReal`
1292: Output Parameter:
1293: . arr - sorted array of integers
1295: Level: intermediate
1297: Notes:
1298: If the array is less than 64 entries long `PetscSortReal()` is automatically used.
1300: This function serves as an alternative to `PetscSortReal()`. While this function works for any array of `PetscReal` it is
1301: significantly faster if the array is not totally random. There are exceptions to this and so it is __highly__
1302: recommended that the user benchmark their code to see which routine is fastest.
1304: .seealso: `PetscTimSort()`, `PetscSortReal()`, `PetscSortRealWithPermutation()`
1305: @*/
1306: PetscErrorCode PetscRealSortSemiOrdered(PetscInt n, PetscReal arr[])
1307: {
1308: PetscFunctionBegin;
1309: if (n <= 1) PetscFunctionReturn(PETSC_SUCCESS);
1310: PetscAssertPointer(arr, 2);
1311: if (n < 64) {
1312: PetscCall(PetscSortReal(n, arr));
1313: } else {
1314: PetscCall(PetscTimSort(n, arr, sizeof(PetscReal), Compare_PetscReal_Private, NULL));
1315: }
1316: PetscFunctionReturn(PETSC_SUCCESS);
1317: }
1319: /*@
1320: PetscRealSortSemiOrderedWithArrayInt - Sorts an array of `PetscReal` in place in increasing order and reorders a second
1321: array of `PetscInt` to match the first.
1323: Not Collective
1325: Input Parameter:
1326: . n - number of values
1328: Input/Output Parameters:
1329: + arr1 - array of `PetscReal` to be sorted, modified on output
1330: - arr2 - array of `PetscInt` to be reordered, modified on output
1332: Level: intermediate
1334: Notes:
1335: This function serves as an alternative to `PetscSortRealWithArray()`. While this function works for any array of `PetscReal` it is
1336: significantly faster if the array is not totally random. There are exceptions to this and so it is __highly__
1337: recommended that the user benchmark their code to see which routine is fastest.
1339: .seealso: `PetscTimSortWithArray()`, `PetscSortRealWithArrayInt()`, `PetscSortRealWithPermutation()`
1340: @*/
1341: PetscErrorCode PetscRealSortSemiOrderedWithArrayInt(PetscInt n, PetscReal arr1[], PetscInt arr2[])
1342: {
1343: PetscFunctionBegin;
1344: if (n <= 1) PetscFunctionReturn(PETSC_SUCCESS);
1345: PetscAssertPointer(arr1, 2);
1346: PetscAssertPointer(arr2, 3);
1347: /* cannot export out to PetscRealSortWithArrayInt here since it isn't stable */
1348: PetscCall(PetscTimSortWithArray(n, arr1, sizeof(PetscReal), arr2, sizeof(PetscInt), Compare_PetscReal_Private, NULL));
1349: PetscFunctionReturn(PETSC_SUCCESS);
1350: }