[freenet-cvs] r18678 - trunk/freenet/src/freenet/client/async

[t...@freenetproject.org]

Author: toad
Date: 2008-03-21 17:46:49 +0000 (Fri, 21 Mar 2008)
New Revision: 18678

Modified:
   trunk/freenet/src/freenet/client/async/OfferedKeysList.java
Log:
Avoid the shuffling penalty.

Modified: trunk/freenet/src/freenet/client/async/OfferedKeysList.java
===================================================================
--- trunk/freenet/src/freenet/client/async/OfferedKeysList.java 2008-03-21 
17:16:24 UTC (rev 18677)
+++ trunk/freenet/src/freenet/client/async/OfferedKeysList.java 2008-03-21 
17:46:49 UTC (rev 18678)
@@ -31,7 +31,6 @@
 public class OfferedKeysList extends SendableRequest {

        private final HashSet keys;
-       // FIXME is there any way to avoid the O(n) shuffling penalty here?
        private final Vector keysList;
        private static boolean logMINOR;
        private final RandomSource random;
@@ -73,7 +72,11 @@
        public Object chooseKey() {
                // Pick a random key
                if(keysList.isEmpty()) return null;
-               Key k = (Key) keysList.remove(random.nextInt(keysList.size()));
+               int ptr = random.nextInt(keysList.size());
+               // Avoid shuffling penalty by swapping the chosen element with 
the end.
+               Key k = (Key) keysList.get(ptr);
+               keysList.set(ptr, keysList.get(keysList.size()-1));
+               keysList.setSize(keysList.size()-1);
                keys.remove(k);
                return k;
        }