16f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 26f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org******************************************************************************* 36f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* 46f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Copyright (C) 2003-2013, International Business Machines 56f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Corporation and others. All Rights Reserved. 66f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* 76f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org******************************************************************************* 86f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* file name: uarrsort.c 96f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* encoding: US-ASCII 106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* tab size: 8 (not used) 116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* indentation:4 126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* 136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* created on: 2003aug04 146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* created by: Markus W. Scherer 156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* 166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org* Internal function for sorting arrays. 176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org*/ 186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "unicode/utypes.h" 206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "cmemory.h" 216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org#include "uarrsort.h" 226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgenum { 246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /** 256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * "from Knuth" 266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * A binary search over 8 items performs 4 comparisons: 286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * log2(8)=3 to subdivide, +1 to check for equality. 296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * A linear search over 8 items on average also performs 4 comparisons. 306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org MIN_QSORT=9, 326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org STACK_ITEM_SIZE=200 336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org}; 346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* UComparator convenience implementations ---------------------------------- */ 366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguprv_uint16Comparator(const void *context, const void *left, const void *right) { 396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right; 406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguprv_int32Comparator(const void *context, const void *left, const void *right) { 446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return *(const int32_t *)left - *(const int32_t *)right; 456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguprv_uint32Comparator(const void *context, const void *left, const void *right) { 496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uint32_t l=*(const uint32_t *)left, r=*(const uint32_t *)right; 506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* compare directly because (l-r) would overflow the int32_t result */ 526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(l<r) { 536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return -1; 546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(l==r) { 556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 0; 566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else /* l>r */ { 576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return 1; 586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* Insertion sort using binary search --------------------------------------- */ 626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI int32_t U_EXPORT2 646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguprv_stableBinarySearch(char *array, int32_t limit, void *item, int32_t itemSize, 656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UComparator *cmp, const void *context) { 666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t start=0; 676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool found=FALSE; 686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Binary search until we get down to a tiny sub-array. */ 706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while((limit-start)>=MIN_QSORT) { 716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t i=(start+limit)/2; 726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t diff=cmp(context, item, array+i*itemSize); 736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(diff==0) { 746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* 756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Found the item. We look for the *last* occurrence of such 766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * an item, for stable sorting. 776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * If we knew that there will be only few equal items, 786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * we could break now and enter the linear search. 796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * However, if there are many equal items, then it should be 806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * faster to continue with the binary search. 816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * It seems likely that we either have all unique items 826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * (where found will never become TRUE in the insertion sort) 836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * or potentially many duplicates. 846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org found=TRUE; 866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org start=i+1; 876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(diff<0) { 886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org limit=i; 896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org start=i; 916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* Linear search over the remaining tiny sub-array. */ 956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(start<limit) { 966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t diff=cmp(context, item, array+start*itemSize); 976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(diff==0) { 986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org found=TRUE; 996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(diff<0) { 1006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 1016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++start; 1036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return found ? (start-1) : ~start; 1056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic void 1086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgdoInsertionSort(char *array, int32_t length, int32_t itemSize, 1096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UComparator *cmp, const void *context, void *pv) { 1106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t j; 1116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org for(j=1; j<length; ++j) { 1136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org char *item=array+j*itemSize; 1146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t insertionPoint=uprv_stableBinarySearch(array, j, item, itemSize, cmp, context); 1156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(insertionPoint<0) { 1166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org insertionPoint=~insertionPoint; 1176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++insertionPoint; /* one past the last equal item */ 1196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(insertionPoint<j) { 1216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org char *dest=array+insertionPoint*itemSize; 1226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_memcpy(pv, item, itemSize); /* v=array[j] */ 1236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_memmove(dest+itemSize, dest, (j-insertionPoint)*itemSize); 1246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_memcpy(dest, pv, itemSize); /* array[insertionPoint]=v */ 1256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic void 1306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orginsertionSort(char *array, int32_t length, int32_t itemSize, 1316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UComparator *cmp, const void *context, UErrorCode *pErrorCode) { 1326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UAlignedMemory v[STACK_ITEM_SIZE/sizeof(UAlignedMemory)+1]; 1336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org void *pv; 1346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* allocate an intermediate item variable (v) */ 1366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(itemSize<=STACK_ITEM_SIZE) { 1376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pv=v; 1386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 1396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org pv=uprv_malloc(itemSize); 1406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pv==NULL) { 1416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 1426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 1436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org doInsertionSort(array, length, itemSize, cmp, context, pv); 1476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pv!=v) { 1496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_free(pv); 1506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 1526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* QuickSort ---------------------------------------------------------------- */ 1546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 1566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * This implementation is semi-recursive: 1576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * It recurses for the smaller sub-array to shorten the recursion depth, 1586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * and loops for the larger sub-array. 1596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 1606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Loosely after QuickSort algorithms in 1616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Niklaus Wirth 1626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Algorithmen und Datenstrukturen mit Modula-2 1636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * B.G. Teubner Stuttgart 1646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * 4. Auflage 1986 1656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * ISBN 3-519-02260-5 1666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 1676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic void 1686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgsubQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize, 1696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UComparator *cmp, const void *context, 1706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org void *px, void *pw) { 1716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org int32_t left, right; 1726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* start and left are inclusive, limit and right are exclusive */ 1746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 1756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if((start+MIN_QSORT)>=limit) { 1766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org doInsertionSort(array+start*itemSize, limit-start, itemSize, cmp, context, px); 1776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org break; 1786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org left=start; 1816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org right=limit; 1826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* x=array[middle] */ 1846f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_memcpy(px, array+((start+limit)/2)*itemSize, itemSize); 1856f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1866f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org do { 1876f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(/* array[left]<x */ 1886f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org cmp(context, array+left*itemSize, px)<0 1896f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ) { 1906f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++left; 1916f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1926f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org while(/* x<array[right-1] */ 1936f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org cmp(context, px, array+(right-1)*itemSize)<0 1946f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ) { 1956f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --right; 1966f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 1976f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 1986f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* swap array[left] and array[right-1] via w; ++left; --right */ 1996f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(left<right) { 2006f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org --right; 2016f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2026f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(left<right) { 2036f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_memcpy(pw, array+left*itemSize, itemSize); 2046f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_memcpy(array+left*itemSize, array+right*itemSize, itemSize); 2056f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_memcpy(array+right*itemSize, pw, itemSize); 2066f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2076f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2086f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org ++left; 2096f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2106f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(left<right); 2116f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2126f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* sort sub-arrays */ 2136f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if((right-start)<(limit-left)) { 2146f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* sort [start..right[ */ 2156f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(start<(right-1)) { 2166f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org subQuickSort(array, start, right, itemSize, cmp, context, px, pw); 2176f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2186f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2196f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* sort [left..limit[ */ 2206f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org start=left; 2216f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2226f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* sort [left..limit[ */ 2236f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(left<(limit-1)) { 2246f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org subQuickSort(array, left, limit, itemSize, cmp, context, px, pw); 2256f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2266f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2276f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* sort [start..right[ */ 2286f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org limit=right; 2296f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2306f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } while(start<(limit-1)); 2316f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 2326f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2336f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgstatic void 2346f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgquickSort(char *array, int32_t length, int32_t itemSize, 2356f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UComparator *cmp, const void *context, UErrorCode *pErrorCode) { 2366f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UAlignedMemory xw[(2*STACK_ITEM_SIZE)/sizeof(UAlignedMemory)+1]; 2376f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org void *p; 2386f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2396f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org /* allocate two intermediate item variables (x and w) */ 2406f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(itemSize<=STACK_ITEM_SIZE) { 2416f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org p=xw; 2426f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2436f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org p=uprv_malloc(2*itemSize); 2446f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(p==NULL) { 2456f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 2466f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 2476f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2486f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2496f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2506f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org subQuickSort(array, 0, length, itemSize, 2516f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org cmp, context, p, (char *)p+itemSize); 2526f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2536f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(p!=xw) { 2546f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org uprv_free(p); 2556f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2566f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 2576f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2586f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* uprv_sortArray() API ----------------------------------------------------- */ 2596f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2606f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org/* 2616f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * Check arguments, select an appropriate implementation, 2626f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org * cast the array to char * so that array+i*itemSize works. 2636f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org */ 2646f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orgU_CAPI void U_EXPORT2 2656f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.orguprv_sortArray(void *array, int32_t length, int32_t itemSize, 2666f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UComparator *cmp, const void *context, 2676f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org UBool sortStable, UErrorCode *pErrorCode) { 2686f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) { 2696f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 2706f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2716f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) { 2726f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 2736f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 2746f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2756f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org 2766f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org if(length<=1) { 2776f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org return; 2786f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else if(length<MIN_QSORT || sortStable) { 2796f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode); 2806f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } else { 2816f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org quickSort((char *)array, length, itemSize, cmp, context, pErrorCode); 2826f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org } 2836f31ac30b9092fd02a8c97e5216cf53f3e4fae4jshin@chromium.org} 284