Package com.github.benmanes.caffeine.cache

Class 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.

    • Field Summary

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

    • 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, or 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 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.
      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.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • BUCKETS

        static final int[] BUCKETS

      • SPANS

        static final long[] SPANS

      • SHIFT

        static final long[] SHIFT

      • wheel

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

      • nanos

        long nanos

    • 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 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 Long.MAX_VALUE if none.

      • peekAhead

        long peekAhead​(int i)
        Returns the duration when the wheel's next bucket expires, or Long.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 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 java.lang.String toString()
        Overrides:
        toString in class java.lang.Object