Below is my implementation of a pool. It is based on a hash table and supports using strong, soft or weak references to store objects. At the start there is a builder class to configure and create instances, followed by a subclass of Pool which allows multiple reference types to be used. Towards the end there is an enum defining the reference types available and an implementation of the Node interface (used to store objects) for each of them.
The Nodes are stored and accessed the same way as in HashMap (minus the trees) and WeakHashMap, in a array of buckets which has a length equal to a power of two with the index being obtained by &ing the length of the array minus one and a modified (to account for only using the lower bits) version of the hash code submitted. Each Node has a reference to the next Node in the bucket, or null if it is the last.
It registers Nodes with a ReferenceQueue and attempts to clean out any that are in the queue when the methods that add or remove objects or check the size of the pool are called. Nodes whose values have been finalized are also removed during re-sizes and when encountered while retrieving objects.
I don't have any specific concerns about my code, I'm just looking for any ways that I can improve.
package common.collections;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;
import java.util.Arrays;
import java.util.Objects;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.function.UnaryOperator;
import java.util.stream.Stream;
import common.utils.EnumUtils;
import common.utils.StreamUtils;
/** A pool based on a hash table which can store its elements in {@code Reference} objects.
* <p>
* Null values are not accepted and will result in a {@code NullPointerException} if you
* try to add them.
* <p>
* This class is not thread safe. */
public class Pool<T> {
private static final int MAX_CAPACITY = 1 << 30;
private static final int MIN_CAPACITY = 1;
private final double growFactor;
private final double shrinkFactor;
private final ReferenceQueue<T> queue;
private final ReferenceType referenceType;
private int size;
private Node<T>[] nodes;
@SuppressWarnings("unchecked")
private Pool(int capacity, double growFactor, double shrinkFactor,
ReferenceType referenceType) {
this.growFactor = growFactor;
this.shrinkFactor = shrinkFactor;
this.referenceType = referenceType;
nodes = new Node[capacity];
queue = new ReferenceQueue<>();
}
public static class Builder<T> {
private static final int DEFAULT_CAPACITY = 16;
private static final double DEFAULT_GROW_FACTOR = 0.75;
private static final double DEFAULT_SHRINK_FACTOR = 0;
private static final ReferenceType DEFAULT_REFERENCE_TYPE = ReferenceType.WEAK;
private int capacity;
private double growFactor;
private double shrinkFactor;
private ReferenceType referenceType;
public Builder() {
capacity = DEFAULT_CAPACITY;
growFactor = DEFAULT_GROW_FACTOR;
shrinkFactor = DEFAULT_SHRINK_FACTOR;
referenceType = DEFAULT_REFERENCE_TYPE;
}
public Pool<T> buildPool() {
return new Pool<>(capacity, growFactor, shrinkFactor, referenceType);
}
public MultiReferenceTypePool<T> buildMultiReferenceTypePool() {
return new MultiReferenceTypePool<>(capacity, growFactor, shrinkFactor,
referenceType);
}
/** Initial number of buckets. Will be rounded up (or down if greater than max
* capacity) to a power of 2. */
public Builder<T> capacity(int initialCapacity) {
initialCapacity = Math.max(MIN_CAPACITY,
Math.min(MAX_CAPACITY, initialCapacity));
capacity = 1;
while (capacity < initialCapacity) {
capacity <<= 1;
}
return this;
}
/** When size is greater than grow factor * capacity, capacity is doubled. */
public Builder<T> growFactor(double f) {
growFactor = f;
return this;
}
/** Similar to grow factor except as a lower bound which reduces capacity. */
public Builder<T> shrinkFactor(double f) {
shrinkFactor = f;
return this;
}
/** Sets the type of reference to use to store objects. */
public Builder<T> referenceType(ReferenceType type) {
referenceType = Objects.requireNonNull(type);
return this;
}
@Override
public String toString() {
return "Capacity: " + capacity + " Reference Type: " + referenceType
+ " Grow Factor: " + growFactor + " ShrinkFactor: " + shrinkFactor;
}
}
/** An Extension of Pool which allows multiple reference types to be used. */
public static class MultiReferenceTypePool<T> extends Pool<T> {
private MultiReferenceTypePool(int capacity, double growFactor,
double shrinkFactor, ReferenceType referenceType) {
super(capacity, growFactor, shrinkFactor, referenceType);
}
/** Extension of {@link Pool#Add(T)} which allows the caller to specify the
* reference type to be used to store the object. If a matching object is found
* with a different reference type its type is changed to {@code referenceType} if
* {@code changeCurrent} returns true. If {@code referenceType} is null the pool's
* reference type is used instead. */
public void Add(T t, ReferenceType ref,
Predicate<? super ReferenceType> changeCurrent) {
getOrCreate(() -> t, t::equals, t.hashCode(), ref, changeCurrent);
}
/** Extension of {@link Pool#getOrCreate(Supplier, Predicate, int)} which allows
* the caller to specify the reference type to be used to store the object. If a
* matching object is found with a different reference type its type is changed to
* {@code referenceType} if {@code changeCurrent} returns true. If
* {@code referenceType} is null the pool's reference type is used instead. */
public T getOrCreate(Supplier<? extends T> supplier, Predicate<? super T> equals,
int hash, ReferenceType referenceType,
Predicate<? super ReferenceType> changeCurrent) {
ReferenceType type = referenceType == null ? super.referenceType
: referenceType;
hash = fixHash(hash);
super.removeDeadNodes();
T t = super.find(equals, hash, n -> n.type() == type ? n
: changeCurrent.test(n.type()) ? type.newNode(n.get(), n.hash(), super.queue)
: n);
if (t != null) {
return t;
}
t = Objects.requireNonNull(supplier.get());
super.insert(type.newNode(t, hash, super.queue));
super.size++;
super.resize();
return t;
}
}
private int largestBucket() {
return Arrays.stream(nodes)
.filter(Objects::nonNull)
.mapToInt(n -> (int) StreamUtils.iterate(n, Node::next).count())
.max()
.orElse(0);
}
/** Returns a sequential stream with this pool as its source. */
public Stream<T> stream() {
return Arrays.stream(nodes)
.filter(Objects::nonNull)
.flatMap(n -> StreamUtils.iterate(n, Node::next))
.map(Node::get)
.filter(Objects::nonNull);
}
@Override
public String toString() {
return "Buckets: " + nodes.length + " Size: " + size + " Reference Type: "
+ referenceType + " Largest Bucket: " + largestBucket();
}
@SuppressWarnings("unchecked")
private void removeDeadNodes() {
Node<T> dead = null;
outer: while ((dead = (Node<T>) queue.poll()) != null) {
int index = dead.hash() & (nodes.length - 1);
Node<T> n = nodes[index];
Node<T> last = null;
while (n != dead) {
if (n == null) {
continue outer;
}
last = n;
n = n.next();
}
size--;
if (last == null) {
nodes[index] = n.next();
} else {
last.setNext(n.next());
}
}
}
/** Removes all objects from this pool. */
@SuppressWarnings("unchecked")
public void clear() {
size = 0;
int s = getNewSize();
if (s == nodes.length) {
Arrays.fill(nodes, null);
} else {
nodes = new Node[s];
}
while (queue.poll() != null);
}
/** Returns an estimate of the number of elements in this pool. This method should not
* be called during the execution of a stream returned from this pool because it may
* modify the source of the stream. */
public int size() {
removeDeadNodes();
resize();
return size;
}
/** Adds {@code t} to this pool if an equal object is not already present. This method
* is equivalent to calling {@code getOrCreate(() -> t, t::equals, t.hashCode());} */
public void Add(T t) {
getOrCreate(() -> t, t::equals, t.hashCode());
}
/** If an object that has a hash value equal to {@code hash} and {@code equals.test()}
* returns true when applied to it exists in this pool, it is returned.
* <p>
* If a matching value cannot be found, {@code supplier.get()} is called to create one
* and it is added to the pool, assigned the hash value {@code hash}, and returned.
*
* @throws NullPointerException if {@code supplier.get()} returns null. */
public T getOrCreate(Supplier<? extends T> supplier, Predicate<? super T> equals,
int hash) {
hash = fixHash(hash);
removeDeadNodes();
T t = find(equals, hash, n -> n);
if (t != null) {
return t;
}
t = Objects.requireNonNull(supplier.get());
insert(referenceType.newNode(t, hash, queue));
size++;
resize();
return t;
}
/** Removes from this pool and returns an object equal to {@code t}, or null if no such
* value is present. This method is equivalent to calling
* {@code remove(t::equals, t.hashCode())} */
public T remove(T t) {
return remove(t::equals, t.hashCode());
}
/** Removes from this pool and returns an object with a hash value of {@code hash}
* which returns true when {@code equals.test()} is applied to it, or null if no
* matching value is present. */
public T remove(Predicate<? super T> equals, int hash) {
hash = fixHash(hash);
removeDeadNodes();
return find(equals, hash, n -> null);
}
private T find(Predicate<? super T> equals, int hash,
UnaryOperator<Node<T>> replacement) {
int index = hash & (nodes.length - 1);
for (Node<T> n = nodes[index], last = null; n != null; n = n.next()) {
if (n.hash() != hash) {
last = n;
continue;
}
T t = n.get();
if (t == null) {
size--;
if (last == null) {
nodes[index] = n.next();
} else {
last.setNext(n.next());
}
continue;
}
if (equals.test(t)) {
Node<T> newn = replacement.apply(n);
if (newn == null) {
size--;
if (last == null) {
nodes[index] = n.next();
} else {
last.setNext(n.next());
}
} else if (newn != n) {
newn.setNext(n.next());
if (last == null) {
nodes[index] = newn;
} else {
last.setNext(newn);
}
}
resize();
return t;
}
last = n;
}
resize();
return null;
}
/** @see java.util.WeakHashMap#hash */
private static int fixHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
private void resize() {
int s = getNewSize();
if (s != nodes.length) {
resize(s);
}
}
private int getNewSize() {
int s = nodes.length;
while (size > s * growFactor && s < MAX_CAPACITY) {
s <<= 1;
}
while (size < s * shrinkFactor && s > MIN_CAPACITY) {
s >>= 1;
}
return s;
}
@SuppressWarnings("unchecked")
private void resize(int length) {
Node<T>[] oldNodes = nodes;
nodes = new Node[length];
for (Node<T> n : oldNodes) {
while (n != null) {
Node<T> next = n.next();
n.setNext(null);
if (n.get() != null) {
insert(n);
} else {
size--;
}
n = next;
}
}
};
private void insert(Node<T> node) {
int index = node.hash() & (nodes.length - 1);
Node<T> n = nodes[index];
if (n == null) {
nodes[index] = node;
return;
}
while (n.next() != null) {
n = n.next();
}
n.setNext(node);
}
private interface Node<T> {
T get();
int hash();
void setNext(Node<T> next);
Node<T> next();
ReferenceType type();
}
@SuppressWarnings("unchecked")
public enum ReferenceType {
WEAK(WeakNode::new), SOFT(SoftNode::new), STRONG(StrongNode::new);
private final NodeConstructor constructor;
private ReferenceType(NodeConstructor constructor) {
this.constructor = constructor;
}
private <T> Node<T> newNode(T value, int hash, ReferenceQueue<T> queue) {
return constructor.create(value, hash, queue);
}
@Override
public String toString() {
return EnumUtils.toString(this);
}
@FunctionalInterface
private interface NodeConstructor {
<T> Node<T> create(T value, int hash, ReferenceQueue<T> queue);
}
}
private static class WeakNode<T> extends WeakReference<T> implements Node<T> {
private final int hash;
private Node<T> next;
private WeakNode(T value, int hash, ReferenceQueue<T> queue) {
super(value, queue);
this.hash = hash;
}
@Override
public int hash() {
return hash;
}
@Override
public Node<T> next() {
return next;
}
@Override
public void setNext(Node<T> next) {
this.next = next;
}
@Override
public ReferenceType type() {
return ReferenceType.WEAK;
}
}
private static class SoftNode<T> extends SoftReference<T> implements Node<T> {
private final int hash;
private Node<T> next;
private SoftNode(T value, int hash, ReferenceQueue<T> queue) {
super(value, queue);
this.hash = hash;
}
@Override
public int hash() {
return hash;
}
@Override
public Node<T> next() {
return next;
}
@Override
public void setNext(Node<T> next) {
this.next = next;
}
@Override
public ReferenceType type() {
return ReferenceType.SOFT;
}
}
private static class StrongNode<T> implements Node<T> {
private final int hash;
private final T value;
private Node<T> next;
private StrongNode(T value, int hash, ReferenceQueue<T> queue) {
this.hash = hash;
this.value = value;
}
@Override
public T get() {
return value;
}
@Override
public int hash() {
return hash;
}
@Override
public Node<T> next() {
return next;
}
@Override
public void setNext(Node<T> next) {
this.next = next;
}
@Override
public ReferenceType type() {
return ReferenceType.STRONG;
}
}
}
