User: osh
Date: 00/10/02 21:07:34
Modified: src/main/org/jboss/util/timeout TimeoutFactory.java
Log:
Fixed a few bugs
Revision Changes Path
1.2 +173 -55 jboss/src/main/org/jboss/util/timeout/TimeoutFactory.java
Index: TimeoutFactory.java
===================================================================
RCS file:
/products/cvs/ejboss/jboss/src/main/org/jboss/util/timeout/TimeoutFactory.java,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- TimeoutFactory.java 2000/09/08 02:32:47 1.1
+++ TimeoutFactory.java 2000/10/03 04:07:33 1.2
@@ -6,7 +6,9 @@
*/
package org.jboss.util.timeout;
+import org.jboss.logging.Logger;
+
/**
* The timeout factory.
*
@@ -20,7 +22,7 @@
* allocating anything on the heap.
*
* @author <a href="[EMAIL PROTECTED]">Ole Husgaard</a>
- * @version $Revision: 1.1 $
+ * @version $Revision: 1.2 $
*/
public class TimeoutFactory {
@@ -28,30 +30,37 @@
* Our private Timeout implementation.
*/
private class TimeoutImpl implements Timeout {
- static final int DONE = -1; // done, may be finalized
+ static final int DONE = -1; // done, may be finalized or reused
static final int TIMEOUT = -2; // target being called
- static final int CWAIT = -3; // target being called and cancel waiting
+ static final int CWAIT = -3; // target being called and cancel waiting
int index; // index in queue, or one of constants above.
- long time;
- TimeoutTarget target;
+ long time; // time to fire
+ TimeoutTarget target; // target to fire at
+ TimeoutImpl nextFree; // next on free list
public void cancel() {
- TimeoutFactory.this.cancelTimeout(this);
+ TimeoutFactory.this.dropTimeout(this);
}
}
+ /** Linked list of free TimeoutImpl instances. */
+ private TimeoutImpl freeList;
+
/** The size of the timeout queue. */
private int size;
/**
* Our priority queue.
- * This is a binary tree. If nonempty, the root is at index 1, and all
- * nodes are at indices 1..size. Nodes with index greater than size
- * are considered null. Index 0 is never used.
+ *
+ * This is a balanced binary tree. If nonempty, the root is at index 1,
+ * and all nodes are at indices 1..size. Nodes with index greater than
+ * size are null. Index 0 is never used.
* Children of the node at index <code>j</code> are at <code>j*2</code>
* and <code>j*2+1</code>. The children of a node always fire the timeout
- * no later than the node.
+ * no earlier than the node.
+ *
+ * @see checkTree
*/
private TimeoutImpl[] q;
@@ -60,15 +69,63 @@
*/
private void assert(boolean expr) {
if (!expr) {
- System.err.println("***** assert failed *****");
- Thread.currentThread().dumpStack();
+ Logger.error("***** assert failed *****");
+ //System.err.println("***** assert failed *****");
+ try {
+ throw new RuntimeException("***** assert failed *****");
+ } catch (RuntimeException ex) {
+ Logger.exception(ex);
+ //ex.printStackTrace();
+ }
+ try {
+ Thread.sleep(30000);
+ } catch (Exception ex) {}
}
}
/**
+ * Check invariants of the queue.
+ */
+ private void checkTree() {
+ assert(size >= 0);
+ assert(size < q.length);
+ assert(q[0] == null);
+
+ if (size > 0) {
+ assert(q[1] != null);
+ assert(q[1].index == 1);
+ for (int i = 2; i <= size; ++i) {
+ assert(q[i] != null);
+ assert(q[i].index == i);
+ assert(q[i >> 1].time <= q[i].time); // parent fires first
+ }
+ for (int i = size+1; i < q.length; ++i)
+ assert(q[i] == null);
+ }
+ }
+
+ /**
+ * Check invariants of the free list.
+ */
+ private void checkFreeList() {
+ TimeoutImpl to = freeList;
+
+ while (to != null) {
+ assert(to.index == TimeoutImpl.DONE);
+ to = to.nextFree;
+ }
+ }
+
+ /**
* Swap two nodes in the tree.
*/
private void swap(int a, int b) {
+ assert(a > 0);
+ assert(a <= size);
+ assert(b > 0);
+ assert(b <= size);
+ assert(q[a] != null);
+ assert(q[b] != null);
assert(q[a].index == a);
assert(q[b].index == b);
TimeoutImpl temp = q[a];
@@ -81,73 +138,126 @@
/**
* A new node has been added at index <code>index</code>.
* Normalize the tree by moving the new node up the tree.
+ *
+ * @return True iff the tree was modified.
*/
- private void normalizeUp(int index) {
+ private boolean normalizeUp(int index) {
assert(index > 0);
assert(index <= size);
assert(q[index] != null);
- long t = q[index].time;
if (index == 1)
- return; // at root
+ return false; // at root
+ boolean ret = false;
+ long t = q[index].time;
int p = index >> 1;
while (q[p].time > t) {
+ assert(q[index].time == t);
swap(p, index);
+ ret = true;
if (p == 1)
- return; // at root
+ break; // at root
index = p;
p >>= 1;
}
+ return ret;
}
/**
* Remove a node from the tree and normalize.
- * Returns the removed node.
+ *
+ * @return The removed node.
*/
private TimeoutImpl removeNode(int index) {
assert(index > 0);
assert(index <= size);
TimeoutImpl res = q[index];
+ assert(res != null);
+ assert(res.index == index);
+
+ if (index == size) {
+ --size;
+ q[index] = null;
+ return res;
+ }
+
+ swap(index, size); // Exchange removed node with last leaf node
+ --size;
+
+ assert(res.index == size + 1);
+ q[res.index] = null;
- // one less entry
- if (--size <= 1)
- return res; // Already normal
+ if (normalizeUp(index))
+ return res; // Node moved up, so it shouldn't move down
- // Normalize
+ long t = q[index].time;
int c = index << 1;
- long t = res.time;
- while (q[c].time <= t) {
- swap(index, c);
+ while (c <= size) {
+ assert(q[index].time == t);
- index = c;
+ TimeoutImpl l = q[c];
+ assert(l != null);
+ assert(l.index == c);
+
+ if (c+1 <= size) {
+ // two children, swap with smallest
+ TimeoutImpl r = q[c+1];
+ assert(r != null);
+ assert(r.index == c+1);
+
+ if (l.time <= r.time) {
+ if (t <= l.time)
+ break; // done
+ swap(index, c);
+ index = c;
+ } else {
+ if (t <= r.time)
+ break; // done
+ swap(index, c+1);
+ index = c+1;
+ }
+ } else { // one child
+ if (t <= l.time)
+ break; // done
+ swap(index, c);
+ index = c;
+ }
- c <<= 1;
- if (c > size)
- break; // node at index is a leaf
+ c = index << 1;
}
+
return res;
}
-
/**
* Create a new timeout.
*/
private synchronized Timeout newTimeout(long time, TimeoutTarget target) {
- if (size == q.length) {
+ checkTree();
+
+ assert(size < q.length);
+ if (++size == q.length) {
TimeoutImpl[] newQ = new TimeoutImpl[2*q.length];
System.arraycopy(q, 0, newQ, 0, q.length);
q = newQ;
}
- ++size;
- if (q[size] == null)
- q[size] = new TimeoutImpl();
+ assert(size < q.length);
+ assert(q[size] == null);
+
+ TimeoutImpl timeout;
- TimeoutImpl timeout = q[size];
+ if (freeList != null) {
+ timeout = q[size] = freeList;
+ freeList = timeout.nextFree;
+ checkFreeList();
+ assert(timeout.index == TimeoutImpl.DONE);
+ } else
+ timeout = q[size] = new TimeoutImpl();
timeout.index = size;
timeout.time = time;
@@ -155,9 +265,11 @@
normalizeUp(size);
- if (timeout.index == 1 || size == 1)
+ if (timeout.index == 1)
notify();
+ checkTree();
+
return timeout;
}
@@ -167,20 +279,29 @@
private void dropTimeout(TimeoutImpl timeout) {
synchronized (this) {
if (timeout.index > 0) {
+ // Active timeout, remove it.
+ assert(q[timeout.index] == timeout);
+ checkTree();
removeNode(timeout.index);
+ checkTree();
+ timeout.index = TimeoutImpl.DONE;
+ timeout.nextFree = freeList;
+ freeList = timeout;
+ checkFreeList();
return;
}
}
- // Timeout has already started, wait until done.
+ // If timeout has already started, wait until done.
synchronized (timeout) {
- if (timeout.index == TimeoutImpl.TIMEOUT) {
+ if (timeout.index == TimeoutImpl.TIMEOUT ||
+ timeout.index == TimeoutImpl.CWAIT) {
// Wait to avoid race with the actual timeout that is happening now.
timeout.index = TimeoutImpl.CWAIT;
while (timeout.index == TimeoutImpl.CWAIT) {
try {
timeout.wait();
- } catch (InterruptedException ex) {}
+ } catch (InterruptedException ex) { }
}
}
}
@@ -188,18 +309,6 @@
/**
- * Cancel a timeout.
- */
- private void cancelTimeout(Timeout timeout) {
- if (timeout == null)
- throw new IllegalArgumentException("Null timeout");
- if (!(timeout instanceof TimeoutImpl))
- throw new IllegalArgumentException("Unknown timeout");
-
- dropTimeout((TimeoutImpl)timeout);
- }
-
- /**
* Timeout worker method.
* This method never returns. Whenever it is time to do a timeout,
* the callback method is called from here.
@@ -208,6 +317,7 @@
while (true) {
TimeoutImpl work = null;
+ // Look for work
synchronized (this) {
if (size == 0) {
try {
@@ -219,21 +329,28 @@
try {
wait(q[1].time - now);
} catch (InterruptedException ex) {}
- } else {
+ }
+ if (size > 0 && q[1].time <= System.currentTimeMillis()) {
work = removeNode(1);
- q[work.index] = null;
work.index = TimeoutImpl.TIMEOUT;
}
}
}
+ // Do work, if any
if (work != null) {
- work.target.timedOut(work);
+ try {
+ work.target.timedOut(work);
+ } catch (Throwable t) {
+ Logger.exception(t);
+ //t.printStackTrace();
+ }
synchronized (work) {
if (work.index == TimeoutImpl.CWAIT) {
work.index = TimeoutImpl.DONE;
- work.notify(); // wake up cancel() thread.
- }
+ work.notifyAll(); // wake up cancel() threads.
+ } else
+ work.index = TimeoutImpl.DONE;
}
}
}
@@ -244,6 +361,7 @@
/** Our private constructor. */
private TimeoutFactory() {
+ freeList = null;
size = 0;
q = new TimeoutImpl[16];
}
