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