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 */ 044public class NodeCachingLinkedList<E> extends AbstractLinkedList<E> implements Serializable { 045 046 /** Serialization version */ 047 private static final long serialVersionUID = 6897789178562232073L; 048 049 /** 050 * The default value for {@link #maximumCacheSize}. 051 */ 052 private static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20; 053 054 /** 055 * The first cached node, or {@code null} if no nodes are cached. 056 * Cached nodes are stored in a singly-linked list with 057 * {@code next} pointing to the next element. 058 */ 059 private transient Node<E> firstCachedNode; 060 061 /** 062 * The size of the cache. 063 */ 064 private transient int cacheSize; 065 066 /** 067 * The maximum size of the cache. 068 */ 069 private int maximumCacheSize; 070 071 /** 072 * Constructor that creates. 073 */ 074 public NodeCachingLinkedList() { 075 this(DEFAULT_MAXIMUM_CACHE_SIZE); 076 } 077 078 /** 079 * Constructor that copies the specified collection 080 * 081 * @param coll the collection to copy 082 */ 083 public NodeCachingLinkedList(final Collection<? extends E> coll) { 084 super(coll); 085 this.maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE; 086 } 087 088 /** 089 * Constructor that species the maximum cache size. 090 * 091 * @param maximumCacheSize the maximum cache size 092 */ 093 public NodeCachingLinkedList(final int maximumCacheSize) { 094 this.maximumCacheSize = maximumCacheSize; 095 init(); // must call init() as use super(); 096 } 097 098 /** 099 * 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}