001    package org.apache.jcs.utils.struct;
002    
003    /*
004     * Licensed to the Apache Software Foundation (ASF) under one
005     * or more contributor license agreements.  See the NOTICE file
006     * distributed with this work for additional information
007     * regarding copyright ownership.  The ASF licenses this file
008     * to you under the Apache License, Version 2.0 (the
009     * "License"); you may not use this file except in compliance
010     * with the License.  You may obtain a copy of the License at
011     *
012     *   http://www.apache.org/licenses/LICENSE-2.0
013     *
014     * Unless required by applicable law or agreed to in writing,
015     * software distributed under the License is distributed on an
016     * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
017     * KIND, either express or implied.  See the License for the
018     * specific language governing permissions and limitations
019     * under the License.
020     */
021    
022    import org.apache.commons.logging.Log;
023    import org.apache.commons.logging.LogFactory;
024    
025    /**
026     * This is an basic thread safe single linked list. It provides very limited functionality. It is
027     * small and fast.
028     * <p>
029     * @author Aaron Smuts
030     */
031    public class SingleLinkedList<T>
032    {
033        /** The logger */
034        private static final Log log = LogFactory.getLog( SingleLinkedList.class );
035    
036        /** for sync */
037        private final Object lock = new Object();
038    
039        /** the head of the queue */
040        private Node<T> head = new Node<T>();
041    
042        /** the end of the queue */
043        private Node<T> tail = head;
044    
045        /** The size of the list */
046        private int size = 0;
047    
048        /**
049         * Takes the first item off the list.
050         * <p>
051         * @return null if the list is empty.
052         */
053        public T takeFirst()
054        {
055            synchronized ( lock )
056            {
057                // wait until there is something to read
058                if ( head == tail )
059                {
060                    return null;
061                }
062    
063                Node<T> node = head.next;
064    
065                T value = node.payload;
066    
067                if ( log.isDebugEnabled() )
068                {
069                    log.debug( "head.payload = " + head.payload );
070                    log.debug( "node.payload = " + node.payload );
071                }
072    
073                // Node becomes the new head (head is always empty)
074    
075                node.payload = null;
076                head = node;
077    
078                size--;
079                return value;
080            }
081        }
082    
083        /**
084         * Adds an item to the end of the list.
085         * <p>
086         * @param payload
087         */
088        public void addLast( T payload )
089        {
090            Node<T> newNode = new Node<T>();
091    
092            newNode.payload = payload;
093    
094            synchronized ( lock )
095            {
096                size++;
097                tail.next = newNode;
098                tail = newNode;
099            }
100        }
101    
102        /**
103         * Removes everything.
104         */
105        public void clear()
106        {
107            synchronized ( lock )
108            {
109                head = tail;
110                size = 0;
111            }
112        }
113    
114        /**
115         * The list is composed of nodes.
116         * <p>
117         * @author Aaron Smuts
118         */
119        protected static class Node<T>
120        {
121            /** next in the list */
122            Node<T> next = null;
123    
124            /** The data in this node */
125            T payload;
126        }
127    
128        /**
129         * Returns the number of elements in the list.
130         * <p>
131         * @return number of items in the list.
132         */
133        public int size()
134        {
135            return size;
136        }
137    }