Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1)

Unified Diff: icu46/source/common/uarrsort.c

Issue 5516007: Check in the pristine copy of ICU 4.6... (Closed) Base URL: svn://chrome-svn/chrome/trunk/deps/third_party/
Patch Set: Created 10 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « icu46/source/common/uarrsort.h ('k') | icu46/source/common/uassert.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: icu46/source/common/uarrsort.c
===================================================================
--- icu46/source/common/uarrsort.c (revision 0)
+++ icu46/source/common/uarrsort.c (revision 0)
@@ -0,0 +1,236 @@
+/*
+*******************************************************************************
+*
+* Copyright (C) 2003, International Business Machines
+* Corporation and others. All Rights Reserved.
+*
+*******************************************************************************
+* file name: uarrsort.c
+* encoding: US-ASCII
+* 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 {
+ MIN_QSORT=9, /* from Knuth */
+ STACK_ITEM_SIZE=200
+};
+
+/* UComparator convenience implementations ---------------------------------- */
+
+U_CAPI int32_t U_EXPORT2
+uprv_uint16Comparator(const void *context, const void *left, const void *right) {
+ 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) {
+ 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) {
+ 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;
+ }
+}
+
+/* Straight insertion sort from Knuth vol. III, pg. 81 ---------------------- */
+
+static void
+doInsertionSort(char *array, int32_t start, int32_t limit, int32_t itemSize,
+ UComparator *cmp, const void *context, void *pv) {
+ int32_t i, j;
+
+ for(j=start+1; j<limit; ++j) {
+ /* v=array[j] */
+ uprv_memcpy(pv, array+j*itemSize, itemSize);
+
+ for(i=j; i>start; --i) {
+ if(/* v>=array[i-1] */ cmp(context, pv, array+(i-1)*itemSize)>=0) {
+ break;
+ }
+
+ /* array[i]=array[i-1]; */
+ uprv_memcpy(array+i*itemSize, array+(i-1)*itemSize, itemSize);
+ }
+
+ if(i!=j) {
+ /* array[i]=v; */
+ uprv_memcpy(array+i*itemSize, pv, itemSize);
+ }
+ }
+}
+
+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, 0, 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, limit, itemSize, cmp, context, px);
+ break;
+ }
+
+ left=start;
+ right=limit;
+
+ /* x=array[middle] */
+ uprv_memcpy(px, array+((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+left*itemSize, itemSize);
+ uprv_memcpy(array+left*itemSize, array+right*itemSize, itemSize);
+ uprv_memcpy(array+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);
+ /* could add heapSort or similar for stable sorting of longer arrays */
+ } else {
+ quickSort((char *)array, length, itemSize, cmp, context, pErrorCode);
+ }
+}
Property changes on: icu46/source/common/uarrsort.c
___________________________________________________________________
Added: svn:eol-style
+ LF
« no previous file with comments | « icu46/source/common/uarrsort.h ('k') | icu46/source/common/uassert.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698