View Javadoc

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  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              // empty list.
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              // empty list.
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             // already the first node. or not a node
136             return;
137         }
138         ln.prev.next = ln.next;
139 
140         if ( ln.next == null )
141         {
142             // last but not the first.
143             last = ln.prev;
144             last.next = null;
145         }
146         else
147         {
148             // neither the last nor the first.
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         // make sure this will work, could be add while this is happening.
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                 // 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                 if ( me == first && me == last )
200                 {
201                     first = last = null;
202                 }
203             }
204             else
205             {
206                 // last but not the first.
207                 last = me.prev;
208                 last.next = null;
209                 me.prev = null;
210             }
211         }
212         else if ( me.prev == null )
213         {
214             // first but not the last.
215             first = me.next;
216             first.prev = null;
217             me.next = null;
218         }
219         else
220         {
221             // neither the first nor the last.
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 }