68 #define TwoWayPartition1(X, pivot, t1, lo, hi, l, r) \  argument
73       while (X[l] < pivot) l++; \
74       while (X[r] > pivot) r--; \
79       SWAP1(X[l], X[r], t1); \
101 #define TwoWayPartitionReverse1(X, pivot, t1, lo, hi, l, r) \  argument
106       while (X[l] > pivot) l++; \
107       while (X[r] < pivot) r--; \
112       SWAP1(X[l], X[r], t1); \
118 #define TwoWayPartition2(X, Y, pivot, t1, t2, lo, hi, l, r) \  argument
123       while (X[l] < pivot) l++; \
124       while (X[r] > pivot) r--; \
129       SWAP2(X[l], X[r], Y[l], Y[r], t1, t2); \
135 #define TwoWayPartition3(X, Y, Z, pivot, t1, t2, t3, lo, hi, l, r) \  argument
140       while (X[l] < pivot) l++; \
141       while (X[r] > pivot) r--; \
146       SWAP3(X[l], X[r], Y[l], Y[r], Z[l], Z[r], t1, t2, t3); \
153 #define QuickSort1(FuncName, X, n, pivot, t1) \  argument
158         pivot = X[i]; \
160           if (pivot > X[j]) { \
161             SWAP1(X[i], X[j], t1); \
162             pivot = X[i]; \
167       p     = MEDIAN(X, hi); \
168       pivot = X[p]; \
169       TwoWayPartition1(X, pivot, t1, 0, hi, l, r); \
170       PetscCall(FuncName(l, X)); \
171       PetscCall(FuncName(hi - r + 1, X + r)); \
176 #define QuickSortReverse1(FuncName, X, n, pivot, t1) \  argument
181         pivot = X[i]; \
183           if (pivot < X[j]) { \
184             SWAP1(X[i], X[j], t1); \
185             pivot = X[i]; \
190       p     = MEDIAN(X, hi); \
191       pivot = X[p]; \
192       TwoWayPartitionReverse1(X, pivot, t1, 0, hi, l, r); \
193       PetscCall(FuncName(l, X)); \
194       PetscCall(FuncName(hi - r + 1, X + r)); \
198 #define QuickSort2(FuncName, X, Y, n, pivot, t1, t2) \  argument
203         pivot = X[i]; \
205           if (pivot > X[j]) { \
206             SWAP2(X[i], X[j], Y[i], Y[j], t1, t2); \
207             pivot = X[i]; \
212       p     = MEDIAN(X, hi); \
213       pivot = X[p]; \
214       TwoWayPartition2(X, Y, pivot, t1, t2, 0, hi, l, r); \
215       PetscCall(FuncName(l, X, Y)); \
216       PetscCall(FuncName(hi - r + 1, X + r, Y + r)); \
220 #define QuickSort3(FuncName, X, Y, Z, n, pivot, t1, t2, t3) \  argument
225         pivot = X[i]; \
227           if (pivot > X[j]) { \
228             SWAP3(X[i], X[j], Y[i], Y[j], Z[i], Z[j], t1, t2, t3); \
229             pivot = X[i]; \
234       p     = MEDIAN(X, hi); \
235       pivot = X[p]; \
236       TwoWayPartition3(X, Y, Z, pivot, t1, t2, t3, 0, hi, l, r); \
237       PetscCall(FuncName(l, X, Y, Z)); \
238       PetscCall(FuncName(hi - r + 1, X + r, Y + r, Z + r)); \
258 PetscErrorCode PetscSortedInt(PetscCount n, const PetscInt X[], PetscBool *sorted)  in PetscSortedInt()  argument
261   if (n) PetscAssertPointer(X, 2);  in PetscSortedInt()
263   PetscSorted(n, X, *sorted);  in PetscSortedInt()
283 PetscErrorCode PetscSortedInt64(PetscCount n, const PetscInt64 X[], PetscBool *sorted)  in PetscSortedInt64()  argument
286   if (n) PetscAssertPointer(X, 2);  in PetscSortedInt64()
288   PetscSorted(n, X, *sorted);  in PetscSortedInt64()
310 PetscErrorCode PetscSortInt(PetscCount n, PetscInt X[])  in PetscSortInt()  argument
315   if (n) PetscAssertPointer(X, 2);  in PetscSortInt()
317   QuickSort1(PetscSortInt, X, N, pivot, t1);  in PetscSortInt()
337 PetscErrorCode PetscSortInt64(PetscCount n, PetscInt64 X[])  in PetscSortInt64()  argument
342   if (n) PetscAssertPointer(X, 2);  in PetscSortInt64()
343   QuickSort1(PetscSortInt64, X, n, pivot, t1);  in PetscSortInt64()
363 PetscErrorCode PetscSortCount(PetscCount n, PetscCount X[])  in PetscSortCount()  argument
368   if (n) PetscAssertPointer(X, 2);  in PetscSortCount()
369   QuickSort1(PetscSortCount, X, n, pivot, t1);  in PetscSortCount()
386 PetscErrorCode PetscSortReverseInt(PetscCount n, PetscInt X[])  in PetscSortReverseInt()  argument
391   if (n) PetscAssertPointer(X, 2);  in PetscSortReverseInt()
392   QuickSortReverse1(PetscSortReverseInt, X, n, pivot, t1);  in PetscSortReverseInt()
412 PetscErrorCode PetscSortedRemoveDupsInt(PetscInt *n, PetscInt X[])  in PetscSortedRemoveDupsInt()  argument
418   PetscCheckSorted(*n, X);  in PetscSortedRemoveDupsInt()
420     if (X[b + s + 1] != X[b]) {  in PetscSortedRemoveDupsInt()
421       X[b + 1] = X[b + s + 1];  in PetscSortedRemoveDupsInt()
445 PetscErrorCode PetscSortedCheckDupsInt(PetscCount n, const PetscInt X[], PetscBool *flg)  in PetscSortedCheckDupsInt()  argument
450   PetscCheckSorted(n, X);  in PetscSortedCheckDupsInt()
453     if (X[i + 1] == X[i]) {  in PetscSortedCheckDupsInt()
477 PetscErrorCode PetscSortedCheckDupsCount(PetscCount n, const PetscCount X[], PetscBool *flg)  in PetscSortedCheckDupsCount()  argument
482   PetscCheckSorted(n, X);  in PetscSortedCheckDupsCount()
485     if (X[i + 1] == X[i]) {  in PetscSortedCheckDupsCount()
509 PetscErrorCode PetscSortRemoveDupsInt(PetscInt *n, PetscInt X[])  in PetscSortRemoveDupsInt()  argument
513   PetscCall(PetscSortInt(*n, X));  in PetscSortRemoveDupsInt()
514   PetscCall(PetscSortedRemoveDupsInt(n, X));  in PetscSortRemoveDupsInt()
535 PetscErrorCode PetscFindInt(PetscInt key, PetscCount n, const PetscInt X[], PetscInt *loc)  in PetscFindInt()  argument
545   PetscAssertPointer(X, 3);  in PetscFindInt()
549 …X[lo] <= X[mid] && X[mid] <= X[hi - 1], PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Input array was not…  in PetscFindInt()
550     if (key < X[mid]) hi = mid;  in PetscFindInt()
553   *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1);  in PetscFindInt()
574 PetscErrorCode PetscFindCount(PetscCount key, PetscCount n, const PetscCount X[], PetscCount *loc)  in PetscFindCount()  argument
584   PetscAssertPointer(X, 3);  in PetscFindCount()
588 …X[lo] <= X[mid] && X[mid] <= X[hi - 1], PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Input array was not…  in PetscFindCount()
589     if (key < X[mid]) hi = mid;  in PetscFindCount()
592   *loc = key == X[lo] ? lo : -(lo + (key > X[lo]) + 1);  in PetscFindCount()
612 PetscErrorCode PetscCheckDupsInt(PetscInt n, const PetscInt X[], PetscBool *dups)  in PetscCheckDupsInt()  argument
619   if (n) PetscAssertPointer(X, 2);  in PetscCheckDupsInt()
626       PetscCall(PetscHSetIQueryAdd(ht, X[i], &missing));  in PetscCheckDupsInt()
654 PetscErrorCode PetscFindMPIInt(PetscMPIInt key, PetscCount n, const PetscMPIInt X[], PetscInt *loc)  in PetscFindMPIInt()  argument
664   PetscAssertPointer(X, 3);  in PetscFindMPIInt()
667 …Assert(X[lo] <= X[mid] && X[mid] <= X[hi - 1], PETSC_COMM_SELF, PETSC_ERR_ARG_WRONG, "Input array …  in PetscFindMPIInt()
668     if (key < X[mid]) hi = mid;  in PetscFindMPIInt()
671   PetscCall(PetscIntCast(key == X[lo] ? lo : -(lo + (MPIU_Count)(key > X[lo]) + 1), loc));  in PetscFindMPIInt()
690 PetscErrorCode PetscSortIntWithArray(PetscCount n, PetscInt X[], PetscInt Y[])  in PetscSortIntWithArray()  argument
695   QuickSort2(PetscSortIntWithArray, X, Y, n, pivot, t1, t2);  in PetscSortIntWithArray()
715 PetscErrorCode PetscSortIntWithArrayPair(PetscCount n, PetscInt X[], PetscInt Y[], PetscInt Z[])  in PetscSortIntWithArrayPair()  argument
720   QuickSort3(PetscSortIntWithArrayPair, X, Y, Z, n, pivot, t1, t2, t3);  in PetscSortIntWithArrayPair()
739 PetscErrorCode PetscSortIntWithMPIIntArray(PetscCount n, PetscInt X[], PetscMPIInt Y[])  in PetscSortIntWithMPIIntArray()  argument
745   QuickSort2(PetscSortIntWithMPIIntArray, X, Y, n, pivot, t1, t2);  in PetscSortIntWithMPIIntArray()
764 PetscErrorCode PetscSortIntWithCountArray(PetscCount n, PetscInt X[], PetscCount Y[])  in PetscSortIntWithCountArray()  argument
770   QuickSort2(PetscSortIntWithCountArray, X, Y, n, pivot, t1, t2);  in PetscSortIntWithCountArray()
793 PetscErrorCode PetscSortIntWithIntCountArrayPair(PetscCount n, PetscInt X[], PetscInt Y[], PetscCou…  in PetscSortIntWithIntCountArrayPair()  argument
799   QuickSort3(PetscSortIntWithIntCountArrayPair, X, Y, Z, n, pivot, t1, t2, t3);  in PetscSortIntWithIntCountArrayPair()
819 PetscErrorCode PetscSortedMPIInt(PetscCount n, const PetscMPIInt X[], PetscBool *sorted)  in PetscSortedMPIInt()  argument
822   PetscSorted(n, X, *sorted);  in PetscSortedMPIInt()
844 PetscErrorCode PetscSortMPIInt(PetscCount n, PetscMPIInt X[])  in PetscSortMPIInt()  argument
849   QuickSort1(PetscSortMPIInt, X, n, pivot, t1);  in PetscSortMPIInt()
869 PetscErrorCode PetscSortRemoveDupsMPIInt(PetscInt *n, PetscMPIInt X[])  in PetscSortRemoveDupsMPIInt()  argument
874   PetscCall(PetscSortMPIInt(N, X));  in PetscSortRemoveDupsMPIInt()
876     if (X[b + s + 1] != X[b]) {  in PetscSortRemoveDupsMPIInt()
877       X[b + 1] = X[b + s + 1];  in PetscSortRemoveDupsMPIInt()
900 PetscErrorCode PetscSortMPIIntWithArray(PetscCount n, PetscMPIInt X[], PetscMPIInt Y[])  in PetscSortMPIIntWithArray()  argument
905   QuickSort2(PetscSortMPIIntWithArray, X, Y, n, pivot, t1, t2);  in PetscSortMPIIntWithArray()
927 PetscErrorCode PetscSortMPIIntWithIntArray(PetscCount n, PetscMPIInt X[], PetscInt Y[])  in PetscSortMPIIntWithIntArray()  argument
933   QuickSort2(PetscSortMPIIntWithIntArray, X, Y, n, pivot, t1, t2);  in PetscSortMPIIntWithIntArray()
952 PetscErrorCode PetscSortIntWithScalarArray(PetscCount n, PetscInt X[], PetscScalar Y[])  in PetscSortIntWithScalarArray()  argument
958   QuickSort2(PetscSortIntWithScalarArray, X, Y, n, pivot, t1, t2);  in PetscSortIntWithScalarArray()
980 PetscErrorCode PetscSortIntWithDataArray(PetscCount n, PetscInt X[], void *Y, size_t size, void *t2)  in PetscSortIntWithDataArray()  argument
989       pivot = X[i];  in PetscSortIntWithDataArray()
991         if (pivot > X[j]) {  in PetscSortIntWithDataArray()
992           SWAP2Data(X[i], X[j], YY + size * i, YY + size * j, t1, t2, size);  in PetscSortIntWithDataArray()
993           pivot = X[i];  in PetscSortIntWithDataArray()
1001     pivot = X[MEDIAN(X, hi)];  in PetscSortIntWithDataArray()
1003       while (X[l] < pivot) l++;  in PetscSortIntWithDataArray()
1004       while (X[r] > pivot) r--;  in PetscSortIntWithDataArray()
1009       SWAP2Data(X[l], X[r], YY + size * l, YY + size * r, t1, t2, size);  in PetscSortIntWithDataArray()
1013     PetscCall(PetscSortIntWithDataArray(l, X, Y, size, t2));  in PetscSortIntWithDataArray()
1014     PetscCall(PetscSortIntWithDataArray(hi - r + 1, X + r, YY + size * r, size, t2));  in PetscSortIntWithDataArray()