/***************************************************************************
 *  include/stxxl/bits/mng/prefetch_pool.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2003-2004 Roman Dementiev <dementiev@mpi-sb.mpg.de>
 *  Copyright (C) 2009 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
 *
 *  Distributed under the Boost Software License, Version 1.0.
 *  (See accompanying file LICENSE_1_0.txt or copy at
 *  http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_PREFETCH_POOL_HEADER
#define STXXL_PREFETCH_POOL_HEADER

#include <list>

#ifdef STXXL_BOOST_CONFIG
 #include <boost/config.hpp>
#endif

#include <stxxl/bits/mng/write_pool.h>
#include <stxxl/bits/compat_hash_map.h>


__STXXL_BEGIN_NAMESPACE

//! \addtogroup schedlayer
//! \{

//! \brief Implements dynamically resizable prefetching pool
template <class BlockType>
class prefetch_pool : private noncopyable
{
public:
    typedef BlockType block_type;
    typedef typename block_type::bid_type bid_type;

protected:
    struct bid_hash
    {
        size_t operator () (const bid_type & bid) const
        {
            size_t result = size_t(bid.storage) +
                            size_t(bid.offset & 0xffffffff) + size_t(bid.offset >> 32);
            return result;
        }
#ifdef BOOST_MSVC
        bool operator () (const bid_type & a, const bid_type & b) const
        {
            return (a.storage < b.storage) || (a.storage == b.storage && a.offset < b.offset);
        }
        enum
        {                               // parameters for hash table
            bucket_size = 4,            // 0 < bucket_size
            min_buckets = 8             // min_buckets = 2 ^^ N, 0 < N
        };
#endif
    };
    typedef std::pair<block_type *, request_ptr> busy_entry;
    typedef typename compat_hash_map<bid_type, busy_entry, bid_hash>::result hash_map_type;
    typedef typename std::list<block_type *>::iterator free_blocks_iterator;
    typedef typename hash_map_type::iterator busy_blocks_iterator;

    // contains free prefetch blocks
    std::list<block_type *> free_blocks;
    // blocks that are in reading or already read but not retrieved by user
    hash_map_type busy_blocks;

    unsigned_type free_blocks_size;

public:
    //! \brief Constructs pool
    //! \param init_size initial number of blocks in the pool
    explicit prefetch_pool(unsigned_type init_size = 1) : free_blocks_size(init_size)
    {
        unsigned_type i = 0;
        for ( ; i < init_size; ++i)
            free_blocks.push_back(new block_type);
    }

    void swap(prefetch_pool & obj)
    {
        std::swap(free_blocks, obj.free_blocks);
        std::swap(busy_blocks, obj.busy_blocks);
        std::swap(free_blocks_size, obj.free_blocks_size);
    }

    //! \brief Waits for completion of all ongoing read requests and frees memory
    virtual ~prefetch_pool()
    {
        while (!free_blocks.empty())
        {
            delete free_blocks.back();
            free_blocks.pop_back();
        }

        try
        {
            busy_blocks_iterator i2 = busy_blocks.begin();
            for ( ; i2 != busy_blocks.end(); ++i2)
            {
                i2->second.second->wait();
                delete i2->second.first;
            }
        }
        catch (...)
        { }
    }
    //! \brief Returns number of owned blocks
    unsigned_type size() const { return free_blocks_size + busy_blocks.size(); }

    //! \brief Gives a hint for prefetching a block
    //! \param bid address of a block to be prefetched
    //! \return \c true if there was a free block to do prefetch and prefetching
    //! was scheduled, \c false otherwise
    //! \note If there are no free blocks available (all blocks
    //! are already in reading or read but not retrieved by user calling \c read
    //! method) calling \c hint function has no effect
    bool hint(bid_type bid)
    {
        // if block is already hinted, no need to hint it again
        if (in_prefetching(bid)) {
            STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " was already cached");
            return true;
        }

        if (free_blocks_size) //  only if we have a free block
        {
            --free_blocks_size;
            block_type * block = free_blocks.back();
            free_blocks.pop_back();
            STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => prefetching");
            request_ptr req = block->read(bid);
            busy_blocks[bid] = busy_entry(block, req);
            return true;
        }
        STXXL_VERBOSE2("prefetch_pool::hint bid=" << bid << " => no free blocks for prefetching");
        return false;
    }

    bool hint(bid_type bid, write_pool<block_type> & w_pool)
    {
        // if block is already hinted, no need to hint it again
        if (in_prefetching(bid)) {
            STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " was already cached");
            return true;
        }

        if (free_blocks_size) //  only if we have a free block
        {
            --free_blocks_size;
            block_type * block = free_blocks.back();
            free_blocks.pop_back();
            if (w_pool.has_request(bid))
            {
                busy_entry wp_request = w_pool.steal_request(bid);
                STXXL_VERBOSE1("prefetch_pool::hint2 bid=" << bid << " was in write cache at " << wp_request.first);
                assert(wp_request.first != 0);
                w_pool.add(block);  //in exchange
                busy_blocks[bid] = wp_request;
                return true;
            }
            STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => prefetching");
            request_ptr req = block->read(bid);
            busy_blocks[bid] = busy_entry(block, req);
            return true;
        }
        STXXL_VERBOSE2("prefetch_pool::hint2 bid=" << bid << " => no free blocks for prefetching");
        return false;
    }

    bool invalidate(bid_type bid)
    {
        busy_blocks_iterator cache_el = busy_blocks.find(bid);
        if (cache_el == busy_blocks.end())
            return false;

        // cancel request if it is a read request, there might be
        // write requests 'stolen' from a write_pool that may not be canceled
        if (cache_el->second.second->get_type() == request::READ)
            cache_el->second.second->cancel();
        // finish the request
        cache_el->second.second->wait();
        ++free_blocks_size;
        free_blocks.push_back(cache_el->second.first);
        busy_blocks.erase(cache_el);
        return true;
    }

    bool in_prefetching(bid_type bid)
    {
        return (busy_blocks.find(bid) != busy_blocks.end());
    }

    //! \brief Reads block. If this block is cached block is not read but passed from the cache
    //! \param block block object, where data to be read to. If block was cached \c block 's
    //! ownership goes to the pool and block from cache is returned in \c block value.
    //! \param bid address of the block
    //! \warning \c block parameter must be allocated dynamically using \c new .
    //! \return request pointer object of read operation
    request_ptr read(block_type * & block, bid_type bid)
    {
        busy_blocks_iterator cache_el = busy_blocks.find(bid);
        if (cache_el == busy_blocks.end())
        {
            // not cached
            STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
            return block->read(bid);
        }

        // cached
        STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists");
        ++free_blocks_size;
        free_blocks.push_back(block);
        block = cache_el->second.first;
        request_ptr result = cache_el->second.second;
        busy_blocks.erase(cache_el);
        return result;
    }

    request_ptr read(block_type * & block, bid_type bid, write_pool<block_type> & w_pool)
    {
        // try cache
        busy_blocks_iterator cache_el = busy_blocks.find(bid);
        if (cache_el != busy_blocks.end())
        {
            // cached
            STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => copy in cache exists");
            ++free_blocks_size;
            free_blocks.push_back(block);
            block = cache_el->second.first;
            request_ptr result = cache_el->second.second;
            busy_blocks.erase(cache_el);
            return result;
        }

        // try w_pool cache
        if (w_pool.has_request(bid))
        {
            busy_entry wp_request = w_pool.steal_request(bid);
            STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " was in write cache at " << wp_request.first);
            assert(wp_request.first != 0);
            w_pool.add(block);  //in exchange
            block = wp_request.first;
            return wp_request.second;
        }

        // not cached
        STXXL_VERBOSE1("prefetch_pool::read bid=" << bid << " => no copy in cache, retrieving to " << block);
        return block->read(bid);
    }

    //! \brief Resizes size of the pool
    //! \param new_size desired size of the pool. If some
    //! blocks are used for prefetching, these blocks can't be freed.
    //! Only free blocks (not in prefetching) can be freed by reducing
    //! the size of the pool calling this method.
    //! \return new size of the pool
    unsigned_type resize(unsigned_type new_size)
    {
        int_type diff = int_type(new_size) - int_type(size());
        if (diff > 0)
        {
            free_blocks_size += diff;
            while (--diff >= 0)
                free_blocks.push_back(new block_type);


            return size();
        }

        while (diff < 0 && free_blocks_size > 0)
        {
            ++diff;
            --free_blocks_size;
            delete free_blocks.back();
            free_blocks.pop_back();
        }
        return size();
    }
};

//! \}

__STXXL_END_NAMESPACE

namespace std
{
    template <class BlockType>
    void swap(stxxl::prefetch_pool<BlockType> & a,
              stxxl::prefetch_pool<BlockType> & b)
    {
        a.swap(b);
    }
}

#endif // !STXXL_PREFETCH_POOL_HEADER
// vim: et:ts=4:sw=4