--- /dev/null
+// © 2016 and later: Unicode, Inc. and others.
+// License & terms of use: http://www.unicode.org/copyright.html
+/*
+*******************************************************************************
+*
+* Copyright (C) 2003-2013, International Business Machines
+* Corporation and others. All Rights Reserved.
+*
+*******************************************************************************
+* file name: uarrsort.c
+* encoding: UTF-8
+* tab size: 8 (not used)
+* indentation:4
+*
+* created on: 2003aug04
+* created by: Markus W. Scherer
+*
+* Internal function for sorting arrays.
+*/
+
+#include "unicode/utypes.h"
+#include "cmemory.h"
+#include "uarrsort.h"
+
+enum {
+ /**
+ * "from Knuth"
+ *
+ * A binary search over 8 items performs 4 comparisons:
+ * log2(8)=3 to subdivide, +1 to check for equality.
+ * A linear search over 8 items on average also performs 4 comparisons.
+ */
+ MIN_QSORT=9,
+ STACK_ITEM_SIZE=200
+};
+
+/* UComparator convenience implementations ---------------------------------- */
+
+U_CAPI int32_t U_EXPORT2
+uprv_uint16Comparator(const void *context, const void *left, const void *right) {
+ (void)context;
+ return (int32_t)*(const uint16_t *)left - (int32_t)*(const uint16_t *)right;
+}
+
+U_CAPI int32_t U_EXPORT2
+uprv_int32Comparator(const void *context, const void *left, const void *right) {
+ (void)context;
+ return *(const int32_t *)left - *(const int32_t *)right;
+}
+
+U_CAPI int32_t U_EXPORT2
+uprv_uint32Comparator(const void *context, const void *left, const void *right) {
+ (void)context;
+ uint32_t l=*(const uint32_t *)left, r=*(const uint32_t *)right;
+
+ /* compare directly because (l-r) would overflow the int32_t result */
+ if(l<r) {
+ return -1;
+ } else if(l==r) {
+ return 0;
+ } else /* l>r */ {
+ return 1;
+ }
+}
+
+/* Insertion sort using binary search --------------------------------------- */
+
+U_CAPI int32_t U_EXPORT2
+uprv_stableBinarySearch(char *array, int32_t limit, void *item, int32_t itemSize,
+ UComparator *cmp, const void *context) {
+ int32_t start=0;
+ UBool found=FALSE;
+
+ /* Binary search until we get down to a tiny sub-array. */
+ while((limit-start)>=MIN_QSORT) {
+ int32_t i=(start+limit)/2;
+ int32_t diff=cmp(context, item, array+i*itemSize);
+ if(diff==0) {
+ /*
+ * Found the item. We look for the *last* occurrence of such
+ * an item, for stable sorting.
+ * If we knew that there will be only few equal items,
+ * we could break now and enter the linear search.
+ * However, if there are many equal items, then it should be
+ * faster to continue with the binary search.
+ * It seems likely that we either have all unique items
+ * (where found will never become TRUE in the insertion sort)
+ * or potentially many duplicates.
+ */
+ found=TRUE;
+ start=i+1;
+ } else if(diff<0) {
+ limit=i;
+ } else {
+ start=i;
+ }
+ }
+
+ /* Linear search over the remaining tiny sub-array. */
+ while(start<limit) {
+ int32_t diff=cmp(context, item, array+start*itemSize);
+ if(diff==0) {
+ found=TRUE;
+ } else if(diff<0) {
+ break;
+ }
+ ++start;
+ }
+ return found ? (start-1) : ~start;
+}
+
+static void
+doInsertionSort(char *array, int32_t length, int32_t itemSize,
+ UComparator *cmp, const void *context, void *pv) {
+ int32_t j;
+
+ for(j=1; j<length; ++j) {
+ char *item=array+j*itemSize;
+ int32_t insertionPoint=uprv_stableBinarySearch(array, j, item, itemSize, cmp, context);
+ if(insertionPoint<0) {
+ insertionPoint=~insertionPoint;
+ } else {
+ ++insertionPoint; /* one past the last equal item */
+ }
+ if(insertionPoint<j) {
+ char *dest=array+insertionPoint*itemSize;
+ uprv_memcpy(pv, item, itemSize); /* v=array[j] */
+ uprv_memmove(dest+itemSize, dest, (j-insertionPoint)*(size_t)itemSize);
+ uprv_memcpy(dest, pv, itemSize); /* array[insertionPoint]=v */
+ }
+ }
+}
+
+static void
+insertionSort(char *array, int32_t length, int32_t itemSize,
+ UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
+ UAlignedMemory v[STACK_ITEM_SIZE/sizeof(UAlignedMemory)+1];
+ void *pv;
+
+ /* allocate an intermediate item variable (v) */
+ if(itemSize<=STACK_ITEM_SIZE) {
+ pv=v;
+ } else {
+ pv=uprv_malloc(itemSize);
+ if(pv==NULL) {
+ *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
+ return;
+ }
+ }
+
+ doInsertionSort(array, length, itemSize, cmp, context, pv);
+
+ if(pv!=v) {
+ uprv_free(pv);
+ }
+}
+
+/* QuickSort ---------------------------------------------------------------- */
+
+/*
+ * This implementation is semi-recursive:
+ * It recurses for the smaller sub-array to shorten the recursion depth,
+ * and loops for the larger sub-array.
+ *
+ * Loosely after QuickSort algorithms in
+ * Niklaus Wirth
+ * Algorithmen und Datenstrukturen mit Modula-2
+ * B.G. Teubner Stuttgart
+ * 4. Auflage 1986
+ * ISBN 3-519-02260-5
+ */
+static void
+subQuickSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
+ UComparator *cmp, const void *context,
+ void *px, void *pw) {
+ int32_t left, right;
+
+ /* start and left are inclusive, limit and right are exclusive */
+ do {
+ if((start+MIN_QSORT)>=limit) {
+ doInsertionSort(array+start*itemSize, limit-start, itemSize, cmp, context, px);
+ break;
+ }
+
+ left=start;
+ right=limit;
+
+ /* x=array[middle] */
+ uprv_memcpy(px, array+(size_t)((start+limit)/2)*itemSize, itemSize);
+
+ do {
+ while(/* array[left]<x */
+ cmp(context, array+left*itemSize, px)<0
+ ) {
+ ++left;
+ }
+ while(/* x<array[right-1] */
+ cmp(context, px, array+(right-1)*itemSize)<0
+ ) {
+ --right;
+ }
+
+ /* swap array[left] and array[right-1] via w; ++left; --right */
+ if(left<right) {
+ --right;
+
+ if(left<right) {
+ uprv_memcpy(pw, array+(size_t)left*itemSize, itemSize);
+ uprv_memcpy(array+(size_t)left*itemSize, array+(size_t)right*itemSize, itemSize);
+ uprv_memcpy(array+(size_t)right*itemSize, pw, itemSize);
+ }
+
+ ++left;
+ }
+ } while(left<right);
+
+ /* sort sub-arrays */
+ if((right-start)<(limit-left)) {
+ /* sort [start..right[ */
+ if(start<(right-1)) {
+ subQuickSort(array, start, right, itemSize, cmp, context, px, pw);
+ }
+
+ /* sort [left..limit[ */
+ start=left;
+ } else {
+ /* sort [left..limit[ */
+ if(left<(limit-1)) {
+ subQuickSort(array, left, limit, itemSize, cmp, context, px, pw);
+ }
+
+ /* sort [start..right[ */
+ limit=right;
+ }
+ } while(start<(limit-1));
+}
+
+static void
+quickSort(char *array, int32_t length, int32_t itemSize,
+ UComparator *cmp, const void *context, UErrorCode *pErrorCode) {
+ UAlignedMemory xw[(2*STACK_ITEM_SIZE)/sizeof(UAlignedMemory)+1];
+ void *p;
+
+ /* allocate two intermediate item variables (x and w) */
+ if(itemSize<=STACK_ITEM_SIZE) {
+ p=xw;
+ } else {
+ p=uprv_malloc(2*itemSize);
+ if(p==NULL) {
+ *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
+ return;
+ }
+ }
+
+ subQuickSort(array, 0, length, itemSize,
+ cmp, context, p, (char *)p+itemSize);
+
+ if(p!=xw) {
+ uprv_free(p);
+ }
+}
+
+/* uprv_sortArray() API ----------------------------------------------------- */
+
+/*
+ * Check arguments, select an appropriate implementation,
+ * cast the array to char * so that array+i*itemSize works.
+ */
+U_CAPI void U_EXPORT2
+uprv_sortArray(void *array, int32_t length, int32_t itemSize,
+ UComparator *cmp, const void *context,
+ UBool sortStable, UErrorCode *pErrorCode) {
+ if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
+ return;
+ }
+ if((length>0 && array==NULL) || length<0 || itemSize<=0 || cmp==NULL) {
+ *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
+ return;
+ }
+
+ if(length<=1) {
+ return;
+ } else if(length<MIN_QSORT || sortStable) {
+ insertionSort((char *)array, length, itemSize, cmp, context, pErrorCode);
+ } else {
+ quickSort((char *)array, length, itemSize, cmp, context, pErrorCode);
+ }
+}
projects / apple / icu.git / blobdiff