    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.list;
    018
    019import java.io.IOException;
    020import java.io.ObjectInputStream;
    021import java.io.ObjectOutputStream;
    022import java.io.Serializable;
    023import java.util.Collection;
    024
    025/**
    026 * A <code>List</code> implementation that stores a cache of internal Node objects
    027 * in an effort to reduce wasteful object creation.
    028 * <p>
    029 * A linked list creates one Node for each item of data added. This can result in
    030 * a lot of object creation and garbage collection. This implementation seeks to
    031 * avoid that by maintaining a store of cached nodes.
    032 * </p>
    033 * <p>
    034 * This implementation is suitable for long-lived lists where both add and remove
    035 * are used. Short-lived lists, or lists which only grow will have worse performance
    036 * using this class.
    037 * </p>
    038 * <p>
    039 * <b>Note that this implementation is not synchronized.</b>
    040 * </p>
    041 *
    042 * @since 3.0
    043 */
    044public class NodeCachingLinkedList<E> extends AbstractLinkedList<E> implements Serializable {
    045
    046    /** Serialization version */
    047    private static final long serialVersionUID = 6897789178562232073L;
    048
    049    /**
    050     * The default value for {@link #maximumCacheSize}.
    051     */
    052    private static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20;
    053
    054    /**
    055     * The first cached node, or <code>null</code> if no nodes are cached.
    056     * Cached nodes are stored in a singly-linked list with
    057     * <code>next</code> pointing to the next element.
    058     */
    059    private transient Node<E> firstCachedNode;
    060
    061    /**
    062     * The size of the cache.
    063     */
    064    private transient int cacheSize;
    065
    066    /**
    067     * The maximum size of the cache.
    068     */
    069    private int maximumCacheSize;
    070
    071    //-----------------------------------------------------------------------
    072    /**
    073     * Constructor that creates.
    074     */
    075    public NodeCachingLinkedList() {
    076        this(DEFAULT_MAXIMUM_CACHE_SIZE);
    077    }
    078
    079    /**
    080     * Constructor that copies the specified collection
    081     *
    082     * @param coll  the collection to copy
    083     */
    084    public NodeCachingLinkedList(final Collection<? extends E> coll) {
    085        super(coll);
    086        this.maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE;
    087    }
    088
    089    /**
    090     * Constructor that species the maximum cache size.
    091     *
    092     * @param maximumCacheSize  the maximum cache size
    093     */
    094    public NodeCachingLinkedList(final int maximumCacheSize) {
    095        super();
    096        this.maximumCacheSize = maximumCacheSize;
    097        init();  // must call init() as use super();
    098    }
    099
    100    //-----------------------------------------------------------------------
    101    /**
    102     * Gets the maximum size of the cache.
    103     *
    104     * @return the maximum cache size
    105     */
    106    protected int getMaximumCacheSize() {
    107        return maximumCacheSize;
    108    }
    109
    110    /**
    111     * Sets the maximum size of the cache.
    112     *
    113     * @param maximumCacheSize  the new maximum cache size
    114     */
    115    protected void setMaximumCacheSize(final int maximumCacheSize) {
    116        this.maximumCacheSize = maximumCacheSize;
    117        shrinkCacheToMaximumSize();
    118    }
    119
    120    /**
    121     * Reduce the size of the cache to the maximum, if necessary.
    122     */
    123    protected void shrinkCacheToMaximumSize() {
    124        // Rich Dougherty: This could be more efficient.
    125        while (cacheSize > maximumCacheSize) {
    126            getNodeFromCache();
    127        }
    128    }
    129
    130    /**
    131     * Gets a node from the cache. If a node is returned, then the value of
    132     * {@link #cacheSize} is decreased accordingly. The node that is returned
    133     * will have <code>null</code> values for next, previous and element.
    134     *
    135     * @return a node, or <code>null</code> if there are no nodes in the cache.
    136     */
    137    protected Node<E> getNodeFromCache() {
    138        if (cacheSize == 0) {
    139            return null;
    140        }
    141        final Node<E> cachedNode = firstCachedNode;
    142        firstCachedNode = cachedNode.next;
    143        cachedNode.next = null; // This should be changed anyway, but defensively
    144                                // set it to null.
    145        cacheSize--;
    146        return cachedNode;
    147    }
    148
    149    /**
    150     * Checks whether the cache is full.
    151     *
    152     * @return true if the cache is full
    153     */
    154    protected boolean isCacheFull() {
    155        return cacheSize >= maximumCacheSize;
    156    }
    157
    158    /**
    159     * Adds a node to the cache, if the cache isn't full.
    160     * The node's contents are cleared to so they can be garbage collected.
    161     *
    162     * @param node  the node to add to the cache
    163     */
    164    protected void addNodeToCache(final Node<E> node) {
    165        if (isCacheFull()) {
    166            // don't cache the node.
    167            return;
    168        }
    169        // clear the node's contents and add it to the cache.
    170        final Node<E> nextCachedNode = firstCachedNode;
    171        node.previous = null;
    172        node.next = nextCachedNode;
    173        node.setValue(null);
    174        firstCachedNode = node;
    175        cacheSize++;
    176    }
    177
    178    //-----------------------------------------------------------------------
    179    /**
    180     * Creates a new node, either by reusing one from the cache or creating
    181     * a new one.
    182     *
    183     * @param value  value of the new node
    184     * @return the newly created node
    185     */
    186    @Override
    187    protected Node<E> createNode(final E value) {
    188        final Node<E> cachedNode = getNodeFromCache();
    189        if (cachedNode == null) {
    190            return super.createNode(value);
    191        }
    192        cachedNode.setValue(value);
    193        return cachedNode;
    194    }
    195
    196    /**
    197     * Removes the node from the list, storing it in the cache for reuse
    198     * if the cache is not yet full.
    199     *
    200     * @param node  the node to remove
    201     */
    202    @Override
    203    protected void removeNode(final Node<E> node) {
    204        super.removeNode(node);
    205        addNodeToCache(node);
    206    }
    207
    208    /**
    209     * Removes all the nodes from the list, storing as many as required in the
    210     * cache for reuse.
    211     *
    212     */
    213    @Override
    214    protected void removeAllNodes() {
    215        // Add the removed nodes to the cache, then remove the rest.
    216        // We can add them to the cache before removing them, since
    217        // {@link AbstractLinkedList.removeAllNodes()} removes the
    218        // nodes by removing references directly from {@link #header}.
    219        final int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize);
    220        Node<E> node = header.next;
    221        for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) {
    222            final Node<E> oldNode = node;
    223            node = node.next;
    224            addNodeToCache(oldNode);
    225        }
    226        super.removeAllNodes();
    227    }
    228
    229    //-----------------------------------------------------------------------
    230    /**
    231     * Serializes the data held in this object to the stream specified.
    232     *
    233     * @param out  the output stream
    234     * @throws IOException if an error occurs while writing to the stream
    235     */
    236    private void writeObject(final ObjectOutputStream out) throws IOException {
    237        out.defaultWriteObject();
    238        doWriteObject(out);
    239    }
    240
    241    /**
    242     * Deserializes the data held in this object to the stream specified.
    243     *
    244     * @param in  the input stream
    245     * @throws IOException if an error occurs while reading from the stream
    246     * @throws ClassNotFoundException if an object read from the stream can not be loaded
    247     */
    248    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    249        in.defaultReadObject();
    250        doReadObject(in);
    251    }
    252
    253}