001: /*
002: * Copyright 2001-2005 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.list;
017:
018: import java.io.IOException;
019: import java.io.ObjectInputStream;
020: import java.io.ObjectOutputStream;
021: import java.io.Serializable;
022: import java.util.Collection;
023:
024: /**
025: * A <code>List</code> implementation that stores a cache of internal Node objects
026: * in an effort to reduce wasteful object creation.
027: * <p>
028: * A linked list creates one Node for each item of data added. This can result in
029: * a lot of object creation and garbage collection. This implementation seeks to
030: * avoid that by maintaining a store of cached nodes.
031: * <p>
032: * This implementation is suitable for long-lived lists where both add and remove
033: * are used. Short-lived lists, or lists which only grow will have worse performance
034: * using this class.
035: * <p>
036: * <b>Note that this implementation is not synchronized.</b>
037: *
038: * @since Commons Collections 3.0
039: * @version $Revision: 348299 $ $Date: 2005-11-22 23:51:45 +0000 (Tue, 22 Nov 2005) $
040: *
041: * @author Jeff Varszegi
042: * @author Rich Dougherty
043: * @author Phil Steitz
044: * @author Stephen Colebourne
045: */
046: public class NodeCachingLinkedList extends AbstractLinkedList implements
047: 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
221: - cacheSize);
222: Node node = header.next;
223: for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) {
224: Node oldNode = node;
225: node = node.next;
226: addNodeToCache(oldNode);
227: }
228: super .removeAllNodes();
229: }
230:
231: //-----------------------------------------------------------------------
232: /**
233: * Serializes the data held in this object to the stream specified.
234: */
235: private void writeObject(ObjectOutputStream out) throws IOException {
236: out.defaultWriteObject();
237: doWriteObject(out);
238: }
239:
240: /**
241: * Deserializes the data held in this object to the stream specified.
242: */
243: private void readObject(ObjectInputStream in) throws IOException,
244: ClassNotFoundException {
245: in.defaultReadObject();
246: doReadObject(in);
247: }
248:
249: }
|