Update of /cvsroot/freenet/freenet/src/freenet/support
In directory sc8-pr-cvs1:/tmp/cvs-serv14335
Modified Files:
LRUQueue.java
Log Message:
Make LRUQueue Hashtable time for everything instead of O(N) for push and remove and
O(1) for pop. Could probably use some optimization for the initial size of the
Hashtable, but it seems to be an improvement as is
Index: LRUQueue.java
===================================================================
RCS file: /cvsroot/freenet/freenet/src/freenet/support/LRUQueue.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- LRUQueue.java 12 Apr 2002 21:44:10 -0000 1.3
+++ LRUQueue.java 10 Sep 2003 19:45:28 -0000 1.4
@@ -1,17 +1,20 @@
package freenet.support;
import java.util.Enumeration;
+import java.util.Hashtable;
public class LRUQueue {
/*
- * I moves this over to a linked list from a vector, because thinking
- * about the way it was was keeping me awake at night.
- *
- * It is still O(n) but at least this looses all the memcopies.
+ * I've just converted this to using the DLList and Hashtable
+ * this makes it Hashtable time instead of O(N) for push and
+ * remove, and Hashtable time instead of O(1) for pop. Since
+ * push is by far the most done operation, this should be an
+ * overall improvement.
*/
private final DoublyLinkedListImpl list = new DoublyLinkedListImpl();
-
+ private final Hashtable hash = new Hashtable();
+
/**
* push()ing an object that is already in
* the queue moves that object to the most
@@ -19,24 +22,24 @@
* a duplicate entry in the queue.
*/
public final synchronized void push(Object obj) {
- QItem insert = null;
- for (Enumeration e = list.forwardElements() ; e.hasMoreElements() ;) {
- QItem qi = (QItem) e.nextElement();
- if (obj.equals(qi.obj)) {
- insert = qi;
- list.remove(qi);
- break;
- }
- }
- if (insert == null)
+ QItem insert = (QItem)hash.get(obj);
+ if (insert == null) {
insert = new QItem(obj);
+ hash.put(obj,insert);
+ } else {
+ list.remove(insert);
+ }
list.unshift(insert);
}
// Least recently pushed Object.
public final synchronized Object pop() {
- return list.size() > 0 ? ((QItem) list.pop()).obj : null;
+ if ( list.size() > 0 ) {
+ return ((QItem)hash.remove(((QItem)list.pop()).obj)).obj;
+ } else {
+ return null;
+ }
}
public final int size() {
@@ -44,13 +47,7 @@
}
public final synchronized void remove(Object obj) {
- for (Enumeration e = list.forwardElements() ; e.hasMoreElements() ;) {
- QItem qi = (QItem) e.nextElement();
- if (obj.equals(qi.obj)) {
- list.remove(qi);
- break;
- }
- }
+ list.remove((QItem)hash.remove(obj));
}
public Enumeration elements() {
_______________________________________________
cvs mailing list
[EMAIL PROTECTED]
http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/cvs
