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