/*
 * Copyright 2015 Terracotta, Inc., a Software AG company.
 *
 * 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.terracotta.offheapstore;

import java.util.Random;
import java.util.concurrent.locks.Lock;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import org.terracotta.offheapstore.exceptions.OversizeMappingException;
import org.terracotta.offheapstore.paging.PageSource;
import org.terracotta.offheapstore.pinning.PinnableCache;
import org.terracotta.offheapstore.pinning.PinnableSegment;
import org.terracotta.offheapstore.storage.StorageEngine;
import org.terracotta.offheapstore.util.DebuggingUtils;

import java.nio.IntBuffer;

An abstract off-heap cache implementation.
 Subclasses must implement the two getEvictionIndex(...) methods to instruct the cache regarding which mappings to remove. 
Author:
Chris Dennis, Manoj Govindassamy
Type parameters:
<K> – the type of keys maintained by this map
<V> – the type of mapped values/**
 * An abstract off-heap cache implementation.
 * <p>
 * Subclasses must implement the two {@code getEvictionIndex(...)} methods to
 * instruct the cache regarding which mappings to remove.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author Chris Dennis
 * @author Manoj Govindassamy
 */
public abstract class AbstractOffHeapClockCache<K, V> extends AbstractLockedOffHeapHashMap<K, V> implements PinnableCache<K, V>, PinnableSegment<K, V> {

  private static final Logger LOGGER = LoggerFactory.getLogger(AbstractOffHeapClockCache.class);

  private static final int PRESENT_CLOCK = 1 << (Integer.SIZE - 1);

  private final Random rndm = new Random();

  private int clockHand;

  public AbstractOffHeapClockCache(PageSource source, StorageEngine<? super K, ? super V> storageEngine) {
    super(source, storageEngine);
  }

  public AbstractOffHeapClockCache(PageSource source, boolean tableAllocationsSteal, StorageEngine<? super K, ? super V> storageEngine) {
    super(source, tableAllocationsSteal, storageEngine);
  }

  public AbstractOffHeapClockCache(PageSource source, StorageEngine<? super K, ? super V> storageEngine, boolean bootstrap) {
    super(source, storageEngine, bootstrap);
  }

  public AbstractOffHeapClockCache(PageSource source, StorageEngine<? super K, ? super V> storageEngine, int tableSize) {
    super(source, storageEngine, tableSize);
  }

  public AbstractOffHeapClockCache(PageSource source, boolean tableAllocationsSteal, StorageEngine<? super K, ? super V> storageEngine, int tableSize) {
    super(source, tableAllocationsSteal, storageEngine, tableSize);
  }

  public AbstractOffHeapClockCache(PageSource source, StorageEngine<? super K, ? super V> storageEngine, int tableSize, boolean bootstrap) {
    super(source, storageEngine, tableSize, bootstrap);
  }

  @Override
  protected void storageEngineFailure(Object failure) {
    if (isEmpty()) {
      throw new OversizeMappingException("Storage Engine and Eviction Failed - Empty Map\nStorage Engine : " + storageEngine);
    } else {
      int evictionIndex = getEvictionIndex();
      if (evictionIndex < 0) {
        throw new OversizeMappingException("Storage Engine and Eviction Failed - Everything Pinned (" + getSize() + " mappings) \n" + "Storage Engine : " + storageEngine);
      } else {
        evict(evictionIndex, false);
      }
    }
  }

  @Override
  protected void tableExpansionFailure(int start, int length) {
    int evictionIndex = getEvictionIndex(start, length);
    if (evictionIndex < 0) {
      if (tryIncreaseReprobe()) {
        LOGGER.debug("Increased reprobe to {} slots for a {} slot table in a last ditch attempt to avoid storage failure.", getReprobeLength(), getTableCapacity());
      } else {
        String msg = "Table Expansion and Eviction Failed.\n" + "Current Table Size (slots) : " + getTableCapacity() + '\n' +
                    "Current Reprobe Length     : " + getReprobeLength() + '\n' +
                    "Resize Will Require        : " + DebuggingUtils.toBase2SuffixedString(getTableCapacity() * ENTRY_SIZE * (Integer.SIZE / Byte.SIZE) * 2) + "B\n" +
                    "Table Page Source          : " + tableSource;
        throw new OversizeMappingException(msg);
      }
    } else {
      evict(evictionIndex, false);
    }
  }

  @Override
  protected void hit(IntBuffer entry) {
    entry.put(STATUS, PRESENT_CLOCK | entry.get(STATUS));
  }

  
Return the table offset of the to be evicted mapping.

The mapping to be evicted can occur anywhere in this cache's table.
Returns:
table offset of the mapping to be evicted/**
   * Return the table offset of the to be evicted mapping.
   * <p>
   * The mapping to be evicted can occur anywhere in this cache's table.
   *
   * @return table offset of the mapping to be evicted
   */
  public int getEvictionIndex() {
    /*
     * If the table has been shrunk then it's possible for the clock-hand to
     * point past the end of the table.  We cannot allow the initial-hand to
     * be equal to this otherwise we may never be able to terminate this loop.
     */
    if (clockHand >= hashtable.capacity()) {
      clockHand = 0;
    }

    int initialHand = clockHand;
    int loops = 0;
    while (true) {
      if ((clockHand += ENTRY_SIZE) + STATUS >= hashtable.capacity()) {
        clockHand = 0;
      }

      int hand = hashtable.get(clockHand + STATUS);

      if (evictable(hand) && ((hand & PRESENT_CLOCK) == 0)) {
        return clockHand;
      } else if ((hand & PRESENT_CLOCK) == PRESENT_CLOCK) {
        hashtable.put(clockHand + STATUS, hand & ~PRESENT_CLOCK);
      }

      if (initialHand == clockHand && ++loops == 2) {
        return -1;
      }
    }
  }

  
Return the table offset of the to be evicted mapping within the given probe
sequence.

The mapping to be evicted must occur within the given probe sequence.
Params:
start – initial slot in probe sequence
length – number of slots in probe sequence
Returns:
table offset of the mapping to be evicted/**
   * Return the table offset of the to be evicted mapping within the given probe
   * sequence.
   * <p>
   * The mapping to be evicted must occur within the given probe sequence.
   *
   * @param start initial slot in probe sequence
   * @param length number of slots in probe sequence
   * @return table offset of the mapping to be evicted
   */
  private int getEvictionIndex(int start, int length) {
    /*
     * TODO This pseudo clock eviction may not be the best algorithm.  Currently
     * the algorithm is to do a regular eviction selection, which helps the clock
     * by advancing it, and also some clock-bit clearing.  If the resultant index
     * is in our probe sequence (which isn't the most simple of calculations - I
     * think I have it right here) then just return that as the eviction index,
     * and all is good.  If that index is not in our probe sequence, then we evict
     * that element anyway, we then go on to see if any of the entries in our
     * probe sequence have their clock bit cleared, if so we evict one of them to
     * clear space for the incoming element.  If all elements have set clock bits
     * then we just kick one out at random.
     */
    int index = getEvictionIndex();

    int tableLength = hashtable.capacity();
    int probeLength = length * ENTRY_SIZE;

    if (probeLength >= hashtable.capacity()) {
      return index;
    }

    int end = (start + probeLength) & (tableLength - 1);

    if (index < 0) {
      return index;
    } else if ((end > start) && (index >= start) && (index <= end)) {
      return index;
    } else if ((end < start) && ((index >= start) || (index < end))) {
      return index;
    } else {
      evict(index, false);

      for (int i = 0, clock = start; i < length; i++) {
        if ((clock += ENTRY_SIZE) >= tableLength) {
          clock = start;
        }

        int hand = hashtable.get(clock + STATUS);

        if (evictable(hand) && ((hand & PRESENT_CLOCK) == 0)) {
          return clock;
        }
      }

      int lastEvictable = -1;
      for (int i = 0, clock = start; i < rndm.nextInt(length) || (lastEvictable < 0 && i < length); i++) {
        if ((clock += ENTRY_SIZE) >= tableLength) {
          clock = start;
        }

        int hand = hashtable.get(clock + STATUS);

        if (evictable(hand)) {
          lastEvictable = clock;
        }
      }
      return lastEvictable;
    }
  }

  protected boolean evictable(int status) {
    return (status & STATUS_USED) == STATUS_USED && ((status & Metadata.PINNED) == 0);
  }

  @Override
  public boolean evict(int index, boolean shrink) {
    Lock l = writeLock();
    l.lock();
    try {
      if (evictable(hashtable.get(index + STATUS))) {
        removeAtTableOffset(index, shrink);
        return true;
      } else {
        return false;
      }
    } finally {
      l.unlock();
    }
  }

  @Override
  public boolean isPinned(Object key) {
    Integer metadata = getMetadata(key, Metadata.PINNED);
    return metadata != null && metadata != 0;
  }

  @Override
  public void setPinning(K key, boolean pinned) {
    if (pinned) {
      getAndSetMetadata(key, Metadata.PINNED, Metadata.PINNED);
    } else {
      getAndSetMetadata(key, Metadata.PINNED, 0);
    }
  }

  @Override
  public V putPinned(K key, V value) {
    return put(key, value, Metadata.PINNED);
  }

  @Override
  public V getAndPin(K key) {
    return getValueAndSetMetadata(key, Metadata.PINNED, Metadata.PINNED);
  }
}