Package org.jboss.util.timeout
Class HashedTimeoutPriorityQueueImpl
- java.lang.Object
-
- org.jboss.util.timeout.HashedTimeoutPriorityQueueImpl
-
- All Implemented Interfaces:
TimeoutPriorityQueue
public class HashedTimeoutPriorityQueueImpl extends java.lang.Object implements TimeoutPriorityQueue
HashedTimeoutPriorityQueueImpl. 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 indexj
are atj*2
andj*2+1
. The children of a node always fire the timeout no earlier than the node. Or, more formally: Only indices1
..size
of this array are used. All other indices contain the null reference. This array represent a balanced binary tree. Ifsize
is0
the tree is empty, otherwise the root of the tree is at index1
. Given an arbitrary node at indexn
that is not the root node, the parent node ofn
is at indexn/2
. Given an arbitrary node at indexn
; if2*n <= size
the node atn
has its left child at index2*n
, otherwise the node atn
has no left child. Given an arbitrary node at indexn
; if2*n+1 <= size
the node atn
has its right child at index2*n+1
, otherwise the node atn
has no right child. The priority function is called T. Given a noden
,T(n)
denotes the absolute time (in milliseconds since the epoch) that the timeout for noden
should happen. Smaller values ofT
means higher priority. The tree satisfies the following invariant: For any noden
in the tree: If noden
has a left childl
,T(n) <= T(l)
. If noden
has a right childr
,T(n) <= T(r)
. The invariant may be temporarily broken while executing synchronized onthis
instance, but is always reestablished before leaving the synchronized code. The node at index1
is always the first node to timeout, as can be deduced from the invariant. For the following algorithm pseudocode, the operationswap(n,m)
denotes the exchange of the nodes at indicesn
andm
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 indexn
: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.- Version:
- $Revision$
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
HashedTimeoutPriorityQueueImpl.InternalPriorityQueue
Internal priority queueprivate class
HashedTimeoutPriorityQueueImpl.TimeoutExtImpl
Our private Timeout implementation.
-
Field Summary
Fields Modifier and Type Field Description private java.util.concurrent.atomic.AtomicBoolean
cancelled
private HashedTimeoutPriorityQueueImpl.InternalPriorityQueue[]
queues
The hashed queuesprivate HashedTimeoutPriorityQueueImpl.TimeoutExtImpl
top
The top elementprivate java.lang.Object
topLock
The lock object
-
Constructor Summary
Constructors Constructor Description HashedTimeoutPriorityQueueImpl()
Create a new TimeoutPriorityQueueImpl.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
assertExpr(boolean expr)
Debugging helper.void
cancel()
Cancels the queueprivate HashedTimeoutPriorityQueueImpl.TimeoutExtImpl
cleanupTimeoutExtImpl(HashedTimeoutPriorityQueueImpl.TimeoutExtImpl timeout)
Recursive cleanup of a TimeoutImplvoid
clear()
Clears the queuejava.lang.String
dump()
boolean
isCancelled()
Whether the queue is cancelledTimeoutExt
offer(long time, TimeoutTarget target)
Add a timeout to the queueTimeoutExt
peek()
Retrieves but does not remove the top of the queue or null if there is no such elementTimeoutExt
poll()
Retrieves and removes the top of the queue if it times out or null if there is no such elementTimeoutExt
poll(long wait)
Retrieves and removes the top of the queue if it times out or null if there is no such elementprivate void
recalculateTop(boolean notify)
boolean
remove(TimeoutExt timeout)
Removes the passed timeout from the queueint
size()
TimeoutExt
take()
Take a timeout when it times out
-
-
-
Field Detail
-
topLock
private java.lang.Object topLock
The lock object
-
top
private HashedTimeoutPriorityQueueImpl.TimeoutExtImpl top
The top element
-
queues
private HashedTimeoutPriorityQueueImpl.InternalPriorityQueue[] queues
The hashed queues
-
cancelled
private java.util.concurrent.atomic.AtomicBoolean cancelled
-
-
Method Detail
-
offer
public TimeoutExt offer(long time, TimeoutTarget target)
Description copied from interface:TimeoutPriorityQueue
Add a timeout to the queue- Specified by:
offer
in interfaceTimeoutPriorityQueue
- Parameters:
time
- the time of the timeouttarget
- the timeout target- Returns:
- timeout when it was added to the queue, false otherwise
-
take
public TimeoutExt take()
Description copied from interface:TimeoutPriorityQueue
Take a timeout when it times out- Specified by:
take
in interfaceTimeoutPriorityQueue
- Returns:
- the top the queue or null if the queue is cancelled
-
poll
public TimeoutExt poll()
Description copied from interface:TimeoutPriorityQueue
Retrieves and removes the top of the queue if it times out or null if there is no such element- Specified by:
poll
in interfaceTimeoutPriorityQueue
- Returns:
- the top the queue or null if the queue is empty
-
poll
public TimeoutExt poll(long wait)
Description copied from interface:TimeoutPriorityQueue
Retrieves and removes the top of the queue if it times out or null if there is no such element- Specified by:
poll
in interfaceTimeoutPriorityQueue
- Parameters:
wait
- how to long to wait in milliseconds if the queue is empty- Returns:
- the top of the queue or null if the queue is empty
-
peek
public TimeoutExt peek()
Description copied from interface:TimeoutPriorityQueue
Retrieves but does not remove the top of the queue or null if there is no such element- Specified by:
peek
in interfaceTimeoutPriorityQueue
- Returns:
- the top of the queue or null if the queue is empty
-
remove
public boolean remove(TimeoutExt timeout)
Description copied from interface:TimeoutPriorityQueue
Removes the passed timeout from the queue- Specified by:
remove
in interfaceTimeoutPriorityQueue
- Returns:
- true when the timeout was removed
-
clear
public void clear()
Description copied from interface:TimeoutPriorityQueue
Clears the queue- Specified by:
clear
in interfaceTimeoutPriorityQueue
-
cancel
public void cancel()
Description copied from interface:TimeoutPriorityQueue
Cancels the queue- Specified by:
cancel
in interfaceTimeoutPriorityQueue
-
size
public int size()
- Specified by:
size
in interfaceTimeoutPriorityQueue
- Returns:
- the size of the queue
-
isCancelled
public boolean isCancelled()
Whether the queue is cancelled- Returns:
- true when cancelled
-
recalculateTop
private void recalculateTop(boolean notify)
-
cleanupTimeoutExtImpl
private HashedTimeoutPriorityQueueImpl.TimeoutExtImpl cleanupTimeoutExtImpl(HashedTimeoutPriorityQueueImpl.TimeoutExtImpl timeout)
Recursive cleanup of a TimeoutImpl- Returns:
- null
-
assertExpr
private void assertExpr(boolean expr)
Debugging helper.
-
dump
public java.lang.String dump()
-
-