#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/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
  public boolean removeFirstOccurrence(Object o) {
    return remove(o);
  }

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

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

  @Override
  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.remove(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> {	×
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;	×
72	first = e;	×
73
74	if (f == null) {	×
75	last = e;	×
76	} else {
77	setPrevious(f, e);	×
78	setNext(e, f);	×
79	}
80	modCount++;	×
81	}	×
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;	×
90	last = e;	×
91
92	if (l == null) {	×
93	first = e;	×
94	} else {
95	setNext(l, e);	×
96	setPrevious(e, l);	×
97	}
98	modCount++;	×
99	}	×
100
101	/** Unlinks the non-null first element. */
102	E unlinkFirst() {
103	E f = requireNonNull(first);	×
104	E next = getNext(f);	×
105	setNext(f, null);	×
106
107	first = next;	×
108	if (next == null) {	×
109	last = null;	×
110	} else {
111	setPrevious(next, null);	×
112	}
113	modCount++;	×
114	return f;	×
115	}
116
117	/** Unlinks the non-null last element. */
118	E unlinkLast() {
119	E l = requireNonNull(last);	×
120	E prev = getPrevious(l);	×
121	setPrevious(l, null);	×
122	last = prev;	×
123	if (prev == null) {	×
124	first = null;	×
125	} else {
126	setNext(prev, null);	×
127	}
128	modCount++;	×
129	return l;	×
130	}
131
132	/** Unlinks the non-null element. */
133	void unlink(E e) {
134	E prev = getPrevious(e);	×
135	E next = getNext(e);	×
136
137	if (prev == null) {	×
138	first = next;	×
139	} else {
140	setNext(prev, next);	×
141	setPrevious(e, null);	×
142	}
143
144	if (next == null) {	×
145	last = prev;	×
146	} else {
147	setPrevious(next, prev);	×
148	setNext(e, null);	×
149	}
150	modCount++;	×
151	}	×
152
153	@Override
154	public boolean isEmpty() {
155	return (first == null);	×
156	}
157
158	void checkNotEmpty() {
159	if (isEmpty()) {	×
160	throw new NoSuchElementException();	×
161	}
162	}	×
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;	×
172	for (E e = first; e != null; e = getNext(e)) {	×
173	size++;	×
174	}
175	return size;	×
176	}
177
178	@Override
179	public void clear() {
180	@Var E e = first;	×
181	while (e != null) {	×
182	E next = getNext(e);	×
183	setPrevious(e, null);	×
184	setNext(e, null);	×
185	e = next;	×
186	}	×
187	first = last = null;	×
188	modCount++;	×
189	}	×
190
191	@Override
192	public abstract boolean contains(Object o);
193
194	@Override
195	public boolean isFirst(@Nullable E e) {
196	return (e != null) && (e == first);	×
197	}
198
199	@Override
200	public boolean isLast(@Nullable E e) {
201	return (e != null) && (e == last);	×
202	}
203
204	@Override
205	public void moveToFront(E e) {
206	if (e != first) {	×
207	unlink(e);	×
208	linkFirst(e);	×
209	}
210	}	×
211
212	@Override
213	public void moveToBack(E e) {
214	if (e != last) {	×
215	unlink(e);	×
216	linkLast(e);	×
217	}
218	}	×
219
220	@Override
221	public @Nullable E peek() {
222	return peekFirst();	×
223	}
224
225	@Override
226	public @Nullable E peekFirst() {
227	return first;	×
228	}
229
230	@Override
231	public @Nullable E peekLast() {
232	return last;	×
233	}
234
235	@Override
236	public E getFirst() {
237	checkNotEmpty();	×
238	return requireNonNull(peekFirst());	×
239	}
240
241	@Override
242	public E getLast() {
243	checkNotEmpty();	×
244	return requireNonNull(peekLast());	×
245	}
246
247	@Override
248	public E element() {
249	return getFirst();	×
250	}
251
252	@Override
253	public boolean offer(E e) {
254	return offerLast(e);	×
255	}
256
257	@Override
258	public boolean offerFirst(E e) {
259	requireNonNull(e);	×
260	if (contains(e)) {	×
261	return false;	×
262	}
263	linkFirst(e);	×
264	return true;	×
265	}
266
267	@Override
268	public boolean offerLast(E e) {
269	requireNonNull(e);	×
270	if (contains(e)) {	×
271	return false;	×
272	}
273	linkLast(e);	×
274	return true;	×
275	}
276
277	@Override
278	public boolean add(E e) {
279	return offerLast(e);	×
280	}
281
282	@Override
283	public void addFirst(E e) {
284	if (!offerFirst(e)) {	×
285	throw new IllegalArgumentException();	×
286	}
287	}	×
288
289	@Override
290	public void addLast(E e) {
291	if (!offerLast(e)) {	×
292	throw new IllegalArgumentException();	×
293	}
294	}	×
295
296	@Override
297	public @Nullable E poll() {
298	return pollFirst();	×
299	}
300
301	@Override
302	public @Nullable E pollFirst() {
303	return isEmpty() ? null : unlinkFirst();	×
304	}
305
306	@Override
307	public @Nullable E pollLast() {
308	return isEmpty() ? null : unlinkLast();	×
309	}
310
311	@Override
312	public E remove() {
313	return removeFirst();	×
314	}
315
316	@Override
317	public E removeFirst() {
318	checkNotEmpty();	×
319	return requireNonNull(pollFirst());	×
320	}
321
322	@Override
323	public abstract boolean remove(Object o);
324
325	@Override
326	public boolean removeFirstOccurrence(Object o) {
327	return remove(o);	×
328	}
329
330	@Override
331	public E removeLast() {
332	checkNotEmpty();	×
333	return requireNonNull(pollLast());	×
334	}
335
336	@Override
337	public boolean removeLastOccurrence(Object o) {
338	return remove(o);	×
339	}
340
341	@Override
342	public boolean removeAll(Collection<?> c) {
343	@Var boolean modified = false;	×
344	for (Object o : c) {	×
345	modified \|= remove(o);	×
346	}	×
347	return modified;	×
348	}
349
350	@Override
351	public void push(E e) {
352	addFirst(e);	×
353	}	×
354
355	@Override
356	public E pop() {
357	return removeFirst();	×
358	}
359
360	@Override
361	public PeekingIterator<E> iterator() {
362	return new AbstractLinkedIterator(first) {	×
363	@Override @Nullable E computeNext() {
364	return getNext(requireNonNull(cursor));	×
365	}
366	};
367	}
368
369	@Override
370	public PeekingIterator<E> descendingIterator() {
371	return new AbstractLinkedIterator(last) {	×
372	@Override @Nullable E computeNext() {
373	return getPrevious(requireNonNull(cursor));	×
374	}
375	};
376	}
377
378	abstract class AbstractLinkedIterator implements PeekingIterator<E> {
379	@Nullable E previous;
380	@Nullable E cursor;
381
382	int expectedModCount;
383
384	/**
385	* Creates an iterator that can traverse the deque.
386	*
387	* @param start the initial element to begin traversal from
388	*/
389	AbstractLinkedIterator(@Nullable E start) {	×
390	expectedModCount = modCount;	×
391	cursor = start;	×
392	}	×
393
394	@Override
395	public boolean hasNext() {
396	checkForConcurrentModification();	×
397	return (cursor != null);	×
398	}
399
400	@Override
401	public @Nullable E peek() {
402	return cursor;	×
403	}
404
405	@Override
406	public E next() {
407	if (!hasNext()) {	×
408	throw new NoSuchElementException();	×
409	}
410	previous = cursor;	×
411	cursor = computeNext();	×
412	return requireNonNull(previous);	×
413	}
414
415	/** Retrieves the next element to traverse to or {@code null} if there are no more elements. */
416	abstract @Nullable E computeNext();
417
418	@Override
419	public void remove() {
420	if (previous == null) {	×
421	throw new IllegalStateException();	×
422	}
423	checkForConcurrentModification();	×
424
425	AbstractLinkedDeque.this.remove(previous);	×
426	expectedModCount = modCount;	×
427	previous = null;	×
428	}	×
429
430	/**
431	* If the expected modCount value that the iterator believes that the backing deque should have
432	* is violated then the iterator has detected concurrent modification.
433	*/
434	void checkForConcurrentModification() {
435	if (modCount != expectedModCount) {	×
436	throw new ConcurrentModificationException();	×
437	}
438	}	×
439	}
440	}

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