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