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