/*
 * Copyright (c) 1997, 2018 Oracle and/or its affiliates. All rights reserved.
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Public License v. 2.0, which is available at
 * http://www.eclipse.org/legal/epl-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the
 * Eclipse Public License v. 2.0 are satisfied: GNU General Public License,
 * version 2 with the GNU Classpath Exception, which is available at
 * https://www.gnu.org/software/classpath/license.html.
 *
 * SPDX-License-Identifier: EPL-2.0 OR GPL-2.0 WITH Classpath-exception-2.0
 */

package com.sun.appserv.util.cache;

import java.util.ArrayList;
import java.util.Map;
import java.util.Properties;
import java.util.ResourceBundle;

/**
 * LRUCache
 * in-memory bounded cache with an LRU list
 */
public class LruCache extends BaseCache {

    // the item never expires
    public static final long NO_TIMEOUT = -1;

    // LRU list
    protected LruCacheItem head;
    protected LruCacheItem tail;

    // the number of times the cache was trimmed
    protected int trimCount;

    protected int listSize;
    protected long timeout = NO_TIMEOUT;

    protected int defaultMaxEntries = Constants.DEFAULT_MAX_ENTRIES;
    protected boolean isUnbounded = false;

    /**
     * default constructor
     */
    public LruCache() { }

    /**
     * constructor with specified max entries.
     * @param defaultMaxEntries specifies the default max entries
     *        to use when the maxEntries is <= 0.
     */
    public LruCache(int defaultMaxEntries) {
        this.defaultMaxEntries = defaultMaxEntries;
    }

    /**
     * initialize the cache
     * @param maxEntries maximum number of entries expected in the cache
     * @param loadFactor the load factor
     * @param timeout to be used to trim the expired entries
     * @param props opaque list of properties for a given cache implementation
     * @throws a generic Exception if the initialization failed
     */
    public void init(int maxEntries, long timeout, float loadFactor, Properties props) {

        // if the max entries is <= 0 then set the default max entries
        if (maxEntries <= 0) {
            maxEntries = defaultMaxEntries;

            // mark this cache unbounded
            isUnbounded = true;
        }
        setTimeout(timeout);

        super.init(maxEntries, loadFactor, props);
    }

    /**
     * sets the timeout value
     * @param timeout to be used to trim the expired entries
     */
    public void setTimeout(long timeout) {
        // accept a positive timeout
        if (timeout > 0)
            this.timeout = timeout;
    }

    /**
     * create new item
     * @param hashCode for the entry
     * @param key <code>Object</code> key
     * @param value <code>Object</code> value
     * @param size size in bytes of the item
     *
     * subclasses may override to provide their own CacheItem extensions
     * e.g. one that permits persistence.
     */
    protected CacheItem createItem(int hashCode, Object key,
                                        Object value, int size) {
        return new LruCacheItem(hashCode, key, value, size);
    }

    /**
     * trim one item from the LRU list
     * @param currentTime of this operation
     * @return the item trimmed from cache
     *
     * list synchronization is handled by the caller
     */
    protected CacheItem trimLru(long currentTime) {

        if(tail == null)
            return null;

        LruCacheItem trimItem = tail;

        if (tail != head) {
            tail = trimItem.lPrev;
            if(tail == null) {
                //TODO:: print out a warning message here
                tail = head = null;
            } else {
                tail.lNext = null;
                trimItem.lPrev = null;
            }
        } else {
            tail = head = null;
        }

            trimItem.isTrimmed = true;
            trimItem.lPrev = null;
            trimCount++;
            listSize--;

        return trimItem;
    }

    /**
    /**
     * this item is just added to the cache
     * @param item <code>CacheItem</code> that was created
     * @return a overflow item; may be null
     *
     * this function checks if adding the new item results in a overflow;
     * if so, it returns the item to be removed.
     *
     * Cache bucket is already synchronized by the caller
     */
    protected CacheItem itemAdded(CacheItem item) {
        boolean updateThreshold = false;
        CacheItem overflow = null;
        if(! (item instanceof LruCacheItem))
            return null;
        LruCacheItem lc = (LruCacheItem) item;

        // set the timestamp
        lc.lastAccessed = System.currentTimeMillis();

        // update the LRU
        synchronized (this) {
            if (head != null) {
                head.lPrev = lc;
                lc.lNext = head;
                lc.lPrev = null;
                head = lc;
            }
            else {
                head = tail = lc;
                lc.lPrev = lc.lNext = null;
            }

            listSize++;

            if (isThresholdReached()) {
                if (!isUnbounded)
                    overflow = trimLru(lc.lastAccessed);
                else
                    updateThreshold = true;
            }
        }

        // update the base cache threshold if needed
        if (updateThreshold)
            super.handleOverflow();

        return overflow;
    }

    /**
     * this item is accessed
     * @param item <code>CacheItem</code> accessed
     *
     * Cache bucket is already synchronized by the caller
     */
    protected void itemAccessed(CacheItem item) {
        if(head == null)
            return;
        if(item == null)
            return;
        if(! (item instanceof LruCacheItem))
            return;
        LruCacheItem lc = (LruCacheItem) item;

        synchronized (this) {

            // if the item is already trimmed from the LRU list, nothing to do.
            if (lc.isTrimmed)
                return;

            // update the timestamp
            lc.lastAccessed = System.currentTimeMillis();

            LruCacheItem prev = lc.lPrev;
            LruCacheItem next = lc.lNext;
            // update the LRU list
            if (prev != null) {
                // put the item at the head of LRU list
                lc.lPrev = null;
                lc.lNext = head;
                head.lPrev = lc;
                head = lc;

                // patch up the previous neighbors
                prev.lNext = next;
                if (next != null)
                    next.lPrev = prev;
                else
                    tail = prev;
           }
        }
    }

    /**
     * item value has been refreshed
     * @param item <code>CacheItem</code> that was refreshed
     * @param oldSize size of the previous value that was refreshed
     * Cache bucket is already synchronized by the caller
     */
    protected void itemRefreshed(CacheItem item, int oldSize) {
        itemAccessed(item);
    }

    /**
     * item value has been removed from the cache
     * @param item <code>CacheItem</code> that was just removed
     *
     * Cache bucket is already synchronized by the caller
     */
    protected void itemRemoved(CacheItem item) {
        if(! (item instanceof LruCacheItem))
            return;
        LruCacheItem l = (LruCacheItem) item;

        // remove the item from the LRU list
        synchronized (this) {
            LruCacheItem prev = l.lPrev;
            LruCacheItem next = l.lNext;

            // if the item is already trimmed from the LRU list, nothing to do.
            if (l.isTrimmed)
                return;

            // patch up the neighbors and make sure head/tail are correct
            if (prev != null)
                prev.lNext = next;
            else
                head = next;

            if (next != null)
                next.lPrev = prev;
            else
                tail = prev;

            l.lPrev = l.lNext = null;
            listSize--;
        }
    }

    /**
     * trim the expired entries from the cache.
     * @param maxCount maximum number of invalid entries to trim
     *        specify Integer.MAX_VALUE to trim all invalid entries
     * This call is to be scheduled by a thread managed by the container.
     *
     * NOTE: this algorithm assumes that all the entries in the cache have
     * identical timeout (otherwise traversing from tail won't be right).
     */
    public void trimExpiredEntries(int maxCount) {

        int count = 0;
        LruCacheItem item;
        long currentTime = System.currentTimeMillis();
        ArrayList list = new ArrayList();

        synchronized (this) {
            // traverse LRU list till we reach a valid item; remove them at once
            for (item = tail; item != null && count < maxCount;
                                                item = item.lPrev) {

                if (timeout != NO_TIMEOUT &&
                    (item.lastAccessed + timeout) <= currentTime) {
                    item.isTrimmed = true;
                    list.add(item);

                    count++;
                } else {
                    break;
                }
            }

            // if there was at least one invalid item then item != tail.
            if (item != tail) {
                if (item != null)
                    item.lNext = null;
                else
                    head = null;

                tail = item;
            }
            listSize -= count;
            trimCount += count;
        }

        // trim the items from the BaseCache from the old tail backwards
        for (int index=list.size()-1; index >= 0; index--) {
            trimItem((LruCacheItem) list.get(index));
        }
    }


    /**
     * get generic stats from subclasses
     */

    /**
     * get the desired statistic counter
     * @param key to corresponding stat
     * @return an Object corresponding to the stat
     * See also: Constant.java for the key
     */
    public Object getStatByName(String key) {
        Object stat = super.getStatByName(key);

        if (stat == null && key != null) {
            if (key.equals(Constants.STAT_LRUCACHE_LIST_LENGTH))
                stat = Integer.valueOf(listSize);
            else if (key.equals(Constants.STAT_LRUCACHE_TRIM_COUNT))
                stat = Integer.valueOf(trimCount);
        }
        return stat;
    }

    public Map getStats() {
        Map stats = super.getStats();
        stats.put(Constants.STAT_LRUCACHE_LIST_LENGTH,
                  Integer.valueOf(listSize));
        stats.put(Constants.STAT_LRUCACHE_TRIM_COUNT,
                  Integer.valueOf(trimCount));

        return stats;
    }

    /** default CacheItem class implementation  ***/
    protected static class LruCacheItem extends CacheItem {

        // double linked LRU list
        protected LruCacheItem lNext;
        protected LruCacheItem lPrev;
        protected boolean isTrimmed;
        protected long lastAccessed;

        protected LruCacheItem(int hashCode, Object key, Object value, int size) {
            super(hashCode, key, value, size);
        }

        /**
         * Return the next item
         */
         public LruCacheItem getLNext() {
             return lNext;
         }

        /**
         * Reset the next item reference
         */
         public void setLNext(LruCacheItem item) {
             lNext = item;
         }

        /**
         * Return the previous item
         */
         public LruCacheItem getLPrev() {
             return lPrev;
         }

        /**
         * Reset the previous item reference
         */
         public void setLPrev(LruCacheItem item) {
             lPrev = item;
         }

        /**
         * Return <code>true</code> if this item is trimmed
         */
         public boolean isTrimmed() {
             return isTrimmed;
         }

        /**
         * Set the trimmed flag
         */
         public void setTrimmed(boolean value) {
             isTrimmed = value;
         }

        /**
         * Return the last accessed timestamp
         */
         public long getLastAccessed() {
             return lastAccessed;
         }

        /**
         * Reset the last accessed timestamp
         */
         public void setLastAccessed(long l) {
             lastAccessed = l;
         }
    }
}