#5612

Committed 11 Jul 2026 03:47PM UTC coverage: 71.292% (-28.7%) from 100.0%

Build # #5612

Build Type

push

github

Committed by

ben-manes

Commit Message

Preserve timestamps on a raced same-instance refresh

The automatic refreshIfNeeded path checked for an equal-value reload
before the ABA/ownership check and returned without preserving the
timestamps, so a reload completing after a concurrent put(k,
sameInstance) did a full update — shifting the entry's expiration
forward by the reload's in-flight duration and stomping the write.
Mirror the explicit-refresh fix: check ownership first. An owned
reload installs the value (refreshing metadata even for a same
instance), while a raced reload preserves the write's timestamps and
only notifies REPLACED when the value differs.

Coverage Stats

2957 of 4134 branches covered (71.53%)

3 of 3 new or added lines in 1 file covered. (100.0%)

2408 existing lines in 53 files now uncovered.

5980 of 8388 relevant lines covered (71.29%)

0.71 hits per line

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

97.24

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

/*
 * Copyright 2014 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 java.util.Objects.requireNonNull;

import java.util.AbstractCollection;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;

import org.jspecify.annotations.Nullable;

import com.google.errorprone.annotations.Var;

/**
 * This class provides a skeletal implementation of the {@link LinkedDeque} interface to minimize
 * the effort required to implement this interface.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 * @param <E> the type of elements held in this collection
 */
abstract class AbstractLinkedDeque<E> extends AbstractCollection<E> implements LinkedDeque<E> {

  // This class provides a doubly-linked list that is optimized for the virtual machine. The first
  // and last elements are manipulated instead of a slightly more convenient sentinel element to
  // avoid the insertion of null checks with NullPointerException throws in the byte code. The links
  // to a removed element are cleared to help a generational garbage collector if the discarded
  // elements inhabit more than one generation.

  /**
   * Pointer to first node.
   * Invariant: (first == null && last == null) ||
   *            (first.prev == null)
   */
  @Nullable E first;

  /**
   * Pointer to last node.
   * Invariant: (first == null && last == null) ||
   *            (last.next == null)
   */
  @Nullable E last;

  /**
   * The number of times this deque has been <i>structurally modified</i>. Structural modifications
   * are those that change the size of the deque, or otherwise perturb it in such a fashion that
   * iterations in progress may yield incorrect results.
   */
  int modCount;

  /**
   * Links the element to the front of the deque so that it becomes the first element.
   *
   * @param e the unlinked element
   */
  void linkFirst(E e) {
    E f = first;
    first = e;

    if (f == null) {
      last = e;
    } else {
      setPrevious(f, e);
      setNext(e, f);
    }
    modCount++;
  }

  /**
   * Links the element to the back of the deque so that it becomes the last element.
   *
   * @param e the unlinked element
   */
  void linkLast(E e) {
    E l = last;
    last = e;

    if (l == null) {
      first = e;
    } else {
      setNext(l, e);
      setPrevious(e, l);
    }
    modCount++;
  }

  /** Unlinks the non-null first element. */
  E unlinkFirst() {
    E f = requireNonNull(first);
    E next = getNext(f);
    setNext(f, null);

    first = next;
    if (next == null) {
      last = null;
    } else {
      setPrevious(next, null);
    }
    modCount++;
    return f;
  }

  /** Unlinks the non-null last element. */
  E unlinkLast() {
    E l = requireNonNull(last);
    E prev = getPrevious(l);
    setPrevious(l, null);
    last = prev;
    if (prev == null) {
      first = null;
    } else {
      setNext(prev, null);
    }
    modCount++;
    return l;
  }

  /** Unlinks the non-null element. */
  void unlink(E e) {
    E prev = getPrevious(e);
    E next = getNext(e);

    if (prev == null) {
      first = next;
    } else {
      setNext(prev, next);
      setPrevious(e, null);
    }

    if (next == null) {
      last = prev;
    } else {
      setPrevious(next, prev);
      setNext(e, null);
    }
    modCount++;
  }

  @Override
  public boolean isEmpty() {
    return (first == null);
  }

  void checkNotEmpty() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
  }

  /**
   * {@inheritDoc}
   * <p>
   * Beware that, unlike in most collections, this method is <em>NOT</em> a constant-time operation.
   */
  @Override
  public int size() {
    @Var int size = 0;
    for (E e = first; e != null; e = getNext(e)) {
      size++;
    }
    return size;
  }

  @Override
  public void clear() {
    @Var E e = first;
    while (e != null) {
      E next = getNext(e);
      setPrevious(e, null);
      setNext(e, null);
      e = next;
    }
    first = last = null;
    modCount++;
  }

  @Override
  public abstract boolean contains(Object o);

  @Override
  public boolean isFirst(@Nullable E e) {
    return (e != null) && (e == first);
  }

  @Override
  public boolean isLast(@Nullable E e) {
    return (e != null) && (e == last);
  }

  @Override
  public void moveToFront(E e) {
    if (e != first) {
      unlink(e);
      linkFirst(e);
    }
  }

  @Override
  public void moveToBack(E e) {
    if (e != last) {
      unlink(e);
      linkLast(e);
    }
  }

  @Override
  public @Nullable E peek() {
    return peekFirst();
  }

  @Override
  public @Nullable E peekFirst() {
    return first;
  }

  @Override
  public @Nullable E peekLast() {
    return last;
  }

  @Override
  public E getFirst() {
    checkNotEmpty();
    return requireNonNull(peekFirst());
  }

  @Override
  public E getLast() {
    checkNotEmpty();
    return requireNonNull(peekLast());
  }

  @Override
  public E element() {
    return getFirst();
  }

  @Override
  public boolean offer(E e) {
    return offerLast(e);
  }

  @Override
  public boolean offerFirst(E e) {
    requireNonNull(e);
    if (contains(e)) {
      return false;
    }
    linkFirst(e);
    return true;
  }

  @Override
  public boolean offerLast(E e) {
    requireNonNull(e);
    if (contains(e)) {
      return false;
    }
    linkLast(e);
    return true;
  }

  @Override
  public boolean add(E e) {
    return offerLast(e);
  }

  @Override
  public void addFirst(E e) {
    if (!offerFirst(e)) {
      throw new IllegalArgumentException();
    }
  }

  @Override
  public void addLast(E e) {
    if (!offerLast(e)) {
      throw new IllegalArgumentException();
    }
  }

  @Override
  public @Nullable E poll() {
    return pollFirst();
  }

  @Override
  public @Nullable E pollFirst() {
    return isEmpty() ? null : unlinkFirst();
  }

  @Override
  public @Nullable E pollLast() {
    return isEmpty() ? null : unlinkLast();
  }

  @Override
  public E remove() {
    return removeFirst();
  }

  @Override
  public E removeFirst() {
    checkNotEmpty();
    return requireNonNull(pollFirst());
  }

  @Override
  public abstract boolean remove(Object o);

  @Override
  @SuppressWarnings("DequeRemoveFirstOccurrence")
  public boolean removeFirstOccurrence(Object o) {
    return remove(o);
  }

  @Override
  public E removeLast() {
    checkNotEmpty();
    return requireNonNull(pollLast());
  }

  @Override
  @SuppressWarnings("DequeRemoveFirstOccurrence")
  public boolean removeLastOccurrence(Object o) {
    return remove(o);
  }

  @Override
  @SuppressWarnings("DequeRemoveFirstOccurrence")
  public boolean removeAll(Collection<?> c) {
    @Var boolean modified = false;
    for (Object o : c) {
      modified |= remove(o);
    }
    return modified;
  }

  @Override
  public void push(E e) {
    addFirst(e);
  }

  @Override
  public E pop() {
    return removeFirst();
  }

  @Override
  public PeekingIterator<E> iterator() {
    return new AbstractLinkedIterator(first) {
      @Override @Nullable E computeNext() {
        return getNext(requireNonNull(cursor));
      }
    };
  }

  @Override
  public PeekingIterator<E> descendingIterator() {
    return new AbstractLinkedIterator(last) {
      @Override @Nullable E computeNext() {
        return getPrevious(requireNonNull(cursor));
      }
    };
  }

  abstract class AbstractLinkedIterator implements PeekingIterator<E> {
    @Nullable E previous;
    @Nullable E cursor;

    int expectedModCount;

    /**
     * Creates an iterator that can traverse the deque.
     *
     * @param start the initial element to begin traversal from
     */
    AbstractLinkedIterator(@Nullable E start) {
      expectedModCount = modCount;
      cursor = start;
    }

    @Override
    public boolean hasNext() {
      checkForConcurrentModification();
      return (cursor != null);
    }

    @Override
    public @Nullable E peek() {
      return cursor;
    }

    @Override
    public E next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      previous = cursor;
      cursor = computeNext();
      return requireNonNull(previous);
    }

    /** Retrieves the next element to traverse to or {@code null} if there are no more elements. */
    abstract @Nullable E computeNext();

    @Override
    public void remove() {
      if (previous == null) {
        throw new IllegalStateException();
      }
      checkForConcurrentModification();

      AbstractLinkedDeque.this.unlink(previous);
      expectedModCount = modCount;
      previous = null;
    }

    /**
     * If the expected modCount value that the iterator believes that the backing deque should have
     * is violated then the iterator has detected concurrent modification.
     */
    void checkForConcurrentModification() {
      if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
      }
    }
  }
}

1	/*
2	* Copyright 2014 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 java.util.Objects.requireNonNull;
19
20	import java.util.AbstractCollection;
21	import java.util.Collection;
22	import java.util.ConcurrentModificationException;
23	import java.util.NoSuchElementException;
24
25	import org.jspecify.annotations.Nullable;
26
27	import com.google.errorprone.annotations.Var;
28
29	/**
30	* This class provides a skeletal implementation of the {@link LinkedDeque} interface to minimize
31	* the effort required to implement this interface.
32	*
33	* @author ben.manes@gmail.com (Ben Manes)
34	* @param <E> the type of elements held in this collection
35	*/
36	abstract class AbstractLinkedDeque<E> extends AbstractCollection<E> implements LinkedDeque<E> {	1✔
37
38	// This class provides a doubly-linked list that is optimized for the virtual machine. The first
39	// and last elements are manipulated instead of a slightly more convenient sentinel element to
40	// avoid the insertion of null checks with NullPointerException throws in the byte code. The links
41	// to a removed element are cleared to help a generational garbage collector if the discarded
42	// elements inhabit more than one generation.
43
44	/**
45	* Pointer to first node.
46	* Invariant: (first == null && last == null) \|\|
47	* (first.prev == null)
48	*/
49	@Nullable E first;
50
51	/**
52	* Pointer to last node.
53	* Invariant: (first == null && last == null) \|\|
54	* (last.next == null)
55	*/
56	@Nullable E last;
57
58	/**
59	* The number of times this deque has been <i>structurally modified</i>. Structural modifications
60	* are those that change the size of the deque, or otherwise perturb it in such a fashion that
61	* iterations in progress may yield incorrect results.
62	*/
63	int modCount;
64
65	/**
66	* Links the element to the front of the deque so that it becomes the first element.
67	*
68	* @param e the unlinked element
69	*/
70	void linkFirst(E e) {
71	E f = first;	1✔
72	first = e;	1✔
73
74	if (f == null) {	1✔
75	last = e;	1✔
76	} else {
77	setPrevious(f, e);	1✔
78	setNext(e, f);	1✔
79	}
80	modCount++;	1✔
81	}	1✔
82
83	/**
84	* Links the element to the back of the deque so that it becomes the last element.
85	*
86	* @param e the unlinked element
87	*/
88	void linkLast(E e) {
89	E l = last;	1✔
90	last = e;	1✔
91
92	if (l == null) {	1✔
93	first = e;	1✔
94	} else {
95	setNext(l, e);	1✔
96	setPrevious(e, l);	1✔
97	}
98	modCount++;	1✔
99	}	1✔
100
101	/** Unlinks the non-null first element. */
102	E unlinkFirst() {
103	E f = requireNonNull(first);	1✔
104	E next = getNext(f);	1✔
105	setNext(f, null);	1✔
106
107	first = next;	1✔
108	if (next == null) {	1✔
109	last = null;	1✔
110	} else {
111	setPrevious(next, null);	1✔
112	}
113	modCount++;	1✔
114	return f;	1✔
115	}
116
117	/** Unlinks the non-null last element. */
118	E unlinkLast() {
119	E l = requireNonNull(last);	1✔
120	E prev = getPrevious(l);	1✔
121	setPrevious(l, null);	1✔
122	last = prev;	1✔
123	if (prev == null) {	1✔
124	first = null;	1✔
125	} else {
126	setNext(prev, null);	1✔
127	}
128	modCount++;	1✔
129	return l;	1✔
130	}
131
132	/** Unlinks the non-null element. */
133	void unlink(E e) {
134	E prev = getPrevious(e);	1✔
135	E next = getNext(e);	1✔
136
137	if (prev == null) {	1✔
138	first = next;	1✔
139	} else {
140	setNext(prev, next);	1✔
141	setPrevious(e, null);	1✔
142	}
143
144	if (next == null) {	1✔
145	last = prev;	1✔
146	} else {
147	setPrevious(next, prev);	1✔
148	setNext(e, null);	1✔
149	}
150	modCount++;	1✔
151	}	1✔
152
153	@Override
154	public boolean isEmpty() {
155	return (first == null);	1✔
156	}
157
158	void checkNotEmpty() {
159	if (isEmpty()) {	1✔
160	throw new NoSuchElementException();	1✔
161	}
162	}	1✔
163
164	/**
165	* {@inheritDoc}
166	* <p>
167	* Beware that, unlike in most collections, this method is <em>NOT</em> a constant-time operation.
168	*/
169	@Override
170	public int size() {
171	@Var int size = 0;	1✔
172	for (E e = first; e != null; e = getNext(e)) {	1✔
173	size++;	1✔
174	}
175	return size;	1✔
176	}
177
178	@Override
179	public void clear() {
180	@Var E e = first;	1✔
181	while (e != null) {	1✔
182	E next = getNext(e);	1✔
183	setPrevious(e, null);	1✔
184	setNext(e, null);	1✔
185	e = next;	1✔
186	}	1✔
187	first = last = null;	1✔
188	modCount++;	1✔
189	}	1✔
190
191	@Override
192	public abstract boolean contains(Object o);
193
194	@Override
195	public boolean isFirst(@Nullable E e) {
UNCOV 196	return (e != null) && (e == first);	×
197	}
198
199	@Override
200	public boolean isLast(@Nullable E e) {
201	return (e != null) && (e == last);	1!
202	}
203
204	@Override
205	public void moveToFront(E e) {
206	if (e != first) {	1✔
207	unlink(e);	1✔
208	linkFirst(e);	1✔
209	}
210	}	1✔
211
212	@Override
213	public void moveToBack(E e) {
214	if (e != last) {	1✔
215	unlink(e);	1✔
216	linkLast(e);	1✔
217	}
218	}	1✔
219
220	@Override
221	public @Nullable E peek() {
222	return peekFirst();	1✔
223	}
224
225	@Override
226	public @Nullable E peekFirst() {
227	return first;	1✔
228	}
229
230	@Override
231	public @Nullable E peekLast() {
232	return last;	1✔
233	}
234
235	@Override
236	public E getFirst() {
237	checkNotEmpty();	1✔
238	return requireNonNull(peekFirst());	1✔
239	}
240
241	@Override
242	public E getLast() {
243	checkNotEmpty();	1✔
244	return requireNonNull(peekLast());	1✔
245	}
246
247	@Override
248	public E element() {
249	return getFirst();	1✔
250	}
251
252	@Override
253	public boolean offer(E e) {
254	return offerLast(e);	1✔
255	}
256
257	@Override
258	public boolean offerFirst(E e) {
259	requireNonNull(e);	1✔
260	if (contains(e)) {	1✔
261	return false;	1✔
262	}
263	linkFirst(e);	1✔
264	return true;	1✔
265	}
266
267	@Override
268	public boolean offerLast(E e) {
269	requireNonNull(e);	1✔
270	if (contains(e)) {	1✔
271	return false;	1✔
272	}
273	linkLast(e);	1✔
274	return true;	1✔
275	}
276
277	@Override
278	public boolean add(E e) {
279	return offerLast(e);	1✔
280	}
281
282	@Override
283	public void addFirst(E e) {
284	if (!offerFirst(e)) {	1✔
285	throw new IllegalArgumentException();	1✔
286	}
287	}	1✔
288
289	@Override
290	public void addLast(E e) {
291	if (!offerLast(e)) {	1!
UNCOV 292	throw new IllegalArgumentException();	×
293	}
294	}	1✔
295
296	@Override
297	public @Nullable E poll() {
UNCOV 298	return pollFirst();	×
299	}
300
301	@Override
302	public @Nullable E pollFirst() {
303	return isEmpty() ? null : unlinkFirst();	1✔
304	}
305
306	@Override
307	public @Nullable E pollLast() {
308	return isEmpty() ? null : unlinkLast();	1!
309	}
310
311	@Override
312	public E remove() {
313	return removeFirst();	1✔
314	}
315
316	@Override
317	public E removeFirst() {
318	checkNotEmpty();	1✔
319	return requireNonNull(pollFirst());	1✔
320	}
321
322	@Override
323	public abstract boolean remove(Object o);
324
325	@Override
326	@SuppressWarnings("DequeRemoveFirstOccurrence")
327	public boolean removeFirstOccurrence(Object o) {
328	return remove(o);	1✔
329	}
330
331	@Override
332	public E removeLast() {
333	checkNotEmpty();	1✔
334	return requireNonNull(pollLast());	1✔
335	}
336
337	@Override
338	@SuppressWarnings("DequeRemoveFirstOccurrence")
339	public boolean removeLastOccurrence(Object o) {
340	return remove(o);	1✔
341	}
342
343	@Override
344	@SuppressWarnings("DequeRemoveFirstOccurrence")
345	public boolean removeAll(Collection<?> c) {
346	@Var boolean modified = false;	1✔
347	for (Object o : c) {	1✔
348	modified \|= remove(o);	1✔
349	}	1✔
350	return modified;	1✔
351	}
352
353	@Override
354	public void push(E e) {
355	addFirst(e);	1✔
356	}	1✔
357
358	@Override
359	public E pop() {
360	return removeFirst();	1✔
361	}
362
363	@Override
364	public PeekingIterator<E> iterator() {
365	return new AbstractLinkedIterator(first) {	1✔
366	@Override @Nullable E computeNext() {
367	return getNext(requireNonNull(cursor));	1✔
368	}
369	};
370	}
371
372	@Override
373	public PeekingIterator<E> descendingIterator() {
374	return new AbstractLinkedIterator(last) {	1✔
375	@Override @Nullable E computeNext() {
376	return getPrevious(requireNonNull(cursor));	1✔
377	}
378	};
379	}
380
381	abstract class AbstractLinkedIterator implements PeekingIterator<E> {
382	@Nullable E previous;
383	@Nullable E cursor;
384
385	int expectedModCount;
386
387	/**
388	* Creates an iterator that can traverse the deque.
389	*
390	* @param start the initial element to begin traversal from
391	*/
392	AbstractLinkedIterator(@Nullable E start) {	1✔
393	expectedModCount = modCount;	1✔
394	cursor = start;	1✔
395	}	1✔
396
397	@Override
398	public boolean hasNext() {
399	checkForConcurrentModification();	1✔
400	return (cursor != null);	1✔
401	}
402
403	@Override
404	public @Nullable E peek() {
405	return cursor;	1✔
406	}
407
408	@Override
409	public E next() {
410	if (!hasNext()) {	1✔
411	throw new NoSuchElementException();	1✔
412	}
413	previous = cursor;	1✔
414	cursor = computeNext();	1✔
415	return requireNonNull(previous);	1✔
416	}
417
418	/** Retrieves the next element to traverse to or {@code null} if there are no more elements. */
419	abstract @Nullable E computeNext();
420
421	@Override
422	public void remove() {
423	if (previous == null) {	1!
UNCOV 424	throw new IllegalStateException();	×
425	}
426	checkForConcurrentModification();	1✔
427
428	AbstractLinkedDeque.this.unlink(previous);	1✔
429	expectedModCount = modCount;	1✔
430	previous = null;	1✔
431	}	1✔
432
433	/**
434	* If the expected modCount value that the iterator believes that the backing deque should have
435	* is violated then the iterator has detected concurrent modification.
436	*/
437	void checkForConcurrentModification() {
438	if (modCount != expectedModCount) {	1✔
439	throw new ConcurrentModificationException();	1✔
440	}
441	}	1✔
442	}
443	}

ben-manes / caffeine / #5612

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