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 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 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 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 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 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 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 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 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 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
