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.collections.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 * This implementation is suitable for long-lived lists where both add and remove
34 * are used. Short-lived lists, or lists which only grow will have worse performance
35 * using this class.
36 * <p>
37 * <b>Note that this implementation is not synchronized.</b>
38 *
39 * @since 3.0
40 * @version $Id: NodeCachingLinkedList.java 1429905 2013-01-07 17:15:14Z ggregory $
41 */
42 public class NodeCachingLinkedList<E> extends AbstractLinkedList<E> implements Serializable {
43
44 /** Serialization version */
45 private static final long serialVersionUID = 6897789178562232073L;
46
47 /**
48 * The default value for {@link #maximumCacheSize}.
49 */
50 protected static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20;
51
52 /**
53 * The first cached node, or <code>null</code> if no nodes are cached.
54 * Cached nodes are stored in a singly-linked list with
55 * <code>next</code> pointing to the next element.
56 */
57 protected transient Node<E> firstCachedNode;
58
59 /**
60 * The size of the cache.
61 */
62 protected transient int cacheSize;
63
64 /**
65 * The maximum size of the cache.
66 */
67 protected int maximumCacheSize;
68
69 //-----------------------------------------------------------------------
70 /**
71 * Constructor that creates.
72 */
73 public NodeCachingLinkedList() {
74 this(DEFAULT_MAXIMUM_CACHE_SIZE);
75 }
76
77 /**
78 * Constructor that copies the specified collection
79 *
80 * @param coll the collection to copy
81 */
82 public NodeCachingLinkedList(final Collection<E> coll) {
83 super(coll);
84 this.maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE;
85 }
86
87 /**
88 * Constructor that species the maximum cache size.
89 *
90 * @param maximumCacheSize the maximum cache size
91 */
92 public NodeCachingLinkedList(final int maximumCacheSize) {
93 super();
94 this.maximumCacheSize = maximumCacheSize;
95 init(); // must call init() as use super();
96 }
97
98 //-----------------------------------------------------------------------
99 /**
100 * Gets the maximum size of the cache.
101 *
102 * @return the maximum cache size
103 */
104 protected int getMaximumCacheSize() {
105 return maximumCacheSize;
106 }
107
108 /**
109 * Sets the maximum size of the cache.
110 *
111 * @param maximumCacheSize the new maximum cache size
112 */
113 protected void setMaximumCacheSize(final int maximumCacheSize) {
114 this.maximumCacheSize = maximumCacheSize;
115 shrinkCacheToMaximumSize();
116 }
117
118 /**
119 * Reduce the size of the cache to the maximum, if necessary.
120 */
121 protected void shrinkCacheToMaximumSize() {
122 // Rich Dougherty: This could be more efficient.
123 while (cacheSize > maximumCacheSize) {
124 getNodeFromCache();
125 }
126 }
127
128 /**
129 * Gets a node from the cache. If a node is returned, then the value of
130 * {@link #cacheSize} is decreased accordingly. The node that is returned
131 * will have <code>null</code> values for next, previous and element.
132 *
133 * @return a node, or <code>null</code> if there are no nodes in the cache.
134 */
135 protected Node<E> getNodeFromCache() {
136 if (cacheSize == 0) {
137 return null;
138 }
139 final Node<E> cachedNode = firstCachedNode;
140 firstCachedNode = cachedNode.next;
141 cachedNode.next = null; // This should be changed anyway, but defensively
142 // set it to null.
143 cacheSize--;
144 return cachedNode;
145 }
146
147 /**
148 * Checks whether the cache is full.
149 *
150 * @return true if the cache is full
151 */
152 protected boolean isCacheFull() {
153 return cacheSize >= maximumCacheSize;
154 }
155
156 /**
157 * Adds a node to the cache, if the cache isn't full.
158 * The node's contents are cleared to so they can be garbage collected.
159 *
160 * @param node the node to add to the cache
161 */
162 protected void addNodeToCache(final Node<E> node) {
163 if (isCacheFull()) {
164 // don't cache the node.
165 return;
166 }
167 // clear the node's contents and add it to the cache.
168 final Node<E> nextCachedNode = firstCachedNode;
169 node.previous = null;
170 node.next = nextCachedNode;
171 node.setValue(null);
172 firstCachedNode = node;
173 cacheSize++;
174 }
175
176 //-----------------------------------------------------------------------
177 /**
178 * Creates a new node, either by reusing one from the cache or creating
179 * a new one.
180 *
181 * @param value value of the new node
182 * @return the newly created node
183 */
184 @Override
185 protected Node<E> createNode(final E value) {
186 final Node<E> cachedNode = getNodeFromCache();
187 if (cachedNode == null) {
188 return super.createNode(value);
189 }
190 cachedNode.setValue(value);
191 return cachedNode;
192 }
193
194 /**
195 * Removes the node from the list, storing it in the cache for reuse
196 * if the cache is not yet full.
197 *
198 * @param node the node to remove
199 */
200 @Override
201 protected void removeNode(final Node<E> node) {
202 super.removeNode(node);
203 addNodeToCache(node);
204 }
205
206 /**
207 * Removes all the nodes from the list, storing as many as required in the
208 * cache for reuse.
209 *
210 */
211 @Override
212 protected void removeAllNodes() {
213 // Add the removed nodes to the cache, then remove the rest.
214 // We can add them to the cache before removing them, since
215 // {@link AbstractLinkedList.removeAllNodes()} removes the
216 // nodes by removing references directly from {@link #header}.
217 final int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize);
218 Node<E> node = header.next;
219 for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) {
220 final Node<E> oldNode = node;
221 node = node.next;
222 addNodeToCache(oldNode);
223 }
224 super.removeAllNodes();
225 }
226
227 //-----------------------------------------------------------------------
228 /**
229 * Serializes the data held in this object to the stream specified.
230 */
231 private void writeObject(final ObjectOutputStream out) throws IOException {
232 out.defaultWriteObject();
233 doWriteObject(out);
234 }
235
236 /**
237 * Deserializes the data held in this object to the stream specified.
238 */
239 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
240 in.defaultReadObject();
241 doReadObject(in);
242 }
243
244 }