1 package org.apache.jcs.utils.struct;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
27 * the operations are so quick that course grained synchronization is more than
28 * acceptible.
29 */
30 public class DoubleLinkedList
31 {
32 /*** record size to avoid having to iterate */
33 private int size = 0;
34
35 /*** The logger */
36 private final static Log log = LogFactory.getLog( DoubleLinkedList.class );
37
38 /*** LRU double linked list head node */
39 private DoubleLinkedListNode first;
40
41 /*** LRU double linked list tail node */
42 private DoubleLinkedListNode last;
43
44 /***
45 * Default constructor.
46 */
47 public DoubleLinkedList()
48 {
49 super();
50 }
51
52 /***
53 * Adds a new node to the end of the link list.
54 * <p>
55 * @param me
56 * The feature to be added to the Last
57 */
58 public synchronized void addLast( DoubleLinkedListNode me )
59 {
60 if ( first == null )
61 {
62
63 first = me;
64 }
65 else
66 {
67 last.next = me;
68 me.prev = last;
69 }
70 last = me;
71 size++;
72 }
73
74 /***
75 * Adds a new node to the start of the link list.
76 * <p>
77 * @param me
78 * The feature to be added to the First
79 */
80 public synchronized void addFirst( DoubleLinkedListNode me )
81 {
82 if ( last == null )
83 {
84
85 last = me;
86 }
87 else
88 {
89 first.prev = me;
90 me.next = first;
91 }
92 first = me;
93 size++;
94 return;
95 }
96
97 /***
98 * Returns the last node from the link list, if there are any nodes.
99 * <p>
100 * @return The last node.
101 */
102 public synchronized DoubleLinkedListNode getLast()
103 {
104 if ( log.isDebugEnabled() )
105 {
106 log.debug( "returning last node" );
107 }
108 return last;
109 }
110
111 /***
112 * Removes the specified node from the link list.
113 * <p>
114 * @return DoubleLinkedListNode, the first node.
115 */
116 public synchronized DoubleLinkedListNode getFirst()
117 {
118 if ( log.isDebugEnabled() )
119 {
120 log.debug( "returning first node" );
121 }
122 return first;
123 }
124
125 /***
126 * Moves an existing node to the start of the link list.
127 * <p>
128 * @param ln
129 * The node to set as the head.
130 */
131 public synchronized void makeFirst( DoubleLinkedListNode ln )
132 {
133 if ( ln.prev == null )
134 {
135
136 return;
137 }
138 ln.prev.next = ln.next;
139
140 if ( ln.next == null )
141 {
142
143 last = ln.prev;
144 last.next = null;
145 }
146 else
147 {
148
149 ln.next.prev = ln.prev;
150 }
151 first.prev = ln;
152 ln.next = first;
153 ln.prev = null;
154 first = ln;
155 }
156
157 /***
158 * Remove all of the elements from the linked list implementation.
159 */
160 public synchronized void removeAll()
161 {
162 for ( DoubleLinkedListNode me = first; me != null; )
163 {
164 if ( me.prev != null )
165 {
166 me.prev = null;
167 }
168 DoubleLinkedListNode next = me.next;
169 me = next;
170 }
171 first = last = null;
172
173 size = 0;
174 }
175
176 /***
177 * Removes the specified node from the link list.
178 * <p>
179 * @param me
180 * Description of the Parameter
181 * @return true if an element was removed.
182 */
183 public synchronized boolean remove( DoubleLinkedListNode me )
184 {
185 if ( log.isDebugEnabled() )
186 {
187 log.debug( "removing node" );
188 }
189
190 if ( me.next == null )
191 {
192 if ( me.prev == null )
193 {
194
195
196
197
198
199 if ( me == first && me == last )
200 {
201 first = last = null;
202 }
203 }
204 else
205 {
206
207 last = me.prev;
208 last.next = null;
209 me.prev = null;
210 }
211 }
212 else if ( me.prev == null )
213 {
214
215 first = me.next;
216 first.prev = null;
217 me.next = null;
218 }
219 else
220 {
221
222 me.prev.next = me.next;
223 me.next.prev = me.prev;
224 me.prev = me.next = null;
225 }
226 size--;
227
228 return true;
229 }
230
231 /***
232 * Removes the specified node from the link list.
233 * <p>
234 * @return The last node if there was one to remove.
235 */
236 public synchronized DoubleLinkedListNode removeLast()
237 {
238 if ( log.isDebugEnabled() )
239 {
240 log.debug( "removing last node" );
241 }
242 DoubleLinkedListNode temp = last;
243 if ( last != null )
244 {
245 remove( last );
246 }
247 return temp;
248 }
249
250 /***
251 * Returns the size of the list.
252 * <p>
253 * @return int
254 */
255 public synchronized int size()
256 {
257 return size;
258 }
259
260
261 /***
262 * Dump the cache entries from first to list for debugging.
263 */
264 public synchronized void debugDumpEntries()
265 {
266 log.debug( "dumping Entries" );
267 for ( DoubleLinkedListNode me = first; me != null; me = me.next )
268 {
269 log.debug( "dump Entries> payload= '" + me.getPayload() + "'" );
270 }
271 }
272 }