java/org/apache/jasper/util/FastRemovalDequeue.java

/*
 * 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.
 */
package org.apache.jasper.util;

/**
 * The FastRemovalDequeue is a Dequeue that supports constant time removal of entries. This is achieved by using a
 * doubly linked list and wrapping any object added to the collection with an Entry type, that is returned to the
 * consumer. When removing an object from the list, the consumer provides this Entry object.
 * <p>
 * The Entry type is nearly opaque to the consumer of the queue. The only public member is the getter for any object
 * displaced when adding a new object to the queue. This can be used to destroy that object.
 * <p>
 * The Entry object contains the links pointing to the neighbours in the doubly linked list, so that removal of an Entry
 * does not need to search for it but instead can be done in constant time.
 * <p>
 * The implementation is fully thread-safe.
 * <p>
 * Invalidation of Entry objects during removal from the list is done by setting their "valid" field to false. All
 * public methods which take Entry objects as arguments are NOP if the entry is no longer valid.
 * <p>
 * A typical use of the FastRemovalDequeue is a list of entries in sorted order, where the sort position of an object
 * will only switch to first or last.
 * <p>
 * Whenever the sort position needs to change, the consumer can remove the object and reinsert it in front or at the end
 * in constant time. So keeping the list sorted is very cheap.
 *
 * @param <T> The type of elements in the queue
 */
public class FastRemovalDequeue<T> {

    /** Maximum size of the queue */
    private final int maxSize;
    /** First element of the queue. */
    protected Entry first;
    /** Last element of the queue. */
    protected Entry last;
    /** Size of the queue */
    private int size;

    /**
     * Initialize empty queue.
     *
     * @param maxSize The maximum size to which the queue will be allowed to grow
     */
    public FastRemovalDequeue(int maxSize) {
        if (maxSize <= 1) {
            maxSize = 2;
        }
        this.maxSize = maxSize;
        first = null;
        last = null;
        size = 0;
    }

    /**
     * Retrieve the size of the list. This method also needs to be externally synchronized to ensure correct publication
     * of changes.
     *
     * @return the size of the list.
     */
    public synchronized int getSize() {
        return size;
    }

    /**
     * Adds an object to the start of the list and returns the entry created for said object. The entry can later be
     * reused for moving the entry.
     *
     * @param object the object to prepend to the start of the list.
     *
     * @return an entry for use when the object should be moved.
     */
    public synchronized Entry push(final T object) {
        Entry entry = new Entry(object);
        if (size >= maxSize) {
            entry.setReplaced(pop());
        }
        if (first == null) {
            first = last = entry;
        } else {
            first.setPrevious(entry);
            entry.setNext(first);
            first = entry;
        }
        size++;

        return entry;
    }

    /**
     * Adds an object to the end of the list and returns the entry created for said object. The entry can later be
     * reused for moving the entry.
     *
     * @param object the object to append to the end of the list.
     *
     * @return an entry for use when the object should be moved.
     */
    public synchronized Entry unpop(final T object) {
        Entry entry = new Entry(object);
        if (size >= maxSize) {
            entry.setReplaced(unpush());
        }
        if (first == null) {
            first = last = entry;
        } else {
            last.setNext(entry);
            entry.setPrevious(last);
            last = entry;
        }
        size++;

        return entry;
    }

    /**
     * Removes the first element of the list and returns its content.
     *
     * @return the content of the first element of the list.
     **/
    public synchronized T unpush() {
        T content = null;
        if (first != null) {
            Entry element = first;
            first = first.getNext();
            content = element.getContent();
            if (first == null) {
                last = null;
            } else {
                first.setPrevious(null);
            }
            size--;
            element.invalidate();
        }
        return content;
    }

    /**
     * Removes the last element of the list and returns its content.
     *
     * @return the content of the last element of the list.
     **/
    public synchronized T pop() {
        T content = null;
        if (last != null) {
            Entry element = last;
            last = last.getPrevious();
            content = element.getContent();
            if (last == null) {
                first = null;
            } else {
                last.setNext(null);
            }
            size--;
            element.invalidate();
        }
        return content;
    }

    /**
     * Removes any element of the list and returns its content.
     *
     * @param element The element to remove
     */
    public synchronized void remove(final Entry element) {
        if (element == null || !element.getValid()) {
            return;
        }
        Entry next = element.getNext();
        Entry prev = element.getPrevious();
        if (next != null) {
            next.setPrevious(prev);
        } else {
            last = prev;
        }
        if (prev != null) {
            prev.setNext(next);
        } else {
            first = next;
        }
        size--;
        element.invalidate();
    }

    /**
     * Moves the element in front. Could also be implemented as remove() and push(), but explicitly coding might be a
     * bit faster.
     *
     * @param element the entry to move in front.
     */
    public synchronized void moveFirst(final Entry element) {
        if (element.getValid() && element.getPrevious() != null) {
            Entry prev = element.getPrevious();
            Entry next = element.getNext();
            prev.setNext(next);
            if (next != null) {
                next.setPrevious(prev);
            } else {
                last = prev;
            }
            first.setPrevious(element);
            element.setNext(first);
            element.setPrevious(null);
            first = element;
        }
    }

    /**
     * Moves the element to the back. Could also be implemented as remove() and unpop(), but explicitly coding might be
     * a bit faster.
     *
     * @param element the entry to move to the back.
     */
    public synchronized void moveLast(final Entry element) {
        if (element.getValid() && element.getNext() != null) {
            Entry next = element.getNext();
            Entry prev = element.getPrevious();
            next.setPrevious(prev);
            if (prev != null) {
                prev.setNext(next);
            } else {
                first = next;
            }
            last.setNext(element);
            element.setPrevious(last);
            element.setNext(null);
            last = element;
        }
    }

    /**
     * Implementation of a doubly linked list entry. All implementation details are private. For the consumer of the
     * above collection, this is simply garbage in, garbage out.
     */
    public class Entry {

        /** Is this entry still valid? */
        private boolean valid = true;
        /** The content this entry is valid for. */
        private final T content;
        /** Optional content that was displaced by this entry */
        private T replaced = null;
        /** Pointer to next element in queue. */
        private Entry next = null;
        /** Pointer to previous element in queue. */
        private Entry previous = null;

        private Entry(T object) {
            content = object;
        }

        private boolean getValid() {
            return valid;
        }

        private void invalidate() {
            this.valid = false;
            this.previous = null;
            this.next = null;
        }

        /**
         * Returns the content stored in this entry.
         *
         * @return the content object
         */
        public final T getContent() {
            return content;
        }

        /**
         * Returns the content that was displaced when this entry was added to a full queue.
         *
         * @return the displaced content, or {@code null} if no content was displaced
         */
        public final T getReplaced() {
            return replaced;
        }

        private void setReplaced(final T replaced) {
            this.replaced = replaced;
        }

        /**
         * Clears the displaced content reference.
         */
        public final void clearReplaced() {
            this.replaced = null;
        }

        private Entry getNext() {
            return next;
        }

        private void setNext(final Entry next) {
            this.next = next;
        }

        private Entry getPrevious() {
            return previous;
        }

        private void setPrevious(final Entry previous) {
            this.previous = previous;
        }

        @Override
        public String toString() {
            return "Entry-" + content.toString();
        }
    }

}