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