1f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)/* 2f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)******************************************************************************* 3f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* 4f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* Copyright (C) 2003, International Business Machines 5f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* Corporation and others. All Rights Reserved. 6f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* 7f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)******************************************************************************* 8f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* file name: uarrsort.c 9f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* encoding: US-ASCII 10f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* tab size: 8 (not used) 11f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* indentation:4 12f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* 13f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* created on: 2003aug04 14f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* created by: Markus W. Scherer 15f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* 16f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)* Internal function for sorting arrays. 17f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)*/ 18f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 19f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)#include "unicode/utypes.h" 20f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)#include "cmemory.h" 21f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)#include "uarrsort.h" 22f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 23f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)enum { 24f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) MIN_QSORT=9, /* from Knuth */ 25f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) STACK_ITEM_SIZE=200 26f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)}; 27f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 28f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)/* UComparator convenience implementations ---------------------------------- */ 29f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 30f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)U_CAPI int32_t U_EXPORT2 31f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)uprv_uint16Comparator(const void *context, const void *left, const void *right) { 32f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right; 33f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)} 34f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 35f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)U_CAPI int32_t U_EXPORT2 36f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)uprv_int32Comparator(const void *context, const void *left, const void *right) { 37f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return *(const int32_t *)left - *(const int32_t *)right; 38f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)} 39f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 40f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)U_CAPI int32_t U_EXPORT2 41f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)uprv_uint32Comparator(const void *context, const void *left, const void *right) { 42f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uint32_t l=*(const uint32_t *)left, r=*(const uint32_t *)right; 43f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 44f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* compare directly because (l-r) would overflow the int32_t result */ 45f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(l<r) { 46f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return -1; 47f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } else if(l==r) { 48f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return 0; 49f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } else /* l>r */ { 50f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return 1; 51f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 52f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)} 53f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 54f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)/* Straight insertion sort from Knuth vol. III, pg. 81 ---------------------- */ 55f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 56f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)static void 57f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)doInsertionSort(char *array, int32_t start, int32_t limit, int32_t itemSize, 58f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) UComparator *cmp, const void *context, void *pv) { 59f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) int32_t i, j; 60f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 61f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) for(j=start+1; j<limit; ++j) { 62f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* v=array[j] */ 63f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uprv_memcpy(pv, array+j*itemSize, itemSize); 64f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 65f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) for(i=j; i>start; --i) { 66f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(/* v>=array[i-1] */ cmp(context, pv, array+(i-1)*itemSize)>=0) { 67f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) break; 68f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 69f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 70f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* array[i]=array[i-1]; */ 71f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uprv_memcpy(array+i*itemSize, array+(i-1)*itemSize, itemSize); 72f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 73f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 74f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(i!=j) { 75f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* array[i]=v; */ 76f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uprv_memcpy(array+i*itemSize, pv, itemSize); 77f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 78f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 79f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)} 80f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 81f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)static void 82f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)insertionSort(char *array, int32_t length, int32_t itemSize, 83f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) UComparator *cmp, const void *context, UErrorCode *pErrorCode) { 84f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) UAlignedMemory v[STACK_ITEM_SIZE/sizeof(UAlignedMemory)+1]; 85f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) void *pv; 86f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 87f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* allocate an intermediate item variable (v) */ 88f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(itemSize<=STACK_ITEM_SIZE) { 89f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) pv=v; 90f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } else { 91f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) pv=uprv_malloc(itemSize); 92f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(pv==NULL) { 93f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 94f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return; 95f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 96f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 97f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 98f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) doInsertionSort(array, 0, length, itemSize, cmp, context, pv); 99f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 100f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(pv!=v) { 101f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uprv_free(pv); 102f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 103f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)} 104f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 105f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)/* QuickSort ---------------------------------------------------------------- */ 106f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 107f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)/* 108f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * This implementation is semi-recursive: 109f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * It recurses for the smaller sub-array to shorten the recursion depth, 110f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * and loops for the larger sub-array. 111f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * 112f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * Loosely after QuickSort algorithms in 113f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * Niklaus Wirth 114f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * Algorithmen und Datenstrukturen mit Modula-2 115f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * B.G. Teubner Stuttgart 116f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * 4. Auflage 1986 117f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * ISBN 3-519-02260-5 118f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) */ 119f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)static void 120f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize, 121f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) UComparator *cmp, const void *context, 122f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) void *px, void *pw) { 123f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) int32_t left, right; 124f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 125f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* start and left are inclusive, limit and right are exclusive */ 126f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) do { 127f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if((start+MIN_QSORT)>=limit) { 128f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) doInsertionSort(array, start, limit, itemSize, cmp, context, px); 129f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) break; 130f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 131f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 132f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) left=start; 133f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) right=limit; 134f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 135f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* x=array[middle] */ 136f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uprv_memcpy(px, array+((start+limit)/2)*itemSize, itemSize); 137f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 138f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) do { 139f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) while(/* array[left]<x */ 140f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) cmp(context, array+left*itemSize, px)<0 141f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) ) { 142f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) ++left; 143f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 144f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) while(/* x<array[right-1] */ 145f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) cmp(context, px, array+(right-1)*itemSize)<0 146f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) ) { 147f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) --right; 148f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 149f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 150f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* swap array[left] and array[right-1] via w; ++left; --right */ 151f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(left<right) { 152f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) --right; 153f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 154f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(left<right) { 155f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uprv_memcpy(pw, array+left*itemSize, itemSize); 156f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uprv_memcpy(array+left*itemSize, array+right*itemSize, itemSize); 157f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uprv_memcpy(array+right*itemSize, pw, itemSize); 158f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 159f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 160f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) ++left; 161f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 162f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } while(left<right); 163f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 164f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* sort sub-arrays */ 165f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if((right-start)<(limit-left)) { 166f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* sort [start..right[ */ 167f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(start<(right-1)) { 168f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) subQuickSort(array, start, right, itemSize, cmp, context, px, pw); 169f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 170f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 171f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* sort [left..limit[ */ 172f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) start=left; 173f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } else { 174f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* sort [left..limit[ */ 175f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(left<(limit-1)) { 176f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) subQuickSort(array, left, limit, itemSize, cmp, context, px, pw); 177f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 178f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 179f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* sort [start..right[ */ 180f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) limit=right; 181f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 182f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } while(start<(limit-1)); 183f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)} 184f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 185f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)static void 186f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)quickSort(char *array, int32_t length, int32_t itemSize, 187f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) UComparator *cmp, const void *context, UErrorCode *pErrorCode) { 188f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) UAlignedMemory xw[(2*STACK_ITEM_SIZE)/sizeof(UAlignedMemory)+1]; 189f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) void *p; 190f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 191f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* allocate two intermediate item variables (x and w) */ 192f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(itemSize<=STACK_ITEM_SIZE) { 193f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) p=xw; 194f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } else { 195f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) p=uprv_malloc(2*itemSize); 196f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(p==NULL) { 197f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 198f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return; 199f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 200f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 201f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 202f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) subQuickSort(array, 0, length, itemSize, 203f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) cmp, context, p, (char *)p+itemSize); 204f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 205f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(p!=xw) { 206f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) uprv_free(p); 207f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 208f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)} 209f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 210f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)/* uprv_sortArray() API ----------------------------------------------------- */ 211f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 212f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)/* 213f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * Check arguments, select an appropriate implementation, 214f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) * cast the array to char * so that array+i*itemSize works. 215f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) */ 216f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)U_CAPI void U_EXPORT2 217f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)uprv_sortArray(void *array, int32_t length, int32_t itemSize, 218f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) UComparator *cmp, const void *context, 219f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) UBool sortStable, UErrorCode *pErrorCode) { 220f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) { 221f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return; 222f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 223f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) { 224f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 225f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return; 226f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 227f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) 228f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) if(length<=1) { 229f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) return; 230f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } else if(length<MIN_QSORT || sortStable) { 231f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode); 232f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) /* could add heapSort or similar for stable sorting of longer arrays */ 233f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } else { 234f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) quickSort((char *)array, length, itemSize, cmp, context, pErrorCode); 235f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles) } 236f4ed1cf5d184064c4cf0e4359c6d5d8aadb50afaTorne (Richard Coles)} 237