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 * This implementation is suitable for long-lived lists where both add and remove
034 * are used. Short-lived lists, or lists which only grow will have worse performance
035 * using this class.
036 * <p>
037 * <b>Note that this implementation is not synchronized.</b>
038 *
039 * @since 3.0
040 */
041public class NodeCachingLinkedList<E> extends AbstractLinkedList<E> implements Serializable {
042
043    /** Serialization version */
044    private static final long serialVersionUID = 6897789178562232073L;
045
046    /**
047     * The default value for {@link #maximumCacheSize}.
048     */
049    private static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20;
050
051    /**
052     * The first cached node, or <code>null</code> if no nodes are cached.
053     * Cached nodes are stored in a singly-linked list with
054     * <code>next</code> pointing to the next element.
055     */
056    private transient Node<E> firstCachedNode;
057
058    /**
059     * The size of the cache.
060     */
061    private transient int cacheSize;
062
063    /**
064     * The maximum size of the cache.
065     */
066    private int maximumCacheSize;
067
068    //-----------------------------------------------------------------------
069    /**
070     * Constructor that creates.
071     */
072    public NodeCachingLinkedList() {
073        this(DEFAULT_MAXIMUM_CACHE_SIZE);
074    }
075
076    /**
077     * Constructor that copies the specified collection
078     *
079     * @param coll  the collection to copy
080     */
081    public NodeCachingLinkedList(final Collection<? extends E> coll) {
082        super(coll);
083        this.maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE;
084    }
085
086    /**
087     * Constructor that species the maximum cache size.
088     *
089     * @param maximumCacheSize  the maximum cache size
090     */
091    public NodeCachingLinkedList(final int maximumCacheSize) {
092        super();
093        this.maximumCacheSize = maximumCacheSize;
094        init();  // must call init() as use super();
095    }
096
097    //-----------------------------------------------------------------------
098    /**
099     * Gets the maximum size of the cache.
100     *
101     * @return the maximum cache size
102     */
103    protected int getMaximumCacheSize() {
104        return maximumCacheSize;
105    }
106
107    /**
108     * Sets the maximum size of the cache.
109     *
110     * @param maximumCacheSize  the new maximum cache size
111     */
112    protected void setMaximumCacheSize(final int maximumCacheSize) {
113        this.maximumCacheSize = maximumCacheSize;
114        shrinkCacheToMaximumSize();
115    }
116
117    /**
118     * Reduce the size of the cache to the maximum, if necessary.
119     */
120    protected void shrinkCacheToMaximumSize() {
121        // Rich Dougherty: This could be more efficient.
122        while (cacheSize > maximumCacheSize) {
123            getNodeFromCache();
124        }
125    }
126
127    /**
128     * Gets a node from the cache. If a node is returned, then the value of
129     * {@link #cacheSize} is decreased accordingly. The node that is returned
130     * will have <code>null</code> values for next, previous and element.
131     *
132     * @return a node, or <code>null</code> if there are no nodes in the cache.
133     */
134    protected Node<E> getNodeFromCache() {
135        if (cacheSize == 0) {
136            return null;
137        }
138        final Node<E> cachedNode = firstCachedNode;
139        firstCachedNode = cachedNode.next;
140        cachedNode.next = null; // This should be changed anyway, but defensively
141                                // set it to null.
142        cacheSize--;
143        return cachedNode;
144    }
145
146    /**
147     * Checks whether the cache is full.
148     *
149     * @return true if the cache is full
150     */
151    protected boolean isCacheFull() {
152        return cacheSize >= maximumCacheSize;
153    }
154
155    /**
156     * Adds a node to the cache, if the cache isn't full.
157     * The node's contents are cleared to so they can be garbage collected.
158     *
159     * @param node  the node to add to the cache
160     */
161    protected void addNodeToCache(final Node<E> node) {
162        if (isCacheFull()) {
163            // don't cache the node.
164            return;
165        }
166        // clear the node's contents and add it to the cache.
167        final Node<E> nextCachedNode = firstCachedNode;
168        node.previous = null;
169        node.next = nextCachedNode;
170        node.setValue(null);
171        firstCachedNode = node;
172        cacheSize++;
173    }
174
175    //-----------------------------------------------------------------------
176    /**
177     * Creates a new node, either by reusing one from the cache or creating
178     * a new one.
179     *
180     * @param value  value of the new node
181     * @return the newly created node
182     */
183    @Override
184    protected Node<E> createNode(final E value) {
185        final Node<E> cachedNode = getNodeFromCache();
186        if (cachedNode == null) {
187            return super.createNode(value);
188        }
189        cachedNode.setValue(value);
190        return cachedNode;
191    }
192
193    /**
194     * Removes the node from the list, storing it in the cache for reuse
195     * if the cache is not yet full.
196     *
197     * @param node  the node to remove
198     */
199    @Override
200    protected void removeNode(final Node<E> node) {
201        super.removeNode(node);
202        addNodeToCache(node);
203    }
204
205    /**
206     * Removes all the nodes from the list, storing as many as required in the
207     * cache for reuse.
208     *
209     */
210    @Override
211    protected void removeAllNodes() {
212        // Add the removed nodes to the cache, then remove the rest.
213        // We can add them to the cache before removing them, since
214        // {@link AbstractLinkedList.removeAllNodes()} removes the
215        // nodes by removing references directly from {@link #header}.
216        final int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize);
217        Node<E> node = header.next;
218        for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) {
219            final Node<E> oldNode = node;
220            node = node.next;
221            addNodeToCache(oldNode);
222        }
223        super.removeAllNodes();
224    }
225
226    //-----------------------------------------------------------------------
227    /**
228     * Serializes the data held in this object to the stream specified.
229     *
230     * @param out  the output stream
231     * @throws IOException if an error occurs while writing to the stream
232     */
233    private void writeObject(final ObjectOutputStream out) throws IOException {
234        out.defaultWriteObject();
235        doWriteObject(out);
236    }
237
238    /**
239     * Deserializes the data held in this object to the stream specified.
240     *
241     * @param in  the input stream
242     * @throws IOException if an error occurs while reading from the stream
243     * @throws ClassNotFoundException if an object read from the stream can not be loaded
244     */
245    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
246        in.defaultReadObject();
247        doReadObject(in);
248    }
249
250}