1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html
3/*
4*******************************************************************************
5*
6* Copyright (C) 2003-2013, International Business Machines
7* Corporation and others. All Rights Reserved.
8*
9*******************************************************************************
10* file name: uarrsort.c
11* encoding: UTF-8
12* tab size: 8 (not used)
13* indentation:4
14*
15* created on: 2003aug04
16* created by: Markus W. Scherer
17*
18* Internal function for sorting arrays.
19*/
20
21#include "unicode/utypes.h"
22#include "cmemory.h"
23#include "uarrsort.h"
24
25enum {
26 /**
27 * "from Knuth"
28 *
29 * A binary search over 8 items performs 4 comparisons:
30 * log2(8)=3 to subdivide, +1 to check for equality.
31 * A linear search over 8 items on average also performs 4 comparisons.
32 */
33 MIN_QSORT=9,
34 STACK_ITEM_SIZE=200
35};
36
37static constexpr int32_t sizeInMaxAlignTs(int32_t sizeInBytes) {
38 return (sizeInBytes + sizeof(max_align_t) - 1) / sizeof(max_align_t);
39}
40
41/* UComparator convenience implementations ---------------------------------- */
42
43U_CAPI int32_t U_EXPORT2
44uprv_uint16Comparator(const void *context, const void *left, const void *right) {
45 (void)context;
46 return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right;
47}
48
49U_CAPI int32_t U_EXPORT2
50uprv_int32Comparator(const void *context, const void *left, const void *right) {
51 (void)context;
52 return *(const int32_t *)left - *(const int32_t *)right;
53}
54
55U_CAPI int32_t U_EXPORT2
56uprv_uint32Comparator(const void *context, const void *left, const void *right) {
57 (void)context;
58 uint32_t l=*(const uint32_t *)left, r=*(const uint32_t *)right;
59
60 /* compare directly because (l-r) would overflow the int32_t result */
61 if(l<r) {
62 return -1;
63 } else if(l==r) {
64 return 0;
65 } else /* l>r */ {
66 return 1;
67 }
68}
69
70/* Insertion sort using binary search --------------------------------------- */
71
72U_CAPI int32_t U_EXPORT2
73uprv_stableBinarySearch(char *array, int32_t limit, void *item, int32_t itemSize,
74 UComparator *cmp, const void *context) {
75 int32_t start=0;
76 UBool found=FALSE;
77
78 /* Binary search until we get down to a tiny sub-array. */
79 while((limit-start)>=MIN_QSORT) {
80 int32_t i=(start+limit)/2;
81 int32_t diff=cmp(context, item, array+i*itemSize);
82 if(diff==0) {
83 /*
84 * Found the item. We look for the *last* occurrence of such
85 * an item, for stable sorting.
86 * If we knew that there will be only few equal items,
87 * we could break now and enter the linear search.
88 * However, if there are many equal items, then it should be
89 * faster to continue with the binary search.
90 * It seems likely that we either have all unique items
91 * (where found will never become TRUE in the insertion sort)
92 * or potentially many duplicates.
93 */
94 found=TRUE;
95 start=i+1;
96 } else if(diff<0) {
97 limit=i;
98 } else {
99 start=i;
100 }
101 }
102
103 /* Linear search over the remaining tiny sub-array. */
104 while(start<limit) {
105 int32_t diff=cmp(context, item, array+start*itemSize);
106 if(diff==0) {
107 found=TRUE;
108 } else if(diff<0) {
109 break;
110 }
111 ++start;
112 }
113 return found ? (start-1) : ~start;
114}
115
116static void
117doInsertionSort(char *array, int32_t length, int32_t itemSize,
118 UComparator *cmp, const void *context, void *pv) {
119 int32_t j;
120
121 for(j=1; j<length; ++j) {
122 char *item=array+j*itemSize;
123 int32_t insertionPoint=uprv_stableBinarySearch(array, j, item, itemSize, cmp, context);
124 if(insertionPoint<0) {
125 insertionPoint=~insertionPoint;
126 } else {
127 ++insertionPoint; /* one past the last equal item */
128 }
129 if(insertionPoint<j) {
130 char *dest=array+insertionPoint*itemSize;
131 uprv_memcpy(pv, item, itemSize); /* v=array[j] */
132 uprv_memmove(dest+itemSize, dest, (j-insertionPoint)*(size_t)itemSize);
133 uprv_memcpy(dest, pv, itemSize); /* array[insertionPoint]=v */
134 }
135 }
136}
137
138static void
139insertionSort(char *array, int32_t length, int32_t itemSize,
140 UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
141
142 icu::MaybeStackArray<max_align_t, sizeInMaxAlignTs(STACK_ITEM_SIZE)> v;
143 if (sizeInMaxAlignTs(itemSize) > v.getCapacity() &&
144 v.resize(sizeInMaxAlignTs(itemSize)) == nullptr) {
145 *pErrorCode = U_MEMORY_ALLOCATION_ERROR;
146 return;
147 }
148
149 doInsertionSort(array, length, itemSize, cmp, context, v.getAlias());
150}
151
152/* QuickSort ---------------------------------------------------------------- */
153
154/*
155 * This implementation is semi-recursive:
156 * It recurses for the smaller sub-array to shorten the recursion depth,
157 * and loops for the larger sub-array.
158 *
159 * Loosely after QuickSort algorithms in
160 * Niklaus Wirth
161 * Algorithmen und Datenstrukturen mit Modula-2
162 * B.G. Teubner Stuttgart
163 * 4. Auflage 1986
164 * ISBN 3-519-02260-5
165 */
166static void
167subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
168 UComparator *cmp, const void *context,
169 void *px, void *pw) {
170 int32_t left, right;
171
172 /* start and left are inclusive, limit and right are exclusive */
173 do {
174 if((start+MIN_QSORT)>=limit) {
175 doInsertionSort(array+start*itemSize, limit-start, itemSize, cmp, context, px);
176 break;
177 }
178
179 left=start;
180 right=limit;
181
182 /* x=array[middle] */
183 uprv_memcpy(px, array+(size_t)((start+limit)/2)*itemSize, itemSize);
184
185 do {
186 while(/* array[left]<x */
187 cmp(context, array+left*itemSize, px)<0
188 ) {
189 ++left;
190 }
191 while(/* x<array[right-1] */
192 cmp(context, px, array+(right-1)*itemSize)<0
193 ) {
194 --right;
195 }
196
197 /* swap array[left] and array[right-1] via w; ++left; --right */
198 if(left<right) {
199 --right;
200
201 if(left<right) {
202 uprv_memcpy(pw, array+(size_t)left*itemSize, itemSize);
203 uprv_memcpy(array+(size_t)left*itemSize, array+(size_t)right*itemSize, itemSize);
204 uprv_memcpy(array+(size_t)right*itemSize, pw, itemSize);
205 }
206
207 ++left;
208 }
209 } while(left<right);
210
211 /* sort sub-arrays */
212 if((right-start)<(limit-left)) {
213 /* sort [start..right[ */
214 if(start<(right-1)) {
215 subQuickSort(array, start, right, itemSize, cmp, context, px, pw);
216 }
217
218 /* sort [left..limit[ */
219 start=left;
220 } else {
221 /* sort [left..limit[ */
222 if(left<(limit-1)) {
223 subQuickSort(array, left, limit, itemSize, cmp, context, px, pw);
224 }
225
226 /* sort [start..right[ */
227 limit=right;
228 }
229 } while(start<(limit-1));
230}
231
232static void
233quickSort(char *array, int32_t length, int32_t itemSize,
234 UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
235 /* allocate two intermediate item variables (x and w) */
236 icu::MaybeStackArray<max_align_t, sizeInMaxAlignTs(STACK_ITEM_SIZE) * 2> xw;
237 if(sizeInMaxAlignTs(itemSize)*2 > xw.getCapacity() &&
238 xw.resize(sizeInMaxAlignTs(itemSize) * 2) == nullptr) {
239 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
240 return;
241 }
242
243 subQuickSort(array, 0, length, itemSize, cmp, context,
244 xw.getAlias(), xw.getAlias() + sizeInMaxAlignTs(itemSize));
245}
246
247/* uprv_sortArray() API ----------------------------------------------------- */
248
249/*
250 * Check arguments, select an appropriate implementation,
251 * cast the array to char * so that array+i*itemSize works.
252 */
253U_CAPI void U_EXPORT2
254uprv_sortArray(void *array, int32_t length, int32_t itemSize,
255 UComparator *cmp, const void *context,
256 UBool sortStable, UErrorCode *pErrorCode) {
257 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
258 return;
259 }
260 if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) {
261 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
262 return;
263 }
264
265 if(length<=1) {
266 return;
267 } else if(length<MIN_QSORT || sortStable) {
268 insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode);
269 } else {
270 quickSort((char *)array, length, itemSize, cmp, context, pErrorCode);
271 }
272}
273