Author: toad
Date: 2006-01-24 20:54:14 +0000 (Tue, 24 Jan 2006)
New Revision: 7909
Added:
branches/async-client/src/freenet/support/IntNumberedItem.java
branches/async-client/src/freenet/support/NumberedItemComparator.java
branches/async-client/src/freenet/support/RandomGrabArray.java
branches/async-client/src/freenet/support/RandomGrabArrayItem.java
branches/async-client/src/freenet/support/RandomGrabArrayWithInt.java
branches/async-client/src/freenet/support/SimpleIntNumberedItemComparator.java
branches/async-client/src/freenet/support/SortedVectorByNumber.java
Modified:
branches/async-client/src/freenet/client/async/ClientGet.java
branches/async-client/src/freenet/client/async/ClientPut.java
branches/async-client/src/freenet/client/async/ClientRequest.java
branches/async-client/src/freenet/client/async/ClientRequestScheduler.java
branches/async-client/src/freenet/client/async/SendableRequest.java
branches/async-client/src/freenet/client/async/SingleBlockInserter.java
branches/async-client/src/freenet/client/async/SingleFileFetcher.java
branches/async-client/src/freenet/node/RequestStarter.java
branches/async-client/src/freenet/support/NumberedRecentItems.java
Log:
Almost implemented ClientRequestScheduler.
Now need to wire it up to RequestStarter etc.
Modified: branches/async-client/src/freenet/client/async/ClientGet.java
===================================================================
--- branches/async-client/src/freenet/client/async/ClientGet.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/client/async/ClientGet.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -73,5 +73,9 @@
currentState.cancel();
}
}
+
+ public boolean isFinished() {
+ return finished || cancelled;
+ }
}
Modified: branches/async-client/src/freenet/client/async/ClientPut.java
===================================================================
--- branches/async-client/src/freenet/client/async/ClientPut.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/client/async/ClientPut.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -72,4 +72,8 @@
}
}
+ public boolean isFinished() {
+ return finished || cancelled;
+ }
+
}
Modified: branches/async-client/src/freenet/client/async/ClientRequest.java
===================================================================
--- branches/async-client/src/freenet/client/async/ClientRequest.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/client/async/ClientRequest.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -27,5 +27,5 @@
return cancelled;
}
-
+ public abstract boolean isFinished();
}
Modified:
branches/async-client/src/freenet/client/async/ClientRequestScheduler.java
===================================================================
--- branches/async-client/src/freenet/client/async/ClientRequestScheduler.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/client/async/ClientRequestScheduler.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -1,5 +1,10 @@
package freenet.client.async;
+import freenet.crypt.RandomSource;
+import freenet.node.RequestStarter;
+import freenet.support.RandomGrabArrayWithInt;
+import freenet.support.SortedVectorByNumber;
+
/**
* Every X seconds, the RequestSender calls the ClientRequestScheduler to
* ask for a request to start. A request is then started, in its own
@@ -7,29 +12,87 @@
*/
public class ClientRequestScheduler {
+ /**
+ * Structure:
+ * array (by priority) -> // one element per possible priority
+ * SortedVectorByNumber (by # retries) -> // contains each current
#retries
+ * RandomGrabArray // contains each element, allows fast
fetch-and-drop-a-random-element
+ *
+ * To speed up fetching, a RGA or SVBN must only exist if it is
non-empty.
+ */
+ final SortedVectorByNumber[] priorities;
+ // we have one for inserts and one for requests
+ final boolean isInsertScheduler;
+ final RandomSource random;
-
- public void register(SendableGet req) {
- // FIXME
+ ClientRequestScheduler(boolean forInserts, RandomSource random) {
+ this.random = random;
+ this.isInsertScheduler = forInserts;
+ priorities = new
SortedVectorByNumber[RequestStarter.NUMBER_OF_PRIORITY_CLASSES];
+ for(int i=0;i<priorities.length;i++)
+ priorities[i] = new SortedVectorByNumber();
}
- public void register(SendableInsert req) {
- // FIXME
+ public synchronized void register(SendableRequest req) {
+ if((!isInsertScheduler) && req instanceof ClientPut)
+ throw new IllegalArgumentException("Expected a
ClientPut: "+req);
+ RandomGrabArrayWithInt grabber =
+ makeGrabArray(req.getPriorityClass(),
req.getRetryCount());
+ grabber.add(req);
}
- public void remove(SendableRequest sr) {
- // FIXME
+ private synchronized RandomGrabArrayWithInt makeGrabArray(short
priorityClass, int retryCount) {
+ SortedVectorByNumber prio = priorities[priorityClass];
+ if(prio == null) {
+ prio = new SortedVectorByNumber();
+ priorities[priorityClass] = prio;
+ }
+ RandomGrabArrayWithInt grabber = (RandomGrabArrayWithInt)
prio.get(retryCount);
+ if(grabber == null) {
+ grabber = new RandomGrabArrayWithInt(retryCount);
+ prio.add(grabber);
+ }
+ return grabber;
}
-
- public void update(SendableRequest sr) {
- // FIXME
+
+ /**
+ * Should not be called often as can be slow if there are many requests
of the same
+ * priority and retry count. Priority and retry count must be the same
as they were
+ * when it was added.
+ */
+ public synchronized void remove(SendableRequest req) {
+ // Should not be called often.
+ int prio = req.getPriorityClass();
+ int retryCount = req.getRetryCount();
+ SortedVectorByNumber s = priorities[prio];
+ if(s == null) return;
+ if(s.isEmpty()) return;
+ RandomGrabArrayWithInt grabber =
+ (RandomGrabArrayWithInt) s.get(retryCount);
+ if(grabber == null) return;
+ grabber.remove(req);
+ if(grabber.isEmpty()) {
+ s.remove(retryCount);
+ if(s.isEmpty())
+ priorities[prio] = null;
+ }
}
- public void startRequest() {
- // FIXME
+ public synchronized ClientRequest getFirst() {
+ // Priorities start at 0
+ for(int i=0;i<RequestStarter.MINIMUM_PRIORITY_CLASS;i++) {
+ SortedVectorByNumber s = priorities[i];
+ if(s == null) continue;
+ RandomGrabArrayWithInt rga = (RandomGrabArrayWithInt)
s.getFirst(); // will discard finished items
+ ClientRequest req = (ClientRequest) rga.removeRandom();
+ if(rga.isEmpty()) {
+ s.remove(rga.getNumber());
+ if(s.isEmpty()) {
+ priorities[i] = null;
+ }
+ }
+ return req;
+ }
+ return null;
}
-
- public void startInsert() {
- // FIXME
- }
}
Modified: branches/async-client/src/freenet/client/async/SendableRequest.java
===================================================================
--- branches/async-client/src/freenet/client/async/SendableRequest.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/client/async/SendableRequest.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -1,10 +1,12 @@
package freenet.client.async;
+import freenet.support.RandomGrabArrayItem;
+
/**
* A low-level request which can be sent immediately. These are registered
* on the ClientRequestScheduler.
*/
-public interface SendableRequest {
+public interface SendableRequest extends RandomGrabArrayItem {
public short getPriorityClass();
Modified:
branches/async-client/src/freenet/client/async/SingleBlockInserter.java
===================================================================
--- branches/async-client/src/freenet/client/async/SingleBlockInserter.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/client/async/SingleBlockInserter.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -196,4 +196,8 @@
cb.onFailure(new
InserterException(InserterException.CANCELLED), this);
}
+ public boolean isFinished() {
+ return finished;
+ }
+
}
Modified: branches/async-client/src/freenet/client/async/SingleFileFetcher.java
===================================================================
--- branches/async-client/src/freenet/client/async/SingleFileFetcher.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/client/async/SingleFileFetcher.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -464,4 +464,8 @@
cancelled = true;
}
+ public boolean isFinished() {
+ return cancelled;
+ }
+
}
Modified: branches/async-client/src/freenet/node/RequestStarter.java
===================================================================
--- branches/async-client/src/freenet/node/RequestStarter.java 2006-01-24
00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/node/RequestStarter.java 2006-01-24
20:54:14 UTC (rev 7909)
@@ -33,6 +33,8 @@
/** Anything less important than prefetch (redundant??) */
public static final short MINIMUM_PRIORITY_CLASS = 6;
+ public static final short NUMBER_OF_PRIORITY_CLASSES =
MINIMUM_PRIORITY_CLASS - MAXIMUM_PRIORITY_CLASS;
+
// Clients registered
final Vector clientsByPriority;
final RequestThrottle throttle;
Added: branches/async-client/src/freenet/support/IntNumberedItem.java
===================================================================
--- branches/async-client/src/freenet/support/IntNumberedItem.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/support/IntNumberedItem.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -0,0 +1,11 @@
+package freenet.support;
+
+/**
+ * An object with a number (as an int).
+ * @see NumberedItem
+ */
+public interface IntNumberedItem {
+
+ int getNumber();
+
+}
Added: branches/async-client/src/freenet/support/NumberedItemComparator.java
===================================================================
--- branches/async-client/src/freenet/support/NumberedItemComparator.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/support/NumberedItemComparator.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -0,0 +1,59 @@
+package freenet.support;
+
+import java.util.Comparator;
+
+public class NumberedItemComparator implements Comparator {
+
+ public NumberedItemComparator(boolean wrap) {
+ this.wrapAround = wrap;
+ }
+
+ final boolean wrapAround;
+
+ public int compare(Object o1, Object o2) {
+ int x = ocompare(o1, o2);
+ Logger.minor(this, "compare("+o1+","+o2+") = "+x);
+ return x;
+ }
+
+ public int ocompare(Object o1, Object o2) {
+ // Nulls at the end of the list
+ if(o1 == null && o2 == null)
+ return 0; // null == null
+ if(o1 != null && o2 == null)
+ return 1; // anything > null
+ if(o2 != null && o1 == null)
+ return -1;
+ long i1, i2;
+ if(o1 instanceof NumberedItem)
+ i1 = ((NumberedItem)o1).getNumber();
+ else if(o1 instanceof Long)
+ i1 = ((Long)o1).longValue();
+ else throw new ClassCastException(o1.toString());
+ if(o2 instanceof NumberedItem)
+ i2 = ((NumberedItem)o2).getNumber();
+ else if(o2 instanceof Long)
+ i2 = ((Long)o2).longValue();
+ else throw new ClassCastException(o2.toString());
+ if(i1 == i2) return 0;
+ if(!wrapAround) {
+ if(i1 > i2) return 1;
+ else return -1;
+ } else {
+ long firstDistance, secondDistance;
+ if(i1 > i2) {
+ firstDistance = i1 - i2; // smaller => i1 > i2
+ secondDistance = i2 + Long.MAX_VALUE - i1; // smaller => i2 >
i1
+ } else {
+ secondDistance = i2 - i1; // smaller => i2 > i1
+ firstDistance = i1 + Long.MAX_VALUE - i2; // smaller => i1 > i2
+ }
+ if(Math.abs(firstDistance) < Math.abs(secondDistance)) {
+ return 1; // i1>i2
+ } else //if(Math.abs(secondDistance) < Math.abs(firstDistance)) {
+ return -1; // i2>i1
+ // REDFLAG: base must be odd, so we never get ==
+ }
+ }
+
+}
Modified: branches/async-client/src/freenet/support/NumberedRecentItems.java
===================================================================
--- branches/async-client/src/freenet/support/NumberedRecentItems.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/support/NumberedRecentItems.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -28,56 +28,7 @@
items = new NumberedItem[maxSize];
count = 0;
wrapAround = wrap;
- myComparator =
- new Comparator() {
-
- public int compare(Object o1, Object o2) {
- int x = ocompare(o1, o2);
- Logger.minor(this, "compare("+o1+","+o2+") = "+x);
- return x;
- }
-
- public int ocompare(Object o1, Object o2) {
- // Nulls at the end of the list
- if(o1 == null && o2 == null)
- return 0; // null == null
- if(o1 != null && o2 == null)
- return 1; // anything > null
- if(o2 != null && o1 == null)
- return -1;
- long i1, i2;
- if(o1 instanceof NumberedItem)
- i1 = ((NumberedItem)o1).getNumber();
- else if(o1 instanceof Long)
- i1 = ((Long)o1).longValue();
- else throw new ClassCastException(o1.toString());
- if(o2 instanceof NumberedItem)
- i2 = ((NumberedItem)o2).getNumber();
- else if(o2 instanceof Long)
- i2 = ((Long)o2).longValue();
- else throw new ClassCastException(o2.toString());
- if(i1 == i2) return 0;
- if(!wrapAround) {
- if(i1 > i2) return 1;
- else return -1;
- } else {
- long firstDistance, secondDistance;
- if(i1 > i2) {
- firstDistance = i1 - i2; // smaller => i1 > i2
- secondDistance = i2 + Long.MAX_VALUE - i1; // smaller
=> i2 > i1
- } else {
- secondDistance = i2 - i1; // smaller => i2 > i1
- firstDistance = i1 + Long.MAX_VALUE - i2; // smaller
=> i1 > i2
- }
- if(Math.abs(firstDistance) < Math.abs(secondDistance)) {
- return 1; // i1>i2
- } else //if(Math.abs(secondDistance) <
Math.abs(firstDistance)) {
- return -1; // i2>i1
- // REDFLAG: base must be odd, so we never get ==
- }
- }
-
- };
+ myComparator = new NumberedItemComparator(wrap);
}
public synchronized NumberedItem get(int num) {
Added: branches/async-client/src/freenet/support/RandomGrabArray.java
===================================================================
--- branches/async-client/src/freenet/support/RandomGrabArray.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/support/RandomGrabArray.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -0,0 +1,72 @@
+package freenet.support;
+
+import java.util.HashSet;
+
+import freenet.crypt.RandomSource;
+
+/**
+ * An array which supports very fast remove-and-return-a-random-element.
+ */
+public class RandomGrabArray {
+
+ /** Array of items. Non-null's followed by null's. */
+ private RandomGrabArrayItem[] reqs;
+ /** Index of first null item. */
+ private int index;
+ /** Random source */
+ private RandomSource rand;
+ /** What do we already have? FIXME: Replace with a Bloom filter or
something (to save
+ * RAM), or rewrite the whole class as a custom hashset maybe based on
the classpath
+ * HashSet. Note that removeRandom() is *the* common operation, so MUST
BE FAST.
+ */
+ private HashSet contents;
+ private final static int MIN_SIZE = 32;
+
+ public synchronized void add(RandomGrabArrayItem req) {
+ if(contents.contains(req)) return;
+ if(req.isFinished()) return;
+ contents.add(req);
+ if(index >= reqs.length) {
+ RandomGrabArray[] r = new
RandomGrabArray[reqs.length*2];
+ System.arraycopy(reqs, 0, r, 0, reqs.length);
+ }
+ reqs[index++] = req;
+ }
+
+ public synchronized RandomGrabArrayItem removeRandom() {
+ while(true) {
+ if(index == 0) return null;
+ int i = rand.nextInt(index);
+ RandomGrabArrayItem ret = reqs[i];
+ reqs[i] = reqs[--index];
+ reqs[index] = null;
+ if(ret != null)
+ contents.remove(ret);
+ // Shrink array
+ if(index < reqs.length / 4 && reqs.length > MIN_SIZE) {
+ // Shrink array
+ int newSize = Math.max(index * 2, MIN_SIZE);
+ RandomGrabArrayItem[] r = new
RandomGrabArrayItem[newSize];
+ System.arraycopy(reqs, 0, r, 0, r.length);
+ reqs = r;
+ }
+ if(ret != null && !ret.isFinished()) return ret;
+ }
+ }
+
+ public synchronized void remove(RandomGrabArrayItem it) {
+ if(!contents.contains(it)) return;
+ contents.remove(it);
+ for(int i=0;i<index;i++) {
+ if(reqs[i] == it || reqs[i].equals(it)) {
+ reqs[i] = reqs[--index];
+ reqs[index] = null;
+ return;
+ }
+ }
+ }
+
+ public boolean isEmpty() {
+ return index == 0;
+ }
+}
Added: branches/async-client/src/freenet/support/RandomGrabArrayItem.java
===================================================================
--- branches/async-client/src/freenet/support/RandomGrabArrayItem.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/support/RandomGrabArrayItem.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -0,0 +1,8 @@
+package freenet.support;
+
+public interface RandomGrabArrayItem {
+
+ /** If true, will be automatically removed from the RGA, and not
returned. */
+ public boolean isFinished();
+
+}
Added: branches/async-client/src/freenet/support/RandomGrabArrayWithInt.java
===================================================================
--- branches/async-client/src/freenet/support/RandomGrabArrayWithInt.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/support/RandomGrabArrayWithInt.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -0,0 +1,15 @@
+package freenet.support;
+
+public class RandomGrabArrayWithInt extends RandomGrabArray implements
IntNumberedItem {
+
+ private final int number;
+
+ public RandomGrabArrayWithInt(int no) {
+ number = no;
+ }
+
+ public int getNumber() {
+ return number;
+ }
+
+}
Added:
branches/async-client/src/freenet/support/SimpleIntNumberedItemComparator.java
===================================================================
---
branches/async-client/src/freenet/support/SimpleIntNumberedItemComparator.java
2006-01-24 00:05:09 UTC (rev 7908)
+++
branches/async-client/src/freenet/support/SimpleIntNumberedItemComparator.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -0,0 +1,38 @@
+package freenet.support;
+
+import java.util.Comparator;
+
+public class SimpleIntNumberedItemComparator implements Comparator {
+
+ public int compare(Object o1, Object o2) {
+ int x = ocompare(o1, o2);
+ Logger.minor(this, "compare("+o1+","+o2+") = "+x);
+ return x;
+ }
+
+ public int ocompare(Object o1, Object o2) {
+ // Nulls at the end of the list
+ if(o1 == null && o2 == null)
+ return 0; // null == null
+ if(o1 != null && o2 == null)
+ return 1; // anything > null
+ if(o2 != null && o1 == null)
+ return -1;
+ long i1, i2;
+ if(o1 instanceof IntNumberedItem)
+ i1 = ((IntNumberedItem)o1).getNumber();
+ else if(o1 instanceof Integer)
+ i1 = ((Integer)o1).intValue();
+ else throw new ClassCastException(o1.toString());
+ if(o2 instanceof IntNumberedItem)
+ i2 = ((IntNumberedItem)o2).getNumber();
+ else if(o2 instanceof Integer)
+ i2 = ((Integer)o2).intValue();
+ else throw new ClassCastException(o2.toString());
+ if(i1 == i2) return 0;
+ if(i1 > i2) return 1;
+ else return -1;
+ }
+
+
+}
Added: branches/async-client/src/freenet/support/SortedVectorByNumber.java
===================================================================
--- branches/async-client/src/freenet/support/SortedVectorByNumber.java
2006-01-24 00:05:09 UTC (rev 7908)
+++ branches/async-client/src/freenet/support/SortedVectorByNumber.java
2006-01-24 20:54:14 UTC (rev 7909)
@@ -0,0 +1,61 @@
+package freenet.support;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+/**
+ * Map of an integer to an element, based on a sorted Vector.
+ * Note that we have to shuffle data around, so this is slowish if it gets big.
+ */
+public class SortedVectorByNumber {
+
+ private IntNumberedItem[] data;
+ private int length;
+ private static final Comparator comparator = new
SimpleIntNumberedItemComparator();
+
+ public synchronized IntNumberedItem getFirst() {
+ if(length == 0) return null;
+ return data[0];
+ }
+
+ public boolean isEmpty() {
+ return length == 0;
+ }
+
+ public synchronized IntNumberedItem get(int retryCount) {
+ int x = Arrays.binarySearch(data, new Integer(retryCount),
comparator);
+ if(x >= 0)
+ return data[x];
+ return null;
+ }
+
+ public void remove(int item) {
+ int x = Arrays.binarySearch(data, new Integer(item),
comparator);
+ if(x >= 0) {
+ if(x < length-1)
+ System.arraycopy(data, x+1, data, x,
length-x-1);
+ data[length--] = null;
+ }
+ if(length < 4*data.length) {
+ IntNumberedItem[] newData = new
IntNumberedItem[length*2];
+ System.arraycopy(data, 0, newData, 0, length);
+ data = newData;
+ }
+ }
+
+ public void add(IntNumberedItem grabber) {
+ int x = Arrays.binarySearch(data, new
Integer(grabber.getNumber()), comparator);
+ if(x >= 0) throw new IllegalArgumentException(); // already
exists
+ // insertion point
+ x = -x-1;
+ // Move the data
+ if(length == data.length) {
+ IntNumberedItem[] newData = new
IntNumberedItem[length*2];
+ System.arraycopy(data, 0, newData, 0, data.length);
+ }
+ if(x < length)
+ System.arraycopy(data, x, data, x+1, length-x);
+ data[x] = grabber;
+ }
+
+}
