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    }