Author: toad
Date: 2007-03-09 02:28:26 +0000 (Fri, 09 Mar 2007)
New Revision: 12049
Added:
trunk/freenet/src/freenet/support/TimeSortedHashtable.java
Modified:
trunk/freenet/src/freenet/node/LocationManager.java
trunk/freenet/src/freenet/support/LRUHashtable.java
Log:
Fix too-many-locations bug
Modified: trunk/freenet/src/freenet/node/LocationManager.java
===================================================================
--- trunk/freenet/src/freenet/node/LocationManager.java 2007-03-09 00:32:33 UTC
(rev 12048)
+++ trunk/freenet/src/freenet/node/LocationManager.java 2007-03-09 02:28:26 UTC
(rev 12049)
@@ -4,14 +4,9 @@
package freenet.node;
import java.security.MessageDigest;
-import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
-import java.util.Set;
-import java.util.SortedMap;
-import java.util.TreeMap;
import java.util.Vector;
-import java.util.Date;
import freenet.crypt.RandomSource;
import freenet.crypt.SHA256;
@@ -23,6 +18,7 @@
import freenet.support.Fields;
import freenet.support.Logger;
import freenet.support.ShortBuffer;
+import freenet.support.TimeSortedHashtable;
/**
* @author amphibian
@@ -1027,8 +1023,10 @@
recentlyForwardedIDs.remove(new Long(item.outgoingID));
}
- private final TreeMap knownLocs = new TreeMap();
+ private final long MAX_AGE = 7*24*60*60*1000;
+ private final TimeSortedHashtable knownLocs = new TimeSortedHashtable();
+
void registerLocationLink(double d, double t) {
if(logMINOR) Logger.minor(this, "Known Link: "+d+ ' ' +t);
}
@@ -1036,28 +1034,23 @@
void registerKnownLocation(double d) {
if(logMINOR) Logger.minor(this, "Known Location: "+d);
Double dd = new Double(d);
- Date timestamp = new Date();
- Long longTime = new Long(timestamp.getTime());
+ long now = System.currentTimeMillis();
synchronized(knownLocs) {
- // FIXME: The TreeMap size will keep on increasing...
- // knownLocs.values().remove(dd); would be costy
- // Maybe the best solution is to do a
- // knownLocs = knownLocs.headMap(longTime -
arbitrary_value)
-
- //Add the location to the map with the current
timestamp as key
- knownLocs.put(longTime, dd);
+ Logger.minor(this, "Adding location "+dd+" knownLocs size
"+knownLocs.size());
+ knownLocs.push(dd, now);
+ Logger.minor(this, "Added location "+dd+" knownLocs size
"+knownLocs.size());
+ knownLocs.removeBefore(now - MAX_AGE);
+ Logger.minor(this, "Added and pruned location "+dd+" knownLocs
size "+knownLocs.size());
}
if(logMINOR) Logger.minor(this, "Estimated net size(session):
"+knownLocs.size());
}
//Return the estimated network size based on locations seen after
timestamp or for the whole session if -1
public int getNetworkSizeEstimate(long timestamp) {
- final SortedMap temp;
synchronized (knownLocs) {
- temp = (timestamp == -1 ? knownLocs : knownLocs.tailMap(new
Long(timestamp)));
+ return knownLocs.countValuesAfter(timestamp);
}
- return temp.size();
}
/**
@@ -1066,12 +1059,8 @@
* @Return an array containing two cells : Locations and their last seen
time for a given timestamp.
*/
public Object[] getKnownLocations(long timestamp) {
- final SortedMap temp;
synchronized (knownLocs) {
- temp = timestamp == -1 ? knownLocs : knownLocs.tailMap(new
Long(timestamp));
- Set keys = temp.keySet();
- Collection values = temp.values();
- return new Object[]{ (Double[])values.toArray(new
Double[keys.size()]), (Long[])keys.toArray(new Long[values.size()])};
+ return knownLocs.pairsAfter(timestamp, new
Double[knownLocs.size()]);
}
}
}
Modified: trunk/freenet/src/freenet/support/LRUHashtable.java
===================================================================
--- trunk/freenet/src/freenet/support/LRUHashtable.java 2007-03-09 00:32:33 UTC
(rev 12048)
+++ trunk/freenet/src/freenet/support/LRUHashtable.java 2007-03-09 02:28:26 UTC
(rev 12049)
@@ -47,6 +47,14 @@
}
}
+ public final synchronized Object peekValue() {
+ if ( list.size() > 0 ) {
+ return ((QItem)hash.get(((QItem)list.pop()).obj)).obj;
+ } else {
+ return null;
+ }
+ }
+
/**
* @return Least recently pushed value.
*/
@@ -120,4 +128,5 @@
return super.toString()+": "+obj+ ' ' +value;
}
}
+
}
Added: trunk/freenet/src/freenet/support/TimeSortedHashtable.java
===================================================================
--- trunk/freenet/src/freenet/support/TimeSortedHashtable.java
(rev 0)
+++ trunk/freenet/src/freenet/support/TimeSortedHashtable.java 2007-03-09
02:28:26 UTC (rev 12049)
@@ -0,0 +1,195 @@
+package freenet.support;
+
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.TreeSet;
+
+/**
+ * Variant on LRUHashtable which provides an efficient how-many-since-time-T
operation.
+ */
+public class TimeSortedHashtable {
+
+ private class Element {
+
+ Element(long t, Comparable v) {
+ time = t;
+ value = v;
+ }
+
+ long time;
+ final Comparable value;
+
+ public int compareTo(Object o) {
+ Element e = (Element) o;
+ if(time > e.time) return 1;
+ if(time < e.time) return -1;
+ return value.compareTo(e.value);
+ }
+ }
+
+ private class MyComparator implements Comparator {
+
+ public int compare(Object arg0, Object arg1) {
+ if(arg0 instanceof Long && arg1 instanceof Long) return
((Long)arg0).compareTo(arg1);
+ if(arg0 instanceof Element && arg1 instanceof Element)
return ((Element)arg0).compareTo(arg1);
+ if(arg0 instanceof Long) {
+ long l = ((Long)arg0).longValue();
+ Element e = (Element)arg1;
+ if(l > e.time) return 1;
+ if(l < e.time) return -1;
+ return 0;
+ } else {
+ // arg1 instanceof Long
+ Element e = (Element)arg0;
+ long l = ((Long)arg1).longValue();
+ if(e.time > l) return 1;
+ if(e.time < l) return -1;
+ return 0;
+ }
+ }
+
+ }
+
+ private final TreeSet elements = new TreeSet(new MyComparator());
+ private final HashMap valueToElement = new HashMap();
+
+ public final void push(Comparable value) {
+ push(value, System.currentTimeMillis());
+ }
+
+ /**
+ * push()ing an object that is already in
+ * the queue moves that object to the most
+ * recently used position, but doesn't add
+ * a duplicate entry in the queue.
+ * @param now
+ */
+ public final synchronized void push(Comparable value, long now) {
+
+ assert(elements.size() == valueToElement.size());
+
+ Element e = (Element) valueToElement.get(value);
+
+ if(e == null) {
+ e = new Element(now, value);
+ elements.add(e);
+ valueToElement.put(value, e);
+ } else {
+ elements.remove(e);
+ e.time = now;
+ elements.add(e);
+ }
+
+ assert(elements.size() == valueToElement.size());
+ }
+
+ /**
+ * @return Least recently pushed value.
+ */
+ public final synchronized Comparable popValue() {
+ assert(elements.size() == valueToElement.size());
+
+ Element e = (Element) elements.first();
+ valueToElement.remove(e.value);
+
+ assert(elements.size() == valueToElement.size());
+ return e.value;
+ }
+
+ public final synchronized Object peekValue() {
+ return ((Element) elements.first()).value;
+ }
+
+ public final int size() {
+ return elements.size();
+ }
+
+ public final synchronized boolean removeValue(Comparable value) {
+ assert(elements.size() == valueToElement.size());
+ Element e = (Element) valueToElement.remove(value);
+ if(e == null) return false;
+ elements.remove(e);
+ assert(elements.size() == valueToElement.size());
+ return true;
+ }
+
+ public final synchronized boolean containsValue(Comparable key) {
+ return valueToElement.containsKey(key);
+ }
+
+ /**
+ * Note that this does not automatically promote the key. You have
+ * to do that by hand with push(key, value).
+ */
+ public final synchronized long getTime(Object value) {
+ Element e = (Element) valueToElement.remove(value);
+ if(e == null) return -1;
+ return e.time;
+ }
+
+ /**
+ * @return The set of times after the given time.
+ */
+ public final synchronized Long[] timesAfter(long t) {
+ Long time = new Long(t);
+
+ Set s = elements.tailSet(time);
+
+ Long[] times = new Long[s.size()];
+ int x = 0;
+ for(Iterator i = s.iterator();i.hasNext();) {
+ times[x++] = new Long(((Element)i.next()).time);
+ }
+
+ return times;
+ }
+
+ /**
+ * @return The set of values after the given time.
+ */
+ public final synchronized Comparable[] valuesAfter(long t, Comparable[]
values) {
+ Long time = new Long(t);
+
+ Set s = elements.tailSet(time);
+
+ int x = 0;
+ for(Iterator i = s.iterator();i.hasNext();) {
+ values[x++] = ((Element)i.next()).value;
+ }
+
+ return values;
+ }
+
+ public int countValuesAfter(long t) {
+ Long time = new Long(t);
+
+ Set s = elements.tailSet(time);
+
+ return s.size();
+ }
+
+ /**
+ * Remove all entries before the given time.
+ */
+ public final synchronized void removeBefore(long t) {
+ assert(elements.size() == valueToElement.size());
+
+ Long time = new Long(t);
+ Set s = elements.headSet(time);
+
+ for(Iterator i = s.iterator();i.hasNext();) {
+ Element e = (Element) i.next();
+ valueToElement.remove(e.value);
+ i.remove();
+ }
+
+ assert(elements.size() == valueToElement.size());
+ }
+
+ public final synchronized Object[] pairsAfter(long timestamp,
Comparable[] valuesArray) {
+ return new Object[] { valuesAfter(timestamp, valuesArray),
timesAfter(timestamp) };
+ }
+
+}
