Class TimerWheel<K,V>

java.lang.Object
com.github.benmanes.caffeine.cache.TimerWheel<K,V>
final class TimerWheel<K,V> extends 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 final class 
    TimerWheel.Sentinel<K,V>
    A sentinel for the doubly-linked list in the bucket.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    (package private) static final int[]
    BUCKETS
     
    (package private) final BoundedLocalCache<K,V>
    cache
     
    (package private) long
    nanos
     
    (package private) static final long[]
    SHIFT
     
    (package private) static final long[]
    SPANS
     
    (package private) final Node<K,V>[][]
    wheel
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    TimerWheel(BoundedLocalCache<K,V> cache)
     

  • Method Summary

    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, or
    invalid reference 
    Long.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, or
    invalid reference 
    Long.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.
    Map<K,V>
    snapshot(boolean ascending, int limit, @NonNull Function<V,V> transformer)
    Returns an unmodifiable snapshot map roughly ordered by the expiration time.
    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.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • BUCKETS

      static final int[] BUCKETS

    • SPANS

      static final long[] SPANS

    • SHIFT

      static final long[] SHIFT

    • cache

      final BoundedLocalCache<K,V> cache

    • wheel

      final Node<K,V>[][] wheel

    • nanos

      long nanos

  • Constructor Details

  • Method Details

    • 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 on
      previousTicks - the previous number of ticks
      currentTicks - 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.

    • unlink

      void unlink(Node<K,V> node)
      Removes the entry from its bucket, if scheduled.

    • getExpirationDelay

      public long getExpirationDelay()
      Returns the duration until the next bucket expires, or
      invalid reference 
      Long.MAX_VALUE
      if none.

    • peekAhead

      long peekAhead(int i)
      Returns the duration when the wheel's next bucket expires, or
      invalid reference 
      Long.MAX_VALUE
      if empty.

    • snapshot

      public Map<K,V> snapshot(boolean ascending, int limit, @NonNull 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 direction
      limit - the maximum number of entries
      transformer - a function that unwraps the value
      Returns:
      an unmodifiable snapshot in the desired order

    • traverse

      static <K,V> Node<K,V> traverse(boolean ascending, Node<K,V> node)

    • toString

      public String toString()
      Overrides:
      toString in class Object