commons-jcs-core/src/main/java/org/apache/commons/jcs3/utils/struct/DoubleLinkedList.java

package org.apache.commons.jcs3.utils.struct;

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

import org.apache.commons.jcs3.log.Log;
import org.apache.commons.jcs3.log.LogManager;

/**
 * This is a generic thread safe double linked list. It's very simple and all the operations are so
 * quick that course grained synchronization is more than acceptable.
 */
@SuppressWarnings({ "unchecked", "rawtypes" }) // Don't know how to resolve this with generics
public class DoubleLinkedList<T extends DoubleLinkedListNode>
{
    /** record size to avoid having to iterate */
    private int size = 0;

    /** The logger */
    private static final Log log = LogManager.getLog( DoubleLinkedList.class );

    /** LRU double linked list head node */
    private T first;

    /** LRU double linked list tail node */
    private T last;

    /**
     * Default constructor.
     */
    public DoubleLinkedList()
    {
    }

    /**
     * Adds a new node to the end of the link list.
     * <p>
     * @param me The feature to be added to the Last
     */
    public synchronized void addLast(final T me)
    {
        if ( first == null )
        {
            // empty list.
            first = me;
        }
        else
        {
            last.next = me;
            me.prev = last;
        }
        last = me;
        size++;
    }

    /**
     * Adds a new node to the start of the link list.
     * <p>
     * @param me The feature to be added to the First
     */
    public synchronized void addFirst(final T me)
    {
        if ( last == null )
        {
            // empty list.
            last = me;
        }
        else
        {
            first.prev = me;
            me.next = first;
        }
        first = me;
        size++;
    }

    /**
     * Returns the last node from the link list, if there are any nodes.
     * <p>
     * @return The last node.
     */
    public synchronized T getLast()
    {
        log.debug( "returning last node" );
        return last;
    }

    /**
     * Removes the specified node from the link list.
     * <p>
     * @return DoubleLinkedListNode, the first node.
     */
    public synchronized T getFirst()
    {
        log.debug( "returning first node" );
        return first;
    }

    /**
     * Moves an existing node to the start of the link list.
     * <p>
     * @param ln The node to set as the head.
     */
    public synchronized void makeFirst(final T ln)
    {
        if ( ln.prev == null )
        {
            // already the first node. or not a node
            return;
        }
        // splice: remove it from the list
        ln.prev.next = ln.next;

        if ( ln.next == null )
        {
            // last but not the first.
            last = (T) ln.prev;
            last.next = null;
        }
        else
        {
            // neither the last nor the first.
            ln.next.prev = ln.prev;
        }
        first.prev = ln;
        ln.next = first;
        ln.prev = null;
        first = ln;
    }

    /**
     * Moves an existing node to the end of the link list.
     * <p>
     * @param ln The node to set as the head.
     */
    public synchronized void makeLast(final T ln)
    {
        if ( ln.next == null )
        {
            // already the last node. or not a node
            return;
        }
        // splice: remove it from the list
        if ( ln.prev != null )
        {
            ln.prev.next = ln.next;
        }
        else
        {
            // first
            first = last;
        }

        if ( last != null )
        {
            last.next = ln;
        }
        ln.prev = last;
        ln.next = null;
        last = ln;
    }

    /**
     * Remove all of the elements from the linked list implementation.
     */
    public synchronized void removeAll()
    {
        for (T me = first; me != null; )
        {
            if ( me.prev != null )
            {
                me.prev = null;
            }
            final T next = (T) me.next;
            me = next;
        }
        first = last = null;
        // make sure this will work, could be add while this is happening.
        size = 0;
    }

    /**
     * Removes the specified node from the link list.
     * <p>
     * @param me Description of the Parameter
     * @return true if an element was removed.
     */
    public synchronized boolean remove(final T me)
    {
        log.debug( "removing node" );

        if ( me.next == null )
        {
            if ( me.prev == null )
            {
                // Make sure it really is the only node before setting head and
                // tail to null. It is possible that we will be passed a node
                // which has already been removed from the list, in which case
                // we should ignore it

                if ( me == first && me == last )
                {
                    first = last = null;
                }
            }
            else
            {
                // last but not the first.
                last = (T) me.prev;
                last.next = null;
                me.prev = null;
            }
        }
        else if ( me.prev == null )
        {
            // first but not the last.
            first = (T) me.next;
            first.prev = null;
            me.next = null;
        }
        else
        {
            // neither the first nor the last.
            me.prev.next = me.next;
            me.next.prev = me.prev;
            me.prev = me.next = null;
        }
        size--;

        return true;
    }

    /**
     * Removes the specified node from the link list.
     * <p>
     * @return The last node if there was one to remove.
     */
    public synchronized T removeLast()
    {
        log.debug( "removing last node" );
        final T temp = last;
        if ( last != null )
        {
            remove( last );
        }
        return temp;
    }

    /**
     * Returns the size of the list.
     * <p>
     * @return int
     */
    public synchronized int size()
    {
        return size;
    }

    // ///////////////////////////////////////////////////////////////////
    /**
     * Dump the cache entries from first to list for debugging.
     */
    public synchronized void debugDumpEntries()
    {
        if ( log.isDebugEnabled() )
        {
            log.debug( "dumping Entries" );
            for (T me = first; me != null; me = (T) me.next)
            {
                log.debug( "dump Entries> payload= \"{0}\"", me.getPayload() );
            }
        }
    }
}