/******************************************************************************
 *
 * Project:  VSI Virtual File System
 * Purpose:  Implementation of caching IO layer.
 * Author:   Frank Warmerdam, warmerdam@pobox.com
 *
 ******************************************************************************
 * Copyright (c) 2011, Frank Warmerdam <warmerdam@pobox.com>
 * Copyright (c) 2011-2014, Even Rouault <even dot rouault at spatialys.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 ****************************************************************************/

#include "cpl_port.h"
#include "cpl_vsi_virtual.h"

#include <cstddef>
#include <cstring>
#if HAVE_FCNTL_H
#include <fcntl.h>
#endif

#include <algorithm>
#include <limits>
#include <map>
#include <memory>
#include <utility>

#include "cpl_conv.h"
#include "cpl_error.h"
#include "cpl_vsi.h"
#include "cpl_vsi_virtual.h"
#include "cpl_mem_cache.h"
#include "cpl_noncopyablevector.h"

//! @cond Doxygen_Suppress



/************************************************************************/
/* ==================================================================== */
/*                             VSICachedFile                            */
/* ==================================================================== */
/************************************************************************/

class VSICachedFile final : public VSIVirtualHandle
{
    CPL_DISALLOW_COPY_ASSIGN(VSICachedFile)

  public:
    VSICachedFile( VSIVirtualHandle *poBaseHandle,
                   size_t nChunkSize,
                   size_t nCacheSize );
    ~VSICachedFile() override { VSICachedFile::Close(); }

    bool         LoadBlocks( vsi_l_offset nStartBlock, size_t nBlockCount,
                              void *pBuffer, size_t nBufferSize );

    std::unique_ptr<VSIVirtualHandle> m_poBase{};

    vsi_l_offset  m_nOffset = 0;
    vsi_l_offset  m_nFileSize = 0;

    size_t        m_nChunkSize = 0;
    lru11::Cache<vsi_l_offset, cpl::NonCopyableVector<GByte>> m_oCache; // can only been initialized in constructor

    bool           m_bEOF = false;

    int Seek( vsi_l_offset nOffset, int nWhence ) override;
    vsi_l_offset Tell() override;
    size_t Read( void *pBuffer, size_t nSize,
                 size_t nMemb ) override;
    int ReadMultiRange( int nRanges, void ** ppData,
                        const vsi_l_offset* panOffsets,
                        const size_t* panSizes ) override;

    size_t Write( const void *pBuffer, size_t nSize,
                  size_t nMemb ) override;
    int Eof() override;
    int Flush() override;
    int Close() override;
    void *GetNativeFileDescriptor() override
        { return m_poBase->GetNativeFileDescriptor(); }

    bool HasPRead() const override { return m_poBase->HasPRead(); }
    size_t PRead( void* pBuffer, size_t nSize, vsi_l_offset nOffset ) const override
        { return m_poBase->PRead(pBuffer, nSize, nOffset); }
};

/************************************************************************/
/*                           GetCacheMax()                              */
/************************************************************************/

static size_t GetCacheMax(size_t nCacheSize)
{
    return nCacheSize ? nCacheSize :
        static_cast<size_t>(std::min(
            static_cast<GUIntBig>(std::numeric_limits<size_t>::max() / 2),
            CPLScanUIntBig(
                 CPLGetConfigOption( "VSI_CACHE_SIZE", "25000000" ), 40 )));
}

/************************************************************************/
/*                           DIV_ROUND_UP()                             */
/************************************************************************/

template<class T> inline T DIV_ROUND_UP(T a, T b)
{
    return a / b + (((a % b) == 0) ? 0 : 1);
}

/************************************************************************/
/*                           VSICachedFile()                            */
/************************************************************************/

VSICachedFile::VSICachedFile( VSIVirtualHandle *poBaseHandle, size_t nChunkSize,
                              size_t nCacheSize ) :
    m_poBase(poBaseHandle),
    m_nChunkSize(nChunkSize ? nChunkSize : 32768),
    m_oCache{DIV_ROUND_UP(GetCacheMax(nCacheSize), m_nChunkSize), 0}
{
    m_poBase->Seek( 0, SEEK_END );
    m_nFileSize = m_poBase->Tell();
}

/************************************************************************/
/*                               Close()                                */
/************************************************************************/

int VSICachedFile::Close()

{
    m_oCache.clear();

    if( m_poBase )
    {
        m_poBase->Close();
        m_poBase.reset();
    }

    return 0;
}

/************************************************************************/
/*                                Seek()                                */
/************************************************************************/

int VSICachedFile::Seek( vsi_l_offset nReqOffset, int nWhence )

{
    m_bEOF = false;

    if( nWhence == SEEK_SET )
    {
        // Use offset directly.
    }
    else if( nWhence == SEEK_CUR )
    {
        nReqOffset += m_nOffset;
    }
    else if( nWhence == SEEK_END )
    {
        nReqOffset += m_nFileSize;
    }

    m_nOffset = nReqOffset;

    return 0;
}

/************************************************************************/
/*                                Tell()                                */
/************************************************************************/

vsi_l_offset VSICachedFile::Tell()

{
    return m_nOffset;
}

/************************************************************************/
/*                             LoadBlocks()                             */
/*                                                                      */
/*      Load the desired set of blocks.  Use pBuffer as a temporary     */
/*      buffer if it would be helpful.                                  */
/************************************************************************/

bool VSICachedFile::LoadBlocks( vsi_l_offset nStartBlock, size_t nBlockCount,
                                void *pBuffer, size_t nBufferSize )

{
    if( nBlockCount == 0 )
        return true;

/* -------------------------------------------------------------------- */
/*      When we want to load only one block, we can directly load it    */
/*      into the target buffer with no concern about intermediaries.    */
/* -------------------------------------------------------------------- */
    if( nBlockCount == 1 )
    {
        if( m_poBase->Seek( static_cast<vsi_l_offset>(nStartBlock) * m_nChunkSize,
                          SEEK_SET ) != 0 )
        {
            return false;
        }

        try
        {
            cpl::NonCopyableVector<GByte> oData(m_nChunkSize);
            const auto nDataRead =
                m_poBase->Read( oData.data(), 1, m_nChunkSize );
            if( nDataRead == 0 )
                return false;
            oData.resize(nDataRead);

            m_oCache.insert(nStartBlock, std::move(oData));
        }
        catch( const std::exception & )
        {
            CPLError(CE_Failure, CPLE_OutOfMemory,
                     "Out of memory situation in VSICachedFile::LoadBlocks()");
            return false;
        }

        return true;
    }

/* -------------------------------------------------------------------- */
/*      If the buffer is quite large but not quite large enough to      */
/*      hold all the blocks we will take the pain of splitting the      */
/*      io request in two in order to avoid allocating a large          */
/*      temporary buffer.                                               */
/* -------------------------------------------------------------------- */
    if( nBufferSize > m_nChunkSize * 20
        && nBufferSize < nBlockCount * m_nChunkSize )
    {
        if( !LoadBlocks( nStartBlock, 2, pBuffer, nBufferSize ) )
            return false;

        return LoadBlocks( nStartBlock+2, nBlockCount-2, pBuffer, nBufferSize );
    }

    if( m_poBase->Seek( static_cast<vsi_l_offset>(nStartBlock) * m_nChunkSize,
                      SEEK_SET ) != 0 )
        return false;

/* -------------------------------------------------------------------- */
/*      Do we need to allocate our own buffer?                          */
/* -------------------------------------------------------------------- */
    GByte *pabyWorkBuffer = static_cast<GByte *>(pBuffer);

    if( nBufferSize < m_nChunkSize * nBlockCount )
    {
        pabyWorkBuffer =
            static_cast<GByte *>( VSI_MALLOC_VERBOSE(m_nChunkSize * nBlockCount) );
        if( pabyWorkBuffer == nullptr )
            return false;
    }

/* -------------------------------------------------------------------- */
/*      Read the whole request into the working buffer.                 */
/* -------------------------------------------------------------------- */

    const size_t nDataRead =
        m_poBase->Read( pabyWorkBuffer, 1, nBlockCount*m_nChunkSize);

    if( nBlockCount * m_nChunkSize > nDataRead + m_nChunkSize - 1 )
        nBlockCount = (nDataRead + m_nChunkSize - 1) / m_nChunkSize;

    bool ret = true;
    for( size_t i = 0; i < nBlockCount; i++ )
    {
        const vsi_l_offset iBlock = nStartBlock + i;

        const auto nDataFilled = ( nDataRead >= (i+1) * m_nChunkSize ) ?
            m_nChunkSize :  nDataRead - i*m_nChunkSize;
        try
        {
            cpl::NonCopyableVector<GByte> oData(nDataFilled);

            memcpy( oData.data(), pabyWorkBuffer + i*m_nChunkSize,
                    nDataFilled );

            m_oCache.insert(iBlock, std::move(oData));
        }
        catch( const std::exception & )
        {
            CPLError(CE_Failure, CPLE_OutOfMemory,
                     "Out of memory situation in VSICachedFile::LoadBlocks()");
            ret = false;
            break;
        }

    }

    if( pabyWorkBuffer != pBuffer )
        CPLFree( pabyWorkBuffer );

    return ret;
}

/************************************************************************/
/*                                Read()                                */
/************************************************************************/

size_t VSICachedFile::Read( void * pBuffer, size_t nSize, size_t nCount )

{
    if( nSize == 0 || nCount == 0 )
        return 0;
    const size_t nRequestedBytes = nSize * nCount;

    // nFileSize might be set wrongly to 0 by underlying layers, such as
    // /vsicurl_streaming/https://query.data.world/s/jgsghstpphjhicstradhy5kpjwrnfy
    if( m_nFileSize > 0 && m_nOffset >= m_nFileSize )
    {
        m_bEOF = true;
        return 0;
    }

/* ==================================================================== */
/*      Make sure the cache is loaded for the whole request region.     */
/* ==================================================================== */
    const vsi_l_offset nStartBlock = m_nOffset / m_nChunkSize;
    const vsi_l_offset nEndBlock =
        (m_nOffset + nRequestedBytes - 1) / m_nChunkSize;

    for( vsi_l_offset iBlock = nStartBlock; iBlock <= nEndBlock; iBlock++ )
    {
        if( !m_oCache.contains(iBlock) )
        {
            size_t nBlocksToLoad = 1;
            while( iBlock + nBlocksToLoad <= nEndBlock &&
                   !m_oCache.contains(iBlock + nBlocksToLoad) )
            {
                nBlocksToLoad++;
            }

            LoadBlocks( iBlock, nBlocksToLoad, pBuffer, nRequestedBytes );
        }
    }

/* ==================================================================== */
/*      Copy data into the target buffer to the extent possible.        */
/* ==================================================================== */
    size_t nAmountCopied = 0;

    while( nAmountCopied < nRequestedBytes )
    {
        const vsi_l_offset iBlock = (m_nOffset + nAmountCopied) / m_nChunkSize;
        const cpl::NonCopyableVector<GByte>* poData = m_oCache.getPtr(iBlock);
        if( poData == nullptr )
        {
            // We can reach that point when the amount to read exceeds
            // the cache size.
            LoadBlocks(iBlock, 1,
                       static_cast<GByte *>(pBuffer) + nAmountCopied,
                       std::min(nRequestedBytes - nAmountCopied, m_nChunkSize));
            poData = m_oCache.getPtr(iBlock);
            if( poData == nullptr )
            {
                break;
            }
        }

        const vsi_l_offset nStartOffset =
            static_cast<vsi_l_offset>(iBlock) * m_nChunkSize;
        if(nStartOffset + poData->size() < nAmountCopied + m_nOffset)
            break;
        const size_t nThisCopy = std::min(
            nRequestedBytes - nAmountCopied,
            static_cast<size_t>(
                ((nStartOffset + poData->size())
                 - nAmountCopied - m_nOffset)));
        if( nThisCopy == 0 )
            break;

        memcpy( static_cast<GByte *>(pBuffer) + nAmountCopied,
                poData->data()
                + (m_nOffset + nAmountCopied) - nStartOffset,
                nThisCopy );

        nAmountCopied += nThisCopy;
    }

    m_nOffset += nAmountCopied;

    const size_t nRet = nAmountCopied / nSize;
    if( nRet != nCount )
        m_bEOF = true;
    return nRet;
}

/************************************************************************/
/*                           ReadMultiRange()                           */
/************************************************************************/

int VSICachedFile::ReadMultiRange( int const nRanges, void ** const ppData,
                                   const vsi_l_offset* const panOffsets,
                                   const size_t* const panSizes )
{
    // If the base is /vsicurl/
    return m_poBase->ReadMultiRange( nRanges, ppData, panOffsets, panSizes );
}

/************************************************************************/
/*                               Write()                                */
/************************************************************************/

size_t VSICachedFile::Write( const void * /* pBuffer */,
                             size_t /*nSize */ ,
                             size_t /* nCount */ )
{
    return 0;
}

/************************************************************************/
/*                                Eof()                                 */
/************************************************************************/

int VSICachedFile::Eof()

{
    return m_bEOF;
}

/************************************************************************/
/*                               Flush()                                */
/************************************************************************/

int VSICachedFile::Flush()

{
    return 0;
}

//! @endcond

/************************************************************************/
/*                        VSICreateCachedFile()                         */
/************************************************************************/

VSIVirtualHandle *
VSICreateCachedFile( VSIVirtualHandle *poBaseHandle,
                     size_t nChunkSize, size_t nCacheSize )

{
    return new VSICachedFile( poBaseHandle, nChunkSize, nCacheSize );
}
