public class HashedTimeoutPriorityQueueImpl extends java.lang.Object implements TimeoutPriorityQueue
j are at j*2
and j*2+1. The children of a node always fire the timeout
no earlier than the node.
Or, more formally:
Only indices 1..size of this array are used.
All other indices contain the null reference.
This array represent a balanced binary tree.
If size is 0 the tree is empty, otherwise
the root of the tree is at index 1.
Given an arbitrary node at index n that is not the root
node, the parent node of n is at index n/2.
Given an arbitrary node at index n; if
2*n <= size the node at n has its left child
at index 2*n, otherwise the node at n has
no left child.
Given an arbitrary node at index n; if
2*n+1 <= size the node at n has its right child
at index 2*n+1, otherwise the node at n has
no right child.
The priority function is called T. Given a node n,
T(n) denotes the absolute time (in milliseconds since
the epoch) that the timeout for node n should happen.
Smaller values of T means higher priority.
The tree satisfies the following invariant:
For any node n in the tree:
If node n has a left child l,
T(n) <= T(l).
If node n has a right child r,
T(n) <= T(r).
The invariant may be temporarily broken while executing synchronized
on this instance, but is always reestablished before
leaving the synchronized code.
The node at index 1 is always the first node to timeout,
as can be deduced from the invariant.
For the following algorithm pseudocode, the operation
swap(n,m) denotes the exchange of the nodes at indices
n and m in the tree.
Insertion of a new node happend as follows:
IF size = q.length THEN
"expand q array to be larger";
ENDIF
size <- size + 1;
q[size] <- "new node";
n <- size;
WHILE n > 1 AND T(n/2) > T(n) DO
swap(n/2, n);
n <- n/2;
ENDWHILE
Proof that this insertion algorithm respects the invariant is left to
the interested reader.
The removal algorithm is a bit more complicated. To remove the node
at index n:
swap(n, size);
size <- size - 1;
IF n > 1 AND T(n/2) > T(n) THEN
WHILE n > 1 AND T(n/2) > T(n) DO
swap(n/2, n);
n <- n/2;
ENDWHILE
ELSE
WHILE 2*n <= size DO
IF 2*n+1 <= size THEN
// Both children present
IF T(2*n) <= T(2*n+1) THEN
IF T(n) <= T(2*n) THEN
EXIT;
ENDIF
swap(n, 2*n);
n <- 2*n;
ELSE
IF T(n) <= T(2*n+1) THEN
EXIT;
ENDIF
swap(n, 2*n+1);
n <- 2*n+1;
ENDIF
ELSE
// Only left child, right child not present.
IF T(n) <= T(2*n) THEN
EXIT;
ENDIF
swap(n, 2*n);
n <- 2*n;
ENDIF
ENDWHILE
ENDIF
Proof that this removal algorithm respects the invariant is left to
the interested reader. Really, I am not going to prove it here.
If you are interested, you can find this data structure and its
associated operations in most textbooks on algorithmics.| Modifier and Type | Class and Description |
|---|---|
private class |
HashedTimeoutPriorityQueueImpl.InternalPriorityQueue
Internal priority queue
|
private class |
HashedTimeoutPriorityQueueImpl.TimeoutExtImpl
Our private Timeout implementation.
|
| Modifier and Type | Field and Description |
|---|---|
private java.util.concurrent.atomic.AtomicBoolean |
cancelled |
private HashedTimeoutPriorityQueueImpl.InternalPriorityQueue[] |
queues
The hashed queues
|
private HashedTimeoutPriorityQueueImpl.TimeoutExtImpl |
top
The top element
|
private java.lang.Object |
topLock
The lock object
|
| Constructor and Description |
|---|
HashedTimeoutPriorityQueueImpl()
Create a new TimeoutPriorityQueueImpl.
|
| Modifier and Type | Method and Description |
|---|---|
private void |
assertExpr(boolean expr)
Debugging helper.
|
void |
cancel()
Cancels the queue
|
private HashedTimeoutPriorityQueueImpl.TimeoutExtImpl |
cleanupTimeoutExtImpl(HashedTimeoutPriorityQueueImpl.TimeoutExtImpl timeout)
Recursive cleanup of a TimeoutImpl
|
void |
clear()
Clears the queue
|
java.lang.String |
dump() |
boolean |
isCancelled()
Whether the queue is cancelled
|
TimeoutExt |
offer(long time,
TimeoutTarget target)
Add a timeout to the queue
|
TimeoutExt |
peek()
Retrieves but does not remove the top of the queue
or null if there is no such element
|
TimeoutExt |
poll()
Retrieves and removes the top of the queue if it times out
or null if there is no such element
|
TimeoutExt |
poll(long wait)
Retrieves and removes the top of the queue if it times out
or null if there is no such element
|
private void |
recalculateTop(boolean notify) |
boolean |
remove(TimeoutExt timeout)
Removes the passed timeout from the queue
|
int |
size() |
TimeoutExt |
take()
Take a timeout when it times out
|
private java.lang.Object topLock
private HashedTimeoutPriorityQueueImpl.TimeoutExtImpl top
private HashedTimeoutPriorityQueueImpl.InternalPriorityQueue[] queues
private java.util.concurrent.atomic.AtomicBoolean cancelled
public HashedTimeoutPriorityQueueImpl()
public TimeoutExt offer(long time, TimeoutTarget target)
TimeoutPriorityQueueoffer in interface TimeoutPriorityQueuetime - the time of the timeouttarget - the timeout targetpublic TimeoutExt take()
TimeoutPriorityQueuetake in interface TimeoutPriorityQueuepublic TimeoutExt poll()
TimeoutPriorityQueuepoll in interface TimeoutPriorityQueuepublic TimeoutExt poll(long wait)
TimeoutPriorityQueuepoll in interface TimeoutPriorityQueuewait - how to long to wait in milliseconds
if the queue is emptypublic TimeoutExt peek()
TimeoutPriorityQueuepeek in interface TimeoutPriorityQueuepublic boolean remove(TimeoutExt timeout)
TimeoutPriorityQueueremove in interface TimeoutPriorityQueuepublic void clear()
TimeoutPriorityQueueclear in interface TimeoutPriorityQueuepublic void cancel()
TimeoutPriorityQueuecancel in interface TimeoutPriorityQueuepublic int size()
size in interface TimeoutPriorityQueuepublic boolean isCancelled()
private void recalculateTop(boolean notify)
private HashedTimeoutPriorityQueueImpl.TimeoutExtImpl cleanupTimeoutExtImpl(HashedTimeoutPriorityQueueImpl.TimeoutExtImpl timeout)
private void assertExpr(boolean expr)
public java.lang.String dump()