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}