View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one
    3    * or more contributor license agreements.  See the NOTICE file
    4    * distributed with this work for additional information
    5    * regarding copyright ownership.  The ASF licenses this file
    6    * to you under the Apache License, Version 2.0 (the
    7    * "License"); you may not use this file except in compliance
    8    * with the License.  You may obtain a copy of the License at
    9    *
    10   *   http://www.apache.org/licenses/LICENSE-2.0
    11   *
    12   * Unless required by applicable law or agreed to in writing,
    13   * software distributed under the License is distributed on an
    14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    15   * KIND, either express or implied.  See the License for the
    16   * specific language governing permissions and limitations
    17   * under the License.
    18   */
    19  package org.apache.myfaces.shared_orchestra.util;
    20
    21  import java.util.*;
    22
    23
    24  /**
    25   * A bi-level cache based on HashMap for caching objects with minimal sychronization
    26   * overhead. The limitation is that <code>remove()</code> is very expensive.
    27   * <p>
    28   * Access to L1 map is not sychronized, to L2 map is synchronized. New values
    29   * are first stored in L2. Once there have been more that a specified mumber of
    30   * misses on L1, L1 and L2 maps are merged and the new map assigned to L1
    31   * and L2 cleared.
    32   * </p>
    33   * <p>
    34   * IMPORTANT:entrySet(), keySet(), and values() return unmodifiable snapshot collections.
    35   * </p>
    36   *
    37   * @author Anton Koinov (latest modification by $Author: grantsmith $)
    38   * @version $Revision: 472630 $ $Date: 2006-11-08 15:40:03 -0500 (Wed, 08 Nov 2006) $
    39   */
    40  public abstract class BiLevelCacheMap implements Map
    41  {
    42      //~ Instance fields ----------------------------------------------------------------------------
    43
    44      private static final int INITIAL_SIZE_L1 = 32;
    45
    46      /** To preinitialize <code>_cacheL1</code> with default values use an initialization block */
    47      protected Map       _cacheL1;
    48
    49      /** Must be final because it is used for synchronization */
    50      private final Map   _cacheL2;
    51      private final int   _mergeThreshold;
    52      private int         _missCount;
    53
    54      //~ Constructors -------------------------------------------------------------------------------
    55
    56      public BiLevelCacheMap(int mergeThreshold)
    57      {
    58          _cacheL1            = new HashMap(INITIAL_SIZE_L1);
    59          _cacheL2            = new HashMap(HashMapUtils.calcCapacity(mergeThreshold));
    60          _mergeThreshold     = mergeThreshold;
    61      }
    62
    63      //~ Methods ------------------------------------------------------------------------------------
    64
    65      public boolean isEmpty()
    66      {
    67          synchronized (_cacheL2) {
    68              return _cacheL1.isEmpty() && _cacheL2.isEmpty();
    69          }
    70      }
    71
    72      public void clear()
    73      {
    74          synchronized (_cacheL2) {
    75              _cacheL1 = new HashMap(); // dafault size
    76              _cacheL2.clear();
    77          }
    78      }
    79
    80      public boolean containsKey(Object key)
    81      {
    82          synchronized (_cacheL2) {
    83              return _cacheL1.containsKey(key) || _cacheL2.containsKey(key);
    84          }
    85      }
    86
    87      public boolean containsValue(Object value)
    88      {
    89          synchronized (_cacheL2) {
    90              return _cacheL1.containsValue(value) || _cacheL2.containsValue(value);
    91          }
    92      }
    93
    94      public Set entrySet()
    95      {
    96          synchronized (_cacheL2)
    97          {
    98              mergeIfL2NotEmpty();
    99              return Collections.unmodifiableSet(_cacheL1.entrySet());
    100         }
    101     }
    102
    103     public Object get(Object key)
    104     {
    105         Map    cacheL1 = _cacheL1;
    106         Object retval = cacheL1.get(key);
    107         if (retval != null)
    108         {
    109             return retval;
    110         }
    111
    112         synchronized (_cacheL2)
    113         {
    114             // Has another thread merged caches while we were waiting on the mutex? Then check L1 again
    115             if (cacheL1 != _cacheL1)
    116             {
    117                 if ((retval = _cacheL1.get(key)) != null)
    118                 {
    119                     // do not update miss count (it is not a miss anymore)
    120                     return retval;
    121                 }
    122             }
    123
    124             if ((retval = _cacheL2.get(key)) == null)
    125             {
    126                 retval = newInstance(key);
    127                 if (retval != null)
    128                 {
    129                     put(key, retval);
    130                     mergeIfNeeded();
    131                 }
    132             }
    133             else
    134             {
    135                 mergeIfNeeded();
    136             }
    137         }
    138
    139         return retval;
    140     }
    141
    142     public Set keySet()
    143     {
    144         synchronized (_cacheL2)
    145         {
    146             mergeIfL2NotEmpty();
    147             return Collections.unmodifiableSet(_cacheL1.keySet());
    148         }
    149     }
    150
    151     /**
    152      * If key is already in cacheL1, the new value will show with a delay,
    153      * since merge L2->L1 may not happen immediately. To force the merge sooner,
    154      * call <code>size()<code>.
    155      */
    156     public Object put(Object key, Object value)
    157     {
    158         synchronized (_cacheL2)
    159         {
    160             _cacheL2.put(key, value);
    161
    162             // not really a miss, but merge to avoid big increase in L2 size
    163             // (it cannot be reallocated, it is final)
    164             mergeIfNeeded();
    165         }
    166
    167         return value;
    168     }
    169
    170     public void putAll(Map map)
    171     {
    172         synchronized (_cacheL2)
    173         {
    174             mergeIfL2NotEmpty();
    175
    176             // sepatare merge to avoid increasing L2 size too much
    177             // (it cannot be reallocated, it is final)
    178             merge(map);
    179         }
    180     }
    181
    182     /** This operation is very expensive. A full copy of the Map is created */
    183     public Object remove(Object key)
    184     {
    185         synchronized (_cacheL2)
    186         {
    187             if (!_cacheL1.containsKey(key) && !_cacheL2.containsKey(key))
    188             {
    189                 // nothing to remove
    190                 return null;
    191             }
    192
    193             Object retval;
    194             Map newMap;
    195             synchronized (_cacheL1)
    196             {
    197                 // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized
    198                 // at least until JVM 1.5 where this should be guaranteed by the volatile keyword
    199                 newMap = HashMapUtils.merge(_cacheL1, _cacheL2);
    200                 retval = newMap.remove(key);
    201             }
    202
    203             _cacheL1 = newMap;
    204             _cacheL2.clear();
    205             _missCount = 0;
    206             return retval;
    207         }
    208     }
    209
    210     public int size()
    211     {
    212         // Note: cannot simply return L1.size + L2.size
    213         //       because there might be overlaping of keys
    214         synchronized (_cacheL2)
    215         {
    216             mergeIfL2NotEmpty();
    217             return _cacheL1.size();
    218         }
    219     }
    220
    221     public Collection values()
    222     {
    223         synchronized (_cacheL2)
    224         {
    225             mergeIfL2NotEmpty();
    226             return Collections.unmodifiableCollection(_cacheL1.values());
    227         }
    228     }
    229
    230     private void mergeIfL2NotEmpty()
    231     {
    232         if (!_cacheL2.isEmpty())
    233         {
    234             merge(_cacheL2);
    235         }
    236     }
    237
    238     private void mergeIfNeeded()
    239     {
    240         if (++_missCount >= _mergeThreshold)
    241         {
    242             merge(_cacheL2);
    243         }
    244     }
    245
    246     private void merge(Map map)
    247     {
    248         Map newMap;
    249         synchronized (_cacheL1)
    250         {
    251             // "dummy" synchronization to guarantee _cacheL1 will be assigned after fully initialized
    252             // at least until JVM 1.5 where this should be guaranteed by the volatile keyword
    253             // But is this enough (in our particular case) to resolve the issues with DCL?
    254             newMap = HashMapUtils.merge(_cacheL1, map);
    255         }
    256         _cacheL1 = newMap;
    257         _cacheL2.clear();
    258         _missCount = 0;
    259     }
    260
    261     /**
    262      * Subclasses must implement to have automatic creation of new instances
    263      * or alternatively can use <code>put<code> to add new items to the cache.<br>
    264      *
    265      * Implementing this method is prefered to guarantee that there will be only
    266      * one instance per key ever created. Calling put() to add items in a multi-
    267      * threaded situation will require external synchronization to prevent two
    268      * instances for the same key, which defeats the purpose of this cache
    269      * (put() is useful when initialization is done during startup and items
    270      * are not added during execution or when (temporarily) having possibly two
    271      * or more instances of the same key is not of concern).<br>
    272      *
    273      * @param key lookup key
    274      * @return new instace for the requested key
    275      */
    276     protected abstract Object newInstance(Object key);
    277 }