1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.collections4.list; 18 19 import java.io.IOException; 20 import java.io.ObjectInputStream; 21 import java.io.ObjectOutputStream; 22 import java.io.Serializable; 23 import java.util.Collection; 24 25 /** 26 * A {@code List} implementation that stores a cache of internal Node objects 27 * in an effort to reduce wasteful object creation. 28 * <p> 29 * A linked list creates one Node for each item of data added. This can result in 30 * a lot of object creation and garbage collection. This implementation seeks to 31 * avoid that by maintaining a store of cached nodes. 32 * </p> 33 * <p> 34 * This implementation is suitable for long-lived lists where both add and remove 35 * are used. Short-lived lists, or lists which only grow will have worse performance 36 * using this class. 37 * </p> 38 * <p> 39 * <b>Note that this implementation is not synchronized.</b> 40 * </p> 41 * 42 * @since 3.0 43 */ 44 public class NodeCachingLinkedList<E> extends AbstractLinkedList<E> implements Serializable { 45 46 /** Serialization version */ 47 private static final long serialVersionUID = 6897789178562232073L; 48 49 /** 50 * The default value for {@link #maximumCacheSize}. 51 */ 52 private static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20; 53 54 /** 55 * The first cached node, or {@code null} if no nodes are cached. 56 * Cached nodes are stored in a singly-linked list with 57 * {@code next} pointing to the next element. 58 */ 59 private transient Node<E> firstCachedNode; 60 61 /** 62 * The size of the cache. 63 */ 64 private transient int cacheSize; 65 66 /** 67 * The maximum size of the cache. 68 */ 69 private int maximumCacheSize; 70 71 /** 72 * Constructor that creates. 73 */ 74 public NodeCachingLinkedList() { 75 this(DEFAULT_MAXIMUM_CACHE_SIZE); 76 } 77 78 /** 79 * Constructor that copies the specified collection 80 * 81 * @param coll the collection to copy 82 */ 83 public NodeCachingLinkedList(final Collection<? extends E> coll) { 84 super(coll); 85 this.maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE; 86 } 87 88 /** 89 * Constructor that species the maximum cache size. 90 * 91 * @param maximumCacheSize the maximum cache size 92 */ 93 public NodeCachingLinkedList(final int maximumCacheSize) { 94 this.maximumCacheSize = maximumCacheSize; 95 init(); // must call init() as use super(); 96 } 97 98 /** 99 * Adds a node to the cache, if the cache isn't full. 100 * The node's contents are cleared, so they can be garbage collected. 101 * 102 * @param node the node to add to the cache 103 */ 104 protected void addNodeToCache(final Node<E> node) { 105 if (isCacheFull()) { 106 // don't cache the node. 107 return; 108 } 109 // clear the node's contents and add it to the cache. 110 final Node<E> nextCachedNode = firstCachedNode; 111 node.previous = null; 112 node.next = nextCachedNode; 113 node.setValue(null); 114 firstCachedNode = node; 115 cacheSize++; 116 } 117 118 /** 119 * Creates a new node, either by reusing one from the cache or creating 120 * a new one. 121 * 122 * @param value value of the new node 123 * @return the newly created node 124 */ 125 @Override 126 protected Node<E> createNode(final E value) { 127 final Node<E> cachedNode = getNodeFromCache(); 128 if (cachedNode == null) { 129 return super.createNode(value); 130 } 131 cachedNode.setValue(value); 132 return cachedNode; 133 } 134 135 /** 136 * Gets the maximum size of the cache. 137 * 138 * @return the maximum cache size 139 */ 140 protected int getMaximumCacheSize() { 141 return maximumCacheSize; 142 } 143 144 /** 145 * Gets a node from the cache. If a node is returned, then the value of 146 * {@link #cacheSize} is decreased accordingly. The node that is returned 147 * will have {@code null} values for next, previous and element. 148 * 149 * @return a node, or {@code null} if there are no nodes in the cache. 150 */ 151 protected Node<E> getNodeFromCache() { 152 if (cacheSize == 0) { 153 return null; 154 } 155 final Node<E> cachedNode = firstCachedNode; 156 firstCachedNode = cachedNode.next; 157 cachedNode.next = null; // This should be changed anyway, but defensively 158 // set it to null. 159 cacheSize--; 160 return cachedNode; 161 } 162 163 /** 164 * Checks whether the cache is full. 165 * 166 * @return true if the cache is full 167 */ 168 protected boolean isCacheFull() { 169 return cacheSize >= maximumCacheSize; 170 } 171 172 /** 173 * Deserializes the data held in this object to the stream specified. 174 * 175 * @param in the input stream 176 * @throws IOException if an error occurs while reading from the stream 177 * @throws ClassNotFoundException if an object read from the stream can not be loaded 178 */ 179 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { 180 in.defaultReadObject(); 181 doReadObject(in); 182 } 183 184 /** 185 * Removes all the nodes from the list, storing as many as required in the 186 * cache for reuse. 187 */ 188 @Override 189 protected void removeAllNodes() { 190 // Add the removed nodes to the cache, then remove the rest. 191 // We can add them to the cache before removing them, since 192 // {@link AbstractLinkedList.removeAllNodes()} removes the 193 // nodes by removing references directly from {@link #header}. 194 final int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize); 195 Node<E> node = header.next; 196 for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) { 197 final Node<E> oldNode = node; 198 node = node.next; 199 addNodeToCache(oldNode); 200 } 201 super.removeAllNodes(); 202 } 203 204 /** 205 * Removes the node from the list, storing it in the cache for reuse 206 * if the cache is not yet full. 207 * 208 * @param node the node to remove 209 */ 210 @Override 211 protected void removeNode(final Node<E> node) { 212 super.removeNode(node); 213 addNodeToCache(node); 214 } 215 216 /** 217 * Sets the maximum size of the cache. 218 * 219 * @param maximumCacheSize the new maximum cache size 220 */ 221 protected void setMaximumCacheSize(final int maximumCacheSize) { 222 this.maximumCacheSize = maximumCacheSize; 223 shrinkCacheToMaximumSize(); 224 } 225 226 /** 227 * Reduce the size of the cache to the maximum, if necessary. 228 */ 229 protected void shrinkCacheToMaximumSize() { 230 // Rich Dougherty: This could be more efficient. 231 while (cacheSize > maximumCacheSize) { 232 getNodeFromCache(); 233 } 234 } 235 236 /** 237 * Serializes the data held in this object to the stream specified. 238 * 239 * @param out the output stream 240 * @throws IOException if an error occurs while writing to the stream 241 */ 242 private void writeObject(final ObjectOutputStream out) throws IOException { 243 out.defaultWriteObject(); 244 doWriteObject(out); 245 } 246 247 }