You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-commits@hadoop.apache.org by cd...@apache.org on 2008/06/11 02:56:56 UTC
svn commit: r666410 - in /hadoop/core/branches/branch-0.17: CHANGES.txt
src/java/org/apache/hadoop/util/QuickSort.java
Author: cdouglas
Date: Tue Jun 10 17:56:55 2008
New Revision: 666410
URL: http://svn.apache.org/viewvc?rev=666410&view=rev
Log:
HADOOP-3442. Limit recursion depth in QuickSort to avoid StackOverflowErrors.
Modified:
hadoop/core/branches/branch-0.17/CHANGES.txt
hadoop/core/branches/branch-0.17/src/java/org/apache/hadoop/util/QuickSort.java
Modified: hadoop/core/branches/branch-0.17/CHANGES.txt
URL: http://svn.apache.org/viewvc/hadoop/core/branches/branch-0.17/CHANGES.txt?rev=666410&r1=666409&r2=666410&view=diff
==============================================================================
--- hadoop/core/branches/branch-0.17/CHANGES.txt (original)
+++ hadoop/core/branches/branch-0.17/CHANGES.txt Tue Jun 10 17:56:55 2008
@@ -10,7 +10,10 @@
HADOOP-3472 MapFile.Reader getClosest() function returns incorrect results
when before is true (Todd Lipcon via Stack)
-
+
+ HADOOP-3442. Limit recursion depth in QuickSort to avoid
+ StackOverflowErrors. (cdouglas)
+
Release 0.17.0 - 2008-05-18
INCOMPATIBLE CHANGES
Modified: hadoop/core/branches/branch-0.17/src/java/org/apache/hadoop/util/QuickSort.java
URL: http://svn.apache.org/viewvc/hadoop/core/branches/branch-0.17/src/java/org/apache/hadoop/util/QuickSort.java?rev=666410&r1=666409&r2=666410&view=diff
==============================================================================
--- hadoop/core/branches/branch-0.17/src/java/org/apache/hadoop/util/QuickSort.java (original)
+++ hadoop/core/branches/branch-0.17/src/java/org/apache/hadoop/util/QuickSort.java Tue Jun 10 17:56:55 2008
@@ -43,6 +43,7 @@
if (null != rep) {
rep.progress();
}
+ while (true) {
if (r-p < 13) {
for (int i = p; i < r; ++i) {
for (int j = i; j > p; --j) {
@@ -76,10 +77,11 @@
// Recurse on smaller interval first to keep stack shallow
if (i - p - 1 < r - i) {
sort(s, p, i - 1, rep);
- sort(s, i, r, rep);
+ p = i;
} else {
sort(s, i, r, rep);
- sort(s, p, i - 1, rep);
+ r = i - 1;
+ }
}
}