Class TimerWheel<K,V>
- java.lang.Object
-
- com.github.benmanes.caffeine.cache.TimerWheel<K,V>
-
final class TimerWheel<K,V> extends java.lang.Object
A hierarchical timer wheel to add, remove, and fire expiration events in amortized O(1) time. The expiration events are deferred until the timer is advanced, which is performed as part of the cache's maintenance cycle.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
TimerWheel.Sentinel<K,V>
A sentinel for the doubly-linked list in the bucket.
-
Constructor Summary
Constructors Constructor Description TimerWheel(BoundedLocalCache<K,V> cache)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
advance(long currentTimeNanos)
Advances the timer and evicts entries that have expired.void
deschedule(@NonNull Node<K,V> node)
Removes a timer event for this entry if present.(package private) void
expire(int index, long previousTicks, long currentTicks)
Expires entries or reschedules into the proper bucket if still active.(package private) Node<K,V>
findBucket(long time)
Determines the bucket that the timer event should be added to.long
getExpirationDelay()
Returns the duration until the next bucket expires, orLong.MAX_VALUE
if none.(package private) void
link(Node<K,V> sentinel, Node<K,V> node)
Adds the entry at the tail of the bucket's list.(package private) long
peekAhead(int i)
Returns the duration when the wheel's next bucket expires, orLong.MAX_VALUE
if empty.void
reschedule(@NonNull Node<K,V> node)
Reschedules an active timer event for the node.void
schedule(@NonNull Node<K,V> node)
Schedules a timer event for the node.java.util.Map<K,V>
snapshot(boolean ascending, int limit, @NonNull java.util.function.Function<V,V> transformer)
Returns an unmodifiable snapshot map roughly ordered by the expiration time.java.lang.String
toString()
(package private) static <K,V>
Node<K,V>traverse(boolean ascending, Node<K,V> node)
(package private) void
unlink(Node<K,V> node)
Removes the entry from its bucket, if scheduled.
-
-
-
Constructor Detail
-
TimerWheel
TimerWheel(BoundedLocalCache<K,V> cache)
-
-
Method Detail
-
advance
public void advance(long currentTimeNanos)
Advances the timer and evicts entries that have expired.- Parameters:
currentTimeNanos
- the current time, in nanoseconds
-
expire
void expire(int index, long previousTicks, long currentTicks)
Expires entries or reschedules into the proper bucket if still active.- Parameters:
index
- the wheel being operated onpreviousTicks
- the previous number of tickscurrentTicks
- the current number of ticks
-
schedule
public void schedule(@NonNull Node<K,V> node)
Schedules a timer event for the node.- Parameters:
node
- the entry in the cache
-
reschedule
public void reschedule(@NonNull Node<K,V> node)
Reschedules an active timer event for the node.- Parameters:
node
- the entry in the cache
-
deschedule
public void deschedule(@NonNull Node<K,V> node)
Removes a timer event for this entry if present.- Parameters:
node
- the entry in the cache
-
findBucket
Node<K,V> findBucket(long time)
Determines the bucket that the timer event should be added to.- Parameters:
time
- the time when the event fires- Returns:
- the sentinel at the head of the bucket
-
link
void link(Node<K,V> sentinel, Node<K,V> node)
Adds the entry at the tail of the bucket's list.
-
getExpirationDelay
public long getExpirationDelay()
Returns the duration until the next bucket expires, orLong.MAX_VALUE
if none.
-
peekAhead
long peekAhead(int i)
Returns the duration when the wheel's next bucket expires, orLong.MAX_VALUE
if empty.
-
snapshot
public java.util.Map<K,V> snapshot(boolean ascending, int limit, @NonNull java.util.function.Function<V,V> transformer)
Returns an unmodifiable snapshot map roughly ordered by the expiration time. The wheels are evaluated in order, but the timers that fall within the bucket's range are not sorted. Beware that obtaining the mappings is NOT a constant-time operation.- Parameters:
ascending
- the directionlimit
- the maximum number of entriestransformer
- a function that unwraps the value- Returns:
- an unmodifiable snapshot in the desired order
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-