/*

* Copyright (c) 2006 Nokia Corporation and/or its subsidiary(-ies).

* All rights reserved.

* This component and the accompanying materials are made available

* under the terms of the License "Eclipse Public License v1.0"

* which accompanies this distribution, and is available

* at the URL "http://www.eclipse.org/legal/epl-v10.html".

*

* Initial Contributors:

* Nokia Corporation - initial contribution.

*

* Contributors:

*

* Description:  Implementation of CHttpCacheEvictionHandler 

*

*/

// INCLUDE FILES

#include "HttpCacheEvictionHandler.h"

#include "HttpCacheEntry.h"

#include "HttpCacheUtil.h"

// EXTERNAL DATA STRUCTURES

// EXTERNAL FUNCTION PROTOTYPES

// CONSTANTS

// MACROS

// from KHTML loader.cpp

#define FAST_LOG2(_log2,_n)   \

      unsigned int j_ = (unsigned int)(_n);   \

      (_log2) = 0;                    \

      if ((j_) & ((j_)-1))            \

      (_log2) += 1;               \

      if ((j_) >> 16)                 \

      (_log2) += 16, (j_) >>= 16; \

      if ((j_) >> 8)                  \

      (_log2) += 8, (j_) >>= 8;   \

      if ((j_) >> 4)                  \

      (_log2) += 4, (j_) >>= 4;   \

      if ((j_) >> 2)                  \

      (_log2) += 2, (j_) >>= 2;   \

      if ((j_) >> 1)                  \

      (_log2) += 1;

const TUint KHttpCacheBucketNum = 5;

// LOCAL CONSTANTS AND MACROS

// MODULE DATA STRUCTURES

// LOCAL FUNCTION PROTOTYPES

// FORWARD DECLARATIONS

// ============================= LOCAL FUNCTIONS ===============================

// ============================ MEMBER FUNCTIONS ===============================

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::CHttpCacheEvictionHandler

// C++ default constructor can NOT contain any code, that

// might leave.

// -----------------------------------------------------------------------------

//

CHttpCacheEvictionHandler::CHttpCacheEvictionHandler()

    {

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::ConstructL

// Symbian 2nd phase constructor can leave.

// -----------------------------------------------------------------------------

//

void CHttpCacheEvictionHandler::ConstructL()

    {

    // 5 buckets

    // LRU, size/nref = 1 to 1

    // LRU, size/nref = 2 to 3

    // LRU, size/nref = 4 to 7

    // LRU, size/nref = 8 to 15

    // LRU, size/nref > 15

    iBuckets = new(ELeave)CArrayPtrFlat<TBucket>( KHttpCacheBucketNum );

    for( TInt i = 0; i < KHttpCacheBucketNum; i++ )

        {

        TBucket* bucket = new(ELeave)TBucket( CHttpCacheEntry::iOffset );

        iBuckets->AppendL( bucket );

        TBucket* bucketi = iBuckets->At( i );

        }

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::NewL

// Two-phased constructor.

// -----------------------------------------------------------------------------

//

CHttpCacheEvictionHandler* CHttpCacheEvictionHandler::NewL()

    {

    CHttpCacheEvictionHandler* self = new( ELeave ) CHttpCacheEvictionHandler();

    CleanupStack::PushL( self );

    self->ConstructL();

    CleanupStack::Pop();

    return self;

    }

// Destructor

CHttpCacheEvictionHandler::~CHttpCacheEvictionHandler()

    {

    if (iBuckets)

        {    	

	    // delete the entries    

	    for( TInt i=0; i<iBuckets->Count(); ++i )

	        delete iBuckets->At( i );	   

        }        

        delete iBuckets;

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::InsertL

//

// -----------------------------------------------------------------------------

//

void CHttpCacheEvictionHandler::Insert(

    CHttpCacheEntry& aCacheEntry )

    {

#ifdef __CACHELOG__

    HttpCacheUtil::WriteUrlToLog( 0, _L( "Eviction table: item is inserted:" ), aCacheEntry.Url() );

    // check double insert

    CHttpCacheEntry* entry;

    for( TInt i = 0; i < KHttpCacheBucketNum; i++ )

        {

        TBucketIter bucketIter( *iBuckets->At( i ) );

        //

        bucketIter.SetToFirst();

        while( ( entry = bucketIter++ ) != NULL )

            {

            __ASSERT_DEBUG( ( entry != &aCacheEntry ) , User::Panic( _L("cacheHandler Panic"), KErrCorrupt ) );

            }

        }

    //

    HttpCacheUtil::WriteLog( 0, _L( "insert entry to eviction table:" ), BucketIndex( FastLog2( aCacheEntry.Size() ) ) );

#endif // __CACHELOG__

    // Objects are classified into a limited number of groups according to log2(Si/refi)

    // caclulate to which bucket it goes.

    // buckets are orderd by LRU

    Bucket( BucketIndex( FastLog2( aCacheEntry.Size() / aCacheEntry.Ref() ) ) )->AddLast( aCacheEntry );

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::Accessed

//

// -----------------------------------------------------------------------------

//

void CHttpCacheEvictionHandler::Accessed(

    CHttpCacheEntry& aCacheEntry )

    {

    HttpCacheUtil::WriteUrlToLog( 0, _L( "Eviction table: item is accessed:" ), aCacheEntry.Url() );

    // first check where it is now

    TInt oldRef( aCacheEntry.Ref() - 1 );

    if( oldRef > 0 )

        {

        //

        // buckets are orderd by LRU

        // see if we need to move it to a new bucket

        TInt currentBucketIndex( BucketIndex( FastLog2( aCacheEntry.Size() / oldRef ) ) );

        TInt newBucketIndex( BucketIndex( FastLog2( aCacheEntry.Size() / aCacheEntry.Ref() ) ) );

        // check if the item is really there

        TBool itemOk( ItemIsInBucket( currentBucketIndex, aCacheEntry ) );

        if( itemOk )

            {

            HttpCacheUtil::WriteLog( 0, _L( "item is in bucket:" ), currentBucketIndex );

            if( currentBucketIndex == newBucketIndex )

                {

                HttpCacheUtil::WriteLog( 0, _L( "move entry to the end of the bucket. it's safe there" ) );

                TBucket* bucket( Bucket( currentBucketIndex ) );

                // move it to the end

                if( !bucket->IsLast( &aCacheEntry ) )

                    {

                    bucket->Remove( aCacheEntry );

                    bucket->AddLast( aCacheEntry );

                    }

                }

            else

                {

                HttpCacheUtil::WriteLog( 0, _L( "move item to a new bucket" ), newBucketIndex );

                // new bucket

                TBucket* currBucket( Bucket( currentBucketIndex ) );

                TBucket* newBucket( Bucket( newBucketIndex ) );

                // remove from the current and add it to the

                // new as last item

                // make sure the item is there

                // move it to the end

                currBucket->Remove( aCacheEntry );

                newBucket->AddLast( aCacheEntry );

                }

            }

        else

            {

            // assert

            __ASSERT_DEBUG( EFalse , User::Panic( _L("cacheHandler Panic"), KErrCorrupt ) );

            }

        }

    else if( oldRef == 0 )

        {

        // first -original access. ignore it

        // as it is already placed at insert()

        }

    else

        {

        // entry with 0 starting refcount??? doh.

        __ASSERT_DEBUG( EFalse , User::Panic( _L("cacheHandler Panic"), KErrCorrupt ) );

        }

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::Changed

//

// -----------------------------------------------------------------------------

//

void CHttpCacheEvictionHandler::Changed(

    CHttpCacheEntry& /*aCacheEntry*/ )

    {

    // check if size changed

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::Remove

//

// -----------------------------------------------------------------------------

//

void CHttpCacheEvictionHandler::Remove(

    CHttpCacheEntry& aCacheEntry )

    {

    HttpCacheUtil::WriteUrlToLog( 0, _L( "Eviction table: try to remove item:" ), aCacheEntry.Url() );

    //

    TInt sizeFreqVal( FastLog2( aCacheEntry.Size() / aCacheEntry.Ref() ) );

    // check if the item is in the right bucket

    TInt bucketIndex( BucketIndex( sizeFreqVal ) );

    TBucket* bucket( Bucket( bucketIndex ) );

    TBool itemOk( ItemIsInBucket( bucketIndex, aCacheEntry ) );

    if( itemOk )

        {

        //

        HttpCacheUtil::WriteLog( 0, _L( "removed from bucket:" ), bucketIndex );

        bucket->Remove( aCacheEntry );

        }

#ifdef __CACHELOG__

    else

        {

         HttpCacheUtil::WriteLog( 0, _L( "item is not in bucket no." ), bucketIndex );

        }

#endif // __CACHELOG__

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::Evict

//

// -----------------------------------------------------------------------------

//

CArrayPtrFlat<CHttpCacheEntry>* CHttpCacheEvictionHandler::EvictL(

    TInt aSpaceNeeded )

    {

    HttpCacheUtil::WriteLog( 0, _L( "need space:" ), aSpaceNeeded );

#ifdef __CACHELOG__

    LogBuckets();

#endif // __CACHELOG__

    //

    CArrayPtrFlat<CHttpCacheEntry>* evictedEntries = new(ELeave)CArrayPtrFlat<CHttpCacheEntry>( 10 );

    CleanupStack::PushL( evictedEntries );

    //

    // Each group is managed using a LRU

    // policy. The extended cost-to-size model is applied to the

    // eviction candidates from all nonempty groups, purging the

    // object with largest ( DeltaT * Size / Ref ) ->delataT == curr time - last accessed

    TTime currTime;

    currTime.HomeTime();

    //

    while( aSpaceNeeded > 0 )

        {

        // take one item from each bucket and

        // check who has to go

        TInt bucketInd( -1 );

        TInt maxVal( -1 );

        TTimeIntervalSeconds secInt;

        CHttpCacheEntry* candidate = NULL;

        for( TInt i = 0; i < KHttpCacheBucketNum; i++ )

            {

            CHttpCacheEntry* entry = NULL;

            TBucket* bucket = iBuckets->At( i );

            // get the first (LRU) item from each bucket

            if( !bucket->IsEmpty() )

                {

                entry = bucket->First();

                }

            // evacuate nonactive entries only

            if( entry && entry->State() == CHttpCacheEntry::ECacheComplete )

                {

                // watch out for 32 bit. it might overflow secInt.

                currTime.SecondsFrom( entry->LastAccessed(), secInt );

                TInt val( secInt.Int() * entry->Size() / entry->Ref() );

                // get the object with largest ( DeltaT * Size / Ref )

                if( val > maxVal )

                    {

                    maxVal = val;

                    bucketInd = i;

                    candidate = entry;

                    }

                }

            }

        // remove from the bucket

        // add it to the evicted list

        // reduce space needed size

        if( candidate )

            {

#ifdef __CACHELOG__

            // no protected entries should be evacuated

            if( candidate->Protected() )

            	{

	            HttpCacheUtil::WriteUrlToLog( 0, _L( "PROTECTED entry is about to be removed" ), candidate->Url() );

            	}

            //

            HttpCacheUtil::WriteUrlToLog( 0, _L( "entry to remove:" ), candidate->Url() );

#endif //__CACHELOG__

            //

            iBuckets->At( bucketInd )->Remove( *candidate );

            // reduce size

            aSpaceNeeded-= candidate->Size();

            aSpaceNeeded-= candidate->HeaderSize();

            //

            evictedEntries->AppendL( candidate );

            //

            HttpCacheUtil::WriteLog( 0, _L( "more space needed" ), aSpaceNeeded );

            }

        else

            {

            // no candidate no free

            break;

            }

        }

    CleanupStack::Pop(); // evictedEntries

    return evictedEntries;

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::RemoveAll

//

// -----------------------------------------------------------------------------

//

void CHttpCacheEvictionHandler::RemoveAll()

    {

    HttpCacheUtil::WriteLog( 0, _L( "Eviction table: remove all item:" ) );

    //

    for( TInt i = 0; i < KHttpCacheBucketNum; i++ )

        {

        iBuckets->At( i )->Reset();

        //

        }

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::Bucket

//

// -----------------------------------------------------------------------------

//

TBucket* CHttpCacheEvictionHandler::Bucket(

    TInt aIndex )

    {

    return iBuckets->At( aIndex );

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::BucketIndex

//

// -----------------------------------------------------------------------------

//

TInt CHttpCacheEvictionHandler::BucketIndex(

    TInt aSizeFrequencyValue )

    {

    // last bucket by default

    TInt index( 4 );

    // supports only 5 buckets at the moment

    if( aSizeFrequencyValue == 1 )

        {

        index = 0;

        }

    else if( aSizeFrequencyValue < 4 )

        {

        index = 1;

        }

    else if( aSizeFrequencyValue < 8 )

        {

        index = 2;

        }

    else if( aSizeFrequencyValue < 16 )

        {

        index = 3;

        }

    return index;

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::ItemIsInBucket

//

// -----------------------------------------------------------------------------

//

TBool CHttpCacheEvictionHandler::ItemIsInBucket(

    TInt aBucketIndex,

    const CHttpCacheEntry& aCacheEntry )

    {

    TBool found( EFalse );

    CHttpCacheEntry* entry;

    TBucketIter bucketIter( *(iBuckets->At( aBucketIndex )) );

    //

    bucketIter.SetToFirst();

    while( ( entry = bucketIter++ ) != NULL )

        {

        if( entry == &aCacheEntry )

            {

            found = ETrue;

            break;

            }

        }

#ifdef __CACHELOG__

    if( !found )

        {

        HttpCacheUtil::WriteLog( 0, _L( "Eviction table: item NOT FOUND" ) );

        }

#endif // __CACHELOG__

    return found;

    }

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::FastLog2

//

// -----------------------------------------------------------------------------

//

TInt CHttpCacheEvictionHandler::FastLog2(

    TUint aNum )

    {

    TInt log2;

    FAST_LOG2( log2, aNum );

    return log2;

    }

#ifdef __CACHELOG__

// -----------------------------------------------------------------------------

// CHttpCacheEvictionHandler::LogBuckets

//

// -----------------------------------------------------------------------------

//

void CHttpCacheEvictionHandler::LogBuckets()

    {

    CHttpCacheEntry* entry;

    for( TInt i = 0; i < KHttpCacheBucketNum; i++ )

        {

        HttpCacheUtil::WriteLog( 0, _L( "------------------------------" ), i );

        TBucketIter bucketIter( *(iBuckets->At( i )) );

        //

        bucketIter.SetToFirst();

        while( ( entry = bucketIter++ ) != NULL )

            {

            _LIT( KDateString,"%D%M%Y%/0%1%/1%2%/2%3%/3 %-B%:0%J%:1%T%:2%S%.%*C4%:3%+B");

            _LIT( KRefSizeString,"size: %d refcount:%d");

            TBuf<50> refStr;

            TBuf<50> lastAccessedStr;

            TTime lastAccessed( entry->LastAccessed() );

            lastAccessed.FormatL( lastAccessedStr, KDateString );

            // add size/refcount

            refStr.Format( KRefSizeString, entry->Size(), entry->Ref() );

            // copy to 8bit string

            HttpCacheUtil::WriteUrlToLog( 0, refStr, entry->Url() );

            HttpCacheUtil::WriteLog( 0, lastAccessedStr );

            }

        }

    }

#endif // __CACHELOG__

//  End of File