diff options
Diffstat (limited to 'Src/nu/sort.cpp')
| -rw-r--r-- | Src/nu/sort.cpp | 361 |
1 files changed, 361 insertions, 0 deletions
diff --git a/Src/nu/sort.cpp b/Src/nu/sort.cpp new file mode 100644 index 00000000..dea3dada --- /dev/null +++ b/Src/nu/sort.cpp @@ -0,0 +1,361 @@ +#include <bfc/platform/types.h> +#include "sort.h" +#include <assert.h> +/*** +*qsort.c - quicksort algorithm; qsort() library function for sorting arrays +* +* Copyright (c) Microsoft Corporation. All rights reserved. +* +*Purpose: +* To implement the qsort() routine for sorting arrays. +* +*******************************************************************************/ + +/* Always compile this module for speed, not size */ +#pragma optimize("t", on) + +/* prototypes for local routines */ +static void shortsort(uint8_t *lo, uint8_t *hi, size_t width, const void *context, + int (__fastcall *comp)(const void *, const void *, const void *)); +static void swap(uint8_t *p, uint8_t *q, size_t width); + +/* this parameter defines the cutoff between using quick sort and + insertion sort for arrays; arrays with lengths shorter or equal to the + below value use insertion sort */ + +#define CUTOFF 8 /* testing shows that this is good value */ + +/*** +*qsort(base, num, wid, context, comp) - quicksort function for sorting arrays +* +*Purpose: +* quicksort the array of elements +* side effects: sorts in place +* maximum array size is number of elements times size of elements, +* but is limited by the virtual address space of the processor +* +*Entry: +* char *base = pointer to base of array +* size_t num = number of elements in the array +* size_t width = width in bytes of each array element +* int (*comp)() = pointer to function returning analog of strcmp for +* strings, but supplied by user for comparing the array elements. +* it accepts 2 pointers to elements and returns neg if 1<2, 0 if +* 1=2, pos if 1>2. +* +*Exit: +* returns void +* +*Exceptions: +* +*******************************************************************************/ + +/* sort the array between lo and hi (inclusive) */ + +#define STKSIZ (8*sizeof(void*) - 2) + +void __cdecl nu::qsort ( + void *base, + size_t num, + size_t width, + const void *context, + int (__fastcall *comp)(const void *, const void *, const void *) + ) +{ + /* Note: the number of stack entries required is no more than + 1 + log2(num), so 30 is sufficient for any array */ + uint8_t *lo, *hi; /* ends of sub-array currently sorting */ + uint8_t *mid; /* points to middle of subarray */ + uint8_t *loguy, *higuy; /* traveling pointers for partition step */ + size_t size; /* size of the sub-array */ + uint8_t *lostk[STKSIZ] = {0}, *histk[STKSIZ] = {0}; + int stkptr; /* stack for saving sub-array to be processed */ + + assert((width % sizeof(void *)) == 0); + if (num < 2 || width == 0) + return; /* nothing to do */ + + stkptr = 0; /* initialize stack */ + + lo = static_cast<uint8_t *>(base); + hi = (uint8_t *)base + width * (num-1); /* initialize limits */ + + /* this entry point is for pseudo-recursion calling: setting + lo and hi and jumping to here is like recursion, but stkptr is + preserved, locals aren't, so we preserve stuff on the stack */ +recurse: + + size = (hi - lo) / width + 1; /* number of el's to sort */ + + /* below a certain size, it is faster to use a O(n^2) sorting method */ + if (size <= CUTOFF) { + shortsort(lo, hi, width, context, comp); + } + else { + /* First we pick a partitioning element. The efficiency of the + algorithm demands that we find one that is approximately the median + of the values, but also that we select one fast. We choose the + median of the first, middle, and last elements, to avoid bad + performance in the face of already sorted data, or data that is made + up of multiple sorted runs appended together. Testing shows that a + median-of-three algorithm provides better performance than simply + picking the middle element for the latter case. */ + + mid = lo + (size / 2) * width; /* find middle element */ + + /* Sort the first, middle, last elements into order */ + if (comp(lo, mid, context) > 0) { + swap(lo, mid, width); + } + if (comp(lo, hi, context) > 0) { + swap(lo, hi, width); + } + if (comp(mid, hi, context) > 0) { + swap(mid, hi, width); + } + + /* We now wish to partition the array into three pieces, one consisting + of elements <= partition element, one of elements equal to the + partition element, and one of elements > than it. This is done + below; comments indicate conditions established at every step. */ + + loguy = lo; + higuy = hi; + + /* Note that higuy decreases and loguy increases on every iteration, + so loop must terminate. */ + for (;;) { + /* lo <= loguy < hi, lo < higuy <= hi, + A[i] <= A[mid] for lo <= i <= loguy, + A[i] > A[mid] for higuy <= i < hi, + A[hi] >= A[mid] */ + + /* The doubled loop is to avoid calling comp(mid,mid), since some + existing comparison funcs don't work when passed the same + value for both pointers. */ + + if (mid > loguy) { + do { + loguy += width; + } while (loguy < mid && comp(loguy, mid, context) <= 0); + } + if (mid <= loguy) { + do { + loguy += width; + } while (loguy <= hi && comp(loguy, mid, context) <= 0); + } + + /* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy, + either loguy > hi or A[loguy] > A[mid] */ + + do { + higuy -= width; + } while (higuy > mid && comp(higuy, mid, context) > 0); + + /* lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi, + either higuy == lo or A[higuy] <= A[mid] */ + + if (higuy < loguy) + break; + + /* if loguy > hi or higuy == lo, then we would have exited, so + A[loguy] > A[mid], A[higuy] <= A[mid], + loguy <= hi, higuy > lo */ + + swap(loguy, higuy, width); + + /* If the partition element was moved, follow it. Only need + to check for mid == higuy, since before the swap, + A[loguy] > A[mid] implies loguy != mid. */ + + if (mid == higuy) + mid = loguy; + + /* A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top + of loop is re-established */ + } + + /* A[i] <= A[mid] for lo <= i < loguy, + A[i] > A[mid] for higuy < i < hi, + A[hi] >= A[mid] + higuy < loguy + implying: + higuy == loguy-1 + or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid] */ + + /* Find adjacent elements equal to the partition element. The + doubled loop is to avoid calling comp(mid,mid), since some + existing comparison funcs don't work when passed the same value + for both pointers. */ + + higuy += width; + if (mid < higuy) { + do { + higuy -= width; + } while (higuy > mid && comp(higuy, mid, context) == 0); + } + if (mid >= higuy) { + do { + higuy -= width; + } while (higuy > lo && comp(higuy, mid, context) == 0); + } + + /* OK, now we have the following: + higuy < loguy + lo <= higuy <= hi + A[i] <= A[mid] for lo <= i <= higuy + A[i] == A[mid] for higuy < i < loguy + A[i] > A[mid] for loguy <= i < hi + A[hi] >= A[mid] */ + + /* We've finished the partition, now we want to sort the subarrays + [lo, higuy] and [loguy, hi]. + We do the smaller one first to minimize stack usage. + We only sort arrays of length 2 or more.*/ + + if ( higuy - lo >= hi - loguy ) { + if (lo < higuy) { + lostk[stkptr] = lo; + histk[stkptr] = higuy; + ++stkptr; + } /* save big recursion for later */ + + if (loguy < hi) { + lo = loguy; + goto recurse; /* do small recursion */ + } + } + else { + if (loguy < hi) { + lostk[stkptr] = loguy; + histk[stkptr] = hi; + ++stkptr; /* save big recursion for later */ + } + + if (lo < higuy) { + hi = higuy; + goto recurse; /* do small recursion */ + } + } + } + + /* We have sorted the array, except for any pending sorts on the stack. + Check if there are any, and do them. */ + + --stkptr; + if (stkptr >= 0) { + lo = lostk[stkptr]; + hi = histk[stkptr]; + goto recurse; /* pop subarray from stack */ + } + else + return; /* all subarrays done */ +} + + +/*** +*shortsort(hi, lo, width, comp) - insertion sort for sorting short arrays +* +*Purpose: +* sorts the sub-array of elements between lo and hi (inclusive) +* side effects: sorts in place +* assumes that lo < hi +* +*Entry: +* char *lo = pointer to low element to sort +* char *hi = pointer to high element to sort +* size_t width = width in bytes of each array element +* int (*comp)() = pointer to function returning analog of strcmp for +* strings, but supplied by user for comparing the array elements. +* it accepts 2 pointers to elements and returns neg if 1<2, 0 if +* 1=2, pos if 1>2. +* +*Exit: +* returns void +* +*Exceptions: +* +*******************************************************************************/ + +static void __cdecl shortsort ( + uint8_t *lo, + uint8_t *hi, + size_t width, + const void *context, + int (__fastcall *comp)(const void *, const void *, const void *) + ) +{ + uint8_t *p; + + /* Note: in assertions below, i and j are alway inside original bound of + array to sort. */ + + while (hi > lo) { + /* A[i] <= A[j] for i <= j, j > hi */ + uint8_t *max = lo; + for (p = lo+width; p <= hi; p += width) { + /* A[i] <= A[max] for lo <= i < p */ + if (comp(p, max, context) > 0) { + max = p; + } + /* A[i] <= A[max] for lo <= i <= p */ + } + + /* A[i] <= A[max] for lo <= i <= hi */ + + swap(max, hi, width); + + /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */ + + hi -= width; + + /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */ + } + /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j, + so array is sorted */ +} + + +/*** +*swap(a, b, width) - swap two elements +* +*Purpose: +* swaps the two array elements of size width +* +*Entry: +* char *a, *b = pointer to two elements to swap +* size_t width = width in bytes of each array element +* +*Exit: +* returns void +* +*Exceptions: +* +*******************************************************************************/ + +static void swap ( + uint8_t *_a, + uint8_t *_b, + size_t width + ) +{ +#if 1 + void *tmp; + void **a = (void **)_a; + void **b = (void **)_b; + if ( a != b ) + /* Do the swap one character at a time to avoid potential alignment + problems. */ + do { + tmp = *a; + *a++ = *b; + *b++ = tmp; + width-=sizeof(void *); + } while (width); +#else + //void *temp = alloca(width); + memcpy(temp, a, width); + memcpy(a, b, width); + memcpy(b, temp, width); + #endif +} |