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