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 }