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