icuSources/common/uarrsort.c

   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 }