10
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
3
\$\begingroup\$
/** 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);
}

The function is doing something else besides what the comment says (namely, running a while loop). What's the while loop for? Additionally, you should (this is a nitpick) write a comment why you use a @SuppressWarnings annotation there.

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;
}

This function has a cyclomatic complexity of 10. That's a bit high, but that's okay. Nothing you can do about it. However, you should keep in mind that as your functions get more complex, your variable names should be more descriptive. What does newn mean? Is it a new Node? I don't see the keyword new though. Additionally, such complex methods could use commentary to explain just exactly what they do (this comment of mine might become irrelevant once you've made the variable names more descriptive).

More @SuppressWarnings show up - comment those with an explanation for a possible maintenance programmer.


My personal preferences (nitpicks):
I'd add a comment why you return this on the builder (I know why, it's for chaining, but others might not.).

I'd also rename the functions growFactor and shrinkFactor to setGrowFactor and setShrinkFactor. This because it seems easy to mistake them for "growByFactor" and "shrinkByFactor". The documentation shows that this is not the case however, which makes this my personal preference rather than a notable improvement.

I'd put blank lines between the end of a function and the start of a comment block documenting the next function. Doing so gives me the feeling that a function ends there and that I can process what I've read before continuing.

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) {

Personally, I prefer to keep functions with the same name together. This makes it easier to look them up. So in this case, I'd swap resize() with getNewSize().


Now we're really getting into nitpick-land.

    /** 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. */

"If a matching object is found with a different reference type its type is changed to referenceType if changeCurrent returns true."
This sentence is missing a comma. Change to "(...)with a different reference type, its type".

"If referenceType is null the pool's reference type is used instead."
Also missing a comma. Change to "If `referenceType is null, the pool's (...)".

At this point I think we can agree that you've written a marvelous piece of code. It's well documented, makes full use of the language's features (loop labels! Last time I saw those is when I was reading the spec for fun!), and doesn't seem to have any obvious flaws. As you can see, none of the things I pointed out relate to the actual code, save for the naming of some functions. The rest is all related to the comments and order of your functions.

I'd suggest analyzing the code with various tools such as Sonar and whatever else is out there. I'd also suggest writing a set of unittests if you really wanted to polish it to perfection.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.