KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > commons > collections > list > NodeCachingLinkedList


1 /*
2  * Copyright 2001-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections.list;
17
18 import java.io.IOException JavaDoc;
19 import java.io.ObjectInputStream JavaDoc;
20 import java.io.ObjectOutputStream JavaDoc;
21 import java.io.Serializable JavaDoc;
22 import java.util.Collection JavaDoc;
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.7 $ $Date: 2004/04/20 23:46:50 $
40  *
41  * @author Jeff Varszegi
42  * @author Rich Dougherty
43  * @author Phil Steitz
44  * @author Stephen Colebourne
45  */
46 public class NodeCachingLinkedList extends AbstractLinkedList implements Serializable JavaDoc {
47
48     /** Serialization version */
49     static final long serialVersionUID = 6897789178562232073L;
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 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 JavaDoc 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(); // must call init() as use super();
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         // Rich Dougherty: This could be more efficient.
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 getNodeFromCache() {
140         if (cacheSize == 0) {
141             return null;
142         }
143         Node cachedNode = firstCachedNode;
144         firstCachedNode = cachedNode.next;
145         cachedNode.next = null; // This should be changed anyway, but defensively
146 // set it to null.
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 node) {
167         if (isCacheFull()) {
168             // don't cache the node.
169 return;
170         }
171         // clear the node's contents and add it to the cache.
172 Node 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 createNode(Object JavaDoc value) {
189         Node 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 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         // Add the removed nodes to the cache, then remove the rest.
216 // We can add them to the cache before removing them, since
217 // {@link AbstractLinkedList.removeAllNodes()} removes the
218 // nodes by removing references directly from {@link #header}.
219 int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize);
220         Node node = header.next;
221         for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) {
222             Node 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 JavaDoc out) throws IOException JavaDoc {
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 JavaDoc in) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
242         in.defaultReadObject();
243         doReadObject(in);
244     }
245
246 }
247
Popular Tags