%line | %branch | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
org.apache.jcs.utils.struct.DoubleLinkedList |
|
|
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 |
|
27 | * the operations are so quick that course grained synchronization is more than |
|
28 | * acceptible. |
|
29 | */ |
|
30 | 9 | public class DoubleLinkedList |
31 | { |
|
32 | /** record size to avoid having to iterate */ |
|
33 | 1962 | private int size = 0; |
34 | ||
35 | /** The logger */ |
|
36 | 543 | 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 | 1962 | super(); |
50 | 1962 | } |
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 | 0 | if ( first == null ) |
61 | { |
|
62 | // empty list. |
|
63 | 0 | first = me; |
64 | 0 | } |
65 | else |
|
66 | { |
|
67 | 0 | last.next = me; |
68 | 0 | me.prev = last; |
69 | } |
|
70 | 0 | last = me; |
71 | 0 | size++; |
72 | 0 | } |
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 | 3807950 | if ( last == null ) |
83 | { |
|
84 | // empty list. |
|
85 | 1047497 | last = me; |
86 | 1007466 | } |
87 | else |
|
88 | { |
|
89 | 2761043 | first.prev = me; |
90 | 2761205 | me.next = first; |
91 | } |
|
92 | 3808489 | first = me; |
93 | 3808084 | size++; |
94 | 3808088 | 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 | 8913954 | if ( log.isDebugEnabled() ) |
105 | { |
|
106 | 0 | log.debug( "returning last node" ); |
107 | } |
|
108 | 8915006 | 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 | 7956782 | if ( log.isDebugEnabled() ) |
119 | { |
|
120 | 0 | log.debug( "returning first node" ); |
121 | } |
|
122 | 7954560 | 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 | 1664819 | if ( ln.prev == null ) |
134 | { |
|
135 | // already the first node. or not a node |
|
136 | 85205 | return; |
137 | } |
|
138 | 1579700 | ln.prev.next = ln.next; |
139 | ||
140 | 1579636 | if ( ln.next == null ) |
141 | { |
|
142 | // last but not the first. |
|
143 | 63730 | last = ln.prev; |
144 | 63728 | last.next = null; |
145 | 63646 | } |
146 | else |
|
147 | { |
|
148 | // neither the last nor the first. |
|
149 | 1515985 | ln.next.prev = ln.prev; |
150 | } |
|
151 | 1579035 | first.prev = ln; |
152 | 1579728 | ln.next = first; |
153 | 1579759 | ln.prev = null; |
154 | 1579740 | first = ln; |
155 | 1579684 | } |
156 | ||
157 | /** |
|
158 | * Remove all of the elements from the linked list implementation. |
|
159 | */ |
|
160 | public synchronized void removeAll() |
|
161 | { |
|
162 | 104 | for ( DoubleLinkedListNode me = first; me != null; ) |
163 | { |
|
164 | 8024 | if ( me.prev != null ) |
165 | { |
|
166 | 7992 | me.prev = null; |
167 | } |
|
168 | 8024 | DoubleLinkedListNode next = me.next; |
169 | 8024 | me = next; |
170 | 8024 | } |
171 | 104 | first = last = null; |
172 | // make sure this will work, could be add while this is happening. |
|
173 | 104 | size = 0; |
174 | 104 | } |
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 | 2959173 | if ( log.isDebugEnabled() ) |
186 | { |
|
187 | 0 | log.debug( "removing node" ); |
188 | } |
|
189 | ||
190 | 2961150 | if ( me.next == null ) |
191 | { |
|
192 | 2548560 | if ( me.prev == null ) |
193 | { |
|
194 | // Make sure it really is the only node before setting head and |
|
195 | // tail to null. It is possible that we will be passed a node |
|
196 | // which has already been removed from the list, in which case |
|
197 | // we should ignore it |
|
198 | ||
199 | 1047222 | if ( me == first && me == last ) |
200 | { |
|
201 | 1047157 | first = last = null; |
202 | 1007177 | } |
203 | } |
|
204 | else |
|
205 | { |
|
206 | // last but not the first. |
|
207 | 1501905 | last = me.prev; |
208 | 1502213 | last.next = null; |
209 | 1502226 | me.prev = null; |
210 | } |
|
211 | 1492389 | } |
212 | 412326 | else if ( me.prev == null ) |
213 | { |
|
214 | // first but not the last. |
|
215 | 1269 | first = me.next; |
216 | 1269 | first.prev = null; |
217 | 1269 | me.next = null; |
218 | 1267 | } |
219 | else |
|
220 | { |
|
221 | // neither the first nor the last. |
|
222 | 411057 | me.prev.next = me.next; |
223 | 411058 | me.next.prev = me.prev; |
224 | 411058 | me.prev = me.next = null; |
225 | } |
|
226 | 2961193 | size--; |
227 | ||
228 | 2961525 | 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 | 1740756 | if ( log.isDebugEnabled() ) |
239 | { |
|
240 | 0 | log.debug( "removing last node" ); |
241 | } |
|
242 | 1740848 | DoubleLinkedListNode temp = last; |
243 | 1740808 | if ( last != null ) |
244 | { |
|
245 | 1740876 | remove( last ); |
246 | } |
|
247 | 1740850 | 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 | 1796395 | 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 | 0 | log.debug( "dumping Entries" ); |
267 | 0 | for ( DoubleLinkedListNode me = first; me != null; me = me.next ) |
268 | { |
|
269 | 0 | log.debug( "dump Entries> payload= '" + me.getPayload() + "'" ); |
270 | } |
|
271 | 0 | } |
272 | } |
This report is generated by jcoverage, Maven and Maven JCoverage Plugin. |