1 package org.apache.jcs.utils.struct;
2
3 /*
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "License"); you may not use this file except in compliance
10 * with the License. You may obtain a copy of the License at
11 *
12 * http://www.apache.org/licenses/LICENSE-2.0
13 *
14 * Unless required by applicable law or agreed to in writing,
15 * software distributed under the License is distributed on an
16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 * KIND, either express or implied. See the License for the
18 * specific language governing permissions and limitations
19 * under the License.
20 */
21
22 import org.apache.commons.logging.Log;
23 import org.apache.commons.logging.LogFactory;
24
25 /**
26 * This is a generic thread safe double linked list. It's very simple and all the operations are so
27 * quick that course grained synchronization is more than acceptable.
28 */
29 public class DoubleLinkedList<T extends DoubleLinkedListNode>
30 {
31 /** record size to avoid having to iterate */
32 private int size = 0;
33
34 /** The logger */
35 private final static Log log = LogFactory.getLog( DoubleLinkedList.class );
36
37 /** LRU double linked list head node */
38 private T first;
39
40 /** LRU double linked list tail node */
41 private T last;
42
43 /**
44 * Default constructor.
45 */
46 public DoubleLinkedList()
47 {
48 super();
49 }
50
51 /**
52 * Adds a new node to the end of the link list.
53 * <p>
54 * @param me The feature to be added to the Last
55 */
56 public synchronized void addLast(T me)
57 {
58 if ( first == null )
59 {
60 // empty list.
61 first = me;
62 }
63 else
64 {
65 last.next = me;
66 me.prev = last;
67 }
68 last = me;
69 size++;
70 }
71
72 /**
73 * Adds a new node to the start of the link list.
74 * <p>
75 * @param me The feature to be added to the First
76 */
77 public synchronized void addFirst(T me)
78 {
79 if ( last == null )
80 {
81 // empty list.
82 last = me;
83 }
84 else
85 {
86 first.prev = me;
87 me.next = first;
88 }
89 first = me;
90 size++;
91 }
92
93 /**
94 * Returns the last node from the link list, if there are any nodes.
95 * <p>
96 * @return The last node.
97 */
98 public synchronized T getLast()
99 {
100 if ( log.isDebugEnabled() )
101 {
102 log.debug( "returning last node" );
103 }
104 return last;
105 }
106
107 /**
108 * Removes the specified node from the link list.
109 * <p>
110 * @return DoubleLinkedListNode, the first node.
111 */
112 public synchronized T getFirst()
113 {
114 if ( log.isDebugEnabled() )
115 {
116 log.debug( "returning first node" );
117 }
118 return first;
119 }
120
121 /**
122 * Moves an existing node to the start of the link list.
123 * <p>
124 * @param ln The node to set as the head.
125 */
126 public synchronized void makeFirst(T ln)
127 {
128 if ( ln.prev == null )
129 {
130 // already the first node. or not a node
131 return;
132 }
133 // splice: remove it from the list
134 ln.prev.next = ln.next;
135
136 if ( ln.next == null )
137 {
138 // last but not the first.
139 last = (T) ln.prev;
140 last.next = null;
141 }
142 else
143 {
144 // neither the last nor the first.
145 ln.next.prev = ln.prev;
146 }
147 first.prev = ln;
148 ln.next = first;
149 ln.prev = null;
150 first = ln;
151 }
152
153 /**
154 * Moves an existing node to the end of the link list.
155 * <p>
156 * @param ln The node to set as the head.
157 */
158 public synchronized void makeLast(T ln)
159 {
160 if ( ln.next == null )
161 {
162 // already the last node. or not a node
163 return;
164 }
165 // splice: remove it from the list
166 if ( ln.prev != null )
167 {
168 ln.prev.next = ln.next;
169 }
170 else
171 {
172 // first
173 first = last;
174 }
175
176 if ( last != null )
177 {
178 last.next = ln;
179 }
180 ln.prev = last;
181 ln.next = null;
182 last = ln;
183 }
184
185 /**
186 * Remove all of the elements from the linked list implementation.
187 */
188 public synchronized void removeAll()
189 {
190 for (T me = first; me != null; )
191 {
192 if ( me.prev != null )
193 {
194 me.prev = null;
195 }
196 T next = (T) me.next;
197 me = next;
198 }
199 first = last = null;
200 // make sure this will work, could be add while this is happening.
201 size = 0;
202 }
203
204 /**
205 * Removes the specified node from the link list.
206 * <p>
207 * @param me Description of the Parameter
208 * @return true if an element was removed.
209 */
210 public synchronized boolean remove(T me)
211 {
212 if ( log.isDebugEnabled() )
213 {
214 log.debug( "removing node" );
215 }
216
217 if ( me.next == null )
218 {
219 if ( me.prev == null )
220 {
221 // Make sure it really is the only node before setting head and
222 // tail to null. It is possible that we will be passed a node
223 // which has already been removed from the list, in which case
224 // we should ignore it
225
226 if ( me == first && me == last )
227 {
228 first = last = null;
229 }
230 }
231 else
232 {
233 // last but not the first.
234 last = (T) me.prev;
235 last.next = null;
236 me.prev = null;
237 }
238 }
239 else if ( me.prev == null )
240 {
241 // first but not the last.
242 first = (T) me.next;
243 first.prev = null;
244 me.next = null;
245 }
246 else
247 {
248 // neither the first nor the last.
249 me.prev.next = me.next;
250 me.next.prev = me.prev;
251 me.prev = me.next = null;
252 }
253 size--;
254
255 return true;
256 }
257
258 /**
259 * Removes the specified node from the link list.
260 * <p>
261 * @return The last node if there was one to remove.
262 */
263 public synchronized T removeLast()
264 {
265 if ( log.isDebugEnabled() )
266 {
267 log.debug( "removing last node" );
268 }
269 T temp = last;
270 if ( last != null )
271 {
272 remove( last );
273 }
274 return temp;
275 }
276
277 /**
278 * Returns the size of the list.
279 * <p>
280 * @return int
281 */
282 public synchronized int size()
283 {
284 return size;
285 }
286
287 // ///////////////////////////////////////////////////////////////////
288 /**
289 * Dump the cache entries from first to list for debugging.
290 */
291 public synchronized void debugDumpEntries()
292 {
293 if ( log.isDebugEnabled() )
294 {
295 log.debug( "dumping Entries" );
296 for (T me = first; me != null; me = (T) me.next)
297 {
298 log.debug( "dump Entries> payload= '" + me.getPayload() + "'" );
299 }
300 }
301 }
302 }