hadoop-common-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From cdoug...@apache.org
Subject svn commit: r666410 - in /hadoop/core/branches/branch-0.17: CHANGES.txt src/java/org/apache/hadoop/util/QuickSort.java
Date Wed, 11 Jun 2008 00:56:56 GMT
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;
+    }
     }
   }
 



Mime
View raw message