Update of /cvsroot/freenet/freenet/src/freenet/node/rt
In directory sc8-pr-cvs1:/tmp/cvs-serv9927/src/freenet/node/rt
Modified Files:
ResponseTimeEstimator.java FFTTimeEstimator.java
Added Files:
RoutingPointStore.java
Log Message:
Moved RoutingPointStore into a separate class in order to support better access
control (using private/public methods etc).
Fix m0davis graph NPE.
--- NEW FILE: RoutingPointStore.java ---
package freenet.node.rt;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import freenet.support.sort.QuickSorter;
import freenet.support.sort.Sortable;
import freenet.Core;
import freenet.support.Logger;
import freenet.Key;
class RoutingPointStore {
RoutingPoint points[];
final RoutingPointStore.RoutingPointKeySorter ms = new RoutingPointKeySorter();
boolean logDEBUG = true;
final BigInteger keyspace;
static final int MAX_ACCURACY = 32;
//Represents a point in a routing graph
//Is the fundamental storage item of the RoutingStore
class RoutingPoint {
//Underlying values write accessible only to this class
//If anyone wants to modify RoutingPoints they need to use
//a RoutingPointEditor instance
private BigInteger key;
private int time;
private double sensitivity;
RoutingPoint() {
key = null;
time = 0;
sensitivity = 0;
}
RoutingPoint(BigInteger key, int time, double sensitivity) {
this.key = key;
this.time = time;
this.sensitivity = sensitivity;
}
//Expose underlying values for reading only to others
public BigInteger getKey() {
return key;
}
public double getSensitivity() {
return sensitivity;
}
public int getTime() {
return time;
}
}
class RoutingPointEditor {
private RoutingPoint p;
private BigInteger key;
private int time;
private double sensitivity;
private boolean keyDirty,timeDirty,sensitivityDirty;
RoutingPointEditor(RoutingPoint p) {
this.p = p;
keyDirty = timeDirty = sensitivityDirty = false;
}
void commit(){
synchronized(RoutingPointStore.this){
p.key = key;
p.time = time;
p.sensitivity = sensitivity;
}
keyDirty = timeDirty = sensitivityDirty = false;
}
public BigInteger getKey() {
if(keyDirty)
return key;
else
return p.key;
}
public void setKey(BigInteger key) {
this.key = key;
keyDirty = true;
}
public double getSensitivity() {
if(sensitivityDirty)
return sensitivity;
else
return p.sensitivity;
}
public void setSensitivity(double sensitivity) {
this.sensitivity = sensitivity;
sensitivityDirty = true;
}
public int getTime() {
if(timeDirty)
return time;
else
return p.time;
}
public void setTime(int time) {
this.time = time;
timeDirty = true;
}
}
//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 points[index1].key.compareTo(points[index2].key);
}
public final void swap(int index1, int index2) {
RoutingPoint p = points[index1];
points[index1] = points[index2];
points[index2] = p;
}
public final int size() {
return length();
}
}
//Create fresh routing store with 'accuracy' number of default-valued
RoutingPoints
public RoutingPointStore(int accuracy,int initTime,BigInteger keyspace) {
this.keyspace = keyspace;
points = new RoutingPoint[accuracy];
for (int x = 0; x < points.length; x++) {
points[x] = new RoutingPoint();
}
setAllTimes(initTime);
logDEBUG = Core.logger.shouldLog(Logger.DEBUG,this);
}
//Create a store by reading a serialization
public RoutingPointStore(DataInputStream i,BigInteger keyspace) throws
IOException {
this.keyspace = keyspace;
logDEBUG = Core.logger.shouldLog(Logger.DEBUG,this);
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);
points = new RoutingPoint[accuracy];
BigInteger prev = BigInteger.ZERO;
for (int x = 0; x < points.length; x++) {
int time = i.readInt();
//time[x] = i.readInt();
if (time < 0)
throw new IOException("negative value");
byte[] b = new byte[Key.KEYBYTES];
i.readFully(b);
BigInteger key = new BigInteger(1, b);
if (key.signum() == -1)
throw new IOException("negative key");
if (key.compareTo(keyspace) == 1)
throw new IOException("exceeded keyspace");
if (key.compareTo(prev) == -1)
throw new IOException("smaller than prev");
prev = key;
double sensitivity = i.readDouble();
points[x] = new RoutingPoint(key,time,sensitivity);
}
}
//TODO: Documentation
public RoutingPointStore(Key k, int high, int low, int accuracy,BigInteger
keyspace) {
this(accuracy,-1,keyspace);
// We will overwrite the initTime:s in as second so they doesn't really
matter.
//Make sure that we detect any assignment problems but setting
initTime to -1
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 = k.toBigInteger();
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++) {
points[i].key = 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;
points[offset].time = val;
if (i <= accuracy / 2)
val -= valStep;
else
val += valStep;
}
//TODO: What about the sensitivities?
}
//Returns the offset of the biggest key that's still less than n.
final synchronized int search(BigInteger n) {
int mid, low = 0, high = points.length - 1;
for (;;) {
mid = (high + low) >> 1;
int i = points[mid].key.compareTo(n);
if (i <= 0 && points[mid+1].key.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 synchronized void setAllTimes(int newtime) {
for (int i = 0; i < points.length; i++) {
points[i].time = newtime;
}
}
//Returns a RoutingPointEditor for the Point at the position 'index' in the
store
//The RoutingPointEditor can be used to modify the routingPoint
synchronized RoutingPointEditor checkout(int index) {
return new RoutingPointEditor(points[index]);
}
//Returns the RoutingPoint at the position 'index' in the store
//The RoutingPointreturned might *not* be modified
synchronized RoutingPoint get(int index) {
return points[index];
}
//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 synchronized int findFirstSmaller_reverse(BigInteger n, int startAt)
{
while (points[startAt].key.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 synchronized int findFirstLarger(BigInteger n, int startAt) {
while (points[startAt].key.compareTo(n) == -1) {
startAt++;
if (startAt >= points.length)
return -1;
}
return startAt;
}
int getDataLength() {
//TODO: What about the times and sensitivities. Shouldn't they be
included in the size?
return 4 + points.length * (4 + Key.KEYBYTES);
}
//Returns the number of items in the store
int length() {
return points.length;
}
public synchronized void dumpLog() {
if (Core.logger.shouldLog(Logger.MINOR, this)) {
StringBuffer sb = new StringBuffer();
for (int x = 0; x < points.length; x++) {
sb.append(points[x].key.toString(16));
sb.append(": ");
int t = points[x].time;
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 < points.length; x++) {
int t = points[x].time;
if (t < 0)
Core.logger.log(this, "time[" + x + "]=" + t +
" - NEGATIVE (" + this +")", Logger.ERROR);
}
}
}
synchronized void dumpHtml(PrintWriter pw) {
for (int x = 0; x < points.length; x++) {
pw.println("<tr><td>" + x + "</td><td>" +
points[x].key.toString(16) + "</td><td>" + points[x].time + "</td><td>" +
points[x].sensitivity + "</td></tr>");
if (points[x].time < 0)
Core.logger.log(this, "time[" + x + "]=" +
points[x].time + " - NEGATIVE (" + this +")", Logger.ERROR);
}
}
//Returns the value (time) of the highest-valued RoutingPoint
public synchronized long highestRaw() {
int highest = 0;
for (int x = 0; x < points.length; x++) {
highest = Math.max(highest,points[x].time);
}
return highest;
}
//Returns the value (time) of the lowest-valued RoutingPoint
public synchronized long lowestRaw() {
int lowest = Integer.MAX_VALUE;
for (int x = 0; x < points.length; x++) {
lowest = Math.min(lowest,points[x].time);
}
return lowest;
}
public synchronized void print() {
for (int i = 0; i < points.length; i++)
System.out.println(i + ":\t" + points[i].key + "\t" +
points[i].time);
}
//Sorts the RoutingStore in order of its RoutingPoint keys
protected synchronized 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 synchronized void writeTo(DataOutputStream o) throws IOException {
logDEBUG = Core.logger.shouldLog(Logger.DEBUG, this);
if (logDEBUG)
Core.logger.log(this,"Serializing store to disk, accuracy " +
points.length, Logger.DEBUG);
o.writeInt(points.length);
for (int i = 0; i < points.length; i++) {
o.writeInt(points[i].time);
byte[] b = points[i].key.toByteArray();
if (b.length > Key.KEYBYTES + 1)
throw new IllegalStateException("Key too long in
serializing: " + b.length);
if (b.length < Key.KEYBYTES) {
int skip = Key.KEYBYTES - b.length;
for (int x = 0; x < skip; x++)
o.writeByte(0);
o.write(b);
} else
o.write(b, b.length - Key.KEYBYTES, Key.KEYBYTES);
// in case of zero padding
o.writeDouble(points[i].sensitivity);
}
}
//Returns the RoutingPoint which has the highest key
private RoutingPoint lastPoint() {
return get(points.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
synchronized void distributeKeysEvenly() {
BigInteger a = keyspace.subtract(BigInteger.ONE);
BigInteger b = a.divide(BigInteger.valueOf(points.length));
for (int i = points.length; --i >= 0; a = a.subtract(b))
points[i].key = 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
//The RoutingPoints returned might *not* be edited!
synchronized NeighbourRoutingPointPair findKeyBeforeAndAfter(BigInteger n) {
NeighbourRoutingPointPair retval = new NeighbourRoutingPointPair();
int pos = search(n);
retval.nPos = pos;
//Is it off the keyspace, either to the left or to the right...
if ((pos == 0 && n.compareTo(firstPoint().key) < 0) || (pos ==
length() - 1)) {
// Off the end/beginning
// Doesn't matter which
retval.includesKeyspaceWrap = true;
pos = length() - 1;
//Yes, beforeKey should be negative
retval.left = new
RoutingPoint(lastPoint().key.subtract(keyspace), points[pos].time,
points[pos].sensitivity);
retval.right = get(0);
} else {//else in the middle
retval.includesKeyspaceWrap = false;
retval.left = get(pos);
retval.right = get(pos+1);
}
return retval;
}
}/*
* Created on Nov 2, 2003
*
*/
Index: ResponseTimeEstimator.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/ResponseTimeEstimator.java,v
retrieving revision 1.28
retrieving revision 1.29
diff -u -w -r1.28 -r1.29
--- ResponseTimeEstimator.java 1 Nov 2003 22:54:02 -0000 1.28
+++ ResponseTimeEstimator.java 3 Nov 2003 08:04:53 -0000 1.29
@@ -3,7 +3,6 @@
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;
@@ -17,8 +16,7 @@
import freenet.support.graph.BitmapEncoder;
import freenet.support.graph.Color;
import freenet.support.graph.DibEncoder;
-import freenet.support.sort.QuickSorter;
-import freenet.support.sort.Sortable;
+
// class Key {
// byte[] b;
@@ -44,15 +42,13 @@
protected RecentReports recent;
protected RoutingPointStore store;
- static final int KEYBYTES = 23,
- TIMEBYTES = 4,
- BYTES = KEYBYTES + TIMEBYTES;
+ static final int TIMEBYTES = 4,
+ BYTES = Key.KEYBYTES + TIMEBYTES;
static final int DEFAULT_ACCURACY = 16;
- static final int MAX_ACCURACY = 32;
- static final BigInteger keyspace = BigInteger.ONE.shiftLeft(KEYBYTES << 3);
+ static final BigInteger keyspace = BigInteger.ONE.shiftLeft(Key.KEYBYTES << 3);
static final BigInteger halfkeyspace =
- BigInteger.ONE.shiftLeft((KEYBYTES << 3) - 1);
+ BigInteger.ONE.shiftLeft((Key.KEYBYTES << 3) - 1);
boolean logDEBUG = true;
public int getDataLength() {
@@ -62,7 +58,7 @@
public ResponseTimeEstimator(DataInputStream i) throws IOException {
int version = i.readInt();
if(version != 1) throw new IOException("unrecognized version "+i);
- store = new RoutingPointStore(i);
+ store = new RoutingPointStore(i,keyspace);
try {
recent = new RecentReports(i);
} catch (IOException e) {
@@ -108,41 +104,21 @@
}
public ResponseTimeEstimator(int initTime, int accuracy) {
- this(accuracy);
+ store = new RoutingPointStore(accuracy,initTime,keyspace);
if(initTime < 0) throw new IllegalArgumentException("negative initTime");
- store.setAllTimes(initTime);
+ recent = new RecentReports();
}
public ResponseTimeEstimator(Key k, int high, int low, int accuracy) {
- store = new RoutingPointStore(k,high,low,accuracy);
+ store = new RoutingPointStore(k,high,low,accuracy,keyspace);
recent = new RecentReports();
}
public ResponseTimeEstimator(int accuracy) {
- store = new RoutingPointStore(accuracy);
-
+ this(0,accuracy);
// Let's evenly distribute the keys across the whole
// keyspace and leave the time values at zero.
store.distributeKeysEvenly();
- store.setAllTimes(0);
- recent = new RecentReports();
- }
-
-
- // Interpret key as value between 0 and 2^183.
- final BigInteger convert(Key k) {
- byte[] b = k.getVal();
- if (b.length < KEYBYTES) {
- byte[] ob = new byte[KEYBYTES];
- System.arraycopy(b, 0, ob, 0, b.length);
- b = ob;
- }
- if (b.length > KEYBYTES) {
- Core.logger.log(this, "Very long key detected!: " + k, new
Exception("debug"), Logger.NORMAL);
- byte[] ob = new byte[KEYBYTES];
- System.arraycopy(b, 0, ob, 0, KEYBYTES);
- }
- return new BigInteger(1, b);
}
@@ -175,14 +151,14 @@
if (lowerBoundPos > upperBoundPos)
return initialSteps;
for (int i = lowerBoundPos; i <= upperBoundPos; i++) {
- RoutingPointStore.RoutingPoint k = store.get(i);
- if (k.time < 0)
- Core.logger.log(this, "time[" + i + "] = " + k.time +
" - NEGATIVE TIME!", Logger.ERROR);
+ RoutingPointStore.RoutingPointEditor k = store.checkout(i);
+ if (k.getTime() < 0)
+ Core.logger.log(this, "time[" + i + "] = " +
k.getTime() + " - NEGATIVE TIME!", Logger.ERROR);
if (logDEBUG)
- Core.logger.log(this, "Trying key[" + i + "]: " +
k.key.toString(16) + "," + k.time, Logger.DEBUG);
- k.sensitivity = Math.min(k.sensitivity,SENSITIVITY_MAX);
+ Core.logger.log(this, "Trying key[" + i + "]: " +
k.getKey().toString(16) + "," + k.getTime(), Logger.DEBUG);
+ k.setSensitivity(Math.min(k.getSensitivity(),SENSITIVITY_MAX));
//double sens = sensitivity[i];
- BigInteger diff = handleKeyspaceWrap(k.key.subtract(center));
+ BigInteger diff =
handleKeyspaceWrap(k.getKey().subtract(center));
// Result = old position + ((old position * sensitivity) /
(sensitivity + 1)
// >> shiftAmount
@@ -195,20 +171,20 @@
*/
// Multiply by 75% to prevent points from collapsing on each
other
BigDecimal fracDiff = new BigDecimal(diff);
- BigDecimal fracSens = new BigDecimal(k.sensitivity);
+ BigDecimal fracSens = new BigDecimal(k.getSensitivity());
BigDecimal fracOrig = new BigDecimal(center);
BigDecimal resultDiff = fracDiff.divide(fracSens.add(DEC_ONE),
BigDecimal.ROUND_DOWN);
diff = resultDiff.toBigInteger().shiftRight(shiftAmount);
diff = diff.multiply(THREE).divide(FOUR);
- k.key = handleKeyspaceWrap(k.key.subtract(diff));
+ k.setKey(handleKeyspaceWrap(k.getKey().subtract(diff)));
- int timediff = usec - k.time;
+ int timediff = usec - k.getTime();
if (logDEBUG)
- Core.logger.log(this, "usec=" + usec + ", time[" + i +
"]=" + k.time + ", timediff=" + timediff, Logger.DEBUG);
+ Core.logger.log(this, "usec=" + usec + ", time[" + i +
"]=" + k.getTime() + ", timediff=" + timediff, Logger.DEBUG);
double fracTimediff = (double) timediff;
if (logDEBUG)
Core.logger.log(this, "fracTimediff=" + fracTimediff,
Logger.DEBUG);
- double resultTimediff = fracTimediff / (k.sensitivity + 1.0);
+ double resultTimediff = fracTimediff / (k.getSensitivity() +
1.0);
if (logDEBUG)
Core.logger.log(this, "resultTimediff=" +
resultTimediff, Logger.DEBUG);
timediff = ((int) resultTimediff) >> shiftAmount;
@@ -216,14 +192,14 @@
Core.logger.log(this, "timediff now = " + timediff,
Logger.DEBUG);
timediff = (int) ((((long) timediff) * 3) / 4);
if (logDEBUG)
- Core.logger.log(this, "time[" + i + "] = " + k.time +
", timediff = " + timediff, Logger.DEBUG);
- k.time += timediff;
+ Core.logger.log(this, "time[" + i + "] = " +
k.getTime() + ", timediff = " + timediff, Logger.DEBUG);
+ k.setTime(k.getTime()+ timediff);
if (logDEBUG)
- 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);
- store.set(i,k);
+ Core.logger.log(this, "key[" + i + "] now: " +
k.getKey().toString(16) + "," + k.getTime(), Logger.DEBUG);
+ if (k.getTime() < 0)
+ Core.logger.log(this, "time[" + i + "] = " +
k.getTime() + " - NEGATIVE TIME!", Logger.ERROR);
+ k.setSensitivity(k.getSensitivity()+ 1.0 / (1 << shiftAmount));
+ k.commit();
shiftAmount++;
}
store.dumpLog();
@@ -274,40 +250,40 @@
if(lowerBoundPos > upperBoundPos) return initialSteps;
for(int i=upperBoundPos;i>=lowerBoundPos;i--) {
- RoutingPointStore.RoutingPoint k = store.get(i);
+ RoutingPointStore.RoutingPointEditor k = store.checkout(i);
if(logDEBUG)
Core.logger.log(this, "Trying key["+i+"]: "+
- k.key.toString(16)+","+k.time,
+ k.getKey().toString(16)+","+k.getTime(),
Logger.DEBUG);
- if(k.time < 0)
- Core.logger.log(this, "time["+i+"] = "+k.time+
+ if(k.getTime() < 0)
+ Core.logger.log(this, "time["+i+"] = "+k.getTime()+
" - NEGATIVE TIME!", Logger.ERROR);
- k.sensitivity = Math.min(k.sensitivity,SENSITIVITY_MAX);
+ k.setSensitivity(Math.min(k.getSensitivity(),SENSITIVITY_MAX));
//double sens = sensitivity[i];
- BigInteger diff = handleKeyspaceWrap(center.subtract(k.key));
+ BigInteger diff = handleKeyspaceWrap(center.subtract(k.getKey()));
BigDecimal fracDiff = new BigDecimal(diff);
- BigDecimal fracSens = new BigDecimal(k.sensitivity);
+ BigDecimal fracSens = new BigDecimal(k.getSensitivity());
BigDecimal fracOrig = new BigDecimal(center);
BigDecimal resultDiff = fracDiff.divide(fracSens.add(DEC_ONE),
BigDecimal.ROUND_DOWN);
diff = resultDiff.toBigInteger().shiftRight(shiftAmount);
diff = diff.multiply(THREE).divide(FOUR);
- k.key = handleKeyspaceWrap(k.key.add(diff.shiftRight(shiftAmount)));
- int timediff = usec - k.time;
+ k.setKey(handleKeyspaceWrap(k.getKey().add(diff.shiftRight(shiftAmount))));
+ int timediff = usec - k.getTime();
double fracTimediff = (double)timediff;
- double resultTimediff = fracTimediff/(k.sensitivity+1.0);
+ double resultTimediff = fracTimediff/(k.getSensitivity()+1.0);
timediff = ((int)resultTimediff) >> shiftAmount;
timediff = (int)((((long)timediff)*3)/4);
- k.time += timediff;
+ k.setTime( k.getTime()+ timediff);
if(logDEBUG)
- Core.logger.log(this, "key["+i+"] now: "+k.key.toString(16)+
- ","+k.time, Logger.DEBUG);
- k.sensitivity += 1.0/(1<<shiftAmount);
+ Core.logger.log(this, "key["+i+"] now: "+k.getKey().toString(16)+
+ ","+k.getTime(), Logger.DEBUG);
+ k.setSensitivity(k.getSensitivity() + 1.0/(1<<shiftAmount));
shiftAmount++;
- if(k.time < 0)
- Core.logger.log(this, "time["+i+"] = "+k.time+
+ if(k.getTime() < 0)
+ Core.logger.log(this, "time["+i+"] = "+k.getTime()+
" - NEGATIVE TIME!", Logger.ERROR);
- store.set(i,k);
+ k.commit();
}
store.dumpLog();
return shiftAmount;
@@ -317,7 +293,7 @@
public synchronized void report(Key k, int usec) {
logDEBUG = Core.logger.shouldLog(Logger.DEBUG,this);
- BigInteger n = convert(k);
+ BigInteger n = k.toBigInteger();
if(usec < 0) throw new IllegalArgumentException("negative usec in report()");
if(n == null) throw new IllegalArgumentException("invalid key in report()");
@@ -464,7 +440,7 @@
}
public int guess(Key k) {
- return guess(convert(k));
+ return guess(k.toBigInteger());
}
public int guess(BigInteger n) {
@@ -475,10 +451,10 @@
n = n.subtract(keyspace);
// Solve for the time given key and two bounding points.
- 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));
+ BigInteger i = BigInteger.valueOf(b.right.getTime() - b.left.getTime())
+ .multiply(n.subtract(b.left.getKey()))
+ .divide(b.right.getKey().subtract(b.left.getKey()))
+ .add(BigInteger.valueOf(b.left.getTime()));
// 2^31 microseconds is 36 minutes.
return i.intValue();
@@ -582,7 +558,7 @@
recentTimes[x] = i.readInt();
if (recentTimes[x] < 0)
throw new IOException("negative
value");
- byte[] b = new byte[KEYBYTES];
+ byte[] b = new byte[Key.KEYBYTES];
i.readFully(b);
recentKeys[x] = new BigInteger(1, b);
if (recentKeys[x].signum() == -1)
@@ -628,21 +604,21 @@
o.writeInt(recentTimes[i]);
byte[] b;
if (recentKeys[i] == null) {
- b = new byte[KEYBYTES];
- for (int ii = 0; ii < KEYBYTES; ii++)
+ b = new byte[Key.KEYBYTES];
+ for (int ii = 0; ii < Key.KEYBYTES; ii++)
b[ii] = 0;
} else {
b = recentKeys[i].toByteArray();
- if (b.length > KEYBYTES + 1)
+ if (b.length > Key.KEYBYTES + 1)
throw new IllegalStateException("Key
too long in serializing: " + b.length);
}
- if (b.length < KEYBYTES) {
- int skip = KEYBYTES - b.length;
+ if (b.length < Key.KEYBYTES) {
+ int skip = Key.KEYBYTES - b.length;
for (int x = 0; x < skip; x++)
o.writeByte(0);
o.write(b);
} else
- o.write(b, b.length - KEYBYTES, KEYBYTES);
+ o.write(b, b.length - Key.KEYBYTES,
Key.KEYBYTES);
// in case of zero padding
}
}
@@ -669,7 +645,8 @@
* @see java.util.Enumeration#hasMoreElements()
*/
public boolean hasMoreElements() {
- return location < RECENT_LENGTH;
+ return (location < RECENT_LENGTH &&
+ recentKeys[location]!= null); //Stop
early if the history hasn't yet filled up
}
/* (non-Javadoc)
@@ -793,313 +770,4 @@
return formatFromRaw(highestRaw(),type);
}
}
-
- protected class RoutingPointStore {
- RoutingPoint points[];
- 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() {
- key = null;
- time = 0;
- sensitivity = 0;
- }
- 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
points[index1].key.compareTo(points[index2].key);
- }
-
- public final void swap(int index1, int index2) {
- RoutingPoint p = points[index1];
- points[index1] = points[index2];
- points[index2] = p;
- }
-
- public final int size() {
- return length();
- }
- }
-
- //Create fresh routing store with 'accuracy' number of default-valued
RoutingPoints
- public RoutingPointStore(int accuracy) {
- points = new RoutingPoint[accuracy];
- for (int x = 0; x < points.length; x++) {
- points[x] = new RoutingPoint();
- }
- }
-
- //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);
- points = new RoutingPoint[accuracy];
-
-
- BigInteger prev = BigInteger.ZERO;
-
- for (int x = 0; x < points.length; x++) {
- int time = i.readInt();
- //time[x] = i.readInt();
- if (time < 0)
- throw new IOException("negative value");
- byte[] b = new byte[KEYBYTES];
- i.readFully(b);
- BigInteger key = new BigInteger(1, b);
- if (key.signum() == -1)
- throw new IOException("negative key");
- if (key.compareTo(keyspace) == 1)
- throw new IOException("exceeded keyspace");
- if (key.compareTo(prev) == -1)
- throw new IOException("smaller than prev");
- prev = key;
- double sensitivity = i.readDouble();
- points[x] = new RoutingPoint(key,time,sensitivity);
- }
- }
- //TODO: Documentation
- public RoutingPointStore(Key k, int high, int low, int accuracy) {
- this(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++) {
- points[i].key = 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;
- points[offset].time = val;
- if (i <= accuracy / 2)
- val -= valStep;
- else
- val += valStep;
- }
- //TODO: What about the sensitivities?
- }
-
- //Returns the offset of the biggest key that's still less than n.
- final synchronized int search(BigInteger n) {
- int mid, low = 0, high = points.length - 1;
-
- for (;;) {
- mid = (high + low) >> 1;
- int i = points[mid].key.compareTo(n);
- if (i <= 0 && points[mid+1].key.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 synchronized void setAllTimes(int newtime) {
- for (int i = 0; i < points.length; i++) {
- points[i].time = newtime;
- }
- }
-
- //Returns the RoutingPoint at the position 'index' in the store
- synchronized RoutingPoint get(int index) {
- return points[index];
- }
-
- synchronized void set(int index, RoutingPoint value) {
- points[index] = value;
- }
- //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 synchronized int findFirstSmaller_reverse(BigInteger n, int
startAt) {
- while (points[startAt].key.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 synchronized int findFirstLarger(BigInteger n, int startAt) {
- while (points[startAt].key.compareTo(n) == -1) {
- startAt++;
- if (startAt >= points.length)
- return -1;
- }
- return startAt;
- }
-
- int getDataLength() {
- return 4 + points.length * (4 + KEYBYTES);
- }
-
- //Returns the number of items in the store
- int length() {
- return points.length;
- }
- public synchronized void dumpLog() {
- if (Core.logger.shouldLog(Logger.MINOR, this)) {
- StringBuffer sb = new StringBuffer();
- for (int x = 0; x < points.length; x++) {
- sb.append(points[x].key.toString(16));
- sb.append(": ");
- int t = points[x].time;
- 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 < points.length; x++) {
- int t = points[x].time;
- if (t < 0)
- Core.logger.log(this, "time[" + x +
"]=" + t + " - NEGATIVE (" + this +")", Logger.ERROR);
- }
- }
- }
- synchronized void dumpHtml(PrintWriter pw) {
- for (int x = 0; x < points.length; x++) {
- pw.println("<tr><td>" + x + "</td><td>" +
points[x].key.toString(16) + "</td><td>" + points[x].time + "</td><td>" +
points[x].sensitivity + "</td></tr>");
- if (points[x].time < 0)
- Core.logger.log(this, "time[" + x + "]=" +
points[x].time + " - NEGATIVE (" + this +")", Logger.ERROR);
- }
- }
- //Returns the value (time) of the highest-valued RoutingPoint
- public synchronized long highestRaw() {
- int highest = 0;
- for (int x = 0; x < points.length; x++) {
- highest = Math.max(highest,points[x].time);
- }
- return highest;
- }
- //Returns the value (time) of the lowest-valued RoutingPoint
- public synchronized long lowestRaw() {
- int lowest = Integer.MAX_VALUE;
- for (int x = 0; x < points.length; x++) {
- lowest = Math.min(lowest,points[x].time);
- }
- return lowest;
- }
- public synchronized void print() {
- for (int i = 0; i < points.length; i++)
- System.out.println(i + ":\t" + points[i].key + "\t" +
points[i].time);
- }
- //Sorts the RoutingStore in order of its RoutingPoint keys
- protected synchronized 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 synchronized void writeTo(DataOutputStream o) throws
IOException {
- logDEBUG = Core.logger.shouldLog(Logger.DEBUG, this);
- if (logDEBUG)
- logDEBUG("Serializing store to disk, accuracy " +
points.length);
- o.writeInt(points.length);
- for (int i = 0; i < points.length; i++) {
- o.writeInt(points[i].time);
- byte[] b = points[i].key.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(points[i].sensitivity);
- }
- }
-
- //Returns the RoutingPoint which has the highest key
- private RoutingPoint lastPoint() {
- return get(points.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 synchronized void distributeKeysEvenly() {
- BigInteger a = keyspace.subtract(BigInteger.ONE);
- BigInteger b = a.divide(BigInteger.valueOf(points.length));
- for (int i = points.length; --i >= 0; a = a.subtract(b))
- points[i].key = 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
- synchronized 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().key) < 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), points[pos].time,
points[pos].sensitivity);
- retval.right = get(0);
- } else {//else in the middle
- retval.includesKeyspaceWrap = false;
- retval.left = get(pos);
- retval.right = get(pos+1);
- }
- return retval;
- }
- }
}
Index: FFTTimeEstimator.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/node/rt/FFTTimeEstimator.java,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -w -r1.6 -r1.7
--- FFTTimeEstimator.java 31 Oct 2003 19:38:21 -0000 1.6
+++ FFTTimeEstimator.java 3 Nov 2003 08:04:54 -0000 1.7
@@ -22,7 +22,7 @@
//overriden to use FFT on all points
public synchronized void report (Key k, int usec) {
- BigInteger n = convert(k);
+ BigInteger n = k.toBigInteger();
recent.report(n,usec);
_______________________________________________
cvs mailing list
[EMAIL PROTECTED]
http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/cvs
