/*
 * 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.myfaces.shared_tomahawk.util;

import java.util.*;


/**
 * A bi-level cache based on HashMap for caching objects with minimal sychronization
 * overhead. The limitation is that <code>remove()</code> is very expensive.
 * <p>
 * Access to L1 map is not sychronized, to L2 map is synchronized. New values
 * are first stored in L2. Once there have been more that a specified mumber of
 * misses on L1, L1 and L2 maps are merged and the new map assigned to L1
 * and L2 cleared.
 * </p>
 * <p>
 * IMPORTANT:entrySet(), keySet(), and values() return unmodifiable snapshot collections.
 * </p>
 *
 * @author Anton Koinov (latest modification by $Author: grantsmith $)
 * @version $Revision: 472630 $ $Date: 2006-11-08 15:40:03 -0500 (Wed, 08 Nov 2006) $
 */
public abstract class BiLevelCacheMap implements Map
{
    //~ Instance fields ----------------------------------------------------------------------------

    private static final int INITIAL_SIZE_L1 = 32;

    /** To preinitialize <code>_cacheL1</code> with default values use an initialization block */
    protected Map       _cacheL1;

    /** Must be final because it is used for synchronization */
    private final Map   _cacheL2;
    private final int   _mergeThreshold;
    private int         _missCount;

    //~ Constructors -------------------------------------------------------------------------------

    public BiLevelCacheMap(int mergeThreshold)
    {
        _cacheL1            = new HashMap(INITIAL_SIZE_L1);
        _cacheL2            = new HashMap(HashMapUtils.calcCapacity(mergeThreshold));
        _mergeThreshold     = mergeThreshold;
    }

    //~ Methods ------------------------------------------------------------------------------------

    public boolean isEmpty()
    {
        synchronized (_cacheL2) {
            return _cacheL1.isEmpty() && _cacheL2.isEmpty();
        }
    }

    public void clear()
    {
        synchronized (_cacheL2) {
            _cacheL1 = new HashMap(); // dafault size
            _cacheL2.clear();
        }
    }

    public boolean containsKey(Object key)
    {
        synchronized (_cacheL2) {
            return _cacheL1.containsKey(key) || _cacheL2.containsKey(key);
        }
    }

    public boolean containsValue(Object value)
    {
        synchronized (_cacheL2) {
            return _cacheL1.containsValue(value) || _cacheL2.containsValue(value);
        }
    }

    public Set entrySet()
    {
        synchronized (_cacheL2)
        {
            mergeIfL2NotEmpty();
            return Collections.unmodifiableSet(_cacheL1.entrySet());
        }
    }

    public Object get(Object key)
    {
        Map    cacheL1 = _cacheL1;
        Object retval = cacheL1.get(key);
        if (retval != null)
        {
            return retval;
        }

        synchronized (_cacheL2)
        {
            // Has another thread merged caches while we were waiting on the mutex? Then check L1 again
            if (cacheL1 != _cacheL1)
            {
                if ((retval = _cacheL1.get(key)) != null)
                {
                    // do not update miss count (it is not a miss anymore)
                    return retval;
                }
            }

            if ((retval = _cacheL2.get(key)) == null)
            {
                retval = newInstance(key);
                if (retval != null)
                {
                    put(key, retval);
                    mergeIfNeeded();
                }
            }
            else
            {
                mergeIfNeeded();
            }
        }

        return retval;
    }

    public Set keySet()
    {
        synchronized (_cacheL2)
        {
            mergeIfL2NotEmpty();
            return Collections.unmodifiableSet(_cacheL1.keySet());
        }
    }

    /**
     * If key is already in cacheL1, the new value will show with a delay,
     * since merge L2->L1 may not happen immediately. To force the merge sooner,
     * call <code>size()<code>.
     */
    public Object put(Object key, Object value)
    {
        synchronized (_cacheL2)
        {
            _cacheL2.put(key, value);

            // not really a miss, but merge to avoid big increase in L2 size
            // (it cannot be reallocated, it is final)
            mergeIfNeeded();
        }

        return value;
    }

    public void putAll(Map map)
    {
        synchronized (_cacheL2)
        {
            mergeIfL2NotEmpty();

            // sepatare merge to avoid increasing L2 size too much
            // (it cannot be reallocated, it is final)
            merge(map);
        }
    }

    /** This operation is very expensive. A full copy of the Map is created */
    public Object remove(Object key)
    {
        synchronized (_cacheL2)
        {
            if (!_cacheL1.containsKey(key) && !_cacheL2.containsKey(key))
            {
                // nothing to remove
                return null;
            }

            Object retval;
            Map newMap;
            synchronized (_cacheL1)
            {
                // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized
                // at least until JVM 1.5 where this should be guaranteed by the volatile keyword
                newMap = HashMapUtils.merge(_cacheL1, _cacheL2);
                retval = newMap.remove(key);
            }

            _cacheL1 = newMap;
            _cacheL2.clear();
            _missCount = 0;
            return retval;
        }
    }

    public int size()
    {
        // Note: cannot simply return L1.size + L2.size
        //       because there might be overlaping of keys
        synchronized (_cacheL2)
        {
            mergeIfL2NotEmpty();
            return _cacheL1.size();
        }
    }

    public Collection values()
    {
        synchronized (_cacheL2)
        {
            mergeIfL2NotEmpty();
            return Collections.unmodifiableCollection(_cacheL1.values());
        }
    }

    private void mergeIfL2NotEmpty()
    {
        if (!_cacheL2.isEmpty())
        {
            merge(_cacheL2);
        }
    }

    private void mergeIfNeeded()
    {
        if (++_missCount >= _mergeThreshold)
        {
            merge(_cacheL2);
        }
    }

    private void merge(Map map)
    {
        Map newMap;
        synchronized (_cacheL1)
        {
            // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized
            // at least until JVM 1.5 where this should be guaranteed by the volatile keyword
            // But is this enough (in our particular case) to resolve the issues with DCL?
            newMap = HashMapUtils.merge(_cacheL1, map);
        }
        _cacheL1 = newMap;
        _cacheL2.clear();
        _missCount = 0;
    }

    /**
     * Subclasses must implement to have automatic creation of new instances
     * or alternatively can use <code>put<code> to add new items to the cache.<br>
     *
     * Implementing this method is prefered to guarantee that there will be only
     * one instance per key ever created. Calling put() to add items in a multi-
     * threaded situation will require external synchronization to prevent two
     * instances for the same key, which defeats the purpose of this cache
     * (put() is useful when initialization is done during startup and items
     * are not added during execution or when (temporarily) having possibly two
     * or more instances of the same key is not of concern).<br>
     *
     * @param key lookup key
     * @return new instace for the requested key
     */
    protected abstract Object newInstance(Object key);
}
