/*

  * #%L

  * AbstractStringCache.java - mongodb-async-driver - Allanbank Consulting, Inc.

  * %%

  * Copyright (C) 2011 - 2014 Allanbank Consulting, Inc.

  * %%

  * 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.

  * #L%

  */

 package com.allanbank.mongodb.bson.io;

 import java.io.Serializable;

 import java.util.Comparator;

 import java.util.Iterator;

 import java.util.LinkedList;

 import java.util.List;

 import java.util.SortedMap;

 import java.util.TreeMap;

 import java.util.concurrent.ConcurrentHashMap;

 import java.util.concurrent.ConcurrentMap;

 import java.util.concurrent.atomic.AtomicInteger;

 /**

  * AbstractStringCache provides the basic functionality for tracking string

  * usage and triggering rebuilds of the cache over time.

  * <p>

  * The basic function of the cache is to maintain two structures. The first

  * (provided by this class) tracks the usage of strings in the cache via a

  * 'seen' {@link ConcurrentMap}. As the cache sees more usage it will

  * periodically trim entries from the map that are not being used often (this is

  * to limit memory usage). Once the cache thinks it has seen enough usage it

  * will trigger the building of the runtime cache. This runtime cache does not

  * require any locking as it is read-only after being constructed.

  * </p>

  * <p>

  * There are two controls on the amount of caching instances of this class will

  * do:

  * </p>

  * <ol>

  * <li>

  * {@link #getMaxCacheLength()} limits the length of the encoded bytes this

  * class will try and retrieve from the cache. Setting this value to zero

  * disables the cache and limit any memory overhead.</li>

  * <li>{@link #getMaxCacheEntries()} controls the number of cached entries in

  * the runtime-cache and how often the accumulated statistics are trimmed. Each

  * entry represents a single encoded string.</li>

  * </ol>

  * 

  * 

  * @api.no This class is <b>NOT</b> part of the drivers API. This class may be

  *         mutated in incompatible ways between any two releases of the driver.

  * @copyright 2014, Allanbank Consulting, Inc., All Rights Reserved

  */

 public abstract class AbstractStringCache {

     /** The default maximum number of entries to keep in the cache. */

     public static final int DEFAULT_MAX_CACHE_ENTRIES = 24;

     /** The default maximum length byte array to cache. */

     public static final int DEFAULT_MAX_CACHE_LENGTH = 25;

     /** The maximum value for the multiplier. */

     protected static final int MAX_MULTIPLIER = 100;

     /**

      * The maximum length of a string to cache. This can be used to stop a

      * single long string from pushing useful values out of the cache.

      */

     protected int myMaxCacheLength;

     /** The maximum number of entries to have in the cache. */

     protected int myMaxCachEntries;

     /**

      * The multiplier for the number of times the cache is used before we

      * re-load the cache.

      */

     protected volatile int myMaxCachEntriesMultiplier;

     /**

      * The map of seen strings that will be used periodically to build the cache

      * cache.

      */

     protected final ConcurrentMap<String, SeenString> mySeen;

     /**

      * The number of time the cache has been used since the last re-load of

      * runtime, read-only cache.

      */

     protected final AtomicInteger myUseCount;

     /**

      * Creates a new AbstractStringCache.

      */

     public AbstractStringCache() {

         super();

         mySeen = new ConcurrentHashMap<String, SeenString>(1024);

         myMaxCacheLength = DEFAULT_MAX_CACHE_LENGTH;

         myMaxCachEntries = DEFAULT_MAX_CACHE_ENTRIES;

         myMaxCachEntriesMultiplier = 0;

         myUseCount = new AtomicInteger(0);

     }

     /**

      * Returns the maximum node count.

      * 

      * @return The maximum node count.

      */

     public int getMaxCacheEntries() {

         return myMaxCachEntries;

     }

     /**

      * Returns the maximum length of strings to cache. This can be used to stop

      * a single long string from pushing useful values out of the cache.

      * 

      * @return The maximum length of strings to cache.

      */

     public int getMaxCacheLength() {

         return myMaxCacheLength;

     }

     /**

      * Sets the value of maximum number of cached strings.

      * 

      * @param maxCacheEntries

      *            The new value for the maximum number of cached strings.

      */

     public void setMaxCacheEntries(final int maxCacheEntries) {

         myMaxCachEntries = maxCacheEntries;

     }

     /**

      * Sets the value of maximum length of strings to cache to the new value.

      * This can be used to stop a single long string from pushing useful values

      * out of the cache.

      * 

      * @param maxlength

      *            The new value for the maximum length of strings to cache.

      */

     public void setMaxCacheLength(final int maxlength) {

         myMaxCacheLength = maxlength;

         // The user has turned the cache off. Release all of the memory.

         if (maxlength <= 0) {

             clear();

         }

     }

     /**

      * Notification that a string/byte[] have been used.

      * 

      * @param source

      *            The bytes in the string.

      * @param offset

      *            The offset of the first byte.

      * @param length

      *            The length of the bytes with a terminal zero byte.

      * @param decoded

      *            The decoded string.

      */

     public void used(final String decoded, final byte[] source,

             final int offset, final int length) {

         // Check for the easiest value to cache or entries that are too long.

         if ((length <= 1) || (myMaxCacheLength < length)) {

             return;

         }

         SeenString entry = mySeen.get(decoded);

         if (entry == null) {

             entry = new SeenString(source, offset, length, decoded);

             final SeenString existing = mySeen.putIfAbsent(decoded, entry);

             if (existing != null) {

                 entry = existing;

             }

         }

         // Count the use.

         entry.incrementCount();

         // Rebuild the count after period of use.

         int use = myUseCount.incrementAndGet();

         while ((myMaxCachEntries * myMaxCachEntriesMultiplier) < use) {

             use = tryRebuild(use);

         }

         // Periodically trim low count entries.

         if ((use != 0) && ((use % myMaxCachEntries) == 0)) {

             trimPending();

         }

     }

     /**

      * Builds a map of the seen strings at each count. The order of the map is

      * reversed so that higher counts are first in the map.

      * 

      * @return A map of the seen strings at each count.

      */

     protected SortedMap<Integer, List<SeenString>> buildCacheGroups() {

         myMaxCachEntriesMultiplier = Math.min(myMaxCachEntriesMultiplier + 1,

                 MAX_MULTIPLIER);

         // Copy the current entries.

         final SortedMap<Integer, List<SeenString>> order = new TreeMap<Integer, List<SeenString>>(

                 ReverseIntegerComparator.INSTANCE);

         for (final SeenString seen : mySeen.values()) {

             final Integer seenCount = Integer.valueOf(seen.reset());

             List<SeenString> seenAtCount = order.get(seenCount);

             if (seenAtCount == null) {

                 seenAtCount = new LinkedList<SeenString>();

                 order.put(seenCount, seenAtCount);

             }

             seenAtCount.add(seen);

         }

         return order;

     }

     /**

      * Clears the cache.

      */

     protected void clear() {

         mySeen.clear();

         myUseCount.set(0);

     }

     /**

      * Rebuilds the cache from the current {@link #mySeen} map. By the end of

      * the method the caceh should have been rebuild and the {@link #mySeen} map

      * cleared.

      */

     protected abstract void rebuildCache();

     /**

      * Trims the seen map of any entries that have not accumulated many counts.

      * This is to avoid the seen map holding too many entries.

      */

     private void trimPending() {

         // Only keep entries that have more than 1% (or more than 1 if 1% is <

         // 1) entries.

         final int trimLevel = Math.max(1, (int) (myMaxCachEntries * 0.01));

         int toRemove = Math.max(0, mySeen.size() - myMaxCachEntries);

         final Iterator<SeenString> iter = mySeen.values().iterator();

         while (iter.hasNext() && (0 < toRemove)) {

             final SeenString seen = iter.next();

             if (seen.getCount() <= trimLevel) {

                 iter.remove();

                 toRemove -= 1;

             }

         }

     }

     /**

      * Attempts to rebuild the cache.

      * 

      * @param use

      *            The expected use count.

      * @return The use count after the attempt.

      */

     private int tryRebuild(final int use) {

         if (myUseCount.compareAndSet(use, 0)) {

             rebuildCache();

             return 0;

         }

         return myUseCount.get();

     }

     /**

      * ReverseIntegerComparator provides a {@link Comparator} that considers

      * higher value integers to be less then lower value integers.

      * 

      * @copyright 2014, Allanbank Consulting, Inc., All Rights Reserved

      */

     public static class ReverseIntegerComparator implements

             Comparator<Integer>, Serializable {

         /** The single instance of the comparator. */

         public static final Comparator<Integer> INSTANCE = new ReverseIntegerComparator();

         /** The serialization version for the class. */

         private static final long serialVersionUID = 7342816815375930353L;

         /**

          * Creates a new ReverseIntegerComparator. Private since this class is

          * stateless and we only need a single copy.

          */

         private ReverseIntegerComparator() {

             super();

         }

         /**

          * {@inheritDoc}

          * <p>

          * Overridden to reverse the comparison of integers.

          * </p>

          */

         @Override

         public int compare(final Integer o1, final Integer o2) {

             final int value = o1.compareTo(o2);

             if (value < 0) {

                 return 1;

             }

             else if (0 < value) {

                 return -1;

             }

             else {

                 return 0;

             }

         }

     }

 }