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} 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 * <strong>Note that this implementation is not synchronized.</strong>
40 * </p>
41 *
42 * @param <E> the type of the elements in the list.
43 * @since 3.0
44 * @deprecated parent {@link AbstractLinkedList} is source incompatible with List methods added in Java 21
45 */
46 @Deprecated
47 public class NodeCachingLinkedList<E> extends AbstractLinkedList<E> implements Serializable {
48
49 /** Serialization version */
50 private static final long serialVersionUID = 6897789178562232073L;
51
52 /**
53 * The default value for {@link #maximumCacheSize}.
54 */
55 private static final int DEFAULT_MAXIMUM_CACHE_SIZE = 20;
56
57 /**
58 * The first cached node, or {@code null} if no nodes are cached.
59 * Cached nodes are stored in a singly-linked list with
60 * {@code next} pointing to the next element.
61 */
62 private transient Node<E> firstCachedNode;
63
64 /**
65 * The size of the cache.
66 */
67 private transient int cacheSize;
68
69 /**
70 * The maximum size of the cache.
71 */
72 private int maximumCacheSize;
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(final Collection<? extends 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(final int maximumCacheSize) {
97 this.maximumCacheSize = maximumCacheSize;
98 init(); // must call init() as use super();
99 }
100
101 /**
102 * Adds a node to the cache, if the cache isn't full.
103 * The node's contents are cleared, so they can be garbage collected.
104 *
105 * @param node the node to add to the cache
106 */
107 protected void addNodeToCache(final Node<E> node) {
108 if (isCacheFull()) {
109 // don't cache the node.
110 return;
111 }
112 // clear the node's contents and add it to the cache.
113 final Node<E> nextCachedNode = firstCachedNode;
114 node.previous = null;
115 node.next = nextCachedNode;
116 node.setValue(null);
117 firstCachedNode = node;
118 cacheSize++;
119 }
120
121 /**
122 * Creates a new node, either by reusing one from the cache or creating
123 * a new one.
124 *
125 * @param value value of the new node
126 * @return the newly created node
127 */
128 @Override
129 protected Node<E> createNode(final E value) {
130 final Node<E> cachedNode = getNodeFromCache();
131 if (cachedNode == null) {
132 return super.createNode(value);
133 }
134 cachedNode.setValue(value);
135 return cachedNode;
136 }
137
138 /**
139 * Gets the maximum size of the cache.
140 *
141 * @return the maximum cache size
142 */
143 protected int getMaximumCacheSize() {
144 return maximumCacheSize;
145 }
146
147 /**
148 * Gets a node from the cache. If a node is returned, then the value of
149 * {@link #cacheSize} is decreased accordingly. The node that is returned
150 * will have {@code null} values for next, previous and element.
151 *
152 * @return a node, or {@code null} if there are no nodes in the cache.
153 */
154 protected Node<E> getNodeFromCache() {
155 if (cacheSize == 0) {
156 return null;
157 }
158 final Node<E> cachedNode = firstCachedNode;
159 firstCachedNode = cachedNode.next;
160 cachedNode.next = null; // This should be changed anyway, but defensively
161 // set it to null.
162 cacheSize--;
163 return cachedNode;
164 }
165
166 /**
167 * Checks whether the cache is full.
168 *
169 * @return true if the cache is full
170 */
171 protected boolean isCacheFull() {
172 return cacheSize >= maximumCacheSize;
173 }
174
175 /**
176 * Deserializes the data held in this object to the stream specified.
177 *
178 * @param in the input stream
179 * @throws IOException if an error occurs while reading from the stream
180 * @throws ClassNotFoundException if an object read from the stream cannot be loaded
181 */
182 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
183 in.defaultReadObject();
184 doReadObject(in);
185 }
186
187 /**
188 * Removes all the nodes from the list, storing as many as required in the
189 * cache for reuse.
190 */
191 @Override
192 protected void removeAllNodes() {
193 // Add the removed nodes to the cache, then remove the rest.
194 // We can add them to the cache before removing them, since
195 // {@link AbstractLinkedList.removeAllNodes()} removes the
196 // nodes by removing references directly from {@link #header}.
197 final int numberOfNodesToCache = Math.min(size, maximumCacheSize - cacheSize);
198 Node<E> node = header.next;
199 for (int currentIndex = 0; currentIndex < numberOfNodesToCache; currentIndex++) {
200 final Node<E> oldNode = node;
201 node = node.next;
202 addNodeToCache(oldNode);
203 }
204 super.removeAllNodes();
205 }
206
207 /**
208 * Removes the node from the list, storing it in the cache for reuse
209 * if the cache is not yet full.
210 *
211 * @param node the node to remove
212 */
213 @Override
214 protected void removeNode(final Node<E> node) {
215 super.removeNode(node);
216 addNodeToCache(node);
217 }
218
219 /**
220 * Sets the maximum size of the cache.
221 *
222 * @param maximumCacheSize the new maximum cache size
223 */
224 protected void setMaximumCacheSize(final int maximumCacheSize) {
225 this.maximumCacheSize = maximumCacheSize;
226 shrinkCacheToMaximumSize();
227 }
228
229 /**
230 * Reduce the size of the cache to the maximum, if necessary.
231 */
232 protected void shrinkCacheToMaximumSize() {
233 // Rich Dougherty: This could be more efficient.
234 while (cacheSize > maximumCacheSize) {
235 getNodeFromCache();
236 }
237 }
238
239 /**
240 * Serializes this object to an ObjectOutputStream.
241 *
242 * @param out the target ObjectOutputStream.
243 * @throws IOException thrown when an I/O errors occur writing to the target stream.
244 */
245 private void writeObject(final ObjectOutputStream out) throws IOException {
246 out.defaultWriteObject();
247 doWriteObject(out);
248 }
249
250 }