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</code> 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</code> if no nodes are cached. 56 * Cached nodes are stored in a singly-linked list with 57 * <code>next</code> 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 /** 73 * Constructor that creates. 74 */ 75 public NodeCachingLinkedList() { 76 this(DEFAULT_MAXIMUM_CACHE_SIZE); 77 } 78 79 /** 80 * Constructor that copies the specified collection 81 * 82 * @param coll the collection to copy 83 */ 84 public NodeCachingLinkedList(final Collection<? extends E> coll) { 85 super(coll); 86 this.maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE; 87 } 88 89 /** 90 * Constructor that species the maximum cache size. 91 * 92 * @param maximumCacheSize the maximum cache size 93 */ 94 public NodeCachingLinkedList(final int maximumCacheSize) { 95 super(); 96 this.maximumCacheSize = maximumCacheSize; 97 init(); // must call init() as use super(); 98 } 99 100 //----------------------------------------------------------------------- 101 /** 102 * Gets the maximum size of the cache. 103 * 104 * @return the maximum cache size 105 */ 106 protected int getMaximumCacheSize() { 107 return maximumCacheSize; 108 } 109 110 /** 111 * Sets the maximum size of the cache. 112 * 113 * @param maximumCacheSize the new maximum cache size 114 */ 115 protected void setMaximumCacheSize(final int maximumCacheSize) { 116 this.maximumCacheSize = maximumCacheSize; 117 shrinkCacheToMaximumSize(); 118 } 119 120 /** 121 * Reduce the size of the cache to the maximum, if necessary. 122 */ 123 protected void shrinkCacheToMaximumSize() { 124 // Rich Dougherty: This could be more efficient. 125 while (cacheSize > maximumCacheSize) { 126 getNodeFromCache(); 127 } 128 } 129 130 /** 131 * Gets a node from the cache. If a node is returned, then the value of 132 * {@link #cacheSize} is decreased accordingly. The node that is returned 133 * will have <code>null</code> values for next, previous and element. 134 * 135 * @return a node, or <code>null</code> if there are no nodes in the cache. 136 */ 137 protected Node<E> getNodeFromCache() { 138 if (cacheSize == 0) { 139 return null; 140 } 141 final Node<E> cachedNode = firstCachedNode; 142 firstCachedNode = cachedNode.next; 143 cachedNode.next = null; // This should be changed anyway, but defensively 144 // set it to null. 145 cacheSize--; 146 return cachedNode; 147 } 148 149 /** 150 * Checks whether the cache is full. 151 * 152 * @return true if the cache is full 153 */ 154 protected boolean isCacheFull() { 155 return cacheSize >= maximumCacheSize; 156 } 157 158 /** 159 * Adds a node to the cache, if the cache isn't full. 160 * The node's contents are cleared to so they can be garbage collected. 161 * 162 * @param node the node to add to the cache 163 */ 164 protected void addNodeToCache(final Node<E> node) { 165 if (isCacheFull()) { 166 // don't cache the node. 167 return; 168 } 169 // clear the node's contents and add it to the cache. 170 final Node<E> nextCachedNode = firstCachedNode; 171 node.previous = null; 172 node.next = nextCachedNode; 173 node.setValue(null); 174 firstCachedNode = node; 175 cacheSize++; 176 } 177 178 //----------------------------------------------------------------------- 179 /** 180 * Creates a new node, either by reusing one from the cache or creating 181 * a new one. 182 * 183 * @param value value of the new node 184 * @return the newly created node 185 */ 186 @Override 187 protected Node<E> createNode(final E value) { 188 final Node<E> cachedNode = getNodeFromCache(); 189 if (cachedNode == null) { 190 return super.createNode(value); 191 } 192 cachedNode.setValue(value); 193 return cachedNode; 194 } 195 196 /** 197 * Removes the node from the list, storing it in the cache for reuse 198 * if the cache is not yet full. 199 * 200 * @param node the node to remove 201 */ 202 @Override 203 protected void removeNode(final Node<E> node) { 204 super.removeNode(node); 205 addNodeToCache(node); 206 } 207 208 /** 209 * Removes all the nodes from the list, storing as many as required in the 210 * cache for reuse. 211 * 212 */ 213 @Override 214 protected void removeAllNodes() { 215 // Add the removed nodes to the cache, then remove the rest. 216 // We can add them to the cache before removing them, since 217 // {@link AbstractLinkedList.removeAllNodes()} removes the 218 // nodes by removing references directly from {@link #header}. 219 final int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize); 220 Node<E> node = header.next; 221 for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) { 222 final Node<E> oldNode = node; 223 node = node.next; 224 addNodeToCache(oldNode); 225 } 226 super.removeAllNodes(); 227 } 228 229 //----------------------------------------------------------------------- 230 /** 231 * Serializes the data held in this object to the stream specified. 232 * 233 * @param out the output stream 234 * @throws IOException if an error occurs while writing to the stream 235 */ 236 private void writeObject(final ObjectOutputStream out) throws IOException { 237 out.defaultWriteObject(); 238 doWriteObject(out); 239 } 240 241 /** 242 * Deserializes the data held in this object to the stream specified. 243 * 244 * @param in the input stream 245 * @throws IOException if an error occurs while reading from the stream 246 * @throws ClassNotFoundException if an object read from the stream can not be loaded 247 */ 248 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { 249 in.defaultReadObject(); 250 doReadObject(in); 251 } 252 253 }