WeakAssQueue allows you to let the GC remove the tail (ass) of this queue automatically.
/* | |
* Licence: | |
* | |
* Feel free to use this however you want with the following limitations. | |
* Don't change this licence here and don't remove it either. | |
* | |
* You can add it to your own namespace and alter the code as you wish. | |
* Please share the changes if you think they might be useful to others. | |
* | |
* Claude Martin. | |
* | |
* Code is available as a gist on GitHub: | |
* https://gist.github.com/claudemartin/9977caba94e1d8d97edf4b0435d8fea4 | |
* | |
* My blog: https://humanoid-readable.claude-martin.ch/2019/10/09/weakassqueue/ | |
*/ | |
import java.lang.ref.Cleaner; | |
import java.lang.ref.Reference; | |
import java.lang.ref.SoftReference; | |
import java.lang.ref.WeakReference; | |
import java.util.AbstractQueue; | |
import java.util.ArrayList; | |
import java.util.Collections; | |
import java.util.Iterator; | |
import java.util.LinkedList; | |
import java.util.List; | |
import java.util.NoSuchElementException; | |
import java.util.Objects; | |
import java.util.Optional; | |
import java.util.function.Function; | |
/** | |
* "Weak Ass" sounds funny, so I use that name. It's a LIFO queue (stack) with | |
* an <i>ass</i> (<i>tail</i>) that is weakly or softly linked. So garbage | |
* collection (GC) can remove elements at any time to prevent | |
* {@link OutOfMemoryError}. | |
* | |
* If you still run into {@link OutOfMemoryError} you must use another value for | |
* the {@link #getLimit() limit}. | |
* | |
* The <i>strong</i> part of this queue is a regular queue with strongly | |
* referenced elements. | |
* | |
* There are two modes to chose from: {@link LimitMode} and {@link RefMode}. | |
* | |
* Use {@link #keep(int)} and {@link #release()} to easily create a queue. | |
* | |
* Works with Java 11 or newer. | |
* | |
* @author Claude Martin | |
* | |
*/ | |
public final class WeakAssQueue<E> extends AbstractQueue<E> implements Iterable<E> { | |
private int limit; | |
private final RefMode refMode; | |
private final LimitMode limitMode; | |
/** | |
* This controls how the elements are swapped between <i>strong</i> and | |
* <i>weak/soft</i> referenced lists. | |
* | |
* See {@link #LIMIT_ASS} and {@link #LIMIT_STRONG} for more details. | |
*/ | |
public enum LimitMode { | |
/** | |
* Limit the number of elements in the weakly/softly referenced list. Put | |
* further elements into the strongly referenced list. This will protect more | |
* elements when GC is cleaning the oldest elements. | |
* | |
* If you still run into {@link OutOfMemoryError} you must use a <b>higher</b> | |
* value for the limit, so that more elements can be removed by GC. | |
*/ | |
LIMIT_ASS, | |
/** | |
* Limit the number of elements in the strongly referenced list. Put further | |
* elements into the weakly/softly referenced list. This mode will not protect | |
* that many elements when GC is cleaning the oldest elements. | |
* | |
* If you still run into {@link OutOfMemoryError} you must use a <b>lower</b> | |
* value for the limit, so that fewer elements are strongly referenced. | |
*/ | |
LIMIT_STRONG, | |
} | |
/** | |
* How the list with the oldest elements are to be referenced. | |
* | |
* @see WeakReference | |
* @see SoftReference | |
* | |
*/ | |
public enum RefMode { | |
/** | |
* Use {@link WeakReference}. Note that this means that the elements will be | |
* removed quite often. | |
*/ | |
WEAK(e -> new WeakReference<Object>(e)), | |
/** | |
* Use {@link SoftReference}. Elements will only be removed if necessary. | |
*/ | |
SOFT(e -> new SoftReference<Object>(e)); | |
private static final Cleaner CLEANER = Cleaner.create(); | |
@SuppressWarnings("rawtypes") | |
private final Function f; | |
private <T> RefMode(Function<T, Reference<T>> f) { | |
this.f = f; | |
} | |
@SuppressWarnings("unchecked") | |
<T> Reference<T> getRef(WeakAssQueue<?> q, T e) { | |
final var reference = (Reference<T>) this.f.apply(e); | |
if (q.getLimitMode() == LimitMode.LIMIT_ASS) { | |
CLEANER.register(e, () -> { | |
q.move(); // move oldest elements away from strongly referenced list | |
System.gc(); // indicate that there are not elements that could be removed | |
}); | |
} | |
return reference; | |
} | |
} | |
/** | |
* When garbage collector tries to removes elements the queue will <b>keep</b> | |
* the last <b>n</b> elements. In other words it protects the <i>n</i> elements, | |
* that were inserted lastly and are ready to be polled next. The older elements | |
* are available to be removed. | |
* | |
* <p> | |
* Use this to create a queue that will hold data that becomes less relevant | |
* over time. For example a queue for <i>undo</i> actions could hold at least 20 | |
* actions and potentially even more. | |
* | |
* @param <T> the type of elements in the queue | |
* @param n The amount of elements that will be protected from GC (mustn't be | |
* too large) | |
* @return A queue that will keep the last n elements. | |
*/ | |
public static <T> WeakAssQueue<T> keep(int n) { | |
return new WeakAssQueue<>(n, RefMode.SOFT, LimitMode.LIMIT_STRONG); | |
} | |
/** | |
* When garbage collector tries to removes elements the queue will | |
* <b>release</b> the oldest <b>n</b> elements. In other words it doesn't | |
* protect any elements from garbage collection, but only <i>n</i> elements, | |
* that were added first and will be polled last, are eligible for removal. | |
* Newer elements would only get removed when GC is run repeatedly, which | |
* happens when there's still not enough memory after GC. | |
* | |
* | |
* <p> | |
* Use this to create a queue that will only release few elements per gc cycle, | |
* so that it remains rather large over time. | |
* | |
* @param <T> the type of elements in the queue | |
* @param n The amount of elements that will be removed by GC (mustn't be too | |
* small) | |
* @return A queue that will allow the oldest n elements to be removed. | |
*/ | |
public static <T> WeakAssQueue<T> release(int n) { | |
return new WeakAssQueue<>(n, RefMode.SOFT, LimitMode.LIMIT_ASS); | |
} | |
/** | |
* Creates a queue that will protect only the 5 newest elements from GC. Older | |
* elements will be softly referenced, so that GC can remove them. | |
*/ | |
public WeakAssQueue() { | |
this(5, RefMode.SOFT, LimitMode.LIMIT_STRONG); | |
} | |
/** | |
* Creates a queue that will protect only the given amount of newest elements | |
* from GC. | |
* | |
* @param limit the amount of elements to be strongly referenced. | |
*/ | |
public WeakAssQueue(int limit) { | |
this(limit, RefMode.SOFT, LimitMode.LIMIT_STRONG); | |
} | |
/** | |
* Creates a queue with the given parameters. | |
* | |
* @param limit the amount of elements to be stronlgy referenced. | |
* @param ref The {@link RefMode mode} used to reference the oldest elements. | |
* @param swap The {@link LimitMode mode} used to limit one part of the list. | |
*/ | |
public WeakAssQueue(int limit, RefMode ref, LimitMode swap) { | |
this.limit = Math.max(0, limit); | |
this.refMode = ref == null ? RefMode.SOFT : ref; | |
this.limitMode = swap == null ? LimitMode.LIMIT_STRONG : swap; | |
} | |
/** | |
* This is the <i>strong</i> part of the queue. GC can't remove this. | |
*/ | |
private final LinkedList<E> strong = new LinkedList<>(); | |
/** This is the <i>weak</i> (or <i>soft</i>) part of the queue. */ | |
private Reference<LinkedList<E>> ass = null; | |
/** Get strong reference to the oldest elements. */ | |
private Optional<LinkedList<E>> getAss() { | |
if (ass == null) | |
return Optional.empty(); | |
final var list = ass.get(); | |
if (list == null) | |
return Optional.empty(); | |
return Optional.of(list); | |
} | |
/** | |
* Get strong reference to the oldest elements. Creates the list if it does not | |
* currently exist. | |
*/ | |
private LinkedList<E> getAssOrCreate() { | |
final var tail2 = getAss(); | |
final LinkedList<E> list; | |
if (tail2.isPresent()) | |
list = tail2.get(); | |
else | |
this.ass = this.refMode.getRef(this, list = new LinkedList<>()); | |
return list; | |
} | |
public synchronized void push(E e) { | |
strong.push(Objects.requireNonNull(e, "can't push null")); | |
if (this.limitMode == LimitMode.LIMIT_STRONG) { | |
if (strong.size() > limit) | |
getAssOrCreate().push(strong.removeLast()); | |
} else | |
move(); | |
} | |
public synchronized Optional<E> pop() { | |
E e; | |
final var ass2 = getAssOrCreate(); | |
if (!strong.isEmpty()) | |
e = strong.pop(); | |
else if (!ass2.isEmpty()) | |
e = ass2.pop(); | |
else | |
return Optional.empty(); | |
if (this.limitMode == LimitMode.LIMIT_STRONG) { | |
if (strong.size() < limit && !ass2.isEmpty()) | |
strong.addLast(ass2.removeFirst()); | |
} else | |
move(); | |
return Optional.of(e); | |
} | |
public synchronized E tryPop() throws NoSuchElementException { | |
return this.pop().orElseThrow(); | |
} | |
public synchronized E popOr(E other) { | |
return this.pop().orElse(other); | |
} | |
/** | |
* The size of this queue. Note that even if only one thread is using the queue | |
* it is possible that GC will | |
* | |
* @return | |
*/ | |
public synchronized int size() { | |
return strong.size() + getAss().map(l -> l.size()).orElse(0); | |
} | |
/** | |
* The maximum of elements allowed in either the strongly referenced part or the | |
* other one. | |
* | |
* @see LimitMode | |
*/ | |
public synchronized int getLimit() { | |
return limit; | |
} | |
/** | |
* Sets the limit of the part that does not grow infinitely. | |
* | |
* @see LimitMode | |
*/ | |
public synchronized void setLimit(int limit) { | |
this.limit = limit; | |
} | |
public RefMode getRefMode() { | |
return refMode; | |
} | |
/** | |
* This defined how the queue is limiting one part of the data structure. | |
* | |
* @see LimitMode | |
* @return The mode used to limit the queue size | |
*/ | |
public LimitMode getLimitMode() { | |
return limitMode; | |
} | |
/** | |
* Move the elements after GC. This is also called by {@link #push} and | |
* {@link #pop} because it could be that the Cleaner didn't yet get to call it. | |
*/ | |
protected synchronized void move() { | |
try { | |
assert this.limitMode == LimitMode.LIMIT_ASS; | |
final LinkedList<E> ass2 = getAssOrCreate(); | |
while (ass2.size() < limit && !strong.isEmpty()) { | |
ass2.push(strong.removeLast()); | |
} | |
} catch (OutOfMemoryError e) { | |
// This dind't work, so we just remove old elements. | |
ass = null; | |
for (int i = 0; i < limit; i++) | |
strong.pollLast(); | |
} | |
} | |
/** | |
* Allows to iterate from oldest to newest. The iterator will use a copy of the | |
* queue as seen when this iterator was created. All elements are strongly | |
* linked as long as this iterator exists. | |
*/ | |
public synchronized Iterator<E> reversedIterator() { | |
final var ass2 = getAss(); | |
final var copy = new LinkedList<E>(); | |
ass2.ifPresent(ass3 -> { | |
for(E e : ass3) | |
copy.addFirst(e); | |
}); | |
for(E e : strong) | |
copy.addFirst(e); | |
return Collections.unmodifiableList(copy).iterator(); | |
} | |
/** | |
* {@inheritDoc} | |
* | |
* This iterators returns the newest element first. It's the reversed insertion | |
* order. Just as you would get the elements by {@link #pop() popping} them one | |
* by one. The iterator will use a copy of the queue as seen when this iterator | |
* was created. All elements are strongly linked as long as this iterator | |
* exists. | |
* | |
* @see #reversedIterator() | |
*/ | |
@Override | |
public synchronized Iterator<E> iterator() { | |
final var ass2 = getAss(); | |
final var size = strong.size() + ass2.map(l -> l.size()).orElse(0); | |
final var copy = new ArrayList<E>(size); | |
copy.addAll(strong); | |
ass2.ifPresent(copy::addAll); | |
return Collections.unmodifiableList(copy).iterator(); | |
} | |
/** | |
* A string representation of this queue. The elements are shown from newest to | |
* oldest (reversed insertion order). | |
*/ | |
@Override | |
public String toString() { | |
final var it = iterator(); | |
if (!it.hasNext()) | |
return "[]"; | |
var sb = new StringBuilder(); | |
sb.append('['); | |
for (;;) { | |
E e = it.next(); | |
sb.append(e == this ? "(this Collection)" : e); | |
if (!it.hasNext()) | |
return sb.append(']').toString(); | |
sb.append(',').append(' '); | |
} | |
} | |
// THE FOLLOWING METHODS ONLY EXIST TO IMPLEMENT java.util.Queue<E> | |
@Override | |
public boolean offer(E e) { | |
this.push(e); | |
return true; | |
} | |
@Override | |
public E poll() { | |
return this.popOr(null); | |
} | |
@Override | |
public synchronized E peek() { | |
if (!strong.isEmpty()) | |
return strong.peek(); | |
final LinkedList<E> ass2 = getAssOrCreate(); | |
if (!ass2.isEmpty()) | |
return ass2.peek(); | |
else | |
return null; | |
} | |
@Override | |
public synchronized void clear() { | |
this.strong.clear(); | |
getAss().ifPresent(List::clear); | |
} | |
} |
import static org.junit.Assert.assertFalse; | |
import static org.junit.Assert.assertNull; | |
import static org.junit.Assert.assertTrue; | |
import static org.junit.jupiter.api.Assertions.assertEquals; | |
import static org.junit.jupiter.api.Assertions.assertThrows; | |
import static org.junit.jupiter.api.Assertions.fail; | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.Iterator; | |
import java.util.List; | |
import java.util.Optional; | |
import java.util.stream.Stream; | |
import org.junit.jupiter.api.Test; | |
import org.junit.jupiter.params.ParameterizedTest; | |
import org.junit.jupiter.params.provider.Arguments; | |
import org.junit.jupiter.params.provider.MethodSource; | |
/** | |
* This uses JUnit 5 (Jupiter). I wrote it in Eclipse and it should be easy to | |
* get the tests running as long as org.junit.jupiter is available. Note that | |
* this runs for a long time and uses lots of memory. | |
* | |
* Note that {@link #testPush} is the only test that actually fills memory to | |
* trigger garbage collection. Try <code>-Xmx50m</code> so this doens't take too | |
* long. | |
* | |
* @author Claude Martin | |
* | |
*/ | |
class WeakAssQueueTest { | |
/** Removes weakly linked queues. GC would just remove elements. */ | |
private static Stream<Arguments> softOnly() { | |
return queues().filter(q -> q.getRefMode() == WeakAssQueue.RefMode.SOFT).map(Arguments::of); | |
} | |
/** Removes unreasonable queues. */ | |
private static Stream<Arguments> reasonable() { | |
return queues().filter(q -> !(q.getLimit() == 0 && q.getLimitMode() == WeakAssQueue.LimitMode.LIMIT_ASS)) | |
.map(Arguments::of); | |
} | |
/** All possible configurations. */ | |
private static Stream<Arguments> all() { | |
return queues().map(Arguments::of); | |
} | |
private static Stream<WeakAssQueue<?>> queues() { | |
return Stream.of(// | |
new WeakAssQueue<>(0, WeakAssQueue.RefMode.SOFT, WeakAssQueue.LimitMode.LIMIT_ASS), // | |
new WeakAssQueue<>(0, WeakAssQueue.RefMode.SOFT, WeakAssQueue.LimitMode.LIMIT_STRONG), // | |
new WeakAssQueue<>(0, WeakAssQueue.RefMode.WEAK, WeakAssQueue.LimitMode.LIMIT_ASS), // | |
new WeakAssQueue<>(0, WeakAssQueue.RefMode.WEAK, WeakAssQueue.LimitMode.LIMIT_STRONG), // | |
new WeakAssQueue<>(5, WeakAssQueue.RefMode.SOFT, WeakAssQueue.LimitMode.LIMIT_ASS), // | |
new WeakAssQueue<>(5, WeakAssQueue.RefMode.SOFT, WeakAssQueue.LimitMode.LIMIT_STRONG), // | |
new WeakAssQueue<>(5, WeakAssQueue.RefMode.WEAK, WeakAssQueue.LimitMode.LIMIT_ASS), // | |
new WeakAssQueue<>(5, WeakAssQueue.RefMode.WEAK, WeakAssQueue.LimitMode.LIMIT_STRONG) // | |
); | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testSize(WeakAssQueue<Integer> q) { | |
q.push(42); | |
assertEquals(1, q.size()); | |
q.push(42); | |
assertEquals(2, q.size()); | |
q.pop(); | |
assertEquals(1, q.size()); | |
q.pop(); | |
assertEquals(0, q.size()); | |
} | |
@ParameterizedTest | |
@MethodSource("reasonable") | |
void testPush(WeakAssQueue<byte[]> q) { | |
for (int i = 1; i < Integer.MAX_VALUE; i++) { | |
final byte[] youngest = new byte[1_000_000]; | |
q.push(youngest); // 1 MB | |
if (i % 10 == 0) { // Check every 10 MB | |
System.gc(); | |
Thread.yield(); | |
if (i != q.size()) { | |
if (q.getLimit() > 0 && q.getRefMode() == WeakAssQueue.RefMode.SOFT) { | |
// With such a configuration the newest element must still be in the queue. | |
// Even with LIMIT_ASS there must be something left in the queue. | |
// Weak references can be deleted at any time, so we can't test those. | |
assertTrue(youngest == q.peek()); // assertSame could trigger OOME | |
} | |
return; // success: GC removed some elements | |
} | |
} | |
} | |
fail("GC didn't remove anything. Try -Xmx50m "); | |
} | |
void fill(WeakAssQueue<String> q) { | |
for (int i = 1; i < 12; i++) | |
q.push(String.format("%d is an integer and that's all we know about it.", i)); | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testTryPop(WeakAssQueue<String> q) { | |
fill(q); | |
q.push("1"); | |
q.push("2"); | |
q.push("3"); | |
q.push("4"); | |
assertEquals("4", q.pop().get()); | |
assertEquals("3", q.pop().get()); | |
assertEquals("2", q.pop().get()); | |
assertEquals("1", q.pop().get()); | |
while (!q.isEmpty()) | |
q.pop(); | |
assertTrue(q.isEmpty()); | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testPopOr(WeakAssQueue<String> q) { | |
q.push("1"); | |
q.push("2"); | |
q.push("3"); | |
q.push("4"); | |
assertEquals("4", q.popOr(null)); | |
assertEquals("3", q.popOr(null)); | |
assertEquals("2", q.popOr(null)); | |
assertEquals("1", q.popOr(null)); | |
assertNull(q.popOr(null)); | |
assertNull(q.popOr(null)); | |
assertNull(q.popOr(null)); | |
} | |
@Test | |
void testGetters() { | |
var q = new WeakAssQueue<>(42, WeakAssQueue.RefMode.SOFT, WeakAssQueue.LimitMode.LIMIT_ASS); | |
assertEquals(42, q.getLimit()); | |
assertEquals(WeakAssQueue.RefMode.SOFT, q.getRefMode()); | |
assertEquals(WeakAssQueue.LimitMode.LIMIT_ASS, q.getLimitMode()); | |
q = new WeakAssQueue<>(123, WeakAssQueue.RefMode.WEAK, WeakAssQueue.LimitMode.LIMIT_STRONG); | |
assertEquals(123, q.getLimit()); | |
assertEquals(WeakAssQueue.RefMode.WEAK, q.getRefMode()); | |
assertEquals(WeakAssQueue.LimitMode.LIMIT_STRONG, q.getLimitMode()); | |
} | |
@Test | |
void testSetLimit() { | |
var q = new WeakAssQueue<String>(3, WeakAssQueue.RefMode.WEAK, WeakAssQueue.LimitMode.LIMIT_STRONG); | |
fill(q); | |
System.gc(); | |
Thread.yield(); | |
assertEquals(3, q.size()); | |
for (int limit = 5; limit < 20; limit++) { | |
q.setLimit(limit); | |
fill(q); | |
System.gc(); | |
Thread.yield(); | |
assertEquals(limit, q.getLimit()); | |
assertEquals(limit, q.size()); | |
} | |
// LIMIT_ASS is impossible to test because the queue can always end up empty. | |
q = new WeakAssQueue<>(3, WeakAssQueue.RefMode.WEAK, WeakAssQueue.LimitMode.LIMIT_ASS); | |
for (int limit = 5; limit < 20; limit++) { | |
q.setLimit(limit); | |
fill(q); | |
System.gc(); | |
Thread.yield(); | |
assertEquals(limit, q.getLimit()); | |
} | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testReversedIterator(WeakAssQueue<Integer> q) { | |
assertFalse(q.reversedIterator().hasNext()); | |
q.push(1); | |
q.push(2); | |
q.push(3); | |
q.push(4); | |
ArrayList<Integer> l = new ArrayList<>(); | |
Iterator<Integer> itr = q.reversedIterator(); | |
while (itr.hasNext()) | |
l.add((Integer) itr.next()); | |
assertEquals(1, l.get(0)); | |
assertEquals(2, l.get(1)); | |
assertEquals(3, l.get(2)); | |
assertEquals(4, l.get(3)); | |
assertThrows(UnsupportedOperationException.class, () -> q.reversedIterator().remove()); | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testIterator(WeakAssQueue<Integer> q) { | |
for (@SuppressWarnings("unused") int i : q) | |
fail(); | |
q.push(1); | |
q.push(2); | |
q.push(3); | |
q.push(4); | |
final var l = new ArrayList<Integer>(); | |
for (int i : q) | |
l.add(i); | |
assertEquals(4, l.get(0)); | |
assertEquals(3, l.get(1)); | |
assertEquals(2, l.get(2)); | |
assertEquals(1, l.get(3)); | |
assertThrows(UnsupportedOperationException.class, () -> q.iterator().remove()); | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testToString(WeakAssQueue<String> q) { | |
assertEquals("[]", q.toString()); | |
q.push("1"); | |
q.push("2"); | |
q.push("3"); | |
q.push("4"); | |
assertEquals("[4, 3, 2, 1]", q.toString()); | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testOffer(WeakAssQueue<String> q) { | |
assertTrue(q.offer("x")); | |
assertEquals(Optional.of("x"), q.pop()); | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testPoll(WeakAssQueue<String> q) { | |
assertNull(q.poll()); | |
assertTrue(q.offer("x")); | |
assertEquals("x", q.poll()); | |
assertTrue(q.isEmpty()); | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testPeek(WeakAssQueue<String> q) { | |
assertNull(q.peek()); | |
assertTrue(q.offer("x")); | |
assertEquals("x", q.peek()); | |
} | |
@ParameterizedTest | |
@MethodSource("softOnly") | |
void testAddAll(WeakAssQueue<Integer> q) { | |
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9); | |
q.addAll(list); | |
assertEquals(9, q.poll()); | |
assertEquals(8, q.poll()); | |
} | |
@ParameterizedTest | |
@MethodSource("all") | |
void testClear(WeakAssQueue<String> q) { | |
fill(q); | |
q.clear(); | |
assertTrue(q.isEmpty()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment