From 9c9e2c6b1db3e2529b057981f8286554cc76f636 Mon Sep 17 00:00:00 2001 From: Jeffrey Stedfast Date: Tue, 7 Aug 2012 12:03:24 -0400 Subject: [PATCH] [corlib] Make all qsort() implementations completely non-recursive This is a better fix for StackOverflowExceptions on large data sets. --- mcs/class/corlib/System/Array.cs | 309 +++++++++++++++++++++++-------- 1 file changed, 235 insertions(+), 74 deletions(-) diff --git a/mcs/class/corlib/System/Array.cs b/mcs/class/corlib/System/Array.cs index 71a85aaea3c..5606a62501e 100644 --- a/mcs/class/corlib/System/Array.cs +++ b/mcs/class/corlib/System/Array.cs @@ -1417,6 +1417,11 @@ namespace System array [j] = val; } + struct QSortStack { + public int high; + public int low; + } + static bool QSortArrange (Array keys, Array items, int lo, ref object v0, int hi, ref object v1, IComparer comparer) { IComparable cmp; @@ -1447,14 +1452,25 @@ namespace System return false; } - private static void qsort (Array keys, Array items, int low, int high, IComparer comparer) + private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer) { + QSortStack[] stack = new QSortStack[32]; //const int QSORT_THRESHOLD = 7; + int high, low, mid, i, k; object key, hi, lo; IComparable cmp; - int mid, i, k; + int sp = 1; + + // initialize our stack + stack[0].high = high0; + stack[0].low = low0; do { + // pop the stack + sp--; + high = stack[sp].high; + low = stack[sp].low; + // TODO: implement InsertionSort when QSORT_THRESHOLD reached // calculate the middle element @@ -1521,19 +1537,34 @@ namespace System swap (keys, items, mid, k); } - // recursively sort the smallest partition - if ((high - (k + 1)) < ((k - 1) - low)) { - if ((k + 1) < high) - qsort (keys, items, k + 1, high, comparer); + // push our partitions onto the stack, largest first + // (to make sure we don't run out of stack space) + if ((high - k) >= (k - low)) { + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } - high = k - 1; + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } } else { - if ((k - 1) > low) - qsort (keys, items, low, k - 1, comparer); + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } - low = k + 1; + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } } - } while (low < high); + } while (sp > 0); } private static void CheckComparerAvailable (Array keys, int low, int high) @@ -1854,13 +1885,24 @@ namespace System return false; } - private static void qsort (T[] keys, U[] items, int low, int high) where T : IComparable + private static void qsort (T[] keys, U[] items, int low0, int high0) where T : IComparable { + QSortStack[] stack = new QSortStack[32]; const int QSORT_THRESHOLD = 7; - int mid, i, k; + int high, low, mid, i, k; + int sp = 1; T key; + // initialize our stack + stack[0].high = high0; + stack[0].low = low0; + do { + // pop the stack + sp--; + high = stack[sp].high; + low = stack[sp].low; + if ((low + QSORT_THRESHOLD) > high) { // switch to insertion sort for (i = low + 1; i <= high; i++) { @@ -1876,7 +1918,7 @@ namespace System } } - return; + continue; } // calculate the middle element @@ -1932,29 +1974,55 @@ namespace System swap (keys, items, mid, k); } - // recursively sort the smallest partition - if ((high - (k + 1)) < ((k - 1) - low)) { - if ((k + 1) < high) - qsort (keys, items, k + 1, high); + // push our partitions onto the stack, largest first + // (to make sure we don't run out of stack space) + if ((high - k) >= (k - low)) { + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } - high = k - 1; + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } } else { - if ((k - 1) > low) - qsort (keys, items, low, k - 1); + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } - low = k + 1; + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } } - } while (low < high); + } while (sp > 0); } // Specialized version for items==null - private static void qsort (T[] keys, int low, int high) where T : IComparable + private static void qsort (T[] keys, int low0, int high0) where T : IComparable { + QSortStack[] stack = new QSortStack[32]; const int QSORT_THRESHOLD = 7; - int mid, i, k; + int high, low, mid, i, k; + int sp = 1; T key; - + + // initialize our stack + stack[0].high = high0; + stack[0].low = low0; + do { + // pop the stack + sp--; + high = stack[sp].high; + low = stack[sp].low; + if ((low + QSORT_THRESHOLD) > high) { // switch to insertion sort for (i = low + 1; i <= high; i++) { @@ -1970,7 +2038,7 @@ namespace System } } - return; + continue; } // calculate the middle element @@ -2025,21 +2093,36 @@ namespace System // swap the pivot with the last element in the first partition swap (keys, mid, k); } - - // recursively sort the smallest partition - if ((high - (k + 1)) < ((k - 1) - low)) { - if ((k + 1) < high) - qsort (keys, k + 1, high); + + // push our partitions onto the stack, largest first + // (to make sure we don't run out of stack space) + if ((high - k) >= (k - low)) { + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } - high = k - 1; + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } } else { - if ((k - 1) > low) - qsort (keys, low, k - 1); + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } - low = k + 1; + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } } - } while (low < high); - } + } while (sp > 0); + } static bool QSortArrange (K [] keys, V [] items, int lo, int hi, IComparer comparer) { @@ -2122,15 +2205,26 @@ namespace System return false; } - private static void qsort (K [] keys, V [] items, int low, int high, IComparer comparer) + private static void qsort (K [] keys, V [] items, int low0, int high0, IComparer comparer) { + QSortStack[] stack = new QSortStack[32]; const int QSORT_THRESHOLD = 7; + int high, low, mid, i, k; IComparable gcmp; IComparable cmp; - int mid, i, k; + int sp = 1; K key; + // initialize our stack + stack[0].high = high0; + stack[0].low = low0; + do { + // pop the stack + sp--; + high = stack[sp].high; + low = stack[sp].low; + if ((low + QSORT_THRESHOLD) > high) { // switch to insertion sort for (i = low + 1; i <= high; i++) { @@ -2160,7 +2254,7 @@ namespace System } } - return; + continue; } // calculate the middle element @@ -2231,31 +2325,57 @@ namespace System swap (keys, items, mid, k); } - // recursively sort the smallest partition - if ((high - (k + 1)) < ((k - 1) - low)) { - if ((k + 1) < high) - qsort (keys, items, k + 1, high, comparer); + // push our partitions onto the stack, largest first + // (to make sure we don't run out of stack space) + if ((high - k) >= (k - low)) { + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } - high = k - 1; + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } } else { - if ((k - 1) > low) - qsort (keys, items, low, k - 1, comparer); + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } - low = k + 1; + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } } - } while (low < high); + } while (sp > 0); } // Specialized version for items==null - private static void qsort (K [] keys, int low, int high, IComparer comparer) + private static void qsort (K [] keys, int low0, int high0, IComparer comparer) { + QSortStack[] stack = new QSortStack[32]; const int QSORT_THRESHOLD = 7; + int high, low, mid, i, k; IComparable gcmp; IComparable cmp; - int mid, i, k; + int sp = 1; K key; + // initialize our stack + stack[0].high = high0; + stack[0].low = low0; + do { + // pop the stack + sp--; + high = stack[sp].high; + low = stack[sp].low; + if ((low + QSORT_THRESHOLD) > high) { // switch to insertion sort for (i = low + 1; i <= high; i++) { @@ -2285,7 +2405,7 @@ namespace System } } - return; + continue; } // calculate the middle element @@ -2356,19 +2476,34 @@ namespace System swap (keys, mid, k); } - // recursively sort the smallest partition - if ((high - (k + 1)) < ((k - 1) - low)) { - if ((k + 1) < high) - qsort (keys, k + 1, high, comparer); + // push our partitions onto the stack, largest first + // (to make sure we don't run out of stack space) + if ((high - k) >= (k - low)) { + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } - high = k - 1; + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } } else { - if ((k - 1) > low) - qsort (keys, low, k - 1, comparer); + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } - low = k + 1; + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } } - } while (low < high); + } while (sp > 0); } static bool QSortArrange (T [] array, int lo, int hi, Comparison compare) @@ -2383,13 +2518,24 @@ namespace System return false; } - private static void qsort (T [] array, int low, int high, Comparison compare) + private static void qsort (T [] array, int low0, int high0, Comparison compare) { + QSortStack[] stack = new QSortStack[32]; const int QSORT_THRESHOLD = 7; - int mid, i, k; + int high, low, mid, i, k; + int sp = 1; T key; + // initialize our stack + stack[0].high = high0; + stack[0].low = low0; + do { + // pop the stack + sp--; + high = stack[sp].high; + low = stack[sp].low; + if ((low + QSORT_THRESHOLD) > high) { // switch to insertion sort for (i = low + 1; i <= high; i++) { @@ -2405,7 +2551,7 @@ namespace System } } - return; + continue; } // calculate the middle element @@ -2462,19 +2608,34 @@ namespace System swap (array, mid, k); } - // recursively sort the smallest partition - if ((high - (k + 1)) < ((k - 1) - low)) { - if ((k + 1) < high) - qsort (array, k + 1, high, compare); + // push our partitions onto the stack, largest first + // (to make sure we don't run out of stack space) + if ((high - k) >= (k - low)) { + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } - high = k - 1; + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } } else { - if ((k - 1) > low) - qsort (array, low, k - 1, compare); + if ((k - 1) > low) { + stack[sp].high = k - 1; + stack[sp].low = low; + sp++; + } - low = k + 1; + if ((k + 1) < high) { + stack[sp].high = high; + stack[sp].low = k + 1; + sp++; + } } - } while (low < high); + } while (sp > 0); } private static void CheckComparerAvailable (K [] keys, int low, int high) -- 2.25.1