package org.apache.lucene.util;

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

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.Map;

/**
 * Simple concurrent LRU cache, using a "double barrel"
 * approach where two ConcurrentHashMaps record entries.
 *
 * <p>At any given time, one hash is primary and the other
 * is secondary.  {@link #get} first checks primary, and if
 * that's a miss, checks secondary.  If secondary has the
 * entry, it's promoted to primary (<b>NOTE</b>: the key is
 * cloned at this point).  Once primary is full, the
 * secondary is cleared and the two are swapped.</p>
 *
 * <p>This is not as space efficient as other possible
 * concurrent approaches (see LUCENE-2075): to achieve
 * perfect LRU(N) it requires 2*N storage.  But, this
 * approach is relatively simple and seems in practice to
 * not grow unbounded in size when under hideously high
 * load.</p>
 *
 * @lucene.internal
 */

final public class DoubleBarrelLRUCache<K extends DoubleBarrelLRUCache.CloneableKey,V> {

  public static abstract class CloneableKey {
    @Override
    abstract public Object clone();
  }

  private final Map<K,V> cache1;
  private final Map<K,V> cache2;
  private final AtomicInteger countdown;
  private volatile boolean swapped;
  private final int maxSize;

  public DoubleBarrelLRUCache(int maxSize) {
    this.maxSize = maxSize;
    countdown = new AtomicInteger(maxSize);
    cache1 = new ConcurrentHashMap<K,V>();
    cache2 = new ConcurrentHashMap<K,V>();
  }

  @SuppressWarnings("unchecked") 
  public V get(K key) {
    final Map<K,V> primary;
    final Map<K,V> secondary;
    if (swapped) {
      primary = cache2;
      secondary = cache1;
    } else {
      primary = cache1;
      secondary = cache2;
    }

    // Try primary first
    V result = primary.get(key);
    if (result == null) {
      // Not found -- try secondary
      result = secondary.get(key);
      if (result != null) {
        // Promote to primary
        put((K) key.clone(), result);
      }
    }
    return result;
  }

  public void put(K key, V value) {
    final Map<K,V> primary;
    final Map<K,V> secondary;
    if (swapped) {
      primary = cache2;
      secondary = cache1;
    } else {
      primary = cache1;
      secondary = cache2;
    }
    primary.put(key, value);

    if (countdown.decrementAndGet() == 0) {
      // Time to swap

      // NOTE: there is saturation risk here, that the
      // thread that's doing the clear() takes too long to
      // do so, while other threads continue to add to
      // primary, but in practice this seems not to be an
      // issue (see LUCENE-2075 for benchmark & details)

      // First, clear secondary
      secondary.clear();

      // Second, swap
      swapped = !swapped;

      // Third, reset countdown
      countdown.set(maxSize);
    }
  }
}