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