1 /*
2 *******************************************************************************
3 *
4 * Copyright (C) 2003, 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 MIN_QSORT=9, /* from Knuth */
25 STACK_ITEM_SIZE=200
26 };
27
28 /* UComparator convenience implementations ---------------------------------- */
29
30 U_CAPI int32_t U_EXPORT2
uprv_uint16Comparator(const void * context,const void * left,const void * right)31 uprv_uint16Comparator(const void *context, const void *left, const void *right) {
32 return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right;
33 }
34
35 U_CAPI int32_t U_EXPORT2
uprv_int32Comparator(const void * context,const void * left,const void * right)36 uprv_int32Comparator(const void *context, const void *left, const void *right) {
37 return *(const int32_t *)left - *(const int32_t *)right;
38 }
39
40 U_CAPI int32_t U_EXPORT2
uprv_uint32Comparator(const void * context,const void * left,const void * right)41 uprv_uint32Comparator(const void *context, const void *left, const void *right) {
42 uint32_t l=*(const uint32_t *)left, r=*(const uint32_t *)right;
43
44 /* compare directly because (l-r) would overflow the int32_t result */
45 if(l<r) {
46 return -1;
47 } else if(l==r) {
48 return 0;
49 } else /* l>r */ {
50 return 1;
51 }
52 }
53
54 /* Straight insertion sort from Knuth vol. III, pg. 81 ---------------------- */
55
56 static void
doInsertionSort(char * array,int32_t start,int32_t limit,int32_t itemSize,UComparator * cmp,const void * context,void * pv)57 doInsertionSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
58 UComparator *cmp, const void *context, void *pv) {
59 int32_t i, j;
60
61 for(j=start+1; j<limit; ++j) {
62 /* v=array[j] */
63 uprv_memcpy(pv, array+j*itemSize, itemSize);
64
65 for(i=j; i>start; --i) {
66 if(/* v>=array[i-1] */ cmp(context, pv, array+(i-1)*itemSize)>=0) {
67 break;
68 }
69
70 /* array[i]=array[i-1]; */
71 uprv_memcpy(array+i*itemSize, array+(i-1)*itemSize, itemSize);
72 }
73
74 if(i!=j) {
75 /* array[i]=v; */
76 uprv_memcpy(array+i*itemSize, pv, itemSize);
77 }
78 }
79 }
80
81 static void
insertionSort(char * array,int32_t length,int32_t itemSize,UComparator * cmp,const void * context,UErrorCode * pErrorCode)82 insertionSort(char *array, int32_t length, int32_t itemSize,
83 UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
84 UAlignedMemory v[STACK_ITEM_SIZE/sizeof(UAlignedMemory)+1];
85 void *pv;
86
87 /* allocate an intermediate item variable (v) */
88 if(itemSize<=STACK_ITEM_SIZE) {
89 pv=v;
90 } else {
91 pv=uprv_malloc(itemSize);
92 if(pv==NULL) {
93 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
94 return;
95 }
96 }
97
98 doInsertionSort(array, 0, length, itemSize, cmp, context, pv);
99
100 if(pv!=v) {
101 uprv_free(pv);
102 }
103 }
104
105 /* QuickSort ---------------------------------------------------------------- */
106
107 /*
108 * This implementation is semi-recursive:
109 * It recurses for the smaller sub-array to shorten the recursion depth,
110 * and loops for the larger sub-array.
111 *
112 * Loosely after QuickSort algorithms in
113 * Niklaus Wirth
114 * Algorithmen und Datenstrukturen mit Modula-2
115 * B.G. Teubner Stuttgart
116 * 4. Auflage 1986
117 * ISBN 3-519-02260-5
118 */
119 static void
subQuickSort(char * array,int32_t start,int32_t limit,int32_t itemSize,UComparator * cmp,const void * context,void * px,void * pw)120 subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
121 UComparator *cmp, const void *context,
122 void *px, void *pw) {
123 int32_t left, right;
124
125 /* start and left are inclusive, limit and right are exclusive */
126 do {
127 if((start+MIN_QSORT)>=limit) {
128 doInsertionSort(array, start, limit, itemSize, cmp, context, px);
129 break;
130 }
131
132 left=start;
133 right=limit;
134
135 /* x=array[middle] */
136 uprv_memcpy(px, array+((start+limit)/2)*itemSize, itemSize);
137
138 do {
139 while(/* array[left]<x */
140 cmp(context, array+left*itemSize, px)<0
141 ) {
142 ++left;
143 }
144 while(/* x<array[right-1] */
145 cmp(context, px, array+(right-1)*itemSize)<0
146 ) {
147 --right;
148 }
149
150 /* swap array[left] and array[right-1] via w; ++left; --right */
151 if(left<right) {
152 --right;
153
154 if(left<right) {
155 uprv_memcpy(pw, array+left*itemSize, itemSize);
156 uprv_memcpy(array+left*itemSize, array+right*itemSize, itemSize);
157 uprv_memcpy(array+right*itemSize, pw, itemSize);
158 }
159
160 ++left;
161 }
162 } while(left<right);
163
164 /* sort sub-arrays */
165 if((right-start)<(limit-left)) {
166 /* sort [start..right[ */
167 if(start<(right-1)) {
168 subQuickSort(array, start, right, itemSize, cmp, context, px, pw);
169 }
170
171 /* sort [left..limit[ */
172 start=left;
173 } else {
174 /* sort [left..limit[ */
175 if(left<(limit-1)) {
176 subQuickSort(array, left, limit, itemSize, cmp, context, px, pw);
177 }
178
179 /* sort [start..right[ */
180 limit=right;
181 }
182 } while(start<(limit-1));
183 }
184
185 static void
quickSort(char * array,int32_t length,int32_t itemSize,UComparator * cmp,const void * context,UErrorCode * pErrorCode)186 quickSort(char *array, int32_t length, int32_t itemSize,
187 UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
188 UAlignedMemory xw[(2*STACK_ITEM_SIZE)/sizeof(UAlignedMemory)+1];
189 void *p;
190
191 /* allocate two intermediate item variables (x and w) */
192 if(itemSize<=STACK_ITEM_SIZE) {
193 p=xw;
194 } else {
195 p=uprv_malloc(2*itemSize);
196 if(p==NULL) {
197 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
198 return;
199 }
200 }
201
202 subQuickSort(array, 0, length, itemSize,
203 cmp, context, p, (char *)p+itemSize);
204
205 if(p!=xw) {
206 uprv_free(p);
207 }
208 }
209
210 /* uprv_sortArray() API ----------------------------------------------------- */
211
212 /*
213 * Check arguments, select an appropriate implementation,
214 * cast the array to char * so that array+i*itemSize works.
215 */
216 U_CAPI void U_EXPORT2
uprv_sortArray(void * array,int32_t length,int32_t itemSize,UComparator * cmp,const void * context,UBool sortStable,UErrorCode * pErrorCode)217 uprv_sortArray(void *array, int32_t length, int32_t itemSize,
218 UComparator *cmp, const void *context,
219 UBool sortStable, UErrorCode *pErrorCode) {
220 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
221 return;
222 }
223 if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) {
224 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
225 return;
226 }
227
228 if(length<=1) {
229 return;
230 } else if(length<MIN_QSORT || sortStable) {
231 insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode);
232 /* could add heapSort or similar for stable sorting of longer arrays */
233 } else {
234 quickSort((char *)array, length, itemSize, cmp, context, pErrorCode);
235 }
236 }
237