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