Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.