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