icuSources/common/uarrsort.cpp

   1 // © 2016 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3 /*
   4 *******************************************************************************
   5 *
   6 *   Copyright (C) 2003-2013, International Business Machines
   7 *   Corporation and others.  All Rights Reserved.
   8 *
   9 *******************************************************************************
  10 *   file name:  uarrsort.c
  11 *   encoding:   UTF-8
  12 *   tab size:   8 (not used)
  13 *   indentation:4
  14 *
  15 *   created on: 2003aug04
  16 *   created by: Markus W. Scherer
  17 *
  18 *   Internal function for sorting arrays.
  19 */
  20
  21 #include "unicode/utypes.h"
  22 #include "cmemory.h"
  23 #include "uarrsort.h"
  24
  25 enum {
  26     /**
  27      * "from Knuth"
  28      *
  29      * A binary search over 8 items performs 4 comparisons:
  30      * log2(8)=3 to subdivide, +1 to check for equality.
  31      * A linear search over 8 items on average also performs 4 comparisons.
  32      */
  33     MIN_QSORT=9,
  34     STACK_ITEM_SIZE=200
  35 };
  36
  37 /* UComparator convenience implementations ---------------------------------- */
  38
  39 U_CAPI int32_t U_EXPORT2
  40 uprv_uint16Comparator(const void *context, const void *left, const void *right) {
  41     (void)context;
  42     return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right;
  43 }
  44
  45 U_CAPI int32_t U_EXPORT2
  46 uprv_int32Comparator(const void *context, const void *left, const void *right) {
  47     (void)context;
  48     return *(const int32_t *)left - *(const int32_t *)right;
  49 }
  50
  51 U_CAPI int32_t U_EXPORT2
  52 uprv_uint32Comparator(const void *context, const void *left, const void *right) {
  53     (void)context;
  54     uint32_t l=*(const uint32_t *)left, r=*(const uint32_t *)right;
  55
  56     /* compare directly because (l-r) would overflow the int32_t result */
  57     if(l<r) {
  58         return -1;
  59     } else if(l==r) {
  60         return 0;
  61     } else /* l>r */ {
  62         return 1;
  63     }
  64 }
  65
  66 /* Insertion sort using binary search --------------------------------------- */
  67
  68 U_CAPI int32_t U_EXPORT2
  69 uprv_stableBinarySearch(char *array, int32_t limit, void *item, int32_t itemSize,
  70                         UComparator *cmp, const void *context) {
  71     int32_t start=0;
  72     UBool found=FALSE;
  73
  74     /* Binary search until we get down to a tiny sub-array. */
  75     while((limit-start)>=MIN_QSORT) {
  76         int32_t i=(start+limit)/2;
  77         int32_t diff=cmp(context, item, array+i*itemSize);
  78         if(diff==0) {
  79             /*
  80              * Found the item. We look for the *last* occurrence of such
  81              * an item, for stable sorting.
  82              * If we knew that there will be only few equal items,
  83              * we could break now and enter the linear search.
  84              * However, if there are many equal items, then it should be
  85              * faster to continue with the binary search.
  86              * It seems likely that we either have all unique items
  87              * (where found will never become TRUE in the insertion sort)
  88              * or potentially many duplicates.
  89              */
  90             found=TRUE;
  91             start=i+1;
  92         } else if(diff<0) {
  93             limit=i;
  94         } else {
  95             start=i;
  96         }
  97     }
  98
  99     /* Linear search over the remaining tiny sub-array. */
 100     while(start<limit) {
 101         int32_t diff=cmp(context, item, array+start*itemSize);
 102         if(diff==0) {
 103             found=TRUE;
 104         } else if(diff<0) {
 105             break;
 106         }
 107         ++start;
 108     }
 109     return found ? (start-1) : ~start;
 110 }
 111
 112 static void
 113 doInsertionSort(char *array, int32_t length, int32_t itemSize,
 114                 UComparator *cmp, const void *context, void *pv) {
 115     int32_t j;
 116
 117     for(j=1; j<length; ++j) {
 118         char *item=array+j*itemSize;
 119         int32_t insertionPoint=uprv_stableBinarySearch(array, j, item, itemSize, cmp, context);
 120         if(insertionPoint<0) {
 121             insertionPoint=~insertionPoint;
 122         } else {
 123             ++insertionPoint;  /* one past the last equal item */
 124         }
 125         if(insertionPoint<j) {
 126             char *dest=array+insertionPoint*itemSize;
 127             uprv_memcpy(pv, item, itemSize);  /* v=array[j] */
 128             uprv_memmove(dest+itemSize, dest, (j-insertionPoint)*(size_t)itemSize);
 129             uprv_memcpy(dest, pv, itemSize);  /* array[insertionPoint]=v */
 130         }
 131     }
 132 }
 133
 134 static void
 135 insertionSort(char *array, int32_t length, int32_t itemSize,
 136               UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
 137     UAlignedMemory v[STACK_ITEM_SIZE/sizeof(UAlignedMemory)+1];
 138     void *pv;
 139
 140     /* allocate an intermediate item variable (v) */
 141     if(itemSize<=STACK_ITEM_SIZE) {
 142         pv=v;
 143     } else {
 144         pv=uprv_malloc(itemSize);
 145         if(pv==NULL) {
 146             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
 147             return;
 148         }
 149     }
 150
 151     doInsertionSort(array, length, itemSize, cmp, context, pv);
 152
 153     if(pv!=v) {
 154         uprv_free(pv);
 155     }
 156 }
 157
 158 /* QuickSort ---------------------------------------------------------------- */
 159
 160 /*
 161  * This implementation is semi-recursive:
 162  * It recurses for the smaller sub-array to shorten the recursion depth,
 163  * and loops for the larger sub-array.
 164  *
 165  * Loosely after QuickSort algorithms in
 166  * Niklaus Wirth
 167  * Algorithmen und Datenstrukturen mit Modula-2
 168  * B.G. Teubner Stuttgart
 169  * 4. Auflage 1986
 170  * ISBN 3-519-02260-5
 171  */
 172 static void
 173 subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
 174              UComparator *cmp, const void *context,
 175              void *px, void *pw) {
 176     int32_t left, right;
 177
 178     /* start and left are inclusive, limit and right are exclusive */
 179     do {
 180         if((start+MIN_QSORT)>=limit) {
 181             doInsertionSort(array+start*itemSize, limit-start, itemSize, cmp, context, px);
 182             break;
 183         }
 184
 185         left=start;
 186         right=limit;
 187
 188         /* x=array[middle] */
 189         uprv_memcpy(px, array+(size_t)((start+limit)/2)*itemSize, itemSize);
 190
 191         do {
 192             while(/* array[left]<x */
 193                   cmp(context, array+left*itemSize, px)<0
 194             ) {
 195                 ++left;
 196             }
 197             while(/* x<array[right-1] */
 198                   cmp(context, px, array+(right-1)*itemSize)<0
 199             ) {
 200                 --right;
 201             }
 202
 203             /* swap array[left] and array[right-1] via w; ++left; --right */
 204             if(left<right) {
 205                 --right;
 206
 207                 if(left<right) {
 208                     uprv_memcpy(pw, array+(size_t)left*itemSize, itemSize);
 209                     uprv_memcpy(array+(size_t)left*itemSize, array+(size_t)right*itemSize, itemSize);
 210                     uprv_memcpy(array+(size_t)right*itemSize, pw, itemSize);
 211                 }
 212
 213                 ++left;
 214             }
 215         } while(left<right);
 216
 217         /* sort sub-arrays */
 218         if((right-start)<(limit-left)) {
 219             /* sort [start..right[ */
 220             if(start<(right-1)) {
 221                 subQuickSort(array, start, right, itemSize, cmp, context, px, pw);
 222             }
 223
 224             /* sort [left..limit[ */
 225             start=left;
 226         } else {
 227             /* sort [left..limit[ */
 228             if(left<(limit-1)) {
 229                 subQuickSort(array, left, limit, itemSize, cmp, context, px, pw);
 230             }
 231
 232             /* sort [start..right[ */
 233             limit=right;
 234         }
 235     } while(start<(limit-1));
 236 }
 237
 238 static void
 239 quickSort(char *array, int32_t length, int32_t itemSize,
 240             UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
 241     UAlignedMemory xw[(2*STACK_ITEM_SIZE)/sizeof(UAlignedMemory)+1];
 242     void *p;
 243
 244     /* allocate two intermediate item variables (x and w) */
 245     if(itemSize<=STACK_ITEM_SIZE) {
 246         p=xw;
 247     } else {
 248         p=uprv_malloc(2*itemSize);
 249         if(p==NULL) {
 250             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
 251             return;
 252         }
 253     }
 254
 255     subQuickSort(array, 0, length, itemSize,
 256                  cmp, context, p, (char *)p+itemSize);
 257
 258     if(p!=xw) {
 259         uprv_free(p);
 260     }
 261 }
 262
 263 /* uprv_sortArray() API ----------------------------------------------------- */
 264
 265 /*
 266  * Check arguments, select an appropriate implementation,
 267  * cast the array to char * so that array+i*itemSize works.
 268  */
 269 U_CAPI void U_EXPORT2
 270 uprv_sortArray(void *array, int32_t length, int32_t itemSize,
 271                UComparator *cmp, const void *context,
 272                UBool sortStable, UErrorCode *pErrorCode) {
 273     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
 274         return;
 275     }
 276     if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) {
 277         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
 278         return;
 279     }
 280
 281     if(length<=1) {
 282         return;
 283     } else if(length<MIN_QSORT || sortStable) {
 284         insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode);
 285     } else {
 286         quickSort((char *)array, length, itemSize, cmp, context, pErrorCode);
 287     }
 288 }