#5707

Committed 02 Aug 2026 12:45AM UTC coverage: 0.106% (-99.9%) from 100.0%

Build # #5707

Build Type

push

github

Committed by

ben-manes

Commit Message

fix wikibench trace reader after overly strict audit fixes

Coverage Stats

0 of 4235 branches covered (0.0%)

9 of 8528 relevant lines covered (0.11%)

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.CanIgnoreReturnValue;
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
  };
  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;
  final Node<K, V> pending;

  boolean advancing;
  long nanos;

  @SuppressWarnings({"rawtypes", "unchecked"})
  TimerWheel() {
    pending = new Sentinel<>();
    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, up to the {@code limit} number of
   * evictions, and returns the unused budget. When the limit is reached the timer is rewound so
   * that the next advance processes the remaining backlog.
   *
   * @param cache the instance that the entries belong to
   * @param currentTimeNanos the current time, in nanoseconds
   * @param limit the maximum number of entries to evict
   * @return the unused portion of the eviction budget; zero if the limit was reached
   */
  @CanIgnoreReturnValue
  public int advance(BoundedLocalCache<K, V> cache, long currentTimeNanos, @Var int limit) {
    if (advancing) {
      return limit;
    }

    advancing = true;
    long previousTimeNanos = nanos;
    nanos = currentTimeNanos;

    // If wrapping from negative to non-negative then shift for the delta computation so that
    // the unsigned tick difference is correct. The raw previousTicks is used for the bucket
    // start to stay consistent with how schedule() places timers.
    @Var long previousDelta = previousTimeNanos;
    @Var long currentDelta = currentTimeNanos;
    if ((previousTimeNanos < 0) && (currentTimeNanos >= 0)) {
      previousDelta += Long.MIN_VALUE;
      currentDelta += Long.MIN_VALUE;
    }

    try {
      for (int i = 0; i < SHIFT.length; i++) {
        long delta = ((currentDelta >>> SHIFT[i]) - (previousDelta >>> SHIFT[i]));
        if (delta <= 0L) {
          break;
        }
        long previousTicks = (previousTimeNanos >>> SHIFT[i]);
        limit = expire(cache, i, previousTicks, delta, limit);
        if (limit == 0) {
          // The backlog was not fully drained, so rewind to process it on the next advance
          nanos = previousTimeNanos;
          break;
        }
      }
      return limit;
    } catch (Throwable t) {
      nanos = previousTimeNanos;
      throw t;
    } finally {
      advancing = false;
    }
  }

  /**
   * 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")
  int expire(BoundedLocalCache<K, V> cache, int index,
      long previousTicks, long delta, @Var int limit) {
    Node<K, V>[] timerWheel = wheel[index];
    int mask = timerWheel.length - 1;

    int steps = (int) Math.min(1 + 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];
      transfer(sentinel, pending);
      try {
        @Var Node<K, V> node;
        while ((node = pending.getNextInVariableOrder()) != pending) {
          deschedule(node);
          try {
            if ((node.getVariableTime() - nanos) > 0) {
              schedule(node);
            } else if (cache.evictEntry(node, RemovalCause.EXPIRED, nanos)) {
              if (--limit == 0) {
                // Leave the unprocessed remainder for the next advance to process
                return 0;
              }
            } else {
              schedule(node);
            }
          } catch (Throwable t) {
            link(pending, node);
            throw t;
          }
        }
      } finally {
        transfer(pending, sentinel);
      }
    }
    return limit;
  }

  /** Moves the entries held by one list to the tail of another. */
  void transfer(Node<K, V> from, Node<K, V> to) {
    Node<K, V> first = from.getNextInVariableOrder();
    if (first == from) {
      return;
    }
    Node<K, V> last = from.getPreviousInVariableOrder();
    from.setPreviousInVariableOrder(from);
    from.setNextInVariableOrder(from);

    first.setPreviousInVariableOrder(to.getPreviousInVariableOrder());
    to.getPreviousInVariableOrder().setNextInVariableOrder(first);
    last.setNextInVariableOrder(to);
    to.setPreviousInVariableOrder(last);
  }

  /**
   * 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 mask = timerWheel.length - 1;
      int start = (int) (ticks & mask);
      int end = start + timerWheel.length;
      for (int j = start; j < end; j++) {
        Node<K, V> sentinel = timerWheel[(j & mask)];
        Node<K, V> next = sentinel.getNextInVariableOrder();
        if (next == sentinel) {
          continue;
        }
        // an occupied current bucket is revisited when the wheel next ticks
        long buckets = Math.max(1, j - start);
        @Var long delay = (buckets << SHIFT[i]) - (nanos & spanMask);

        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;
    Node<K, V> current = timerWheel[(int) (ticks & mask)];
    Node<K, V> upcoming = timerWheel[(int) ((ticks + 1) & mask)];
    boolean empty = (current.getNextInVariableOrder() == current)
        && (upcoming.getNextInVariableOrder() == upcoming);
    return empty ? 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.CanIgnoreReturnValue;
30	import com.google.errorprone.annotations.Var;
31
32	/**
33	* A hierarchical timer wheel to add, remove, and fire expiration events in amortized O(1) time. The
34	* expiration events are deferred until the timer is advanced, which is performed as part of the
35	* cache's maintenance cycle.
36	*
37	* @author ben.manes@gmail.com (Ben Manes)
38	*/
39	@SuppressWarnings("GuardedBy")
40	final class TimerWheel<K, V> implements Iterable<Node<K, V>> {
41
42	/*
43	* A timer wheel [1] stores timer events in buckets on a circular buffer. A bucket represents a
44	* coarse time span, e.g. one minute, and holds a doubly-linked list of events. The wheels are
45	* structured in a hierarchy (seconds, minutes, hours, days) so that events scheduled in the
46	* distant future are cascaded to lower buckets when the wheels rotate. This allows for events
47	* to be added, removed, and expired in O(1) time, where expiration occurs for the entire bucket,
48	* and the penalty of cascading is amortized by the rotations.
49	*
50	* [1] Hashed and Hierarchical Timing Wheels
51	* http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf
52	*/
53
54	static final int[] BUCKETS = { 64, 64, 32, 4, 1 };	×
55	static final long[] SPANS = {	×
56	ceilingPowerOfTwo(TimeUnit.SECONDS.toNanos(1)), // 1.07s	×
57	ceilingPowerOfTwo(TimeUnit.MINUTES.toNanos(1)), // 1.14m	×
58	ceilingPowerOfTwo(TimeUnit.HOURS.toNanos(1)), // 1.22h	×
59	ceilingPowerOfTwo(TimeUnit.DAYS.toNanos(1)), // 1.63d	×
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	final Node<K, V> pending;
72
73	boolean advancing;
74	long nanos;
75
76	@SuppressWarnings({"rawtypes", "unchecked"})
77	TimerWheel() {	×
78	pending = new Sentinel<>();	×
79	wheel = new Node[BUCKETS.length][];	×
80	for (int i = 0; i < wheel.length; i++) {	×
81	wheel[i] = new Node[BUCKETS[i]];	×
82	for (int j = 0; j < wheel[i].length; j++) {	×
83	wheel[i][j] = new Sentinel<>();	×
84	}
85	}
86	}	×
87
88	/**
89	* Advances the timer and evicts entries that have expired, up to the {@code limit} number of
90	* evictions, and returns the unused budget. When the limit is reached the timer is rewound so
91	* that the next advance processes the remaining backlog.
92	*
93	* @param cache the instance that the entries belong to
94	* @param currentTimeNanos the current time, in nanoseconds
95	* @param limit the maximum number of entries to evict
96	* @return the unused portion of the eviction budget; zero if the limit was reached
97	*/
98	@CanIgnoreReturnValue
99	public int advance(BoundedLocalCache<K, V> cache, long currentTimeNanos, @Var int limit) {
100	if (advancing) {	×
101	return limit;	×
102	}
103
104	advancing = true;	×
105	long previousTimeNanos = nanos;	×
106	nanos = currentTimeNanos;	×
107
108	// If wrapping from negative to non-negative then shift for the delta computation so that
109	// the unsigned tick difference is correct. The raw previousTicks is used for the bucket
110	// start to stay consistent with how schedule() places timers.
111	@Var long previousDelta = previousTimeNanos;	×
112	@Var long currentDelta = currentTimeNanos;	×
113	if ((previousTimeNanos < 0) && (currentTimeNanos >= 0)) {	×
114	previousDelta += Long.MIN_VALUE;	×
115	currentDelta += Long.MIN_VALUE;	×
116	}
117
118	try {
119	for (int i = 0; i < SHIFT.length; i++) {	×
120	long delta = ((currentDelta >>> SHIFT[i]) - (previousDelta >>> SHIFT[i]));	×
121	if (delta <= 0L) {	×
122	break;	×
123	}
124	long previousTicks = (previousTimeNanos >>> SHIFT[i]);	×
125	limit = expire(cache, i, previousTicks, delta, limit);	×
126	if (limit == 0) {	×
127	// The backlog was not fully drained, so rewind to process it on the next advance
128	nanos = previousTimeNanos;	×
129	break;	×
130	}
131	}
132	return limit;	×
133	} catch (Throwable t) {	×
134	nanos = previousTimeNanos;	×
135	throw t;	×
136	} finally {
137	advancing = false;	×
138	}
139	}
140
141	/**
142	* Expires entries or reschedules into the proper bucket if still active.
143	*
144	* @param cache the instance that the entries belong to
145	* @param index the timing wheel being operated on
146	* @param previousTicks the previous number of ticks
147	* @param delta the number of additional ticks
148	*/
149	@SuppressWarnings("Varifier")
150	int expire(BoundedLocalCache<K, V> cache, int index,
151	long previousTicks, long delta, @Var int limit) {
152	Node<K, V>[] timerWheel = wheel[index];	×
153	int mask = timerWheel.length - 1;	×
154
155	int steps = (int) Math.min(1 + delta, timerWheel.length);	×
156	int start = (int) (previousTicks & mask);	×
157	int end = start + steps;	×
158
159	for (int i = start; i < end; i++) {	×
160	Node<K, V> sentinel = timerWheel[i & mask];	×
161	transfer(sentinel, pending);	×
162	try {
163	@Var Node<K, V> node;
164	while ((node = pending.getNextInVariableOrder()) != pending) {	×
165	deschedule(node);	×
166	try {
167	if ((node.getVariableTime() - nanos) > 0) {	×
168	schedule(node);	×
169	} else if (cache.evictEntry(node, RemovalCause.EXPIRED, nanos)) {	×
170	if (--limit == 0) {	×
171	// Leave the unprocessed remainder for the next advance to process
172	return 0;	×
173	}
174	} else {
175	schedule(node);	×
176	}
177	} catch (Throwable t) {	×
178	link(pending, node);	×
179	throw t;	×
180	}	×
181	}
182	} finally {
183	transfer(pending, sentinel);	×
184	}
185	}
186	return limit;	×
187	}
188
189	/** Moves the entries held by one list to the tail of another. */
190	void transfer(Node<K, V> from, Node<K, V> to) {
191	Node<K, V> first = from.getNextInVariableOrder();	×
192	if (first == from) {	×
193	return;	×
194	}
195	Node<K, V> last = from.getPreviousInVariableOrder();	×
196	from.setPreviousInVariableOrder(from);	×
197	from.setNextInVariableOrder(from);	×
198
199	first.setPreviousInVariableOrder(to.getPreviousInVariableOrder());	×
200	to.getPreviousInVariableOrder().setNextInVariableOrder(first);	×
201	last.setNextInVariableOrder(to);	×
202	to.setPreviousInVariableOrder(last);	×
203	}	×
204
205	/**
206	* Schedules a timer event for the node.
207	*
208	* @param node the entry in the cache
209	*/
210	public void schedule(Node<K, V> node) {
211	Node<K, V> sentinel = findBucket(node.getVariableTime());	×
212	link(sentinel, node);	×
213	}	×
214
215	/**
216	* Reschedules an active timer event for the node.
217	*
218	* @param node the entry in the cache
219	*/
220	public void reschedule(Node<K, V> node) {
221	if (node.getNextInVariableOrder() != null) {	×
222	unlink(node);	×
223	schedule(node);	×
224	}
225	}	×
226
227	/**
228	* Removes a timer event for this entry if present.
229	*
230	* @param node the entry in the cache
231	*/
232	public void deschedule(Node<K, V> node) {
233	unlink(node);	×
234	node.setNextInVariableOrder(null);	×
235	node.setPreviousInVariableOrder(null);	×
236	}	×
237
238	/**
239	* Determines the bucket that the timer event should be added to.
240	*
241	* @param time the time when the event fires
242	* @return the sentinel at the head of the bucket
243	*/
244	@SuppressWarnings("Varifier")
245	Node<K, V> findBucket(@Var long time) {
246	long duration = Math.max(0L, time - nanos);	×
247	if (duration == 0L) {	×
248	time = nanos;	×
249	}
250
251	int length = wheel.length - 1;	×
252	for (int i = 0; i < length; i++) {	×
253	if (duration < SPANS[i + 1]) {	×
254	long ticks = (time >>> SHIFT[i]);	×
255	int index = (int) (ticks & (wheel[i].length - 1));	×
256	return wheel[i][index];	×
257	}
258	}
259	return wheel[length][0];	×
260	}
261
262	/** Adds the entry at the tail of the bucket's list. */
263	void link(Node<K, V> sentinel, Node<K, V> node) {
264	node.setPreviousInVariableOrder(sentinel.getPreviousInVariableOrder());	×
265	node.setNextInVariableOrder(sentinel);	×
266
267	sentinel.getPreviousInVariableOrder().setNextInVariableOrder(node);	×
268	sentinel.setPreviousInVariableOrder(node);	×
269	}	×
270
271	/** Removes the entry from its bucket, if scheduled. */
272	void unlink(Node<K, V> node) {
273	Node<K, V> next = node.getNextInVariableOrder();	×
274	if (next != null) {	×
275	Node<K, V> prev = node.getPreviousInVariableOrder();	×
276	next.setPreviousInVariableOrder(prev);	×
277	prev.setNextInVariableOrder(next);	×
278	}
279	}	×
280
281	/** Returns the duration until the next bucket expires, or {@link Long#MAX_VALUE} if none. */
282	@SuppressWarnings({"IntLongMath", "Varifier"})
283	public long getExpirationDelay() {
284	for (int i = 0; i < SHIFT.length; i++) {	×
285	Node<K, V>[] timerWheel = wheel[i];	×
286	long ticks = (nanos >>> SHIFT[i]);	×
287
288	long spanMask = SPANS[i] - 1;	×
289	int mask = timerWheel.length - 1;	×
290	int start = (int) (ticks & mask);	×
291	int end = start + timerWheel.length;	×
292	for (int j = start; j < end; j++) {	×
293	Node<K, V> sentinel = timerWheel[(j & mask)];	×
294	Node<K, V> next = sentinel.getNextInVariableOrder();	×
295	if (next == sentinel) {	×
296	continue;	×
297	}
298	// an occupied current bucket is revisited when the wheel next ticks
299	long buckets = Math.max(1, j - start);	×
300	@Var long delay = (buckets << SHIFT[i]) - (nanos & spanMask);	×
301
302	for (int k = i + 1; k < SHIFT.length; k++) {	×
303	long nextDelay = peekAhead(k);	×
304	delay = Math.min(delay, nextDelay);	×
305	}
306
307	return delay;	×
308	}
309	}
310	return Long.MAX_VALUE;	×
311	}
312
313	/**
314	* Returns the duration when the wheel's next bucket expires, or {@link Long#MAX_VALUE} if empty.
315	*
316	* @param index the timing wheel being operated on
317	*/
318	@SuppressWarnings("Varifier")
319	long peekAhead(int index) {
320	long ticks = (nanos >>> SHIFT[index]);	×
321	Node<K, V>[] timerWheel = wheel[index];	×
322
323	long spanMask = SPANS[index] - 1;	×
324	int mask = timerWheel.length - 1;	×
325	Node<K, V> current = timerWheel[(int) (ticks & mask)];	×
326	Node<K, V> upcoming = timerWheel[(int) ((ticks + 1) & mask)];	×
327	boolean empty = (current.getNextInVariableOrder() == current)	×
328	&& (upcoming.getNextInVariableOrder() == upcoming);	×
329	return empty ? Long.MAX_VALUE : (SPANS[index] - (nanos & spanMask));	×
330	}
331
332	/**
333	* Returns an iterator roughly ordered by the expiration time from the entries most likely to
334	* expire (oldest) to the entries least likely to expire (youngest). The wheels are evaluated in
335	* order, but the timers that fall within the bucket's range are not sorted.
336	*/
337	@Override
338	public Iterator<Node<K, V>> iterator() {
339	return new AscendingIterator();	×
340	}
341
342	/**
343	* Returns an iterator roughly ordered by the expiration time from the entries least likely to
344	* expire (youngest) to the entries most likely to expire (oldest). The wheels are evaluated in
345	* order, but the timers that fall within the bucket's range are not sorted.
346	*/
347	public Iterator<Node<K, V>> descendingIterator() {
348	return new DescendingIterator();	×
349	}
350
351	/** An iterator with rough ordering that can be specialized for either direction. */
352	abstract class Traverser implements Iterator<Node<K, V>> {
353	final long expectedNanos;
354
355	@Nullable Node<K, V> current;
356	@Nullable Node<K, V> next;
357
358	Traverser() {	×
359	expectedNanos = nanos;	×
360	}	×
361
362	@Override
363	public boolean hasNext() {
364	if (nanos != expectedNanos) {	×
365	throw new ConcurrentModificationException();	×
366	} else if (next != null) {	×
367	return true;	×
368	} else if (isDone()) {	×
369	return false;	×
370	}
371	next = computeNext();	×
372	return (next != null);	×
373	}
374
375	@Override
376	public Node<K, V> next() {
377	if (!hasNext()) {	×
378	throw new NoSuchElementException();	×
379	}
380	current = next;	×
381	next = null;	×
382	return requireNonNull(current);	×
383	}
384
385	@Nullable Node<K, V> computeNext() {
386	@Var var node = (current == null) ? sentinel() : current;	×
387	for (;;) {
388	node = traverse(node);	×
389	if (node != sentinel()) {	×
390	return node;	×
391	} else if ((node = goToNextBucket()) != null) {	×
392	continue;	×
393	} else if ((node = goToNextWheel()) != null) {	×
394	continue;	×
395	}
396	return null;	×
397	}
398	}
399
400	/** Returns if the iteration has completed. */
401	abstract boolean isDone();
402
403	/** Returns the sentinel at the current wheel and bucket position. */
404	abstract Node<K, V> sentinel();
405
406	/** Returns the node's successor, or the bucket's sentinel if at the end. */
407	abstract Node<K, V> traverse(Node<K, V> node);
408
409	/** Returns the sentinel for the wheel's next bucket, or null if the wheel is exhausted. */
410	abstract @Nullable Node<K, V> goToNextBucket();
411
412	/** Returns the sentinel for the next wheel's bucket position, or null if no more wheels. */
413	abstract @Nullable Node<K, V> goToNextWheel();
414	}
415
416	final class AscendingIterator extends Traverser {	×
417	int wheelIndex;
418	int steps;
419
420	@Override boolean isDone() {
421	return (wheelIndex == wheel.length);	×
422	}
423	@Override Node<K, V> sentinel() {
424	return wheel[wheelIndex][bucketIndex()];	×
425	}
426	@Override Node<K, V> traverse(Node<K, V> node) {
427	return node.getNextInVariableOrder();	×
428	}
429	@Override @Nullable Node<K, V> goToNextBucket() {
430	return (++steps < wheel[wheelIndex].length)	×
431	? wheel[wheelIndex][bucketIndex()]	×
432	: null;	×
433	}
434	@Override @Nullable Node<K, V> goToNextWheel() {
435	if (++wheelIndex == wheel.length) {	×
436	return null;	×
437	}
438	steps = 0;	×
439	return wheel[wheelIndex][bucketIndex()];	×
440	}
441	int bucketIndex() {
442	@SuppressWarnings("Varifier")
443	int ticks = (int) (nanos >>> SHIFT[wheelIndex]);	×
444	int bucketMask = wheel[wheelIndex].length - 1;	×
445	int bucketOffset = (ticks & bucketMask) + 1;	×
446	return (bucketOffset + steps) & bucketMask;	×
447	}
448	}
449
450	final class DescendingIterator extends Traverser {
451	int wheelIndex;
452	int steps;
453
454	DescendingIterator() {	×
455	wheelIndex = wheel.length - 1;	×
456	}	×
457	@Override boolean isDone() {
458	return (wheelIndex == -1);	×
459	}
460	@Override Node<K, V> sentinel() {
461	return wheel[wheelIndex][bucketIndex()];	×
462	}
463	@Override @Nullable Node<K, V> goToNextBucket() {
464	return (++steps < wheel[wheelIndex].length)	×
465	? wheel[wheelIndex][bucketIndex()]	×
466	: null;	×
467	}
468	@Override @Nullable Node<K, V> goToNextWheel() {
469	if (--wheelIndex < 0) {	×
470	return null;	×
471	}
472	steps = 0;	×
473	return wheel[wheelIndex][bucketIndex()];	×
474	}
475	@Override Node<K, V> traverse(Node<K, V> node) {
476	return node.getPreviousInVariableOrder();	×
477	}
478	int bucketIndex() {
479	@SuppressWarnings("Varifier")
480	int ticks = (int) (nanos >>> SHIFT[wheelIndex]);	×
481	int bucketMask = wheel[wheelIndex].length - 1;	×
482	int bucketOffset = (ticks & bucketMask);	×
483	return (bucketOffset - steps) & bucketMask;	×
484	}
485	}
486
487	/** A sentinel for the doubly-linked list in the bucket. */
488	static final class Sentinel<K, V> extends Node<K, V> {
489	Node<K, V> prev;
490	Node<K, V> next;
491
492	Sentinel() {	×
493	prev = next = this;	×
494	}	×
495
496	@Override public Node<K, V> getPreviousInVariableOrder() {
497	return prev;	×
498	}
499	@SuppressWarnings({"DataFlowIssue", "NullAway"})
500	@Override public void setPreviousInVariableOrder(@Nullable Node<K, V> prev) {
501	this.prev = prev;	×
502	}	×
503	@Override public Node<K, V> getNextInVariableOrder() {
504	return next;	×
505	}
506	@SuppressWarnings({"DataFlowIssue", "NullAway"})
507	@Override public void setNextInVariableOrder(@Nullable Node<K, V> next) {
508	this.next = next;	×
509	}	×
510
511	@Override public @Nullable K getKey() { return null; }	×
512	@Override public Object getKeyReference() { throw new UnsupportedOperationException(); }	×
513	@Override public Object getKeyReferenceOrNull() { throw new UnsupportedOperationException(); }	×
514	@Override public @Nullable V getValue() { return null; }	×
515	@Override public Object getValueReference() { throw new UnsupportedOperationException(); }	×
516	@Override public void setValue(V value, @Nullable ReferenceQueue<V> referenceQueue) {}	×
517	@Override public boolean containsValue(Object value) { return false; }	×
518	@Override public boolean isAlive() { return false; }	×
519	@Override public boolean isRetired() { return false; }	×
520	@Override public boolean isDead() { return false; }	×
521	@Override public void retire() {}	×
522	@Override public void die() {}	×
523	}
524	}

ben-manes / caffeine / #5707

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