/*
 * $Header: /home/cvspublic/jakarta-slide/src/share/org/apache/slide/util/TxLRUObjectCache.java,v 1.8 2004/10/20 07:22:43 ozeigermann Exp $
 * $Revision: 1.8 $
 * $Date: 2004/10/20 07:22:43 $
 *
 * ====================================================================
 *
 * Copyright 1999-2002 The Apache Software Foundation 
 *
 * Licensed 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.slide.util;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import org.apache.slide.util.logger.Logger;

import org.apache.commons.collections.LRUMap;

/**
 * Transactional LRU object cache. Caches objects using a least-recently-used strategy.
 * 
 * It provides basic isolation from other transactions and atomicity of all operations. As
 * no locking is used (which is undesirable mainly as a cache should never block and a commit must never fail) 
 * serializability needs to be guaranteed by underlying stores. 
 * <br>
 * <br>
 * <em>Caution</em>: Only global caches are limited by given size. 
 * Size of temporary data inside a transaction is unlimited.   
 * <br>
 * <br>
 * <em>Note</em>: This cache has no idea if the data it caches in transactions are read from or written to store. 
 * It thus handles both access types the same way. This means read accesses are cached in transactions even though they
 * could be cached globally. Like write accesses they will be moved to global cache at commit time. 
 * 
 * @version $Revision: 1.8 $
 */
public class TxLRUObjectCache {

    protected Map globalCache = null;

    protected Map txChangeCaches;
    protected Map txDeleteCaches;

    protected int hits = 0;
    protected int misses = 0;

    protected String name;
    protected Logger logger;
    protected String logChannel;
    protected final boolean loggingEnabled;
    
    protected boolean noGlobalCachingInsideTx; 

    /**
     * Creates a new object cache. If global caching is disabled, the cache
     * reflects isolation of underlying store as only double reads inside a single transaction
     * will be cached. This may even increase isolation as repeatable read is guaranteed.  
     * 
     * @param globalCacheSize maximum size in objects of global cache or <code>-1</code> to indicate no
     * global cache shall be used
     * @param name the name used to construct logging category / channel
     * @param logger Slide logger to be used for logging 
     * @param noGlobalCachingInsideTx indicates global caches are enabled, but shall not be used inside transactions
     */
    public TxLRUObjectCache(int globalCacheSize, String name, Logger logger, boolean noGlobalCachingInsideTx) {
        if (globalCacheSize != -1) {
            globalCache = new LRUMap(globalCacheSize);
        }
        txChangeCaches = new HashMap();
        txDeleteCaches = new HashMap();

        this.name = name;
        this.logger = logger;
        this.noGlobalCachingInsideTx = noGlobalCachingInsideTx;

        logChannel = "TxLRUObjectCache";
        if (name != null) {
            logChannel += "." + name;
        }

        // used for guarded logging as preparation is expensive
        loggingEnabled = logger.isEnabled(logChannel, Logger.DEBUG);
    }

    public synchronized void clear() {
        if (globalCache != null) globalCache.clear();
        txChangeCaches.clear();
        txDeleteCaches.clear();
    }

    public synchronized Object get(Object txId, Object key) {
        if (txId != null) {
            Set deleteCache = (Set) txDeleteCaches.get(txId);
            if (deleteCache.contains(key)) {
                hit(txId, key);
                // reflects that entry has been deleted in this tx 
                return null;
            }

            Map changeCache = (Map) txChangeCaches.get(txId);
            Object changed = getFromLocalCache(changeCache, key);
            if (changed != null) {
                hit(txId, key);
                // if object has been changed in this tx, get the local one
                return changed;
            }
        }
        
        if (globalCache == null) return null;
        
        // if global cache is disabled inside transactions, do not use it
        if (noGlobalCachingInsideTx && txId != null) return null;
        
        // as fall back return value from global cache (if present)
        Object global = getFromGlobalCache(key);
        if (global != null) {
            hit(txId, key);
        } else {
            miss(txId, key);
        }
        return global;
    }

    public synchronized void put(Object txId, Object key, Object value, long timeout) {
        if (timeout != -1) {
            value = new TimeoutValuePair(value, timeout);
        }
        put(txId, key, value);
    }

    public synchronized void put(Object txId, Object key, Object value) {
        if (txId != null) {
            // if it has been deleted before, undo this
            Set deleteCache = (Set) txDeleteCaches.get(txId);
            deleteCache.remove(key);

            Map changeCache = (Map) txChangeCaches.get(txId);
            changeCache.put(key, value);

            if (loggingEnabled) {
                logger.log(txId + " added '" + key + "'", logChannel, Logger.DEBUG);
            }
        } else {
            if (globalCache != null) {
                putToGlobalCache(key, value);
                if (loggingEnabled) {
                    logger.log("Added '" + key + "'", logChannel, Logger.DEBUG);
                }
            }
        }
    }

    public synchronized void remove(Object txId, Object key) {
        if (txId != null) {
            // if it has been changed before, undo this
            Map changeCache = (Map) txChangeCaches.get(txId);
            changeCache.remove(key);

            Set deleteCache = (Set) txDeleteCaches.get(txId);
            deleteCache.add(key);

            // guard logging as preparation is expensive
            if (loggingEnabled) {
                logger.log(txId + " removed '" + key + "'", logChannel, Logger.DEBUG);
            }
        } else {
            if (globalCache != null) {
                globalCache.remove(key);
                if (loggingEnabled) {
                    logger.log("Removed '" + key + "'", logChannel, Logger.DEBUG);
                }
            }
        }
    }
    
    /**
     * <p>
     * Removes the object identified by <code>key</code> as well as any objects
     * identified by <code>key.toString() + delimiter</code>.
     * </p>
     * <p>
     * Example: <code>remove(xId, "/slide/files", "-")</code> would remove
     * <code>/slide/files</code> and <code>/slide/files-1.3</code> but not
     * <code>/slide/files/temp</code>.
     * 
     * @param txId the id of the current transaction or <code>null</code> if not
     *             in a transaction.
     * @param key the key to remove from the cache.
     * @param delimiter the delimiter to use to identify subnodes that should be
     *                  removed as well.
     */
    public synchronized void remove(Object txId, Object key, String delimiter) {
        if (txId != null) {
            // undo any changes
            Map changeCache = (Map) txChangeCaches.get(txId);
            changeCache.remove(key);
            prune(changeCache, key, delimiter);

            Set deleteCache = (Set) txDeleteCaches.get(txId);
            deleteCache.add(key);
            deprune(deleteCache, key, delimiter);

            // guard logging as preparation is expensive
            if (loggingEnabled) {
                logger.log(txId + " removed '" + key + "'", logChannel, Logger.DEBUG);
            }
        } else {
            if (globalCache != null) {
                globalCache.remove(key);
                prune(globalCache, key, delimiter);
                if (loggingEnabled) {
                    logger.log("Removed '" + key + "'", logChannel, Logger.DEBUG);
                }
            }
        }
    }

    public synchronized void start(Object txId) {
        if (txId != null) {
            txChangeCaches.put(txId, new HashMap());
            txDeleteCaches.put(txId, new HashSet());
        }
    }

    public synchronized void rollback(Object txId) {
        if (txId != null) {

            if (loggingEnabled) {
                Map changeCache = (Map) txChangeCaches.get(txId);
                Set deleteCache = (Set) txDeleteCaches.get(txId);
                logger.log(
                    txId
                        + " rolled back "
                        + changeCache.size()
                        + " changes and "
                        + deleteCache.size()
                        + " scheduled deletes",
                    logChannel,
                    Logger.DEBUG);
            }

            // simply forget about tx
            forget(txId);
        }
    }

    public synchronized void commit(Object txId) {
        if (txId != null) {

            if (globalCache != null) {
                // apply local changes and deletes (is atomic as we have a global lock on this TxCache)

                Map changeCache = (Map) txChangeCaches.get(txId);
                for (Iterator it = changeCache.entrySet().iterator(); it.hasNext();) {
                    Map.Entry entry = (Map.Entry) it.next();
                    putToGlobalCache(entry.getKey(), entry.getValue());
                }

                Set deleteCache = (Set) txDeleteCaches.get(txId);
                for (Iterator it = deleteCache.iterator(); it.hasNext();) {
                    Object key = it.next();
                    globalCache.remove(key);
                }

                if (loggingEnabled) {
                    logger.log(
                        txId
                            + " committed "
                            + changeCache.size()
                            + " changes and "
                            + deleteCache.size()
                            + " scheduled deletes",
                        logChannel,
                        Logger.DEBUG);
                }
            }
            // finally forget about tx
            forget(txId);
        }
    }

    public synchronized void forget(Object txId) {
        if (txId != null) {
            txChangeCaches.remove(txId);
            txDeleteCaches.remove(txId);
        }
    }

    protected void hit(Object txId, Object key) {
        hits++;
        log(txId, key, true);
    }

    protected void miss(Object txId, Object key) {
        misses++;
        log(txId, key, false);
    }

    protected void log(Object txId, Object key, boolean hit) {
        if (loggingEnabled) {
            StringBuffer log = new StringBuffer();

            if (txId != null) {
                Map changeCache = (Map) txChangeCaches.get(txId);
                Set deleteCache = (Set) txDeleteCaches.get(txId);
                log.append(txId + " (" + changeCache.size() + ", " + deleteCache.size() + ") ");
            }

            log.append(
                (hit ? "Cache Hit: '" : "Cache Miss: '")
                    + key
                    + "' "
                    + hits
                    + " / "
                    + misses
                    + " / "
                    + (globalCache != null ? globalCache.size() : -1));
            logger.log(log.toString(), logChannel, Logger.DEBUG);
        }
    }
    
    protected void putToGlobalCache(Object key, Object value) {
        if (value instanceof TimeoutValuePair) {
            // start the timeout process as soon as the entry is pushed to the global store
            ((TimeoutValuePair) value).activate();
        }
        globalCache.put(key, value);
    }
    
    protected Object getFromGlobalCache(Object key) {
        Object value = globalCache.get(key);
        
        if (value != null && value instanceof TimeoutValuePair) {
            if (!((TimeoutValuePair) value).isValid()) {
                globalCache.remove(key);
                value = null;
            } else {
                value = ((TimeoutValuePair) value).value;
            }
        }
        return value;
    }
    
    protected Object getFromLocalCache(Map cache, Object key) {
        Object value = cache.get(key);

        // XXX local caches never time out
        if (value != null && value instanceof TimeoutValuePair) {
            value = ((TimeoutValuePair) value).value;
        }
        return value;
    }
    
    protected void prune(Map map, Object key, String delimiter) {
        String prefix = key + delimiter;
        for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
        	Map.Entry entry = (Map.Entry)it.next();
            String keyString = entry.getKey().toString();
        	if (keyString.startsWith(prefix)) {
        		it.remove();
        	}
        }
    }
    
    protected void deprune(Set set, Object key, String delimiter) {
        if (globalCache != null) {
            String prefix = key + delimiter;
            for (Iterator it = globalCache.entrySet().iterator(); it.hasNext();) {
                Map.Entry entry = (Map.Entry) it.next();
                String keyString = entry.getKey().toString();
                if (keyString.startsWith(prefix)) {
                    set.add(entry.getKey());
                }
            }
        }
    }
    
    static class TimeoutValuePair {

        Object value;
        long invalidationTime;
        long timeOut;
        
        TimeoutValuePair(Object value, long timeOut) {
            this.value = value;
            this.timeOut = timeOut;
            this.invalidationTime = -1;
        }
        
        void activate() {
            invalidationTime = timeOut + System.currentTimeMillis();
        }
        
        boolean isValid() {
            long currentTime = System.currentTimeMillis();
            return (invalidationTime > currentTime);
        }
    }
}
