#5173

Committed 29 Dec 2025 05:27AM UTC coverage: 0.0% (-100.0%) from 100.0%

Build # #5173

Build Type

push

github

Committed by

ben-manes

Commit Message

speed up development ci build

Run Details

0 of 3838 branches covered (0.0%)

0 of 7869 relevant lines covered (0.0%)

0.0 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/caffeine/src/main/java/com/github/benmanes/caffeine/cache/TimerWheel.java

/*
 * Copyright 2017 Ben Manes. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.benmanes.caffeine.cache;

import static com.github.benmanes.caffeine.cache.Caffeine.ceilingPowerOfTwo;
import static java.util.Objects.requireNonNull;

import java.lang.ref.ReferenceQueue;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.TimeUnit;

import org.jspecify.annotations.Nullable;

import com.google.errorprone.annotations.Var;

/**
 * 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.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 */
@SuppressWarnings("GuardedBy")
final class TimerWheel<K, V> implements Iterable<Node<K, V>> {

  /*
   * A timer wheel [1] stores timer events in buckets on a circular buffer. A bucket represents a
   * coarse time span, e.g. one minute, and holds a doubly-linked list of events. The wheels are
   * structured in a hierarchy (seconds, minutes, hours, days) so that events scheduled in the
   * distant future are cascaded to lower buckets when the wheels rotate. This allows for events
   * to be added, removed, and expired in O(1) time, where expiration occurs for the entire bucket,
   * and the penalty of cascading is amortized by the rotations.
   *
   * [1] Hashed and Hierarchical Timing Wheels
   * http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
   */

  static final int[] BUCKETS = { 64, 64, 32, 4, 1 };
  static final long[] SPANS = {
      ceilingPowerOfTwo(TimeUnit.SECONDS.toNanos(1)), // 1.07s
      ceilingPowerOfTwo(TimeUnit.MINUTES.toNanos(1)), // 1.14m
      ceilingPowerOfTwo(TimeUnit.HOURS.toNanos(1)),   // 1.22h
      ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)),    // 1.63d
      BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6.5d
      BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6.5d
  };
  static final long[] SHIFT = {
      Long.numberOfTrailingZeros(SPANS[0]),
      Long.numberOfTrailingZeros(SPANS[1]),
      Long.numberOfTrailingZeros(SPANS[2]),
      Long.numberOfTrailingZeros(SPANS[3]),
      Long.numberOfTrailingZeros(SPANS[4]),
  };

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

  long nanos;

  @SuppressWarnings({"rawtypes", "unchecked"})
  TimerWheel() {
    wheel = new Node[BUCKETS.length][];
    for (int i = 0; i < wheel.length; i++) {
      wheel[i] = new Node[BUCKETS[i]];
      for (int j = 0; j < wheel[i].length; j++) {
        wheel[i][j] = new Sentinel<>();
      }
    }
  }

  /**
   * Advances the timer and evicts entries that have expired.
   *
   * @param cache the instance that the entries belong to
   * @param currentTimeNanos the current time, in nanoseconds
   */
  public void advance(BoundedLocalCache<K, V> cache, @Var long currentTimeNanos) {
    @Var long previousTimeNanos = nanos;
    nanos = currentTimeNanos;

    // If wrapping then temporarily shift the clock for a positive comparison. We assume that the
    // advancements never exceed a total running time of Long.MAX_VALUE nanoseconds (292 years)
    // so that an overflow only occurs due to using an arbitrary origin time (System.nanoTime()).
    if ((previousTimeNanos < 0) && (currentTimeNanos > 0)) {
      previousTimeNanos += Long.MAX_VALUE;
      currentTimeNanos += Long.MAX_VALUE;
    }

    try {
      for (int i = 0; i < SHIFT.length; i++) {
        long previousTicks = (previousTimeNanos >>> SHIFT[i]);
        long currentTicks = (currentTimeNanos >>> SHIFT[i]);
        long delta = (currentTicks - previousTicks);
        if (delta <= 0L) {
          break;
        }
        expire(cache, i, previousTicks, delta);
      }
    } catch (Throwable t) {
      nanos = previousTimeNanos;
      throw t;
    }
  }

  /**
   * Expires entries or reschedules into the proper bucket if still active.
   *
   * @param cache the instance that the entries belong to
   * @param index the timing wheel being operated on
   * @param previousTicks the previous number of ticks
   * @param delta the number of additional ticks
   */
  @SuppressWarnings("Varifier")
  void expire(BoundedLocalCache<K, V> cache, int index, long previousTicks, long delta) {
    Node<K, V>[] timerWheel = wheel[index];
    int mask = timerWheel.length - 1;

    // We assume that the delta does not overflow an integer and cause negative steps. This can
    // occur only if the advancement exceeds 2^61 nanoseconds (73 years).
    int steps = Math.min(1 + (int) delta, timerWheel.length);
    int start = (int) (previousTicks & mask);
    int end = start + steps;

    for (int i = start; i < end; i++) {
      Node<K, V> sentinel = timerWheel[i & mask];
      Node<K, V> prev = sentinel.getPreviousInVariableOrder();
      @Var Node<K, V> node = sentinel.getNextInVariableOrder();
      sentinel.setPreviousInVariableOrder(sentinel);
      sentinel.setNextInVariableOrder(sentinel);

      while (node != sentinel) {
        Node<K, V> next = node.getNextInVariableOrder();
        node.setPreviousInVariableOrder(null);
        node.setNextInVariableOrder(null);

        try {
          if (((node.getVariableTime() - nanos) > 0)
              || !cache.evictEntry(node, RemovalCause.EXPIRED, nanos)) {
            schedule(node);
          }
          node = next;
        } catch (Throwable t) {
          node.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());
          node.setNextInVariableOrder(next);
          sentinel.getPreviousInVariableOrder().setNextInVariableOrder(node);
          sentinel.setPreviousInVariableOrder(prev);
          throw t;
        }
      }
    }
  }

  /**
   * Schedules a timer event for the node.
   *
   * @param node the entry in the cache
   */
  public void schedule(Node<K, V> node) {
    Node<K, V> sentinel = findBucket(node.getVariableTime());
    link(sentinel, node);
  }

  /**
   * Reschedules an active timer event for the node.
   *
   * @param node the entry in the cache
   */
  public void reschedule(Node<K, V> node) {
    if (node.getNextInVariableOrder() != null) {
      unlink(node);
      schedule(node);
    }
  }

  /**
   * Removes a timer event for this entry if present.
   *
   * @param node the entry in the cache
   */
  public void deschedule(Node<K, V> node) {
    unlink(node);
    node.setNextInVariableOrder(null);
    node.setPreviousInVariableOrder(null);
  }

  /**
   * Determines the bucket that the timer event should be added to.
   *
   * @param time the time when the event fires
   * @return the sentinel at the head of the bucket
   */
  @SuppressWarnings("Varifier")
  Node<K, V> findBucket(@Var long time) {
    long duration = Math.max(0L, time - nanos);
    if (duration == 0L) {
      time = nanos;
    }

    int length = wheel.length - 1;
    for (int i = 0; i < length; i++) {
      if (duration < SPANS[i + 1]) {
        long ticks = (time >>> SHIFT[i]);
        int index = (int) (ticks & (wheel[i].length - 1));
        return wheel[i][index];
      }
    }
    return wheel[length][0];
  }

  /** Adds the entry at the tail of the bucket's list. */
  void link(Node<K, V> sentinel, Node<K, V> node) {
    node.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());
    node.setNextInVariableOrder(sentinel);

    sentinel.getPreviousInVariableOrder().setNextInVariableOrder(node);
    sentinel.setPreviousInVariableOrder(node);
  }

  /** Removes the entry from its bucket, if scheduled. */
  void unlink(Node<K, V> node) {
    Node<K, V> next = node.getNextInVariableOrder();
    if (next != null) {
      Node<K, V> prev = node.getPreviousInVariableOrder();
      next.setPreviousInVariableOrder(prev);
      prev.setNextInVariableOrder(next);
    }
  }

  /** Returns the duration until the next bucket expires, or {@link Long#MAX_VALUE} if none. */
  @SuppressWarnings({"IntLongMath", "Varifier"})
  public long getExpirationDelay() {
    for (int i = 0; i < SHIFT.length; i++) {
      Node<K, V>[] timerWheel = wheel[i];
      long ticks = (nanos >>> SHIFT[i]);

      long spanMask = SPANS[i] - 1;
      int start = (int) (ticks & spanMask);
      int end = start + timerWheel.length;
      int mask = timerWheel.length - 1;
      for (int j = start; j < end; j++) {
        Node<K, V> sentinel = timerWheel[(j & mask)];
        Node<K, V> next = sentinel.getNextInVariableOrder();
        if (next == sentinel) {
          continue;
        }
        long buckets = (j - start);
        @Var long delay = (buckets << SHIFT[i]) - (nanos & spanMask);
        delay = (delay > 0) ? delay : SPANS[i];

        for (int k = i + 1; k < SHIFT.length; k++) {
          long nextDelay = peekAhead(k);
          delay = Math.min(delay, nextDelay);
        }

        return delay;
      }
    }
    return Long.MAX_VALUE;
  }

  /**
   * Returns the duration when the wheel's next bucket expires, or {@link Long#MAX_VALUE} if empty.
   *
   * @param index the timing wheel being operated on
   */
  @SuppressWarnings("Varifier")
  long peekAhead(int index) {
    long ticks = (nanos >>> SHIFT[index]);
    Node<K, V>[] timerWheel = wheel[index];

    long spanMask = SPANS[index] - 1;
    int mask = timerWheel.length - 1;
    int probe = (int) ((ticks + 1) & mask);
    Node<K, V> sentinel = timerWheel[probe];
    Node<K, V> next = sentinel.getNextInVariableOrder();
    return (next == sentinel) ? Long.MAX_VALUE : (SPANS[index] - (nanos & spanMask));
  }

  /**
   * Returns an iterator roughly ordered by the expiration time from the entries most likely to
   * expire (oldest) to the entries least likely to expire (youngest). The wheels are evaluated in
   * order, but the timers that fall within the bucket's range are not sorted.
   */
  @Override
  public Iterator<Node<K, V>> iterator() {
    return new AscendingIterator();
  }

  /**
   * Returns an iterator roughly ordered by the expiration time from the entries least likely to
   * expire (youngest) to the entries most likely to expire (oldest). The wheels are evaluated in
   * order, but the timers that fall within the bucket's range are not sorted.
   */
  public Iterator<Node<K, V>> descendingIterator() {
    return new DescendingIterator();
  }

  /** An iterator with rough ordering that can be specialized for either direction. */
  abstract class Traverser implements Iterator<Node<K, V>> {
    final long expectedNanos;

    @Nullable Node<K, V> current;
    @Nullable Node<K, V> next;

    Traverser() {
      expectedNanos = nanos;
    }

    @Override
    public boolean hasNext() {
      if (nanos != expectedNanos) {
        throw new ConcurrentModificationException();
      } else if (next != null) {
        return true;
      } else if (isDone()) {
        return false;
      }
      next = computeNext();
      return (next != null);
    }

    @Override
    public Node<K, V> next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      current = next;
      next = null;
      return requireNonNull(current);
    }

    @Nullable Node<K, V> computeNext() {
      @Var var node = (current == null) ? sentinel() : current;
      for (;;) {
        node = traverse(node);
        if (node != sentinel()) {
          return node;
        } else if ((node = goToNextBucket()) != null) {
          continue;
        } else if ((node = goToNextWheel()) != null) {
          continue;
        }
        return null;
      }
    }

    /** Returns if the iteration has completed. */
    abstract boolean isDone();

    /** Returns the sentinel at the current wheel and bucket position. */
    abstract Node<K, V> sentinel();

    /** Returns the node's successor, or the bucket's sentinel if at the end. */
    abstract Node<K, V> traverse(Node<K, V> node);

    /** Returns the sentinel for the wheel's next bucket, or null if the wheel is exhausted. */
    abstract @Nullable Node<K, V> goToNextBucket();

    /** Returns the sentinel for the next wheel's bucket position, or null if no more wheels. */
    abstract @Nullable Node<K, V> goToNextWheel();
  }

  final class AscendingIterator extends Traverser {
    int wheelIndex;
    int steps;

    @Override boolean isDone() {
      return (wheelIndex == wheel.length);
    }
    @Override Node<K, V> sentinel() {
      return wheel[wheelIndex][bucketIndex()];
    }
    @Override Node<K, V> traverse(Node<K, V> node) {
      return node.getNextInVariableOrder();
    }
    @Override @Nullable Node<K, V> goToNextBucket() {
      return (++steps < wheel[wheelIndex].length)
          ? wheel[wheelIndex][bucketIndex()]
          : null;
    }
    @Override @Nullable Node<K, V> goToNextWheel() {
      if (++wheelIndex == wheel.length) {
        return null;
      }
      steps = 0;
      return wheel[wheelIndex][bucketIndex()];
    }
    int bucketIndex() {
      @SuppressWarnings("Varifier")
      int ticks = (int) (nanos >>> SHIFT[wheelIndex]);
      int bucketMask = wheel[wheelIndex].length - 1;
      int bucketOffset = (ticks & bucketMask) + 1;
      return (bucketOffset + steps) & bucketMask;
    }
  }

  final class DescendingIterator extends Traverser {
    int wheelIndex;
    int steps;

    DescendingIterator() {
      wheelIndex = wheel.length - 1;
    }
    @Override boolean isDone() {
      return (wheelIndex == -1);
    }
    @Override Node<K, V> sentinel() {
      return wheel[wheelIndex][bucketIndex()];
    }
    @Override @Nullable Node<K, V> goToNextBucket() {
      return (++steps < wheel[wheelIndex].length)
          ? wheel[wheelIndex][bucketIndex()]
          : null;
    }
    @Override @Nullable Node<K, V> goToNextWheel() {
      if (--wheelIndex < 0) {
        return null;
      }
      steps = 0;
      return wheel[wheelIndex][bucketIndex()];
    }
    @Override Node<K, V> traverse(Node<K, V> node) {
      return node.getPreviousInVariableOrder();
    }
    int bucketIndex() {
      @SuppressWarnings("Varifier")
      int ticks = (int) (nanos >>> SHIFT[wheelIndex]);
      int bucketMask = wheel[wheelIndex].length - 1;
      int bucketOffset = (ticks & bucketMask);
      return (bucketOffset - steps) & bucketMask;
    }
  }

  /** A sentinel for the doubly-linked list in the bucket. */
  static final class Sentinel<K, V> extends Node<K, V> {
    Node<K, V> prev;
    Node<K, V> next;

    Sentinel() {
      prev = next = this;
    }

    @Override public Node<K, V> getPreviousInVariableOrder() {
      return prev;
    }
    @SuppressWarnings({"DataFlowIssue", "NullAway"})
    @Override public void setPreviousInVariableOrder(@Nullable Node<K, V> prev) {
      this.prev = prev;
    }
    @Override public Node<K, V> getNextInVariableOrder() {
      return next;
    }
    @SuppressWarnings({"DataFlowIssue", "NullAway"})
    @Override public void setNextInVariableOrder(@Nullable Node<K, V> next) {
      this.next = next;
    }

    @Override public @Nullable K getKey() { return null; }
    @Override public Object getKeyReference() { throw new UnsupportedOperationException(); }
    @Override public Object getKeyReferenceOrNull() { throw new UnsupportedOperationException(); }
    @Override public @Nullable V getValue() { return null; }
    @Override public Object getValueReference() { throw new UnsupportedOperationException(); }
    @Override public void setValue(V value, @Nullable ReferenceQueue<V> referenceQueue) {}
    @Override public boolean containsValue(Object value) { return false; }
    @Override public boolean isAlive() { return false; }
    @Override public boolean isRetired() { return false; }
    @Override public boolean isDead() { return false; }
    @Override public void retire() {}
    @Override public void die() {}
  }
}

1	/*
2	* Copyright 2017 Ben Manes. All Rights Reserved.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package com.github.benmanes.caffeine.cache;
17
18	import static com.github.benmanes.caffeine.cache.Caffeine.ceilingPowerOfTwo;
19	import static java.util.Objects.requireNonNull;
20
21	import java.lang.ref.ReferenceQueue;
22	import java.util.ConcurrentModificationException;
23	import java.util.Iterator;
24	import java.util.NoSuchElementException;
25	import java.util.concurrent.TimeUnit;
26
27	import org.jspecify.annotations.Nullable;
28
29	import com.google.errorprone.annotations.Var;
30
31	/**
32	* A hierarchical timer wheel to add, remove, and fire expiration events in amortized O(1) time. The
33	* expiration events are deferred until the timer is advanced, which is performed as part of the
34	* cache's maintenance cycle.
35	*
36	* @author ben.manes@gmail.com (Ben Manes)
37	*/
38	@SuppressWarnings("GuardedBy")
39	final class TimerWheel<K, V> implements Iterable<Node<K, V>> {
40
41	/*
42	* A timer wheel [1] stores timer events in buckets on a circular buffer. A bucket represents a
43	* coarse time span, e.g. one minute, and holds a doubly-linked list of events. The wheels are
44	* structured in a hierarchy (seconds, minutes, hours, days) so that events scheduled in the
45	* distant future are cascaded to lower buckets when the wheels rotate. This allows for events
46	* to be added, removed, and expired in O(1) time, where expiration occurs for the entire bucket,
47	* and the penalty of cascading is amortized by the rotations.
48	*
49	* [1] Hashed and Hierarchical Timing Wheels
50	* http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
51	*/
52
53	static final int[] BUCKETS = { 64, 64, 32, 4, 1 };	×
54	static final long[] SPANS = {	×
55	ceilingPowerOfTwo(TimeUnit.SECONDS.toNanos(1)), // 1.07s	×
56	ceilingPowerOfTwo(TimeUnit.MINUTES.toNanos(1)), // 1.14m	×
57	ceilingPowerOfTwo(TimeUnit.HOURS.toNanos(1)), // 1.22h	×
58	ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 1.63d	×
59	BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6.5d	×
60	BUCKETS[3] * ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 6.5d	×
61	};
62	static final long[] SHIFT = {	×
63	Long.numberOfTrailingZeros(SPANS[0]),	×
64	Long.numberOfTrailingZeros(SPANS[1]),	×
65	Long.numberOfTrailingZeros(SPANS[2]),	×
66	Long.numberOfTrailingZeros(SPANS[3]),	×
67	Long.numberOfTrailingZeros(SPANS[4]),	×
68	};
69
70	final Node<K, V>[][] wheel;
71
72	long nanos;
73
74	@SuppressWarnings({"rawtypes", "unchecked"})
75	TimerWheel() {	×
76	wheel = new Node[BUCKETS.length][];	×
77	for (int i = 0; i < wheel.length; i++) {	×
78	wheel[i] = new Node[BUCKETS[i]];	×
79	for (int j = 0; j < wheel[i].length; j++) {	×
80	wheel[i][j] = new Sentinel<>();	×
81	}
82	}
83	}	×
84
85	/**
86	* Advances the timer and evicts entries that have expired.
87	*
88	* @param cache the instance that the entries belong to
89	* @param currentTimeNanos the current time, in nanoseconds
90	*/
91	public void advance(BoundedLocalCache<K, V> cache, @Var long currentTimeNanos) {
92	@Var long previousTimeNanos = nanos;	×
93	nanos = currentTimeNanos;	×
94
95	// If wrapping then temporarily shift the clock for a positive comparison. We assume that the
96	// advancements never exceed a total running time of Long.MAX_VALUE nanoseconds (292 years)
97	// so that an overflow only occurs due to using an arbitrary origin time (System.nanoTime()).
98	if ((previousTimeNanos < 0) && (currentTimeNanos > 0)) {	×
99	previousTimeNanos += Long.MAX_VALUE;	×
100	currentTimeNanos += Long.MAX_VALUE;	×
101	}
102
103	try {
104	for (int i = 0; i < SHIFT.length; i++) {	×
105	long previousTicks = (previousTimeNanos >>> SHIFT[i]);	×
106	long currentTicks = (currentTimeNanos >>> SHIFT[i]);	×
107	long delta = (currentTicks - previousTicks);	×
108	if (delta <= 0L) {	×
109	break;	×
110	}
111	expire(cache, i, previousTicks, delta);	×
112	}
113	} catch (Throwable t) {	×
114	nanos = previousTimeNanos;	×
115	throw t;	×
116	}	×
117	}	×
118
119	/**
120	* Expires entries or reschedules into the proper bucket if still active.
121	*
122	* @param cache the instance that the entries belong to
123	* @param index the timing wheel being operated on
124	* @param previousTicks the previous number of ticks
125	* @param delta the number of additional ticks
126	*/
127	@SuppressWarnings("Varifier")
128	void expire(BoundedLocalCache<K, V> cache, int index, long previousTicks, long delta) {
129	Node<K, V>[] timerWheel = wheel[index];	×
130	int mask = timerWheel.length - 1;	×
131
132	// We assume that the delta does not overflow an integer and cause negative steps. This can
133	// occur only if the advancement exceeds 2^61 nanoseconds (73 years).
134	int steps = Math.min(1 + (int) delta, timerWheel.length);	×
135	int start = (int) (previousTicks & mask);	×
136	int end = start + steps;	×
137
138	for (int i = start; i < end; i++) {	×
139	Node<K, V> sentinel = timerWheel[i & mask];	×
140	Node<K, V> prev = sentinel.getPreviousInVariableOrder();	×
141	@Var Node<K, V> node = sentinel.getNextInVariableOrder();	×
142	sentinel.setPreviousInVariableOrder(sentinel);	×
143	sentinel.setNextInVariableOrder(sentinel);	×
144
145	while (node != sentinel) {	×
146	Node<K, V> next = node.getNextInVariableOrder();	×
147	node.setPreviousInVariableOrder(null);	×
148	node.setNextInVariableOrder(null);	×
149
150	try {
151	if (((node.getVariableTime() - nanos) > 0)	×
152	\|\| !cache.evictEntry(node, RemovalCause.EXPIRED, nanos)) {	×
153	schedule(node);	×
154	}
155	node = next;	×
156	} catch (Throwable t) {	×
157	node.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());	×
158	node.setNextInVariableOrder(next);	×
159	sentinel.getPreviousInVariableOrder().setNextInVariableOrder(node);	×
160	sentinel.setPreviousInVariableOrder(prev);	×
161	throw t;	×
162	}	×
163	}	×
164	}
165	}	×
166
167	/**
168	* Schedules a timer event for the node.
169	*
170	* @param node the entry in the cache
171	*/
172	public void schedule(Node<K, V> node) {
173	Node<K, V> sentinel = findBucket(node.getVariableTime());	×
174	link(sentinel, node);	×
175	}	×
176
177	/**
178	* Reschedules an active timer event for the node.
179	*
180	* @param node the entry in the cache
181	*/
182	public void reschedule(Node<K, V> node) {
183	if (node.getNextInVariableOrder() != null) {	×
184	unlink(node);	×
185	schedule(node);	×
186	}
187	}	×
188
189	/**
190	* Removes a timer event for this entry if present.
191	*
192	* @param node the entry in the cache
193	*/
194	public void deschedule(Node<K, V> node) {
195	unlink(node);	×
196	node.setNextInVariableOrder(null);	×
197	node.setPreviousInVariableOrder(null);	×
198	}	×
199
200	/**
201	* Determines the bucket that the timer event should be added to.
202	*
203	* @param time the time when the event fires
204	* @return the sentinel at the head of the bucket
205	*/
206	@SuppressWarnings("Varifier")
207	Node<K, V> findBucket(@Var long time) {
208	long duration = Math.max(0L, time - nanos);	×
209	if (duration == 0L) {	×
210	time = nanos;	×
211	}
212
213	int length = wheel.length - 1;	×
214	for (int i = 0; i < length; i++) {	×
215	if (duration < SPANS[i + 1]) {	×
216	long ticks = (time >>> SHIFT[i]);	×
217	int index = (int) (ticks & (wheel[i].length - 1));	×
218	return wheel[i][index];	×
219	}
220	}
221	return wheel[length][0];	×
222	}
223
224	/** Adds the entry at the tail of the bucket's list. */
225	void link(Node<K, V> sentinel, Node<K, V> node) {
226	node.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());	×
227	node.setNextInVariableOrder(sentinel);	×
228
229	sentinel.getPreviousInVariableOrder().setNextInVariableOrder(node);	×
230	sentinel.setPreviousInVariableOrder(node);	×
231	}	×
232
233	/** Removes the entry from its bucket, if scheduled. */
234	void unlink(Node<K, V> node) {
235	Node<K, V> next = node.getNextInVariableOrder();	×
236	if (next != null) {	×
237	Node<K, V> prev = node.getPreviousInVariableOrder();	×
238	next.setPreviousInVariableOrder(prev);	×
239	prev.setNextInVariableOrder(next);	×
240	}
241	}	×
242
243	/** Returns the duration until the next bucket expires, or {@link Long#MAX_VALUE} if none. */
244	@SuppressWarnings({"IntLongMath", "Varifier"})
245	public long getExpirationDelay() {
246	for (int i = 0; i < SHIFT.length; i++) {	×
247	Node<K, V>[] timerWheel = wheel[i];	×
248	long ticks = (nanos >>> SHIFT[i]);	×
249
250	long spanMask = SPANS[i] - 1;	×
251	int start = (int) (ticks & spanMask);	×
252	int end = start + timerWheel.length;	×
253	int mask = timerWheel.length - 1;	×
254	for (int j = start; j < end; j++) {	×
255	Node<K, V> sentinel = timerWheel[(j & mask)];	×
256	Node<K, V> next = sentinel.getNextInVariableOrder();	×
257	if (next == sentinel) {	×
258	continue;	×
259	}
260	long buckets = (j - start);	×
261	@Var long delay = (buckets << SHIFT[i]) - (nanos & spanMask);	×
262	delay = (delay > 0) ? delay : SPANS[i];	×
263
264	for (int k = i + 1; k < SHIFT.length; k++) {	×
265	long nextDelay = peekAhead(k);	×
266	delay = Math.min(delay, nextDelay);	×
267	}
268
269	return delay;	×
270	}
271	}
272	return Long.MAX_VALUE;	×
273	}
274
275	/**
276	* Returns the duration when the wheel's next bucket expires, or {@link Long#MAX_VALUE} if empty.
277	*
278	* @param index the timing wheel being operated on
279	*/
280	@SuppressWarnings("Varifier")
281	long peekAhead(int index) {
282	long ticks = (nanos >>> SHIFT[index]);	×
283	Node<K, V>[] timerWheel = wheel[index];	×
284
285	long spanMask = SPANS[index] - 1;	×
286	int mask = timerWheel.length - 1;	×
287	int probe = (int) ((ticks + 1) & mask);	×
288	Node<K, V> sentinel = timerWheel[probe];	×
289	Node<K, V> next = sentinel.getNextInVariableOrder();	×
290	return (next == sentinel) ? Long.MAX_VALUE : (SPANS[index] - (nanos & spanMask));	×
291	}
292
293	/**
294	* Returns an iterator roughly ordered by the expiration time from the entries most likely to
295	* expire (oldest) to the entries least likely to expire (youngest). The wheels are evaluated in
296	* order, but the timers that fall within the bucket's range are not sorted.
297	*/
298	@Override
299	public Iterator<Node<K, V>> iterator() {
300	return new AscendingIterator();	×
301	}
302
303	/**
304	* Returns an iterator roughly ordered by the expiration time from the entries least likely to
305	* expire (youngest) to the entries most likely to expire (oldest). The wheels are evaluated in
306	* order, but the timers that fall within the bucket's range are not sorted.
307	*/
308	public Iterator<Node<K, V>> descendingIterator() {
309	return new DescendingIterator();	×
310	}
311
312	/** An iterator with rough ordering that can be specialized for either direction. */
313	abstract class Traverser implements Iterator<Node<K, V>> {
314	final long expectedNanos;
315
316	@Nullable Node<K, V> current;
317	@Nullable Node<K, V> next;
318
319	Traverser() {	×
320	expectedNanos = nanos;	×
321	}	×
322
323	@Override
324	public boolean hasNext() {
325	if (nanos != expectedNanos) {	×
326	throw new ConcurrentModificationException();	×
327	} else if (next != null) {	×
328	return true;	×
329	} else if (isDone()) {	×
330	return false;	×
331	}
332	next = computeNext();	×
333	return (next != null);	×
334	}
335
336	@Override
337	public Node<K, V> next() {
338	if (!hasNext()) {	×
339	throw new NoSuchElementException();	×
340	}
341	current = next;	×
342	next = null;	×
343	return requireNonNull(current);	×
344	}
345
346	@Nullable Node<K, V> computeNext() {
347	@Var var node = (current == null) ? sentinel() : current;	×
348	for (;;) {
349	node = traverse(node);	×
350	if (node != sentinel()) {	×
351	return node;	×
352	} else if ((node = goToNextBucket()) != null) {	×
353	continue;	×
354	} else if ((node = goToNextWheel()) != null) {	×
355	continue;	×
356	}
357	return null;	×
358	}
359	}
360
361	/** Returns if the iteration has completed. */
362	abstract boolean isDone();
363
364	/** Returns the sentinel at the current wheel and bucket position. */
365	abstract Node<K, V> sentinel();
366
367	/** Returns the node's successor, or the bucket's sentinel if at the end. */
368	abstract Node<K, V> traverse(Node<K, V> node);
369
370	/** Returns the sentinel for the wheel's next bucket, or null if the wheel is exhausted. */
371	abstract @Nullable Node<K, V> goToNextBucket();
372
373	/** Returns the sentinel for the next wheel's bucket position, or null if no more wheels. */
374	abstract @Nullable Node<K, V> goToNextWheel();
375	}
376
377	final class AscendingIterator extends Traverser {	×
378	int wheelIndex;
379	int steps;
380
381	@Override boolean isDone() {
382	return (wheelIndex == wheel.length);	×
383	}
384	@Override Node<K, V> sentinel() {
385	return wheel[wheelIndex][bucketIndex()];	×
386	}
387	@Override Node<K, V> traverse(Node<K, V> node) {
388	return node.getNextInVariableOrder();	×
389	}
390	@Override @Nullable Node<K, V> goToNextBucket() {
391	return (++steps < wheel[wheelIndex].length)	×
392	? wheel[wheelIndex][bucketIndex()]	×
393	: null;	×
394	}
395	@Override @Nullable Node<K, V> goToNextWheel() {
396	if (++wheelIndex == wheel.length) {	×
397	return null;	×
398	}
399	steps = 0;	×
400	return wheel[wheelIndex][bucketIndex()];	×
401	}
402	int bucketIndex() {
403	@SuppressWarnings("Varifier")
404	int ticks = (int) (nanos >>> SHIFT[wheelIndex]);	×
405	int bucketMask = wheel[wheelIndex].length - 1;	×
406	int bucketOffset = (ticks & bucketMask) + 1;	×
407	return (bucketOffset + steps) & bucketMask;	×
408	}
409	}
410
411	final class DescendingIterator extends Traverser {
412	int wheelIndex;
413	int steps;
414
415	DescendingIterator() {	×
416	wheelIndex = wheel.length - 1;	×
417	}	×
418	@Override boolean isDone() {
419	return (wheelIndex == -1);	×
420	}
421	@Override Node<K, V> sentinel() {
422	return wheel[wheelIndex][bucketIndex()];	×
423	}
424	@Override @Nullable Node<K, V> goToNextBucket() {
425	return (++steps < wheel[wheelIndex].length)	×
426	? wheel[wheelIndex][bucketIndex()]	×
427	: null;	×
428	}
429	@Override @Nullable Node<K, V> goToNextWheel() {
430	if (--wheelIndex < 0) {	×
431	return null;	×
432	}
433	steps = 0;	×
434	return wheel[wheelIndex][bucketIndex()];	×
435	}
436	@Override Node<K, V> traverse(Node<K, V> node) {
437	return node.getPreviousInVariableOrder();	×
438	}
439	int bucketIndex() {
440	@SuppressWarnings("Varifier")
441	int ticks = (int) (nanos >>> SHIFT[wheelIndex]);	×
442	int bucketMask = wheel[wheelIndex].length - 1;	×
443	int bucketOffset = (ticks & bucketMask);	×
444	return (bucketOffset - steps) & bucketMask;	×
445	}
446	}
447
448	/** A sentinel for the doubly-linked list in the bucket. */
449	static final class Sentinel<K, V> extends Node<K, V> {
450	Node<K, V> prev;
451	Node<K, V> next;
452
453	Sentinel() {	×
454	prev = next = this;	×
455	}	×
456
457	@Override public Node<K, V> getPreviousInVariableOrder() {
458	return prev;	×
459	}
460	@SuppressWarnings({"DataFlowIssue", "NullAway"})
461	@Override public void setPreviousInVariableOrder(@Nullable Node<K, V> prev) {
462	this.prev = prev;	×
463	}	×
464	@Override public Node<K, V> getNextInVariableOrder() {
465	return next;	×
466	}
467	@SuppressWarnings({"DataFlowIssue", "NullAway"})
468	@Override public void setNextInVariableOrder(@Nullable Node<K, V> next) {
469	this.next = next;	×
470	}	×
471
472	@Override public @Nullable K getKey() { return null; }	×
473	@Override public Object getKeyReference() { throw new UnsupportedOperationException(); }	×
474	@Override public Object getKeyReferenceOrNull() { throw new UnsupportedOperationException(); }	×
475	@Override public @Nullable V getValue() { return null; }	×
476	@Override public Object getValueReference() { throw new UnsupportedOperationException(); }	×
477	@Override public void setValue(V value, @Nullable ReferenceQueue<V> referenceQueue) {}	×
478	@Override public boolean containsValue(Object value) { return false; }	×
479	@Override public boolean isAlive() { return false; }	×
480	@Override public boolean isRetired() { return false; }	×
481	@Override public boolean isDead() { return false; }	×
482	@Override public void retire() {}	×
483	@Override public void die() {}	×
484	}
485	}

ben-manes / caffeine / #5173

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous