1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package net.sf.collections15.list;
17
18 import java.io.IOException;
19 import java.io.ObjectInputStream;
20 import java.io.ObjectOutputStream;
21 import java.io.Serializable;
22 import java.util.Collection;
23
24 /***
25 * A <code>List</code> implementation that stores a cache of internal Node objects
26 * in an effort to reduce wasteful object creation.
27 * <p>
28 * A linked list creates one Node for each item of data added. This can result in
29 * a lot of object creation and garbage collection. This implementation seeks to
30 * avoid that by maintaining a store of cached nodes.
31 * <p>
32 * This implementation is suitable for long-lived lists where both add and remove
33 * are used. Short-lived lists, or lists which only grow will have worse performance
34 * using this class.
35 * <p>
36 * <b>Note that this implementation is not synchronized.</b>
37 *
38 * @since Commons Collections 3.0
39 * @version $Revision: 1.1 $ $Date: 2005/05/03 22:45:38 $
40 *
41 * @author Jeff Varszegi
42 * @author Rich Dougherty
43 * @author Phil Steitz
44 * @author Stephen Colebourne
45 */
46 public class NodeCachingLinkedList<E> extends AbstractLinkedList<E> implements Serializable {
47
48 /*** Serialization version */
49 private static final long serialVersionUID = 4050761580998244661L;
50
51 /***
52 * The default value for {@link #maximumCacheSize}.
53 */
54 protected static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20;
55
56 /***
57 * The first cached node, or <code>null</code> if no nodes are cached.
58 * Cached nodes are stored in a singly-linked list with
59 * <code>next</code> pointing to the next element.
60 */
61 protected transient Node<E> firstCachedNode;
62
63 /***
64 * The size of the cache.
65 */
66 protected transient int cacheSize;
67
68 /***
69 * The maximum size of the cache.
70 */
71 protected int maximumCacheSize;
72
73
74 /***
75 * Constructor that creates.
76 */
77 public NodeCachingLinkedList() {
78 this(DEFAULT_MAXIMUM_CACHE_SIZE);
79 }
80
81 /***
82 * Constructor that copies the specified collection
83 *
84 * @param coll the collection to copy
85 */
86 public NodeCachingLinkedList(Collection<E> coll) {
87 super(coll);
88 this.maximumCacheSize = DEFAULT_MAXIMUM_CACHE_SIZE;
89 }
90
91 /***
92 * Constructor that species the maximum cache size.
93 *
94 * @param maximumCacheSize the maximum cache size
95 */
96 public NodeCachingLinkedList(int maximumCacheSize) {
97 super();
98 this.maximumCacheSize = maximumCacheSize;
99 init();
100 }
101
102
103 /***
104 * Gets the maximum size of the cache.
105 *
106 * @return the maximum cache size
107 */
108 protected int getMaximumCacheSize() {
109 return maximumCacheSize;
110 }
111
112 /***
113 * Sets the maximum size of the cache.
114 *
115 * @param maximumCacheSize the new maximum cache size
116 */
117 protected void setMaximumCacheSize(int maximumCacheSize) {
118 this.maximumCacheSize = maximumCacheSize;
119 shrinkCacheToMaximumSize();
120 }
121
122 /***
123 * Reduce the size of the cache to the maximum, if necessary.
124 */
125 protected void shrinkCacheToMaximumSize() {
126
127 while (cacheSize > maximumCacheSize) {
128 getNodeFromCache();
129 }
130 }
131
132 /***
133 * Gets a node from the cache. If a node is returned, then the value of
134 * {@link #cacheSize} is decreased accordingly. The node that is returned
135 * will have <code>null</code> values for next, previous and element.
136 *
137 * @return a node, or <code>null</code> if there are no nodes in the cache.
138 */
139 protected Node<E> getNodeFromCache() {
140 if (cacheSize == 0) {
141 return null;
142 }
143 Node<E> cachedNode = firstCachedNode;
144 firstCachedNode = cachedNode.next;
145 cachedNode.next = null;
146
147 cacheSize--;
148 return cachedNode;
149 }
150
151 /***
152 * Checks whether the cache is full.
153 *
154 * @return true if the cache is full
155 */
156 protected boolean isCacheFull() {
157 return cacheSize >= maximumCacheSize;
158 }
159
160 /***
161 * Adds a node to the cache, if the cache isn't full.
162 * The node's contents are cleared to so they can be garbage collected.
163 *
164 * @param node the node to add to the cache
165 */
166 protected void addNodeToCache(Node<E> node) {
167 if (isCacheFull()) {
168
169 return;
170 }
171
172 Node<E> nextCachedNode = firstCachedNode;
173 node.previous = null;
174 node.next = nextCachedNode;
175 node.setValue(null);
176 firstCachedNode = node;
177 cacheSize++;
178 }
179
180
181 /***
182 * Creates a new node, either by reusing one from the cache or creating
183 * a new one.
184 *
185 * @param value value of the new node
186 * @return the newly created node
187 */
188 protected Node<E> createNode(E value) {
189 Node<E> cachedNode = getNodeFromCache();
190 if (cachedNode == null) {
191 return super.createNode(value);
192 } else {
193 cachedNode.setValue(value);
194 return cachedNode;
195 }
196 }
197
198 /***
199 * Removes the node from the list, storing it in the cache for reuse
200 * if the cache is not yet full.
201 *
202 * @param node the node to remove
203 */
204 protected void removeNode(Node<E> node) {
205 super.removeNode(node);
206 addNodeToCache(node);
207 }
208
209 /***
210 * Removes all the nodes from the list, storing as many as required in the
211 * cache for reuse.
212 *
213 */
214 protected void removeAllNodes() {
215
216
217
218
219 int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize);
220 Node<E> node = header.next;
221 for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) {
222 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 private void writeObject(ObjectOutputStream out) throws IOException {
234 out.defaultWriteObject();
235 doWriteObject(out);
236 }
237
238 /***
239 * Deserializes the data held in this object to the stream specified.
240 */
241 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
242 in.defaultReadObject();
243 doReadObject(in);
244 }
245
246 }