Update of /cvsroot/freenet/freenet/src/freenet/node/rt
In directory sc8-pr-cvs1:/tmp/cvs-serv14480/src/freenet/node/rt
Modified Files:
ResponseTimeEstimator.java
Log Message:
Initial version of the RoutingPointStore. ResponseTimeEstimator now handles the
routing calculations whilst RoutingPointStore manages the storage of the RoutingPoints.
Index: ResponseTimeEstimator.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/ResponseTimeEstimator.java,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -w -r1.23 -r1.24
--- ResponseTimeEstimator.java 1 Nov 2003 11:50:55 -0000 1.23
+++ ResponseTimeEstimator.java 1 Nov 2003 20:01:39 -0000 1.24
@@ -3,6 +3,7 @@
import java.io.DataOutputStream;
import java.io.IOException;
import java.io.OutputStream;
+import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.NumberFormat;
@@ -35,12 +36,13 @@
// }
public class ResponseTimeEstimator implements TimeEstimator {
- BigInteger key[];
- int time[];
- double sensitivity[];
+ //BigInteger key[];
+ //int time[];
+ //double sensitivity[];
protected static final double SENSITIVITY_MAX = 10.0;
protected RecentReports recent;
+ protected RoutingPointStore store;
static final int KEYBYTES = 23,
TIMEBYTES = 4,
@@ -54,68 +56,29 @@
boolean logDEBUG = true;
public int getDataLength() {
- return 4 + key.length * (4 + KEYBYTES);
+ return store.getDataLength();
}
public ResponseTimeEstimator(DataInputStream i) throws IOException {
int version = i.readInt();
if(version != 1) throw new IOException("unrecognized version "+i);
- int accuracy = i.readInt();
- if(accuracy < 0) throw new IOException("failed read");
- if(accuracy == 0 || accuracy > MAX_ACCURACY) // seems reasonable bounds
- throw new IOException("Invalid accuracy word "+accuracy);
- key = new BigInteger[accuracy];
- time = new int[accuracy];
- sensitivity = new double[accuracy];
- BigInteger prev = BigInteger.ZERO;
- for(int x = 0; x<accuracy;x++) {
- time[x] = i.readInt();
- if(time[x] < 0) throw new IOException("negative value");
- byte[] b = new byte[KEYBYTES];
- i.readFully(b);
- key[x] = new BigInteger(1, b);
- if(key[x].signum() == -1) throw new IOException("negative key");
- if(key[x].compareTo(keyspace) == 1)
- throw new IOException("exceeded keyspace");
- if(key[x].compareTo(prev) == -1)
- throw new IOException("smaller than prev");
- prev = key[x];
- sensitivity[x] = i.readDouble();
- }
+ store = new RoutingPointStore(i);
try {
recent = new RecentReports(i);
} catch (IOException e) {
Core.logger.log(this, "Failed reading estimator report history from
InputStream, using empty history",e, Logger.ERROR);
recent = new RecentReports();
- // Not fatal - probably upgrading
+ // Not fatal - possibly upgrading
}
logDEBUG = Core.logger.shouldLog(Logger.DEBUG,this);
}
- public void writeTo(DataOutputStream o) throws IOException {
- logDEBUG = Core.logger.shouldLog(Logger.DEBUG,this);
- if(logDEBUG) logDEBUG("Serializing to disk, accuracy "+time.length);
+ public synchronized void writeTo(DataOutputStream o) throws IOException {
o.writeInt(1); // current version. Using negative numbers for compatibility.
- o.writeInt(time.length);
- synchronized(this) {
- for(int i=0;i<time.length;i++) {
- o.writeInt(time[i]);
- byte[] b = key[i].toByteArray();
- if(b.length > KEYBYTES + 1)
- throw new IllegalStateException("Key too long in serializing:
"+b.length);
- if(b.length < KEYBYTES) {
- int skip = KEYBYTES - b.length;
- for(int x=0;x<skip;x++)
- o.writeByte(0);
- o.write(b);
- } else o.write(b, b.length - KEYBYTES, KEYBYTES);
- // in case of zero padding
- o.writeDouble(sensitivity[i]);
- }
+ store.writeTo(o);
recent.writeTo(o);
}
- }
private void logMINOR(String s) {
if(Core.logger.shouldLog(Logger.MINOR,this))
@@ -147,88 +110,24 @@
public ResponseTimeEstimator(int initTime, int accuracy) {
this(accuracy);
if(initTime < 0) throw new IllegalArgumentException("negative initTime");
- setAllTimes(initTime);
- }
-
- //Sets all times to the supplied value
- private void setAllTimes(int newtime) {
- for(int i=0;i<time.length;i++) {
- time[i] = newtime;
- }
+ store.setAllTimes(initTime);
}
public ResponseTimeEstimator(Key k, int high, int low, int accuracy) {
- key = new BigInteger[accuracy];
- time = new int[accuracy];
- sensitivity = new double[accuracy];
-
- if(high < 0 || low < 0) throw new IllegalArgumentException("negative high
"+high+
- " or low "+low);
- // Center on k
- // b = keyspace / accuracy
- // c = k % c
- // Then set keys as in monadic constructor, except adding k
- BigInteger a = keyspace.subtract(BigInteger.ONE);
- BigInteger b = a.divide(BigInteger.valueOf(accuracy));
- BigInteger ik = convert(k);
- BigInteger[] dr = ik.divideAndRemainder(b);
- BigInteger c = dr[1]; // remainder. positive!
- if(c.signum() < 0) throw new IllegalStateException("argh");
- int kOffset = dr[0].intValue();
- for(int i = 0; i < accuracy; i++) {
- key[i] = c;
- c.add(b);
- }
- // Now the times
- int val = high;
- int valStep = (high - low) / accuracy;
- for(int i = 0; i < accuracy; i++) {
- int offset = (kOffset + i) % accuracy;
- time[offset] = val;
- if(i <= accuracy / 2)
- val -= valStep;
- else
- val += valStep;
- }
+ store = new RoutingPointStore(k,high,low,accuracy);
recent = new RecentReports();
}
public ResponseTimeEstimator(int accuracy) {
- key = new BigInteger[accuracy];
- time = new int[accuracy];
- sensitivity = new double[accuracy];
+ store = new RoutingPointStore(accuracy);
// Let's evenly distribute the keys across the whole
// keyspace and leave the time values at zero.
- dristributeKeysEvenly();
+ store.distributeKeysEvenly();
+ store.setAllTimes(0);
recent = new RecentReports();
}
- //distributes the keys evenly all through the keyspace
- private void dristributeKeysEvenly() {
- BigInteger a = keyspace.subtract(BigInteger.ONE);
- BigInteger b = a.divide(BigInteger.valueOf(key.length));
- for (int i = key.length; --i >= 0; a = a.subtract(b))
- key[i] = a;
- }
-
- // Return offset of the biggest key that's still less than n.
- final int search(BigInteger n) {
- int mid, low = 0, high = key.length - 1;
-
- for (;;) {
- mid = (high + low) >> 1;
- int i = key[mid].compareTo(n);
- if (i <= 0 && key[mid + 1].compareTo(n) > 0)
- return mid;
- if (i > 0)
- high = mid;
- else
- low = mid + 1;
- if (low == high)
- return low;
- }
- }
// Interpret key as value between 0 and 2^183.
final BigInteger convert(Key k) {
@@ -246,87 +145,18 @@
return new BigInteger(1, b);
}
- protected final class MySorter implements Sortable {
- public final int compare(int index1, int index2) {
- return key[index1].compareTo(key[index2]);
- }
-
- public final void swap(int index1, int index2) {
- BigInteger bi = key[index1];
- key[index1] = key[index2];
- key[index2] = bi;
- }
-
- public final int size() {
- return key.length;
- }
- }
-
- final MySorter ms = new MySorter();
-
- protected void orderKeys() {
- if(logDEBUG)
- Core.logger.log(this, "Reordering keys", Logger.DEBUG);
- dumpLog();
- // We cannot simply find the lowest value and then shift,
- // Becuase we are not using anything like strict gravity
- // We move the first key 1/2 the distance closer, the second 1/4 its distance
- // closer, the third 1/8 its distance closer etc
- // They get reordered!
- QuickSorter.quickSort(ms);
- dumpLog();
- }
-
- class keyTimeSens{
- BigInteger key;
- int time;
- double sensitivity;
- keyTimeSens(BigInteger key, int time, double sensitivity){
- this.key = key;
- this.time = time;
- this.sensitivity = sensitivity;
- }
- }
- keyTimeSens get(int index){
- return new keyTimeSens(key[index],time[index],sensitivity[index]);
- }
- void set(int index,keyTimeSens value){
- key[index] = value.key;
- time[index] = value.time;
- sensitivity[index] = value.sensitivity;
- }
static final BigDecimal DEC_ONE = new BigDecimal(1.0);
static final BigInteger THREE = BigInteger.valueOf(3);
static final BigInteger FOUR = BigInteger.valueOf(4);
- //Reversively finds the position of the first key in the store, after the
position 'startAt', that is smaller than n
- //Returns -1 if no such key is present in the store
- protected int findFirstSmaller_reverse(BigInteger n, int startAt){
- while (key[startAt].compareTo(n) == 1) {
- startAt--;
- if (startAt < 0)
- return -1;
- }
- return startAt;
- }
- //Finds the position of the first key in the store, after the position 'startAt',
that is larger than n
- //Returns -1 if no such key is present in the store
- protected int findFirstLarger(BigInteger n, int startAt){
- while (key[startAt].compareTo(n) == -1) {
- startAt++;
- if (startAt >= key.length)
- return -1;
- }
- return startAt;
- }
protected synchronized int reportDecreasing(BigInteger lowerBound, BigInteger
upperBound, BigInteger center, int usec, int initialSteps, int lowerBoundPos, int
upperBoundPos) {
if (logDEBUG)
Core.logger.log(this, "reportDecreasing(" +
lowerBound.toString(16) + "," + upperBound.toString(16) + "," + center.toString(16) +
"," + initialSteps + "," + lowerBoundPos + "," + upperBoundPos + ")", new
Exception("debug"), Logger.DEBUG);
- dumpLog();
- upperBoundPos = Math.min(upperBoundPos,key.length - 1);
- lowerBoundPos = Math.min(lowerBoundPos,key.length - 1);
+ store.dumpLog();
+ upperBoundPos = Math.min(upperBoundPos,store.length() - 1);
+ lowerBoundPos = Math.min(lowerBoundPos,store.length() - 1);
lowerBoundPos = Math.max(lowerBoundPos,0);
upperBoundPos = Math.max(upperBoundPos,0);
if (usec < 0)
@@ -336,21 +166,21 @@
// inc shiftAmount each time we move a point
int shiftAmount = initialSteps;
- upperBoundPos = findFirstSmaller_reverse(upperBound,upperBoundPos);
+ upperBoundPos =
store.findFirstSmaller_reverse(upperBound,upperBoundPos);
if (upperBoundPos < 0) return initialSteps;
- lowerBoundPos = findFirstLarger(lowerBound,lowerBoundPos);
+ lowerBoundPos = store.findFirstLarger(lowerBound,lowerBoundPos);
if (lowerBoundPos < 0) return initialSteps;
if (lowerBoundPos > upperBoundPos)
return initialSteps;
for (int i = lowerBoundPos; i <= upperBoundPos; i++) {
- keyTimeSens k = get(i);
+ RoutingPointStore.RoutingPoint k = store.get(i);
if (k.time < 0)
Core.logger.log(this, "time[" + i + "] = " + k.time +
" - NEGATIVE TIME!", Logger.ERROR);
if (logDEBUG)
Core.logger.log(this, "Trying key[" + i + "]: " +
k.key.toString(16) + "," + k.time, Logger.DEBUG);
- ensureSensitivityBelowMax(i);
+ k.sensitivity = Math.min(k.sensitivity,SENSITIVITY_MAX);
//double sens = sensitivity[i];
BigInteger diff = handleKeyspaceWrap(k.key.subtract(center));
// Result = old position + ((old position * sensitivity) /
(sensitivity + 1)
@@ -374,7 +204,7 @@
int timediff = usec - k.time;
if (logDEBUG)
- Core.logger.log(this, "usec=" + usec + ", time[" + i +
"]=" + time[i] + ", timediff=" + timediff, Logger.DEBUG);
+ Core.logger.log(this, "usec=" + usec + ", time[" + i +
"]=" + k.time + ", timediff=" + timediff, Logger.DEBUG);
double fracTimediff = (double) timediff;
if (logDEBUG)
Core.logger.log(this, "fracTimediff=" + fracTimediff,
Logger.DEBUG);
@@ -386,17 +216,17 @@
Core.logger.log(this, "timediff now = " + timediff,
Logger.DEBUG);
timediff = (int) ((((long) timediff) * 3) / 4);
if (logDEBUG)
- Core.logger.log(this, "time[" + i + "] = " + time[i] +
", timediff = " + timediff, Logger.DEBUG);
+ Core.logger.log(this, "time[" + i + "] = " + k.time +
", timediff = " + timediff, Logger.DEBUG);
k.time += timediff;
if (logDEBUG)
- Core.logger.log(this, "key[" + i + "] now: " +
key[i].toString(16) + "," + time[i], Logger.DEBUG);
+ Core.logger.log(this, "key[" + i + "] now: " +
k.key.toString(16) + "," + k.time, Logger.DEBUG);
if (k.time < 0)
Core.logger.log(this, "time[" + i + "] = " + k.time +
" - NEGATIVE TIME!", Logger.ERROR);
k.sensitivity += 1.0 / (1 << shiftAmount);
- set(i,k);
+ store.set(i,k);
shiftAmount++;
}
- dumpLog();
+ store.dumpLog();
return shiftAmount;
}
@@ -425,9 +255,9 @@
upperBound.toString(16)+","+center.toString(16)+","+
initialSteps+","+lowerBoundPos+","+upperBoundPos+")",
new Exception("debug"), Logger.DEBUG);
- dumpLog();
- upperBoundPos = Math.min(upperBoundPos,key.length - 1);
- lowerBoundPos = Math.min(lowerBoundPos,key.length - 1);
+ store.dumpLog();
+ upperBoundPos = Math.min(upperBoundPos,store.length() - 1);
+ lowerBoundPos = Math.min(lowerBoundPos,store.length() - 1);
lowerBoundPos = Math.max(lowerBoundPos,0);
upperBoundPos = Math.max(upperBoundPos,0);
if(usec < 0) throw new IllegalArgumentException("usec "+usec+" negative!");
@@ -436,15 +266,15 @@
// inc shiftAmount each time we move a point
int shiftAmount = initialSteps;
- upperBoundPos = findFirstSmaller_reverse(upperBound,upperBoundPos);
+ upperBoundPos = store.findFirstSmaller_reverse(upperBound,upperBoundPos);
if (upperBoundPos < 0) return initialSteps;
- lowerBoundPos = findFirstLarger(lowerBound,lowerBoundPos);
+ lowerBoundPos = store.findFirstLarger(lowerBound,lowerBoundPos);
if (lowerBoundPos < 0)return initialSteps;
if(lowerBoundPos > upperBoundPos) return initialSteps;
for(int i=upperBoundPos;i>=lowerBoundPos;i--) {
- keyTimeSens k = get(i);
+ RoutingPointStore.RoutingPoint k = store.get(i);
if(logDEBUG)
Core.logger.log(this, "Trying key["+i+"]: "+
k.key.toString(16)+","+k.time,
@@ -452,7 +282,7 @@
if(k.time < 0)
Core.logger.log(this, "time["+i+"] = "+k.time+
" - NEGATIVE TIME!", Logger.ERROR);
- ensureSensitivityBelowMax(i);
+ k.sensitivity = Math.min(k.sensitivity,SENSITIVITY_MAX);
//double sens = sensitivity[i];
BigInteger diff = handleKeyspaceWrap(center.subtract(k.key));
BigDecimal fracDiff = new BigDecimal(diff);
@@ -477,16 +307,13 @@
if(k.time < 0)
Core.logger.log(this, "time["+i+"] = "+k.time+
" - NEGATIVE TIME!", Logger.ERROR);
- set(i,k);
+ store.set(i,k);
}
- dumpLog();
+ store.dumpLog();
return shiftAmount;
}
- //Ensures that the sensitivity at the given position is below the allowed
threshold
- private void ensureSensitivityBelowMax(int index) {
- if(sensitivity[index] > SENSITIVITY_MAX)
- sensitivity[index] = SENSITIVITY_MAX;
- }
+
+
public synchronized void report(Key k, int usec) {
logDEBUG = Core.logger.shouldLog(Logger.DEBUG,this);
@@ -496,13 +323,13 @@
if(n == null) throw new IllegalArgumentException("invalid key in report()");
recent.report(n,usec);
- int pos = search(n);
+ int pos = store.search(n);
if(logDEBUG)
Core.logger.log(this, "report("+n.toString(16)+","+usec+")",
Logger.DEBUG);
- dumpLog();
+ store.dumpLog();
int x = n.compareTo(halfkeyspace);
if(x == 1) {
if(logDEBUG)
@@ -512,11 +339,11 @@
// n ... keyspace, 0 ... n-halfkeyspace moved left
// n-halfkeyspace ... n moved right
BigInteger m = n.subtract(halfkeyspace);
- int mpos = search(m);
- int steps = reportDecreasing(n, keyspace, n, usec, 0, pos+1, key.length-1);
+ int mpos = store.search(m);
+ int steps = reportDecreasing(n, keyspace, n, usec, 0, pos+1,
store.length()-1);
reportDecreasing(BigInteger.ZERO, m, n, usec, steps, 0, mpos);
- reportIncreasing(m, n, n, usec, 0, mpos+1, key.length-1);
- orderKeys(); // if the edge wraps, over the next section, then we
orderKeys before the next section is done, we are stuffed
+ reportIncreasing(m, n, n, usec, 0, mpos+1, store.length()-1);
+ store.sortByKey(); // if the edge wraps, over the next section, then we
orderKeys before the next section is done, we are stuffed
} else if(x == -1) {
if(logDEBUG)
Core.logger.log(this, "Below half keyspace",
@@ -526,22 +353,22 @@
// 0 ... n moved right
// n+halfkeyspace .. keyspace moved right
BigInteger c = n.add(halfkeyspace);
- int cpos = search(c);
+ int cpos = store.search(c);
reportDecreasing(n, c, n, usec, 0, pos+1, cpos);
int steps = reportIncreasing(BigInteger.ZERO, n, n, usec, 0, 0, pos);
- reportIncreasing(c, keyspace, n, usec, steps, cpos+1, key.length-1);
- orderKeys();
+ reportIncreasing(c, keyspace, n, usec, steps, cpos+1, store.length()-1);
+ store.sortByKey();
} else {
if(logDEBUG)
Core.logger.log(this, "Dead on half keyspace",
Logger.DEBUG);
// We are in the exact center
- int mpos = search(halfkeyspace);
+ int mpos = store.search(halfkeyspace);
reportIncreasing(BigInteger.ZERO, halfkeyspace, halfkeyspace, usec,
0, 0, mpos);
reportDecreasing(halfkeyspace, keyspace, halfkeyspace, usec,
- 0, mpos+1, key.length-1);
- orderKeys();
+ 0, mpos+1, store.length()-1);
+ store.sortByKey();
}
if(logDEBUG)
Core.logger.log(this, "report("+n.toString(16)+","+usec+") completed",
@@ -556,28 +383,6 @@
// }
}
- public void dumpLog() {
- if (Core.logger.shouldLog(Logger.MINOR, this)) {
- StringBuffer sb = new StringBuffer();
- for (int x = 0; x < key.length; x++) {
- sb.append(key[x].toString(16));
- sb.append(": ");
- int t = time[x];
- sb.append(Integer.toString(t));
- if (t < 0)
- Core.logger.log(this, "time[" + x + "]=" + t +
" - NEGATIVE (" + this +")", Logger.ERROR);
- sb.append("\n");
- }
- Core.logger.log(this, "Dump of " + this +": \n" +
sb.toString(), Logger.MINOR);
- }else{
- //Do only the sanity check if we wont log the contents of the
estimator
- for (int x = 0; x < key.length; x++) {
- int t = time[x];
- if (t < 0)
- Core.logger.log(this, "time[" + x + "]=" + t +
" - NEGATIVE (" + this +")", Logger.ERROR);
- }
- }
- }
public double guessTime(Key k) {
return (double)guess(k); // resolution 1ms
@@ -663,47 +468,17 @@
}
public synchronized int guess(BigInteger n) {
- logDEBUG = Core.logger.shouldLog(Logger.DEBUG,this);
- int pos = search(n);
+ RoutingPointStore.NeighbourRoutingPointPair b =
store.findKeyBeforeAndAfter(n);
- // It's off the charts...
- //if (pos == 0 && n.compareTo(key[0]) < 0 || pos == key.length - 1)
- //return time[pos];
-
- int npos;
- BigInteger beforeKey, afterKey;
- int beforeTime, afterTime;
- int opos = pos;
- if ((pos == 0 && n.compareTo(key[0]) < 0) ||
- (pos == key.length - 1)) {
- // Off the end/beginning
- // Doesn't matter which
- pos = key.length -1;
- npos = 0;
- beforeTime = time[pos];
- afterTime = time[npos];
- BigInteger a = keyspace;
- beforeKey = key[key.length-1].
- subtract(a);
- // Yes, beforeKey should be negative
- if(opos == key.length -1)
- n = n.subtract(a);
- afterKey = key[0];
- } else {
- // In the middle
- //pos = pos;
- npos = pos + 1;
- beforeTime = time[pos];
- afterTime = time[npos];
- beforeKey = key[pos];
- afterKey = key[npos];
- }
+ if(b.includesKeyspaceWrap)
+ if(b.nPos == store.length() -1)
+ n = n.subtract(keyspace);
// Solve for the time given key and two bounding points.
- BigInteger i = BigInteger.valueOf(afterTime - beforeTime)
- .multiply(n.subtract(beforeKey))
- .divide(afterKey.subtract(beforeKey))
- .add(BigInteger.valueOf(beforeTime));
+ BigInteger i = BigInteger.valueOf(b.right.time - b.left.time)
+ .multiply(n.subtract(b.left.key))
+ .divide(b.right.key.subtract(b.left.key))
+ .add(BigInteger.valueOf(b.left.time));
//System.out.println("\n"+key[pos]+"="+time[pos]);
//System.out.println(n+"="+i.intValue());
@@ -738,11 +513,6 @@
}
*/
- public void print() {
- for (int i = 0; i < key.length; i++)
- System.out.println(i+":\t"+key[i]+"\t"+time[i]);
- }
-
public static TimeEstimatorFactory factory() {
return factory(DEFAULT_ACCURACY);
}
@@ -751,8 +521,7 @@
return new ResponseTimeEstimatorFactory(accuracy);
}
- public static class ResponseTimeEstimatorFactory
- implements TimeEstimatorFactory {
+ public static class ResponseTimeEstimatorFactory implements TimeEstimatorFactory {
int accuracy;
public ResponseTimeEstimatorFactory(int accuracy) {
this.accuracy = accuracy;
@@ -763,8 +532,7 @@
}
public TimeEstimator create(Key k, long high, long low) {
- return new ResponseTimeEstimator(k, convertTime(high),
- convertTime(low), accuracy);
+ return new ResponseTimeEstimator(k, convertTime(high),
convertTime(low), accuracy);
}
public TimeEstimator createZero() {
@@ -772,20 +540,19 @@
}
public TimeEstimator createInitTransfer(double initRate) {
- return new ResponseTimeEstimator(convertRate(initRate),
- accuracy);
+ return new ResponseTimeEstimator(convertRate(initRate),
accuracy);
}
}
public static void main(String[] args) {
Random r = new Random();
ResponseTimeEstimator rte = new ResponseTimeEstimator(1024);
- rte.print();
+ rte.store.print();
byte[] b = new byte[5];
r.nextBytes(b);
Key k = new Key(b);
rte.report(k, 64);
- rte.print();
+ rte.store.print();
/*
for (int i = 0; i < 1000; i++) {
rte.report(new Key(r), r.nextInt(Integer.MAX_VALUE));
@@ -810,19 +577,11 @@
}
public long highestRaw() {
- int highest = 0;
- for(int x=0;x<time.length;x++) {
- highest = Math.max(time[x],highest);
- }
- return highest;
+ return store.highestRaw();
}
public long lowestRaw() {
- int lowest = Integer.MAX_VALUE;
- for(int x=0;x<time.length;x++) {
- lowest = Math.min(time[x],lowest);
- }
- return lowest;
+ return store.lowestRaw();
}
//A class for keeping track of the recent reports that has come in to the
Estimator
protected static class RecentReports {
@@ -965,14 +724,8 @@
public void dumpHtml(java.io.PrintWriter pw) throws IOException {
pw.println("<table border=\"0\">");
- for(int x=0;x<key.length;x++) {
- pw.println("<tr><td>"+x+"</td><td>"+key[x].toString(16)+
- "</td><td>"+time[x]+"</td><td>"+sensitivity[x]+
- "</td></tr>");
- if(time[x] < 0)
- Core.logger.log(this, "time["+x+"]="+time[x]+
- " - NEGATIVE ("+this+")",
Logger.ERROR);
- }
+ store.dumpHtml(pw);
+
pw.println("<tr><td>Maximum</td><td colspan=\"2\">"+
keyspace.toString(16)+
"</td></tr>");
@@ -993,7 +746,7 @@
public String formatFromRaw(long x, int type) {
if(x < 0) {
- dumpLog();
+ store.dumpLog();
throw new IllegalArgumentException("negative!");
}
if(type == TIME) return Long.toString(x)+"ms";
@@ -1076,8 +829,312 @@
public String highestString(int type) {
return formatFromRaw(highestRaw(),type);
}
+ }
+ protected class RoutingPointStore {
+ BigInteger key[];
+ double sensitivity[];
+ int time[];
+ final RoutingPointStore.RoutingPointKeySorter ms = new
RoutingPointKeySorter();
+ //Represents a point in a routing graph
+ //Is the fundamental storage item of the RoutingStore
+ class RoutingPoint {
+ BigInteger key;
+ int time;
+ double sensitivity;
+ RoutingPoint(BigInteger key, int time, double sensitivity) {
+ this.key = key;
+ this.time = time;
+ this.sensitivity = sensitivity;
+ }
+ }
+ //A pair of two neighbouring RoutingPoints, including information on
wheter or not
+ //there is a keyspace wrap between them (right-key actually a larger
value than left-key)
+ class NeighbourRoutingPointPair {
+ RoutingPointStore.RoutingPoint left, right; //The key before
and the key after the supplied key
+ boolean includesKeyspaceWrap; //Wheter or not a keyspace wrap
is actually between the two RoutingPoints
+ int nPos; //TODO:Get rid of this one. The position of the key
that before and after is just that.
+ }
+
+ //Sorts the store in order of the RoutingPoint keys.
+ private final class RoutingPointKeySorter implements Sortable {
+ public final int compare(int index1, int index2) {
+ return key[index1].compareTo(key[index2]);
+ }
+
+ public final void swap(int index1, int index2) {
+ BigInteger bi = key[index1];
+ key[index1] = key[index2];
+ key[index2] = bi;
+ }
+
+ public final int size() {
+ return length();
+ }
+ }
+
+ //Create fresh, empty routing store with space for 'accuracy'
RoutingPoints
+ public RoutingPointStore(int accuracy) {
+ key = new BigInteger[accuracy];
+ time = new int[accuracy];
+ sensitivity = new double[accuracy];
+ }
+
+ //Create a store by reading a serialization
+ public RoutingPointStore(DataInputStream i) throws IOException {
+ int accuracy = i.readInt();
+ if (accuracy < 0)
+ throw new IOException("failed read");
+ if (accuracy == 0 || accuracy > MAX_ACCURACY) // seems
reasonable bounds
+ throw new IOException("Invalid accuracy word " +
accuracy);
+
+ key = new BigInteger[accuracy];
+ time = new int[accuracy];
+ sensitivity = new double[accuracy];
+
+ BigInteger prev = BigInteger.ZERO;
+
+ for (int x = 0; x < accuracy; x++) {
+ time[x] = i.readInt();
+ if (time[x] < 0)
+ throw new IOException("negative value");
+ byte[] b = new byte[KEYBYTES];
+ i.readFully(b);
+ key[x] = new BigInteger(1, b);
+ if (key[x].signum() == -1)
+ throw new IOException("negative key");
+ if (key[x].compareTo(keyspace) == 1)
+ throw new IOException("exceeded keyspace");
+ if (key[x].compareTo(prev) == -1)
+ throw new IOException("smaller than prev");
+ prev = key[x];
+ sensitivity[x] = i.readDouble();
+ }
+ }
+
+ public RoutingPointStore(Key k, int high, int low, int accuracy) {
+
+ if (high < 0 || low < 0)
+ throw new IllegalArgumentException("negative high " +
high + " or low " + low);
+ // Center on k
+ // b = keyspace / accuracy
+ // c = k % c
+ // Then set keys as in monadic constructor, except adding k
+ BigInteger a = keyspace.subtract(BigInteger.ONE);
+ BigInteger b = a.divide(BigInteger.valueOf(accuracy));
+ BigInteger ik = convert(k);
+ BigInteger[] dr = ik.divideAndRemainder(b);
+ BigInteger c = dr[1]; // remainder. positive!
+ if (c.signum() < 0)
+ throw new IllegalStateException("argh");
+ int kOffset = dr[0].intValue();
+ for (int i = 0; i < accuracy; i++) {
+ key[i] = c;
+ c.add(b);
+ }
+ // Now the times
+ int val = high;
+ int valStep = (high - low) / accuracy;
+ for (int i = 0; i < accuracy; i++) {
+ int offset = (kOffset + i) % accuracy;
+ time[offset] = val;
+ if (i <= accuracy / 2)
+ val -= valStep;
+ else
+ val += valStep;
+ }
+ }
+
+ //Returns the offset of the biggest key that's still less than n.
+ final int search(BigInteger n) {
+ int mid, low = 0, high = key.length - 1;
+
+ for (;;) {
+ mid = (high + low) >> 1;
+ int i = key[mid].compareTo(n);
+ if (i <= 0 && key[mid + 1].compareTo(n) > 0)
+ return mid;
+ if (i > 0)
+ high = mid;
+ else
+ low = mid + 1;
+ if (low == high)
+ return low;
+ }
+ }
+
+ //Sets all times to the supplied value
+ private void setAllTimes(int newtime) {
+ for (int i = 0; i < time.length; i++) {
+ time[i] = newtime;
+ }
+ }
+
+ //Returns the RoutingPoint at the position 'index' in the store
+ RoutingPoint get(int index) {
+ return new RoutingPoint(key[index], time[index],
sensitivity[index]);
}
+ void set(int index, RoutingPoint value) {
+ key[index] = value.key;
+ time[index] = value.time;
+ sensitivity[index] = value.sensitivity;
+ }
+ //Finds the position of the first key in the store, before the
position 'startAt', that is smaller than n
+ //Returns -1 if no such key is present in the store
+ protected int findFirstSmaller_reverse(BigInteger n, int startAt) {
+ while (key[startAt].compareTo(n) == 1) {
+ startAt--;
+ if (startAt < 0)
+ return -1;
+ }
+ return startAt;
+ }
+ //Finds the position of the first key in the store, after the position
'startAt', that is larger than n
+ //Returns -1 if no such key is present in the store
+ protected int findFirstLarger(BigInteger n, int startAt) {
+ while (key[startAt].compareTo(n) == -1) {
+ startAt++;
+ if (startAt >= key.length)
+ return -1;
+ }
+ return startAt;
+ }
+
+ int getDataLength() {
+ return 4 + key.length * (4 + KEYBYTES);
+ }
+
+ //Returns the number of items in the store
+ int length() {
+ return key.length;
+ }
+ public void dumpLog() {
+ if (Core.logger.shouldLog(Logger.MINOR, this)) {
+ StringBuffer sb = new StringBuffer();
+ for (int x = 0; x < key.length; x++) {
+ sb.append(key[x].toString(16));
+ sb.append(": ");
+ int t = time[x];
+ sb.append(Integer.toString(t));
+ if (t < 0)
+ Core.logger.log(this, "time[" + x +
"]=" + t + " - NEGATIVE (" + this +")", Logger.ERROR);
+ sb.append("\n");
+ }
+ Core.logger.log(this, "Dump of " + this +": \n" +
sb.toString(), Logger.MINOR);
+ } else {
+ //Do only the sanity check if we wont log the contents
of the estimator
+ for (int x = 0; x < key.length; x++) {
+ int t = time[x];
+ if (t < 0)
+ Core.logger.log(this, "time[" + x +
"]=" + t + " - NEGATIVE (" + this +")", Logger.ERROR);
+ }
+ }
+ }
+ void dumpHtml(PrintWriter pw) {
+ for (int x = 0; x < key.length; x++) {
+ pw.println("<tr><td>" + x + "</td><td>" +
key[x].toString(16) + "</td><td>" + time[x] + "</td><td>" + sensitivity[x] +
"</td></tr>");
+ if (time[x] < 0)
+ Core.logger.log(this, "time[" + x + "]=" +
time[x] + " - NEGATIVE (" + this +")", Logger.ERROR);
+ }
+ }
+ //Returns the value (time) of the highest-valued RoutingPoint
+ public long highestRaw() {
+ int highest = 0;
+ for (int x = 0; x < time.length; x++) {
+ highest = Math.max(highest,time[x]);
+ }
+ return highest;
+ }
+ //Returns the value (time) of the lowest-valued RoutingPoint
+ public long lowestRaw() {
+ int lowest = Integer.MAX_VALUE;
+ for (int x = 0; x < time.length; x++) {
+ lowest = Math.min(lowest,time[x]);
+ }
+ return lowest;
+ }
+ public void print() {
+ for (int i = 0; i < key.length; i++)
+ System.out.println(i + ":\t" + key[i] + "\t" +
time[i]);
+ }
+ //Sorts the RoutingStore in order of its RoutingPoint keys
+ protected void sortByKey() {
+ if (logDEBUG)
+ Core.logger.log(this, "Reordering keys", Logger.DEBUG);
+ dumpLog();
+ // We cannot simply find the lowest value and then shift,
+ // Becuase we are not using anything like strict gravity
+ // We move the first key 1/2 the distance closer, the second
1/4 its distance
+ // closer, the third 1/8 its distance closer etc
+ // They get reordered!
+ QuickSorter.quickSort(ms);
+ dumpLog();
+ }
+
+ //Serializes the store to the supplied DataOutputStream
+ public void writeTo(DataOutputStream o) throws IOException {
+ logDEBUG = Core.logger.shouldLog(Logger.DEBUG, this);
+ if (logDEBUG)
+ logDEBUG("Serializing store to disk, accuracy " +
time.length);
+ o.writeInt(time.length);
+ for (int i = 0; i < time.length; i++) {
+ o.writeInt(time[i]);
+ byte[] b = key[i].toByteArray();
+ if (b.length > KEYBYTES + 1)
+ throw new IllegalStateException("Key too long
in serializing: " + b.length);
+ if (b.length < KEYBYTES) {
+ int skip = KEYBYTES - b.length;
+ for (int x = 0; x < skip; x++)
+ o.writeByte(0);
+ o.write(b);
+ } else
+ o.write(b, b.length - KEYBYTES, KEYBYTES);
+ // in case of zero padding
+ o.writeDouble(sensitivity[i]);
+ }
+ }
+
+ //Returns the RoutingPoint which has the highest key
+ private RoutingPoint lastPoint() {
+ return get(key.length - 1);
+ }
+ //Returns the RoutingPoint which has the lowest key
+ private RoutingPoint firstPoint() {
+ return get(0);
+ }
+ //distributes the keys evenly throughout all of the keyspace
+ private void distributeKeysEvenly() {
+ BigInteger a = keyspace.subtract(BigInteger.ONE);
+ BigInteger b = a.divide(BigInteger.valueOf(key.length));
+ for (int i = key.length; --i >= 0; a = a.subtract(b))
+ key[i] = a;
+ }
+
+ //Locates the RoutingPoints who are keywise located right before and
right after the supplied BigInteger
+ //Handles keyspace wrap situations. The returned class contains
information wheter or not a wrap occurred
+ NeighbourRoutingPointPair findKeyBeforeAndAfter(BigInteger n) {
+ NeighbourRoutingPointPair retval = new
NeighbourRoutingPointPair();
+ int pos = store.search(n);
+
+ retval.nPos = pos;
+ //Is it off the keyspace, either to the left or to the right...
+ if ((pos == 0 && n.compareTo(store.firstPoint()) < 0) || (pos
== store.length() - 1)) {
+ // Off the end/beginning
+ // Doesn't matter which
+ retval.includesKeyspaceWrap = true;
+ pos = store.length() - 1;
+ // Yes, beforeKey should
be negative
+ retval.left = new
RoutingPoint(store.lastPoint().key.subtract(keyspace), time[pos], sensitivity[pos]);
+ retval.right = get(0);
+ } else {//else in the middle
+
+ retval.includesKeyspaceWrap = false;
+ retval.left = get(pos);
+ retval.right = get(pos+1);
+ }
+ return retval;
+ }
+ }
}
_______________________________________________
cvs mailing list
[EMAIL PROTECTED]
http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/cvs
