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
23enum {
24    MIN_QSORT=9, /* from Knuth */
25    STACK_ITEM_SIZE=200
26};
27
28/* UComparator convenience implementations ---------------------------------- */
29
30U_CAPI int32_t U_EXPORT2
31uprv_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
35U_CAPI int32_t U_EXPORT2
36uprv_int32Comparator(const void *context, const void *left, const void *right) {
37    return *(const int32_t *)left - *(const int32_t *)right;
38}
39
40U_CAPI int32_t U_EXPORT2
41uprv_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
56static void
57doInsertionSort(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
81static void
82insertionSort(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 */
119static void
120subQuickSort(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
185static void
186quickSort(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 */
216U_CAPI void U_EXPORT2
217uprv_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}
237