1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/intl/icu/source/common/uarrsort.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,283 @@
1.4 +/*
1.5 +*******************************************************************************
1.6 +*
1.7 +* Copyright (C) 2003-2013, International Business Machines
1.8 +* Corporation and others. All Rights Reserved.
1.9 +*
1.10 +*******************************************************************************
1.11 +* file name: uarrsort.c
1.12 +* encoding: US-ASCII
1.13 +* tab size: 8 (not used)
1.14 +* indentation:4
1.15 +*
1.16 +* created on: 2003aug04
1.17 +* created by: Markus W. Scherer
1.18 +*
1.19 +* Internal function for sorting arrays.
1.20 +*/
1.21 +
1.22 +#include "unicode/utypes.h"
1.23 +#include "cmemory.h"
1.24 +#include "uarrsort.h"
1.25 +
1.26 +enum {
1.27 + /**
1.28 + * "from Knuth"
1.29 + *
1.30 + * A binary search over 8 items performs 4 comparisons:
1.31 + * log2(8)=3 to subdivide, +1 to check for equality.
1.32 + * A linear search over 8 items on average also performs 4 comparisons.
1.33 + */
1.34 + MIN_QSORT=9,
1.35 + STACK_ITEM_SIZE=200
1.36 +};
1.37 +
1.38 +/* UComparator convenience implementations ---------------------------------- */
1.39 +
1.40 +U_CAPI int32_t U_EXPORT2
1.41 +uprv_uint16Comparator(const void *context, const void *left, const void *right) {
1.42 + return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right;
1.43 +}
1.44 +
1.45 +U_CAPI int32_t U_EXPORT2
1.46 +uprv_int32Comparator(const void *context, const void *left, const void *right) {
1.47 + return *(const int32_t *)left - *(const int32_t *)right;
1.48 +}
1.49 +
1.50 +U_CAPI int32_t U_EXPORT2
1.51 +uprv_uint32Comparator(const void *context, const void *left, const void *right) {
1.52 + uint32_t l=*(const uint32_t *)left, r=*(const uint32_t *)right;
1.53 +
1.54 + /* compare directly because (l-r) would overflow the int32_t result */
1.55 + if(l<r) {
1.56 + return -1;
1.57 + } else if(l==r) {
1.58 + return 0;
1.59 + } else /* l>r */ {
1.60 + return 1;
1.61 + }
1.62 +}
1.63 +
1.64 +/* Insertion sort using binary search --------------------------------------- */
1.65 +
1.66 +U_CAPI int32_t U_EXPORT2
1.67 +uprv_stableBinarySearch(char *array, int32_t limit, void *item, int32_t itemSize,
1.68 + UComparator *cmp, const void *context) {
1.69 + int32_t start=0;
1.70 + UBool found=FALSE;
1.71 +
1.72 + /* Binary search until we get down to a tiny sub-array. */
1.73 + while((limit-start)>=MIN_QSORT) {
1.74 + int32_t i=(start+limit)/2;
1.75 + int32_t diff=cmp(context, item, array+i*itemSize);
1.76 + if(diff==0) {
1.77 + /*
1.78 + * Found the item. We look for the *last* occurrence of such
1.79 + * an item, for stable sorting.
1.80 + * If we knew that there will be only few equal items,
1.81 + * we could break now and enter the linear search.
1.82 + * However, if there are many equal items, then it should be
1.83 + * faster to continue with the binary search.
1.84 + * It seems likely that we either have all unique items
1.85 + * (where found will never become TRUE in the insertion sort)
1.86 + * or potentially many duplicates.
1.87 + */
1.88 + found=TRUE;
1.89 + start=i+1;
1.90 + } else if(diff<0) {
1.91 + limit=i;
1.92 + } else {
1.93 + start=i;
1.94 + }
1.95 + }
1.96 +
1.97 + /* Linear search over the remaining tiny sub-array. */
1.98 + while(start<limit) {
1.99 + int32_t diff=cmp(context, item, array+start*itemSize);
1.100 + if(diff==0) {
1.101 + found=TRUE;
1.102 + } else if(diff<0) {
1.103 + break;
1.104 + }
1.105 + ++start;
1.106 + }
1.107 + return found ? (start-1) : ~start;
1.108 +}
1.109 +
1.110 +static void
1.111 +doInsertionSort(char *array, int32_t length, int32_t itemSize,
1.112 + UComparator *cmp, const void *context, void *pv) {
1.113 + int32_t j;
1.114 +
1.115 + for(j=1; j<length; ++j) {
1.116 + char *item=array+j*itemSize;
1.117 + int32_t insertionPoint=uprv_stableBinarySearch(array, j, item, itemSize, cmp, context);
1.118 + if(insertionPoint<0) {
1.119 + insertionPoint=~insertionPoint;
1.120 + } else {
1.121 + ++insertionPoint; /* one past the last equal item */
1.122 + }
1.123 + if(insertionPoint<j) {
1.124 + char *dest=array+insertionPoint*itemSize;
1.125 + uprv_memcpy(pv, item, itemSize); /* v=array[j] */
1.126 + uprv_memmove(dest+itemSize, dest, (j-insertionPoint)*itemSize);
1.127 + uprv_memcpy(dest, pv, itemSize); /* array[insertionPoint]=v */
1.128 + }
1.129 + }
1.130 +}
1.131 +
1.132 +static void
1.133 +insertionSort(char *array, int32_t length, int32_t itemSize,
1.134 + UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
1.135 + UAlignedMemory v[STACK_ITEM_SIZE/sizeof(UAlignedMemory)+1];
1.136 + void *pv;
1.137 +
1.138 + /* allocate an intermediate item variable (v) */
1.139 + if(itemSize<=STACK_ITEM_SIZE) {
1.140 + pv=v;
1.141 + } else {
1.142 + pv=uprv_malloc(itemSize);
1.143 + if(pv==NULL) {
1.144 + *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1.145 + return;
1.146 + }
1.147 + }
1.148 +
1.149 + doInsertionSort(array, length, itemSize, cmp, context, pv);
1.150 +
1.151 + if(pv!=v) {
1.152 + uprv_free(pv);
1.153 + }
1.154 +}
1.155 +
1.156 +/* QuickSort ---------------------------------------------------------------- */
1.157 +
1.158 +/*
1.159 + * This implementation is semi-recursive:
1.160 + * It recurses for the smaller sub-array to shorten the recursion depth,
1.161 + * and loops for the larger sub-array.
1.162 + *
1.163 + * Loosely after QuickSort algorithms in
1.164 + * Niklaus Wirth
1.165 + * Algorithmen und Datenstrukturen mit Modula-2
1.166 + * B.G. Teubner Stuttgart
1.167 + * 4. Auflage 1986
1.168 + * ISBN 3-519-02260-5
1.169 + */
1.170 +static void
1.171 +subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
1.172 + UComparator *cmp, const void *context,
1.173 + void *px, void *pw) {
1.174 + int32_t left, right;
1.175 +
1.176 + /* start and left are inclusive, limit and right are exclusive */
1.177 + do {
1.178 + if((start+MIN_QSORT)>=limit) {
1.179 + doInsertionSort(array+start*itemSize, limit-start, itemSize, cmp, context, px);
1.180 + break;
1.181 + }
1.182 +
1.183 + left=start;
1.184 + right=limit;
1.185 +
1.186 + /* x=array[middle] */
1.187 + uprv_memcpy(px, array+((start+limit)/2)*itemSize, itemSize);
1.188 +
1.189 + do {
1.190 + while(/* array[left]<x */
1.191 + cmp(context, array+left*itemSize, px)<0
1.192 + ) {
1.193 + ++left;
1.194 + }
1.195 + while(/* x<array[right-1] */
1.196 + cmp(context, px, array+(right-1)*itemSize)<0
1.197 + ) {
1.198 + --right;
1.199 + }
1.200 +
1.201 + /* swap array[left] and array[right-1] via w; ++left; --right */
1.202 + if(left<right) {
1.203 + --right;
1.204 +
1.205 + if(left<right) {
1.206 + uprv_memcpy(pw, array+left*itemSize, itemSize);
1.207 + uprv_memcpy(array+left*itemSize, array+right*itemSize, itemSize);
1.208 + uprv_memcpy(array+right*itemSize, pw, itemSize);
1.209 + }
1.210 +
1.211 + ++left;
1.212 + }
1.213 + } while(left<right);
1.214 +
1.215 + /* sort sub-arrays */
1.216 + if((right-start)<(limit-left)) {
1.217 + /* sort [start..right[ */
1.218 + if(start<(right-1)) {
1.219 + subQuickSort(array, start, right, itemSize, cmp, context, px, pw);
1.220 + }
1.221 +
1.222 + /* sort [left..limit[ */
1.223 + start=left;
1.224 + } else {
1.225 + /* sort [left..limit[ */
1.226 + if(left<(limit-1)) {
1.227 + subQuickSort(array, left, limit, itemSize, cmp, context, px, pw);
1.228 + }
1.229 +
1.230 + /* sort [start..right[ */
1.231 + limit=right;
1.232 + }
1.233 + } while(start<(limit-1));
1.234 +}
1.235 +
1.236 +static void
1.237 +quickSort(char *array, int32_t length, int32_t itemSize,
1.238 + UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
1.239 + UAlignedMemory xw[(2*STACK_ITEM_SIZE)/sizeof(UAlignedMemory)+1];
1.240 + void *p;
1.241 +
1.242 + /* allocate two intermediate item variables (x and w) */
1.243 + if(itemSize<=STACK_ITEM_SIZE) {
1.244 + p=xw;
1.245 + } else {
1.246 + p=uprv_malloc(2*itemSize);
1.247 + if(p==NULL) {
1.248 + *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1.249 + return;
1.250 + }
1.251 + }
1.252 +
1.253 + subQuickSort(array, 0, length, itemSize,
1.254 + cmp, context, p, (char *)p+itemSize);
1.255 +
1.256 + if(p!=xw) {
1.257 + uprv_free(p);
1.258 + }
1.259 +}
1.260 +
1.261 +/* uprv_sortArray() API ----------------------------------------------------- */
1.262 +
1.263 +/*
1.264 + * Check arguments, select an appropriate implementation,
1.265 + * cast the array to char * so that array+i*itemSize works.
1.266 + */
1.267 +U_CAPI void U_EXPORT2
1.268 +uprv_sortArray(void *array, int32_t length, int32_t itemSize,
1.269 + UComparator *cmp, const void *context,
1.270 + UBool sortStable, UErrorCode *pErrorCode) {
1.271 + if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
1.272 + return;
1.273 + }
1.274 + if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) {
1.275 + *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1.276 + return;
1.277 + }
1.278 +
1.279 + if(length<=1) {
1.280 + return;
1.281 + } else if(length<MIN_QSORT || sortStable) {
1.282 + insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode);
1.283 + } else {
1.284 + quickSort((char *)array, length, itemSize, cmp, context, pErrorCode);
1.285 + }
1.286 +}
