/src/skia/third_party/externals/icu/source/common/uarrsort.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | |
39 | 0 | static constexpr int32_t sizeInMaxAlignTs(int32_t sizeInBytes) { |
40 | 0 | return (sizeInBytes + sizeof(std::max_align_t) - 1) / sizeof(std::max_align_t); |
41 | 0 | } |
42 | | |
43 | | /* UComparator convenience implementations ---------------------------------- */ |
44 | | |
45 | | U_CAPI int32_t U_EXPORT2 |
46 | 0 | uprv_uint16Comparator(const void *context, const void *left, const void *right) { |
47 | 0 | (void)context; |
48 | 0 | return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right; |
49 | 0 | } |
50 | | |
51 | | U_CAPI int32_t U_EXPORT2 |
52 | 0 | uprv_int32Comparator(const void *context, const void *left, const void *right) { |
53 | 0 | (void)context; |
54 | 0 | return *(const int32_t *)left - *(const int32_t *)right; |
55 | 0 | } |
56 | | |
57 | | U_CAPI int32_t U_EXPORT2 |
58 | 0 | uprv_uint32Comparator(const void *context, const void *left, const void *right) { |
59 | 0 | (void)context; |
60 | 0 | 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 | 0 | if(l<r) { |
64 | 0 | return -1; |
65 | 0 | } else if(l==r) { |
66 | 0 | return 0; |
67 | 0 | } else /* l>r */ { |
68 | 0 | return 1; |
69 | 0 | } |
70 | 0 | } |
71 | | |
72 | | /* Insertion sort using binary search --------------------------------------- */ |
73 | | |
74 | | U_CAPI int32_t U_EXPORT2 |
75 | | uprv_stableBinarySearch(char *array, int32_t limit, void *item, int32_t itemSize, |
76 | 0 | UComparator *cmp, const void *context) { |
77 | 0 | int32_t start=0; |
78 | 0 | UBool found=FALSE; |
79 | | |
80 | | /* Binary search until we get down to a tiny sub-array. */ |
81 | 0 | while((limit-start)>=MIN_QSORT) { |
82 | 0 | int32_t i=(start+limit)/2; |
83 | 0 | int32_t diff=cmp(context, item, array+i*itemSize); |
84 | 0 | 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 | 0 | found=TRUE; |
97 | 0 | start=i+1; |
98 | 0 | } else if(diff<0) { |
99 | 0 | limit=i; |
100 | 0 | } else { |
101 | 0 | start=i; |
102 | 0 | } |
103 | 0 | } |
104 | | |
105 | | /* Linear search over the remaining tiny sub-array. */ |
106 | 0 | while(start<limit) { |
107 | 0 | int32_t diff=cmp(context, item, array+start*itemSize); |
108 | 0 | if(diff==0) { |
109 | 0 | found=TRUE; |
110 | 0 | } else if(diff<0) { |
111 | 0 | break; |
112 | 0 | } |
113 | 0 | ++start; |
114 | 0 | } |
115 | 0 | return found ? (start-1) : ~start; |
116 | 0 | } |
117 | | |
118 | | static void |
119 | | doInsertionSort(char *array, int32_t length, int32_t itemSize, |
120 | 0 | UComparator *cmp, const void *context, void *pv) { |
121 | 0 | int32_t j; |
122 | |
|
123 | 0 | for(j=1; j<length; ++j) { |
124 | 0 | char *item=array+j*itemSize; |
125 | 0 | int32_t insertionPoint=uprv_stableBinarySearch(array, j, item, itemSize, cmp, context); |
126 | 0 | if(insertionPoint<0) { |
127 | 0 | insertionPoint=~insertionPoint; |
128 | 0 | } else { |
129 | 0 | ++insertionPoint; /* one past the last equal item */ |
130 | 0 | } |
131 | 0 | if(insertionPoint<j) { |
132 | 0 | char *dest=array+insertionPoint*itemSize; |
133 | 0 | uprv_memcpy(pv, item, itemSize); /* v=array[j] */ |
134 | 0 | uprv_memmove(dest+itemSize, dest, (j-insertionPoint)*(size_t)itemSize); |
135 | 0 | uprv_memcpy(dest, pv, itemSize); /* array[insertionPoint]=v */ |
136 | 0 | } |
137 | 0 | } |
138 | 0 | } |
139 | | |
140 | | static void |
141 | | insertionSort(char *array, int32_t length, int32_t itemSize, |
142 | 0 | UComparator *cmp, const void *context, UErrorCode *pErrorCode) { |
143 | |
|
144 | 0 | icu::MaybeStackArray<std::max_align_t, sizeInMaxAlignTs(STACK_ITEM_SIZE)> v; |
145 | 0 | if (sizeInMaxAlignTs(itemSize) > v.getCapacity() && |
146 | 0 | v.resize(sizeInMaxAlignTs(itemSize)) == nullptr) { |
147 | 0 | *pErrorCode = U_MEMORY_ALLOCATION_ERROR; |
148 | 0 | return; |
149 | 0 | } |
150 | | |
151 | 0 | doInsertionSort(array, length, itemSize, cmp, context, v.getAlias()); |
152 | 0 | } |
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 |
169 | | subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize, |
170 | | UComparator *cmp, const void *context, |
171 | 0 | void *px, void *pw) { |
172 | 0 | int32_t left, right; |
173 | | |
174 | | /* start and left are inclusive, limit and right are exclusive */ |
175 | 0 | do { |
176 | 0 | if((start+MIN_QSORT)>=limit) { |
177 | 0 | doInsertionSort(array+start*itemSize, limit-start, itemSize, cmp, context, px); |
178 | 0 | break; |
179 | 0 | } |
180 | | |
181 | 0 | left=start; |
182 | 0 | right=limit; |
183 | | |
184 | | /* x=array[middle] */ |
185 | 0 | uprv_memcpy(px, array+(size_t)((start+limit)/2)*itemSize, itemSize); |
186 | |
|
187 | 0 | do { |
188 | 0 | while(/* array[left]<x */ |
189 | 0 | cmp(context, array+left*itemSize, px)<0 |
190 | 0 | ) { |
191 | 0 | ++left; |
192 | 0 | } |
193 | 0 | while(/* x<array[right-1] */ |
194 | 0 | cmp(context, px, array+(right-1)*itemSize)<0 |
195 | 0 | ) { |
196 | 0 | --right; |
197 | 0 | } |
198 | | |
199 | | /* swap array[left] and array[right-1] via w; ++left; --right */ |
200 | 0 | if(left<right) { |
201 | 0 | --right; |
202 | |
|
203 | 0 | if(left<right) { |
204 | 0 | uprv_memcpy(pw, array+(size_t)left*itemSize, itemSize); |
205 | 0 | uprv_memcpy(array+(size_t)left*itemSize, array+(size_t)right*itemSize, itemSize); |
206 | 0 | uprv_memcpy(array+(size_t)right*itemSize, pw, itemSize); |
207 | 0 | } |
208 | |
|
209 | 0 | ++left; |
210 | 0 | } |
211 | 0 | } while(left<right); |
212 | | |
213 | | /* sort sub-arrays */ |
214 | 0 | if((right-start)<(limit-left)) { |
215 | | /* sort [start..right[ */ |
216 | 0 | if(start<(right-1)) { |
217 | 0 | subQuickSort(array, start, right, itemSize, cmp, context, px, pw); |
218 | 0 | } |
219 | | |
220 | | /* sort [left..limit[ */ |
221 | 0 | start=left; |
222 | 0 | } else { |
223 | | /* sort [left..limit[ */ |
224 | 0 | if(left<(limit-1)) { |
225 | 0 | subQuickSort(array, left, limit, itemSize, cmp, context, px, pw); |
226 | 0 | } |
227 | | |
228 | | /* sort [start..right[ */ |
229 | 0 | limit=right; |
230 | 0 | } |
231 | 0 | } while(start<(limit-1)); |
232 | 0 | } |
233 | | |
234 | | static void |
235 | | quickSort(char *array, int32_t length, int32_t itemSize, |
236 | 0 | UComparator *cmp, const void *context, UErrorCode *pErrorCode) { |
237 | | /* allocate two intermediate item variables (x and w) */ |
238 | 0 | icu::MaybeStackArray<std::max_align_t, sizeInMaxAlignTs(STACK_ITEM_SIZE) * 2> xw; |
239 | 0 | if(sizeInMaxAlignTs(itemSize)*2 > xw.getCapacity() && |
240 | 0 | xw.resize(sizeInMaxAlignTs(itemSize) * 2) == nullptr) { |
241 | 0 | *pErrorCode=U_MEMORY_ALLOCATION_ERROR; |
242 | 0 | return; |
243 | 0 | } |
244 | | |
245 | 0 | subQuickSort(array, 0, length, itemSize, cmp, context, |
246 | 0 | xw.getAlias(), xw.getAlias() + sizeInMaxAlignTs(itemSize)); |
247 | 0 | } |
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 |
256 | | uprv_sortArray(void *array, int32_t length, int32_t itemSize, |
257 | | UComparator *cmp, const void *context, |
258 | 0 | UBool sortStable, UErrorCode *pErrorCode) { |
259 | 0 | if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) { |
260 | 0 | return; |
261 | 0 | } |
262 | 0 | if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) { |
263 | 0 | *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; |
264 | 0 | return; |
265 | 0 | } |
266 | | |
267 | 0 | if(length<=1) { |
268 | 0 | return; |
269 | 0 | } else if(length<MIN_QSORT || sortStable) { |
270 | 0 | insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode); |
271 | 0 | } else { |
272 | 0 | quickSort((char *)array, length, itemSize, cmp, context, pErrorCode); |
273 | 0 | } |
274 | 0 | } |