/*
 *      Copyright (C) 2014 Robert Stupp, Koeln, Germany, robert-stupp.de
 *
 *   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.caffinitas.ohc.linked;

import org.caffinitas.ohc.OHCacheBuilder;

final class OffHeapLinkedWTinyLFUMap extends OffHeapLinkedMap
{
    private long edenLruHead;
    private long edenLruTail;
    private long edenFreeCapacity;
    private long edenCapacity;

    private long mainLruHead;
    private long mainLruTail;
    private long mainFreeCapacity;
    private long mainCapacity;

    private long probationCapacity;

    private FrequencySketch frequencySketch;

    private final double edenSize;

    OffHeapLinkedWTinyLFUMap(OHCacheBuilder builder, long freeCapacity)
    {
        super(builder);

        edenSize = builder.getEdenSize();
        if (edenSize <= 0d)
            throw new IllegalArgumentException("Illegal edenSize, must be > 0");

        updateFreeCapacity(freeCapacity);

        int freqSketchSize = builder.getFrequencySketchSize();
        if (freqSketchSize <= 0)
            freqSketchSize = table.size();

        frequencySketch = new FrequencySketch(freqSketchSize);
    }

    void release()
    {
        boolean wasFirst = lock();
        try
        {
            frequencySketch.release();

            super.release();
        }
        finally
        {
            unlock(wasFirst);
        }
    }

    long freeCapacity()
    {
        return edenFreeCapacity + mainFreeCapacity;
    }

    void updateFreeCapacity(long diff)
    {
        long edenPart = (long)(edenSize * diff);
        long mainPart = diff - edenPart;

        edenFreeCapacity += edenPart;
        edenCapacity += edenPart;
        mainFreeCapacity += mainPart;
        mainCapacity += mainPart;

        // capacity of probation area needs to be as big as eden because when a new entry is added, it might be
        // necessary to check all entries in the whole eden generation whether these are admitted for main generation.
        probationCapacity = (long)(edenSize * mainCapacity);
    }

    LongArrayList ensureFreeSpaceForNewEntry(long bytes)
    {
        // enough free capacity in eden generation?
        if (edenFreeCapacity >= bytes)
            return null;

        // eden generation too small for entry?
        if (edenCapacity < bytes)
            return null;

        // need to make room in eden

        long candidateAdr = edenLruTail;
        long nextCandidateAdr;

        // main generation has enough free capacity for candidate from eden, just move candidate to main generation and return
        // (note: this happens when the cache is initially empty and new entries get added)
        if (mainLruTail == 0L || mainFreeCapacity >= bytes)
        {
            moveCandidateFromEdenToMain(candidateAdr);
            return null;
        }

        // status: main generation has not enough room - need to check entries in eden generation against entries in
        // probation area.

        long victimAdr = mainLruTail;
        long nextVictimAdr;


        // TODO following code compares one entry in eden with one entry in probation (starting at the tail).
        // It feels that it is ok to do it like that - but not sure.

        LongArrayList derefList = null;
        long probationUsed = probationUsed();
        for (;bytes > edenFreeCapacity && probationUsed > 0L; candidateAdr = nextCandidateAdr, victimAdr = nextVictimAdr)
        {
            if (candidateAdr == 0L)
                throw new AssertionError();
            if (victimAdr == 0L)
                throw new AssertionError();

            nextCandidateAdr = HashEntries.getLRUPrev(candidateAdr);
            nextVictimAdr = HashEntries.getLRUPrev(victimAdr);

            int candidateFreq = frequencySketch.frequency(HashEntries.getHash(candidateAdr));
            int victimFreq = frequencySketch.frequency(HashEntries.getHash(victimAdr));

            probationUsed -= HashEntries.getAllocLen(victimAdr);

            if (admit(candidateFreq, victimFreq))
            {
                // evict victim from main generation & move candidate to main generation

                derefList = evictEntry(derefList, victimAdr);

                moveCandidateFromEdenToMain(candidateAdr);
            }
            else
            {
                // candidate not admitted, evict it

                derefList = evictEntry(derefList, candidateAdr);
            }
        }

        return derefList;
    }

    boolean hasFreeSpaceForNewEntry(long bytes)
    {
        return edenFreeCapacity >= bytes;
    }

    private LongArrayList evictEntry(LongArrayList derefList, long targetAdr)
    {
        removeInternal(targetAdr, -1L, true);
        size--;
        evictedEntries++;
        if (derefList == null)
            derefList = new LongArrayList();
        derefList.add(targetAdr);
        return derefList;
    }

    private void moveCandidateFromEdenToMain(long candidateAdr)
    {
        removeFromLruAndUpdateCapacity(candidateAdr);
        HashEntries.setGeneration(candidateAdr, Util.GEN_MAIN);
        addToLruAndUpdateCapacity(candidateAdr);
    }

    private long probationUsed()
    {
        //                                          Split           MainCapacity
        //              protected                     |    probation    |
        // -------------------------------------------|-----------------|
        //
        //
        //long protectedSize = mainCapacity - probationCapacity;
        //long mainUsed = mainCapacity - mainFreeCapacity;
        //long probationUsed = mainUsed - protectedSize;
        // -->                 (mainCapacity - mainFreeCapacity) - (mainCapacity - probationCapacity)
        // -->                 mainCapacity - mainFreeCapacity - mainCapacity + probationCapacity
        // -->                 - mainFreeCapacity + probationCapacity
        return - mainFreeCapacity + probationCapacity;
    }

    private boolean admit(int candidateFreq, int victimFreq)
    {
        if (candidateFreq > victimFreq) {
            return true;
        } else if (candidateFreq <= 5) {
            // The maximum frequency is 15 and halved to 7 after a reset to age the history. An attack
            // exploits that a hot candidate is rejected in favor of a hot victim. The threshold of a warm
            // candidate reduces the number of random acceptances to minimize the impact on the hit rate.
            return false;
        }

        // only admit a small number of entries to pass admission filter on a candidate/victim frequency tie
        return frequencySketch.tieAdmit();
    }

    void addToLruAndUpdateCapacity(long hashEntryAdr)
    {
        int gen = HashEntries.getGeneration(hashEntryAdr);

        long h = lruHead(gen);
        HashEntries.setLRUNext(hashEntryAdr, h);
        if (h != 0L)
            HashEntries.setLRUPrev(h, hashEntryAdr);
        HashEntries.setLRUPrev(hashEntryAdr, 0L);
        lruHead(gen, hashEntryAdr);

        if (lruTail(gen) == 0L)
            lruTail(gen, hashEntryAdr);

        adjustFreeCapacity(gen, -HashEntries.getAllocLen(hashEntryAdr));
    }

    void removeFromLruAndUpdateCapacity(long hashEntryAdr)
    {
        int gen = HashEntries.getGeneration(hashEntryAdr);

        long next = HashEntries.getLRUNext(hashEntryAdr);
        long prev = HashEntries.getLRUPrev(hashEntryAdr);

        if (lruHead(gen) == hashEntryAdr)
            lruHead(gen, next);
        if (lruTail(gen) == hashEntryAdr)
            lruTail(gen, prev);

        if (next != 0L)
            HashEntries.setLRUPrev(next, prev);
        if (prev != 0L)
            HashEntries.setLRUNext(prev, next);

        adjustFreeCapacity(gen, HashEntries.getAllocLen(hashEntryAdr));
    }

    void clearLruAndCapacity()
    {
        edenLruHead = edenLruTail =
        mainLruHead = mainLruTail = 0L;

        edenFreeCapacity = edenCapacity;
        mainFreeCapacity = mainCapacity;
    }

    long[] hotN(int n)
    {
        boolean wasFirst = lock();
        try
        {
            long[] r = new long[n];
            int i = 0;
            for (long hashEntryAdr = mainLruHead;
                 hashEntryAdr != 0L && i < n;
                 hashEntryAdr = HashEntries.getLRUNext(hashEntryAdr))
            {
                r[i++] = hashEntryAdr;
                HashEntries.reference(hashEntryAdr);
            }
            for (long hashEntryAdr = edenLruHead;
                 hashEntryAdr != 0L && i < n;
                 hashEntryAdr = HashEntries.getLRUNext(hashEntryAdr))
            {
                r[i++] = hashEntryAdr;
                HashEntries.reference(hashEntryAdr);
            }
            return r;
        }
        finally
        {
            unlock(wasFirst);
        }
    }

    void replaceSentinelInLruAndUpdateCapacity(long hashEntryAdr, long newHashEntryAdr, long bytes)
    {
        // TODO also handle the case, that the sentinel has been evicted

        int gen = HashEntries.getGeneration(hashEntryAdr);

        HashEntries.setGeneration(newHashEntryAdr, gen);

        long next = HashEntries.getLRUNext(hashEntryAdr);
        long prev = HashEntries.getLRUPrev(hashEntryAdr);

        HashEntries.setLRUNext(newHashEntryAdr, next);
        HashEntries.setLRUPrev(newHashEntryAdr, prev);

        if (lruHead(gen) == hashEntryAdr)
            lruHead(gen, newHashEntryAdr);
        if (lruTail(gen) == hashEntryAdr)
            lruTail(gen, newHashEntryAdr);

        if (next != 0L)
            HashEntries.setLRUPrev(next, newHashEntryAdr);
        if (prev != 0L)
            HashEntries.setLRUNext(prev, newHashEntryAdr);

        // note: only need to add bytes since this method only replaces a sentinel with the real value
        adjustFreeCapacity(gen, -bytes);
    }

    void touch(long hashEntryAdr)
    {
        frequencySketch.increment(HashEntries.getHash(hashEntryAdr));

        int gen = HashEntries.getGeneration(hashEntryAdr);

        long head = lruHead(gen);

        if (head == hashEntryAdr)
            // short-cut - entry already at LRU head
            return;

        // LRU stuff

        long next = HashEntries.getAndSetLRUNext(hashEntryAdr, head);
        long prev = HashEntries.getAndSetLRUPrev(hashEntryAdr, 0L);

        long tail = lruTail(gen);
        if (tail == hashEntryAdr)
            lruTail(gen, prev == 0L ? hashEntryAdr : prev);
        else if (tail == 0L)
            lruTail(gen, hashEntryAdr);

        if (next != 0L)
            HashEntries.setLRUPrev(next, prev);
        if (prev != 0L)
            HashEntries.setLRUNext(prev, next);

        // LRU stuff (basically an add to LRU linked list)

        if (head != 0L)
            HashEntries.setLRUPrev(head, hashEntryAdr);
        lruHead(gen, hashEntryAdr);

    }

    private void adjustFreeCapacity(int gen, long amount)
    {
        switch (gen)
        {
            case Util.GEN_EDEN: edenFreeCapacity += amount; break;
            case Util.GEN_MAIN: mainFreeCapacity += amount; break;
        }
    }

    private long lruHead(int gen)
    {
        switch (gen)
        {
            case Util.GEN_EDEN: return edenLruHead;
            case Util.GEN_MAIN: return mainLruHead;
        }
        return 0L;
    }

    private void lruHead(int gen, long hashEntryAdr)
    {
        switch (gen)
        {
            case Util.GEN_EDEN: edenLruHead = hashEntryAdr; break;
            case Util.GEN_MAIN: mainLruHead = hashEntryAdr; break;
        }
    }

    private long lruTail(int gen)
    {
        switch (gen)
        {
            case Util.GEN_EDEN: return edenLruTail;
            case Util.GEN_MAIN: return mainLruTail;
        }
        return 0L;
    }

    private void lruTail(int gen, long hashEntryAdr)
    {
        switch (gen)
        {
            case Util.GEN_EDEN: edenLruTail = hashEntryAdr; break;
            case Util.GEN_MAIN: mainLruTail = hashEntryAdr; break;
        }
    }
}
