Attachment 198271 Details for Bug 317785 – fixed comparator implementation incl unit tests (without GPL component)

[patch] fixed comparator implementation incl unit tests (without GPL component)

bug317785_new_comparator_implementation.patch (text/plain), 23.87 KB, created by Martin W. Kirst

on 2011-06-20 13:28:22 EDT

(hide)

Description:

Filename:

MIME Type:

Creator: Martin W. Kirst

Created: 2011-06-20 13:28:22 EDT

Size: 23.87 KB

patch

obsolete

>### Eclipse Workspace Patch 1.0
>#P org.eclipse.equinox.p2.artifact.repository
>Index: src/org/eclipse/equinox/internal/p2/artifact/repository/MirrorSelector.java
>===================================================================
>RCS file: /cvsroot/rt/org.eclipse.equinox/p2/bundles/org.eclipse.equinox.p2.artifact.repository/src/org/eclipse/equinox/internal/p2/artifact/repository/MirrorSelector.java,v
>retrieving revision 1.22
>diff -u -r1.22 MirrorSelector.java
>--- src/org/eclipse/equinox/internal/p2/artifact/repository/MirrorSelector.java	2 May 2011 22:20:15 -0000	1.22
>+++ src/org/eclipse/equinox/internal/p2/artifact/repository/MirrorSelector.java	20 Jun 2011 17:20:08 -0000
>@@ -8,9 +8,15 @@
>  * Contributors:
>  *     IBM Corporation - initial API and implementation
>  *     Cloudsmith Inc - bug fixes
>+ *     martin.kirst@s1998.tu-chemnitz.de - fixed and improved sort algorithm
>  *******************************************************************************/
> package org.eclipse.equinox.internal.p2.artifact.repository;
> 
>+import static java.lang.Math.abs;
>+import static java.lang.Math.max;
>+import static java.lang.Math.min;
>+import static java.lang.Math.sqrt;
>+
> import java.io.FileNotFoundException;
> import java.net.URI;
> import java.net.URISyntaxException;
>@@ -33,6 +39,9 @@
>  * The contents of the file at this URL is expected to be an XML document 
>  * containing a list of <mirror> elements. The mirrors are assumed to be already 
>  * sorted geographically with closer mirrors first.
>+ * <br><br>
>+ * Always use {@link MirrorSelector.MirrorInfoComparator} for comparison.
>+ *
>  */
> public class MirrorSelector {
> 	private static final double LOG2 = Math.log(2);
>@@ -40,7 +49,7 @@
> 	/**
> 	 * Encapsulates information about a single mirror
> 	 */
>-	public static class MirrorInfo implements Comparable<MirrorInfo> {
>+	public static class MirrorInfo {
> 		private static final long PRIMARY_FAILURE_LINGER_TIME = 30000; // Retry again after 30 seconds
> 		private static final long SECONDARY_FAILURE_LINGER_TIME = 300000; // Wait 5 minutes
> 		private static final int ACCEPTABLE_FILE_NOT_FOUND_COUNT = 5; // Given an established connection, those are generally quick
>@@ -50,7 +59,7 @@
> 		int failureCount;
> 		int fileNotFoundCount;
> 		int totalFailureCount;
>-		private final int initialRank;
>+		final int initialRank;
> 		String locationString;
> 
> 		public MirrorInfo(String location, int initialRank) {
>@@ -63,44 +72,7 @@
> 			bytesPerSecond = DownloadStatus.UNKNOWN_RATE;
> 		}
> 
>-		/**
>-		 * Comparison used to sort mirrors.
>-		 */
>-		public synchronized int compareTo(MirrorInfo that) {
>-			synchronized (that) {
>-				double rank = 0.0;
>-				if (bytesPerSecond != that.bytesPerSecond) {
>-					if (bytesPerSecond != DownloadStatus.UNKNOWN_RATE && that.bytesPerSecond != DownloadStatus.UNKNOWN_RATE) {
>-						if (bytesPerSecond > that.bytesPerSecond)
>-							rank -= (double) bytesPerSecond / (double) that.bytesPerSecond;
>-						else
>-							rank += (double) that.bytesPerSecond / (double) bytesPerSecond;
>-					}
>-				}
>-
>-				//less failures is better
>-				if (failureCount != that.failureCount) {
>-					if (failureCount > that.failureCount)
>-						rank += ((double) (failureCount + 1) / (double) (that.failureCount + 1)) * 2.0;
>-					else
>-						rank -= ((double) (that.failureCount + 1) / (double) (failureCount + 1)) * 2.0;
>-				}
>-
>-				if (rank == 0.0)
>-					//trust that initial rank indicates geographical proximity
>-					rank = initialRank - that.initialRank;
>-
>-				if (rank == 0.0)
>-					return 0;
>-
>-				int intRank;
>-				intRank = (int) rank;
>-				if (intRank == 0)
>-					intRank = rank > 0 ? 1 : -1;
>-				return intRank;
>-			}
>-		}
>-
>+		@Override
> 		public synchronized String toString() {
> 			return "Mirror(" + locationString + ',' + failureCount + ',' + bytesPerSecond + ')'; //$NON-NLS-1$
> 		}
>@@ -134,6 +106,10 @@
> 			bytesPerSecond = newValue;
> 		}
> 
>+		public synchronized long getBytesPerSecond() {
>+			return bytesPerSecond;
>+		}
>+
> 		public synchronized void incrementFileNotFoundCount() {
> 			if (++fileNotFoundCount > ACCEPTABLE_FILE_NOT_FOUND_COUNT) {
> 				incrementFailureCount();
>@@ -178,6 +154,97 @@
> 	}
> 
> 	/**
>+	 * This {@link Comparator} uses a vector space classification algorithm
>+	 * and implements some kind of Rocchio Classification.
>+	 * In theory, when sorting multiple mirrors, we want to know which one
>+	 * is the best in terms of its attributes 'bytesPerSecons', 'failureCount'
>+	 * and 'initialRank'.
>+	 * This {@link Comparator} needs three initial query attributes, which mean
>+	 * to search for the fastest mirror, with lowest failure and nearest to the
>+	 * initial rank.
>+	 * By calculating the vector space distance from query to Object 1 and
>+	 * query to Object 2, we implicitly know, which mirror is better.
>+	 * <br><br>
>+	 * There are two weight factors, which directly influences sorting results.
>+	 * They are computed by using a one real live mirror list of eclipse.org
>+	 * and tweak as long as the results look good as a list ;-)
>+	 * See test case fore more details.
>+	 * <br><br>
>+	 * <h4>Mathematical basics used in
>+	 *  {@link MirrorInfoComparator#compare(MirrorInfo, MirrorInfo)}:</h4>
>+	 * Given two vectors Q and T, where Q is query and t is Target
>+	 * and Q_a (or T_a) are attributes of each vector, this is
>+	 * the formula, which is computed to each MirrorInfo object.
>+	 * <pre>
>+	 *                       ->   ->
>+	 *                       q  * t                             (dot product)
>+	 *  sim(q,t) = --------------------------- 
>+	 *               / || -> ||   || -> || \
>+	 *              |  || q  || * || t  ||  |             (euclidean lengths)
>+	 *               \                     /
>+	 *  
>+	 *                              N
>+	 *                             ---
>+	 *                             \
>+	 *                              >   Q   * T           
>+	 *                             /     ai    ai
>+	 *                             ---
>+	 *                            i = 1
>+	 *  sim(q,t) = -----------------------------------------
>+	 *               /     ___________       ___________ \
>+	 *              |     |   N             |   N         |
>+	 *              |     |  ---            |  ---        |
>+	 *              |  _  |  \     2     _  |  \     2    |
>+	 *              |   \ |   >   Q    *  \ |   >   T     |
>+	 *              |    \|  /     ai      \|  /     ai   |
>+	 *              |     |  ---            |  ---        |
>+	 *               \    | i = 1           | i = 1      / 
>+	 * </pre>
>+	 */
>+	public static final class MirrorInfoComparator implements Comparator<MirrorInfo> {
>+
>+		/**
>+		 * This weight is used to treat speed attribute in 25kByte steps.
>+		 */
>+		static final double WEIGHT_BYTESPERSECOND = 1d / 25000d;
>+		/**
>+		 * This weight influences the failureCount classification
>+		 * Value was calculated by empirical tests. 
>+		 */
>+		static final double WEIGHT_FAILURECOUNT = 1.75d;
>+
>+		final double qBytesPerSeconds;
>+		final double qFailureCount;
>+		final double qRank;
>+		final double qel; // euclidean length
>+
>+		public MirrorInfoComparator(long qBytesPerSeconds, int qFailureCount, int qRank) {
>+			// Query: bytesPerSecondond=max + 10%, failureCountr=0, rank=1
>+			this.qBytesPerSeconds = (qBytesPerSeconds + qBytesPerSeconds / 10) * WEIGHT_BYTESPERSECOND;
>+			this.qFailureCount = qFailureCount;
>+			this.qRank = qRank;
>+			this.qel = sqrt(qBytesPerSeconds * qBytesPerSeconds + (qFailureCount * 1d) * (qFailureCount * 1d) + qRank * qRank);
>+		}
>+
>+		public int compare(MirrorInfo o1, MirrorInfo o2) {
>+			if (o1 == o2) {
>+				return 0; // shortest way
>+			}
>+			// euclidean lengths
>+			double o1_el = sqrt(abs(o1.bytesPerSecond * WEIGHT_BYTESPERSECOND) * abs(o1.bytesPerSecond * WEIGHT_BYTESPERSECOND) + (o1.failureCount * WEIGHT_FAILURECOUNT) * (o1.failureCount * WEIGHT_FAILURECOUNT) + o1.initialRank * o1.initialRank);
>+			double o2_el = sqrt(abs(o2.bytesPerSecond * WEIGHT_BYTESPERSECOND) * abs(o2.bytesPerSecond * WEIGHT_BYTESPERSECOND) + (o2.failureCount * WEIGHT_FAILURECOUNT) * (o2.failureCount * WEIGHT_FAILURECOUNT) + o2.initialRank * o2.initialRank);
>+			// vector dot products
>+			double dp_1 = (qBytesPerSeconds * abs(o1.bytesPerSecond * WEIGHT_BYTESPERSECOND) + qFailureCount * (o1.failureCount * WEIGHT_FAILURECOUNT) + qRank * o1.initialRank);
>+			double dp_2 = (qBytesPerSeconds * abs(o2.bytesPerSecond * WEIGHT_BYTESPERSECOND) + qFailureCount * (o2.failureCount * WEIGHT_FAILURECOUNT) + qRank * o2.initialRank);
>+			// similarities from o1 to Q and o2 to Q (where q=query)
>+			double sim1 = dp_1 / (qel * o1_el);
>+			double sim2 = dp_2 / (qel * o2_el);
>+			return new Double(sim2).compareTo(new Double(sim1));
>+		}
>+
>+	}
>+
>+	/**
> 	 * Parses the given mirror URL to obtain the list of mirrors. Returns the mirrors,
> 	 * or null if mirrors could not be computed.
> 	 * 
>@@ -270,6 +337,17 @@
> 		return mirrors;
> 	}
> 
>+	private MirrorInfoComparator getComparator() {
>+		long maxBytesPerSecond = 0;
>+		if (mirrors != null) {
>+			for (MirrorInfo mi : mirrors) {
>+				maxBytesPerSecond = max(maxBytesPerSecond, mi.bytesPerSecond);
>+			}
>+		}
>+		// Use the fastest mirror, with 0 failures and initial rank 1 as base query
>+		return new MirrorInfoComparator(maxBytesPerSecond, 0, 1);
>+	}
>+
> 	private void log(String message, Throwable exception) {
> 		LogHelper.log(new Status(IStatus.ERROR, Activator.ID, message, exception));
> 	}
>@@ -316,7 +394,7 @@
> 		// return true if there is a mirror and it doesn't have multiple failures.
> 		if (mirrors == null || mirrors.length == 0)
> 			return false;
>-		Arrays.sort(mirrors);
>+		Arrays.sort(mirrors, getComparator());
> 		return mirrors[0].failureCount < 2;
> 	}
> 
>@@ -326,7 +404,7 @@
> 	 */
> 	private MirrorInfo selectMirror(IProgressMonitor monitor) {
> 		initMirrors(monitor);
>-		int mirrorCount;
>+		final int mirrorCount;
> 		if (mirrors == null || (mirrorCount = mirrors.length) == 0)
> 			return null;
> 
>@@ -334,7 +412,7 @@
> 		if (mirrorCount == 1)
> 			selected = mirrors[0];
> 		else {
>-			Arrays.sort(mirrors);
>+			Arrays.sort(mirrors, getComparator());
> 			for (;;) {
> 				//this is a function that randomly selects a mirror based on a logarithmic
> 				//distribution. Mirror 0 has a 1/2 chance of being selected, mirror 1 has a 1/4 chance, 
>@@ -342,7 +420,7 @@
> 				//selection, while still heavily favoring better mirrors
> 				//the algorithm computes the most significant digit in a binary number by computing the base 2 logarithm
> 				//if the first digit is most significant, mirror 0 is selected, if the second is most significant, mirror 1 is selected, etc
>-				int highestMirror = Math.min(15, mirrorCount);
>+				int highestMirror = min(15, mirrorCount);
> 				int result = (int) (Math.log(random.nextInt(1 << highestMirror) + 1) / LOG2);
> 				if (result >= highestMirror || result < 0)
> 					result = highestMirror - 1;
>@@ -350,9 +428,8 @@
> 				int mirrorIndex = highestMirror - 1 - result;
> 				selected = mirrors[mirrorIndex];
> 
>-				// If the ranking of the selected mirror is significantly worse then the top ranked
>-				// mirror, then we consider this a bad choice and reiterate.
>-				if (mirrorIndex == 0 || mirrors[0].compareTo(selected) < 4)
>+				// Only choose a mirror from the best 50% of the top 15 of all mirrors
>+				if (mirrorIndex <= (mirrorCount * 0.5d))
> 					// This is good enough
> 					break;
> 			}
>#P org.eclipse.equinox.p2.tests
>Index: src/org/eclipse/equinox/p2/tests/artifact/repository/MirrorSelectorTest.java
>===================================================================
>RCS file: /cvsroot/rt/org.eclipse.equinox/p2/bundles/org.eclipse.equinox.p2.tests/src/org/eclipse/equinox/p2/tests/artifact/repository/MirrorSelectorTest.java,v
>retrieving revision 1.3
>diff -u -r1.3 MirrorSelectorTest.java
>--- src/org/eclipse/equinox/p2/tests/artifact/repository/MirrorSelectorTest.java	2 May 2011 23:03:09 -0000	1.3
>+++ src/org/eclipse/equinox/p2/tests/artifact/repository/MirrorSelectorTest.java	20 Jun 2011 17:20:10 -0000
>@@ -7,65 +7,312 @@
>  * 
>  * Contributors:
>  *     IBM Corporation - initial API and implementation
>+ *     martin.kirst@s1998.tu-chemnitz.de - fixed and improved sort algorithm tests
>  *******************************************************************************/
> package org.eclipse.equinox.p2.tests.artifact.repository;
> 
>-import java.util.Arrays;
>+import java.util.*;
>+import junit.framework.TestCase;
>+import org.eclipse.equinox.internal.p2.artifact.repository.MirrorSelector;
> import org.eclipse.equinox.internal.p2.artifact.repository.MirrorSelector.MirrorInfo;
>-import org.eclipse.equinox.p2.tests.AbstractProvisioningTest;
> 
> /**
>  * 
>  */
>-public class MirrorSelectorTest extends AbstractProvisioningTest {
>+public class MirrorSelectorTest extends TestCase {
>+
>+	private List<MirrorInfo> originals;
>+
>+	@Override
>+	protected void setUp() throws Exception {
>+		super.setUp();
>+
>+		// examples taken from real live.
>+		// This is the expected order of mirrors,
>+		// doesn't matter how often you're resorting ;-)
>+
>+		originals = new ArrayList<MirrorSelector.MirrorInfo>();
>+		MirrorInfo mi = null;
>+
>+		mi = new MirrorInfo("http://ftp.wh2.tu-dresden.de/pub/mirrors/eclipse/", 3);
>+		mi.setBytesPerSecond(224906);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp-stud.fht-esslingen.de/pub/Mirrors/eclipse/", 1);
>+		mi.setBytesPerSecond(125868);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://mirror.netcologne.de/eclipse//", 0);
>+		mi.setBytesPerSecond(199719);
>+		mi.incrementFailureCount();
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 2;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://mirror.selfnet.de/eclipse/", 5);
>+		mi.setBytesPerSecond(132379);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://mirror.switch.ch/eclipse/", 7);
>+		mi.setBytesPerSecond(137107);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://www.rcp-vision.com/eclipse/eclipseMirror/", 8);
>+		mi.setBytesPerSecond(128472);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://eclipse.mirror.garr.it/mirrors/eclipse//", 10);
>+		mi.setBytesPerSecond(129359);
>+		mi.incrementFailureCount();
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 2;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.roedu.net/pub/mirrors/eclipse.org/", 6);
>+		mi.setBytesPerSecond(59587);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://giano.com.dist.unige.it/eclipse/", 9);
>+		mi.setBytesPerSecond(85624);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.roedu.net/mirrors/eclipse.org//", 19);
>+		mi.setBytesPerSecond(149572);
>+		mi.incrementFailureCount();
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 2;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.ing.umu.se/mirror/eclipse/", 18);
>+		mi.setBytesPerSecond(105858);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://mirrors.fe.up.pt/pub/eclipse//", 15);
>+		mi.setBytesPerSecond(67202);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.heanet.ie/pub/eclipse//", 17);
>+		mi.setBytesPerSecond(68067);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.sh.cvut.cz/MIRRORS/eclipse/", 21);
>+		mi.setBytesPerSecond(73659);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.man.poznan.pl/eclipse/", 22);
>+		mi.setBytesPerSecond(73446);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://eclipse.dcc.fc.up.pt/", 16);
>+		mi.setBytesPerSecond(45175);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://eclipse.nordnet.fi/eclipse/", 23);
>+		mi.setBytesPerSecond(61443);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://www.gtlib.gatech.edu/pub/eclipse/", 26);
>+		mi.setBytesPerSecond(57637);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.osuosl.org/pub/eclipse//", 28);
>+		mi.setBytesPerSecond(35928);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://mirrors.med.harvard.edu/eclipse//", 32);
>+		mi.setBytesPerSecond(40683);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://mirrors.ibiblio.org/pub/mirrors/eclipse/", 31);
>+		mi.setBytesPerSecond(34207);
>+		mi.incrementFailureCount();
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 2;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.ussg.iu.edu/eclipse/", 33);
>+		mi.setBytesPerSecond(31402);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://mirrors.xmission.com/eclipse/", 29);
>+		mi.setBytesPerSecond(24147);
>+		mi.incrementFailureCount();
>+		//mi.totalFailureCount = 1;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.osuosl.org/pub/eclipse/", 34);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://www.ftp.saix.net/Eclipse//", 40);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.daum.net/eclipse/", 41);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://eclipse.stu.edu.tw/", 43);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://eclipse.stu.edu.tw/", 44);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.kaist.ac.kr/eclipse/", 45);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://eclipse.stu.edu.tw//", 46);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.tsukuba.wide.ad.jp/software/eclipse//", 47);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://mirror.neu.edu.cn/eclipse/", 50);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://mirror.bit.edu.cn/eclipse/", 51);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.cs.pu.edu.tw/pub/eclipse/", 52);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://ftp.neu.edu.cn/mirrors/eclipse/", 53);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://download.actuatechina.com/eclipse/", 54);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://linorg.usp.br/eclipse/", 57);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://eclipse.c3sl.ufpr.br/", 59);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+		mi = new MirrorInfo("http://download.eclipse.org/", 61);
>+		mi.setBytesPerSecond(-1);
>+		//mi.totalFailureCount = 0;
>+		originals.add(mi);
>+
>+	}
>+
> 	public void testSorting() {
>-		MirrorInfo one = new MirrorInfo("one", 0);
>-		MirrorInfo two = new MirrorInfo("two", 1);
>-		MirrorInfo three = new MirrorInfo("three", 2);
>-		MirrorInfo four = new MirrorInfo("four", 3);
>-
>-		MirrorInfo[] sorted = new MirrorInfo[] {one, two, three, four};
>-		Arrays.sort(sorted);
>-		assertOrder("1.0", sorted, one, two, three, four);
>-
>-		//make sure order on initial rank is correct
>-		sorted = new MirrorInfo[] {four, two, three, one};
>-		Arrays.sort(sorted);
>-		assertOrder("1.1", sorted, one, two, three, four);
>-
>-		//increase the failure count and ensure order is correctly updated
>-		one.incrementFailureCount();
>-		one.incrementFailureCount();
>-		two.incrementFailureCount();
>-		Arrays.sort(sorted);
>-		assertOrder("1.2", sorted, three, four, two, one);
>-
>-		//go back to default order
>-		one = new MirrorInfo("one", 0);
>-		two = new MirrorInfo("two", 1);
>-		three = new MirrorInfo("three", 2);
>-		four = new MirrorInfo("four", 3);
>-		sorted = new MirrorInfo[] {one, two, three, four};
>-
>-		//set bit rate and ensure order is updated
>-		one.setBytesPerSecond(100L);
>-		two.setBytesPerSecond(400L);
>-		three.setBytesPerSecond(800L);
>-		four.setBytesPerSecond(600L);
>-		Arrays.sort(sorted);
>-		assertOrder("1.3", sorted, three, four, two, one);
>-
>-		//introduce a failure and ensure order is updated but that
>-		//the failure isn't put last
>-		three.incrementFailureCount();
>-		Arrays.sort(sorted);
>-		assertOrder("1.4", sorted, four, two, three, one);
>+
>+		long maxBytesPerSecond = 0;
>+		for (MirrorInfo x : originals) {
>+			maxBytesPerSecond = Math.max(maxBytesPerSecond, x.getBytesPerSecond());
>+		}
>+
>+		MirrorSelector.MirrorInfoComparator comparator = new MirrorSelector.MirrorInfoComparator(maxBytesPerSecond, 0, 0);
>+
>+		// do 1000 tries of randomize and new sort
>+		// the result should always be the same
>+		// This way we hopefully get sure, that contract of Comparator#compareTo
>+		// is fulfilled.
>+		for (int x = 0; x < 1000; x++) {
>+			ArrayList<MirrorInfo> templist = new ArrayList<MirrorInfo>(originals);
>+			Collections.shuffle(templist);
>+			MirrorInfo[] mirrors = templist.toArray(new MirrorInfo[originals.size()]);
>+			Arrays.sort(mirrors, comparator);
>+			assertList(originals, mirrors);
>+			/*
>+			 * ================================================================
>+			 * 
>+			 * Because of 
>+			 * Bug 317785 - Synchronization problem in mirror selection
>+			 * 
>+			 * We need an implementation of TimSort for this test.
>+			 * But because of incompatibility of EPL and GPL, the TimSort
>+			 * algorithm was removed.
>+			 * Instead, this test relies on the fact, that a proper implementation
>+			 * of Comparator will always compute the same result.
>+			 * When this test case runs within a JVM7, it will automatically
>+			 * use the new TimSort algorithm.
>+			 * ================================================================
>+			 */
>+		}
>+
> 	}
> 
>-	private void assertOrder(String message, MirrorInfo[] sorted, MirrorInfo one, MirrorInfo two, MirrorInfo three, MirrorInfo four) {
>-		assertTrue(message + ".1", sorted[0] == one);
>-		assertTrue(message + ".1", sorted[1] == two);
>-		assertTrue(message + ".1", sorted[2] == three);
>-		assertTrue(message + ".1", sorted[3] == four);
>+	public void testComparatorZeros() {
>+
>+		MirrorSelector.MirrorInfoComparator comparator = new MirrorSelector.MirrorInfoComparator(0, 0, 0);
>+
>+		assertEquals("equals", comparator.compare(originals.get(0), originals.get(0)), 0);
>+		assertEquals("equals", comparator.compare(originals.get(1), originals.get(1)), 0);
>+
> 	}
>+
>+	/**
>+	 * @param originallist
>+	 * @param mirrors
>+	 */
>+	private void assertList(List<MirrorInfo> originallist, MirrorInfo[] mirrors) {
>+		assertEquals("length", originallist.size(), mirrors.length);
>+		for (int i = 0; i < originallist.size(); i++) {
>+			assertEquals("equal mirror_" + i, originallist.get(i), mirrors[i]);
>+		}
>+	}
>+
> }

Flags:

john.arthorne: iplog+
john.arthorne: review+

Actions: View | Diff

Attachments on bug 317785: 172622 | 198111 | 198147 | 198271 | 198308