    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}