Loading

Revision differences

Return to paste
Old revision #pxwjx24zlNew revision #p1xjx4tqv
1//  1/**
2// qsort.cpp  2 * Type safe Gnome Sort.
3//  3 *
4//      Copyright (c) Microsoft Corporation. All rights reserved.  4 * This is a slightly modified Gnome search. The basic
5//  5 * Gnome search tries to sort already sorted list parts.
6// Defines qsort(), a routine for sorting arrays.  6 * The modification skips these.
7//  7 *
8#include <corecrt_internal.h>  8 * @note Use this sort for presorted / regular sorted data.
9#include <search.h>  9 *
   10 * @param base Pointer to the first element of the array to be sorted.
   11 * @param num Number of elements in the array pointed by base.
   12 * @param comparator Function that compares two elements.
   13 * @param desc Sort descending.
   14 */
   15template <typename T>
   16static inline void GSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
   17{
   18    if (num < 2) return;
10  19  
  20    assert(base != NULL);  
  21    assert(comparator != NULL);  
11  22  
  23    T *a = base;  
  24    T *b = base + 1;  
  25    uint offset = 0;  
12  26  
13// Always compile this module for speed, not size  27    while (num > 1) {
14#pragma optimize("t", on)  28        const int diff = comparator(a, b);
   29        if ((!desc && diff <= 0) || (desc && diff >= 0)) {
   30            if (offset != 0) {
   31                /* Jump back to the last direction switch point */
   32                a += offset;
   33                b += offset;
   34                offset = 0;
   35                continue;
   36            }
15  37  
  38            a++;  
  39            b++;  
  40            num--;  
  41        } else {  
  42            Swap(*a, *b);  
16  43  
  44            if (a == base) continue;  
17  45  
18#ifdef _M_CEE  18            a--;
19    #define __fileDECL __clrcall  19            b--;
20#else  20            offset++;
21    #define __fileDECL __cdecl  21        }
22#endif  22    }
23  23}
24    
25    
26#ifdef __USE_CONTEXT    
27    #define __COMPARE(context, p1, p2)                comp(context, p1, p2)    
28    #define __SHORTSORT(lo, hi, width, comp, context) shortsort_s(lo, hi, width, comp, context);    
29#else    
30    #define __COMPARE(context, p1, p2)                comp(p1, p2)    
31    #define __SHORTSORT(lo, hi, width, comp, context) shortsort(lo, hi, width, comp);    
32#endif    
33    
34    
35    
36// Swaps the objects of size 'width' that are pointed to by 'a' and 'b'    
37#ifndef _QSORT_SWAP_DEFINED    
38#define _QSORT_SWAP_DEFINED    
39_CRT_SECURITYSAFECRITICAL_ATTRIBUTE    
40static void __fileDECL swap(_Inout_updates_(width) char* a, _Inout_updates_(width) char* b, size_t width)    
41{    
42    if (a != b)    
43    {    
44        // Do the swap one character at a time to avoid potential alignment    
45        // problems:    
46        while (width--)    
47        {    
48            char const tmp = *a;    
49            *a++ = *b;    
50            *b++ = tmp;    
51        }    
52    }    
53}    
54#endif // _QSORT_SWAP_DEFINED    
55    
56    
57    
58// An insertion sort for sorting short arrays.  Sorts the sub-array of elements    
59// between lo and hi (inclusive).  Assumes lo < hi.  lo and hi are pointers to    
60// the first and last elements in the range to be sorted (note:  hi does not    
61// point one-past-the-end).  The comp is a comparer with the same behavior as    
62// specified for qsort.    
63_CRT_SECURITYSAFECRITICAL_ATTRIBUTE    
64#ifdef __USE_CONTEXT    
65static void __fileDECL shortsort_s(    
66    _Inout_updates_(hi - lo + 1) char*        lo,    
67    _Inout_updates_(width)       char*        hi,    
68    size_t const width,    
69    int (__fileDECL* comp)(void*, void const*, void const*),    
70    void*  const context    
71    )    
72#else // __USE_CONTEXT    
73static void __fileDECL shortsort(    
74    _Inout_updates_(hi - lo + 1) char*        lo,    
75    _Inout_updates_(width)       char*        hi,    
76    size_t const width,    
77    int (__fileDECL* comp)(void const*, void const*)    
78    )    
79#endif // __USE_CONTEXT    
80{    
81    // Note: in assertions below, i and j are alway inside original bound of    
82    // array to sort.    
83    
84    // Reentrancy diligence: Save (and unset) global-state mode to the stack before making callout to 'compare'    
85    __crt_state_management::scoped_global_state_reset saved_state;    
86    
87    while (hi > lo)    
88    {    
89        // A[i] <= A[j] for i <= j, j > hi    
90        char* max = lo;    
91        for (char* p = lo+width; p <= hi; p += width)    
92        {    
93            // A[i] <= A[max] for lo <= i < p    
94            if (__COMPARE(context, p, max) > 0)    
95            {    
96                max = p;    
97            }    
98            // A[i] <= A[max] for lo <= i <= p    
99        }    
100    
101        // A[i] <= A[max] for lo <= i <= hi    
102    
103        swap(max, hi, width);    
104    
105        // A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi    
106    
107        hi -= width;    
108    
109        // A[i] <= A[j] for i <= j, j > hi, loop top condition established    
110    }    
111    
112    // A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,    
113    // so array is sorted    
114}    
115    
116    
117    
118// This macro defines the cutoff between using QuickSort and insertion sort for    
119// arrays; arrays with lengths shorter or equal to the below value use insertion    
120// sort.    
121#define CUTOFF 8 // Testing shows that this is a good value.    
122    
123// Note:  The theoretical number of stack entries required is no more than 1 +    
124// log2(num).  But we switch to insertion sort for CUTOFF elements or less, so    
125// we really only need 1 + log2(num) - log(CUTOFF) stack entries.  For a CUTOFF    
126// of 8, that means we need no more than 30 stack entries for 32-bit platforms    
127// and 62 for 64-bit platforms.    
128#define STKSIZ (8 * sizeof(void*) - 2)    
129    
130    
131    
132// QuickSort function for sorting arrays.  The array is sorted in place.    
133// Parameters:    
134//  * base:  Pointer to the initial element of the array    
135//  * num:   Number of elements in the array    
136//  * width: Width of each element in the array, in bytes    
137//  * comp:  Pointer to a function returning analog of strcmp for strings, but    
138//           supplied by the caller for comparing the array elements.  It    
139//           accepts two pointers to elements; returns negative if 1 < 2;    
140//           zero if 1 == 2, and positive if 1 > 2.    
141#ifndef _M_CEE    
142extern "C"    
143#endif    
144_CRT_SECURITYSAFECRITICAL_ATTRIBUTE    
145#ifdef __USE_CONTEXT    
146void __fileDECL qsort_s(    
147    void*  const base,    
148    size_t const num,    
149    size_t const width,    
150    int (__fileDECL* const comp)(void*, void const*, void const*),    
151    void*  const context    
152    )    
153#else // __USE_CONTEXT    
154void __fileDECL qsort(    
155    void*  const base,    
156    size_t const num,    
157    size_t const width,    
158    int (__fileDECL* const comp)(void const*, void const*)    
159    )    
160#endif // __USE_CONTEXT    
161{    
162    _VALIDATE_RETURN_VOID(base != nullptr || num == 0, EINVAL);    
163    _VALIDATE_RETURN_VOID(width > 0, EINVAL);    
164    _VALIDATE_RETURN_VOID(comp != nullptr, EINVAL);    
165    
166    // A stack for saving the sub-arrays yet to be processed:    
167    char* lostk[STKSIZ];    
168    char* histk[STKSIZ];    
169    int stkptr = 0;    
170    
171    if (num < 2)    
172        return; // Nothing to do:    
173    
174    // The ends of the sub-array currently being sorted (note that 'hi' points    
175    // to the last element, not one-past-the-end):    
176    char* lo = static_cast<char*>(base);    
177    char* hi = static_cast<char*>(base) + width * (num-1);    
178    
179    // This entry point is for pseudo-recursion calling: setting    
180    // lo and hi and jumping to here is like recursion, but stkptr is    
181    // preserved, locals aren't, so we preserve stuff on the stack.    
182recurse:    
183    
184    // The number of elements in the sub-array currently being sorted:    
185    size_t const size = (hi - lo) / width + 1;    
186    
187    // Below a certain size, it is faster to use a O(n^2) sorting method:    
188    if (size <= CUTOFF)    
189    {    
190        __SHORTSORT(lo, hi, width, comp, context);    
191    }    
192    else    
193    {    
194        // First we pick a partitioning element.  The efficiency of the    
195        // algorithm demands that we find one that is approximately the median    
196        // of the values, but also that we select one fast.  We choose the    
197        // median of the first, middle, and last elements, to avoid bad    
198        // performance in the face of already sorted data, or data that is made    
199        // up of multiple sorted runs appended together.  Testing shows that a    
200        // median-of-three algorithm provides better performance than simply    
201        // picking the middle element for the latter case.    
202    
203        // Find the middle element:    
204        char* mid = lo + (size / 2) * width;    
205    
206        // Sort the first, middle, last elements into order:    
207        if (__COMPARE(context, lo, mid) > 0)    
208            swap(lo, mid, width);    
209    
210        if (__COMPARE(context, lo, hi) > 0)    
211            swap(lo, hi, width);    
212    
213        if (__COMPARE(context, mid, hi) > 0)    
214            swap(mid, hi, width);    
215    
216        // We now wish to partition the array into three pieces, one consisting    
217        // of elements <= partition element, one of elements equal to the    
218        // partition element, and one of elements > than it.  This is done    
219        // below; comments indicate conditions established at every step.    
220    
221        char* loguy = lo;    
222        char* higuy = hi;    
223    
224        // Note that higuy decreases and loguy increases on every iteration,    
225        // so loop must terminate.    
226        for (;;)    
227        {    
228            // lo <= loguy < hi, lo < higuy <= hi,    
229            // A[i] <= A[mid] for lo <= i <= loguy,    
230            // A[i] > A[mid] for higuy <= i < hi,    
231            // A[hi] >= A[mid]    
232    
233            // The doubled loop is to avoid calling comp(mid,mid), since some    
234            // existing comparison funcs don't work when passed the same    
235            // value for both pointers.    
236    
237            if (mid > loguy)    
238            {    
239                do    
240                {    
241                    loguy += width;    
242                }    
243                while (loguy < mid && __COMPARE(context, loguy, mid) <= 0);    
244            }    
245            if (mid <= loguy)    
246            {    
247                do    
248                {    
249                    loguy += width;    
250                }    
251                while (loguy <= hi && __COMPARE(context, loguy, mid) <= 0);    
252            }    
253    
254            // lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy,    
255            // either loguy > hi or A[loguy] > A[mid]    
256    
257            do    
258            {    
259                higuy -= width;    
260            }    
261            while (higuy > mid && __COMPARE(context, higuy, mid) > 0);    
262    
263            // lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi,    
264            // either higuy == lo or A[higuy] <= A[mid]    
265    
266            if (higuy < loguy)    
267                break;    
268    
269            // if loguy > hi or higuy == lo, then we would have exited, so    
270            // A[loguy] > A[mid], A[higuy] <= A[mid],    
271            // loguy <= hi, higuy > lo    
272    
273            swap(loguy, higuy, width);    
274    
275            // If the partition element was moved, follow it.  Only need    
276            // to check for mid == higuy, since before the swap,    
277            // A[loguy] > A[mid] implies loguy != mid.    
278    
279            if (mid == higuy)    
280                mid = loguy;    
281    
282            // A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top    
283            // of loop is re-established    
284        }    
285    
286        //     A[i] <= A[mid] for lo <= i < loguy,    
287        //     A[i] > A[mid] for higuy < i < hi,    
288        //     A[hi] >= A[mid]    
289        //     higuy < loguy    
290        // implying:    
291        //     higuy == loguy-1    
292        //     or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid]    
293    
294        // Find adjacent elements equal to the partition element.  The    
295        // doubled loop is to avoid calling comp(mid,mid), since some    
296        // existing comparison funcs don't work when passed the same value    
297        // for both pointers.    
298    
299        higuy += width;    
300        if (mid < higuy)    
301        {    
302            do    
303            {    
304                higuy -= width;    
305            }    
306            while (higuy > mid && __COMPARE(context, higuy, mid) == 0);    
307        }    
308        if (mid >= higuy)    
309        {    
310            do    
311            {    
312                higuy -= width;    
313            }    
314            while (higuy > lo && __COMPARE(context, higuy, mid) == 0);    
315        }    
316    
317        // OK, now we have the following:    
318        //    higuy < loguy    
319        //    lo <= higuy <= hi    
320        //    A[i]  <= A[mid] for lo <= i <= higuy    
321        //    A[i]  == A[mid] for higuy < i < loguy    
322        //    A[i]  >  A[mid] for loguy <= i < hi    
323        //    A[hi] >= A[mid] */    
324    
325        // We've finished the partition, now we want to sort the subarrays    
326        // [lo, higuy] and [loguy, hi].    
327        // We do the smaller one first to minimize stack usage.    
328        // We only sort arrays of length 2 or more.    
329    
330        if (higuy - lo >= hi - loguy)    
331        {    
332            if (lo < higuy)    
333            {    
334                // Save the big recursion for later:    
335                lostk[stkptr] = lo;    
336                histk[stkptr] = higuy;    
337                ++stkptr;    
338            }    
339    
340            if (loguy < hi)    
341            {    
342                // Do the small recursion:    
343                lo = loguy;    
344                goto recurse;    
345            }    
346        }    
347        else    
348        {    
349            if (loguy < hi)    
350            {    
351                // Save the big recursion for later:    
352                lostk[stkptr] = loguy;    
353                histk[stkptr] = hi;    
354                ++stkptr;    
355            }    
356    
357            if (lo < higuy)    
358            {    
359                // Do the small recursion:    
360                hi = higuy;    
361                goto recurse;    
362            }    
363        }    
364    }    
365    
366    // We have sorted the array, except for any pending sorts on the stack.    
367    // Check if there are any, and sort them:    
368    --stkptr;    
369    if (stkptr >= 0)    
370    {    
371        // Pop sub-array from the stack:    
372        lo = lostk[stkptr];    
373        hi = histk[stkptr];    
374        goto recurse;    
375    }    
376    else    
377    {    
378        // Otherwise, all sub-arrays have been sorted:    
379        return;    
380    }    
381}    
382    
383#undef __COMPARE    
384#undef __SHORTSORT