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