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 an basic thread safe single linked list. It provides very limited functionality. It is
27   * small and fast.
28   * <p>
29   * @author Aaron Smuts
30   */
31  public class SingleLinkedList
32  {
33      private static final Log log = LogFactory.getLog( SingleLinkedList.class );
34  
35      private Object lock = new Object();
36  
37      // the head of the queue
38      private Node head = new Node();
39  
40      // the end of the queue
41      private Node tail = head;
42  
43      private int size = 0;
44  
45      /***
46       * Takes the first item off the list.
47       * <p>
48       * @return null if the list is empty.
49       */
50      public Object takeFirst()
51      {
52          synchronized ( lock )
53          {
54              // wait until there is something to read
55              if ( head == tail )
56              {
57                  return null;
58              }
59  
60              Node node = head.next;
61  
62              Object value = node.payload;
63  
64              if ( log.isDebugEnabled() )
65              {
66                  log.debug( "head.payload = " + head.payload );
67                  log.debug( "node.payload = " + node.payload );
68              }
69  
70              // Node becomes the new head (head is always empty)
71  
72              node.payload = null;
73              head = node;
74  
75              size--;
76              return value;
77          }
78      }
79  
80      /***
81       * Adds an item to the end of the list.
82       * <p>
83       * @param payload
84       */
85      public void addLast( Object payload )
86      {
87          Node newNode = new Node();
88  
89          newNode.payload = payload;
90  
91          synchronized ( lock )
92          {
93              size++;
94              tail.next = newNode;
95              tail = newNode;
96          }
97      }
98  
99      /***
100      * Removes everything.
101      */
102     public void clear()
103     {
104         synchronized ( lock )
105         {
106             head = tail;
107             size = 0;
108         }
109     }
110 
111     /***
112      * The list is composed of nodes.
113      * <p>
114      * @author Aaron Smuts
115      */
116     private static class Node
117     {
118         Node next = null;
119 
120         Object payload;
121     }
122 
123     /***
124      * Returns the number of elements in the list.
125      * <p>
126      * @return number of items in the list.
127      */
128     public int size()
129     {
130         return size;
131     }
132 }